合作博弈與運輸優(yōu)化

第34卷第4期四川大學(xué)學(xué)報(工程科學(xué)版)Vol.34 No.42002年7月JOURNAL OF SICHUAN UNIVERSITY( ENGINEERING SCIENCE EDITION )July 2002文章編號:1009-3087 2002 )4-0051-05合作博弈與運輸優(yōu)化張建高,鄭乃偉(重慶大學(xué)建設管理與房地產(chǎn)學(xué)院重慶400045)摘要從博弈論的角度分析了區域性大系統中的運輸問(wèn)題考慮了在這種運輸系統中由于各個(gè)子運輸系統之間的相對獨立性和彼此之間的競爭采用運籌學(xué)中通常的運輸問(wèn)題模型是無(wú)法使這樣的一個(gè)運輸系統達到最優(yōu)狀態(tài)的。理論與實(shí)踐的分析都證明要在區域性運輸大系統中實(shí)現運輸問(wèn)題的最優(yōu)解,允許各子運輸系統之間結盟是必要的。作者將合作博弈理論與運籌學(xué)中的運輸問(wèn)題模型相結合在允許子運輸系統之間結盟的條件下建立了全局運輸問(wèn)題的博弈模型,證明了該模型構成一個(gè)n人合作博弈。提出了在由若干相對獨立的子系統所構成的大系統中如何實(shí)現運輸問(wèn)題最優(yōu)方案的一-個(gè)新方法。關(guān)鍵詞運輸問(wèn)題合作博弈效用轉移聯(lián)盟中圖分類(lèi)號:0225 .文獻標識碼ACooperative Games and Optimization of Transportation SystemsZHANG Jian-gao ,ZHENG Nai-rwei( Faculty of Constuction Management and Real Estate , Chongqing Univ. , Chongqing 400045 ,China )Abstract :The paper analyzes the transportation problem of regional large system in the aspect of games , and considersthat the usual transportation problem model of operational research can not realize the optimization of above transportationsystem because of the relative independency and competition of every subsystem of the large system. The theoretical anal-ysis and practical analysis both prove that it is necessary to allow every subsystem to make coalition for realizing the opti-mization of the transportation problem in the regional large system. This paper combines cooperative games and transporta-tion problem model of operations research , etablishes game model of overall transportation problem on the condition of al-lowing the coalition of subsystems , proves that the model forms a n-person cooperative games , and proposes a new methodof realizing optimization scheme of transportation problem in large system consisting of subsystems with relative indepen-dency.Key words :transportation problem ; cooperative games ; transfer of utility coalition局系統通常是由若干子系統所構成的,并且這些子1全局運輸的博弈形式系統相對于大系統來(lái)說(shuō)通常是獨立的(不論從經(jīng)濟運籌學(xué)中的運輸問(wèn)題及其求解是眾所周知上還是行政一喪看卻具機此)因此在一個(gè)大的產(chǎn)中國煤化工的1]。一般來(lái)說(shuō)運輸問(wèn)題只能解決一個(gè)可以控制銷(xiāo)布國等盡管可以建立運調度的運輸系統實(shí)現該系統中的運輸優(yōu)化。在現輸問(wèn)YHen MH導學(xué)中的方法求得最佳實(shí)中,由于市場(chǎng)機制和自由競爭,-個(gè)較大的產(chǎn)銷(xiāo)布調運方案但是這些最佳調運方案通常是無(wú)法實(shí)現的。因為全局最佳調運方案可能會(huì )損害-些在市場(chǎng)收稿日期2001-10-08機制下具有優(yōu)勢的子系統的利益給-些弱勢的子作者簡(jiǎn)介張建費1955- )男碩士.研究方向運籌學(xué).52四川大學(xué)學(xué)報(工程科學(xué)版)第34卷系統帶來(lái)額外獲利。另-方面，全局最佳調運方案表2子系統 i的運輸問(wèn)題與市場(chǎng)機制下的自由競爭原則相違背,由于大系統Tab.2 Transportation problem of subsystem i不能控制子系統的調度所以必然會(huì )有-些子系統產(chǎn)地.銷(xiāo)地拒絕全局最佳調運方案。B(i-1)+1..Bu1); Bxn)1.BAKi-1)+1在一個(gè)運輸大系統中或者說(shuō)在一個(gè)大的產(chǎn)銷(xiāo)布局系統中,由于各子系統相對于大系統在經(jīng)濟上AKi) .( Cq)AMn)+1和行政上具有-定的獨立性在市場(chǎng)機制下各個(gè)子系統除了向本系統提供服務(wù)以外還向其它的子系_A統提供服務(wù)或接受其它的子系統提供的服務(wù)。因在表2所示的子系統i的運輸問(wèn)題中，如果供此在考慮運輸費用或營(yíng)運盈利時(shí),每個(gè)子系統都會(huì )應量不超過(guò)需求量即:為了自身利益而局部地優(yōu)化本子系統的調運方案,aK(i-1)+1 + .... + aK(i)+ ak(n)+1+..+aK≤當從而破壞整體的帕累托最優(yōu)性2。從博弈論的角b(i-1)+1+... + b(i)+ br(n)+...+ bl度看在自由競爭的原則下這是很正常的事情。則在市場(chǎng)機制下和自由競爭的原則下子系統設所考慮的運輸系統中有K個(gè)產(chǎn)地(供應地),i靠自己的能力能優(yōu)化的運輸問(wèn)題如表2所示稱(chēng)記為AA2..Ax有L個(gè)銷(xiāo)地(需求地),記為B,為子系統運輸問(wèn)題。如果表2中供應量大于需求B2.,Bro該運輸系統由n個(gè)獨立的子系統構成可量那么子系統i必須等有富余需求量的子系統優(yōu)能運輸調度是非統一,運輸費用或營(yíng)運盈利由各子化完自身的運輸問(wèn)題后再加上其他子系統提供的系統承擔或獲得。用1.. ,n表示這n個(gè)子系統假銷(xiāo)地的剩余需求量,才能靠自己的能力優(yōu)化擴展了設子系統i擁有產(chǎn)地Ax(-1)21.. AKi)和銷(xiāo)地的子系統運輸問(wèn)題。Br(i-12+1..,B(;)的壟斷營(yíng)運權(或部分壟斷營(yíng)運從博弈的角度看這種全局運輸問(wèn)題構成了大權本文考慮全部壟斷營(yíng)運權的情況);其中0 <系統和各個(gè)子系統之間的一個(gè)運輸費用博弈。K(i-1)< K(i),K(n)= K 0≤l(i-1)≤I( i),2全局運輸的合作博弈模型I( n)≤L,i= 1 2... ,no這里的假設條件0< K( i-1)+1，從全局經(jīng)濟角度考慮,該運輸問(wèn)題可以描述成.. Axi)和銷(xiāo)地Bui-1)+1 . B(i)i = 12.n銷(xiāo)表1的形式而從子系統的經(jīng)濟角度來(lái)考慮子系統地Br(n)+1.. B,是公共的。用J( i)和Jh i)分別表i的運輸問(wèn)題可以描述成表2的形式。示局中人i壟斷的產(chǎn)地和銷(xiāo)地的指標集J表示及公表1全局運輸問(wèn)題共產(chǎn)地的指標集。假設允許結盟。設s c N是一個(gè)聯(lián)Tab.1 Overall transportation problem盟I中國煤花壬題如表3。運輸問(wèn)題YHBcNMHGoteofcliosA產(chǎn)地B，t∈J6i i∈s; Bun)b1 B( Cy)Azk∈J(i)i∈sCa為聯(lián)盟s所壟斷的產(chǎn)地和公共Aεk∈J產(chǎn)地到s所壟斷的銷(xiāo)地及公共銷(xiāo)地的單位物資運輸費用第4期張建高等:合作博弈與運輸優(yōu)化53對于聯(lián)盟s的運輸問(wèn)題,如果在表3中的供應后而得到的即,( T)=簡(jiǎn)記為( T)= s( s |r)量ak不超過(guò)需求量b。即:定理1.設T和S是局中人的兩個(gè)聯(lián)盟,T c s ,2 2 an+2a≤2 2 b.e2.>.+... +b,)( S)是s問(wèn)題的可行解小T)= )(SIr)是)( s)i∈sk∈Ki)則聯(lián)盟s憑自己的能力可以?xún)?yōu)化如表3所示的聯(lián)盟在聯(lián)盟T上的限制則s( T)是T問(wèn)題的一個(gè)可行運輸問(wèn)題使聯(lián)盟承擔的費用最小。如果表3中的聯(lián)解。盟運輸問(wèn)題的供應量大于需求量那么,該聯(lián)盟s只證明設(S)= {y:(S).. m S))}∈xs),有在其他子系統或聯(lián)盟優(yōu)化完自身的運輸問(wèn)題后,因為s(s)是s問(wèn)題的可行解有:再加上N_s中有富余需求量的所有子系統所提供j=i{(S)= ar,V k∈I(S)U J ;的相應銷(xiāo)地的剩余需求量,才 能優(yōu)化擴展了的聯(lián)盟運輸問(wèn)題。以及:2 yn(S)≤b%,j= 12.. L;顯然當S= N時(shí)聯(lián)盟s的運輸問(wèn)題表3 ,成和:yn(S)≥0,V k∈J(S)∪J ,1≤j≤Lo為表1中的全局運輸問(wèn)題而當s = {i}時(shí)表3所由于Tcs故入T)c J(S)JT)UJc JS)示的聯(lián)盟s的運輸問(wèn)題成為表2中的子系統i的運∪J。因此,把上面的指標集J(S)∪J換成指標集輸問(wèn)題或稱(chēng)為局中人i的運輸問(wèn)題。J(T)∪J后,所有的等式和不等式仍然成立。所以,設表3中聯(lián)盟s的運輸問(wèn)題在供大于求時(shí)為)( T)= s(S Ir )是T問(wèn)題的-一個(gè)可行解。(證明完畢)擴展了的聯(lián)盟運輸問(wèn)題)的最優(yōu)值為u(S),則定理2.設r和s是兩個(gè)聯(lián)盟,Tcs ,( s)是s問(wèn)《( s)對每一-個(gè)聯(lián)盟Sc N有定義且u( 0)=0。在題的任--可行解u(T)是T問(wèn)題的最優(yōu)值則有1(T)文中將在下面的假設下來(lái)證明u滿(mǎn)足超可加性?！?)(S |r))公共銷(xiāo)地假設.假設所有的銷(xiāo)地B Br... B,證明由定理1 ,(S Ir )是T問(wèn)題的一個(gè)可行解，都是公共的即I( n)= 0。在公共銷(xiāo)地假設下,不存在擴展了的聯(lián)盟運輸而u(;(SIr))是T問(wèn)題相應于可行解y(sIr)的目標問(wèn)題,而表3所示的聯(lián)盟s的運輸問(wèn)題可以簡(jiǎn)化為函數值d( T )是T問(wèn)題的最優(yōu)值所以ud T)≤u( s( sIr ))(證明完畢)表4。表4公共銷(xiāo)地假設 下聯(lián)盟s的運輸問(wèn)題定理3.由s問(wèn)題的最優(yōu)值u( s )所定義的聯(lián)盟的Tab.4 Transportation problem of coalition S with特征函數u滿(mǎn)足超可加性。the assumption of public destination證明設s和T是兩個(gè)聯(lián)盟s∩T=σ聯(lián)盟s銷(xiāo)地產(chǎn)地B..∪T的運輸問(wèn)題的- -個(gè)最優(yōu)解是s( S∪T)最優(yōu)值是Axk∈J(i),i∈su(s∪T)令j(S)= ((S∪T)Is )是j(S∪T)在( C;)Ank∈J聯(lián)盟s,上的限制n( T)= j((s∪T)|r)是j(S∪T)為了證明u滿(mǎn)足超可加性,還需要一些概念。在聯(lián)盟T上的限制。由定理1,(s)是s問(wèn)題的一-個(gè)可為了敘述簡(jiǎn)單起見(jiàn)，以下簡(jiǎn)稱(chēng)表4中聯(lián)盟s的運.行解,(T)是T問(wèn)題的一一個(gè)可行解所以應該有(S)輸問(wèn)題為s問(wèn)題。令JI(S)=∪J i)則集合I( s )是≤1()(S))和u( T)≤(( T))s中的全部局中人所壟斷的產(chǎn)地的指標集。設s( s)另-方面因為運輸問(wèn)題的目標函數是線(xiàn)性函數,是s問(wèn)題的任- -可行解則s( s )可以用矩陣形式表故有:示為:;(S)= {yn:(S).. 水( s))h∈xs);但是,a(S∪T)= a()((S∪T)I;))+( )((S∪T)Ir))=通常稱(chēng)s問(wèn)題的可行解s(s)是-個(gè)解向量而不說(shuō)1((S))+ 1(s( T)))(S)是一個(gè)解矩陣。對于任意可行解3(S),用所以:_ u(S∪ T)≥u(S)+ u( T)(s(s))表示s問(wèn)題相應于可行解s(S)的目標函數中國煤化工正明完畢)值如果s(s)是最優(yōu)解則u()(S))=u(S)YHCNMHG理。定義1.設)(S)= {yn(S)...兆小s))}∈xs)定理4.在由獨立子系統所構成的運輸系統中,是s問(wèn)題的可行解,聯(lián)盟TcS。說(shuō)向量s(T)是如果銷(xiāo)地都是公共的則以子系統為局中人各聯(lián)盟( s )在聯(lián)盟T上的限制如果向量y( T )是從」( s)運輸問(wèn)題的最優(yōu)值為聯(lián)盟特征函數的全局運輸博中去掉不在方年的局中人所壟斷的產(chǎn)地的相應分量弈是一個(gè)n人合作博弈。54四川大學(xué)學(xué)報(工程科學(xué)版)第34卷則局中人i應該獲得以( )( NI; ))- x的補償彌補實(shí)3子系統之間的效用轉移現全局最優(yōu)方案所帶來(lái)的損失。如果u( s( N1;))<在上一節中,證明了在由獨立子系統所構成的x則局中人i應該支付x;一u( y( N 1;))的額外費運輸系統中在公共銷(xiāo)地假設條件下，全局運輸最優(yōu)用以補償實(shí)現全局最優(yōu)方案給其他局中人所造成的化問(wèn)題構成一個(gè)n人合作博弈。從超可加性,知道損失。這樣-來(lái),就實(shí)現了子系統之間的效用轉移(2 )式成立。這是否意味著(zhù)各子系統在自由競爭下同時(shí)也實(shí)現了全局運輸問(wèn)題的最優(yōu)化。根據合作博的總費用之和不超過(guò)全局最優(yōu)化的總費用呢當然弈的解3A] ,例如核仁( Nucleolus ) ,對某個(gè)局中人i不是。因為合作博弈中所考慮的局中人或聯(lián)盟的效來(lái)說(shuō) 如果有x= ( i) ,由于核仁的良好性質(zhì),有充用都是理想效用。在非合作的競爭中,不可能每個(gè)分的理由論證局中人i支付費用u i )的公平合理子系統都能實(shí)現表2所示的子系統i的運輸問(wèn)題,因性其他的局中人是沒(méi)有好的理由進(jìn)行反駁的。同此各子系統的實(shí)際總費用之和必然大于或等于全樣若局中人j所支付的費用x;遠大于u( j) ,也有足局最優(yōu)化時(shí)的總費用。夠的理由說(shuō)明他為什么應該支付這個(gè)費用。合作博弈的一個(gè)重要特征,就是在參與博弈的4某小城鎮運輸博弈分析局中人之間,可以進(jìn)行效用轉移，從而使得合作成為可能聯(lián)盟能在博弈中出現并在博弈過(guò)程中維持下在本節中以某小城鎮的運輸問(wèn)題來(lái)說(shuō)明運輸去。在n人合作博弈理論中實(shí)現局中人之間效用轉中的博弈問(wèn)題。已知某小城鎮有3家運輸公司,記移的方式是以合作博弈的解來(lái)體現的。為A,B,C。只考慮-種物資的運輸問(wèn)題。該物資采用全局運輸的合作博弈模型設x =(x x2,在城鎮及其附近區域內有7個(gè)產(chǎn)地,用A ,A2 A3,.... xn)∈X(T)是該合作博弈的一-個(gè)解按照合作A4 ,As A6 Ay表示;有6個(gè)銷(xiāo)地用B B2 B3 ,B4 ,Bs ,博弈理論局中人i應該獲得的公平合理的效用是B6表示。根據全年統計數據,可以認為在1周內3x;即局中人i應該分攤費用是x;o設全局最優(yōu)解和家公司運輸這種物資的平均情況如表5所示。最優(yōu)值仍為)(N)和u( N)如果u((NI;))> x，表5各家公司平均每周的運輸情況Tab.5 Transportation volume for one week averageA公司總運輸量200B公司總運輸量180C公司總運輸量210產(chǎn)地運量/t 銷(xiāo)地運量/t 產(chǎn)地運量/t 銷(xiāo)地運量/t產(chǎn)地運量/t銷(xiāo)地運量/t6(B1006080Az50110A4(7040300B。105(20I0_A_5(從表5 ,可以得到各個(gè)產(chǎn)地的產(chǎn)量和各個(gè)銷(xiāo)地表7產(chǎn)地和銷(xiāo)地之間的距離Tab.7 Distances between origins and destinations的需求量如表6。單位km表6各產(chǎn)地的產(chǎn)量和各銷(xiāo)地的需求量B_B_B_BB_B。_產(chǎn)量/Tab.6 Output of each origin and demand volume of\u18202119232:(203025321'2each destinationAR 222726 33:18產(chǎn)地“量/1銷(xiāo)地需求量/1 _79(248(2(A7403025242822需求量/1100 80 100 180 617(A公司:8500 kmt t ;B公司:9500kmt t;C公司:1100中國煤化工L( 100 kmx5t)計算,合計_590根據產(chǎn)地和銷(xiāo)地之間的距離,可 以得到用里程可以M出CNMHG耗為:0.07L(kmt 12表示的運輸問(wèn)題如表7。根據調查空車(chē)調撥及返.于是3家公司1周內的忌油耗分別:A公司0.07x空費用與運載物資的費用基本相同在1周中每家8500=595 L ,B公司:0.07x9500=665 L,C公司:0.07x 11000= 770 L。公司運載物資的總公里噸數分別為:在現實(shí)問(wèn)題中,由于競爭各家公司的運輸問(wèn)題第4期張建高等:合作博弈與運輸優(yōu)化55是沒(méi)有優(yōu)化的。如果3家公司可以在一段時(shí)期內結以核仁( mucleolus )作為這個(gè)合作博弈的解可以盟那么他們就能優(yōu)化聯(lián)盟的運輸問(wèn)題。采用表上求得核仁為:x =(940 ,1340 ,2580)。因此與現狀作業(yè)法容易解出各家公司和各個(gè)聯(lián)盟優(yōu)化運輸問(wèn)相比,A公司應該少跑940kmtt,B公司應該少跑題后與現狀相比所少跑的公里噸數為:1340kmt t ,C公司應該少跑2580 km t 是較為合理(A)= 180 r(B)= 480 n(C)= 1840 n( AB)的。所以最佳調運方案的分配是:A公司運輸7560= 2040,( AC) = 3280 ,a( BC) = 3680 ,( ABC) =kmt,B公司運輸8160kmt,C公司運輸8240kmt。4860。v作為定義在運輸公司集合N = {A B C}的實(shí)際運輸物資為A= 3780 kmt t ,B=4080 km t ,C=子集上的函數顯然滿(mǎn)足超可加性。因此,在允許各4120 km to公司結盟時(shí)運輸節能問(wèn)題(即在總運輸量不變的情因為運輸的利潤與運輸的物資量成正比在保況下，少跑公里噸的問(wèn)題)是一個(gè)典型的n人合作持各家公司的總運輸量不變時(shí),在最佳運輸方案中博弈。對各家公司在產(chǎn)地和銷(xiāo)地的運輸量略加調整,可以-般來(lái)說(shuō)合作博弈理論可以解決上述問(wèn)題而得到一個(gè)公平合理的3家公司在-段時(shí)間內結盟的合作博弈的一個(gè)解可以作為各公司應該少跑的公里最佳協(xié)同物資運輸方案如表8。噸的一個(gè)公平合理分配。表8 3家公司結盟的最佳協(xié)調運輸方案Tab.8 Optimum transportation scheme of the coalitionA公司:總運輸量200B公司總運輸量180C公司總運輸量210產(chǎn)地運量/t銷(xiāo)地運量/t 產(chǎn)地運量/t 銷(xiāo)地運量/t產(chǎn)地運量/t銷(xiāo)地運量/tB500A6[6(A3104C308020Bz5C3,As5(或某種較好的算法,能同時(shí)求解全局運輸問(wèn)題最優(yōu)5結論解和運輸合作博弈的核心,或者最小核心,或者核證明了如果所有銷(xiāo)地都是公共的則全局運輸仁。優(yōu)化問(wèn)題中子系統之間的博弈在允許結盟時(shí)構成一參考文獻:個(gè)n人合作博弈。提出運輸合作博弈的另一個(gè)理由是,許多運輸問(wèn)題都有不止一個(gè)的最優(yōu)解如果費用[1王建華.對策論[ M ].北京清華大學(xué)出版社,1988.或效益由運輸系統中的各子系統獨立承擔那么選[ 2 ]Guillemno Owen , Game Theon)[ M ] Academic Press ,Inc. ,U擇哪一個(gè)最優(yōu)解作為調運方案,是通常的運輸模型SA,1982.所不能解決的。在結束本文前提出運輸合作博弈的[3 ]Dragan I. A procedure for finding the nmucleolus of a cooerativen person gand[ J]. Z0R ,1981 255):119~ 132.兩個(gè)問(wèn)題:1 )如果公共銷(xiāo)地假設條件不成立,即至少有-[ 4 ]Bhaskar Q V. Fgaltarianism and fficiency in repeated symmet-c game[ J ] Games and Economic Behavior , 2000 32 247~個(gè)子系統壟斷某個(gè)銷(xiāo)地,運輸合作博弈的特征函數262.還滿(mǎn)足超可加性嗎?(編輯張瓊)2)對于運輸合作博弈是否存在一個(gè)線(xiàn)性規劃中國煤化工MHCNMHG