运筹学 第四章 运输与指派问题 第一讲 运输模型与运输单纯形法.ppt

表上作业法 表上作业法的计算步骤： 2．位势法求检验数: 位势法求检验数是根据对偶理论推导出来的一种方法。 设平衡运输问题为 设前m个约束对应的对偶变量为ui(i=1,2,…,m)，后n个约束对应的对偶变量为vj(j=1,2,…,n), 则运输问题的对偶问题是 4.2 运输单纯形法 Transportation Simplex Method 加入松驰变量λij将约束化为等式: ui+vj+λij=cij 记原问题基变量XB的下标集为I，由第二章对偶性质知，原问题xij的检验数的相反数是对偶问题的松弛变量λij ，当（i，j）∈I 时λij=0，因而有 解上面第一个方程，将ui、vj 代入第二个方程求出λij 4.2 运输单纯形法 Transportation Simplex Method 【例8】用位势法求例7给出的初始基本可行解的检验数。 【解】第一步求位势u1、u2、u3及v1、v2、v3、v4。 10 60 40 30 令u1=0得到位势的解为 4.2 运输单纯形法 Transportation Simplex Method 再由公式 求出检验数，其中Cij是非基变量对应的运价。 计算结果与例7结果相同。 4.2 运输单纯形法 Transportation Simplex Method B1 B2 B3 B4 产量 A1 A2 A3 12 4 4 11 2 10 3 9 8 5 11 6 销量 8 14 10 2 6 8 16 10 22 8 14 12 14 ui vj 0 4 11 -5 -1 3 10 销地 产地 求位势： B1 B2 B3 B4 产量 A1 A2 A3 12 4 4 11 2 10 3 9 8 5 11 6 销量 8 14 10 2 6 8 16 10 22 8 14 12 14 销地 产地 B1 B2 B3 B4 产量 A1 A2 A3 12 4 4 11 2 10 3 9 8 5 11 6 销量 16 10 22 8 14 12 14 销地 产地 0 -5 -1 vj 4 11 3 10 ui 1 2 0 0 0 1 0 -1 10 0 12 0 求检验数： 4.2.3 调整运量 当某个检验数小于零时，基可行解不是最优解，总运费还可以下降，这时需调整运输量，改进原运输方案，使总运费减少，改进运输方案的步骤是： 第一步：确定进基变量: 第二步：确定出基变量: 在进基变量xik的闭回路中，标有负号的最小运量作为调整量θ，θ对应的基变量为出基变量，并打上“×”以示作为非基变量。 第三步：调整运量: 在进基变量的闭回路中标有正号的变量加上调整量θ，标有负号的变量减去调整量θ，其余变量不变，得到一组新的基可行解，然后求所有非基变量的检验数重新检验。 4.2 运输单纯形法 Transportation Simplex Method Bj Ai B1 B2 B3 B4 ai A1 5 8 9 2 70 × 40 × 30 A2 3 6 4 7 80 45 × 35 × A3 10 12 14 5 40 × 25 15 × bj 45 65 50 30 190 【例4.9】求下列运输问题的最优解 表4-19 4.2 运输单纯形法 Transportation Simplex Method 【解】 用最小元素法求得初始基本可行解如表4-19 用闭回路法求非基变量的检验数 得： Bj Ai B1 B2 B3 B4 ai A1 5 8 9 2 70 × 40 × 30 A2 3 6 4 7span 80 45 × 35 × A3 10 12 14 5 40 × 25 15 × bj 45 65 50 30 190 5.2 运输单纯形法 Transportation Simplex Method + _ + _ + _ 因为有4个检验数小于零，所以这组基本可行解不是最优解。对应的非基变量x11进基. 对应的非基变量x11进基. x11的闭回路是 x33最小，x33是出基量，调整量θ=15 Bj Ai B1 B2 B3 B4 ai A1 5 8 9 2 70 × 40 × 30 A2 3 6 4 7 80 45 × 35 × A3 10 12 14 5 40 × 25 15 × bj 45 65 50 30 190 4.2 运输单纯形法 Transportation Simplex Method + _ + _ + _ Bj Ai B1 B2 B3 B4 ai A1 5 8 9 2 70 15 25 × 30 A2 3 6