运筹学运输问题[1]学习教案

《运筹学运输问题[1]学习教案》由会员分享，可在线阅读，更多相关《运筹学运输问题[1]学习教案（73页珍藏版）》请在装配图网上搜索。

1、会计学1第一页，共73页。使总运费最小。第1页/共73页第二页，共73页。第2页/共73页第三页，共73页。销地销地产地产地B1B2B3B4产量产量A1 41241116A2 2103910A3 8511622销量销量 814121448运输问题(wnt)的LP模型 第3页/共73页第四页，共73页。供应(gngyng)平衡条件产 地 ( c h n d ) A 1 ：x11+x12+x13+x14=16产 地 ( c h n d ) A 2 ：x21+x22+x23+x24=10产 地 ( c h n d ) A 3 ： x31+x32+x33+x34 =22销售(xioshu)平衡条件销地

2、B1：x11+x21+x31=8销地B2： x12+x22+x32=14销地B3： x13+x23+x33=12销地B4： x14+x24+x34=14非负性约束 xij0 (i=1,2,3；j=1,2,3,4) 第4页/共73页第五页，共73页。 销地产地A1A2Am产量a1a2amB1B2Bn销地b1b2bnc11c12c1nc21 c22c2ncm1cm2cmn x11 x12 x1nx21 x22 x2n xm1 xm2 xmn第5页/共73页第六页，共73页。minjjiba110,.,2 , 1,.,2 , 1,min1111ijmijijnjiijminjijijxnjbxmia

3、xxcZ第6页/共73页第七页，共73页。产大于销minjjiba110,.,2 , 1,.,2 , 1,min1111ijmijijnjiijminjijijxnjbxmiaxxcZ第7页/共73页第八页，共73页。产小于销minjjiba110,.,2 , 1,.,2 , 1,min1111ijmijijnjiijminjijijxnjbxmiaxxcZ第8页/共73页第九页，共73页。111111111111111111Ax11x12x1nx21x22x2nxm1xm2 xmnm行n列第9页/共73页第十页，共73页。10001000100001000100010000100010001

4、0000100010001111100000000000011110000000000001111A343332312423222114131211xxxxxxxxxxxx约束(yush)1约束(yush)2约束(yush)3约束(yush)4约束(yush)5约束(yush)6约束(yush)7第10页/共73页第十一页，共73页。第11页/共73页第十二页，共73页。束条件是线性独立的，所以一般我们在迭代过程中都保持基变量的个数为(m+n-1)个。第12页/共73页第十三页，共73页。第13页/共73页第十四页，共73页。第14页/共73页第十五页，共73页。第15页/共73页第十六页，共

5、73页。第16页/共73页第十七页，共73页。销地销地产地产地B1B2B3B4产量产量A141241116A22103910A38511622销量销量814121448初始(ch sh)基可行解：x11=8,x12=8,x22=6,x23=4,x33=8,x34=14，Z=3728864814（8）第17页/共73页第十八页，共73页。第18页/共73页第十九页，共73页。销地销地产地产地B1B2B3B4产量产量A141241116A22103910A38511622销量销量814121448初始(ch sh)基可行解：x13=10,x14=6,x21=8,x23=2,x32=14,x34=8

6、，Z=24682101486第19页/共73页第二十页，共73页。第20页/共73页第二十一页，共73页。销地销地产地产地B1B2B3B4产量产量A141241116A22103910A38511622销量销量814121448列罚数行罚数10111 2 5 1 31420122 2 1 383013 2 1 284764 1 2125005 224初始(ch sh)基可行解：x13=12,x14=4,x21=8,x24=2,x32=14,x34=8，Z=244第21页/共73页第二十二页，共73页。闭回路(hul)法对偶变量法第22页/共73页第二十三页，共73页。第23页/共73页第二十四

