img296 (8)

Tablica 41. III tablica simpleksowa

Tablica 41. III tablica simpleksowa

	^ci	30	20	0	0	0	Rozwiązanie
	Zmienne bazowe	*i	*2	*3	*4	*5
20	*2	0	1	1	0	-4/3	200
0	x4	0	0	-3	1	2	600
30	X1	1	0	0	0	2/3	400
	^zi	30	20	20	0	-20/3	16000
	Cj-Zj	0	0	-20	0	20/3

Rozwiązanie nadal nie jest optymalne, ponieważ w wierszu zerowym występuje jeszcze element dodatni. Wprowadzając zatem zmienną *₅ (c₅ — z₅ = 20/3 >0) do kolejnej bazy, zwiększymy jeszcze wartość funkcji celu. W kolejnej IY iteracji do bazy weszła zmienna x₅ w miejsce x₄ [min{600:2; 400:2/3} = 300, co odpowiada wierszowi x₄]. IV tablicę simpleksową (tabl. 42) przedstawiono poniżej. W jej wierszu zerowym nie występują już liczby dodatnie, a więc rozwiązanie jest optymalne.

Tablica 42. IV (ostatnia) tablica simpleksowa

Cb	^CJ	30	20	0	0	0	Rozwiązanie
	Zmienne bazowe		*2	*3	*4	*5
20	*2	0	1	-1	2/3	0	600
0	*5	0	0	-1,5	0,5	1	300
30		1	0	1	-1/3	0	200
	^ZJ	30	20	10	10/3	0	18000
	Cj-Zj	0	0	-10	-10/3	0

W rozwiązaniu (ostatnia kolumna każdej tablicy) pod wartościami zmiennych bazowych podana jest wartość funkcji celu w danej iteracji. W analizowanym przykładzie w kolejnych iteracjach wartość funkcji celu wzrastała od zera w I iteracji do 18000 w ostatniej. Zauważmy, iż rozwiązania bazowe w kolejnych iteracjach odpowiadają poszczególnym wierzchołkom zbioru rozwiązań dopuszczalnych (rys. 8): wierzchołkowi O (w iteracji I), A (w iteracji II), D (w iteracji III) i C (w iteracji IV).

Poniżej obliczono raz jeszcze elementy tablicy IV, posługując się rachunkiem macierzowym. Ponieważ zmienne bazowe w ostatniej iteracji (a tym

, a macierze

samym w rozwiązaniu zadania), to x₂, x_s i x_L, zatem x_b = B i fi^-1 mają postać (wyznacznik macierzy B jest równy 3):

B =

x2	xs a:,
1	0 2
3	0 3
0	1 1,5
A więc
	-1

B~¹ = —

B-'A =

1,5

1

2

I

0,5

1

" 3

-3

2

0

-4,5

1,5

3

2
-1 - 0
3
-1,5 0,5 1	*-<
i o
3	i

elementy kolumn odpowiadających zmiennym swobodnym

1,5 0

0 1 0 0 1 0

f elementy kolumn odpowiadają-< cych zmiennym decyzyjnym l (bazowym).

	-i	2 I	0	1000"		-1000+1600+0 '		600"
to i Cr II	-1,5	0,5	1	2400	=	-1500+1200+600	=	300
	1	1 ~~3	0	600_		1000 - 800 +0		200_

wartośd

zmiennych

bazowych,

[0 1'

120]

a zatem

c^Br^lA = [20 0 30]

0 0

1 o

= [30 20]

elementy wiersza Zj dla zmiennych decyzyjnych,

-i i

3

0

e{ B~^l = [20 0 30]

1,5    0,5    1

1

ł»

-pof ^0]

elementy wiersza Zj dla zmiennych swobodnych,

c - dB~^lA = [30 20] - [30 20] = [0 0], -c^TbB^ = [-10 y 0]

elementy

wiersza

„zerowe-

go.

clB ^lb = [20 0 30]

600'

300

200

= 12000 + 0 + 6000 = 18000

wartość funkcji celu.

49