6307877469

A

AGH

WYZNACZANIE ROZWIĄZAŃ OPTYMALNYCH

METODA POTENCJAŁÓW

4.    Sprawdzić ,czy C°>0. Jeśli warunek jest spełniony to uzyskaliśmy rozwiązanie optymalne, jeśli nie to szukamy dalej.

5.    Ustalić indeksy (k,l) nowej zmiennej bazowej x_kt przy wykorzystaniu kryterium wejścia według formuły:

c°_kl = min{ Ą : Ą < 0}

6. Wyznaczyć cykl Ł(k,l) oraz podzbiory Łn(k,l) i Łp(k,l) - łuki, cykl, po dołączeniu nowego wierzchołka (bazowego)

CYKL TO TAKI ZBIÓR WĘZŁÓW, DLA KTÓREGO W KAŻDEJ LINII (WIERSZU LUB KOLUMNIE) ZNAJDUJĄ SIĘ 0 LUB 2 WĘZŁY TEGO ZBIORU.

Ł(k,l) to graf tworzący cykl w rozwiązaniu bazowym przez dołączenie wierzchołka (k,l). Chcąc wyodrębnić wierzchołki parzyste i nieparzyste w grafie oznacza się je indeksami n i p.