1636661682

13

2. METODA SYMPLEKSOWA

Twierdzenie 2.8 (o istnieniu punktów ekstremalnych). Niech X = {x £ Rⁿ; Ax = b, x > 0}, gdzie A £ M_mxn(R), b £ R^m, rz (A) = m. Jeśli X ^ I),to zbiór X posiada co najmniej jeden punkt ekstremalny.

Dowód. Ustalmy x £ X. Niech x — [x\, £2, • • • , £&, 0,0,..., 0]^T, gdzie Xi > 0, i = 1,2,..., k. Rozpatrzmy kolumny aą, 02,..., a*, macierzy A. Gdy są one liniowo niezależne, to punkt x jest ekstremalny. Załóżmy, że a\, 02,..., są liniowo zależne, to znaczy istnieją liczby Ai, A₂,..., A* £ R, J2i=i Af 7^ 0 oraz Yli=i = 0. Niech r = minj₌i₎2,...,fc{fⁱ; A* > 0} = Możemy założyć, że zbiór i £ {1,2,..., A:} takich, że A* > 0 jest niepusty. Niech x' £ Rⁿ, gdzie

,_[xi — r\i dla i = 1,2,...,A:

\    0 dla i = k + l,k + 2, ...,n

1. x' > 0, bo inaczej dla pewnego j £ {1,2,,k} mielibyśmy Xj — r\j < 0, a stąd r > ^ i otrzymujemy sprzeczność z minimalnością.

2.    Ax' = b, rzeczywiście Ax' = Yli=i(^xi~^r^i)^ai ⁼ Si=i ^xi^ai~^r12i=1 ^i^ai ⁼ Ax = b. Zatem x' £ X.

3.    x'_iQ = 0 dla pewnego indeksu żo £ (1,2,..., A;}. Wiemy, że istnieje «o € {1,2,..., A;} taki, że r = Zatem x'_io = Xi₀ — rAj₀ = 0.

Jeśli kolumny a!,a₂, ...,afe bez a_io są liniowo niezależne, to punkt x' jest ekstremalny.    □

Lemat 2.9. Niech X = {x £ Rⁿ; Ax = 6, x > 0}, gdzie A £ M_mxn(R), b £ R^m, rz (A) = m. Wektor v £ Rⁿ jest wektorem kierunkowym niepustego zbioru X wtedy i tylko wtedy, gdy Av = 0iv>0,v^0.

Dowód. Niech v £ Rⁿ będzie wektorem kierunkowym zbioru X. Weźmy x £ X, wtedy x+v £ X. Mamy Av = A(x+v—x) = A(x+v)—Ax = b—b = 0, bo v > 0 jest wektorem kierunkowym.

Załóżmy teraz, że Av = 0, v > 0. Niech x £ X, A > 0. Mamy A(x + \v) = Ax + AAv = Ax = b. Ponieważ x > 0, A > 0, v > 0, to x + Au > 0 czyli x + Au £ X.    □

Twierdzenie 2.10 (o charakteryzacji kierunków ekstremalnych). Niech X = {x £ Rⁿ; Ax = b, x > 0}, gdzie A £ M_TOXn(R), b £ R^TO, rz (A) = m. Wektor v jest kierunkiem ekstremalnym zbioru X wtedy i tylko wtedy, gdy istnieją B £ C(A), kolumna aj macierzy A nie występująca w macierzy B oraz A > 0 takie, że