2014运筹学-03-3位势法-讲课版03PPT

调整已有调运方案: 解的改进
重新计算位势和检验数.
产地
B1 A1 A2 A3 位势 3 10 1 2 3 1 7 2 9 1 8 B2
销地
B3 11 3 B4 10
位势
1 0 -4
4+1 4
9 2
3-1 3
-1 19 8 5
1-1 1
4 12 10
-3
1
6
8
wk.baidu.com
-2
2
3
9
相当于单纯形法的转轴运算. 重新计算位势和检验数.
3 2 6 9 2 3 3 4 1 2 6 5 110
Recap: 表上作业法—最小元素法
第一步，做产销空格表，并将空格对应的产 销地运费填在空格的右上角;
第二步，在表中找出运价最小的一个
(1) 如果产大于销，则在该格中填上销量; (2) 如果销大于产，则在该格中填上产量;
产地
B1 A1 2 B2
销地
B3 9 6 1 × 8 × 3-3 3 × 8-6-2 8-6 8 2 4 3 3 2 × 4 × 5 6 4 4-3 4-3-1 10 × 2 B4 7
供 应
9 9-3-6 9-3 5 5-2 5-2-3 7 7-1 21
3
A2 A3 需求
1
6-6 6
初始调运的运费为
产地
A1 A2
销地
位势
B3 B4 3 10 2 2 8
0 3
3
B1 3 1
2 9 2 7
6
B2 11 5 9 4
2
A3 位势
9 -2
7
1 1 12 -2
1
10 3 5
0
-3
1 7 1 8 所有的检验数均已大于等于零 所以此表为最优调运方案，总运费为
s 1 3 6 4 5 3 2 10 1 8 3 5 85
Recap: 元素差额(Vogel)法
第一步，做产销空格表，并将空格对应的产销地运费 填在空格的右上角.
第二步，增加一行和一列作为差额行和差额列，填上 对应行和对应列的最小元素和次小元素的差额. 第三步，在差额行和差额列中选取差额最大的一行或 一列进行分配，并对该行(列)的最小元素填数，填数 规则同最小元素法. 第四步，重新计算差额并进行分配，直到每一个格上 都被填上数字或画×为止.
最优调运方案的判断—闭回路法
闭回路：由一个空格开始，沿水平方向或垂 直方向前进. 遇到一个有数字的格子时，则 可以按前进方向的垂直方向转向前进，经过 若干次后,必然回到原出发点. 转角：填有数字，并且前进方向改变的格子. 某一空格的检验数：从空格开始沿闭回路前 进，空格的单位运费取正，第一个转角运费 取负，第二个取正, …, 将这些运费加起来， 作为该空格的检验数. 最优解：所有空格的检验数非负
2
A2 8 A3 需 求 2 7 0 2
3 3 2
3 8
3
5 5 4 1 9
2
0
2 2
0
3
7 7 1 3
2
2 2 0 4 -2 6
4
4
3
vj
0
1
1
2
-2
产销不平衡问题: 销>产
假设一个“虚产地”，其产量就是不平衡问题 的差额部分, 虚产地到各个销售地的运费为0. 在制定初始运输方案时，单位运价应该从真实 产地的最小价格为准, 最后考虑虚产地! 例 某运输问题如下，求最佳调运方案
运筹学
第三章 运输问题
北京工业大学 城市交通学院 周雨阳
运输问题
第三章 运输问题 运输问题的数学模型 表上作业法求解运输问题 产销不平衡问题等进一步讨论
• 第一节 • 第二节 • 第三节
Recap: 运输问题的一般形式
某种物资有m个产地A1, A2, …, Am 供应量分别为a1, a2, …, am个单位 联合供应n个销地B1, B2, …, Bn， 需求量分别为b1, b2, …, bn个单位. 从产地A1向销地B1单位运价cij已知
A1
A2
1
2
3
1
2 9 1 8
11
4 9 1 4
3
3 2
10
1 0
-1 9
8 5
3 A3 位势
10
7 6
12 -2
10 3
-3
-4
1
8
2
9
与闭回路法求出的检验数是一致的
调整已有调运方案: 解的改进
3 调整已有的调运方案 实质上是从一个基本可行解找出另一个基本 可行解，使目标函数下降.
换入变量：选出一个检验数为负的空格(一般 选具有最负值检验数的空格(若两个空格的检 验数一样则任选一个)，然后做选出闭回路.
P94页几点说明
产销不平衡问题: 产>销
在运输问题的数学模型中
m n
a b
i 1 i j 1
j
即产销不平衡问题. 1. 产大于销的不平衡问题 具体的做法是在表上加入一列“库存” 库存量就是产量与销量的差额部分, 运费为0 用最小元素法制定初始方案从哪个运费开始?
产销不平衡问题: 产>销
例 求下表A2B2的一个闭回路和检验数
产地
B1 A1 A2 3 1 B2 11 4
销地
B3 3 3 2 8 5 3 B4 10
供应
7 4 9
1
9
3
A3 7 6 4
1
10
需求
3
6
5
6
20
检验数:
9 4 5 10 3 2 1
最优调运方案的判断—位势法(对偶变量法)
位势法（对偶变量法） 如果产销地的个数很多，闭回路法应用起来 非常麻烦，对于这种情况，采用位势法: 第一步，做产销空格表，并作初始调运方案， 表中的数字是相应的单位运价和运量. 第二步，增加一行vj和一列ui , 使得表中(非 空格)基变量的单位运价cij刚好是ui和vj的和. 第三步，计算空格处的检验数: σij=cij-(ui+vj) 最优解：所有空格的检验数非负
季 度
1 2 3
季
I 5 M II
度
III IV
产量 (万 )
6
5 M
7
6
8
7 7
13 15 15
M
M
6
M
4
需求 (万 )
M 14 20
6 8
13 56 52
10
添加库存
季 度 1 2
季度
I
5 M
II
6 5
III
7 6
IV
8 7
库存
0 0
产 量 13 15
3
4
M
M
M
M
6
M
7
6
0
0
15
13
需 求
10
子矩阵
子矩阵
转运问题
例 求下面的转运问题.
12 20 A 10 6 3 4 7 B 9
1
2 6
2 9 3
10
5
3
9
解： 这是一个产销平衡问题，所以转运量 U=27 建立产销空格表如下：
A A B 1 0
B 3
1 12
2 10
3
供 14 47 5 34 27
27
3 0
9
6 0
9
10
2 7
27
12 6 2
（1）左上角法（西北角法）
（2）最小元素法 （3）元素差额法
Recap: 表上作业法—西北角法
第一步，做产销空格表，将空格对应的产销 地运费填在空格的右上角. 第二步，从表中左上角(西北角)进行分配 (1) 如果产大于销，则在这个方格填上销量, 并在表中划去这一列 (2) 如果销大于产，则在这个方格填上产量, 并在表中划去这一行 第三步，在剩下的表中，反复进行第二步.
A1 A2 A3 收量
B1 3 1 7 7
B2 11 9 5 8
B3 6 9 8 6
B4 10 7 8 7
发量 7 8 9
解：虚产地产量为4.
A1 A2 A3
-1 4 1
B1
3 1
4 7 5
4
B2
11
B3
6
B4
发量 ui 10 7
6
9 5
0 1
9 7 8 9 4 28
4
6 3 4 4 4
-4 6
6 7
14
20
8
4
转运问题
运输路线包括发点到发点，收点到收点甚至 收点到发点的运输，此类为题称为转运问题.
如图所示 C A D B 发点，
假定是一个产销平衡问
题，即发点的发量 ai
m
等于收点的收量 b j
j 1
n
i 1
E 收点
那么每个点的转运量
U则不能超过 ai
i 1
m
转运矩阵
发点 1 … i … m 发 1 点 i … m 收 1 点 j … n U … U … U b1+U … bj+U … bn+U (3) 收点到发点的 (4) 收点到收点的 … (1) 发点到发点的 子矩阵 … 1 收点 … j … (2) 发点到收点的 子矩阵 供应量 n a1+U … ai+U … am+U U … U … U
例 求下表各空格处的检验数
产地
B1 A1 A2 3 1 B2 11 4 9 2
销地
B3 3 3 8 5 3 B4 10
供应
7 4 9
3
A3 7 6 4
1
10
需求
3
6
5
6
20
解：任意指定非空格(基变量)的某一位势等于一个 较小的整数。空格(非基变量)检验数: σij=cij-(ui+vj)
产地 B1 B2 销地 B3 B4 位势
-3
1
0 4 0
0
收量 vj
7 0
8 3
6 3
7 6
28
没有线路的情况
某产地到销地没有运输路线，可认为该产地 到这个销地的运费非常大，一般用M表示. 例 某公司生产一种产品，该产品的各季度预 测销售量及各季度的生产能力如下表所示, 已 知一二季度的单位成本价格为5元，三四季度 的为6元，如果生产当季没有销售出去时,保管 在仓库里每单位产品还要1元的库存费用,该公 司希望能制定一个成本最低的生产计划满足 市场的需要，各季度应生产多少?
季度 1 2 3 4
预测需求量(个) 最大生产能力(个) 100000 130000 140000 150000 200000 150000 80000 130000
解： 首先要确定收点和发点 存在类似按季度生产货物的分配与销售问题 可以认为发点是生产的四季，收点是销售的 四季这样就可以的到一个产销表：
第三步，在剩下的表中，反复进行第二步.
产地
B1 A1 2 B2
销地
B3 9 10 B4 7
供应
9 5 5-3 7 7-4 21
×
A2 1
5
3
×
4
4
2
3
A3 8
×
4
×
2
2
5
×
需求 3
3
8
4
4
×
6
初始总运费为
5 9 4 7 3 1 2 2 3 4 4 2 100
如何运物资才能使总运输费用最少?
Recap: 运输问题的一般形式
数学模型: 包含有m×n个变量，m+n个约束方程
min s cij xij
i 1 j 1 m n
约束方程的系数矩阵每一列元素 只有两个元素为1，其余为0
1 1 A 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
在制定初始运输方案时，最小的单位运价应 该从实际最小价格为准, 最后考虑库存这列!
A1 A2 A3 收量
B1 2 10 7 2 B2 11 3 8 3 B3 3 5 1 4 B4 4 9 2 6 发量 7 5 7
解：总发量为19，而总收量为15，所以为产 销不平衡问题.
产销不平衡问题: 产>销
B1 A1 2 8 B2 11 0 3 10 B3 3 B4 4 库存 0 供应 ui 7 5 7 19
B1
A1 A2 2
B2
9
B3
10
B4
差额
7 2 9 5 7
3
1
5
3
×
4
1 5
2 5 1
×
A3 8
×
4
×
2
5
×
3
差 额
3
8
4
4
×
6 21
2 1
1
1 5
2 8
3 2
初始调运方案为
2 3 5 9 7 1 2 5 4 3 2 4 88
最优调运方案的判断
判断一个调运方案是否是最优方案，实质是 判别一个基本可行解是否为最优解. 单纯形法中，最优解是根据对应的非基变量的 检验数来判断的. 运输问题也采用类似的方法. 单纯形法最优解中非基变量一般取0 调运量为零(即×空格)位置对应于非基变量 所以只要判别出每个空格的检验数就可以了
5 7
2 1
8 8
1
2
2 虚产 6 地 -6 收量 vj 7
8
0 3 -3 8 0
1
0 0
4
7
-6
0
3
2
6
B1
A1 1 3
5
B2
11 6 5 4 3 5 3 -3
B3
6
1
B4
A2
A3 6 5
1
7 0
6 5
4
9 9
2 8
发量 ui 10 7 3 7
8
9
5
8
9 4
1 2 -6
2 虚产 6 地 -6
8 3
3
27
10 14
27 27
运输问题
第三章 运输问题 运输问题的数学模型 表上作业法求解运输问题 产销不平衡问题等进一步讨论
• 第一节 • 第二节 • 第三节
表上作业法的几个问题
1 运输问题中的基变量的个数 当收点的个数为n，发点的个数为m时， 在表中填格子的个数为m+n-1个. 定理 运输问题系数矩阵的秩为m+n-1.
2. 多重最优解、退化
s.t .
xij ai , i 1, 2, ..., m
j 1 m
n
x
i 1
ij
b j , j 1, 2, ..., n
xij 0.
m n
当ai和bj满足 ai b j 时，称该运输问题为平衡的
i 1 j 1
Recap: 表上作业法
第一阶段，制定初始调运方案; 第二阶段，从初始调运方案出发，调整调运 方案，逐步获得最优解. 1. 制定初始调运方案