1636661681

12

2. METODA SYMPLEKSOWA

Dowód. Weźmy B G C(A) takie, że B ^lb > 0. Niech x =    . Za

uważmy, że x G X. Rzeczywiście dla A = [BN] mamy Ax = [BN] ^ q =

b + iV0 = 6, zarazem x > 0. Załóżmy, że x = Aa;i + (1 — A)x2 dla X\,X2 € X oraz A G (0,1). Niech xj =    #2 ⁼ i^x2i>^22]• Wtedy

- (1 — A)

Ponieważ #12,£22 — 0, A G (0,1), A, 1 — A > 0, to mamy #12 = £22 = 0. Ponadto, b = Ax 1 = Bxn, a więc Xn = B~^lb. Podobnie x%\ = B~^lb. Wobec równości Xu = £21 = B~^lb mamy x\ = X2 = x, zatem x jest punktem ekstremalnym w X.

Niech teraz x G Rⁿ będzie punktem ekstremalnym. Załóżmy, że x = [zi, X2i.. •, Xki 0,0,..., 0]^T, gdzie Xi > 0 dla i = 1,2, Pokażemy, że kolumny ai, 02,..., a* są liniowo niezależne. Gdyby tak nie było, to istniałyby liczby Ai, A2,...»A* G R, Af 7^ 0 takie, że Yli=i ^i^ai = 0- Niech A = [Ai, A2, • • •, Aft, 0,0,..., 0]^T. Rozpatrzmy wektory a^¹) = x+r\, x⁽'²’ = x — r\, gdzie r > 0, x^\ x^⁾ > 0. Zauważmy, że

+ C^-1)' ^lrAi) = Y ^ai^xi + (-¹)* '^r Y ^ai^Xi “ ^b-

Zatem x^\x^ G X, a ponieważ r > 0, to    7^ x^. Ponadto x = \x^ +

\x^, co przeczy temu, że x jest punktem ekstremalnym. Zatem kolumny ai, CL2, ■ ■ ., «ft są liniowo niezależne. Czyli z n — k kolumn można wybrać m — k kolumn tak, aby razem z pierwszymi k kolumnami tworzyły m liniowo niezależnych wektorów. Załóżmy, że tymi kolumnami są aft+i,(Zft+2, • ■ • ,«m-Wobec tego macierz A może być zapisana w postaci A = [BN], gdzie B = [ai, <Z2,..., a_m] G C(A), rz (B) = m. Mamy b = Ax = Bxb + Nx^ = Bxb, a

□

stąd xb = B ¹b, czyli a; =

Wniosek 2.7. Niech X = {x E Rⁿ; Aa; = b, x > 0}, gdzie A G M_mXn(R)> b G R^m, rz (A) = m. Zbiór X posiada skończenie wiele punktów ekstremalnych.

□

Dowód. Wynika z twierdzenia 2.6 oraz faktu, że |C(A)| < 00.