运筹学胡运权第三版第三章运输问题

《运筹学胡运权第三版第三章运输问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章运输问题2本章内容运输问题及其数学模型用表上作业法求解运输问题运输问题的进一步讨论应用问题举例问题的提出：一般的运输问题就是要解决把某种产品从若干个产地调运到若干个销地，在每个产地的供应量与每个销地的需求量已知，并知道各地之间的运输单价的前提下，如何确定一个使得总的运输费用最小的方案。§1运输问题及其数学模型§1运输问题及其数学模型1.经典运输问题——单一品种物资的运输调度问题由产地Ai运往销地Bj的物品数量Ai到Bj的单位运价§1运输问题及其数学模型网络表示：5,0002,5006,000B2(b2)B1(b

2、1)B3(b3)Bn(bn)销地…产地A2(a2)Am(am)A1(a1)…x22x23x21x11x12x13x1nx2nxm3xm1xm2xmnc11c12c13c1nc21c22c23c2ncm1cm2cm3cmn如果运输问题的总产量等于其总销量，即有则称该运输问题为产销平衡运输问题；反之，称产销不平衡运输问题。产销平衡运输问题的数学模型可表示如下：§1运输问题及其数学模型二、运输问题数学模型的特点：运输问题一定有最优解；基变量的个数=m+n-1运输问题约束条件的系数矩阵：x1mx2mxm1xmmx11x12…x21x22…xm

3、2……m行n行§1运输问题及其数学模型运输问题具有下述特点：(1)约束条件系数矩阵的元素等于0或1；(2)约束条件系数矩阵的每一列有两个非零元素，这对应于每一个变量在前m个约束方程中出现一次，在后n个约束方程中也出现一次。§1运输问题及其数学模型对产销平衡运输问题，除上述两个特点外，还有以下特点：(1)所有结构约束条件都是等式约束；(2)各产地产量之和等于各销地销量之和。§1运输问题及其数学模型例1某部门有3个生产同类产品的工厂(产地)，生产的产品由4个销售点(销地)出售，各工厂的生产量、各销售点的

4、销售量(假定单位均为t)以及各工厂到各销售点的单位运价(元／t)示于表3-2中，要求研究产品如何调运才能使总运费最小?表3-2销地产地B1B2B3B4产量A116A210A322销量8141214484281254101139611§1运输问题及其数学模型该问题的数学模型：§1运输问题及其数学模型12本章内容运输问题及其数学模型用表上作业法求解运输问题运输问题的进一步讨论应用问题举例一、表上作业法的基本思想和步骤：1.基本思想：同单纯形法的基本思想基本可行解是否为最优解换基结束YN§2用表上作业法求解

5、运输问题二、表上作业法的步骤（1）寻找初始基可行解；最小元素法、西北角法、沃格尔法（2）求出非基变量检验数（空格检验数），判断是否为最优解；闭回路法、位势法（3）换基改进，找到新的基可行解闭回路调整法（4）重复（2）（3）§2用表上作业法求解运输问题1.最小元素法从运价最小的格开始，在格内的右下角标上允许取得的最大数。然后按运价从小到大顺序填数。若某行（列）的产量（销量）已满足，则把该行（列）的其他格划去。如此进行下去，直至得到一个基本可行解。寻找初始基可行解销地产地B1B2B3B4产量A116A210A322

6、销量8141214484285101112346911①8②2③10④14⑤8⑥⑥61.最小元素法总费用z==10×4+6×11+8×2+2×3+14×5+8×6=246寻找初始基可行解2.西北角法从西北角（左上角）格开始，在格内的右下角标上允许取得的最大数。然后按行（列）标下一格的数。若某行（列）的产量（销量）已满足，则把该行（列）的其他格划去。如此进行下去，直至得到一个基本可行解。寻找初始基可行解销地产地B1B2B3B4产量A116A210A322销量8141214484285101112346911①8④46③⑥14⑥8②⑤82.西

7、北角法总费用z==8×4+8×12+6×10+4×3+8×11+14×6=372寻找初始基可行解3.沃格尔法罚数=次小费用-最小费用找出最大的罚数行或列所对应的最小费用优先安排。重复计算步骤1和2寻找初始基可行解3.沃格尔法销地产地B1B2B3B4产量行罚数12345A116A210A322销量814121448列罚数123454101211346911285201513221011321148810217062201242总费用z==244寻找初始基可行解最优性检验就是检查所得到的方案是不是最优方案。检查的方法与单纯形方法中的原理相同，

8、即计算检验数。由于目标要求极小，因此，当所有的检验数都大于或等于零时该调运方案就是最优方案；否