第三章 运输问题_1

1、运运学学筹筹第三章第三章 运输问题运输问题3.1 3.1 运输问题及其数学模型运输问题及其数学模型3.2 3.2 用表上作业法求解运输问题用表上作业法求解运输问题3.3 3.3 运输问题的进一步讨论运输问题的进一步讨论3.4 3.4 应用问题举例应用问题举例运运学学筹筹3 运输问题运输问题3.1 3.1 运输问题及其数学模型运输问题及其数学模型 日常生活中人们常需将某些物品（包括自身）由一个空间日常生活中人们常需将某些物品（包括自身）由一个空间位置移动到另一个空间位置位置移动到另一个空间位置运输运输 单一品种物资运输调度典型应用单一品种物资运输调度典型应用 产地产地A1 （产量（产量a1） 销

2、地销地B1 （销量（销量b1） 产地产地A2 （产量（产量a2） 销地销地B2 （销量（销量b2 ） 产地产地Am （产量（产量am） 销地销地Bn （销量（销量bn ） 运价运价cij 怎样调运这些物品使总运费最小？怎样调运这些物品使总运费最小？运运学学筹筹 决策变量决策变量 Xij 表示由产地表示由产地Ai 到销地到销地Bj的物品数量的物品数量 Cij为为Ai 到到Bj的单位运价的单位运价12c11cnc121c22cnc21mc2mcmncnmmnmmmnnnbbbaxxxAaxxxAaxxxABBB21212222212111211121销地产地销量产量运价表运价表运运学学筹筹 产销平

3、衡问题产销平衡问题总产量总产量=总销量总销量 即即 产销不平衡问题产销不平衡问题总产量总产量=总销量总销量nijmiiba113.1 3.1 运输问题及其数学模型运输问题及其数学模型运运学学筹筹3.1 3.1 运输问题及其数学模型运输问题及其数学模型 典型案例典型案例 某企业有三个工厂（某企业有三个工厂（B1,B2,B3）和三座仓库（）和三座仓库（A1,A2,A3）根据生产需要要将仓库的原材料运输到工厂。由于工厂和根据生产需要要将仓库的原材料运输到工厂。由于工厂和仓库位置不同，单位运价仓库位置不同，单位运价cij也不同，具体数据如下表。请也不同，具体数据如下表。请您为该企业安排一个使总运费最小

