DSC00094 (7)

W Badania Operacyjne

METODA SIMPLEKS

Poszukiwanie rozwiązania optymalnego można ograniczyć do badania wierzchołków zbioru rozwiązań dopuszczalnych, czyli bazowych rozwiązań dopuszczalnych.

Metoda simpleks jest metodą iteracyjną. Po znalezieniu początkowego rozwiązania bazowego dopuszczalnego wyznacza następne (sąsiednie ) dopuszczalne rozwiązania bazowe zależne od poprzedniego, polepszające wartość funkcji celu. Przez sąsiednie rozwiązanie bazowe przyjmuje się rozwiązanie różniące się od danego tylko jedną zmienną bazową.

Etapy Algorytmu Simpleks

1.    Wyznaczenie początkowego rozwiązania bazowego

Budowa tablicy simpleksowej - macierzy zagadnienia programowania liniowego o postaci standardowej zawierającej macierz jednostkową.

Z tablicy wyznaczenie pierwszego bazowego rozwiązania dopuszczalnego.

2.    Obliczenie wskaźników optymalności Zj- Cj (J =J,2,.~,ri) odpowiadających aktualnemu rozwiązaniu bazowemu (różnica między iloczynami skalarnymi

wektorów a-, a_}......a. (a, e R”) a odpowiednimi elementami wektora

Ci. c* pi— c.eff)

Śr^P !)<?/<»#-9

Ml

3.    Sprawdzenie, czy aktualne dopuszczalne rozwiązanie bazowe jest rozwiązaniem optymalnym, (czy dla każdego tśj £n. zj- Cj i 0). Jeśli tak to aktualne rozwiązanie bazowe jest optymalne =» koniec postępowania

4.    Sprawdzenie, czy to zadanie ma skończone rozwiązanie optymalne.

Jeżeli Istnieje jlakie, tezj-Cj <0. przy którym a^S Odia wszystkich ieB to zadanie nie ma skończonego rozwiązania optymalnego - funkcja celu jest nieograniczona) ■=> koniec postępowania.

5.    Wprowadzenie nowego wektora do bazy (x»).

Spośród ujemnych elementów wskaźników optymalności Z/ - Cj wybór elementu o najmniejszej wartości Element ten wskazuje wektor & ( k-tą kolumnę macierzy) którą należy wprowadzić do nowego dopuszczalnego rozwiązania bazowego.

z»-c» - min fy-Cj )

6 Usunięcie wektora z bazy (x, ).

Dla kat de go dodatniego elementu wektora Xt wprowadzanego da bazy naleiy obliczyć iloraz: elementu wektora b przez element kolumny xt.

Najmniejszy dodatni iloraz wskazuje wektor x, który naleiy usunąć z bazy.

Element stojący na przecięciu kolumny k i wiersza r nosi nazwę elementu centralnego.

7. Tworzenie nowej tablicy simpleksowej.

Otrzymujemy nową bazą w której wektor bazowy a_r został zastąpiony wektorem Ot.

Elementy tablicy simpleksowej przekształcamy według wzoru:

Wyznaczamy nowe rozwiązanie bazowe. 8. Powrót do etapu drugiego.

Posłać tablicy simpleksowej

			et	et	Cl		c.
ct	Zmienne bazowe	Xb	Xl	Xt	*t	—	X.	SL „
		b	Ol	di	9k	.....	a.
Wit _?gy."	ażniki wlnoSci	z(xb)	Ird	tfCt	tret	i_i —■i	tw<m