2021年度运筹学运输问题讲义.ppt

*
本章内容
运输问题及其数学模型
用表上作业法求解运输问题
运输问题的进一步讨论
应用问题举例
运筹学运输问题
*
问题的提出：
一般的运输问题就是要解决把某种产品从若干个产地调运到若干个销地，在每个产地的供应量与每个销地的需求量已知，并知道各地之间的运输单价的前提下，如何确定一个使得总的运输费用最小的方案。
§1运输问题及其数学模型
*
运筹学运输问题
*
§1运输问题及其数学模型
——单一品种物资的运输调度问题
由产地Ai运往销地Bj的物品数量
Ai到Bj的单位运价
*
运筹学运输问题
*
§1运输问题及其数学模型
网络表示：
5,000
2,500
6,000
B2(b2)
B1(b1)
B3(b3)
Bn(bn)
销地
…
产地
A2(a2)
Am(am)
A1(a1)
…
x22
x23
x21
x11
x12
x13
x1n
x2n
xm3
xm1
xm2
xmn
c11
c12
c13
c1n
c21
c22
c23
c2n
cm1
cm2
cm3
cmn
*
运筹学运输问题
*
如果运输问题的总产量等于其总销
量，即有 则称该运输问题
为产销平衡运输问题；反之，称产销不平衡运输问题。
产销平衡运输问题的数学模型可表示如下：
§1运输问题及其数学模型
*
运筹学运输问题
*
二、运输问题数学模型的特点：
运输问题一定有最优解；基变量的个数=m+n-1
运输问题约束条件的系数矩阵：
x1m
x2m
xm1
xmm
x11
x12
…
x21
x22
…
xm2
…
…
m行
n行
§1运输问题及其数学模型
*
运筹学运输问题
*
运输问题具有下述特点：
(1) 约束条件系数矩阵的元素等于0或1；
(2) 约束条件系数矩阵的每一列有两个非零元素，这对应于每一个变量在前m个约束方程中出现一次，在后n个约束方程中也出现一次。
§1运输问题及其数学模型
*
运筹学运输问题
*
对产销平衡运输问题，除上述两个特点外，还有以下特点：
(1) 所有结构约束条件都是等式约束；
(2) 各产地产量之和等于各销地销量之和。
§1运输问题及其数学模型
*
运筹学运输问题
*
例1 某部门有3个生产同类产品的工厂(产地)，生产的产品由4个销售点(销地)出售，各工厂的生产量、各销售点的销售量(假定单位均为t)以及各工厂到各销售点的单位运价(元／t)示于表3-2中，要求研究产品如何调运才能使总运费最小?
表3-2
销地
产地
B1
B2
B3
B4
产量
A1
16
A2
10
A3
22
销量
8
14
12
14
48
4
2
8
12
5
4
10
11
3
9
6
11
§1运输问题及其数学模型
*
运筹学运输问题
*
该问题的数学模型：
§1运输问题及其数学模型
*
运筹学运输问题
*