运筹学运输问题求解方法

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

2、求平衡。,M（任意大正数)表示非常高的运价，M不会进入最优解,产销平衡表,M（任意大正数)表示非常高的运价，M不会进入最优解,产销平衡表,M（任意大正数)表示非常高的运价，M不会进入最优解,产销平衡表,*解的退化：在用最小元素法求解初始基本可行解时，当产销平衡表上填上一个数后，单位运价表上要同时划去一行和一列，则此时会出现退化。退化分为两种情况。,20,求解步骤：利用最小元素法求解运输问题的初始解,20,30,求解步骤：利用最小元素法求解运输问题的初始解,*解的退化情况1：在确定供需关系时，若在（i,j）格内填入数字后出现处 的余量等于 处的需量，此时在产销平衡表上填上一个数后，单位运价表上要

3、同时划去一行和一列，并在划去的行或列的任一空格处填上一个0（始终保持表上有m+n-1个数字格）。,20,30,求解步骤：利用最小元素法求解运输问题的初始解,*解的退化情况1：在确定供需关系时，若在（i,j）格内填入数字后出现处 的余量等于 处的需量，此时在产销平衡表上填上一个数后，单位运价表上要同时划去一行和一列，并在划去的行或列的任一空格处填上一个0（始终保持表上有m+n-1个数字格）。,0,20,30,50,30,20,0,10,0,50,求解步骤：利用位势法求解表中所有非基变量的检验数,20,30,50,30,20,0,10,0,50,.,.,.,.,求解步骤：利用闭回路法进行第一次方案

4、调整,20,30,50,30,20,0,10,30,20,求解步骤：利用闭回路法进方案调整得到下表表2,20,30,50,30,20,0,10,30,20,.,.,.,.,求解步骤：表2未得最优解，用闭回路法进行第二次调整,20,30,50,30,20,0,10,50,0,求解步骤：利用闭回路法进方案调整得到下表表3,20,30,50,30,20,0,10,50,0,.,.,.,.,求解步骤： 表3未得最优解，用闭回路法进行第三次调整,20,30,50,30,20,0,10,50,0,求解步骤：利用闭回路法进方案调整得到下表表4,20,30,50,30,20,0,10,50,0,.,.,.,.

5、,.,.,求解步骤： 表4未得最优解，用闭回路法进行第四次调整,20,30,50,30,20,0,10,30,20,求解步骤：利用闭回路法进方案调整得到下表表5,经检验，所有非基变量的检验数均为非负，因而表5给出的基本可行解，即为问题的最优解。,30,0,20,30,10,30,20,50,20,50,20,40,50,最少总运费为：Z=1950+1350+1320+1540=2460万元。,总结,产销不平衡运输问题的求解方法:,（1）产大于销的问题：增加虚销地，销量为产销之差，但实际没有运输，故单位运价为0，这样将该问题转化为产销平衡问题，然后用表上作业法求解。 （2）产小于销的问题：增加虚产点，产量为销产之差，但实际没有运输，故单位运价为0，这样将该问题转化为产销平衡问题，然后用表上作业法求解。,本次求解过程遇到的问题及解决思路:,（1） 同一个地区有两种需求情况： 凡是需求分两种情况的地区,可以看成两个销地：一个销地为了保证最低需求，对应的虚供应点的单位运价取任意大整数M(M不会进入最优解）。 若已知某需求地 对某供应地 没有需求，则其相对应的单位运价取任意大整数M(M不会进入最优解）。 （2）表上作业法计算中的退化问题： 在用最小元素法求解初始可行解时，在（i,j）格内填入数字后出现