运筹学课件第三节运输问题的进一步讨论.ppt

1、？转化转化0.min1111ijmiiijnjiijminjijijxbxaxstxcZminjjiba11minjjinnbabb11110)1,.,3,2,1(),.3,2,1(.min11111ijmijijnjiijminjijijxnnjbxmiaxstxcZB1B2BnBn+1(贮存)产量A1x11x12x1nX 1,n+1a1A2x21x22x2nX 2,n+1a2:Amxm1xm2XmnX m,n+1am销量 b1b2bnminjjiba11产地销地c11c1nc2n000cmncm2cm1c22c21c12 某公司有某公司有 A1、A2 两个分厂生产某种产两个分厂生产某种产品

2、，分别供应品，分别供应 B1、B2、B3 三个地区的销售三个地区的销售公司销售。假设两个分厂的产品质量相同，公司销售。假设两个分厂的产品质量相同，假设有两个中转站假设有两个中转站 T1、T2，并且物资的运输，并且物资的运输允许在各产地、各销地及各转运站之间，即允许在各产地、各销地及各转运站之间，即可以在可以在 A1、A2、B1、B2、B3、T1、T2 之间相之间相互转运。有关数据如下表所示，试求总费用互转运。有关数据如下表所示，试求总费用为最少的调运方案。为最少的调运方案。产产 地地中转站中转站销销 地地产产量量A1A2T1T2B1B2B3产产地地A1 12131137A21 351929中中

3、转转T123 1284T2151 452销销地地B13124 14B2119851 2B3324242 需求量需求量475 产地、销地及中转站的有关数据、运价（元产地、销地及中转站的有关数据、运价（元/kg）发送接受 解：从表可以看出，从解：从表可以看出，从 A1 到到 B2 直接运费单直接运费单价为价为 11 元元/kg；但从；但从 A1 经经 A2 到到 B2，运价为，运价为 1+9=10元元/kg；而从；而从 A1 经经 T2 到到 B2 只需只需 l+5=6元元/kg；若从；若从A1 到到 A2 再经再经 B1 到到 B2 仅仅需仅仅需 l+1+1=3元元/kg。可见转运问题比一般运输

4、。可见转运问题比一般运输问题复杂。现在我们把此转运问题化成一般问题复杂。现在我们把此转运问题化成一般运输问题，要做如下处理：运输问题，要做如下处理：由于问题中的所有产地、中转站、销地都由于问题中的所有产地、中转站、销地都可以看成产地，也可以看成销地，因此整个可以看成产地，也可以看成销地，因此整个问题可以看成一个有问题可以看成一个有7个产地有个产地有7个销地的扩个销地的扩大的运输问题；大的运输问题；对扩大了的运输问题建立运价表，将表中对扩大了的运输问题建立运价表，将表中不可能的运输方案用任意大的正数不可能的运输方案用任意大的正数M代替；代替；所有中转站的产量等于销量，也即流入量所有中转站的产量等

5、于销量，也即流入量等于流出量。等于流出量。每个中转站的转运量不会超过每个中转站的转运量不会超过 16 kg，可以规定，可以规定 T1，T2 的产量和销量均为的产量和销量均为 16 kg。由于实际的转运量：。由于实际的转运量：7,2,1isxin1jij7,2,1idxin1jij 这里这里si表示表示i点的流出量，点的流出量，dj表示表示j点的流入量，点的流入量，对中转点来说，因此对中转点来说，因此si=dj=16。这样可以在每个约束条件中增加一个松弛变这样可以在每个约束条件中增加一个松弛变量量xii，xii 相当于一个虚构的中转站，其意义相当于一个虚构的中转站，其意义就是自己运给自己。就是自

6、己运给自己。(16-xii)就是每个中转就是每个中转站的实际转运量，站的实际转运量，xii 的对应运价的对应运价cii=0；扩大了的运输问题中原来的产地与销地由扩大了的运输问题中原来的产地与销地由于也具有转运作用，所以同样在原来的产量与于也具有转运作用，所以同样在原来的产量与销量的数字上加上销量的数字上加上16 kg，即两个分厂的产量，即两个分厂的产量改为改为23、25 kg，销量均为，销量均为16 kg；三个销地；三个销地的每天销量改为的每天销量改为20、23、21 kg，产量均为，产量均为16 kg，同时引进，同时引进xii 为松弛变量。为松弛变量。于是得到带有中转运输的产销平衡运输表于是

7、得到带有中转运输的产销平衡运输表产产 地地中转站中转站销销 地地产产量量A1A2T1T2B1B2B3产产地地A1 0121311323A21 03519225中中转转T123 0128416T21510 45216销销地地B13124 01416B21198510 216B33242420 16需求量需求量16161616202321128带有中转站的产销平衡运输表带有中转站的产销平衡运输表 发送接受产产 地地中转站中转站销销 地地产产量量A1A2T1T2B1B2B3产产地地A1 12131137A21 351929中中转转T123 1284T2151 452销销地地B13124 14B211

8、9851 2B3324242 需求量需求量475 使用生产B1B2B3生产量A1243 6a1 11A2156 a2=7A3324 a34使用量1046 使用生产B1B2B3B4（虚拟）生产量A1243M 6（必须发出的）（必须发出的）A12430 5A2156M 7（必须发出的）（必须发出的）A3324M 4（必须发出的）（必须发出的）A33240 3使用量10465解：当解：当A1A1的产量的产量a a1=6=6（min)min)，A1,A2A1,A2的产量之和的产量之和=13=13，总需求量为，总需求量为2020，所以，所以在产销平衡的情况下在产销平衡的情况下 A3A3的产量最大为的产量

