8107620634

Definicja 6 Wielościennym zbiorem wypukłym nazywamy zbiór M. C X będący przecięciem skończonej liczby półprzestrzeni domkniętych: P%j..... P%™, gdzie bi € K, a,- € Mi,_n, i € Ni,_TOi czyli

M=f)PZ; = {xeX: cnx < bi}.    (7)

Definicja 7 Rozwiązaniem dopuszczalnym równania

(8)

Ax = b z niewiadomą x € M_nil

nazywamy każdą macierz x € M_n<1 spełniającą warunki Ax = b i x > 0.

Definicja 8 Rozwiązanie dopuszczalne x nazywamy bazowym rozwiązaniem dopuszczalnym względem macierzy bazowej Ab, jeśli Xj = 0 dla każdego j G B'.

(9)

^x[B]j =

Twierdzenie 1 Dla każdej macierzy bazowej Ab istnieje dokładnie jedno rozwiązanie bazowe A~_B'b J6 B

,3 e b:

. Wtedy B¹ = N_hn\B =

Dowód. Bez zmniejszenia ogólności rozważań, przyjmijmy, że B = F ^TO+i,n- Przyjmijmy następujący zapis

^alm °lm+l O-nim ^amm+l

Z warunku Ax = b mamy więc

\A_bA_B'] ^33/5 =b. czyli A_Bx_B + A_B'X_B' = b. I    J \Xb'\

Ponieważ macierz Ab jest nieosobliwa więc istnieje macierz odwrotna -Ag¹. Wówczas x_B = Ajj^l(b - Ab'X_B')-

Przyjmując x_B> = 0, otrzymujemy

x_B — Ag b.

(10)

a stąd,

r

jest jedynym bazowym rozwiązaniem względem Ag.

Wniosek 1 Dla każdej macierzy bazowej A_B istnieje co najwyżej jedno bazowe rozwiązanie dopuszczalne.

Wniosek 2 Macierz bazowa Ag jest dopuszczalna wtedy i tylko wtedy, gdy

Aj^b > 0.

Twierdzenie 2 Rozwiązanie dopuszczalne x równania (8) jest bazowym rozwiązaniem dopuszczalnym wtedy i tylko wtedy, gdy jest wierzchołkiem zbioru rozwiązań dopuszczalnych tego równania.

4