运输问题(运筹学)选编课件.ppt

1、-1-Transportation problem第5章 运输模型2问题的提出问题的提出 运输问题：产地、销地、产量、销量运输问题：产地、销地、产量、销量 引例：有引例：有A A1 1，A A2 2，A A3 3三座铁矿，每天要把生产三座铁矿，每天要把生产的铁矿石运往的铁矿石运往B B1 1，B B2 2，B B3 3，B B4 4四个炼铁厂。各矿的四个炼铁厂。各矿的产量、各厂的销量以及各厂矿间的运价如下表所示。产量、各厂的销量以及各厂矿间的运价如下表所示。问应如何组织调运才能使运费最少？问应如何组织调运才能使运费最少？一、一、运输问题的定义运输问题的定义第5章 运输模型3B1 B2 B3 B

2、4产量产量A1A2A36 3 2 57 5 8 43 2 9 7523销量销量2 3 1 4(百元百元/百吨百吨)xij Ai运给运给Bj的铁矿石数量（百吨）的铁矿石数量（百吨）z 总运费（百元）总运费（百元）调运示意图调运示意图A1A2A3B1B2B3B45吨2吨3吨2吨3吨1吨4吨x11x12x13x14x21x22x23x24x31x32x33x34产地销地第5章 运输模型5B1B2B3B4产量产量A163255A275842A332973销量销量2314(百元百元/百吨百吨)x11x12x13x14x21x22x23x24x31x32x33x34表式模型表式模型第5章 运输模型6 数学

3、模型为数学模型为:min z=6x11+3x12+2x13+5x14+7x21+5x22+8x23+4x24 +3x31+2x32+9x33+7x34 x11+x12+x13+x14 =5 x21+x22+x23+x24 =2 x31+x32+x33+x34=3 x11 +x21 +x31 =2 x12 +x22 +x32 =3 x13 +x23 +x33 =1 x14 +x24 +x34=4 xij0 (i=1,2,3;j=1,2,3,4)s.t.第5章 运输模型7表式表式模型模型 产销平衡产销平衡的运输问题的运输问题:ssi i=ddj j 产大于销产大于销的运输问题的运输问题:ssi i

4、ddj j 产小于销产小于销的运输问题的运输问题:ssi iddj jB1B2Bn 产量产量 A1c11 x11c12 x12c1n x1n s1A2c21 x21c22 x22c2n x2ns2Amcm1 xm1 cm2 xm2 cmn xmnsm销量销量d1d2dn sid dj第5章 运输模型8xij 0 xij=si i=1,2,，mj=1n xij=dj j=1,2,，ni=1ms.t.min z=i=1mj=1n cij xijLP式式 产销平衡产销平衡模型模型第5章 运输模型9 LP式式 产大于销产大于销模型模型xij 0 xij si i=1,2,，mj=1n xij =dj

5、j=1,2,，ni=1ms.t.min z=i=1mj=1n cij xij第5章 运输模型10 xij 0 xij =si i=1,2,，mj=1n xij dj j=1,2,，ni=1ms.t.LP式式 产小于销产小于销模型模型min z=i=1mj=1n cij xij第5章 运输模型11 运输模型有两个特点：运输模型有两个特点：(1)它有它有mn个变量，个变量，m+n个约束方程个约束方程,最大独立方程数：最大独立方程数：m+n-1 (2)其系数阵具有特殊的结构其系数阵具有特殊的结构 m=3行行n=4行行A=1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

6、1 1 1 1 -第3章 运输问题-12-x11 x12 x1n x21 x22 x2n ,xm1 xm2 xmn1 1 1 0 0 0 0 0 00 0 0 1 1 1 0 0 00 0 0 0 0 0 1 1 11 0 0 1 0 0 1 0 00 1 0 0 1 0 0 1 00 0 1 0 0 1 0 0 1i=1i=2i=mj=1j=2j=n 运输表网络图中的回路运输表网络图中的回路运输表中的闭回路从运输网络图中一个基应满足的条件，容易得出运输表中一个基必须满足的条件：1、一个基应占表中的m+n-1格；2、构成基的同行同列格子不能构成闭回路；3、一个基在表中所占的m+n-1个格子应包

7、括表的每一行和每一列。运输问题可以用单纯形法求解，但由于其模型的特殊性，也可以用基于单纯形法思想的表上作业法求解。求解的速度要优于单纯形法。-第3章 运输问题-17-二、表上作业算法求运输问题二、表上作业算法求运输问题表上作业法步骤:初始基本可行解最优性检验改进方案一、确定初始基本可行解1.西北角法西北角法2.最小元素法最小元素法3.Vogel法法二、计算非基变量的检验数1.闭回路法闭回路法2.对偶变量对偶变量法法三、解的改进方法在闭回路闭回路内改进。例2-11 给出运输表及单位运价表如下如下。运用西北角法求初始调运方案。供应地1的供应量为30，需求地1的需求量为15，在（1，1）上安排运量1