9、最大为7 7；如果如果A1,A3A1,A3的产量均取最大的产量均取最大1111，7 7，则总产量大于总需求，则总产量大于总需求2020，此时应增加一，此时应增加一个虚销地个虚销地B4,B4,需求量为需求量为5 5。例例3 3：某公司承担：某公司承担4 4条航线运输任务，已知（条航线运输任务，已知（1 1）各条航线的起）各条航线的起点和终点以及每天的航班数；各个城市之间的航行时间；每次点和终点以及每天的航班数；各个城市之间的航行时间；每次装船、卸船时间均为装船、卸船时间均为1 1天；问题：公司至少需要配备多少条船天；问题：公司至少需要配备多少条船才能满足需要？才能满足需要？航线起点城市终点城市每

10、天航班数量1234EBADDCFB3211从 至 ABCDEFABCDEF0121477103138823015551413150172078517037852030航线装船（天）卸船（天）航行（天）小记（天）航班数量所需船数12341111111117371319591532115710915所需要船只共91条船。城市ABCDEF每天到达每天需要余缺数01-112-120231203-3101 至由ABE多余船只C235 2D141317 2F783 1缺少船只11351,1,1,1,11,1,1,2FEDEDBCECAFEDBDACExxxxxxxxx和 nmmmmnmmmmmbbbbbb

11、aaaaaaa,.,0.0.,.,212121121)(0),.,2,1(.),.,2,1(0.),.,2,1(0.),.,2,1(.min,1,121,1,1211,1,211,1,21111jixnmmmjbtxxxxxmjtxxxxxnmmmitxxxxxmiatxxxxxsttcxcSijjjmjjjjjjjjmjjjjjjjiimiiiiiiiiimiiiiiinmiiijinminmjijij4个约束条件两边均加上Q;令xii=Q-ti,xjj=Q-tjnmmmmnmmmmmbbbbbbaaaaaaa,.,0.0.,.,212121121)(0),.,2,1(.),.,2,1(0.

12、),.,2,1(0.),.,2,1(.min,1,121,1,1211,1,211,1,21111jixnmmmjbQtQxxxxxmjQtQxxxxxnmmmiQtQxxxxxmiaQtQxxxxxsttcxcSijjjmjjjjjjjjmjjjjjjjiimiiiiiiiiimiiiiiinmiiijinminmjijij)(0),.,2,1(.),.,2,1(0.),.,2,1(0.),.,2,1(.min,1,121,1,1211,1,211,1,21111jixnmmmjbQxxxxxxmjQxxxxxxnmmmiQxxxxxxmiaQxxxxxxsttcxcSijjjjmjjjjj

13、jjjjmjjjjjjjiiimiiiiiiiiiimiiiiiinmiiijinminmjijijnmiijnmiiijnmmmiQxmiaQx11),.,2,1(),.,2,1(nmiijnmijijnmjijnmjiijnmiinminmjijijnmiinmiiiijinminmjijijnmiiiijinminmjijijnmmmjQxmjbQxnmmmiQxmiaQxstQcxcQcxcxcxQcxcS11111111111111),.,2,1(),.,2,1(),.,2,1(),.,2,1(.)(minxij0(i,j=1,2,m+n)说明:当i=j时,所有的cij=-ci产地销

14、地发送量1 .mm+1.m+n产地1.mx11.x1m.Xm1.xmmX1,m+1.x1,m+n.Xm,m+1xm,m+nQ+a1Q+am目的地m+1.m+nxm+1,1xm+1,m.Xm+n,1xm+n,mXm+1,m+1.xm+1,m+n.Xm+n,m+1.xm+n,m+nQQ接受量Q QQ+b m+1.Q+b m+n发送接受 接受发送产地销地发送量1.mm+1.m+n产地1.m-c1.c1m.cm1.-cmc1,m+1.c1,m+n.cm,m+1cm,m+nQ+a1Q+am目的地m+1.m+ncm+1,1cm+1,m.cm+n,1 cm+n,m-cm+1.cm+1,m+n.cm+n,m+

15、1.-cm+nQQ接受量Q QQ+b m+1.Q+b m+n12345104020305225643543153运输系统，运输系统，2个产地个产地1，2；一个中间转运站；一个中间转运站3；2个目的地个目的地4，5；产地的产量产地的产量a1=10,a2=40,a3=a4=a5=0;目的地接受量目的地接受量b1=b2=b3=0,b4=30,b5=20 接受发送产地转运 销地发送量12345产地 1-4532M 6025-12M4 90转运 332-355 50销地 42M5-36 505M456-5 50接受量5050508070 接受发送产地转运 销地发送量12345产地 1501060250202090转运 350050销地 4505055050接受量5050508070 接受发送产地转运 销地发送量12345产 地 1501060250202090转 运 3302050销 地 4505055050接受量5050508070Z=C14x14+c25x25+c23x23+c3x34+c34x34=2X10+4X20+2X20+3X20+5X20=300小结小结:产销不平衡的运输问题和有转运的产销不平衡的运输问题和有转运的运输问题。运输问题。