1636661683

14

2. METODA SYMPLEKSOWA

(i)    B~^la,j < O,

(ii)    v = A((—B~¹dj)^T, eJ)^T, gdzie ej jest wektorem mającym n — m współrzędnych z których tylko j-ta współrzędna jest różna od zera i równa się jeden.

Dowód. Niech v = A((—B~¹aj)^T, eJ)^T i B~^laj < 0. Pokażemy, że v jest wektorem kierunkowym. Zauważmy, że v > 0, v 7^ 0 oraz

Av = [BJV]A    ^1<t3j =    + \N_ej = A(-a, + a,) = 0.

Zatem na mocy Lematu 2.9 wektor v jest kierunkowy.

Niech V\,V2 będą wektorami kierunkowymi oraz niech v — Aitą + X₂v₂, gdzie Ai, A2 > 0. Zauważmy, że n — m — 1 współrzędnych wektora v jest równe 0. Zatem odpowiednie współrzędne wektorów V\ i v₂ są również zerowe i wektory te mogą być zapisane w postaci vj = ot\[yj_x, ej], vj = a₂ , ej], gdzie cui, Of2 > 0. Wiemy, że Av\ — Av2 = 0 zatem mamy

0 = Avi = [BN]o>i[vJ₁,eJ]^T =    + NeJ) = a^ByJ + aj),

stąd Vn = —B~^laj. Podobnie y₂\ = —B~^laj, mamy więc V\\ = %, a w konsekwencji V\ = Xv₂, gdzie A = ^. Ostatecznie otrzymujemy, że wektor v jest ekstremalny.

Niech v będzie wektorem ekstremalnym, v = \y\,v₂,..., Vk, 0,..., 0, Vj, 0,..., 0]^T, Vi > 0 dla i = 1,2,..., A; oraz i = j. Pokażemy, że kolumny a\, a₂,..., ak macierzy A są liniowo niezależne. Załóżmy, że tak nie jest tzn. istnieją Ai, A2,..., A& € M takie, że Yli=1    7^    Ya=i ⁼ 0.

Niech A = [A_l5 A₂,..., A*, 0, 0,..., 0]^T. Rozpatrzmy wektory z/¹) = v + rA, _v(²) = _v — r\, gdzie r > 0, z/¹),    > 0, r = min_i=i₎₂,...₁fc{f^L; A* > 0} = yi.

Zauważmy, że

k

Av^ = A(v + (—l)^z_1rA) = Av + (—l)*^_1rA\ = 0 + (—l)*^-1r JJa^A* — 0,

i—1

Ponieważ r > 0, to z/¹) 7^    7^ v. Zatem v = |z/b + co przeczy te

mu, że v jest wektorem ekstremalnym. Czyli kolumny ai, 02,..., a* są liniowo niezależne. Dodatkowo rz (A) = m, stąd k <m więc możemy wybrać m — k wektorów ze zbioru {a*; i = k 4- 1, k + 2,..., m, i 7- j}, które razem z kolumnami ai,a₂, ■ ■. ,ak są liniowo niezależne. Oznaczmy B = [a\,a₂,...,a_m]