运筹学基础-运输问题(2。).ppt

上节小结：表上作业法求运输问题 最小元素法-最小运费 “就近运给” （二）修正分配法(位势法)判定是否最优及改进 非基变量（无数字格）的检验数用来判别是否最优的： 第一步：计算位势量的技巧 第二步：计算非基变量检验数 调整运输方案（得第二方案） 再次用修正分配法判定是否最优并确定调整格 调整运输方案（得第三方案） 再次用修正分配法判定是否最优并确定调整格 调整运输方案（得第四方案） 再次用修正分配法判定是否最优并确定调整格 ?修正分配法与闭合回路的关系 闭合回路是修正分配法的基础 五、关于退化问题 1、初始解退化 例：调整运输方案（最小元素法初始方案） 调整运量 判定是否最优 调整运量 判定是否最优 第三节 产销不平衡问题 产销平衡的运输问题采取表上作业法求解。 一、 产大于销（需要量小于供应量） 二、 产小于销 另例：产大于销（需要量小于供应量） 另例： 产小于销 第四节 运输问题的应用 ［解］ 　 ［解］ 　 ［解］判定是否最优 　 二、 资源转运问题 　 最小转运能力 t=max{?ai， ?bj}=10 　 用表上作业法求得最优方案 　闭回路调整 非基变量x21的检验数?21= -70，即让非基变量x21进基。 30 0 0 0 虚设Z厂 vj 102 130 240 70 B段 61 160 110 140 C段 77 82 56 产量 80 Y厂 120 X厂 82 销量 40 W厂 ui A段 销地 产地 26 61 51 21 30 56 26 21 5 21 51 72 调整后的方案：x11=56,x21=21,x32=72,x31=5,x23=61，Z=21230 － + + － 　最优性检验－－修正指数法 非基变量x12的检验数?12= -20，即让非基变量x12进基。 30 0 0 0 虚设Z厂 vj 102 130 240 70 B段 61 160 110 140 C段 77 82 56 产量 80 Y厂 120 X厂 82 销量 40 W厂 ui A段 销地 产地 61 72 30 21 56 5 110 -20 70 90 50 60 0 40 90 -90 40 80 30 　闭回路调整 非基变量x12的检验数?12= -20，即让非基变量x12进基。 30 0 0 0 虚设Z厂 vj 102 130 240 70 B段 61 160 110 140 C段 77 82 56 产量 80 Y厂 120 X厂 82 销量 40 W厂 ui A段 销地 产地 61 72 30 21 56 5 72 16 5 56 56 调整后的方案：x12=56,x21=21,x31=61,x32=16,x23=61，Z=20110 61 + － － + 　最优性检验－－修正指数法 所有非基变量xij的检验数?ij= cij –ui– vj≥0，即得最优解。 30 0 0 0 虚设Z厂 vj 102 130 240 70 B段 61 160 110 140 C段 77 82 56 产量 80 Y厂 120 X厂 82 销量 40 W厂 ui A段 销地 产地 61 30 61 16 21 56 20 130 70 90 50 60 0 70 20 100 60 -70 10 　已经是最优方案 增加一个销地 12 2 1 9 B2 16 8 7 2 B3 17 6 A3 18 3 A2 18 销量 15 5 A1 产量 B1 销地 产地 50 46 12 2 1 9 B2 16 8 7 2 B3 17 6 A3 18 3 A2 18 销量 15 5 A1 产量 B1 销地 产地 50-46 4 0 0 0 B4 50 50 初始基可行解 4 0 0 0 B4 12 2 1 9 B2 16 8 7 2 B3 17 18 15 产量 6 A3 3 A2 18 销量 5 A1 B1 销地 产地 12 15 6 12 1 4 初始基可行解：x13=15,x21=6,x22=12,x31=12,x33=1,x34=4，Z=140 最优性检验 非基变量x32的检验数?32= -2，即让非基变量x32进基。 vj 4 0 4 0 0 B4 12 2 1 12 9 B2 16 8 1 7 2 15 B3 17 18 15 产量 6 12 A3 3 6 A2 18 销量 5 A1 ui B1 销地 产地 0 2 -6 0 6 3 -2 5 11 6 2 3 -2 闭回路调整 x32 进基、最小调整量为12， x31 离基 4 16 12 18 销量 17 0 4 8 1 2 x32 6 12 A3 18 0 7 1 12 3 6 A2 15 0 2 15 9 5 A1 产量