管理运筹学-04-运输模型.ppt

管理运筹学
运输问题
第三讲
11/11/2017
3
若一家公司拥有多个工厂,这些工厂位于不同的地点,并且生产同一种产品。这些产品要运输到不同的地点,以满足用户的需求。
供应节点:这些工厂,它们是运输的起点;
需求节点:用户所在点,它们是运输的终点或目的地。
同时假定产品不能在供应节点之间运输,也不能在需求节点之间运输。
公司面临的问题:应如何组织运输,才能在满足供应节点的供应量约束和需求节点的需求量约束的前提下,使得运输成本最低。
这类问题就是运输问题。
一、问题的模型描述
11/11/2017
4
二、运输问题数学模型
xij --供应节点i至需求节点j的运输量;
ai --供应节点i的可供应量,i=1,2, …,m;
bj --需求节点j的需求量,j=1,2,…,n;
cij --供应节点i至需求节点j的单位运输成本。
11/11/2017
5
平衡型运输问题:
二、运输问题数学模型
模型包含
变量:m×n个
约束方程:m+n个
秩:r(A)=m+n-1
11/11/2017
6
二、运输问题数学模型
m 行
n 行
稀疏矩阵
x11,x12,…,x1n,…x21,…x2n,…,xm1,…xmn
11/11/2017
7
平衡型运输问题:
三、运输问题的基本性质
1. 约束方程数为m+n个,但有一个冗余方程,所以独立方程数为m+n-1个,即秩r(A)=m+n-1。
2. 存在最优解
3. 当供应量和需求量均为整数时,存在整数最优解。
4. 基可行解中基变量个数为m+n-1个
5. 基可行解中基变量的重要特征: 不含闭回路。
6. 任何一个非基变量与基变量含且仅含一个闭回路。
11/11/2017
8
最小元素法
西北角法
Vogel法
四、初始基可行解的确定
11/11/2017
9
最小元素法
B1
B2
B3
B4
产量
A1
16
A2
10
A3
22
销量
8
14
12
14
48
4
12
4
11
2
10
3
6
8
5
9
11
11/11/2017
10
B1
B2
B3
B4
产量
A1
16
A2
10
A3
22
销量
8
14
12
14
48
4
12
4
11
2
10
3
6
8
5
9
11
8
2
2
10
10
14
8
8
6
6
X=(0,0,10,6,8,0,2,0,0,14,0,8)