8107620627

Po wprowadzeniu dodatkowych zmiennych £3, £4 i £5 oraz pomnożeniu funkcji celu przez —1, otrzymamy problem PL w postaci standardowej (równoważny problemowi (35))

—2x\ — 3x2 —► min

2xj	+2x2 +x3		= 14
Xi	+2x2	+x4	= 8
4xi		+x5	= 16
	Xj > 0,	j e Ni,5.

(44)

Problem ten można zapisać także w postaci (l)-(3), przyjmując

	2 2 10 0		14
A — a2 o3 04 —	12 0 10 4 0 0 0 1	, b =	8 16

*1

X2

*3

Xą

X -

c - [ci c₂ c₃ c₄ c₆] - [-2 -3 0 0 0].

Jest to postać bazowa problemu względem zbioru B = {3,4,5}, Ab = (a₃ a₄ 05) = I. Zatem zmiennymi bazowymi są zmienne dodatkowe x₃,x₄,x₅, natomiast zmienne xj,x₂ przyjmują wartość 0. Mamy więc B = {3,4,5}, B' = {1,2}. Wartości Zj obliczymy ze wzoru Zj = Cghj, j € Njjj. Ponieważ cb = 0, więc Zj = 0 dla j 6 Ni,s i macierz c — z nie jest nieujemna.

Tablica sympleksowa dla początkowego rozwiązania bazowego ma zatem postać tabeli 9.

Tablica 9: Pierwsza tablica sympleksowa

		-2	-3	0	0	0
cB	zmienne bazowe	h\	h2	h3	h4	hs	ho
0	£3	2	2	1	0	0	14
0	£4	1	2	0	1	0	8
0	£5	4	0	0	0	1	16
		0	0	0	0	0	0
	Gj — Zj	-2	-3	0	0	0

Kryterium wejścia: wyznaczamy indeks k 6 B', dla którego c/. — z*, jest najmniejszym wyrazem macierzy c — z. Jest nim c₂ — z₂ = —3. Tak więc k = 2, czyli w drugiej iteracji wprowadzimy zmienną bazową x₂.

Aby ustalić, w miejsce której z dotychczasowych zmiennych bazowych ją wprowadzić, należy podzielić wyrazy macierzy ho przez dodatnie wyrazy macierzy h₂ i wybrać indeks / € B, dla którego ten iloraz jest najmniejszy (kryterium wyjścia). W tym przypadku spośród dwóch (nie należy obliczać gdyż /i₃₂ = 0) ilorazów y i | najmniejszy odpowiada zmiennej x₄. A zatem l = 4, czyli w drugiej iteracji w tablicy sympleksowej zmiennymi bazowymi są x₃,x₂,X5, a B_2j4 = (B\ {4}) U {2} — {3,2,5}. Poszczególne elementy tej tablicy można obliczyć stosując przekształcenia (16)-(20).

Druga tablica sympleksowa ma zatem postać tabeli 10. Macierz c- z wciąż nie jest nieujemna. Z kryterium wejścia: k = 1.

16