8107620636

Należy jeszcze wykazać, że drugi z nich jest problemem w postaci bazowej. Bez zmniejszenia ogólności rozważań przyjmijmy, że B = Ni,_m. Z (16) mamy

H=[H„ H_b,]=A_b' [a_b Ab,\,

a stąd	H a = AB^l Ab = I.	(22)
Ponadto z (17) i (11) mamy	h0 = A~B^lb > 0.	(23)
Natomiast z (18) i (19) mamy	d = c — z — c— cbH.	(24)
czyli \dB de-] = [cb cb']	— cB [Hs iTs'] = [cb — cbHb cB' — cbHij'] .	(25)
Z (25) i (22) otrzymujemy dB	= cB — cbHb = cB — cB I = 0.	(26)

Warunki (22), (23) i (26) oznaczają, że problem (14)-(15) określony przez (16)-(19) jest problemem w postaci bazowej, co kończy dowód. ■

Z (16) wynika, że

A_BH = A, czyli Au [/&i ... h_nj = [ai ... o„] ,

gdzie

aj := A,j i hj := H,j dla j € Ni_>n, a więc aj = A_Bhj, j € Ni,„.

Wniosek 3 Liczba zq określona wzorem (20) jest wartością funkcji celu (1) odpowiadającą bazowemu rozwiązaniu dopuszczalnemu względem macierzy bazowej A_B.

Stosowanie metody sympleks polega na kolejnym przekształcaniu problemu PL (l)-(3) do odpowiednich postaci bazowych.

Załóżmy, że zadany jest problem PL (l)-(3) oraz zbiór B C N_1>n jest dowolnie ustalonym zbiorem takim, że A_B jest macierzą bazową dopuszczalaną. Z dowodu twierdzenia 3 wynika, że macierze H, ho i d określone wzorami (16)-(19), wyznaczają problem PL w postaci bazowej względem zbioru B równoważny problemowi PL (l)-(3).

Istotną rolę odgrywają elementy dj — Cj — Zj, j € B' macierzy d — c — z (cj c(l,j), dj := d(l,j), Zj z(l,j) dla j 6 Ni_>n). Elementy te pozwalają stwierdzić, czy bazowe rozwiązanie dopuszczalne x[B\ względem macierzy bazowej A_B jest rozwiązaniem optymalnym i dlatego nazywamy je wskaźnikami optymalności. Wynika to z następującego twierdzenia.

Twierdzenie 4 Jeżeli c — z > 0, to x[B] jest rozwiązaniem optymalnym problemu PL (l)-(3).

Dowód. Dla każdego * € V mamy x > 0. Ponadto z założeń twierdzenia wiemy, że c — z > 0. Zatem dla każdego x € V mamy

(c - z)x > 0.    (27)

6