运筹学章运输问题.ppt

调整方法： 闭回路上每个奇次拐点的调运量都减去调整量 (其中有一个且仅允许有一个调运量为0变为空格成为非基变量，其他变为0的仍然要填上0)，各偶次拐点的调运量均加上调整量，其中有一个由非基变量(空格)变为基变量。 对例1，取 表2-3 运输问题调运方案调整表 B1 B2 B3 B4 发量 B1 B2 B3 B4 A1 3 1 4 3 1 A2 2 4-3→ → ●+3↓ 6 2 1 3 A3 0+3↑ ← ←3-3 3 3 收量 2 4 3 4 13 §4.2 求解运输问题的表上作业法 使用位势法求检验数，过程如下： 有检验数l33 =-10, 继续调整, 取 表2-4 运输问题调运方案调整表 B1 B2 B3 B4 发量 B1 B2 B3 B4 A1 3-3 → 1+3↓ 4 4 A2 2 1+3↓ ← ↑ ←3-3 6 2 4 0 A3 3-3 → ●+3 ↑ 3 0 3 收量 2 4 3 4 13 §4.2 求解运输问题的表上作业法 注意：这里经调整以后，有3个基变量x13, x24, x31同时变为零！但只能有一个x13成为非基变量(空格)，另外两个x24, x31仍为基变量，其对应的调运量等于0。 继续求检验数： 此时所有检验数全部非负，因此对应的调运方案是最优的。 min Z=4×4+2×4+4×4+3×5=55。 §4.2 求解运输问题的表上作业法 例2 求表2-5对应的运输问题的最优解： 表2-5 运输问题的平衡表与运价表 B1 B2 B3 B4 发量 B1 B2 B3 B4 A1 7 3 11 3 10 A2 4 1 9 2 8 A3 9 7 4 10 5 收量 3 6 5 6 20 解：首先用最小元素法求初始调运方案，见表2-6。 表2-6 运输问题的初始调运方案 B1 B2 B3 B4 发量 B1 B2 B3 B4 A1 4 3 7 3 11 3 10 A2 3 1 4 1 9 2 8 A3 6 3 9 7 4 10 5 收量 3 6 5 6 20 总费用Z= 4×3+3×10+3×1+1×2+6×4+3×5=86 §4.2 求解运输问题的表上作业法 采用位势法求检验数： 有检验数为负,非最优方案,需要进行方案的调整,见表2-7。 表2-7 运输问题的调运方案调整表 B1 B2 B3 B4 发量 B1 B2 B3 B4 A1 4↓+1 ←3-1 7 5 2 A2 3 1→-1 ●↑+1 4 3 1 A3 6 3 9 6 3 收量 3 6 5 6 20 总费用Z=5×3+2×10+3×1+1×8+6×4+3×5=85 §4.2 求解运输问题的表上作业法 采用位势法求检验数： 所有检验数全部非负,此方案是最优的调运方案。 由于非基变量x11的检验数l11 =0, 该运输问题可能 不止一个最优方案。进行调整见表1-79，该表对应另一个最优方案。 最小费用Z=5×3+2×10+3×1+1×8+6×4+3×5=85。 §4.2 求解运输问题的表上作业法 表2-8 运输问题的调运方案调整表 B1 B2 B3 B4 发量 B1 B2 B3 B4 A1 ● →+2 → 5 → ↓2-2 7 2 5 A2 ↑3-2 ← ← ←1+2 4 1 3 A3 6 3 9 6 3 收量 3 6 5 6 20 最小费用Z=2×3+5×3+1×1+3×8+6×4+3×5=85 §4.2 求解运输问题的表上作业法 对例2用LINDO软件进行求解，程序如下： min 3x11+11x12+3x13+10x14+x21+9x22 +2x23+8x24+7x31+4x32+10x33+5x34 st x11+x12+x13+x14=7 x21+x22+x23+x24=4 x31+x32+x33+x34=9 x11+x21+x31=3 x12+x22+x32=6 x13+x23+x33=5 x14+x24+X34=6 end §4.2 求解运输问题的表上作业法 LP OPTIMUM FOUND AT STEP 6 OBJECTIVE FUNCTION VALUE 1) 85.00000 VARIABLE VALUE REDUCED COST x11 2.000000 0.000000 x12 0.000000 2.000000 x13 5.000000 0.000000 x14 0.000000 0.0