1636661685

16

2. METODA SYMPLEKSOWA

jest prawdziwa tylko wtedy, gdy p^TVi < 0 dla i = 1,2Kładąc Hi = 0 dla wszystkich i, A* = 1 i Aj = 0 dla j ^ i dostajemy z (*), że p^rXi < a dla ż = 1,2,..., fc. Ponieważ p^Tz > a, to > p^TXi dla dowolnego i. Z powyższych rozważań wynika, że istnieje niezerowy wektor p, dla którego zachodzą następujące nierówności:

(**) p^Tz > p^TXi dla i = 1,2,..., k,

(* * *) p^Tv_i < 0 dla i = 1,2,... ,1.

Rozważmy punkt ekstremalny x określony następująco: p^Tx = max p^TXi.

1 <i<k

Ponieważ x jest punktem ekstremalnym, to z Twierdzenia 2.6 x =

gdzie A = [i?iV] oraz B~^lb > 0. Ponieważ z € X, to Az = b oraz z > 0. Zatem Bzb + Nzn = b i zb = B~^x{b — Nzn) = B~^lb — B~^xNzn- Niech z^T = [zg, zjf\. Z (**) mamy p^Tz — p^Tx > 0, ponadto niech p^T = [Pb,pJj\-Wówczas

0 < p^T z — p^Tx = p^TBz_B + PnZn ~ Pb%b ~ PnXn = Pb(B *b- B ¹Nz_n)+

Pn ~ PB^B~^lb = PB^B~^lb - PbB^Nzn +Pn -PB^B~^lb = (Pn-Pb^b~¹n)^zn,

bo Zn > 0, z G X. Wobec tego istnieje indeks io > m taki, że Zi₀ > 0 oraz Pio — p^B~^l(ii₀ > 0. Pokażemy, że nierówność B~^lai₀ < 0 nie jest prawdziwa. Załóżmy, że B~^lai₀ < 0. Wówczas vJ_Q = ((—B~¹cii₀)^T, ef₀), gdzie e*₀ jest wektorem o n — m współrzędnych z jedynką (jako jedynym niezerowym elementem) na miejscu o indeksie io, jest ekstremalnym wektorem kierunkowym zbioru X na mocy Twierdzenia 2.10. Z (* * *) wynika, że p^TVi₀ < 0 czyli pi₀ — p^B~^lai₀ < 0, co daje sprzeczność. Zatem B~^ldi₀ ^ 0. Zdefiniujmy wektor x następująco:

x =

~B 'atol

. ^e*o J '

gdzie A =    * 0} = ^ > 0, b = B ¹6, j/_fc = B ¹o_io.

Zauważmy, że x posiada nie więcej niż m dodatnich współrzędnych oraz x_r = 0, Xi₀ = A. Wektor x G X, ponieważ mamy

Ax = [BN]x = BB-¹ b + A {-BB^a^ + Ne_io) = BB^b = b.