084 085 2

84 Programowanie liniowe

simpleks. Zmienną opuszczającą bazę jest x₂. Otrzymujemy wówczas (tablica 1.36):

Tablica 1.36

c(/)x —» max		2 + 3/	3-/	0	0	0
Baza	CB	-n	^X2	*3	x4	X5
X.\	0	0	2	1	0	-0,5	6
X,	0	0	2	0	1	-0,25	4
r,	2 + 3/	1	0	0	0	0.25	4
^cr	-Z;	0	3-/	0	0	-0,5-0,75/	8+12/

Zbadamy, dla jakich wartości t to nowe rozwiązanie pozostanie rozwiązaniem optymalnym. Ponownie rozwiążemy układ nierówności liniowych, wyznaczony przez wartości współczynników optymalności dla zmiennych niebazowych. Otrzymujemy:

3-fsSO,

- 0,5-0,75/<0.

Układ ten jest spełniony dla każdej wartości / takiej, żc z ^ 3.

Powróćmy teraz do wyjściowej wartości /„ = 0. Wiemy już, że rozwiązanie optymalne odpowiadające tej wartości t pozostanie optymalne dla -0,143 ^ f <3. Podstawiając za / wartość -0,143, otrzymujemy następującą tablicę simpleksową (tablica 1.37):

Tablica 1.37

cx —»	max	1,5712	3,143	0	0	0	b
Baza	C„	JC,	■*2	•Ti	Xą	*5
Jf.ł	0	0	0	1	-I	-0,25	2
*2	3,143	0	1	0	0,5	-0,125	2
X,	1,571	1	0	0	0	0,25	4
^CJ~		0	0	0	-1,571	0	12,57

Ponieważ wartość współczynnika optymalności zmiennej niebazowej jc₅ jest równa 0, więc istnieje optymalne alternatywne rozwiązanie bazowe. Wykonamy ponownie jeden krok prymalnej metody simpleks. Zmienną wchodzącą do bazy jest x₅, zmienną opuszczającą bazę jest x,. Otrzymujemy następującą tablicę simpleksową (tablica 1.38):

Tablica 1.38

C(f)x	-» max	2 + 31	3 — 1	0	0	0	i)
Ba?.a	C«	«*l	x2	X,	Xą
	0	1	0	1	-1	0	6
x2	3-t	0,5	1	0	0,5	0	4
X*	0	4	0	0	0	1	16
^CJ-	-Zr	0,5 + 3,5/	0	0	-1,5+ 0,5/	0	12-4/

oraz rozwiązanie bazowe: jc,=0, x₂ = 4. jc₃ = 6, x₄ = 0, x₅ = 16. Rozwiązanie to pozostaje rozwiązaniem optymalnym wówczas, gdy spełniony jest układ nierówności:

0,5 + 3,5r<0,

-1,5 + 0,5r < 0.

Układ ten jest spełniony dla każdej wartości t <-0,143.

Reasumując, podamy rozwiązanie optymalne w zależności od wartości parametru i:

(I)    Dla r<-0,143 mamy:

x, = 0, x₂ = 4, x₃ = 6, x₄ = 0, x_s= 16.

(II)    Dla / = — 0.143 rozwiązaniami są punkty leżące na odcinku między rozwiązaniami (I) a (III).

(III)    Dla -0,0143 </<3 mamy:

x, = 4, x₂ - 2, x₂ = 2, x₄ = 0, jc₅ = 0.

(IV)    Dla t-3 rozwiązaniami są punkty leżące na odcinku między rozwiązaniami (111) a (V).

(V)    Dla 3 mamy:

x,=4, x₂ = 0, jc₃ = 6, x₄ = 4, x₅ = 0.

Rozwiązanie zadania możemy zilustrować graficznie. Ponieważ sparamet-ryzowana została jedynie funkcja celu, zbiór rozwiązań dopuszczalnych pozostaje bez zmian. Dla początkowej wartości parametru r₀ = 0 funkcja celu ma postać:

/i(z,, x₂) = 2x_l+3x₂,

a rozwiązaniem optymalnym jest wierzchołek B (rys. 1.20). Dla wartości parametru t-3 funkcja celu ma postać: /->(•*!> x₂)= lLc,.