1636661687

18

2. METODA SYMPLEKSOWA

Twierdzenie 2.14. Niech X = {x G Rⁿ; Ar — b,x > 0}, gdzie A G M_mxn(R), b G R^m, rz (^4) = m i niech Xi,X2, ■ • • ,Xk będą wszystkimi punktami ekstremalnymi, zaś vi,V2wszystkimi wektorami ekstremalnymi zbioru X, c G Rⁿ. Wówczas inf{c^Trr; iGI}gR-^ Vj=i,2,...,ic^TVj > 0. Jeżeli Vj=i,2,...,iC^TVj > 0, to 3ie{i,2,...,/c} 'mi{c^rx\x G X} = ćFxi.

Dowód. Z Twierdzenia 2.12 wiemy, że dowolny element x spełnia warunki Ax = b, x > 0 wtedy i tylko wtedy, gdy x = X^i=i + X]j=i h-Wi > Aj,/^- > 0, Aj = 1, i = 1,2 ,...,k,j = 1,2,...,/. Zatem c^T:r = ^cT(St=i + Sj=i gdzie > 0, X^=i ^ = 1> i = 1,2, j = 1,2,...,/. Jeśli dla pewnego j, cJvj < 0, to nasze wyrażenie jest nieograniczone, ponieważ fij możemy wybrać dowolnie duże. Zatem inf{c^Tx; x G X} G R wtedy i tylko wtedy, gdy c^TVj > 0 dla dowolnego j = 1,2,...,/.

Jeśli c^TVj > 0 dla dowolnego jf = 1,2,...,/, to w celu osiągnięcia najmniejszej wartości możemy przyjąć fij = 0 dla j = 1,2,...,/. Zatem

kl    k    k

inf{c^T(y^ A iXi +    Pj^vj)} ⁼ inf{c^T    AjXj; A j > 0, Aj = 1}.

i=l    j=l    i=l    i=l

Niech Aj₀ = 1 oraz Aj = 0 dla i ± i₀, gdzie indeks io jest taki, że c^TXi₀ = mini<j<fc{c^Ta;j}. Wówczas c^TXi₀ < J2i=i Kc^TXi, co kończy dowód.    □

Niech X = {x G R;Ar = b, x > 0}, gdzie A G M_mxn(R), b G R^m, rz (A) = m. Zajmiemy się szukaniem inf{c^T:r; a; G X}. Niech x będzie punktem ekstremalnym zbioru X. Z Twierdzenia 2.6 wiemy, że istnieje B G C(A),

B~^xb > 0 oraz >1 = [5A/], x =    . Weźmy dowolny x G X, x = j^J.

Wówczas Ar = 6 tzn. [5N] \^Xb\ = b, skąd dostajemy Bxb + Afaw = b.

[_^XN]

Zatem xb = B~^lb — B~¹Nx^. Policzmy c^Tx c^Tx = c^xb + cJjXn = c^TB~¹b — c^tbB~¹Nxn + cJjXn = opr# + Cn^xn~\-—Ć^B~¹Nxn +    = c^Tx + (c£ — c^B~¹N)xn-

Przypadek 1:

cl — clB~^lN > 0. Ponieważ x > 0, to Xn > 0 i w konsekwencji c^Tx > c^T:r. Zatem :f jest szukanym punktem.