第三部分运输问题.ppt

§3.1 运输问题与有关概念 §3.2 运输问题的求解—表上作业法 §3.1 运输问题模型及有关概念 问题的提出 一般的运输问题就是要解决把某种产 品从若干个产地调运到若干个销地，在每 个产地的供应量与每个销地的需求量已知， 并知道各地之间的运输单价的前提下，如 何确定一个使得总的运输费用最小的方案. 上述计算过程可用流程图描述如下（图2-2） 取未划去的单元格xij ,令 xij = min { ai , bj } ai’ = ai - xij bj’ = bj - xij ai’ = 0? 划去第i行 划去第j列 是 否 bj’ = 0 否 所有行列是 否均被划去 是 找到初始基 本可行解 图3-2 求运输问题的初始基本可行解过程 注：应用西北角法和最小元素法，每次填完数，都 只划去一行或一列。当填上一个数后行、列同时饱 和时，也应任意划去一行（列）在保留的列（行） 任意没被划去的格内标一个 0 . 例3.5 某公司下属有生产一种化工产品的三个产地 A1、A2、A3 ,有四个销售点B1、B2、B3、B4 销售 这种化工产品.各产地的产量、各销地的销量和各 产地运往各销地每吨产品的运费(百元)如下表所示. 195 65 55 40 35 需求 5 7 3 6 80 A3 8 4 9 2 40 A2 9 5 8 3 75 A1 B4 B3 B2 B1 产量 B4 B3 B2 B1 销 产 产销平衡表 运价表 问应如何调运，可使得总运输费最小? 解：用西北角法求初始基本可行解 195 65 55 40 35 需求 5 7 3 6 80 A3 8 4 9 2 40 A2 9 5 8 3 75 A1 B4 B3 B2 B1 产量 B4 B3 B2 B1 销 产 产销平衡表 运价表 35 40 0 40 15 65 z = 35×3 + 40×8 + 40×4 + 15×7 + 65×5 = 1015 195 65 55 40 35 需求 5 7 3 6 80 A3 8 4 9 2 40 A2 9 5 8 3 75 A1 B4 B3 B2 B1 产量 B4 B3 B2 B1 销 产 产销平衡表 运价表 2 35 3 40 4 5 5 50 5 40 9 25 z = 50×5+25×9+35×2+5×4+ 40×3+40×5= 885 产销平衡表 运价表 195 65 55 40 35 需求 5 7 3 6 80 A3 8 4 9 2 40 A2 9 5 8 3 75 A1 B4 B3 B2 B1 产量 B4 B3 B2 B1 销 产 1 5 1 3 3 40 5 40 3 35 2 2 4 2 2 4 2 1 4 40 15 25 z = 35×3+15×5+ 25×9+ 40×4+ 40×3 +40×5= 885 1 1 1 练习：求解以下列数据为单位运费的运输问题 (1) 100 35 30 20 15 销量 50 8 4 3 9 3 25 6 7 2 8 2 25 7 6 5 10 1 产量 丁 丙 乙 甲 销地 产地 30 8 6 3 4 5 4 30 7 5 3 戊 100 20 25 15 10 销量 20 8 9 1 2 3 20 7 1 4 3 2 30 5 4 5 2 1 产量 丁 丙 乙 甲 销地 产地 (2) 100 35 30 20 15 销量 50 3 25 2 25 1 产量 丁 丙 乙 甲 销地 产地 8 4 3 9 6 7 2 8 7 6 5 10 丁 丙 乙 甲 100 35 30 20 15 销量 50 3 25 2 25 1 产量 丁 丙 乙 甲 销地 产地 8 4 3 9 6 7 2 8 7 6 5 10 丁 丙 乙 甲 100 35 30 20 15 销量 50 3 25 2 25 1 产量 丁 丙 乙 甲 销地 产地 8 4 3 9 6 7 2 8 7 6 5 10 丁 丙 乙 甲 30 4 30 戊 100 20 25 15 10 销量 20 3 20 2 30 1 产量 丁 丙 乙 甲 销地 产地 8 6 3 4 5 7 8 9 1 2 5 7 1 4 3 3 5 4 5 2 戊 丁 丙 乙 甲 30 4 30 戊 100 20 25 15 10 销量 20 3 20 2 30 1 产量 丁 丙 乙 甲 销地 产地 8 6 3 4 5 7 8 9 1 2 5 7 1 4 3 3 5 4 5 2