7、页，共73页。由线性规化的模型可以(ky)看出：ij= cij CBPij= cij CBB-1Pij运输问题的目标函数要求为最小，即当ij0视为最优。也就是说只要存在ij小零，此时就不能得到最优解。闭回路法就为我们提供了一种计算非基变量检验数的方法第24页/共73页第二十五页，共73页。销地销地产地产地B1B2B3B4产量产量A141241116A22103910A38511622销量销量81412144882101486以最小元素(yun s)法C11-C21+C23-C31=4-2+3-4=1C22-C32+C34-C14+C13-C23=10-5+6-11+4-3=1第25页/共73页

8、第二十六页，共73页。 销地产地 B1B2B3B4产量A112A21-1A31012销量在这个之中存在检验数小于零，所以此时没有(mi yu)得到最优解。第26页/共73页第二十七页，共73页。封闭多边形，可以证明，每个空格都唯一存在这样的一条闭回路。n闭回路可以是一个简单的矩形，也可以是由水平和竖直边线组成的其它更复杂的封闭多边形。第27页/共73页第二十八页，共73页。VOGEL法得到的解满足这些条件。第28页/共73页第二十九页，共73页。第29页/共73页第三十页，共73页。muuu,21nvvv,21),(2121nmvvvuuuY的符号不限jiijjinjjjmiiivunjmic

9、vuvbuaz, 1, 1max11(3.7)第30页/共73页第三十一页，共73页。线性规划(xin xn u hu)问题的检验数Xj的检验数可表示为：jjjBjjjjYPcPBCczc1)(),(2121jiijijnmijijijijijijvucPvvvuuucYPczc所以(suy)运输问题某量的Xij的检验数为：现设我们已得到(d do)了运输问题的一个基可行解，其基变量是：1,2211nmsxxxisjsjiji第31页/共73页第三十二页，共73页。对应于这些基变量(binling)的检验数都为零，即这些基变量(binling)的检验数可写为方程组：isjsjsisjijiji

10、jicvucvucvu22221111（3.9）第32页/共73页第三十三页，共73页。显然，上述方程组有m+n-1 个方程。运输表中每个产地和每个销地都对应(duyng)原运输问题的一个约束条件，从而也对应(duyng)各自的一个对偶变量；由于运输表中每行和每列都含有基变量，可知这样构造的方程组中含有全部m+n个对偶变量。可以证明，方程组(3.9)有解，且由于对偶变量数比方程数多一个，故解不唯一。方程(3.9)的解称为位势。第33页/共73页第三十四页，共73页。0)(jiijijvuc由前面的互补松定理，此时对偶问题(wnt)与原问题(wnt)同时达到最优解。若由(3.9)解得的某组解不满

11、足(3.7)的所有约束条件，即非基变量的检验数有负值存在，则上面得到的运输问题(wnt)的解不是最优解，需要进行解的调整。第34页/共73页第三十五页，共73页。销地销地产地产地aB1B2B3B4产量产量A141241116A22103910A38511622销量销量81412144882101486uiu1u2u3 vj v1 v2 v3 v4(1)对于上表(shn bio)中增加一位势列ui和位势行vj，如下所示第35页/共73页第三十六页，共73页。6532114432332124131vuvuvuvuvuvu对于(duy)左式的计算，为计算方便，常任意指定一位势等于一个较小的整数或零。

12、为了和书上一致，我们假定u2=0，由此可算出：V1=3,V3=3,u1=1,v4=10,u3=-4V2=9, 将其填入表中的圆括号内。如上页所示。第36页/共73页第三十七页，共73页。一般情况下我们不用(byng)列方程求解，直接在表中假设任意一个位势为0,不妨我们也假设u2=0销地销地产地产地aB1B2B3B4产量产量A141241116A22103910A38511622销量销量81412144882101486Ui vjU2(0)V1(2)V3(3)U1(1)V4(10)U3(-4)V2(9)第37页/共73页第三十八页，共73页。销地销地产地产地aB1B2B3B4产量产量A14124

13、1116A22103910A38511622销量销量814121448Ui vjU2(0)V1(2)V3(3)U1(1)V4(10)U3(-4)V2(9)(3)计算各个(gg)非基变量的检验数111=C11-U1-V1=121-11012由以上可以看出(kn ch)，位势法与用闭回路法算出的检验数完全相同，因24=-10,故这个解不是最优解。第38页/共73页第三十九页，共73页。第39页/共73页第四十页，共73页。值，从而得出一新的运输方案。该运输方案的总运费比原运输方案减少，改变量等于ijeLx)(minijeLx)(min)(min)(ijeLx第40页/共73页第四十一页，共73页。

14、解：由前面的表可知，由于 24=-10,故以X24为换入变量(binling)，它对应的闭回路示于如下表销地销地产地产地aB1B2B3B4产量产量A141241116A22103910A38511622销量销量81412144882101486第41页/共73页第四十二页，共73页。2)2,6min(),min(2314xx销地销地产地产地aB1B2B3B4产量产量A141241116A22103910A38511622销量销量81412144882101486所以(suy)对 x24+2 x14-2 x13+2 x23-2+2-2+2-2第42页/共73页第四十三页，共73页。销地销地产地产

15、地aB1B2B3B4产量产量A141241116A22103910A38511622销量销量81412144882121484现在用位势法或闭回路法求这个新基可行(kxng)解各非基变量的检验数，结果如上图所示(0)(2)(2)(1)(9)(12)由于所有非基变量的检验数全非负，故这个(zh ge)解为最优解。从图中我们还可以看出，有一个非基变量的检验数为0，所以存在无穷多最优解。第43页/共73页第四十四页，共73页。有多重（无穷多）最优解。第44页/共73页第四十五页，共73页。ge)0变量，使迭代过程中基可行解的分量恰好为（m+n-1)个。第45页/共73页第四十六页，共73页。第46页

