运筹学运输问题求解方法.

1、特殊运输问题的求解方法特殊运输问题的求解方法例例5.5 产销不平衡运输问题的求解方法产销不平衡运输问题的求解方法 例例5.5 5.5 设有三个化肥厂供应四个地区的农用化肥。 假定等量的化肥在这些地区使用效果相同，各化肥厂 年产量、各地区年需量及从各化肥厂到各地区运送化 肥的单位运价(万元/万t）如5-25所示。试求出总运费 最少的化肥调拨方案。 160 万万t 分析：产销不平衡；根据现有产量，第分析：产销不平衡；根据现有产量，第IVIV地区最地区最 多能分配到多能分配到:160-:160-（30+70+030+70+0）=60=60万万t(t(总厂量减去总厂量减去 前三个地区最低需求量之和前三

2、个地区最低需求量之和 ). ). 210万万t60万万t 则最大需求量为：则最大需求量为：50+70+30+60=21050+70+30+60=210万万t;t; 最大需求最大需求210210万万t t比供应比供应160160万万t t多多5050万万t,t,因此需要因此需要 虚拟一个供应点虚拟一个供应点D D，其供应量为，其供应量为5050万万t t，使得供求，使得供求 平衡。平衡。 M（任意大正数（任意大正数)表示非常高的运价，表示非常高的运价，M不会进入最优解不会进入最优解 1 I 2 I 1 IV 2 IV 产销平衡表产销平衡表 M（任意大正数（任意大正数)表示非常高的运价，表示非常高

3、的运价，M不会进入最优解不会进入最优解 1 I 2 I 1 IV 2 IV 产销平衡表产销平衡表 M（任意大正数（任意大正数)表示非常高的运价，表示非常高的运价，M不会进入最优解不会进入最优解 1 I 2 I 1 IV 2 IV 产销平衡表产销平衡表 * *解的退化：解的退化：在用最小元素法求解初始基本可行解时，当产销平衡表上在用最小元素法求解初始基本可行解时，当产销平衡表上 填上一个数后，单位运价表上要同时划去一行和一列，则此时会出现退填上一个数后，单位运价表上要同时划去一行和一列，则此时会出现退 化。退化分为两种情况。化。退化分为两种情况。 1 I 2 I 1 IV 2 IV 20 求解步

4、骤：求解步骤：利用最小元素法求解运输问题的初始利用最小元素法求解运输问题的初始 解解 1 I 2 I 1 IV 2 IV 2030 求解步骤：求解步骤：利用最小元素法求解运输问题的初始利用最小元素法求解运输问题的初始 解解 * *解的退化情况解的退化情况1 1：在确定供需关系时，若在（在确定供需关系时，若在（i,j）格内填入数字后出现处）格内填入数字后出现处 的余量等于的余量等于 处的需量，此时在产销平衡表上填上一个数后，单位运价表上要处的需量，此时在产销平衡表上填上一个数后，单位运价表上要 同时划去一行和一列，并在划去的行或列的任一空格处填上一个同时划去一行和一列，并在划去的行或列的任一空格

5、处填上一个0（始终保持表（始终保持表 上有上有m+n-1个数字格）。个数字格）。 i A j B 1 I 2 I 1 IV 2 IV 20 30 求解步骤：求解步骤：利用最小元素法求解运输问题的初始利用最小元素法求解运输问题的初始 解解 * *解的退化情况解的退化情况1 1：在确定供需关系时，若在（在确定供需关系时，若在（i,j）格内填入数字后出现处）格内填入数字后出现处 的余量等于的余量等于 处的需量，此时在产销平衡表上填上一个数后，单位运价表上要处的需量，此时在产销平衡表上填上一个数后，单位运价表上要 同时划去一行和一列，并在划去的行或列的任一空格处填上一个同时划去一行和一列，并在划去的行

