1、在我們的日常生活中，網(wǎng)絡(luò)無處不在，它們以各種各樣應(yīng)用為背景的形式出現(xiàn)。通常，當(dāng)網(wǎng)絡(luò)中所有的參數(shù)，如點的容量和弧的容量都是常數(shù)，也不考慮流在運(yùn)輸過程中所需的時間，這樣的網(wǎng)絡(luò)就被看作靜態(tài)的。但是這些假設(shè)在現(xiàn)實生活中未必成立。例如，一支艦隊，從一個港口出發(fā)到達(dá)另一個港口，途中所需時間是需要考慮的，還有航道的容量和泊位的數(shù)量也都可能隨著時間的變化。若一個網(wǎng)絡(luò)的參數(shù)會隨著時間而變化，則稱這樣的網(wǎng)絡(luò)為時變網(wǎng)絡(luò)。與靜態(tài)網(wǎng)絡(luò)相反，目前只有少數(shù)幾種解決時

2、變網(wǎng)絡(luò)最優(yōu)化問題的方法。 文中考慮了時變網(wǎng)絡(luò)的最大流問題。G(N,A,b,l)表示一個時變網(wǎng)絡(luò)，N是點集，A是弧集，b(i,j,t)是流經(jīng)弧(i,j)((i,j,)∈A)所需的傳輸時間，l(i,j,t)是弧(i,j)的容量。b(i,j,t)和l(i,j,t)都是弧(i,j)第一個點上流的出發(fā)時間t的函數(shù)，t=0,1，2，...,T, T(T >0)是一個給定的數(shù)。時變網(wǎng)絡(luò)最優(yōu)化問題就是在時間限制T內(nèi)，從發(fā)點送盡可能多的流到達(dá)收點

3、，這個問題已被證明是NP-完備問題。 本文的結(jié)構(gòu)如下：1.基于偽流我們提出一個解決時變最大流問題的算法，剩余容量收縮算法。2.給出時間標(biāo)號算法，使得所求最大流的每個子流到達(dá)終點的時間都是最早(或最晚)的。用同樣的算法解決了最短間隔路問題，即所求解中每個子流出發(fā)時間和到達(dá)時間之間的間隔是最短的。3.考慮了兩種等待條件，它們分別是零等待時間和任意等待時間，證明算法正確性的同時也列舉算例闡明算法如何進(jìn)行運(yùn)算，每一種算法都能在偽多項式時