8107620638

2.    Jeśli c—z = c—c_BA_B' A > O, to na mocy twierdzenia 4, x[B] jest rozwiązaniem optymalnym

problemu PL (l)-(3).    —>    koniec działania algorytmu!

3.    Jeśli istnieje takie k € B¹, że c* — Zk < 0, to wybieramy k 6 B’, dla którego Ck — Zk jest najmniejszym wyrazem macierzy c — z (kryterium wejścia).

4.    Jeśli h_k < 0 (k wyznaczone przez kryterium z punktu 3), to na mocy twierdzenia 5 funkcja celu problemu PL (l)-(3) jest nieograniczona od dołu i tym samym problem ten nie ma rozwiązania optymalnego.

5.    Jeśli hk posiada wyraz dodatni, to wybieramy l G B, dla którego iloraz wyrazów macierzy h₀ przez dodatnie wyrazy macierzy hk jest najmniejszy ^ (kryterium wyjścia).

6.    Tworzymy zbiór Bk,i — (B\ {/}) U {fc} numerów kolumn nowej macierzy bazowej i wracamy do punktu 1 (początek następnej iteracji).

Postępowanie zwykle (o ile jest to możliwe) zaczynamy od takiej postaci bazowej, w której A_b — I, dzięki czemu wyznaczenie H, h₀, c — z ze wzorów (16)-(19) jest natychmiastowe. Jeśli c—z jest wektorem nieujemnym, to rozwiązaniem optymalnym jest x[B\. W przeciwnym przypadku, istnieje wyraz c_k — z_k, który jest ujemny. Wybór najmniejszego wyrazu macierzy c — z zapewnia największy jednostkowy spadek wartości minimalizowanej funkcji celu x >—> cx. Wyraz Ck — Zk jest bowiem zmianą wartości funkcji celu spowodowaną przez powiększenie wartości Xk o 1 w stosunku do wartości funkcji celu odpowiadającej x[B]. Kryterium z punktu 3 określające macierz ak, która wejdzie do nowej macierzy bazowej (jeśli hk ma wyraz dodatni) nazywamy kryterium wejścia metody sympleks. Kryterium z punktu 5, nazwane kryterium wyjścia metody sympleks określa, która macierz a< zostanie usunięta z macierzy bazowej A_B.

Definicja 10 Bazowe rozwiązanie dopuszczalne x[B] nazywamy niezdegenerowanym, jeśli x[B]j > 0 dla każdego j € B. W przeciwnym przypadku tzn. gdyx[B]j = 0 dla pewnego j € B, rozwiązanie x[B\ nazywamy zdegenerowanym.

Definicja 11 Problem programowania liniowego nazywamy niezdegenerowanym, jeśli każde jego bazowe rozwiązanie dopuszczalne jest niezdegenerowane.

Twierdzenie 6 W niezdegenerowanym problemie programowania liniowego metoda sympleks kończy się w skończonej liczbie iteracji.

Przy rozwiązywaniu problemów PL metodą sympleks możemy stosować bardzo wygodny zapis z wykorzystaniem tablic sympleksowych. Pierwszą tablicę sympleksową można przedstawić jak w tabeli 1, natomiast każdą następną - jak w tabeli 2.

Tablica 1: Zapis macierzowy pierwszej tablicy sympleksowej

		c
CB	x[B]b	A	b
	^Z3	0
	Cj - Zj	c