16、/共73页第四十七页，共73页。产大于销minjjiba110,.,2 , 1,.,2 , 1,min1111ijmijijnjiijminjijijxnjbxmiaxxcZ对于这种问题(wnt)，我们可以增加一个销地，使其变为产销平衡问题(wnt)！第47页/共73页第四十八页，共73页。例：销地销地产地产地B1B2B3产量产量A159215A231718A362817销量销量181216增加(zngji)一个销地销地销地产地产地B1B2B3产量产量A159215A231718A362817销量销量18121650-4650465050B40004第48页/共73页第四十九页，共73页。初始

17、(ch sh)基可行解(最小元素法)销地销地产地产地B1B2B3B4产量产量A1592015A2317018A3628017销量销量1812164121561214 初始(ch sh)基可行解：x13=15,x21=6,x22=12,x31=12,x33=1,x34=4，Z=140第49页/共73页第五十页，共73页。最优性检验(jinyn)销地销地产地产地B1B2B3B4产量产量uiA159215015A2361127018A36122810417销量销量1812164vj0260-63-2 非基变量(binling)x32的检验数32= -2，即让非基变量(binling)x32进基。第5

18、0页/共73页第五十一页，共73页。闭回路(hul)调整x32 进基最小调整(tiozhng)量为12， x22 离基销地销地产地产地B1B2B3B4产量产量A159215015A2361127018A36122 x32 810417销量销量1812164-+-+第51页/共73页第五十二页，共73页。非最优方案的调整(tiozhng)所有偶点的值都加上调整(tiozhng)量；所有奇点的值都减去调整(tiozhng)量。 基可行(kxng)解：x13=15,x21=18,x31=0,x32=12,x31=1,x34=4，Z=34销地销地产地产地B1B2B3B4产量产量A159215015A2

19、317018A362810417销量销量181216461212 180 12 第52页/共73页第五十三页，共73页。l基变量的检验数ij= cij ui vj =0，且令u1 =0，计算(j sun)位势量ui和vj最优性检验(jinyn) 所有非基变量(binling)xij的检验数ij= cij ui vj0，即得最优解。销地销地产地产地B1B2B3B4产量产量uiA159215015A231817018A360212810417销量销量1812164vj0260-4-63第53页/共73页第五十四页，共73页。产小于销minjjiba110,.,2 , 1,.,2 , 1,min11