8、5。供应地1和需求地1的供应量和需求量分别变为15和0。需求地4的需求量为75，供应地3的供应量为50，安排（3，4）上的运量为50，供应地3的供应量0，需求地4的需求量25；供应地4的供应量为25，需求地4的需求量为25，安排（4，4）上的运量25，供应地4的供应量为0，需求地4的需求量为0，供求和需求都得到满足。用西北角法确定初始可行解方法简单，不会出现回路，而且一般情况下基变量的个数恰为m+n-1个（退化的情况基变量可能少于m+n-1，需通过在相应位置添0的方法处理），而且基变量位于每一行每一列，因而得到的是一个基础可行解。西北角法的缺点是在安排运量时不考虑运价，因而得到的初始解可能离开

9、最优解比较远。以上例子中用西北角法得到的初始解的目标函数值为z=1015+1115+125+1631+99+1050+1325 =1777 41i41jijijxc-第3章 运输问题-27-产地销地A1 A2 A3B1 B2 B3 B4产地销地A1 A2 A3B1 B2 B3 B4产地销地A1 A2 A3B1 B2 B3 B4产量销量3 11 3 10 1 9 2 8 7 4 10 5 6343133 6 5 67 4 93 6 5 67 4 9产量销量363521(1)(2)(1)(-1)(10)(12)z=c11-c13+c23-c21=1=11z=-c12+c14-c34+c33=2=1

10、2(0)(2)(2)(9)(1)(12)单位运价表产销平衡表（2）最小元素法）最小元素法-第3章 运输问题-28-产地销地A1 A2 A3B1 B2 B3 B47 4 9产量销量3 6 5 6635213产地销地A1 A2 A3B1 B2 B3 B4行两最小元素之差列两最小元素之差3 11 3 10 1 9 2 8 7 4 10 5 0 1 12 5 1 3 0 1 22 -1 30 1-2 -1 27 6-1 2Vogel法:产销平衡表2.计算非基变量的检验数zij ij-cij ij（1）闭回路法对于非基变量xij，检验数为其中向量Y Yij可由该非基变量与基变量形成的闭回路来确定，这个闭