6、或列的任一空格处填上一个0（始终保持表（始终保持表 上有上有m+n-1个数字格）。个数字格）。 i A j B 0 1 I 2 I 1 IV 2 IV 2030 50 30 20 0 100 50 求解步骤：求解步骤：利用位势法求解表中所有非基变量的检验数利用位势法求解表中所有非基变量的检验数 )( vuc jiijij 226222 1615141211 ，MM MMMM224202924 3332312422 ， M232325240 4645434135 ， 1 I 2 I 1 IV 2 IV 2030 50 30 20 0 100 50 . . . . . . 求解步骤：求解步骤：利用

7、闭回路法进行第一次方案调整利用闭回路法进行第一次方案调整 30-20 213131 为换出变量，调整量为为换入变量，最小，故选取检验数XXM 1 I 2 I 1 IV 2 IV 2030 50 30 20 0 1030 20 求解步骤：求解步骤：利用闭回路法进方案调整得到下表表利用闭回路法进方案调整得到下表表2 22172319 1615141211 ，MMM MMMM234202521 3332242221 ， MM24242641 4645434135 ， 1 I 2 I 1 IV 2 IV 2030 50 30 20 0 1030 20 . . . . 求解步骤：求解步骤：表表2未得最优

8、解，用闭回路法进行第二次调整未得最优解，用闭回路法进行第二次调整 20-23 363333 为换出变量，调整量为为换入变量，最小，故选取检验数XXM 1 I 2 I 1 IV 2 IV 20 30 50 3020 0 1050 0 求解步骤：求解步骤：利用闭回路法进方案调整得到下表表利用闭回路法进方案调整得到下表表3 22604 1615141211 ， 22-432-2 3532242221 M， 113422 4645434136 ，MMMM 1 I 2 I 1 IV 2 IV 20 30 50 3020 0 1050 0 . . . . 求解步骤：求解步骤： 表表3未得最优解，用闭回路法

9、进行第三次调整未得最优解，用闭回路法进行第三次调整 04- 343232 为换出变量，调整量为为换入变量，最小，故选取检验数XX 1 I 2 I 1 IV 2 IV 20 30 50 3020 0 1050 0 求解步骤：求解步骤：利用闭回路法进方案调整得到下表表利用闭回路法进方案调整得到下表表4 121044 1615141211 ， 22-4722 3534242221 M， 4-3-2423 4645434136 ，MMMM 1 I 2 I 1 IV 2 IV 20 30 50 3020 0 1050 0 . . . . . . 求解步骤：求解步骤： 表表4未得最优解，用闭回路法进行第四

10、次调整未得最优解，用闭回路法进行第四次调整 204- 424646 为换出变量，调整量为为换入变量，最小，故选取检验数XX 1 I 2 I 1 IV 2 IV 20 30 50 30 20 0 1030 20 求解步骤：求解步骤：利用闭回路法进方案调整得到下表表利用闭回路法进方案调整得到下表表5 22744 1615141211 ， 22-1422 3534242221 M， MMMM 4542413635 332222， 经检验，所有非基变量的检验数均为非负，因而表经检验，所有非基变量的检验数均为非负，因而表5给出的基本可行解，给出的基本可行解， 即为问题的最优解。即为问题的最优解。 1 I

11、 2 I1 IV 2 IV 300 20 30 10 30 20 50 20 50 2040 50 最少总运费为：最少总运费为：Z=1950+1350+1320+1540=2460万元。万元。 总结总结 产销不平衡运输问题的求解方法产销不平衡运输问题的求解方法: （1）产大于销的问题：增加虚销地，销量为产销之差，但实际没有运输，故单位运）产大于销的问题：增加虚销地，销量为产销之差，但实际没有运输，故单位运 价为价为0，这样将该问题转化为产销平衡问题，然后用表上作业法求解。，这样将该问题转化为产销平衡问题，然后用表上作业法求解。 （2）产小于销的问题：增加虚产点，产量为销产之差，但实际没有运输，

12、故单位运）产小于销的问题：增加虚产点，产量为销产之差，但实际没有运输，故单位运 价为价为0，这样将该问题转化为产销平衡问题，然后用表上作业法求解。，这样将该问题转化为产销平衡问题，然后用表上作业法求解。 本次求解过程遇到的问题及解决思路本次求解过程遇到的问题及解决思路: （1） 同一个地区有两种需求情况：同一个地区有两种需求情况： 凡是需求分两种情况的地区凡是需求分两种情况的地区,可以看成两个销地：一个销地为了保证最低可以看成两个销地：一个销地为了保证最低 需求，对应的虚供应点的单位运价取任意大整数需求，对应的虚供应点的单位运价取任意大整数M(M不会进入最优解）。不会进入最优解）。 若已知某需求地若已知某需求地 对某供应地对某供应地 没有需求，则其相对应的单位运价取没有需求，则其相对应的单位运价取 任意大整数任意大整数M(M不会进入最优解）。不会进入最优解）。 （2）表上作业法计算中的退化问题：）表上作业法计算中的退化问题： 在用最小元素法求解初始可行解时，在（在用最小元素法求解初始可行解时，在（i,j）格内