熊伟编《运筹学》Ch5运输与指派问题.ppt

销大于产平衡问题的数学模型为 ： 具体计算时，在运价表的下方增加一行Am+1，运价为零。产量为am+1即可。 5.2 运输单纯形法 Transportation Simplex Method 180 160 45 35 60 20 bj 50 11 10 8 4 A4 30 2 4 6 3 A3 40 8 7 4 -- A2 60 3 2 9 5 A1 ai B4 B3 B2 B1 因为有： 【例】求下列表中极小化运输问题的最优解。 所以是一个产大于销的运输问题。 5.2 运输单纯形法 Transportation Simplex Method 表5-25 表5—14 4 7 1 4 vj 60 25 5 10 20 bj 2 20 8 13 10 6 A3 1 25 4 2 7 1 A2 3 15 12 9 8 5 A1 ui ai B4 B3 B2 B1 Bj Ai 【 】 5 × × 5.2 运输单纯形法 Transportation Simplex Method 表5-15 4 － 1 4 vj 60 25 5 10 20 bj × 2 20 8 13 10 6 A3 5 3 25 4 2 7 1 A2 × 3 15 12 9 8 5 A1 ui ai B4 B3 B2 B1 Bj Ai 20 × × × 0 【 】 × 5.2 运输单纯形法 Transportation Simplex Method 表5-16 4 － 2 － vj 60 25 5 10 20 bj × 2 20 8 13 10 6 A3 5 － 25 4 2 7 1 A2 × 4 15 12 9 8 5 A1 ui ai B4 B3 B2 B1 Bj Ai 20 × × × 0 【 】 10 × 20 5 基本可行解为 总运费Z=10×8+20×1+5×2+20×8=270。 5.2 运输单纯形法 Transportation Simplex Method 3. 左上角法。左上角法(亦称西北角法)是优先从运价表的左上角的变量赋值，当行或列分配完毕后，再在表中余下部分的左上角赋值，依次类推，直到右下角元素分配完毕．当出现同时分配完一行和一列时，仍然应在打“×”的位置上选一个变量作基变量，以保证最后的基变量数等于m+n－1 100 10 30 60 销 量 25 8 4 7 A3 45 5 3 4 A2 30 7 6 8 A1 产 量 B3 B2 B1 Bj Ai 【例5.6】用左上角法求例5.3中表5-6的初始基本可行解 表5-17 30 × × 30 × 15 × 15 10 求出一组基可行解后，判断是否为最优解，仍然是用检验数来判断，记xij的检验数为λij由第一章知，求最小值的运输问题的最优判别准则是： 所有非基变量的检验数都非负，则运输方案最优（即为最优解）。 求检验数的方法有两种，闭回路法和位势法。 1．闭回路法求检验数 求某一非基变量的检验数的方法是：在基本可行解矩阵中，以该非基变量为起点，以基变量为其它顶点，找一条闭回路，由起点开始，分别在顶点上交替标上代数符号+、-、+、-、…，以这些符号分别乘以相应的运价，其代数和就是这个非基变量的检验数。 5.2 运输单纯形法 Transportation Simplex Method 5.2.2求检验数 【解】用最小元素法得到下列一组基本可行解 【例5.7】求下列运输问题的一个初始基本可行解及其检验数。矩阵中的元素为运价Cij ，矩阵右边的元素为产量ai ，下方的元素为销量bj 。 5.2 运输单纯形法 Transportation Simplex Method 矩阵中打“×”的位置是非基变量，其余是基变量，这里只求非基变量的检验数。 求λ11，先找出x11的闭回路 ，对应的运价为 再用正负号分别交替乘以运价有 直接求代数和得 5.2 运输单纯形法 Transportation Simplex Method 30 40 60 10 bj × 10 × 10 20 2 9 10 2 A3 30 20 × × 50 1 5 6 7 A2 × 10 60 × 70 4 8 3 9 A1 ai B4 B3 B2 B1 Bj Ai 8 0 9 6 6 -3 5.2 运输单纯形法 Transportation Simplex Method 同理可求出其它非基变量的检验数： 这里λ340，说明这组基本可行解不是最优解。 只要求得的基变量是正确的且数目为m+n－1，则某个非基变量的闭回路存在