1636661684

15

2. METODA SYMPLEKSOWA

G C(A). Zauważmy, że aj 0 B, bo a\, a2,..., a^, aj są liniowo zależne. Mamy 0 = Av =    = Bvb + Nvn = Bvb + cijUj, a stąd vb = Vj(—B~^la,j),

czyli v = Vj\ ^ ^aA. Ponieważ v > 0, Vj > 0 więc B~^xaj <0.    □

Wniosek 2.11. Niech X = {x G Rⁿ;Ar = b,x > 0}, gdzie A G M_mxn(R), b G R^m, rz (A) = m. Zbiór X posiada skończenie wiele kierunków ekstremalnych.

Twierdzenie 2.12 (o reprezentacji). Niech X = {x G Rⁿ; Ar = b,x > 0}, gdzie A G M_mxn(R), b G R^m, rz(A) = m. Niech Xi,X2,... _}Xk będą wszystkimi punktami ekstremalnymi zbioru X, natomiast V\,V2,... ,vi wszystkimi wektorami ekstremalnymi zbioru X. Wówczas x G X wtedy i tylko wtedy, gdy istnieją takie liczby Ai, A2,..., A* > 0, których suma jest równa jeden oraz takie liczby //2, • • •, l^i > 0, że

k    1

x = y^ a iXi+y^ p,iVi.

i= 1    i=1

Dowód. Niech

k    1

Y — {x G R ; 3_Ai)A2)...,A_fc>0,^₌₁ Af=l»    ^X =    ^^iXi

ż=l    i=l

Pokażemy, że X = Y. Zauważmy, że Y 7^ 0, bo z twierdzenia 2.8 istnieje co najmniej jeden punkt ekstremalny.

(i)    Y C X. Niech x G V, x = Yli=1 Ai£i + X^=i A*, /ij > 0, X^i=i ⁼ 1, i = 1,2 ,...,k,j = 1,2,...,/. Mamy = ^i₌₁ ^i^xi £ -AT- Niech x\ =

+ HiVi, gdzie x'₀ = x'. Wówczas G X czyli x = x\ E X.

(ii)    I C y. Zauważmy, że Y jest wypukły i domknięty. Załóżmy, że X \ Y 7^ 0 i niech z E X \ Y, czyli z ^ Y. Na mocy Twierdzenia 13.18 istnieją wówczas: wektor p E Rⁿ i a > 0 takie, że p^rz > a oraz

k    1

w p^T(Y^XiXi+Y - ^a’

i=1    i= 1

dla dowolnych A i,p,j takich, że ]P*₌₁Aj ⁼ KiPj > 0, i = 1,2 j = 1,2,...,/. Ponieważ jij można wybrać dowolnie duże, to nierówność (*)