時變網絡最大流問題的新算法.pdf

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

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

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