文档介绍：第四章运输问题
I、基本要求
教学目标
了解运输问题的基本原理,掌握运输问题表上作业法的计算方法。能够进行产销平衡与产销不平衡的运输问题的优化安排。
重点问题
运输问题表上作业法的计算方法。
II、基本内容
第一节运输问题的基本原理和表上作业法
一、运输问题的基本原理
二、运输问题表上作业法
第二节运输问题优化实例
一、产销平衡的运输问题
二、产销不平衡的运输问题
III、学时分配表
序号
教学内容
课时分配
1
运输问题的基本原理和表上作业法
2
2
运输问题优化实例
2
合计
4
IV、教学方法
本章主要采取讲授课外练习相结合的方法教学。
第一节运输问题的概念和模型
一、运输问题的概念
一般运输问题,就是为解决把某种产品从若干个产地调运到若干个销地,在每个产地的供应量与每个销地的需求量已知,并知道各地之间的运输单价的情况下,确定使总运输费用最小的方案的数学问题。
二、运输问题数学模型
某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3,各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示,问:应如何调运可使总运输费用最小?
商品产销调运表
B1
B2
B3
产量
A1
6
4
6
200
A2
6
5
5
300
销量
150
150
200
解:两个产地的总产量为:200+300=500;
三个销地的总销量为150+150+200=500;
总产量= 总销量,故称产销平衡问题。
设 xij 为从产地Ai运往销地Bj的运输量,得到下列运输量表:
商品运量表
B1
B2
B3
产量
A1
x11
x12
x13
200
A2
x21
x22
x23
300
销量
150
150
200
500
根据题意可写出如下数学模型:
Min f = 6x11+4x12+6x13+6x21+5x22+5x23
. x11+ x12 + x13 = 200 (满足产地产量约束条件)
x21 + x22+ x23 = 300 (满足产地产量约束条件)
x11 + x21 = 150 (满足销地销量约束条件)
x12 + x22 = 150 (满足销地销量约束条件)
x13 + x23 = 200 (满足销地销量约束条件)
xij≥0(i=1,2;j=1,2,3)。
若设 A1, A2,…,Am 表示某物资的m个产地;
B1,B2,…,Bn 表示某物资的n个销地;
si表示产地 Ai 的产量;
dj 表示销地 Bj 的销量;
cij 表示把物资从产地 Ai 运往销地 Bj 的单位运价则可得如下运价表(表4-3)。
运输价格表
销地
产地
B1 B2 … Bn
产量
A1
A2
┇
Am
c11 c12 … c1n
c21 c22 … c2n
┇┇┇
cm1 cm2 … cmn
s1
s2
┇
sm
销量
d1 d2 … dn
如果s1 + s2 + …+ sm = d1+ d2 + …+ dn
则称该运输问题为产销平衡问题,其一般线性规划模型如下:
设 xij 为从产地 Ai 运往销地 Bj 的运输量,根据这个运输问题的要求,可以建立一般运输变量表(表 )。
商品运输变量表
销地
产地
B1 B2 … Bn
产量
A1
A2
┇
Am
x11 x12 … x1n
x21 x22 … x2n
┇┇┇
xm1 xm2 … xmn
s1
s2
┇
sm
销量
d1 d2 … dn
于是得到下列一般运输问题的模型:
Min
第二节运输问题的表上作业法
一、确定基本初始可行解
例:某食品公司下属的A1、A2、A3 3个厂生产方便食品,要运送到B1、B2、B3、B4 4个销售点,数据如下:
某食品公司商品供销调运资料表
B1
B2
B3
B4
产量ai
A1
3
11
3
10
7
A2
1
9
2
8
4
A3
7
4
10
5
9
销量bj
3
6
5
6
20
求最优运输方案。
解:
确定初始可行解主要有西北解法、最小元素法和伏格尔(Vogl)近似法等方法。下面,我们根据教材的介绍,简述西北解法和最小元素法。
(一)西北角法
从西北角(左上角)格开始,在格内的右下角标上允许取得的最大数。然后按行(列)标下一格的数。若某行(列)的产量(销量)已满足,则把该行