4、的运输方案。您为该企业安排一个使总运费最小的运输方案。运价运价B1B2B3产量产量A148856A216241682A38162477销量销量7210241215运运学学筹筹一一 数学模型法求解数学模型法求解)3 , 2 , 1; 3 , 2 , 1(0411027277825624168162416884min3323133222123121113332312322211312113332312322211312113131jixxxxxxxxxxxxxxxxxxxxxxxxxxxxxczjiijijij运运学学筹筹 njmixnjbxmiaxxczijjmiijinjijminjijij,

5、2,1,2,1,0,2,1,2,1,min11113.1 3.1 运输问题及其数学模型运输问题及其数学模型由某一产地运往各个销由某一产地运往各个销地的物品数量之和等地的物品数量之和等于该产地的产量于该产地的产量由各产地运往某一销地由各产地运往某一销地的物品数量之和等于的物品数量之和等于该销地的销量该销地的销量单纯形法求解单纯形法求解？引入人工变量引入人工变量运运学学筹筹111111111111111111mnmmnnxxxxxxxxx212222111211运输问题数学模型的特点运输问题数学模型的特点运运学学筹筹运输问题数学模型的特点运输问题数学模型的特点 运输问题有有限最优解运输问题有有限最

6、优解 运输问题约束条件的系数矩阵运输问题约束条件的系数矩阵 约束条件系数矩阵每一列只有两个1，其余为0； 对产销平衡问题对产销平衡问题 约束条件均为等式，且产量之和=销量之和；运运学学筹筹求解思路求解思路一一 数学模型法数学模型法二二 表上作业法（表上作业法（运输单纯形法运输单纯形法）1 列出产销平衡表列出产销平衡表2 确定初始调运方案确定初始调运方案 （1）最小元素法）最小元素法 （2）西北角法）西北角法 （3）沃格尔（）沃格尔（Vogel）法）法3 位势法判定是否最优解位势法判定是否最优解4 解的改进解的改进运运学学筹筹1 列出产销平衡表列出产销平衡表 产销平衡及运价表产销平衡及运价表运价

7、运价B1B2B3产量产量A14x118x128x1356A216x2124x2216x2382A38x3116x3224x3377销量销量7210241215运运学学筹筹2 确定初始调运方案确定初始调运方案（1）最小元素法）最小元素法 减少运费减少运费单位运价最小的供销业务单位运价最小的供销业务运价运价B1B2B3产量产量A14x118x128x1356A216x2124x2216x2382A38x3116x3224x3377销量销量721024121556产产地地销地销地1616041004161416141000运运学学筹筹这时得到该运输问题的一个初始解：这时得到该运输问题的一个初始解：x

8、11=56,x22=41,x23=41, x31=16,x32=61,其余为其余为0总运费（目标函数值）总运费（目标函数值）=2968元元运价运价B1B2B3产量产量A14x118x128x1356A216x2124x2216x2382A38x3116x3224x3377销量销量7210241215561616041004161416141000运运学学筹筹2 确定初始调运方案确定初始调运方案（2）西北角法）西北角法运价运价B1B2B3产量产量A14x118x128x1356A216x2124x2216x2382A38x3116x3224x3377销量销量7210241215561616006

9、6663603641041运运学学筹筹至此得到该运输问题的初始基可行解：至此得到该运输问题的初始基可行解：x11=56,x21=16,x22=66, x32=36,x33=41,其余为其余为0总运费（目标函数值）总运费（目标函数值）=3624元元运价运价B1B2B3产量产量A14x118x128x1356A216x2124x2216x2382A38x3116x3224x3377销量销量72102412155616160066663603641041运运学学筹筹2 确定初始调运方案确定初始调运方案（3）沃格尔（）沃格尔（Vogel）法）法 按最小单位运价优先安排物品调运按最小单位运价优先安排物品

10、调运不得不采用运费不得不采用运费很高的其它供销点对很高的其它供销点对整个运输费增加整个运输费增加 罚数罚数=次小单位运价次小单位运价-最小单位运价最小单位运价 罚数值较小罚数值较小不能按最小运价安排运输造成的损失不大不能按最小运价安排运输造成的损失不大 罚数值很大罚数值很大不按最小运价组织运输会造成很大损失不按最小运价组织运输会造成很大损失 运运学学筹筹8 总运费总运费=2744元元行罚数行罚数123运价运价B1B2B3产量产量A14x118x128x1356A216x2124x2216x2382A38x3116x3224x3377销量销量7210241215列列罚罚数数12356046408

11、48088887205888885041410414108088以行罚数最大者分以行罚数最大者分配运输方案结果配运输方案结果如何？如何？运运学学筹筹2 确定初始调运方案确定初始调运方案 比较上述三种方法给出的初始基可行解，以沃比较上述三种方法给出的初始基可行解，以沃格尔法给出的解的目标函数值最小，最小元素法次格尔法给出的解的目标函数值最小，最小元素法次之，西北角法解的目标函数值最大。之，西北角法解的目标函数值最大。 一般，沃格尔法给出的初始解质量最好，常用一般，沃格尔法给出的初始解质量最好，常用来作为运输问题最优解的近似解。来作为运输问题最优解的近似解。运运学学筹筹3 位势法判定是否最优解位势

12、法判定是否最优解 步骤步骤 （1）在（最小元素法）初始解表上增加一位势列）在（最小元素法）初始解表上增加一位势列ui和和位势行位势行vj运价运价B1B2B3产量产量uiA14x118x128x1356u1A216x2124x2216x2382u2A38x3116x3224x3377u3销量销量7210241215vjv1v2v35616416141运运学学筹筹3 位势法判定是否最优解位势法判定是否最优解（2）计算位势，即建立方程组：）计算位势，即建立方程组：运价运价B1B2B3产量产量uiA14x118x128x1356u1A216x2124x2216x2382u2A38x3116x3224x

13、3377u3销量销量7210241215vjv1v2v35616416141u1+ v1=4u2+ v2=24u2+ v3=16 u3+ v1 =8u3+ v2=16运运学学筹筹3 位势法判定是否最优解位势法判定是否最优解（2）计算位势，即建立方程组：）计算位势，即建立方程组： 为计算简便，常任意指定某一位势为计算简便，常任意指定某一位势 等于一个较小的整数或零。等于一个较小的整数或零。 这里我们任意指定这里我们任意指定u2=0，由此可算出：，由此可算出： v2=24, v3=16 , u3=-8,v1=16,u1=-12 将上述位势表格相应圆括号内将上述位势表格相应圆括号内u1+ v1=4u

14、2+ v2=24u2+ v3=16 u3+ v1 =8u3+ v2=16运运学学筹筹（3）计算空格检验数）计算空格检验数 因为因为 0 ，故这个解不是最优解，故这个解不是最优解运价运价B1B2B3产量产量uiA14x118x128x1356u1（-12）A216x2124x2216x2382u2 （0）A38x3116x3224x3377u3 （-8）销量销量7210241215vjv1 （16）v2 （24）v3 （16）56-4416041416116)(jiijijvuc412运运学学筹筹4 解的改进解的改进 为负，说明将这个非基变量变为基变量时运费会更为负，说明将这个非基变量变为基变量

15、时运费会更 小，因而这个解不是最优解。小，因而这个解不是最优解。 改进方法改进方法 在运输表中找出这个空格对应的闭合回路在运输表中找出这个空格对应的闭合回路Lij，在满足所，在满足所有约束条件的前提下，使有约束条件的前提下，使xij尽量增大并相应调整次闭合尽量增大并相应调整次闭合回路上其他顶点的运输量，以得到另一个更好的基可行回路上其他顶点的运输量，以得到另一个更好的基可行解。解。 步骤（步骤（1）以）以x12为换入变量，找出它在运输表中的闭合为换入变量，找出它在运输表中的闭合回路回路 12运运学学筹筹 （2）以空格（）以空格（A1,B2） 为第一个奇数顶点，沿为第一个奇数顶点，沿 闭合回路的

16、顺（或逆）闭合回路的顺（或逆） 时针方向前进，对闭合时针方向前进，对闭合 回路上的顶点依次编号回路上的顶点依次编号 （3）偶数顶点中，找出）偶数顶点中，找出 运输量运输量xij最小的顶点，最小的顶点， 以该格中变量为换出变以该格中变量为换出变量量（4）以）以min xij为调整量，将回路中奇数顶点运输量都增加该数值，偶数为调整量，将回路中奇数顶点运输量都增加该数值，偶数顶点运输量都减去该数值，从而得出一新运输方案。顶点运输量都减去该数值，从而得出一新运输方案。 该运输方案总运费比原运输方案减少该运输方案总运费比原运输方案减少ijmin xij（5）基变量个数仍维持）基变量个数仍维持5个，目标函

17、数值：个，目标函数值： 2968+(-4)56=2744运价运价B1B2B3产量产量A14x118856A21624x221682A38162477销量销量72102412155616414161567205运运学学筹筹练习练习 用位势法检验用西北角法所得初始解是否最优解？用位势法检验用西北角法所得初始解是否最优解？若不是，对该解进行改进。若不是，对该解进行改进。 总运费总运费=3624元元运价运价B1B2B3产量产量A14x118x128x1356A216x2124x2216x2382A38x3116x3224x3377销量销量72102412155616160066663603641041

18、运运学学筹筹 表上作业法是求解运输问题的一种简便方法。表上作业法是求解运输问题的一种简便方法。 单纯形法与表上作业法的关系：单纯形法与表上作业法的关系：（1）找出初始基可行解）找出初始基可行解 （2）求各非基变量的检验数）求各非基变量的检验数（3）判断是否最优解）判断是否最优解计算表中空格检验数表上给出m+n-1个数字格判断方法相同运运学学筹筹换基：换基：（4）确定换入变量和换出变量找出新的基可行解。（5）重复（2）、（3）直至求出最优解。表上调整（闭回路调整）（运输问题必有最优解）停止最优解？是否运运学学筹筹说明说明1 有多个检验数均非负，在继续进行迭代时，取它们中的任有多个检验数均非负，在继续进行迭代时，取它们中的任一变量均可使