资源描述：
《网络优化第5章最短路问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、网络优化NetworkOptimizationhttp://www.csiam.edu.cn/netopt清华大学数学科学系谢金星办公室：理科楼2206#（电话：62787812）Email:jxie@math.tsinghua.edu.cnhttp://faculty.math.tsinghua.edu.cn/~jxie/courses/netopt清华大学课号：70420133第5章最短路问题(ShortestPathProblem)1许多实际问题都可以转化为最短路问题其有效算法经常在其它网络优化问题中作为子算法调用ST最短路问
2、题的例子和意义2例5.1（Single-levelUncapacitatedLotsizing）某工厂生产某种产品用以满足市场需求,且已知在时段t中的市场需求为dt.在某时段t,如果开工生产,则生产开工所需的生产准备费为st,单件产品的生产费为ct.在某时段t期末,如果有产品库存,单件产品的库存费为ht.假设初始库存为0,不考虑能力限制,工厂应如何安排生产,可以保证按时满足生产,且使总费用最小?（Wagner–Whitin，1958）最短路问题的例子-单产品、无能力限制的批量问题假设在时段t,产品的生产量为xt,期末产品的库存为It
3、(I0=0);用二进制变量yt表示在时段t工厂是否进行生产准备.假设费用均非负，则在最优解中，即可以证明：一定存在满足条件的最优解.可以只考虑3单产品、无能力限制的批量问题记wij为第i时段生产量为时所导致的费用(包括生产准备费、生产费和库存费),即其中网络：从所有节点i到j(>i)连一条弧,弧上的权为wi,j-1,如T=4时：12345w11w33w22w44w34w23w12w13w24w144例5.3计划评审技术,即PERT(ProjectEvaluation&ReviewTechnique),又称网络计划技术或统筹法)大型复
4、杂工程项目(Project)往往被分成许多子项目,子项目之间有一定的先后顺序(偏序)要求,每一子项目需要一定的时间完成.PERT网络的每条弧表示一个子项目,如果以弧长表示每一子项目需要的时间,则最早完工时间对应于网络中的最长路(关键路线).工程上所谓的关键路线法(CPM:CriticalPathMethod)基本上也是计划评审技术的一部分.项目网络不含圈,其最长路问题和最短路问题都是可解的.(开始)AF(结束)566744513BEDC5最短路问题给定有向网络N，弧（i，j）对应的权又称为弧长（或费用）.对于其中的两个顶点s，t，以
5、s为起点和t为终点的有向路称为s-t有向路，其所经过的所有弧上的权（或弧长、费用）之和称为该有向路的权（或弧长、费用）.所有s-t有向路中权(或弧长、费用)最小的一条称为s-t最短路.对于有向网络中的一个圈，定义它的权为圈上所有前向弧上的权的和,减去圈上所有反向弧上的权.权为正的圈称为正圈;权为负的圈称为负圈;权为0的圈称为零圈.对一个有向圈，它的权就是圈上所有弧上的权的和.本章的圈一般都是指有向圈,我们直接将正有向圈简称为“正圈”，负有向圈简称为“负圈”，零有向圈简称为“零圈”,而“无圈”指的是不存在有向圈.st6无向网络上的最短
6、路问题一般可以转化为有向网络上的问题.如果所有弧上的权全为非负（或非正）数，只需将无向图的一条边代之以两条对称的有向弧即可.如果弧上的权有负有正，一般来说问题要复杂得多。最短路问题–两点说明最长路问题可以转化为最短路问题，把弧上的费用反号即可.必须指出：目前为止，一切最短路算法都只对不含负有向圈的网络有效.对于含负有向圈的网络，最短路问题是NP困难的.因此，本章中除非特别说明，一律假定网络不包含负有向圈.7xij表示弧（i，j）是否位于s-t路上：当xij=1时，表示弧（i，j）位于s-t路上，当xij=0时，表示弧（i，j）不在s
7、-t路上.关联矩阵是全么模矩阵，因此0-1变量可以松弛为区间[0,1]中的实数不含负圈，变量直接松弛为所有非负实数思考：为什么xij可以不限定为{0，1}？最短路问题的数学描述85.2.1Bellman方程对偶问题为根据互补松弛条件,当x和u分别为原问题和对偶问题的最优解时:9Bellman方程当某弧(i,j)位于最短路上时，即变量xij>0时,一定有如果u为对偶问题最优解,易知u+c(c为任意实数)仍为最优解.不妨令us=0，则u的具体数值就可以唯一确定了.Bellman方程(最短路方程、动态规划基本方程)相当于对节点j赋予的一个
8、实数值uj（通常称为“标号”），在us=0时表示的正好是节点s到节点j的最短路的长度.一般情况下直接求解最短路方程是相当困难的.10定理5.1对于只含正有向圈的连通有向网络，从起点s到任一顶点j都存在最短路，它们构成以起点s为根的树形
