1636661686

17

2. METODA SYMPLEKSOWA

Zauważmy, że układ a\, a,2,.. ., a_r_i, a_r+i, a_r+2, • • ■, a_m, Ui₀ jest liniowo niezależny. Mamy yj₀ = B~^lai₀ zatem = By^. Wówczas

^aio = Oi\CLl+ OL2^a2 + • • • +    ^oraz 7^ 0.

Zatem zbiór wektorów {a_l5 a,2,..., a_m}\{a_r}, ai₀ jest liniowo niezależny. Niech B = [ai,a,2, ..., a_r~i, a_r+i,a_r+2,..., a_m, a*₀]. Mamy £? G C(A), A = [B, IV],

b — Ax = [B, AT]# — .fta# + Afo/y — Ba:#.

Stąd xb — B ^lb > 0. Zatem x = ^ q    i ² Twierdzenia 2.6 a; jest punktem

ekstremalnym. Ponadto

p^Tx = IpI,Pn] p _Ae^'°] = p^TB(b- Ay_i0) + p^TN\e_ia = p^TBb - Ap^TBy_ia + Ap_io =

= Ps-^B_16 + Afo₀ - plB^ai₀) = p^TBx + X(p_io - plB^aic).

Ponieważ A > 0 oraz pi₀—pgB~¹ai₀ > 0, to p^Tx > p^TXi₀. Zatem skonstruowaliśmy punkt ekstremalny x, dla którego p^Tx > p^Tx, co daje sprzeczność, ponieważ p^Tx = maxi<i<fcp^Ta;*.    □

Wniosek 2.13 (o istnieniu kierunkowych wektorów ekstremalnych). Niech X = {x E Rⁿ;Aa; = b, x > 0}, gdzie A G M_mxn(R), b G R^TO, rz(.<4) = m. Wówczas X posiada kierunkowy wektor ekstremalny wtedy i tylko wtedy, gdy X jest nieograniczony.

Dowód. Oczywiście jeśli zbiór X posiada kierunkowy wektor ekstremalny, to X jest nieograniczony. Pokażemy implikację przeciwną. W tym celu załóżmy, że X nie posiada kierunkowych wektorów ekstremalnych. Niech x g x, x =    aiXi, yA__T A* = 1, A* > 0 oraz niech ari, a;2,..., Xk będą

punktami ekstremalnymi. Mamy

ii x 11=11 J2^XiXi

i=1

n< 51 w ii ^Xi u ^ ““{ii ^x‘ ii}-

^z'    l<t<k

i-1

Zatem X jest ograniczony. Otrzymana sprzeczność dowodzi, że zbiór X posiada kierunkowy wektor ekstremalny.    □