2999072768

Dwie bazy B i B nazywamy bazami sąsiednimi, jeżeli różnią się tylko jedną kolumną macierzy A, a rozwiązanie bazowe będziemy nazywali rozwiązaniem sąsiednim, jeśli będzie różnić się tylko jedną zmienną bazową.

2.4.2. Algorytm simpleks

Metoda simpleks polega na iteracyjnym rozpatrywaniu ciągu sąsiednich rozwiązań bazowych. Doboru bazy sąsiedniej dokonujemy w taki sposób, aby otrzymane nowe rozwiązanie bazowe nie było gorsze od rozwiązania poprzedniego. Poszukiwań tych dokonuje się poprzez wielokrotne wykorzystanie tablicy simpleksowej, będącej pewną modyfikacją zapisu macierzowego [2.32].

Tab. 2.2. Schemat pierwszej tablicy simpleksowej.

		^ci
^XB	^CB	A I	b
	Zj	wiersz zerowy	wartość FC
	c, - Zj	wiersz kryterium simpleks (wskaźnik optymalności)

Centralną część tej tablicy zajmuje macierz współczynników zmiennych decyzyjnych, występujących w warunkach ograniczających A wraz z jej podmacierzą jednostkową I, utworzoną przez te współczynniki stojące przy zmiennych bazowych. Jak można zauważyć, macierz A w zapisie [2.32] została podzielona na część A - utworzoną przez kolumny zmiennych niebazowych, oraz część I -utworzoną przez kolumny zmiennych bazowych. Pierwszy wiersz zajmuje wektor współczynników funkcji celu Cj. Dwie pierwsze kolumny z lewej strony macierzy współczynników przeznaczone są na wykaz zmiennych aktualnie tworzących bazę oraz ich współczynniki występujące w funkcji celu. Ostatnią kolumnę zajmuje wektor wyrazów wolnych b - jako wektor kolumnowy prawych stron warunków ograniczających.

Tab. 2.3. Schemat obliczeń tablicy simpleksowej w i-tej iteracji z wykorzystaniem rachunku macierzowego.    _

		^c)
4	^CB	b;'A b;^1	b;^1 • b
	Zj	c'b ■ B]^1 • A c'B - B:^1	c'B • Bj^1 • b
	Cj - Zj	Cj - c'B • B;^1 • A Cj -c'B • Bj^1

Po sprawdzeniu otrzymanego rozwiązania pod względem jego dopuszczalności i optymalności, przechodzimy do bazy sąsiedniej w następnej iteracji i wypełniamy tablice simpleksową według schematu zawartego w tab. 2.3. W tablicy tej pokazano

18