论文部分内容阅读
本文将动态网络优化问题和逆优化问题相结合,考察动态最小费用路在L1模下的逆问题,其中在弧费用的定义中,将弧(i,j)上的运行时间dij(t)分成最小可能运行时间dij*和超出的运行时间(excesstime)eij(t)两部分,弧(i,j)上费用即为两者赋权之和.本论文的研究和创新工作主要包括以下内容:
(1)介绍离散情形和连续情形下两种基本的动态网络流模型,引入时间扩张图概念,用于将动态网络转化成静态网络,从而提供了一个解决动态网络优化问题的工具.
(2)在弧费用的特定定义下,介绍一个求解最小费用途径问题的较优的伪多项式时间算法.并对该问题的更一般情形给出一个一般算法.
(3)论述了L1模下线性规划的逆问题的求解问题,阐明了线性规划中逆问题的对偶和原问题的松弛之间的关系.
(4)研究动态最小费用路在L1模下的逆问题,通过时间扩张网络GT将动态问题转化为静态问题,再利用解线性规划的逆问题的方法给出该问题的结果,并给出相应算法.