20、11ijmijijnjiijminjijijxnjbxmiaxxcZ对于这种问题，我们可以增加一个产地(chnd)，使其变为产销平衡问题！第54页/共73页第五十五页，共73页。增加(zngji)一个产地例：销地销地产地产地B1B2B3产量产量A141210A234312销量销量8105销地销地产地产地B1B2B3产量产量A141210A234312A3销量销量810523-22000122232323第55页/共73页第五十六页，共73页。初始(ch sh)基可行解销地销地产地产地B1B2B3产量产量A141210A234312A30001销量销量8105100571 初始(ch sh)基可

21、行解：x12=10,x13=0,x21=7,x23=5,x31=1，Z=46第56页/共73页第五十七页，共73页。最优性检验(jinyn)销地销地产地产地B1B2B3产量产量uiA141102010A23743512A301001销量销量8105vj01212-2检验数ij0，得最优解:x12=10, x13=0, x21=7, x23=5, x31=1，Z=46由于非基变量 x33 的检验数33=0，为多最优解。 让x33进基,x31离基,得另一最优解:x12=10, x13=0, x21=8, x23=4, x33=1上例x12=10, x13=0, x21=7, x23=5, x31=

22、1，表示销地B1脱销(tu xio)1个单位； 然而x12=10, x13=0, x21=8, x23=4, x33=1 ，则表示销地B3 脱销(tu xio)1个单位；第57页/共73页第五十八页，共73页。第58页/共73页第五十九页，共73页。生产与储存问题例1、某厂按合同规定须于当年每个季度(jd)末分别提供10、15、25、20台同一规格的柴油机。已知该厂各季度(jd)的生产能力及生产每台柴油机的成本如右表。如果生产出来的柴油机当季不交货，每台每积压一个季度(jd)需储存费用0.15万元。试求在完成合同的情况下，使该厂全年生产总费用为最小的决策方案。生产能力（台） 单位成本（万元）一

23、季度2510.8二季度3511.1三季度3011.0四季度1011.3第59页/共73页第六十页，共73页。解： 设 xij为第 i 季度生产的第 j 季度交货(jio hu)的柴油机数目，那末应满足： 交货(jio hu)：x11 = 10 生产：x11 + x12 + x13 + x14 25 x12 + x22 = 15 x22 + x23 + x24 35 x13 + x23 + x33 = 25 x33 + x34 30 x14 + x24 + x34 + x44 = 20 x44 10 第60页/共73页第六十一页，共73页。第 一 季 度 第 二 季 度 第 三 季 度 第 四

24、季 度D产 量第 一 季 度10.8010.9511.1011.2025第 二 季 度M11.1011.2511.40035第 三 季 度MM11.0011.15030第 四 季 度MMM11.30010销 量1015252030建立如下(rxi)运输表：把第 i 季度生产(shngchn)的柴油机数目看作第 i 个生产(shngchn)厂的产量；把第 j 季度交货的柴油机数目看作第 j 个销售点的销量；第61页/共73页第六十二页，共73页。第62页/共73页第六十三页，共73页。例2：自来水分配问题(wnt)：水价90元/千吨，管理费45元/千吨，引水费价格如下表：供区水库甲乙丙丁供水量k

25、t/dA1613221750B1413191560C192023-50最低需求kt/d3070010最高需求kt/d507030不限第63页/共73页第六十四页，共73页。如何分配供水量，保障各区最低需求(xqi)，获利最大？ 利润=收入-成本，收入最大，成本最小，则利润最大。收入：每天供水总量是一常数，水价也是常数，则每天总收入也是常数。每天供水总量若能全部售出，每天总收入则能达到最大。丁区最高需求不限，每天总供水量能全售出。每天总收入是常数，与水量分配无关(wgun)，可以不与考虑。成本：各区管理费相同45元/kt，每天售水总量是一常数，则管理费也是常数。各区引水费不同，如果总的引水费达到

