8107620635

2 Postać bazowa problemu programowania liniowego

Definicja 9 Mówimy, że problem (l)-(3) jest problemem w postaci bazowej względem m-elementowego zbioru B C Nj_in, jeśli:

(i)    macierz A_B jest macierzą jednostkową z dokładnością do kolejności wierszy;

(ii)    b > 0;

(iii)    Cj = 0 dla każdego j G B.

Twierdzenie 3 Dla niesprzecznego problemu PL (l)-(3) istnieje równoważny mu problem PL w postaci bazowej względem ustalonego zbioru B, tzn. oba problemy mają ten sam zbiór rozwiązań dopuszczalnych i optymalnych.

Dowód. Wykażemy, że dla dowolnej macierzy bazowej dopuszczalnej Ab istnieje problem PL w postaci bazowej względem zbioru B równoważny problemowi (l)-(3). Niech Ab będzie macierzą bazową dopuszczalną, a więc istnieje macierz odwrotna A~_B^l. Z wniosku 2 mamy

	AB^lb> 0.	(11)
Rozpatrzmy funkcję celu określoną w (1) na zbiorze V danym przez (4). Dla każdego igD zachodzi
Ax = b. Stąd	AB Ax = ABb,	(12)
co daje —cbAb^1Ax + cBAB	6 = 0. Wówczas
cx	= cx — cbAb^1Ax + CBAB^lb , xe~D	(13)
Zauważmy, że cgAg b jest w	elkością stałą.
Rozpatrzmy teraz problem	zminimalizowania funkcjonału
	Mn ł 3 x •-» dx	(14)
przy warunkach	Hx — ho oraz x > 0,	(15)
w którym	H :=Ab'A.	(16)
	ho :—ABb.	(17)
	d —c — z,	(18)
gdzie	z := cbAb^1A = cbH e Mi,„.	(19)
Oznaczmy	z0 := cBAB^lb = cBh0-	(20)
Na mocy (12) warunki ograniczające (2) i (15) są równoważne. Z (13) i z		(18)-(20) otrzymujemy
	CX = (c - z)x + Zo = dx + Zo,	(21)

gdzie Zq jest wielkością stałą. Zatem minimalizacja funkcji celu * »-» cx określonej w (1) jest równoważna minimalizacji funkcji x i—► dx określonej w (14). Zatem problemy (l)-(3) i (14)-(15) są równoważne.

5