合作博弈与运输优化

第34卷第4期四川大学学报(工程科学版)Vol.34 No.42002年7月JOURNAL OF SICHUAN UNIVERSITY( ENGINEERING SCIENCE EDITION )July 2002文章编号:1009-3087 2002 )4-0051-05合作博弈与运输优化张建高,郑乃伟(重庆大学建设管理与房地产学院重庆400045)摘要从博弈论的角度分析了区域性大系统中的运输问题考虑了在这种运输系统中由于各个子运输系统之间的相对独立性和彼此之间的竞争采用运筹学中通常的运输问题模型是无法使这样的一个运输系统达到最优状态的。理论与实践的分析都证明要在区域性运输大系统中实现运输问题的最优解,允许各子运输系统之间结盟是必要的。作者将合作博弈理论与运筹学中的运输问题模型相结合在允许子运输系统之间结盟的条件下建立了全局运输问题的博弈模型,证明了该模型构成一个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局系统通常是由若干子系统所构成的,并且这些子1全局运输的博弈形式系统相对于大系统来说通常是独立的(不论从经济运筹学中的运输问题及其求解是众所周知上还是行政一丧看却具机此)因此在一个大的产中国煤化工的1]。一般来说运输问题只能解决一个可以控制销布国等尽管可以建立运调度的运输系统实现该系统中的运输优化。在现输问YHen MH导学中的方法求得最佳实中,由于市场机制和自由竞争,-个较大的产销布调运方案但是这些最佳调运方案通常是无法实现的。因为全局最佳调运方案可能会损害-些在市场收稿日期2001-10-08机制下具有优势的子系统的利益给-些弱势的子作者简介张建費1955- )男硕士.研究方向运筹学.52四川大学学报(工程科学版)第34卷系统带来额外获利。另-方面，全局最佳调运方案表2子系统 i的运输问题与市场机制下的自由竞争原则相违背,由于大系统Tab.2 Transportation problem of subsystem i不能控制子系统的调度所以必然会有-些子系统产地.销地拒绝全局最佳调运方案。B(i-1)+1..Bu1); Bxn)1.BAKi-1)+1在一个运输大系统中或者说在一个大的产销布局系统中,由于各子系统相对于大系统在经济上AKi) .( Cq)AMn)+1和行政上具有-定的独立性在市场机制下各个子系统除了向本系统提供服务以外还向其它的子系_A统提供服务或接受其它的子系统提供的服务。因在表2所示的子系统i的运输问题中，如果供此在考虑运输费用或营运盈利时,每个子系统都会应量不超过需求量即:为了自身利益而局部地优化本子系统的调运方案,aK(i-1)+1 + .... + aK(i)+ ak(n)+1+..+aK≤当从而破坏整体的帕累托最优性2。从博弈论的角b(i-1)+1+... + b(i)+ br(n)+...+ bl度看在自由竞争的原则下这是很正常的事情。则在市场机制下和自由竞争的原则下子系统设所考虑的运输系统中有K个产地(供应地),i靠自己的能力能优化的运输问题如表2所示称记为AA2..Ax有L个销地(需求地),记为B,为子系统运输问题。如果表2中供应量大于需求B2.,Bro该运输系统由n个独立的子系统构成可量那么子系统i必须等有富余需求量的子系统优能运输调度是非统一,运输费用或营运盈利由各子化完自身的运输问题后再加上其他子系统提供的系统承担或获得。用1.. ,n表示这n个子系统假销地的剩余需求量,才能靠自己的能力优化扩展了设子系统i拥有产地Ax(-1)21.. AKi)和销地的子系统运输问题。Br(i-12+1..,B(;)的垄断营运权(或部分垄断营运从博弈的角度看这种全局运输问题构成了大权本文考虑全部垄断营运权的情况);其中0 <系统和各个子系统之间的一个运输费用博弈。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，从全局经济角度考虑,该运输问题可以描述成.. Axi)和销地Bui-1)+1 . B(i)i = 12.n销表1的形式而从子系统的经济角度来考虑子系统地Br(n)+1.. B,是公共的。用J( i)和Jh i)分别表i的运输问题可以描述成表2的形式。示局中人i垄断的产地和销地的指标集J表示及公表1全局运输问题共产地的指标集。假设允许结盟。设s c N是一个联Tab.1 Overall transportation problem盟I中国煤花壬题如表3。运输问题YHBcNMHGoteofcliosA产地B，t∈J6i i∈s; Bun)b1 B( Cy)Azk∈J(i)i∈sCa为联盟s所垄断的产地和公共Aεk∈J产地到s所垄断的销地及公共销地的单位物资运输费用第4期张建高等:合作博弈与运输优化53对于联盟s的运输问题,如果在表3中的供应后而得到的即,( T)=简记为( T)= s( s |r)量ak不超过需求量b。即:定理1.设T和S是局中人的两个联盟,T c s ,2 2 an+2a≤2 2 b.e2.>.+... +b,)( S)是s问题的可行解小T)= )(SIr)是)( s)i∈sk∈Ki)则联盟s凭自己的能力可以优化如表3所示的联盟在联盟T上的限制则s( T)是T问题的一个可行运输问题使联盟承担的费用最小。如果表3中的联解。盟运输问题的供应量大于需求量那么,该联盟s只证明设(S)= {y:(S).. m S))}∈xs),有在其他子系统或联盟优化完自身的运输问题后,因为s(s)是s问题的可行解有:再加上N_s中有富余需求量的所有子系统所提供j=i{(S)= ar,V k∈I(S)U J ;的相应销地的剩余需求量,才 能优化扩展了的联盟运输问题。以及:2 yn(S)≤b%,j= 12.. L;显然当S= 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)示的联盟s的运输问题成为表2中的子系统i的运∪J。因此,把上面的指标集J(S)∪J换成指标集输问题或称为局中人i的运输问题。J(T)∪J后,所有的等式和不等式仍然成立。所以,设表3中联盟s的运输问题在供大于求时为)( T)= s(S Ir )是T问题的-一个可行解。(证明完毕)扩展了的联盟运输问题)的最优值为u(S),则定理2.设r和s是两个联盟,Tcs ,( s)是s问《( s)对每一-个联盟Sc N有定义且u( 0)=0。在题的任--可行解u(T)是T问题的最优值则有1(T)文中将在下面的假设下来证明u满足超可加性。≤()(S |r))公共销地假设.假设所有的销地B Br... B,证明由定理1 ,(S Ir )是T问题的一个可行解，都是公共的即I( n)= 0。在公共销地假设下,不存在扩展了的联盟运输而u(;(SIr))是T问题相应于可行解y(sIr)的目标问题,而表3所示的联盟s的运输问题可以简化为函数值d( T )是T问题的最优值所以ud T)≤u( s( sIr ))(证明完毕)表4。表4公共销地假设 下联盟s的运输问题定理3.由s问题的最优值u( s )所定义的联盟的Tab.4 Transportation problem of coalition S with特征函数u满足超可加性。the assumption of public destination证明设s和T是两个联盟s∩T=σ联盟s销地产地B..∪T的运输问题的- -个最优解是s( S∪T)最优值是Axk∈J(i),i∈su(s∪T)令j(S)= ((S∪T)Is )是j(S∪T)在( C;)Ank∈J联盟s,上的限制n( T)= j((s∪T)|r)是j(S∪T)为了证明u满足超可加性,还需要一些概念。在联盟T上的限制。由定理1,(s)是s问题的一-个可为了叙述简单起见，以下简称表4中联盟s的运.行解,(T)是T问题的一一个可行解所以应该有(S)输问题为s问题。令JI(S)=∪J i)则集合I( s )是≤1()(S))和u( T)≤(( T))s中的全部局中人所垄断的产地的指标集。设s( s)另-方面因为运输问题的目标函数是线性函数,是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)的目标函数中国煤化工正明完毕)值如果s(s)是最优解则u()(S))=u(S)YHCNMHG理。定义1.设)(S)= {yn(S)...兆小s))}∈xs)定理4.在由独立子系统所构成的运输系统中,是s问题的可行解,联盟TcS。说向量s(T)是如果销地都是公共的则以子系统为局中人各联盟( s )在联盟T上的限制如果向量y( T )是从」( s)运输问题的最优值为联盟特征函数的全局运输博中去掉不在方年的局中人所垄断的产地的相应分量弈是一个n人合作博弈。54四川大学学报(工程科学版)第34卷则局中人i应该获得以( )( NI; ))- x的补偿弥补实3子系统之间的效用转移现全局最优方案所带来的损失。如果u( s( N1;))<在上一节中,证明了在由独立子系统所构成的x则局中人i应该支付x;一u( y( N 1;))的额外费运输系统中在公共销地假设条件下，全局运输最优用以补偿实现全局最优方案给其他局中人所造成的化问题构成一个n人合作博弈。从超可加性,知道损失。这样-来,就实现了子系统之间的效用转移(2 )式成立。这是否意味着各子系统在自由竞争下同时也实现了全局运输问题的最优化。根据合作博的总费用之和不超过全局最优化的总费用呢当然弈的解3A] ,例如核仁( Nucleolus ) ,对某个局中人i不是。因为合作博弈中所考虑的局中人或联盟的效来说 如果有x= ( i) ,由于核仁的良好性质,有充用都是理想效用。在非合作的竞争中,不可能每个分的理由论证局中人i支付费用u i )的公平合理子系统都能实现表2所示的子系统i的运输问题,因性其他的局中人是没有好的理由进行反驳的。同此各子系统的实际总费用之和必然大于或等于全样若局中人j所支付的费用x;远大于u( j) ,也有足局最优化时的总费用。够的理由说明他为什么应该支付这个费用。合作博弈的一个重要特征,就是在参与博弈的4某小城镇运输博弈分析局中人之间,可以进行效用转移，从而使得合作成为可能联盟能在博弈中出现并在博弈过程中维持下在本节中以某小城镇的运输问题来说明运输去。在n人合作博弈理论中实现局中人之间效用转中的博弈问题。已知某小城镇有3家运输公司,记移的方式是以合作博弈的解来体现的。为A,B,C。只考虑-种物资的运输问题。该物资采用全局运输的合作博弈模型设x =(x x2,在城镇及其附近区域内有7个产地,用A ,A2 A3,.... xn)∈X(T)是该合作博弈的一-个解按照合作A4 ,As A6 Ay表示;有6个销地用B B2 B3 ,B4 ,Bs ,博弈理论局中人i应该获得的公平合理的效用是B6表示。根据全年统计数据,可以认为在1周内3x;即局中人i应该分摊费用是x;o设全局最优解和家公司运输这种物资的平均情况如表5所示。最优值仍为)(N)和u( N)如果u((NI;))> x，表5各家公司平均每周的运输情况Tab.5 Transportation volume for one week averageA公司总运输量200B公司总运输量180C公司总运输量210产地运量/t 销地运量/t 产地运量/t 销地运量/t产地运量/t销地运量/t6(B1006080Az50110A4(7040300B。105(20I0_A_5(从表5 ,可以得到各个产地的产量和各个销地表7产地和销地之间的距离Tab.7 Distances between origins and destinations的需求量如表6。单位km表6各产地的产量和各销地的需求量B_B_B_BB_B。_产量/Tab.6 Output of each origin and demand volume of\u18202119232:(203025321'2each destinationAR 222726 33:18产地“量/1销地需求量/1 _79(248(2(A7403025242822需求量/1100 80 100 180 617(A公司:8500 kmt t ;B公司:9500kmt t;C公司:1100中国煤化工L( 100 kmx5t)计算,合计_590根据产地和销地之间的距离,可 以得到用里程可以M出CNMHG耗为:0.07L(kmt 12表示的运输问题如表7。根据调查空车调拨及返.于是3家公司1周内的忌油耗分别:A公司0.07x空费用与运载物资的费用基本相同在1周中每家8500=595 L ,B公司:0.07x9500=665 L,C公司:0.07x 11000= 770 L。公司运载物资的总公里吨数分别为:在现实问题中,由于竞争各家公司的运输问题第4期张建高等:合作博弈与运输优化55是没有优化的。如果3家公司可以在一段时期内结以核仁( mucleolus )作为这个合作博弈的解可以盟那么他们就能优化联盟的运输问题。采用表上求得核仁为:x =(940 ,1340 ,2580)。因此与现状作业法容易解出各家公司和各个联盟优化运输问相比,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}的实际运输物资为A= 3780 kmt t ,B=4080 km t ,C=子集上的函数显然满足超可加性。因此,在允许各4120 km to公司结盟时运输节能问题(即在总运输量不变的情因为运输的利润与运输的物资量成正比在保况下，少跑公里吨的问题)是一个典型的n人合作持各家公司的总运输量不变时,在最佳运输方案中博弈。对各家公司在产地和销地的运输量略加调整,可以-般来说合作博弈理论可以解决上述问题而得到一个公平合理的3家公司在-段时间内结盟的合作博弈的一个解可以作为各公司应该少跑的公里最佳协同物资运输方案如表8。吨的一个公平合理分配。表8 3家公司结盟的最佳协调运输方案Tab.8 Optimum transportation scheme of the coalitionA公司:总运输量200B公司总运输量180C公司总运输量210产地运量/t销地运量/t 产地运量/t 销地运量/t产地运量/t销地运量/tB500A6[6(A3104C308020Bz5C3,As5(或某种较好的算法,能同时求解全局运输问题最优5结论解和运输合作博弈的核心,或者最小核心,或者核证明了如果所有销地都是公共的则全局运输仁。优化问题中子系统之间的博弈在允许结盟时构成一参考文献:个n人合作博弈。提出运输合作博弈的另一个理由是,许多运输问题都有不止一个的最优解如果费用[1王建华.对策论[ M ].北京清华大学出版社,1988.或效益由运输系统中的各子系统独立承担那么选[ 2 ]Guillemno Owen , Game Theon)[ M ] Academic Press ,Inc. ,U择哪一个最优解作为调运方案,是通常的运输模型SA,1982.所不能解决的。在结束本文前提出运输合作博弈的[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~个子系统垄断某个销地,运输合作博弈的特征函数262.还满足超可加性吗?(编辑张琼)2)对于运输合作博弈是否存在一个线性规划中国煤化工MHCNMHG