（运筹学与控制论专业论文）动态最小费用路在l1模下的逆问题研究.pdf

摘要 本文将动态网络优化问题和逆优化问题相结合，考察动态最小费用路在l ，模下的逆 问题，其中在弧费用的定义中，将弧( i ，j ) 上的运行时间d , j ( t ) 分成最小可能运行时间d 玉 和超出的运行时间( e x c e s st i m e ) e t j ( t ) 两部分，弧( i ：j ) 上费用即为两者赋权之和 本论文的研究和创新工作主要包括以下内容： ( 1 ) 介绍离散情形和连续情形下两种基本的动态网络流模型，引入时间扩张图概念， 用于将动态网络转化成静态网络，从而提供了一个解决动态网络优化问题的工具 ( 2 ) 在弧费用的特定定义下，介绍一个求解最小费用途径问题的较优的伪多项式时间 算法，并对该问题的更一般情形给出一个一般算法 ( 3 ) 论述t l l 模下线性规划的逆问题的求解问题，阐明了线性规划中逆问题的对偶和 原问题的松弛之间的关系 ( 4 ) 研究动态最小费用路在l ，模下的逆问题，通过时间扩张网络g r 将动态问题转化 为静态阏题，再利用解线性规划的逆问题的方法给出该问题的结果，并给出相应算法 关键词：运行时间；时问扩张图；动态最小费用路；对偶；逆问题；时间复杂性 a b s t r a c t i nt h i sp a p e r ，w es t u d ya ni n v e r s ed y n a m i cm i n i m u mc o s tp a t hp r o b l e mu n d e rl 1n o r m w h i c hc o m b i n e dd y n a m i cn e t w o r kc o m b i n a t o r i a lo p t i m i z a t i o nw i t hi n v e r s eo p t i m i z a t i o n t h e c o s to ft r a v e r s i n ga r c ( i ，j ) i sd e f i n e da st h ew e i g h t e ds u mo ft h em i n i m u mp o s s i b l et r a v e l t i m e 喵a n d t h ee x c e s st r a v e lt i m e ( o v e rt h em i n i m u mp o s s i b l et r a v e lt i m e ) e , t ) t h ep a p e r i so r g a n i z e da 8f o l l o w s ： ( 1 ) p r e s e n t st w ob a s i cd y n a m i cn e t w o r kf l o wm o d e l si n c l u d i n gd i s c r e t ef l o wo v e rt i m e a n dc o n t i n u o u sf l o wo v e rt i m e ，a n dt h ec o n c e p to ft i m e - e x p a n d e dg r a p hw h i c hc a nt r a n s f o r m e v e r yd i s c r e t ef l o wo v e rt i m ep r o b l e mi n t oa s t a t i cf l o wp r o b l e m ( 2 ) d e v e l o p sap s e u d o p o l y n o m i a l t i m ea l g o r i t h mt os o l v et h em i n i m u mc o s tw a l kp r o b l e m ( f o ri n t e g e rt r a v e lt i m e s ) a n de x t e n dt h ep r o b l e mt ot h em o r er e a l i s t i cc a s e ( 3 ) d i s c u s s e ss o l v i n gt h ei n v e r s el i n e a rp r o g r a m m i n gp r o b l e mu n d e rt h el 1n o r ma n d d a r i f i e st i l ec o n n e c t i o nb e t w e e nt h ed u a lo ft h ei n v e r s ep r o b l e ma n dar e l a x a t i o no ft h e o r i g i n a lp r o b l e m ( 4 ) g i v e st h er e s u l ta n da na l g o r i t h mo ft h ei n v e r s ed y n a m i cm i n i m u m c o s tp a t hp r o b l e m u n d e rl 1x l o r mb yu s i n gt i m e - e x p a n d e dg r a p ha n dt h ea p p r o a c hf o rs o l v i n gt h ei n v e r s el i n e a r p r o g r a m m i n gp r o b l e mu n d e rl 1n o r m k e y w o r d s ：t r a v e lt i m e ；t i m e - e x p a n d e dg r a p h ；d y n a m i cm i n i m u mc o s tp a t h ； d u a l ；i n v e r s ep r o b l e m ；t i m ec o m p l e x i t y i i 第一章引言 本文研究的是动态最小费用路在l l 模下的逆问题，这是一个涉及动态网络背景的逆问 题讨论这样个问题不仅需要逆优化问题的相关知识和技巧，还要考虑动态网络中的时 间特征本章首先引入对动态网络流与动态最短路问题的讨论，然后简要描述了逆优化问 题，最后介绍本文的研究内容，研究方法和主要结果 1 1 动态网络流与动态最短路问题 网络流是组合优化领域中的种基本而重要的问题经典的网络流，诸如最短路，最 大流，最小费用流等这类网络优化问题受到关注较多，已经得到了很好的解决，也给出了 很好的结果还有一类优化问题产生于现实的应用中，如道路交通控制，生产系统，通讯 网络等等，在问题的阐述中时间成为一个不可忽略的重要因素，这类问题就是动态网络流 i 7 题与之相对应，我们也将传统的网络流问题称为静态网络流问题动态网络流模型首 先是由f o r d 和f u l k e r s o n 于上世纪五十年代后期提出的，由于与现实问题联系比较紧密， 逐渐引起了人们广泛的兴趣，尤其近些年来，在动态网络流问题的研究上取得了很大的进 展 动态网络流实际上就是在传统网络流问题的基础上加入了时间的因素，从而使之从 两个方面区别与后者首先，弧上的流值随时间而变化这个特征具有重要的现实意义， 如在交通运输模型中，高峰时段的车流量观显要高于其它时段的流量其次，每个流经历 每段弧需要花费一定数量的时间单位即运行时间一般说来，在实际应用中不仅流速而且 弧上的运行时间都是随时间而变化的正是由于以上时间的因素，这类问题比静态网络流 浙江大学硕士学位论文 问题要难解得多f o r d 和f u l k e r s ；o n 考虑的是离散时间情形下动态流模型，随着研究的深 入，连续时间的度量方法也被引入到动态流模型中，并且成为一种常用的方法 最短路问题是人们所熟知的一个经典的网络优化问题，在静态意义下它有行之有效的 算法然而许多最短路问题又具有动态网络的特征，如弧上某些参数随着时间以一种可以 预计的方式而变化，这就是动态最短路问题c o o k e 和h a l s e y i ：j ：1 9 6 6 年首次提出离散时 间下的动态最短路问题这类问题也经常产生于运输问题的应用中 动态最短路问题就是动态网络中的最短路问题，由于弧上的量加入了时间因素，因而 通常是p 困难的，在文献中有很多关于此类问题的讨论，如c h a b i n i ( 2 ， 3 】) ，d r e y f u s 【4 ，k a u f m a n n 和s m i t h 【5 】，k i r b y 和p o r t s 【6 ，o r d a 和r o m ( 7 】， 8 ) ，p a l l o t t i n o 和 s c u t e l t a 9 ，z i l i a s k o p o u l o s 和m a h m a s s a n i 1 0 j ，w a r d e l l 和z i l i a s k o p o u l o s 1 1 f 给定一个有向网络g = ( ，a ) ，其中为节点集，a 为弧集，1 n i n ，l a l = m ，其 中s n 为源点g 中的节点序列w = ( i 1 ，i 2 ，i ，- 1 】0 ) ，1 冬r 一1 ，( k ，i k + 1 ) a 称为 一个有向途径若有向途径w 中无重复节点，则称为有向路这里假设沿着每条弧运行的 时间是这条弧上出发时刻的函数，我们考虑的是从一个指定的源点到其它节点的关于时问 及费用的两个动态最短路问题，即最小时间途径问题及最小费用途径问题 1 2 逆优化问题介绍 当我们解一个优化问题时，经常假设诸如费用，容量等参数是已知的，我们感兴趣的 是如何找出一个最优解然而，在实际当中，可能仅仅知道某些参数的估计值此外，我 们也可能通过观察或试验知道某些解是最优解在这种情况下，我们要去推断出某些参数 的值，这类问题就是逆优化问题 设p 表示一个优化问题的实例，s 船是可行解的集合，c 础是给定的费用向 量，f ：磁n 渺一鼹是目标函数，则原问题p 可表示为 r a i n f ( c ，o ) s t o s _ 2 浙江大学硕士学位论文 逆优化问题的思想就是通过改变某些参数的值使得给定的解成为最优解，、并且使参数 的改变量尽可能的小设岔s 是给定的一个可行解，它可能不是问题p 关于费用向量c 的 最优解，为了使圣成为最优解，需要改变c 将调整后的费用向量记为e ，用p f j ) 表示将原问 题p 中的费用向量c 替换成6 后所对应的优化问题p 的逆问题的目标就是尽可能小的将c 调整到6 ，使岔成为p ( e ) 的最优解令r ：= r u 仕。 ，设f “融表示调整以后的费用 向量a 的下界和上界，- 为向量的某一模，则尸的逆问题表示为 蛐n 8 t 胪一c ，( e ，圣) = m i n f ( o ，z ) ：z s 2 e u ，e r ” 逆问题的模通常考虑如下的几种情形： 1 l l 模：舱一t i l l = j j 钍。l 白一勺i ，j 表示变量巧的指标集，叼表示对应变量j 的 权，若( ) 托j = 1 ，则称为单位权厶模 2 l 2 模：l l e c l 2 = 【j 。ji 岛一勺1 2 j 3 l 。模： 一c l ；。= m a x 3 e j 屿j 冬勺， 此外，近些年来，在逆优化闻题的研究中还出现了一个较新的分支，即哈明距离下的 网络逆问题设日( u ，”) ： 1 ，钍”是u 与 间的哈明距离，定义以下两种范数： 10 ，札= ” 即= w j h ( a j ，o ) h ，o 。一脚m a x 、。w j h ( a j ，o ) 若逆问题的目标函数考虑这两种范数，则称为哈明距离下的逆优化问题这类逆优化问题 具有较大的理论研究和实际应用价值 逆问题是由地球物理学家们在研究地震运动时首先g l 入研究的t a r a n t o l a 于1 9 8 7 年在 地球物理科学领域首次对逆问题理论进行了阐述1 9 9 2 年b u r t o n 和t o i n t 对逆最短路问题 进行了研究此后，人们逐渐对逆优化问题产生了兴趣，并对许多逆优化问题进行了深入 的研究。这其中在逆线性规划和逆网络流问题上做了大量的工作，比如z a n g 和l i u 皿2 j 研 浙江大学硕士学位论文 窥了逆指派和逆最小费用流问题；y a _ f i g ，z h a n g 和m a 1 a ，z h a n g 和c a i 1 4 研究了逆 最小割问题；) h 和z h a n g 【15 】研究了逆最短路问题；s o k k a l i n g a m ，a h u j a 和o r l i n 【1 6 研 究了逆生成树问题；a h u j a 和o r l i n 1 7 】研究了逆排序问题哈明距离下的网络逆问题的研 究尚处于起步阶段，已做的工作有：h e ，z h a n g 和y a o 【1 8 研究了哈明距离下的加权逆最 小支撑树河题；z h a n g 和h e 1 9 】研究了哈明距离下的中心选址改造问题等 1 3 本文的主要研究内容和结果 本文首先描述了动态网络流模型，讨论了动态最短路问题、线性规划的逆问题等相关 问题，在此基础上对动态最小费用路在l 。模下的逆问题进行了研究 第二章主要叙述了确定运行时间情形下动态网络流的两种基本模型：离散动态流模型 和连续动态流模型，引出了将动态网络转化成静态网络的时间扩张图概念，并阐明了两种 动态流模型之间的关系 第三章研究的是动态最短路问题，介绍了最小时间途径问题的有关结果，详细证明了 最小费用途径问题的p 困难性，并给出一个已知较优的算法对弧费用的参数为变量的 最小费用途径问题本文给出一个一般算法 第四章介绍的是逆优化问题，对线性规划在l 。模下的逆问题的求解进行了详细的讨 论，并将结果应用于0 一】线性规划，最后给出了关于线性规划逆问题的已知结果 第五章研究动态最小费用路在l t 模下的逆阀题，给出一个求解该问题的伪多项式时间 算法 4 第二章动态网络流模型 动态网络流模型是研究动态网络问题的基础，根据对时间划分形式的不同，可以分 为离散时间的动态网络流模型和连续时间的动态网络流模型两大类与静态网络流模型相 比，虽然只是加入了时间的因素，动态问题的难度却大大增加了本章不对动态流模型作 深入的探讨，只给出较简单情形下的动态网络流模型的概念 本章的内容安排如下：第一节首先介绍网络流的预备知识以及静态流模型 第二节给出了离散动态网络流模型及在这种模型下将动态流转化成静态流的工具一时 间扩张图 第三节简要介绍了连续动态网络流模型。 第四节讨论了两种模型之间的关系 2 1 预备知识 给定一个有向网络g = ( u a ) ，考虑g 中只含有单个源点及单个收点的情形，s 和t 分 别表示源点及收点既不是源点也不是收点的节点称为中间节点源点s 上对应一个供 应d 0 ，收点t 上对应一个需求一d 对节点 v ，矿( u ) 和6 一( ) 分别表示节点u 的出弧和 入弧的集合对每条弧a a ，定义容量 0 ，费用c d 芝0 ，及一个非负，非减，左连续 的运行时间函数： 0 ，札。】一r + g 中一个静态s t 流z 在每条弧a a 上分配一个非负流值o 。，使得以下流量守恒成 5 浙江大学硕士学位论文 z 。一z 。= 0 ， d + ( 口)a e j 一( 口) 箬茹遵守容量约束，即如u 。， a a ，称静态流z 是可行的若 一z 。= d l ，可 s ，毋 。d + 一)a e 6 一) 则称静态流。满足供应和需求静态s 一# 流z 的流值即为 茁 = 茁。一z 。 n d + b )a e 6 一( s ) 静态流茁的费用定义为：c ( 。) = 。ac a x 。 为了从概念上描述方便，在下面对动态流模型的讨论中假设弧上的运行时间不变 即( 矗) 。a 为定值路径p 上的运行时间定义为印一。p 气 2 2 离散动态网络流 2 2 1 离散动态网络流模型 假定) 。a 取整数值对每条弧a = ( u ，w ) a ，g 中一个离散动态流厂定义了一个函 数，口：z + 一r + 对于口z + ，丘( 日) 表示在时间段f 口，0 + 1 动态流，进入弧a 的流量总和 在时n o 进入弧a 的流到达节点w 的时刻为0 + r a 由于弧a 上的运行时间是整数，在动态 流，上定义如下的整数时间范围t ：如果在时刻t 一1 一气之后任一弧n a 上都没有流进 入，称动态流，有时间范围t ，即：对于a a ，0 t 一，有 ( 目) = 0 与静态流模型类似，我们同样要求动态流，满足流量守恒原则考虑到现实中可能会 出现流在中间节点暂时储存的情况，即流在到达节点后暂时停留一段时间再向外发送，并 最终在时间范围t 内到达收点t ，可将离散动态流，的流量守恒约束描述为： ，0 ( 口) 一厶( p 一) 冬0 ， 可s ，t 一1 ( 2 1 ) 口5 + ( ”) 0 = 0a e 6 一( ) 0 = 7 a 6 浙江大学硕士学位论文 e 上式中，左边和式表示到f 十1 时刻为止流出节点钞的流量总和，类似的，右边和式表 耩到f + 1 时刻为止流进节点口的流量总和考虑到流在中间节点的储存，因此到 + 1 时 朗为止节点u 的净流出量是小于或等于。的当 隹( s ，t ) ，= t 一1 时，所有中间节点储 孥的流都在时间范围t 内到达收点t ，等式成立 若对所有的p z + ，o a ，厶( p ) 曼u 。，则称动态流，是可行的若” s ，讣， t 一1t 一1 f o ( o ) 一a ( o 一) = 南 ( 2 2 ) 口p ( u ) 日= oo 5 一( u ) 日= h 称动态流，满足供应和需求动态流，的费用定义为 t 一1 c ( ，) = c 。九( 目) 8 a p = 0 由于只有一个源点及一个收点，又将，称为动态s t 流，其流值为 t 一1r l i f l = 丘( 目) 一 ( 口一) 。d + ( 对口；o口j 一( s ) o = 危 这里i ，j 是到时刻t 为止从源点s 流出的总流量，由于流量守恒的缘故，j ， 也等于到时 刻t 为止流入收点t 的总流量 2 ，2 2 时间扩张图 时间扩张图f 2 0 是f o r d 和p a l k e r s o n 当时在处理离散动态流模型时提出的概念，用于 设计和分析离散情形下的动态流算法，作为动态流模型与静态流模型之间联系的平台，这 个概念的提出使动态流模型转化为静态流模型在理论上成为种可能时间扩张图本质上 就是对应每个节点在每一个可能的时刻都作为一个节点固定下来，从而将流在原网络中的 动态流动静态化，这样就使我们有可能用静态问题的相关算法来解决动态流问题下面来 具体介绍这个概念 给定个离散动态流问题，有向图g = ( v a ) ，弧上的运行时间矗及时间范围t 为整 数，g 的t 时间扩张图记为g t 则g 伊通过以下过程得到： 1 节点的复制：g 中每一节点”v 对应g t 中的节点 d ， 1 ，叼一l ，其中表示节 点u 在口时刻对应的节点，目 o ，i ，于一1 7 浙江大学硕士学位论文 2 弧的复制：g 中每条弧n = ( ， t o ) a j 对应g t 中的从节点到叫口+ 。的弧口( 口) ， 芍虑到os 日 t h ，这样的弧口( 日) 有t 一条弧o ( 目) 的容量及费用均和弧a 保持致 3 延滞弧：如果允许流在节点 v 暂时储存，则引入一种容量为无限大的延滞 孤( 珊，u 口+ 1 ) ，其中o s 目 t 一1 下面给出了一个动态图转化为时间扩张图的简单例子，其中左图是一个给定的动 态图g ，时间集t = o ，1 ，2 ，3 ，4 ) ，弧上的数字表示运行时间；右图是g 对应的时间扩张 图g r 如果允许流在中间节点储存，则g 口包含图中用虚线表示的延滞弧，否则忽略 毋一4 拶= 3 毋= 立 疗。1 拉一0 图1 在r 时间扩张图中，可将其看作静态网络流这样一个离散的动态流在g v 中就与一个 静态流一对应起来显然这种转化是保持费用的如上图例予所示，g 中的动态s t 流一 一对应于g 叮中的静态- s o t t 一1 流 因此每一个离散动态流问题都可以转化成一个时间扩张图中的静态流问题来处理考 虑n g t 的规模是线性依赖于t 的，一个多项式时间的静态流算法应用在对应的动态问题中 通常成为个伪多项式时间算法 8 浙江大学硕士学位论文 ：一 2 3 连续动态网络流 由于本文主要研究离散情形下的动态问题，因此对于连续情形的动态网络流只作一个 渝单介绍 g 中一个连续动态流，是由以下l e b e s g u e 可测度函数厶：r + 一r + 定义的，对每 条弧d a ，( 目) 表示在口时刻动态流，进入弧口时的流速如果在时刻? 一之后任 一弧。a 上都没有流进入，称动态流，有时间范围t ，即：对于。a ，口三t 一亿， 有矗( 8 ) = 0 同离散情形下的动态流一样，连续动态流，也满足流量守恒原则，其形式为： 。三，胁州卜。磊，胁h 瑚弛峨球阳，眨3 ， 由于在时刻丁时除了收点t 其它节点上都没有流存在，因此当u 隹 s ，t ) ，= t 时，等式成 立 若对所有的8 r + ，。a ，a ( o ) 珏。，则称动态流，是可行的。若勘0 ，t ， 。三，f o t f 。扯a e 6 - ( 。，r 坤叫拈也 眨4 ， 称动态流，满足供应和需求动态流，的费用定义为： c ( ，) = f a ( o ) d o 2 4 两个模型的关系 下面讨论离散动态流和连续动态流模型之间的关系一方面，g 中任一离散动态 流，口为整数) 对应于一个连续动态流，：这时把流量，a ( p ) 看作是时段 9 ，口+ l 】内弧。上的 固定流速五( p ) 因为在每个时段p ，p + 1 】上，都有厶( p ) ，即五( 口) su 。，因此，是可 行的对z + ，下面验证，在节点”s 满足连续动态流的流量守恒约束： 。蒹，胁啪。善，f 加圳= 。蒹善：o ( o ) - 矧e ，量脚刊 9 浙江大学硕士学位论文 鞫为，是满足流量守恒约束的，即等式右边是小于等于。的，从而，也满足流量守恒类 m 的，可证明，也满足与，相同的供应和需求 另一方面，当时间范围t 与弧上运行时间( ) 。a 均为整数时，g 中一个连续动态流， 钶看作是个离散动态流，：只要对所有的口a ，0 0 t 一1 一，置 厂口+ 1 ，8 p ) ：= 7五悠) ( 2 , 5 ) d 对每一整数时间值日，因，是可行的，有：矗( 口) = 片“五( ) 必譬“u a d su 。，所以， 是可行的同样也可以验证，满足流量守恒约束及供应和需求 在以上两种转化中流的费用均保持不变需要说明的是，当t 和( r ) 。a 取整数值时， 通过将连续动态流问题转化成一个楣应的离散动态流闯题，进而可将其转化成一个r 时间 扩张图g t 上的静态流问题来讨论，这具有很重要的意义f l e i s c h e r 和t a r d o s 已经证明即 使t 不是整数，仍有相当大数量的离散动态流算法可以用来解对应的连续动态流问题 2 5 小结 在本章，我们主要阐述了确定运行时间情形下动态网络流的两种基本模型：离散动态 流模型和连续动态流模型，介绍了在设计离散动态流模型的算法时常用到的种工具：时 间扩张图时间扩张图的提出具有重要意义，它使我们有可能将动态网络问题转化成静态 网络问题来讨论此外还讨论了这两种动态流模型之间的关系，即两种模型之间可以互相 转化，进而可以用各自算法来解对应的模型 1 0 g g - _ 章 动态最短路问题 、，。妻苎筻内容安排如下：第节根据弧上的运行时间及费用的定义给出两个动态最短路 问题的描述 一 第二节简要介绍了最小时间途径问题的结果 。薰篓篓要剐、费用途径闫题的p 困难性，并通过简化运行时间的定义给出个伪 多项式时间算法 第四节讨论了弧费用定义中参数为变量情形下的最小费用途径问题 3 1 问题的描述 定义3 l 噶= m i n 奶( t ) ：t 巧为弧( t 上的最小可能运行时间 8 u ( ) 2 岛( 。) 嘞为t 时刻开始经历弧( i ，j ) 的超出时间f e x c e s 8t i m e ) e + 。m a x ( 8 玎0 ) ：( f ，j ) a ，t r n n n n 出时n 1 1 一帆一一赫一 硐错啪眦埔幢 骄筋喇袖耻卧掷一一一 啉溉则搬州靳确雏呱黜鼢 一一籼一一 一一一一 考恫“那仅少 一一一一 浙江大学硕士学位论文 c ，j ( t ) = q 矗+ ( 妨为对刻开始经历弧( 1 ，j ) 所需支付的费用，这里口，p 为 暗定非负参数 由定义知，条弧上的费用线性依赖于这条弧上的最小可能运行时间和超出时间又 。“ ) = d 专+ p 8 玎0 ) = c v d ( j ) + ( p n ) 8 旬( 亡) = 卢d 订 ) + ( a p ) 唱， 可见该定义也可用于弧上的费用线性依赖于弧上的运行时问和超出时间或线性依赖于弧上 构运行时间和最小可能运行时间的模型若p = n ，定义的弧费用为弧上运行时间的乜倍 着p = 0 ，。f = 1 ，定义的弧费用即为弧上的最小可能运行时间若q = 0 ，p = l ，定义的 弧费用为弧上的超出时间若0 卢 a ，这定义了超出时间比运行时间占用更少费用的情 形，例如在车上的等待时间花费的费用比驾驶时间要少若q o 时，可将弧费用记为( t ) = + ：( ) 若p 一0 ，最小费用途径问题可归 结为通常的最短路问题若口= q ，则问题变为最小时间途径问题，可见最小时间途径问题 是最小费用途径问题的特殊情形下面给出q 和p 的其它取值情况时问题的复杂性及其证 明【2 2 】 定理3 5 设最小费用途径问题的弧费用为0 ) = 蠕+ ：e 巧( 嘎则对于口，臼的取值 为严格正整数且n 卢时，对应的最小费用途径问题是n p 困难的 证：给出数字划分问题到最小费用途径闯题的一个转换设盘l ，o 。，b 是数字划分问 题的输入首先考虑o 卢的情形设每一0 及b 均为口一j 8 的整数倍( 否则，用数 1 3 浙江大学硕士学位论文 字划分问题中所有的整数乘以口一p ) 构建一个网络岔= ( n ，a ) ，其中节点集n = f 1 ，1 7 ，2 ，2 7 ，n + 1 ，( n + 1 ) ，扎+ 2 ) ，对每一个i = 1 到n ，引入一条从i 到i + 1 的弧，定义 对所有t ，d ，件l ( t ) 一件1 = 差此外，再引入弧( t ，i ) 和( 以i 十1 ) ，对所有t ，弧( t ，计1 ) 上 的运行时间都为0 对弧( i ，t ，) 成i ，= 0 ，8 讲，( t ) = 鲁岛( 对于某个很大的寺值，设d ，f ( t ) = 0 可以保证i = o ) 注意到弧( i ，i + 1 ) 的费用是磐，弧( t ，t 7 ) 的费用是! 吉 = 盥c 。- - l f 3 因而 从i 到i + 1 的运行费用对于从i 到i 十1 的两个子路来说是相同的而两个子路上的运行时间 是不同的其差值为盛，( t ) 一画，件l ( t ) = 旦a - 吐一差= n t ，现在考虑弧+ 1 ，钆+ 2 ) ，设t 7 = 6 + 1 吉，对所有t ，弧( n 十1 ，札+ 2 ) 有嚷, 8 + 1 ，计2 = 0 ，e 叶l 卅2 ( ) = 1 ，且。+ 1 ，。+ 2 ( t ) = 0 下面证明存在一条从节点l 到节点礼+ 2 费用为：】鹣的路径当且仅当数字划分问 题有一个解首先，假设x 是数字划分问题的一个可行解设彤是如下定义的从节点1 到节 点n + 2 的途径：若鼢= 1 ，则包含孤( i ，i 7 ) 和t + 1 ) ；若甄= 0 ，则w 包含弧( ，i + 1 ) 途径也包含弧( 礼+ l ，7 2 + 2 ) 注意到在彬上花费亡，单位的时间到达节点n + 1 后，在相同 时刻到达节点礼+ 2 ，在- 矿上花费的费用恰为：1 黠 反过来，假设缈是一条从节点l 到节点+ 2 费用为ij 的路径因为每条从节 点1 到节点几+ 1 的路径，其费用为：1 岛，可知弧( n + 1 ，扎+ 2 ) 上的超出时间为o ，因 此路径到达节点7 z + 1 的时刻为t 7 设嗣= l 若i ) w ，甄= 0 若( i ，i + 1 ) w ，则正是 数字划分问题的个可行解 这样就证明了 的情形，对于 0 ，p 0 给定，且口p 时，考虑求解最小费用途径问题，并给出相应的算 法 2 2 1 构建时间扩张网络 处理动态网络问题的通常方法是构建一个时问扩张网络g r ，将动态问题转化为静态 问题来讨论 = ( v e ) 构建如下： 1 4 浙江大学硕士学位论文 y = 讧：i n ，1 h q ) e ； ( 如，j 1 ) ：( i ，j ) a ，t h + d = c j ( t h ) = 南，1 h l q ) u ( ( s ，8 h + 1 ) ：1 h g 1 ) u ( 岛t ， + 1 ) ：1 冬h q 一1 ) 对应不同出发时间的弧( 如，m ) e 至多有g 条g 丁中对应弧( t h ，a ) 的费用为口略十 卢e 。j ( 如) 根据假设g r 是个无圈网络 性质3 6g 中每条在t l = 0 时刻从源点s 出发于t 。时刻到达节点j 的途径都一一对 应于g t 中一条从s - 到血的路径，且两者所需支付的费用相同 这样g 中的最小费用途径问题就转化为g 丁中的最短路问题来解我们知道在无圈网络 中，最短路问题可以在线性于网络中弧的数量的时间内被解，而g t 有d ( m 口) 条弧，因此 最小费用途径问题可以在0 ( m g ) 时问内被解随着g 的增大，当e + 增长较慢时，通过下面的 技巧可以给出一个较0 ( m g ) 更优的算法 简化运行时间 考虑g 中关于最小可能运行时间嘭的最短路问题设p ( 尼) 表示从源点s 到节点膏的最短 路，丌( k ) 表示其运行时间由最短路最优化条件知： ：；三：；：耄： i , ，j ，) ep a i j 。詹，惫n 、。， c s 。， 仃( j ) = 7 r ( i ) + 略，( ，) p ( 詹) ，惫 s ) 、。 由于弧长是非负的，不失一般性设汀( s ) = 0 将关于7 r 的简化的最小运行时间噶”定义 为：呓”2 屹+ 丌( i ) 一丌0 ) ，则最短路最优化条件可简化为： 孽呈滦i , j ) 6 a i 啉博) ( 3 a ) 戎f ”= o ，( ，j ) p ( ) ，角0 ) 、 同样，设喝( t ) = 如( t ) + 7 r ( i ) 一丌( ，) 表示弧( i ，j ) 上简化的运行时间( t ) 一奶( t ) 一略= 唱( t ) 一d ”，因此，这种简化不影响超出时间相应地，喝( t ) = o 奶”+ p ( ) 表示 弧( ，j ) 在t 时刻的简化的费用 引理3 7 g 中一条从源点s 到节点的途径w 是关于费用( t ) 的最小费用途径当且 仅当w 是关于简化的费用唱( z ) 的最小费用途径 1 5 浙江大学硕士学位论文 证 c ( ) 一矿( ) = a ( 矿( 彬) 一矿”( ) ) = q 屹一口( + 7 r ( i ) 一丌o ) ) ( i , j ) e w ( j ) = 一a ( 丌( s ) 一7 r ( 南) ) = a v ( k ) 对于每一节点南，c ( w ) 与c 丌( w ) 只相差一个常数量，因此一条从源点s 到节点七的关 于费用c 的最小费用途径也是关于费用c 竹的最小费用途径 一 由该引理知，解关于费用c 的最小费用途径问题等价于解关于简化的费用，的最小费 用途径问题 引理3 8 设p = 甓幂茜，那么每一条从源点s 到其它节点后的最小费用途径的简化的 最小运行时间都不多于例 证：设p ( 后) 表示从源点s 到节点是的关于蝣的最短路，将p ( ) 记为p ，则p 的简化的费用 为： c r ( p ) = a d “( p ) 4 - p e ( p ) = l ? e ( p ) sp ( n 一1 ) 矿 ( 3 5 ) 因为p 至多有礼一1 条弧，且每条弧上的超出时间至多为e + ，上式显然成立要证明引理只 要证明任一简化的最小运行时间至少为p 的途径尸7 ，其简化的费用都大于或等于c 丌( p ) ， 因此都不会比路径p 更优下面分两种情况来证明 设口2 卢，此时p = 面b ( n 硫- i 丽) e = ( n 一1 ) e + 对于任简化的最小运行时间至少为p 的 途径，其简化的费用至少为卸助= p ( 扎一1 ) 矿矿( 尸) 再考虑q 0 ，而将超出时间部分对应的参数定义为弧上的函数如即：e i j ( t ) = 。屹+ 屁j 8 。( # ) ，这样定义在现实中具有更为普遍的意义，比如既在交通运输中可以根据 道路使用状况及其重要程度在不同的道路上定义不同的费用参数 给定g 中一条途径w ，从0 时刻开始经历途径w 所需支付的费用可表示为： c ( ) = 叼( t ) = 口f ( w ) + 等( t ) ( ，j ) 阿( i j ) e w ” 在此定义下的动态最小费用路问题是求t ，= 0 时刻开始从源点s 出发到每一个其它节点忌 的最小费用途径w ，即m i nc ( w ) 若对所有( i ，j ) a ，均有岛= p 为定值，则由定理3 5 知对应的最小费用路问题是 n p 困难的因此一般的动态最小费用路问题当然也是n p 困难的 本文给出解该问题的一个伪多项式时间算法，称为b u c k e t 标号算法 b u c k e t 标号算法 】7 浙江大学硕士学位论文 步骤1 构建时间扩张网络g t ，将g r 中的弧( i h ，五) 上的费用置为) = 凸略+ 艮( 如) 步骤2 在g 口中按照时间顺序建立一个b u c k e t 表日= 目，b 2 ，玩) ，其中b h 表示在t 时 刻到达节点的集合，称为一个b u c k e t 给g r 中每一节点 赋予一个费用标号，用于 表示当前从源点s l 到节点如的最小费用+ 按时间顺序对占k 中的节点进行标号，对 每一b u c k e t 中的不同节点，按照d i j k s t r a 算法中的标号顺序进行标号，直到所有的 b u c k e t 为空( 即所有b u c k e t 中的节点都已标号完毕) 步骤3 比较所有如的标号，找出最小者即为t 1 = o 时刻从源点8 到节点i 的最短路的费用 该算法的时间复杂性：j , j o ( i e + q n l o g n ) = o ( q ( m + n l o g n ) ) 3 5 小结 本章讨论的是动态最短路问题，尤其是最小费用途径问题及其推广的情形主要内容 有： 1 ，给出最小时间途径问题在f i f 0 网络及非f i f o 网络中的不同结果 2 详细证明最小费用途径问题的尸困难性 3 给出个已知较优的求解最小费用途径问题的伪多项式时间算法 4 对弧费用的参数为变量的最小费用途径问题给出一个一般算法 t 8 第四章逆优化问题 逆优化问题考虑的是，已知原优化问题的某个可行解，通过改变优化问题的某些参数 的值使它成为最优解，并且使得参数的改变量尽可能的小鉴于本文主要研究的是动态最 短路在l ，模下的逆问题，而最短路是一种特殊的线性规划，因此这章我们主要给出线性 规划在l 。模下的逆问题的相关讨论 关于线性规划在h 模下的逆问题，z h a n g 和l i u 1 2 证明这个问题是可解的a i a 和 o r l i n 2 3 】进一步阐明了在线性规划中逆问题的对偶和原问题的松弛之间的关系，并证明 了在一些网络流问题中，利用简化费用的定义，逆问题的解易于通过求解原问题来获得 本章的内容安排如下：第一节讨论线性规划的逆问题及其在l 1 模下的解撂矧 第二节将线性规划在三l 模下的逆问题的结果应用子0 1 线性规划 第三节给出线性规划逆问题的其它已知结果 4 ，1 线性规划在l 1 模下的逆问题 考虑如下的线性规划问题，记为l p ： r a i n j j 乌q s t 、j j a i j x j 玩，；_ ， 0 ， ， j j 一巧一呦，j j 1 9 ( 4 1 ) 浙江大学硕士学位论文 其中，表示向量。的指标集合，j 表示不等式约束的指标集，l j 和分别表示的下 界和上界分别用丌、沁、咖表示( 4 1 ) 式中三个不等式约束所对应的对偶变量，则l p 的对 偶阃题可表示为： m a x ；i 玩孔+ j j 如b 一j j 呦如 s t 讵j 。廿砸+ 如一奶= q ， j j( 4 2 ) 7 l i 0 ，i ，i 0 ，j j ；九0 ，j j 由线性规划的最优性条件知，( 4 1 ) 的初始解。和对偶解( 丌，a ，) 是各自问题的最优解 当且仅当z 和( 丌，a ，) 都是可行的，并且满足以下互补松弛条件： ( 1 ) 当j j a i j x j 玩，则丌t = o ( 2 ) 当 b ，则= 0 ( 4 , 3 ) ( 3 ) 当码 吩，则咖= 0 设z o 是( 4 1 ) 的一个可行解，b 、己、u 分别表示( 4 1 ) 式中的三个不等式约束关于妒取 等式时的指标集，e b b = 0 ，：托j o 订。 = 6 i ，三= d j ：巧0 = b ) ，u = d j ： 巧o = 嘶) 设f = d j ：0 0 弓= 呼+ j 哆 ，哆 o 且砖 唧 ( 4 8 ) 【勺， 其它 这样就可以通过解( 4 6 ) 来解线性规划在三1 模下的逆问题，即利用最优值丌通过( 48 ) 式 来获取最优费用向量，此外，线性规划在l 1 模下的逆问题也可以考虑通过解( 4 6 ) 的对 偶问题来解决，并且在下面可以证明( 4 6 ) 的对偶闻题即是原问题( 4 1 ) 的一个孝公弛为此 将( 4 ，6 ) 中第，个等式约束对应的对偶变量记为协，则线性规划在l 1 模下的逆问题的对偶问 题的形式为： r a i n 3 。c 弹i s , t e 俺jo t ) 珊o ，i b o 协5 屿， 歹三( 4 9 ) 一叫j 0 ，j u 一屿s 珊w i ，j f 令钓= 一霹，j j ，可得与( 4 9 ) 等价的形式 r a i n c 弼 s t j a i d x 3 堍， i b os 勘屿，j l 一w j z j 屿， j u 雩一哟巧砖+ 哟，f ( 41 0 ) ( 4 9 ) 与( 4 l 1 0 ) 都是逆线性规划问题( 4 6 ) 的对偶，从形式上看( 4 1 0 ) 更类似于原l 尸问 题( 4 1 ) ，可以看作是原何题的个松弛由于这两种形式等价，虽然它们具有不同的初 始最优解，但用于确定最优费用向量p 的最优对偶解丌却是相同的为此把( 4 9 ) 称为以o 为中心的对偶逆问题，而把( 4 1 0 ) 称为以护为中心的对偶逆问题这样我