時變最短路問題及其在時變最小費用流中的應(yīng)用.pdf

1、網(wǎng)絡(luò)優(yōu)化研究的是網(wǎng)絡(luò)上的優(yōu)化問題。它在許多重要領(lǐng)域都有廣泛的應(yīng)用，例如，交通，通信，計算機網(wǎng)絡(luò)，能源系統(tǒng)等。大量文獻中研究的網(wǎng)絡(luò)優(yōu)化問題都是靜態(tài)的，即流經(jīng)過一條弧不需要花費任何時間，并且網(wǎng)絡(luò)的參數(shù)，例如，流經(jīng)過一條弧的費用，弧的容量都是不隨時間變化的。然而，現(xiàn)實生活中的網(wǎng)絡(luò)本質(zhì)上是時變的。在這種網(wǎng)絡(luò)上，流經(jīng)過一條弧需要花費一定的時間，網(wǎng)絡(luò)的參數(shù)(例如，弧和頂點容量)是隨時間而變化的。 本文詳細地研究了時變網(wǎng)絡(luò)上的兩個優(yōu)化問題。一

2、個是時變最短路問題，即在總的傳送時間小于給定的常數(shù)T下，找出從源點到其他所有點的最短路。本文研究了該問題的三種不同情形。第一種情形，假設(shè)流在除了源點外的其他任何頂點都不能等待。第二種情形，假設(shè)流在任何點都能無限制地等待。最后，考慮一般情形，假設(shè)流在每個頂點的等待時間有一個上界。對每一種情形，給出它的原規(guī)劃，并相應(yīng)地寫出其對偶規(guī)劃，提出最短路最優(yōu)性條件。然后，根據(jù)最優(yōu)性條件，設(shè)計出對偶算法，并分析其算法復(fù)雜性。另一個是時變最小費用流問題，

3、即在截止時間T前，確定怎樣從源點送給定數(shù)量的流到收點以致總的費用最小。本文研究了該問題的二種情形。首先，考慮零等待時間，即流在除了源點和收點外的其他任何頂點都不能等待。然后，考慮任意等待時間，即流能在任何頂點無限制的等待。同樣地，對每一種情形，給出它的原規(guī)劃和對偶規(guī)劃，從線性規(guī)劃的互不松弛定理推導出一些最優(yōu)性條件。接下來，利用時變最短路的對偶算法和最優(yōu)性條件，設(shè)計出偽多項式時間算法，并分析了算法復(fù)雜性。 最后，本文用一些數(shù)值的例