运筹学运输问题求解方法学习教案

1、会计学1第一页，共21页。第1页/共21页第二页，共21页。160万t分析(fnx)：产销不平衡；根据现有产量，第IV地区最多能分配到:160-（30+70+0）=60万t(总厂量减去前三个地区最低需求量之和 ).210万t60万t则最大需求量为：50+70+30+60=210万t;最大需求210万t比供应(gngyng)160万t多50万t,因此需要虚拟一个供应(gngyng)点D，其供应(gngyng)量为50万t，使得供求平衡。第2页/共21页第三页，共21页。M（任意大正数)表示非常高的运价，M不会(b hu)进入最优解1I2I1IV2IV产销(chnxio)平衡表第3页/共21页第四

2、页，共21页。M（任意大正数)表示非常高的运价，M不会(b hu)进入最优解1I2I1IV2IV产销(chnxio)平衡表第4页/共21页第五页，共21页。M（任意大正数)表示非常高的运价(yn ji)，M不会进入最优解1I2I1IV2IV产销(chnxio)平衡表第5页/共21页第六页，共21页。*解的退化：在用最小元素法求解初始基本可行解时，当产销平衡表上填上一个数后，单位运价(yn ji)表上要同时划去一行和一列，则此时会出现退化。退化分为两种情况。1I2I1IV2IV20求解步骤：利用最小元素(yun s)法求解运输问题的初始解第6页/共21页第七页，共21页。1I2I1IV2IV20

3、30求解步骤：利用(lyng)最小元素法求解运输问题的初始解*解的退化情况(qngkung)1：在确定供需关系时，若在（i,j）格内填入数字后出现处 的余量等于 处的需量，此时在产销平衡表上填上一个数后，单位运价表上要同时划去一行和一列，并在划去的行或列的任一空格处填上一个0（始终保持表上有m+n-1个数字格）。iAjB第7页/共21页第八页，共21页。1I2I1IV2IV2030求解步骤(bzhu)：利用最小元素法求解运输问题的初始解*解的退化情况1：在确定(qudng)供需关系时，若在（i,j）格内填入数字后出现处 的余量等于 处的需量，此时在产销平衡表上填上一个数后，单位运价表上要同时划

4、去一行和一列，并在划去的行或列的任一空格处填上一个0（始终保持表上有m+n-1个数字格）。iAjB0第8页/共21页第九页，共21页。1I2I1IV2IV2030503020010050求解步骤(bzhu)：利用位势法求解表中所有非基变量的检验数)(vucjiijij2262221615141211，MMMMMM2242029243332312422，M2323252404645434135，第9页/共21页第十页，共21页。1I2I1IV2IV2030503020010050.求解步骤(bzhu)：利用闭回路法进行第一次方案调整30-20213131为换出变量，调整量为为换入变量，最小，故选

5、取检验数XXM第10页/共21页第十一页，共21页。1I2I1IV2IV20305030200103020求解(qi ji)步骤：利用闭回路法进方案调整得到下表表2221723191615141211，MMMMMMM2342025213332242221，MM242426414645434135，第11页/共21页第十二页，共21页。1I2I1IV2IV20305030200103020.求解步骤：表2未得最优解，用闭回路法进行(jnxng)第二次调整20-23363333为换出变量，调整量为为换入变量，最小，故选取检验数XXM第12页/共21页第十三页，共21页。1I2I1IV2IV2030

6、503020010500求解步骤：利用闭回路(hul)法进方案调整得到下表表3226041615141211，22-432-23532242221M，1134224645434136，MMMM第13页/共21页第十四页，共21页。1I2I1IV2IV2030503020010500.求解步骤： 表3未得最优解，用闭回路(hul)法进行第三次调整04-343232为换出变量，调整量为为换入变量，最小，故选取检验数XX第14页/共21页第十五页，共21页。1I2I1IV2IV2030503020010500求解步骤：利用闭回路法进方案调整得到(d do)下表表41210441615141211，2

7、2-47223534242221M，4-3-24234645434136，MMMM第15页/共21页第十六页，共21页。1I2I1IV2IV2030503020010500.求解步骤： 表4未得最优解，用闭回路(hul)法进行第四次调整204-424646为换出变量，调整量为为换入变量，最小，故选取检验数XX第16页/共21页第十七页，共21页。1I2I1IV2IV20305030200103020求解(qi ji)步骤：利用闭回路法进方案调整得到下表表5227441615141211，22-14223534242221M，MMMM4542413635332222，经检验，所有非基变量的检验数

8、均为非负，因而表5给出的基本可行(kxng)解，即为问题的最优解。 第17页/共21页第十八页，共21页。1I2I1IV2IV3002030103020502050204050 最少总运费(yn fi)为：Z=1950+1350+1320+1540=2460万元。第18页/共21页第十九页，共21页。总结(zngji)产销不平衡(pnghng)运输问题的求解方法:（1）产大于销的问题：增加虚销地，销量为产销之差，但实际没有运输，故单位运价为0，这样(zhyng)将该问题转化为产销平衡问题，然后用表上作业法求解。（2）产小于销的问题：增加虚产点，产量为销产之差，但实际没有运输，故单位运价为0，这样(zhyng)将该问题转化为产销平衡问题，然后用表上作业法求解。本次求解过程遇到的问题及解决思路:（1） 同一个地区有两种需求情况：凡是需求分两种情况的地区,可以看成两个销地：一个销地为了保证最低需求，对应的虚供应点的单位运价取任意大整数M(M不会进入最优解）。若已知某需求地 对某供应地 没有需求，则其相对应的单位运价取任意大整数M(M不会进入最优解）。（2）表上作业法计算中的退化问题：在用最小元素法求解初始可行解时，在（i,j）格内填入