032 033 2

32 Programowanie liniowe

W rozpatrywanym przez nas zadaniu występuje 5 zmiennych (decyzyjnych i bilansujących) i 3 warunki ograniczające, stąd składowe wektorów i elementy macierzy są następujące:    V

32 Programowanie liniowe

>

i

		~2	2	1	0	o~		~ 1Ą
c=[~2 3 0 0 0]	A =	1	2	0	1	0	, b =	8
		4	0	0	0	1		16

i

i

Widzimy, że wybierając z macierzy A kolumny: trzecią, czwartą i piątą otrzymamy podmacierz jednostkową. Oznacza to, że układ równań odpowiadający warunkom ograniczającym rozpatrywanego przez nas problemu jest w postaci bazowej oraz że zmiennymi bazowymi są: x_}, a₄ i a₅, a zmiennymi niebazowymi

—    pozostałe zmienne. Powiemy wówczas, że rozpatrywane zadanie programowania liniowego jest zadaniem w postaci bazowej, a zmiennymi bazowymi

—    wymienione powyżej zmienne. Ponieważ wszystkie wartości zmiennych bazowych są nieujemne, jest to bazowe rozwiązanie dopuszczalne.

Przyjrzyjmy się rozwiązaniu bazowemu odpowiadającemu tej bazie. Przyjmując dla zmiennych niebazowych a, i x₂ wartości równe zeru, otrzymujemy:

X, =0, X₂- 0, X₃ = 1 4, Aj = 8, Aj = 16.

W rozwiązaniu tym wartość funkcji celu jest równa 0. Na płaszczyźnie rozwiązanie to odpowiada wierzchołkowi 0(0, 0). Ze względu na to, że przyjmując to rozwiązanie, nie uruchamiamy produkcji (mamy a, =0, a₂ = 0), zmienne bilansujące, określające niewykorzystane zasoby środków S,, S₂ i .S\, równe są wielkościom zasobów tych środków.

W dalszych rozważaniach wykorzystamy wielokrotnie tablicę simpleksową, będącą pewną modyfikacją postaci macierzowej zadania. W pierwszym wierszu tej tablicy zamieszczamy współczynniki funkcji celu, w drugim — nazwy zmiennych. Trzonem tablicy jest macierz współczynników A oraz wektor wyrazów wolnych b. Dwie dodatkowe kolumny zamieszczone w lewej części tablicy to wykaz zmiennych bazowych oraz wektor wartości współczynników funkcji celu odpowiadających zmiennym bazowym, oznaczony jako c,,.

Przykładową tablicę simpleksową odpowiadającą bazie, w której zmiennymi bazowymi są a,, a₄ i a₅, przedstawiono jako tablicę 1.2.

Z tablicy 1.2 łatwo odczytać wartość funkcji celu odpowiadającą rozwiązaniu bazowemu, w którym zmiennymi bazowymi są a₃, a., i a₅. Posłużymy się kolumną drugą zawierającą składowe wektora c_B oraz kolumną ósmą (ostatnią), w której

Metoda simpleks Tablica 1-2

cx —*	max	2	3	0	0 Z-	0	h
Baza	^c»	*\	X}	Xy	x*	Xs
*>(	0	2	2	i	&	0	t4
x, [£■	0	t	2	0	1	0-	8
. 4	0 i	4	0	0	a	1 »	16

ly)pj^0 < tćOS ^C/

o .t-y y i    toS u

»' 0» • i ■'.’/■^;

iOOMz

?U-< -

i ( ;

C+,i

31

! • O I •

ce-tu

znajdują się wartości zmiennych bazowych w rozpatrywanym rozwiązaniu bazowym. Mnożąc skalarnie te kolumny, otrzymujemy:

0-14+0-8 + 0-16 = 0,

czyli wartość funkcji celu odpowiadająca pierwszemu rozwiązaniu bazowemu jest równa zeru.

1.3.2. Badanie optymalności rozwiązania

Metoda simpleks polega na rozpatrzeniu ciągu sąsiednich rozwiązań bazowych. czyli takich rozwiązań bazowych, w których dwie kolejno rozpatrywane bazy różnią się między sobą dokładnie jedną zmienną. Doboru bazy sąsiedniej dokonujemy w taki sposób, aby zagwarantować otrzymywanie coraz lepszych, a przynajmniej nie gorszych wartości funkcji celu. Przejście od jednej postaci bazowej do następnej odbywa się przy wykorzystaniu przekształceń elementarnych układu warunków ograniczających w postaci standardowej.

Aby wykonać jeden krok (nazywany dalej iteracją) algorytmu metody simpleks, należy:

•    stwierdzić, czy rozpatrywane rozwiązanie bazowe jest optymalne, czy też nie,

+ w przypadku gdy nie jest optymalne, wyznaczyć nową bazę sąsiednią;

•    przekształcić za pomocą przekształceń elementarnych macierz warunków ograniczających do postaci bazowej względem bazy sąsiedniej:

Opiszemy dalej szczegółowo kolejne kroki postępowania:

Iteracja 1:

Zbadamy, jaki wpływ na dotychczasowe rozwiązanie (w którym zmienne bazowe to x$, x₄ i x₅, a niebazowe to x_x i x₂) miałoby przyjęcie przez jedną ze zmiennych niebazowych, np.. zmienną jc„. wartości równej 1; (druga zmienna niebazowa, czyli x_2r przyjmuje cały czas wartość 0). Zajmiemy się kolejnymi ograniczeniami.