哈尔滨工程大学：《运筹学基础》课程教学资源（PPT课件讲稿）第三章 运输问题

-第3章运输问题 第三章运输问题 Transportation problem 2006

2006/3 --第3章 运输问题-- --2-- 第三章 运输问题 Transportation problem

一-第3章运输问题 3.1运输问题的典例和数学模型 典例 某食品公司经营糖果业务,公司下设三个工厂A1、A2、 A3,四个销售门市部B1、B2、B3、B4。已知每天各自的生 量、销售量及调运时的单位运输费用情况。问:如何调运可 使总费用最小? 生产量:A17吨,A2—4吨,A3—9吨 销售量:B1—3吨,B2 6吨,B3 5吨,B4 6吨 销地 产地办 B1 B3 Al A2 317 A3 4 10 2006/3

2006/3 --第3章 运输问题-- --3-- 3.1 运输问题的典例和数学模型 一、典例： 某食品公司经营糖果业务，公司下设三个工厂A1、A2、 A3，四个销售门市部B1、B2、B3、B4。已知每天各自的生产 量、销售量及调运时的单位运输费用情况。问：如何调运可 使总费用最小？ 生产量：A1——7吨， A2 —— 4吨， A3 —— 9吨 销售量：B1 —— 3吨，B2 —— 6吨，B3 —— 5吨，B4 —— 6吨 产地 销地 B1 B2 B3 B4 A1 A2 A3 3 11 3 10 1 9 2 8 7 4 10 5

-第3章运输问题 调运示意图 X 3吨 X 6吨 4 销 地 B3)5吨 地 9吨 6吨 X 2006/3

2006/3 --第3章 运输问题-- --4-- 调运示意图 A1 A2 A3 B1 B2 B3 B4 7吨 4吨 9吨 3吨 6吨 5吨 6吨 x11 x34 产 地 销 地

-第3章运输问题 建立模型 设x1;—第i产地到第j销地之间的调运量,则有 Min J =1j=1 +x1o+X13 x14=7 1 + 11X21 tXo 31 14 X1222X 6 量限制 x21+x22+x23+x244 销量限制 X13+x23+x35 X31+x32+x33+x34 +x,A+x24=6 24 x;≥0,(i=1,2, 2006/3

2006/3 --第3章 运输问题-- --5-- 二、建立模型 设 xij——第i产地到第j销地之间的调运量，则有 Min z =   cij·xij 3 4 i=1 j=1 x11+x12+x13+x14=7 x11+x21+x31=3 xij0,(i=1,2,┄,3；j=1,2,┄,4) 产 量 限 制 销 量 限 制 x21+x22+x23+x24=4 x31+x32+x33+x34=9 x12+x22+x32=6 x13+x23+x33=5 x14+x24+x34=6

一-第3章运输问题 般模型表示: 设有个m产地、n个销地,其中第i个产地的产量为a,第j 销地的销量为b,且Σa∑b。若第i个产地到第j个销地每调运单 位物资的运费为c,则使总费用最少的调运模型为: Min z= i=1j=1 ∑x1=a ∑x=b, (1=1,2,…,m;j=1,2,,n) 2006 6

2006/3 --第3章 运输问题-- --6-- 一般模型表示： 设有个m产地、n个销地，其中第i个产地的产量为ai，第j个 销地的销量为bj，且 ai =bj。若第i个产地到第j个销地每调运单 位物资的运费为cij，则使总费用最少的调运模型为： Min z =   cij·xij n i=1 j=1 m (i 1,2,...,m) 1  = = = ai n j ij x 0 (i 1,2,..., m; j 1,2 ,..., n) (j 1,2 ,..., n) 1  = =  = = = xi j j m i i j b x

-第3章运输问题 、模型的特点 1.变量数 m×n 2.约束方程数:m+n个 最大独立方程数:m+n-1 3.系数列向量结构: 第i个分量 第m+j个分量 2006/3

2006/3 --第3章 运输问题-- --7-- 三、模型的特点 1.变量数：mn个 2.约束方程数：m+n个 最大独立方程数：m+n-1 3.系数列向量结构： Pij = ···· 0 ··· 1 ··· 1 0 ——第i个分量 ——第m+j个分量

-第3章运输问题 X 11X12 XO1 X 00 0 0 1=m 00 00 10 0:10 0 J-n 0 2006 00

2006/3 --第3章 运输问题-- --8-- x11 x12 ······x1n x21 x22 ······x2n ,············, xm1 xm2 ······xmn 1 1 ······ 1 0 0 ······0 ············ 0 0 ······ 0 0 0 ······ 0 1 1 ······1 ············ 0 0 ······ 0 0 0 ······ 0 0 0 ······0 ············ 1 1 ······ 1 1 0 ······ 0 1 0 ······0 ············ 1 0 ······ 0 0 1 ······ 0 0 1 ······0 ············ 0 1 ······ 0 0 0 ······ 1 0 0 ······1 ············ 0 0 ······ 1 i=1 i=2 i=m j=1 j=2 j=n ······ ······ ······ ······ ······ ······ ······ ······ ······ ······ ······ ······ ······ ······ ·· ···· ······ ······ ······

一-第3章运输问题 3.2运输问题的表上作业算法和程序求解 表上作业法步骤:初始方案→丶最优性检验→>改进方案 、初始方案的确定 1.最小元素法 2.yoge法 、最优性检验 1.闭回路法 2.位势法 三、方案改进方法 在闭回路内改进。 2006/3 9

2006/3 --第3章 运输问题-- --9-- 3.2 运输问题的表上作业算法和程序求解 表上作业法步骤: 初始方案→最优性检验→改进方案 一、初始方案的确定 1.最小元素法 2.Vogel法 二、最优性检验 1.闭回路法 2.位势法 三、方案改进方法 在闭回路内改进

一-第3章运输问题 产销平衡表 单位运价表 地B1B2B3B4产量产地BB2B3B4 地 A1(1)(2)437 A23(4)1(-1)4 A2 A3(10)6(12)39 A3 销量3656 △z=C1c13+C23C21=1=o1 产州的地B1B2B3B4产量 △Z=C12C1424C22=2=612 A1(0)(2)527 A23 4 A3(9) 266 (12)39 销量 2006/3

2006/3 --第3章 运输问题-- --10-- A1 A2 A3 B1 B2 B3 B4 A1 A2 A3 B1 B2 B3 B4 A1 A2 A3 B1 B2 B3 B4 产量 销量 3 11 3 10 1 9 2 8 7 4 10 5 6 3 4 3 1 3 3 6 5 6 7 4 9 3 6 5 6 7 4 9 产量 销量 3 6 3 5 2 1 (1) (2) (1) (-1) (10) (12) △z=c11-c13+c23-c21=1=11 △z=c12-c14+c24-c22=2=12 (0) (2) (2) (9) (1) (12) 产销平衡表 单位运价表

-第3章运输问题 Voge法 产销平衡表 产地的地B1B2B3B4产量产地地B1B2B3B行两最小元素之差 Al 527 0007 A2 4 A3 6 39 A3 12 销量3656 两 最小 元素 222 3322 之差 2006

2006/3 --第3章 运输问题-- --11-- A1 A2 A3 B1 B2 B3 B4 7 4 9 产量 销量 3 6 5 6 6 3 5 2 3 1 A1 A2 A3 B1 B2 B3 B4 行两最小元素之差 列两 最小 元素 之差 3 11 3 10 1 9 2 8 7 4 10 5 0 1 1 2 5 1 3 0 1 2 2 - 1 3 0 1 - 2 - 1 2 7 6 - - - 1 2 Vogel法: 产销平衡表