经济管理数学模型案例教程(总)

[2-1-12]利益分配的合作博弈模型1、问题的提出在经济和社会活动中，若干实体（如个人、公司、党派、国家等）相互合作结成联盟或者集团，常能获利得比他们单独行动时更大的经济或社会效益，并且，通常这种利益是非对抗性的。合理地分配这些效益的方案是促成合作的前提，那么，应该如何分配利益才算是合理？2、模型的构建若干方合作获利的效益分配问题，称为合作博弈。1953年，L.S.Shapley给出了n人合作博弈问题的一种方法。假定在n方合作博弈中，若干人的每一种组合（特别，单人也看作为一种组合）都会得到一定的效益，合作中人数的增加不会引起效益的减少，于是，全体人员的合作将带来最大效益，在这种假定下，Shapley提出了一系列的公理的唯一的分配这个最大效益的一种方案，并且严格证明了这种方案是满足这组公理的唯一的分配。设},,2,1{nI为合作博弈的n方。对于参加者的某种组合(即I的一个子集)S,以)(Sv记其相应的效益(它是一种有特定含义的特征函数).。用iP表示I中第i位成员从合作收益中应得到的一份收入。称TnvpvpvpP))(,),(),((21为Shapley值，它由效益函数)(Sv确定它的计算公式为iSsiniiSvSvSwp)17.1.2(,,2,1)],\()()[(其中iS是I中包含i的所有子集，S是子集S中的元素个数（组合S中的参加者数量），)(Sw是加权因子!)!1()!()(nSSnSw注意到)(Sv是有第i方参加的某种合作方案S的获利，)\(iSv表示在这种合作方式中第i方退出以后的获利。因此，)\()(iSvSv可以看成在这种合作方案中第i方的“贡献”。根据前面的假设，任何一方在任何合作方案中的贡献都是非负的。而iPv则是在各种有第i方参加的合作方案iS中第i方“贡献”的加权总和。通俗地说，就是按照贡献大小分配利益。可以证明，这种分配方案满足：i）不贡献的不得利（即如果他在各种合作方案中所有的贡献值都为零，则他的获利为零）：ii）各合作方的获利总和等于总收益。3模型求解与应用下面通过实例说明模型如何根据)17.1.2(求解合作获利的效益分配，沿河有1、2、3三个城镇，地理位置及各城镇的距离如图2-9所示。城镇排放的污需经过处理才能排入河中，三个城镇既可以单独建污水处理厂，也可以联合建厂，用管道将污集中处理（污水必须从上游城镇送往下游城镇，处理厂必须建在下游位置。）按照经验公式，建造污水处理厂的费用1p和铺设管道的费用2p分别为)(73712.01千元Qp02p)(66.51.0千元LQ其中Q表示污水处理量（吨/秒），L表示管道长度（km）、如果三城镇的污水量分别为62135，Q，QQ6，试从节约总投资的角度为三城镇制定建厂方案。如果联合建厂，费用应如何分担。三城镇建厂方案一共有以下5种（1）城镇分别建造，建造费用分别为73)1(F×，。)(23057120千元73)2(F)(1603712.0千元，F)(260673)3(712.0千元总投资额为)(650)3()2()1(千元FFF（2）城1，2合作，在城2处建厂，城3单独建，建造费用为)(35020566.0)35(73)2,1(51.0712.0千元F，总投资额为)(610)3()2,1(千元FF。（3）城2，3合作，在城3处建厂，城1单独建.建造费用为)(39038366.0)63(73)3,2(51.0712.0千元F，总投资额为)(620)1()3,2(千元FF。（4）城1，3合作，在城3处建厂，城2单独建.建造费用为)(49058566.0)65(73)3,1(51.0712.0千元F，总投资额为)(650)2()3,1(千元FF。（5）三方合作建厂.建造费用为)(58038)35(66.020566.0)635(73)3,2,1(51.051.0712.0千元F比较以上方案，费用最省的自然是第5种，三城镇自然都会考虑合作建设。那么，应该如何分担这笔合作建造费用？如果不采用Shapley的方法，人们首先会想到根据排放污水量平均分担的办法.于是，城1应该分担)(2075806355)1(千元V，同样，城2应分担)(124)2(千元V，城3应分担)(249)3(千元V。然而，按照这样的方案，城1可以节省23千元。城3可以节省36千元，城3却只能节省11千元似乎并不尽合理。考虑到合作建厂的费用由建处理厂和铺设管道两部分组成，城3提出另外的方案：建处理厂费用应按排污量平均分担，而2，3段管道费用应由1，2两城分担，1，2段管道费用由城1单独承担.这种方案貌似公平，但仔细算来，城3只需承担费用)(205)635(736356)3(712.0千元V而城2和城1的费用将分别达到130千元和245千元（计算略）.城1甚至超过单独建厂的费用,这显然更是不合理的。如果采用Shapley的方法，我们可以把合作方案节省的投资额看成收益，它将符合特征函数的要求，因此，可以要Shapley值计算各方节省的资金额。更方便地，可以直接用各种合作方案的建造费用作为效益函数计算Shapley值，其结果就是各方应承担的投资费用.用上述数据计算，以第1城为例，可得下表表2-1-6iS12,13,13,2,1)(iSv230350490580)\(iSvi0160260390v230190230190iS12,13,13,2,1iS1223)(iSw1/31/61/61/3vSwi).(230/3190/6230/6190/3210即得)(2101千元p。类似地可以计算得到)(1252千元p，)(2453千元p.也就是说，如果三方合作，则各方投资应按上述比例分摊.这时，各方按排污量平均每秒吨的投资额分别为42千元、41.67千元、和40.83千元.排放距离即铺设管道长些，承担费用略大些。各方节省额的差额比按照排放污水量平均分担方案小些，这种分摊结果还是更合理些。[2-4-1]钢管的订购和运输模型1、问题的提出2000年全国大学生数学建模竞赛B题《钢管的订购种运输》，问题是要铺设天然气输送管道，在若干钢管生产厂以及不同的运输路径、方案中，如何进行选择，确定购运计划，才能使总费用最小。2．模型和构建《钢管的订购和运输》赛题提出的大到上是这样的问题：要铺设一条1521AAA的输送天然气的主管道，如图2-24所示。经筛选后可以生产这种主管道钢管的钢厂有7,2,1,SSS.图中粗线表示铁路，单细线表示公路，双细线表示要铺设管道的地方（假设沿线原有公路或建有施工公路），每段铁路和公路旁的数字表示路段长（单位：km）.为和距离有所区别，1km长的钢管称为1个单位。钢厂iS在指定期限内该种钢管的最大生产能力为is单位（如下表）：表2-4-1i1234567is800800100020002000200030001单位钢管的铁路运价如下表：表2-4-2里程（km）≤300301~350351~400401~450451~500运价（万元）2023262932里程（km）501~600601~700701~800801~900901~1000运价（万元）3744505560注：1000km以下每增加1~100km，运价增加5运价（万元）。公路运价不1单位钢管每千米路程0.1运价（万元）（不足1km部分按1km计算）.钢管可从某几家钢厂订购，由铁路、公路运往各铺设点（不足是运到,15,2,1,AAA而是管道的全线）。请制定订购和运输计划，我们应当分成几个层面和的子问题考虑：首先需要计算出单位长度钢管从各钢厂S，运到需要铺设点P，（以1km管道为一个点，总共有5171个点）的最小运输费用).5171,,2,1;7,,2,1((jicij钢管可以通过铁路或公路运输。公路运费是运输里程的线性函数（稍有不同的是不足1km要进整），但是铁路运价却是一种分段的阶跃的常数函数。因此在计算时，不管对运输里程还是费用而言，都不具有可加性。图论中用以计算最短路的Dijkstra算法和Floyd算法等都将失效，只能将铁路运价（即由运输总里程找出对应费率）和公路运价分别计算后再迭加，好在整个图形比较简单，钢厂出来都是铁路，铺设点沿线都是公路。而且通常情况下平均每千米的铁路运价要低于公路运价，所以只要在优先考虑尽量使用铁路运输的前提下，通过可能方案的枚举，就能找到费用最小的路径和费用。（根据题目提供的数据，铁路运价中601km段的运价比分解为300+301段的运价要高，从而带来计算的问题。这可能是命题者的疏忽。此外，有个别点对jiPS在运输方案的枚举计算时会出现意外，但这不具一般性。）其实，并不需要逐一求出所有点对jiPS的费用ijc。因为从iS到jP总要经过某个枢纽站。假定jP位于构纽站kA和1kA之间，那么只要比较从jkiPAS和jkiPAS1两者的大小。也就是说，只要先求出kiAS的费用（15,,3,2;7,,2,1ki），再在1kkAA段上找出通过两侧到达铺设点jP费用相同的平衡点ikQ，显然如果jP在平衡点的左侧应该经过kA，在平衡点的右侧则应该经过1kA到达。这样就可以大大减少计算量。（直接计算ijc需要算7×5171个量，而计算kiAS的费用则需要7×14个，平衡点ikQ共7×13个，总共119个量。每个点的费率再需加一小段公路运费即可）。根据题意，公路路段的费用，行驶里程不足1km部分按1km计算。因此，平衡点ikQ的小数部分是不起作用的，不妨均取整数，根据铺设点jP在平衡点的哪一侧来确定费率ijc。知道了从钢厂到铺设点的费率，就容易得出原问题的数学模型——运输问题模型。模型一：线性规模型用ikX表示铺设点jP的钢管是否从第i家钢厂购运而来。如果是则取1，否则取0。那么，总的运输费用便是：ijijijxcW.根据钢厂生产能力有以下不等式：7,,2,1,isxjiij于是，原问题就可以表示成：ijijijxcW.min.5171,,2,1,7,,2,1,1,0,7,,2,1,..jixisxtsijijij这就是原问题的运输问题模型。用该模型求解，显然存在变量过多（共有7×5171个）的困难。考虑到前文所述钢厂到铺设点的运输必定要经过枢纽站，因此可以用下述方式简化。模型二：二次规划模型用ikx表示从钢厂iS运到枢纽站kA、kZ分别表示从枢纽站kA向右边（即kA1kA段）及左边（即1kAkA段）的钢管总量，（这里假设ky、kZ都是整数）。注意到将总量为ky的钢管运到每单位铺设点，其运费应为第一公里、第二公里……直到第ky公里的运费之和，即为)21(1.0ky。往左也一样。又因为从枢纽站运往两边的量受路段长度制约，故有.||11kkkkAAzy综上所述，原问题的模型为：,2)1(2)1(1.021min.ijkkkkkikikzzyyxcW.14,,3,2,7,,2,1,0,,|,|,14,,3,2|,|,7,,2,1,..121211kizyxAAzKAAzyisxtskkijKkkkijij用该模型，变量个数从7×5171=36197减少到7×14+2×13=114个。上述模型，其目标函数是一个二次函数，而约束条件则是线性方程和线性不等式组。这种形式的数学规划问题称为二次规划。它的一般形式为：0..,21min(max)XbAXtsdXCQXXTT对于二次规划的讨论，可参阅有关文献。3、模型的求解对于所构建的线性规划——运输问题模型，一般数学软件包都有相关的软件可以采用。由于约束条件的系数矩阵的全幺模性，用普通的线性规划方法直接可以得到整数解，不用作特别处理，只是由于变量较多，可能有的计算机容纳不了。至于模型