运筹学课件17运输问题

1、第七节第七节 运输规划问题运输规划问题1、供求平衡的运输规划问题2、供求不平衡运输问题的解法3、运输问题的应用举例一、供求平衡运输规划问题供求平衡运输问题及其数学模型l例1-10l供求平衡运输问题l数学模型表上作业法l求初始基本可行解l计算检验数及最优解检验l调整求新解解的退化问题二、供求不平衡运输问题的解法供大于求的情况求大于供的情况都应化为供求平衡问题后再求解三、运输规划问题的应用举例例1-11l供求不平衡问题l按最低需求量计算是供大于求，首先增加一个销地将销地4增加一个分部l按最高需求量计算是可能求大于供，增加一产地4。例1-10设有三个电视机厂。生产同一种彩色电视机，日生产能力分别是：

2、50，60，50，供应四个门市部，日销售量分别是：40，40，60，20台，从各分厂运往各门市部的运费如表1-23所示，试安排一个运费最低的运输计划。 门市部工厂1234供应总计12397612359796711506050需求总计40406020供求平衡的运输问题：供：50+60+50=160 需：40+40+60+20=160数学模型04 , 3 , 2 , 1,3 , 2 , 1,. .min31413141ijjiijijijijijijxjdxisxtsxcz表上作业法运输问题的单纯形法运输问题总有最优解。求解步骤l确定初始可行解l求空格检验数，检验最优解l调整（换基、求新解）可行解

3、l重复作上述2、3两步，直至求得最优解。初始可行解（西北角法） 门市部工厂1234供应总计19129650273776036591150需求总计40406020初始可行解（西北角法） 门市部工厂1234供应总计19129650273776036591150需求总计40406020401030303020 门市部工厂1234供应总计19129650273776036591150需求总计40406020初始可行解（最小元素法）404020203010366799 门市部工厂1234供应总计19129650 401027377603030365911502030需求总计40406020计算检验数（闭

4、合回路法）计算检验数（闭合回路法）对于空格（1，4）其它的空格12)11712(936140)93(754)399(12762)117(977)39(1277)712(393231242113计算检验数（位势法）对偶问题的变量为 ，则约束条件为又因为检验数当 时，取得最优解，同时对偶问题的基本解可行（也最优）。根据单纯形法，对于基变量 。),(jivuy ijjicvujiijijijijvucyPc0ij0ij方程共有m+n-1个方程，但有m+n个变量，一般令 。因此可求得这些变量。我们称 分别为产地位势和销地位势。对于本例：计算检验数（位势法）ijjicvu01ujivu 和11,97,3

5、0,12,94333322212111vuvuvuvuuvuvu解得：因而可计算得计算检验数（位势法）18;7;16;9;12;9433221vuvuvv0, 4, 27127323124122121411414311313vucvucvuc调整基本解（换基和求新解）-闭合回路法取负检验数中绝对值最大的空格作回路。从空格开始依次给回路顶点格标“+”和“-”找出“-”格中运量最小者，作为调整量，将每个“+”格的运量加上该调整量，每个“-”格的运量减去该调整量。即得新的基本可行解。再计算空格检验数和调整基本解，直到检验数非负为止。例1-10西北角法初始解的调整 门市部工厂1234供应总计19129

6、650 + 4010 -273776030 -30+3659115020 -30+需求总计40406020调整的结果 门市部工厂1234供应总计19129650（5） 1040（12）273776020（-2）(-5)403659115010（-8） （0）40需求总计40406020调整的结果 门市部工厂1234供应总计19129650 104027377602040365911501040需求总计40406020+-+203010调整的结果 门市部工厂1234供应总计19129650-3 104042737760206340365911508040需求总计40406020203010最优解

7、（运费=980） 门市部工厂1234供应总计1912965030 20 （3）（7）273776020（3）（3）4036591150（5）40（0）10需求总计40406020最优解无穷多和解的退化问题因为 ，因此最优解有无穷多个。如何求其它最优解？出现零的数字格，即为解的退化问题l在求初始解时，添进一个数字格，若供和求同时满足，则引进一个零数字格；l在调整时，若有两个及以上最小运量的“-”格，调整后，将出现零数字格。如何添零数字格？（分两个情况考虑）032表1-35 初始解时的退化问题12345s1769355 2 3 2823576 5 135410695 1 4d235240表1-31

8、 调整引起的退化问题12s18730 20 1026920 (-4) 20d203012s18730 (4) 3026920 20 0d2030供大于求的情况数学模型0, 2 , 1, 2 , 1,. .min1111ijjmiijinjijminjijijxnjdxmisxtsxcz特点与处理办法特点处理办法：设置一个虚销售点n+1，使且 ，因而化为平衡问题。njjmiids11njjmiindsd11101,nic结果01, 2 , 1, 2 , 1,. .min11111ijjmiijinjijminjijijxnjdxmisxtsxcz求大于供数学模型0, 2 , 1, 2 , 1,.

9、 .min1111ijjmiijinjijminjijijxnjdxmisxtsxcz特点与处理办法特点处理办法：增加一个虚产地m+1，使且 ，化为平衡问题。njjmiids11miinjjmsds1110, 1jmc结果0, 2 , 1,1, 2 , 1,. .min11111ijjmiijinjijminjijijxnjdxmisxtsxcz例1-11 物资调度问题有一批物资在三个供应点，供应给四个需求点，运价如表1-36所示，但第三供应点不能向第四需求点运送该物资，求总运费最少的调运方案。1234s1231614191313202219231715M506050dmin3070010dm

10、ax507030不限化不平衡为平衡问题对第四需求点的最大供应量：160-100=60吨按最大需求计算，需求为：150+60=210吨因此设置虚的第四供应点，供应量：50吨1234s1231614191614191313202219231715M1715M506050d302070301050M0M0M0450初始可行解1234s116161322171750214141319151560319192023MM504M0M0M050d30207030105050502030101030100检验数1234s116161322171750（2） （2）50(4)021414131915156030

11、1020(-1)（-2）319192023MM50(0)10（2）30104M0M0M050(M)(3)(M)(-1)50d302070301050-M+22-M+20第一次调整1234s116161322171750500214141319151560301020319192023MM501030104M0M0M05050d302070301050(-M+20)10200第一次调整检验数1234s116161322171750（2） （2）50(4)（2）021414131915156030020(1)10(-2)319192023MM50（0）20（2）30(M)(M)4M0M0M050(

12、M)(3)(M)(-1)(M)50d302070301050第二次调整1234s11616132217175050021414131915156030020100319192023MM5020304M0M0M05050d302070301050第二次调整检验数1234s1161613221717502250422214141319151560300201100319192023MM500202304M0M0M0501-350d302070301050第三次调整1234s1161613221717505021414131915156030020100319192023MM5020304M0M0M

13、050050d302070301050第三次调整检验数1234s116161322171750(2)(5)50(7)(2)(2)21414131915156030（3）20(4)10319192023MM50（-3）20（-1）30(M)(M)4M0M0M050(4)(M)50d30207030105000第四次调整1234s11616132217175050214141319151560302010319192023MM5020304M0M0M05050d30207030105000第四次调整检验数1234s1161613221717505550722214141319151560332041030319192023MM503020-104M0M0M05043020d302070301050第五次调整1234s11616132217175050214141319151560201030319192023MM50302004M0M0M0503020d302070301050第五次调