运筹学运输问题求解方法

特殊运输问题的求解方法—例5.5产销不平衡运输问题的求解方法•例5.5设有三个化肥厂供应四个地区的农用化肥。假定等量的化肥在这些地区使用效果相同，各化肥厂年产量、各地区年需量及从各化肥厂到各地区运送化肥的单位运价(万元/万t）如5-25所示。试求出总运费最少的化肥调拨方案。运价需求化肥厂IIIIIIIV产量A1613221750B1413191560C192023-50最低需求3070010最高需求507030不限运价需求化肥厂IIIIIIIV产量A1613221750B1413191560C192023-50最低需求3070010110(万t)不限最高需求507030不限160万t分析：产销不平衡；根据现有产量，第IV地区最多能分配到:160-（30+70+0）=60万t(总厂量减去前三个地区最低需求量之和).210万t60万t则最大需求量为：50+70+30+60=210万t;最大需求210万t比供应160万t多50万t,因此需要虚拟一个供应点D，其供应量为50万t，使得供求平衡。运价需求化肥厂IIIIIIIV产量A1613221750B1413191560C192023-50最低需求3070010110万t（210）最高需求507030不限（60）运价需求地供应地IIIII供应量A161650B141460C191950DM050需求量3020M（任意大正数)表示非常高的运价，M不会进入最优解1I2I1IV2IV产销平衡表运价需求化肥厂IIIIIIIV产量A1613221750B1413191560C192023-50最低需求3070010110t（210）最高需求507030不限（60）运价需求地供应地IIIII供应量A16161350B14141360C19192050DM0M50需求量302070M（任意大正数)表示非常高的运价，M不会进入最优解1I2I1IV2IV产销平衡表运价需求化肥厂IIIIIIIV产量A1613221750B1413191560C192023-50最低需求3070010110t（210）最高需求507030不限（60）运价需求地供应地IIIII供应量A16161322171750B14141319151560C19192023MM50DM0M0M050需求量302070301050M（任意大正数)表示非常高的运价，M不会进入最优解1I2I1IV2IV产销平衡表运价需求地供应地IIIII供应量A1616×1322171750B1414×1319151560C1919×2023MM50DM0M0M050需求量302070301050*解的退化：在用最小元素法求解初始基本可行解时，当产销平衡表上填上一个数后，单位运价表上要同时划去一行和一列，则此时会出现退化。退化分为两种情况。1I2I1IV2IV20求解步骤：利用最小元素法求解运输问题的初始解运价需求地供应地IIIII供应量A1616×1322×171750B1414×1319×151560C1919×2023×MM50DM×0M×0M×0×50需求量3020703010501I2I1IV2IV2030求解步骤：利用最小元素法求解运输问题的初始解*解的退化情况1：在确定供需关系时，若在（i,j）格内填入数字后出现处的余量等于处的需量，此时在产销平衡表上填上一个数后，单位运价表上要同时划去一行和一列，并在划去的行或列的任一空格处填上一个0（始终保持表上有m+n-1个数字格）。iAjB运价需求地供应地IIIII供应量A1616×1322×171750B1414×1319×151560C1919×2023MM50DM×0M×0M×0×50需求量3020703010501I2I1IV2IV20求解步骤：利用最小元素法求解运输问题的初始解*解的退化情况1：在确定供需关系时，若在（i,j）格内填入数字后出现处的余量等于处的需量，此时在产销平衡表上填上一个数后，单位运价表上要同时划去一行和一列，并在划去的行或列的任一空格处填上一个0（始终保持表上有m+n-1个数字格）。iAjB0运价需求地供应地IIIII供应量A16×16×1322×17×17×50B1414×1319×151560C19×19×20×23M×M50DM×0M×0M×0×50需求量3020703010501I2I1IV2IV2030503020010050求解步骤：利用位势法求解表中所有非基变量的检验数)(vucjiijij2262221615141211，，，，MMMMMM2242029243332312422，，，，M2323252404645434135，，，，运价需求地供应地IIIII供应量A16×16×1322×17×17×50B1414×1319×151560C19×19×20×23M×M50DM×0M×0M×0×50需求量3020703010501I2I1IV2IV2030503020010050....................................................................................................................................................................求解步骤：利用闭回路法进行第一次方案调整30-20213131为换出变量，调整量为为换入变量，最小，故选取检验数XXM运价需求地供应地IIIII供应量A16×16×1322×17×17×50B14×14×1319×151560C1919×20×23M×M50DM×0M×0M×0×50需求量3020703010501I2I1IV2IV20305030200103020求解步骤：利用闭回路法进方案调整得到下表表2221723191615141211，，，，MMMMMMM2342025213332242221，，，，MM242426414645434135，，，，运价需求地供应地IIIII供应量A16161322171750B14141319151560C19192023MM50DM0M0M050需求量3020703010501I2I1IV2IV20305030200103020..................................................................................求解步骤：表2未得最优解，用闭回路法进行第二次调整20-23363333为换出变量，调整量为为换入变量，最小，故选取检验数XXM运价需求地供应地IIIII供应量A16161322171750B14141319151560C19192023MM50DM0M0M050需求量3020703010501I2I1IV2IV2030503020010500求解步骤：利用闭回路法进方案调整得到下表表3226041615141211，，，，22-432-23532242221M，，，，1134224645434136，，，，MMMM运价需求地供应地IIIII供应量A16161322171750B14141319151560C19192023MM50DM0M0M050需求量3020703010501I2I1IV2IV2030503020010500........................................................................求解步骤：表3未得最优解，用闭回路法进行第三次调整04-343232为换出变量，调整量为为换入变量，最小，故选取检验数XX运价需求地供应地IIIII供应量A16161322171750B14141319151560C19192023MM50DM0M0M050需求量3020703010501I2I1IV2IV2030503020010500求解步骤：利用闭回路法进方案调整得到下表表41210441615141211，，，，22-47223534242221M，，，，4-3-24234645434136，，，，MMMM运价需求地供应地IIIII供应量A16161322171750B14141319151560C19192023MM50DM0M0M050需求量3020703010501I2I1IV2IV2030503020010500...................................................................................................................................求解步骤：表4未得最优解，用闭回路法进行第四次调整204-424646为换出变量，调整量为为换入变量，最小，故选取检验数XX运价需求地供应地IIIII供应量A16161322171750B14141319151560C19192023MM50DM0M0M050需求量3020703010501I2I1IV2IV20305030200103020求解步骤：利用闭回路法进方案调整得到下表表5227441615141211，，，，22-14223534242221M，，，，MMMM4542413635332222，，，，经检验，所有非基变量的检验数均为非负，因而表5给出的基本可行解，即为问题的最优解。运价需求化肥厂IIIIIIIV产量A1613221750B1413191560C192023-50最低需求3070010110万t（210）最高需求507030不限（60）运价需求地供应地IIIII供应量A16161322171750B14141319151560C19192023MM50DM0M0M050需求量3020703010501I2I1IV2IV3002030103020502050204050最少总运费为：Z=19×50+13×50+13×20+15×40=2460万元。总结产销不平衡运输问题的求解方法:（1）产大于销的问题：增加虚销地，销量为产销之差，但实际没有运输，故单位运价为0，这样将该问题转化为产销平衡问题，然后用表上作业法求解。（2）产小于销的问题：增加虚产点，产量为销产之差，但实际没有运输，故单位运价为0，这样将该问题转化为产销平衡问题，然后用表上作业法求解。本次求解过程遇到的问题及解决思路:（1）同一个地区有两种需求情况：凡是需求分两种情况的地区,可以看成两个销地：一个销地为了保证最低需求，对应的虚供应点的单位运价取任意大整数M(M不会进入最优解）。若已知某需求地对某供应地没有需求，则其相对应的单位运价取任意大整数M(M不会进入最优解）。（2）表上作业法计算中的退化问题：在用最小元素法求解初始可行解时，在（i,j）格内填入数字后出现处的余量等于处的需量，此时在产销平衡表上填上一个数后，单位运价表上要同时划去一行和一列，并在划去的行或列的任一空格处填上一个0（始终保持表上有m+n-1个数字格）。iAjBjBiA谢谢大家！