文档介绍：网络优化
Network Optimization
/netopt
清华大学数学科学系谢金星
清华大学课号:40420213(本),70420133(研)
第5章最短路问题(Shortest Path Problem)
1
许多实际问题都可以转化为最短路问题
其有效算法经常在其它网络优化问题中作为子算法调用
S
T
最短路问题的例子和意义
2
(Single-level Uncapacitated Lotsizing)
某工厂生产某种产品用以满足市场需求,且已知在时段t中的市场需求为dt . 在某时段t, 如果开工生产, 则生产开工所需的生产准备费为st , 单件产品的生产费为ct .在某时段t期末, 如果有产品库存, 单件产品的库存费为ht . 假设初始库存为0, 不考虑能力限制, 工厂应如何安排生产, 可以保证按时满足生产, 且使总费用最小? (Wagner – Whitin,1958)
最短路问题的例子- 单产品、无能力限制的批量问题
假设在时段t, 产品的生产量为xt , 期末产品的库存为It (I0 =0); 用二进制变量yt表示在时段t工厂是否进行生产准备.
假设费用均非负,则在最优解中,即
可以证明:一定存在满足条件的最优解.
可以只考虑
3
单产品、无能力限制的批量问题
记wij为第i时段生产量为时所导致的费用(包括生产准备费、生产费和库存费), 即
其中
网络:从所有节点i到j (> i)连一条弧, 弧上的权为wi,j-1 , 如T=4时:
1
2
3
4
5
w11
w33
w22
w44
w34
w23
w12
w13
w24
w14
4
计划评审技术, 即PERT(Project Evaluation & Review Technique), 又称网络计划技术或统筹法)
大型复杂工程项目(Project)往往被分成许多子项目,子项目之间有一定的先后顺序(偏序)要求, 每一子项目需要一定的时间完成. PERT网络的每条弧表示一个子项目,如果以弧长表示每一子项目需要的时间,则最早完工时间对应于网络中的最长路(关键路线). 工程上所谓的关键路线法(CPM: Critical Path Method)基本上也是计划评审技术的一部分.
项目网络不含圈, 其最长路问题和最短路问题都是可解的.
(开始) A
F (结束)
5
6
6
7
4
4
5
1
3
B
E
D
C
5
最短路问题
给定有向网络N,弧(i,j)对应的权又称为弧长(或费用).
对于其中的两个顶点s,t,以s为起点和t为终点的有向路称为s-t有向路,其所经过的所有弧上的权(或弧长、费用)之和称为该有向路的权(或弧长、费用).
所有s-t有向路中权(或弧长、费用)最小的一条称为s-t最短路.
对于有向网络中的一个圈,定义它的权为圈上所有前向弧上的权的和, 减去圈上所有反向弧上的权. 权为正的圈称为正圈; 权为负的圈称为负圈; 权为0的圈称为零圈.
对一个有向圈, 它的权就是圈上所有弧上的权的和. 本章的圈一般都是指有向圈, 我们直接将正有向圈简称为“正圈”, 负有向圈简称为“负圈”, 零有向圈简称为“零圈”, 而“无圈”指的是不存在有向圈.
s
t
6
无向网络上的最短路问题一般可以转化为有向网络上的问题.
如果所有弧上的权全为非负(或非正)数,只需将无向图的一条边代之以两条对称的有向弧即可.
如果弧上的权有负有正,一般来说问题要复杂得多。
最短路问题–两点说明
最长路问题可以转化为最短路问题,把弧上的费用反号即可.
必须指出:目前为止,一切最短路算法都只对不含负有向圈的网络有效. 对于含负有向圈的网络,最短路问题是NP困难的.
因此,本章中除非特别说明,一律假定网络不包含负有向圈.
7
xij表示弧(i,j)是否位于s-t路上:当xij =1时,表示弧(i,j)位于s-t路上,当xij =0时,表示弧(i,j)不在s-t路上.
关联矩阵是全么模矩阵,因此0-1变量可以松弛为区间[0,1]中的实数
不含负圈,变量直接松弛为所有非负实数
思考:为什么xij 可以不限定为{0,1}?
最短路问题的数学描述
8
Bellman方程
对偶问题为
根据互补松弛条件, 当x和u分别为原问题和对偶问题的最优解时:
9
Bellman方程
当某弧(i,j)位于最短路上时, 即变量xij>0时, 一定有
如果u为对偶问题最优解,易知u+c (c为任意实数)仍为最优解.
不妨令 us=0 ,则u的具体数值就可以唯一确定了.
Bellman方程(最短路方程、动态规划基本方程