26、最小，总成本则最低。如何分配水量，既满足最低需求，又使总的引水费最低？ 分析(fnx)第64页/共73页第六十五页，共73页。最大需求量：供水总量=50+60+50=160，四区最低需求量=30+70+10=110，故丁区最大需求量160-110+10=60。四区最大需求=50+70+30+60=210，比供水总量160多50，则是一个(y )产小于销的不平衡问题。产小于销的运输问题化为平衡问题，虚设水库D，供水量50。各区的最低需求(xqi)为基本需求(xqi)，不允许脱销，不能由虚设水库D供水，故单位引水费（运费）为M。各区的最大需求(xqi)与最低需求(xqi)的差为额外需求(xqi)，

27、可以由虚设水库D供水，故单位引水费（运费）为0 。第65页/共73页第六十六页，共73页。供区水库供水量A50B60C50甲1甲2乙丙丁1丁216161322171714141319151519192023MM销量302070301050DM0M0M050用表上作业(zuy)法求得最优方案供区水库甲1甲2乙丙丁1丁2供水量A5050B20103060C3020050D302050销量302070301050第66页/共73页第六十七页，共73页。最优分配方案：水库A向乙区供水50，水库B分别向乙区、丁区供水20和40，水库C向甲区供水50，不给丙区供水。最小引水(ynshu)费：1350+13

28、20+ 15(10+30)+19(30+20) =2460 引水(ynshu)管理费：45(50+60+50)=7200 总成本：2460+7200=9600 总收入：90(50+60+50)=14400 最大获利：14400-9600=47403.7 3.8表3-35 3-9 及下例第67页/共73页第六十八页，共73页。1、设有A、B、C三个化肥(hufi)厂供应1、2、3、4四个地区的农用化肥(hufi)。假设效果相同，有关数据如下表，试求总费用为最低的化肥(hufi)调拨方案。 1 2 3 4 产量 A 16 13 22 17 50 B 14 13 19 15 60 C 19 20 2

29、3 - 50 最低需要量 30 70 0 10 最高需要量 50 70 30 不限 第68页/共73页第六十九页，共73页。2、石家庄北方研究院有一、二、三三个区。每年分别需要用煤3000、， 1000、2000吨，由河北临城、山西盂县两处煤矿负责供应，价格、质量相同。供应能力分别为1500、4000吨，运价为如下表，由于需大于供，经院研究决定一区供应量可减少0-200吨，二区必须满足需求量三区供应量不少(b sho)于1700吨，试求总费用为最低的调运方案。一区二区三区产量山西盂县1.651.701.754000河北临城1.601.651.701500需要量300010002000第69页/

30、共73页第七十页，共73页。1、参考答案解： 根据(gnj)题意，作出产销平衡与运价表如下， 最低要求必须满足，因此把相应的虚设产地运费取为 M ，而最高要求与最低要求的差允许按需要安排，因此把相应的虚设产地运费取为 0 。对应 4”的销量 50 是考虑问题本身适当取的数据，根据(gnj)产销平衡要求确定 D的产量为 50。 11”2344”产量A16161322171750B14141319151560C19192023MM50DM0M0M050销量302070301050第70页/共73页第七十一页，共73页。2、参考答案：解： 根据题意，作出产销平衡与运价表如下，这里 M 代表一个(y )很大的正数，其作用是强迫相应的 x31、 x33、 x34取值为0。 一区一区二区三区三区产量山西盂县1.651.651.701.751.754000河北临城1.601.601.651.701.701500假想生产点M0MM0500需要量280020010001700300第71页/共73页第七十二页，共73页。本章(bn zhn)小结End第72页/共73页第七十三页，共73页。