11、回路转角处的基变量对应于y=1，其余的基变量对应于y=0。这样就等于转角处基变量对应的cij依次加减的值。在上例中，用西北角法得到初始基础可行解，计算各非基变量的检验数zij-cij非基变量（1，3）相应的闭回路为+6因此x13的检验数 z13-c13=(c12-c22+c23）-c13=(11-12+16)-9=+6。非基变量（1，4）相应的闭回路为-7-2+1将其他检验数填入运输表，用“”表示。-7+5+6-2+10+8+1+1+3第5章 运输模型36表上作业法表上作业法最优性检验最优性检验 在初始方案表中在初始方案表中,可将基变量所在格的运价可将基变量所在格的运价cij分解为两部分分解为

12、两部分 ui+=cij 其中其中ui代表产地代表产地Ai所在行的所在行的行位势量行位势量，代表销地代表销地Bj所在列所在列的的列位势量列位势量，cij为为画圈数字画圈数字所在格的所在格的运价运价。所有所有ui，vj的值确定以后，可以证明，的值确定以后，可以证明，ij可按下式计算：可按下式计算：ij=cij ui 基变量对应的检验数显然全都为基变量对应的检验数显然全都为0，因此，只需计算非基，因此，只需计算非基变量的检验数。这种计算检验数的方法就是变量的检验数。这种计算检验数的方法就是。（2 2）对偶变量法设与前m个约束对应的对偶变量为u1，u2，um，与后n个约束对应的对偶变量为v1，v2，v

13、n。则对偶问题为：max y=s1u1+s2u2+smum +d1v1+d2v2+dnvns.t.u1+v1c11 u1+v2c12 um+vncmn (i=1,2,m；j=1,2,n（u1，u2，um，v1，v2，vn无约束）xij 0 xij=si i=1,2,，mj=1n xij=dj j=1,2,，ni=1ms.t.min z=i=1mj=1n cij xij以上对偶问题，可以简写成：ui+vjcij(i=1,2,m；j=1,2,n)ui，vj：unr 对偶问题中有m+n个变量，mn个约束。n1jjjim1iivdusymax对于运输问题的一个基B，如果能够求出相应的对偶变量 就可以计

14、算非基变量xij的检验数zij-cij：对于一个确定的基，如果xij是基变量，则有由于基变量一共有m+n-1个，因此对偶问题一共有m+n-1个等式约束，只要先确定一个对偶变量的值，就可以由m+n-1个等式约束确定其余m+n-1个对偶变量的值。求出ui、vj的值以后，就可以进一步计算各非基变量的检验数。1BCWBTijjiijjmiTijijTijijijijcvuceeWcaWcacz)(BC1Bijjicvu-第3章 运输问题-40-产地销地A1A2 A3B1 B1 B3 B4 3 101 8 4 5 位势法:(3)(9)(7)(-2)(1)(-2)2.计算行位势和列位势；令u1=0，则依c

15、ij=ui+vj 计算各ui和vj 3.计算空格处位势；ij=ui+vj行位势列位势 03-2-539101.数字格处上添上对应的运价；销地A1 A2 A3B1 B1 B3 B43 11 3 10 1 9 2 8 7 4 10 5 产地单位运价表位势表:产地销地A1 A2 A37 4 9销量3 6 5 6635213产销平衡表B1 B1 B3 B4-第3章 运输问题-41-产地销地A1 A2 A3B1 B1 B3 B474 9产量销量3 6 5 6635213(0)(2)(2)(9)(1)(12)检验数表4.计算空格处检验数：ij=cij-ij3.解的改进-闭回路法（1）确定进基变量 检验数为

16、正数的非基变量（2）确定离基变量第5章 运输模型43表上作业法表上作业法调整非优方案的一般步骤与规则调整非优方案的一般步骤与规则 1 1进基变量的确定进基变量的确定规则规则 按按 min ijij 0 =lk 确定确定xlk进基。进基。若有多个若有多个lk同时最小，则选其中同时最小，则选其中最小运价最小运价minclk 所对应的那个所对应的那个 xlk进基进基;又若有多个这样的又若有多个这样的clk同时最小，同时最小，则从中任选一个则从中任选一个clk对应对应xlk的的 进基。进基。进而画出进而画出进基变量进基变量xlk的闭回路的闭回路及及奇偶点奇偶点。2 2离基变量的确定离基变量的确定规则规

17、则 在进基变量在进基变量xlk的闭回路上，按的闭回路上，按 xij-=min =xpq (为为奇点奇点 ）xij-确定确定xpq离基，同时也就确定离基，同时也就确定xpq的值的值 为为。若有多个奇点若有多个奇点 xpq 的值同时最小，则选其中的值同时最小，则选其中最大运价最大运价 maxcpq 所对所对应的那个应的那个xpq离基；又若有多个这样的离基；又若有多个这样的cpq同时最大，则从中任选一个同时最大，则从中任选一个cpq 对应的对应的xpq离基。离基。第5章 运输模型44表上作业法表上作业法3 3非最优方案的调整非最优方案的调整规则规则 xij+xij=+xij+(1 1)所有偶点的值所

18、有偶点的值 都加上调整量都加上调整量 ,得得(2 2)所有奇点的值所有奇点的值 都减去调整量都减去调整量 ,得得xij-xij-xij=-不在不在上的上的xij的的值值不变不变。在在上：上：-第3章 运输问题-45-3.3 3.3 产销不平衡运输问题及其应用产销不平衡运输问题及其应用Min z=cij xijni=1j=1mm)1,2,.,(i 1ainjijxn)1,.,j ;m.,1,(i 0n),.,1,2(j 1xijjmiijbx一、产销不平衡问题1产销Min z=cijxij+0 xi,n+1ni=1j=1mm)1,2,.,(i 11ainjijx1)nn,1,.,j ;m.,1,

19、(i 01)nn,.,1,2(j 1xijjmiijbxi=1m-第3章 运输问题-46-产地销地A1 A2 AmB1B2BnC11C12C1n C21C22C2n Cm1Cm2CmnBn+1 产销问题单位运价表销量产量b1b2bna1 a2 amaibj-第3章 运输问题-47-Min z=cij xijni=1j=1mm)1,2,.,(i 1ainjijxn)1,.,j ;m.,1,(i 0n),.,1,2(j 1xijjmiijbx2销产Min z=cijxij+0 xm+1,jni=1 j=1m1)mm,1,2,.,(i 1ainjijxn)1,.,j ;1mm,.,1,(i 0n),

20、.,1,2(j 11xijjmiijbxj=1n-第3章 运输问题-48-产地销地A1 A2 AmB1B2BnC11C12C1n C21C22C2n Cm1Cm2CmnAm+1销产问题单位运价表0 0 0销量产量b1b2bna1 a2 ambjai第5章 运输模型49 B1 B2 B3 ai A1 A2 A3 5 9 2 3 1 7 6 2 8 15 18 17 bj 18 12 16 50 46 表上作业法表上作业法 产销不平衡问题的解法产销不平衡问题的解法 第5章 运输模型50表上作业法表上作业法 B1 B2 B3 B4 ai A1 5 9 2 0 15 A2 3 1 7 0 18 A3

21、6 2 8 0 17 bj 18 12 16 4 50 第5章 运输模型51运输模型的应用运输模型的应用短缺资源的分配问题短缺资源的分配问题 例例4 自来水分配问题自来水分配问题 额额 外外 基基 本本第5章 运输模型525.3 5.3 运输模型的应用运输模型的应用 50C60B50A供供水水量量引水引水 区区 管理费管理费水库水库(虚虚)甲甲 甲甲1甲甲2需需 求求 量量 乙乙 丙丙 丁丁 丁丁1丁丁2160140190160140190M130130200M220190230170150MM170150M自来水分配问题自来水分配问题的的第5章 运输模型53运输模型的应用运输模型的应用210

22、501030702030需求量需求量502030脱销脱销5002030C60301020B5050A供水量供水量丁丁2 2丁丁1 1丙丙乙乙甲甲2 2甲甲1 1分配量分配量水库水库区区的的-第3章 运输问题-54-例一：某工厂按合同规定必须于当年的每个季度末分别提供10、15、25、20台同一规格的柴油机。已知该厂的生产能力及生产每台柴油机的成本如表示。又如果生产出来的柴油机当季不交货，每台每积压一个季度需要存储维护费用0.15万元。要求在完成合同的情况下，做出使全年生产费用最小的决策。季度生产能力(台)单位成本(万元/台)2535301010.8 11.1 11.0 11.34、应用运输问题

23、模型的其他实例-第3章 运输问题-55-模型：模型：设 xij第i季度生产，用于第j季度交货的数量。obj.min z=cij xiji=1j=1 4 4x11+x12+x13+x1425 x22+x23+x2435 x33+x3430 x4410 x11 =10 x12+x22 =15x13+x23+x33 =25x14+x24+x34+x44=20 xij 0,(i=1,4;j=1,4)供应：需求：-第3章 运输问题-56-单位费用表：单位费用表：10.8 10.95 11.10 11.25 M 11.10 11.25 11.40 M M 11.00 11.15 M M M 11.30单位

24、：万元供应需求-第3章 运输问题-57-例二：例二：某餐馆承办宴会，每晚连续举行，共举行五次。宴会上需用特殊的餐巾，根据参加的人数，预计每晚的需要量为：第一天1000条，第二天700条，第三天800条，第四天1200条，第五天1500条，五天之后，所有的餐巾作废。宴会中用过的餐巾经过洗涤处理后可以重复使用，这样可以降低使用成本。已知每条新餐巾需要1元的费用，送洗时可选择两种方式：快洗仅需要一天时间，每条洗涤费用为0.2元，慢洗需要两天时间，每条洗涤费用0.1元。问：如何安排，可使总费用最低？-第3章 运输问题-58-建立模型：建立模型：设 xj第j天使用新毛巾的数量；yij第i天送第j天使用快

25、洗 餐巾的数量；zij第i天送第j天使用慢洗餐巾的数量；第一天：x1=1000第二天：x2+y12=700第三天：x3+z13+y23=800第四天：x4+z14+z24+y34=1200第五天：x5+z15+z25+z35+y45=1500需求约束供应约束新购餐巾：x1+x2+x3+x4+x55200第一天送洗：y12+z13+z14+z151000第二天送洗：y23+z24+z25700第三天送洗：y34+z35800第四天送洗：y451200 xj0，yij0，zij0，（i=1,4；j=1,5）Min z=xj+0.2yij+0.1zij-第3章 运输问题-59-新 购 第一天第二天第三天第四天111110 M0.20.10.10.10MM0.20.10.10MMM0.20.10供应需求产量销 量5200 1000 700 8001200MMM0.20.101000700800120015003700产销平衡表人有了知识，就会具备各种分析能力，明辨是非的能力。所以我们要勤恳读书，广泛阅读，古人说“书中自有黄金屋。”通过阅读科技书籍，我们能丰富知识，培养逻辑思维能力；通过阅读文学作品，我们能提高文学鉴赏水平，培养文学情趣；通过阅读报刊，我们能增长见识，扩大自己的知识面。有许多书籍还能培养我们的道德情操，给我们巨大的精神力量，鼓舞我们前进。