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