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

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

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

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