034 035 2

34 Programowanie liniowe

Pierwszy warunek ograniczający:

2x, + 2x₂+x₃ = 14.

Ponieważ x, = 1 oraz x₂ = 0, po dokonaniu podstawienia otrzymujemy:

2+x₃ = 14,

a stąd = 12. Widzimy, że wartość zmiennej bazowej x₃ zmniejszyła się o 2 jednostki — z 14 do 12. Jeżeli będziemy wprowadzali do rozwiązania coraz większe wartości zmiennej x_H będzie się to odbywało kosztem zmiennej bazowej x₃. Zauważmy przy tym, że każdej dodanej jednostce zmiennej x₁ odpowiada spadek wartości zmiennej bazowej x₃ o 2 jednostki i zmiana ta zapisana jest wartością współczynnika a_n, znajdującego się w rozważanym przez nas pierwszym warunku Ograniczającym przy wprowadzanej zmiennej x,. W rozpatrywanym przypadku wartość ta jest równa 2.

Drugi warunek ograniczający:

x, + 2x₂+x₄= 8.

Ponieważ wciąż mamy x₂ = 0, po podstawieniu tych wartości otrzymujemy:

1 + x₄ = 8,

a stąd x₄ = 7. Zauważmy, że każdej dodanej jednostce zmiennej x, odpowiada spadek wartości zmiennej bazowej x₄ i zmiana ta zapisana jest wartością współczynnika a₂i = I-

Trzeci warunek ograniczający:

4x, +x_s = 16.

Widzimy, że wzrostowi wartości zmiennej x, o jednostkę towarzyszy spadek wartości zmiennej bazowej x₅ o 4 jednostki, czyli o wartość współczynnika a_3i.

Analogiczne rozważania możemy przeprowadzić dla drugiej zmiennej nieba-zowej x₂, podnosząc jej wartość do poziomu x₂ = 1 (zmienna x, przyjmuje wówczas wartość 0).

Zastanówmy się teraz, w jaki sposób zmieni się wartość funkcji celu, która w rozwiązaniu początkowym była równa 0. Z jednej strony spodziewamy się wzrostu tej wartości związanego z tym, że współczynnik funkcji celu C|=2. Ponieważ mamy x, = 1, więc wzrost ten wynosi:

t'i -x, = 2- 1=2.

Z drugiej strony możliwy jest spadek wartości funkcji celu związany z obniżeniem dotychczasowych wartości przez zmienne bazowe. Z pierwszym warunkiem ograniczającym związana jest wartość:

c₃ -a_n = 0- 2 = 0.

Podobnie dla warunków drugiego i trzeciego otrzymujemy odpowiednio:

c_A-a₂\=0- 1 =0 oraz

c₅-flti = 0-4 = 0.

Dodając uzyskane wyniki, uzyskujemy łączny spadek z, wartości funkcji celu, związany z obniżeniem dotychczasowych wartości przez zmiene bazowe, obliczony następująco:

Z, = 0 • 2 + 0 • I +0-4 = 0.

Zauważmy jednocześnie, że zmianę tg, oznaczoną dla rozpatrywanej aktualnie zmiennej symbolem z_Jy obliczyliśmy jako iloczyn skalarny. dwóch wektorów będących kolumnami tablicy simpleksowej: wektora c„ oraz kolumny macierzy współczynników odpowiadających zmiennej Xj,..którejwartość zwiększamy.

W taki sam sposób obliczamy zmiany wartości funkcji celu spowodowane zmianami wartości zmiennych bazowych przy wprowadzeniu do rozwiązania drugiej występującej w zadaniu zmiennej niebazowej x₂=\ (pamiętamy, że wówczas x, pozostaje zmienną niebazową, czyli x, = 0). Obliczając w podany powyżej sposób wartości Z, dla zmiennych bazowych, stwierdzamy, że są one równe zeru.

Różnica c, - z,! określa zmiany netto w wartości funkcji celu, jeżeli jedna jednostka Xj zostanie wprowadzona do rozpatrywanego aktualnie rozwiązania bazowego. Wartości fj-Zj nazywamy wskaźnikami optymalności. Dopisujemy je jako ostatni wiersz tablicy simpleksowej. Ostatnim elementem w tym wierszu jest wartość funkcji celu odpowiadająca rozpatrywanemu rozwiązaniu. Otrzymujemy tablicę 1.3:    •' }-■'    !

-u -T'    \ o»

O

o ■yf-'

Tablica 1.3

* j - -    ‘t &

(Aa

C

cx —	max	2 CĄ	3 = ^	0	0 U.	0’
Baza	C»		x2		*4	*5
A?	0	2,	2	i	0	0	14
X*	0	1	2	0	^s 1	0	8
	0	4	0	0	0	1	16
H * o-	-- .	2	3	0	0	0	0

Wartości wskaźników optymalności dla zmiennych x, i x₂ są dodatnie, co oznacza, że jeżeli wprowadzimy którąkolwiek z tych zmiennych do bazy, to wartość funkcji celu będzie wzrastać. Tak więc rozpatrywane przez nas pierwsze rozwiązanie bazowe nie jest optymalne i można je poprawić. Dotychczasowe rozwiązania pozwalają nam więc sformułować wniosek, który stanowi kryterium optymalności dla zadania maksymalizacji.