421 2

10.3. Dualność

421

Znaleźć minimum wyrażenia

giy)=y^ti>

y^TA >c^T.

(10.3.4)

przy ograniczeniach

<10.3.5)

Wektor y spełniający te ograniczenia nazywa się wektorem dopuszczalnym dla zadania dualnego.

Twierdzeń if 10.3.1. Zachodzi ró wnaść

(10.3.6)    min^(7)«max/(i).

Funkcja g osiąga minimum w punkcie y spełniającym układm równań

(10.3.7)    y\=Ci (ieS),

gdzie Sjest określonym wyżej zbiorem liczb całkowitych.

Dowód. Niech x i y będą dowolnymi wektorami dopuszczalnymi, odpowiednio dla zadania pierwotnego i dualnego. Wtedy

g(y)=y^Tb=y^TAx>c^lx=f(x).

Stąd

(10.3.8)

ming(p)^max/(x).

Wykażemy następnie, że wektor y określony w (10.3.7) jest dopuszczalny. Ponieważ Ax^b, więc

/ (x)=c^Tx-p^T(^x-A)=p^TA-Kc^T-jT^r^)x.

Z (103.7) wynika zatem, że

(łO.3.9)    f(x)~y^r*+ Y(cj-r*j)xj-

J*s

f(x) wyraża się teraz przez zmienne prawostronne odpowiadające rozwiązaniu optymalnemu zadania pierwotnego. Z kryterium maksimum (zob. § 103) wynika więc, że

Cj-y^T*j<: 0 (jtS).

^°» wraz z równaniami (10.3.7), oznacza, że y jest wektorem dopuszczalnym dla zadania dualnego. Poza tym,ponieważxj=0dlay£ S, więc z(10.3.9) wynika,że

f(x)**y^rb*=g{y).

^ożaa to pogodzić z nierównością (10.3.8) tylko wtedy, gdy min g(y)=g(y). Stąd ^w*^Xifi^r(j)“max/(x), co należało udowodnić.