6307877468

AGH

WYZNACZANIE ROZWIĄZAŃ OPTYMALNYCH METODA POTENCJAŁÓW

W tym algorytmie wykorzystujemy rozwiązanie wstępne wyznaczone jedną z dwóch poprzednich metod. Postać algorytmu jest następująca:

1.    Wyznaczenie rozwiązania bazowego wstępnego dla zadania zbilansowanego (wg. Jednej z poprzednio przedstawionych metod)

2.    Rozwiązanie układu równań:

c_tj + «j + vj — 0 {i,j) e B

u, + Vj , są niewiadomymi układu równań (tzw. potencjały) o indeksach odpowiadających dotychczasowym wierzchołkom grafu rozwiązań,

B - zbiór par (i,j) takich, że xij jest zmienną bazową.

Powyższy układ równań jest układem nieoznaczonym, gdyż składa się z m+n-1 równań i m+n niewiadomych. Aby rozwiązać układ należy przyjąć w jednym z równań dowolną wartość dla jednej z niewiadomych.

3.    Wyznaczenie tzw. równoważną macierz zerową C° > 0 rozwiązania bazowego,

której elementy wynoszą:    c°j = c_tj +u_t + v_}