img297

Reasumując raz jeszcze: optymalne rozwiązanie zadania to

	x2		600'
*b =	*5	=	300
	*1-		200

czyli x\ = 200, x₂ = 600,    x'₂) = 18000. Wartość zmiennej x\ = 300 ozna

cza, iż przy takim rozwiązaniu zostaje nie wykorzystany zasób surowca S₂ w ilości 300 kg.

Przykład 9. Rozwiążemy obecnie program dualny do zadania z przykładu 8. Program dualny ma postać:

lOOOyj + 2400}’₂ + 600}>₃ -> min, i + 3y₂ + l,5y₃ ^ 30,

Ji + 3y₂    ^20,

71^2^3^°-

Ponieważ w układzie warunków ograniczających występują nierówności „ > ”, aby je sprowadzić do postaci liniowej, należy od lewych stron nierówności odjąć zmienne swobodne y₄ i y₅ i dodać zmienne sztuczne (opowiednio s₂ i s^)¹. Zauważmy jeszcze, że = —y₄, a s₂ — —y₅. Postać kanoniczna programu dualnego jest zatem następująca:

lOOOyj + 2400}'₂ + 600}’₃ + 0y₄ + 0y₅ + Ms_l -I- Ms₂-» min,

2y_t + 3y₂ + l,5y₃ - y₄ +    = 30,

y_x + 3y₂    -y_s    +s₂ = 20.

Pierwsza tablica simpleksowa ma postać tabl. 43.

Jak widać, największym ujemnym kryterium simpleks charakteryzuje się zmienna y₂, ona zatem wejdzie do bazy w kolejnej iteracji, w miejsce zmiennej

Tablica 43

	^ci	1000	2400	600	0	0	M	M	Rozwiązanie
	Zmienne bazowe	yi	y%	y 3	y*	y5	■Tl
M		2	3	1,5	-i	0	1	0	30
M	■*2	1	3	0	0	-i	0	1	20
	^zi	3 M	6M	l,5Af	— M	— M	M	M	50M
	^cj~^zj	1000 - 3A/	2400-6M	600-1, 5M	M	M	0	0

¹ Jeżeli w modelu występują warunki równościowe, do nich również wprowadzamy zmienną sztuczną, która wchodzi do pierwszej bazy, ale jak wiadomo, nie może znaleźć się w rozwiązaniu optymalnym.

V, (min{30:3; 20:3} = 20/3, co odpowiada zmiennej .v₂). W rezultacie tablica simpleks dla II iteracji przybierze postać tabl. 44.

Tablica 44

	^CJ	1000	2400	600	0	0	M	M	Rozwiązanie
	Zmienne bazowe	Ti	Tz	y3	y4	ys	•Sl	*2
M	*i	1	0	1,5	-t	i	1	-1	10
•M00	yi	1/3	1	0	0	-1/3	0	1/3	20/3
	^zi	800 + M	2400	1,5M	— M	8 oo 1	M	Si 1 8 oo	16000+ 10M
	^ci~^zi	200-M	0	5 lo 1 8	M	800 -M	0	— 800 + M

()becnie największy spadek wartości funkcji celu można uzyskać wprowadzając do kolejnej bazy zmienną y₃ w miejsce ^ (10/1,5 = 20/3; 20/3 :()->■ oo). Tablica simpleks dla trzeciej iteracji ma postać tabl. 45.

Tablica 45

c*	^CJ	1000	2400	600	0	0	M	M	Rozwiązanie
	Zmienne bazowe	Ti	y 2	Ts	T4	Ts		s2
600	y 3	2/3	0	1	-2/3	2/3	2/3	-2/3	20/3
2400	y 2	1/3	i	0	0	-1/3	0	1/3	20/3
	^z)	1200	2400	600	-400	-400	400	400	20000
	^cj~^zj	-200	0	0	400	400	8 ■*3- 1 §	A/—400

Rozwiązanie nadal nie jest optymalne, ponieważ w wierszu zerowym występuje jeszcze element ujemny, co oznacza, że wartość funkcji celu można zmniejszyć wprowadzając do kolejnej bazy zmienną y_t¹. Ponieważ min{20/3:2/3; 20/3:1/3} = 10, co odpowiada wierszowi y₃, zatem w kolejnej tablicy (tabl. 46) zmiennymi bazowymi są y₁ i y₂.

Tablica 46

cb	^CJ	1000	2400	600	0	0	M	M	Rozwiązanie
	Zmienne bazowe	Ti	Tz	T 3	T4	Ts	■Sl	^S2
1000	Ti	1	0	1,5	-1	1	1	-i	10
2400	Tz	0	1	-0,5	1/3	-2/3	-1/3	2/3	10/3
	^zi	1000	2400	300	-200	-600	200	600	18000
	^ci~^zi	0	0	300	200	600	— 200 +A/	— 600 + M

51

1

Zauważmy, że M -» oo, zatem M — 400 « co i zmienne sztuczne nie mogą wejść do kolejnych rozwiązań bazowych.