Notice: Undefined index: mode in /home/misc/mst/public_html/common.php on line 63 Notice: Undefined index: mode in /home/misc/mst/public_html/common.php on line 65 Notice: Undefined index: mode in /home/misc/mst/public_html/common.php on line 67 Notice: Undefined index: mode in /home/misc/mst/public_html/common.php on line 69 Notice: Undefined variable: base in /home/misc/mst/public_html/lecture.php on line 36 Optymalizacja I – 8. Teoria dualności – MIM UW

Zagadnienia

8. Teoria dualności

8.1. Teoria dualności.

Definicja 8.1

Rozważmy zadanie PL zwane pierwotnym P.

Max\, x_{0}=c_{1}x_{1}^{T}+c_{2}x_{2}^{T}+c_{3}x_{3}^{T}+b_{0},

gdzie x_{1}\in R^{{n_{1}}},x_{2}\in R^{{n_{2}}},x_{3}\in R^{{n_{3}}},x=(x_{1},x_{2},x_{3})\in R^{{n_{1}+n_{2}+n_{3}}}

\begin{array}[]{c|c|cc}\left\lceil A_{{1,1}}\right.&A_{{1,2}}&\left.A_{{1,3}}\right\rceil&x^{T}=b_{1}^{T}\end{array}

\begin{array}[]{c|c|cc}\left|A_{{2,1}}\right.&A_{{2,2}}&\left.A_{{2,3}}\right|&x^{T}\leq b_{2}^{T}\end{array}

\begin{array}[]{c|c|cc}\left\lfloor A_{{3,1}}\right.&A_{{3,2}}&\left.A_{{3,3}}\right\rfloor&x^{T}\geq b_{2}^{T}\end{array}

x_{1}\in R^{{n_{1}}},\, x_{2}\geq 0,\, x_{3}\leq 0.

wtedy zadaniem dualnym D nazywamy zadanie:

Min\, y_{0}=c_{1}y_{1}^{T}+c_{2}y_{2}^{T}+c_{3}y_{3}^{T}+b_{0},

gdzie y_{1}\in R^{{t_{1}}},y_{2}\in R^{{t_{2}}},y_{3}\in R^{{t_{3}}},y=(y_{1},y_{2},y_{3})\in R^{{t_{1}+t_{2}+t_{3}}}

\begin{array}[]{c|c|cc}\left\lceil A_{{1,1}}^{T}\right.&A_{{2,1}}^{T}&\left.A_{{3,1}}^{T}\right\rceil&y^{T}=c_{1}^{T}\end{array}

\begin{array}[]{c|c|cc}\left|A_{{1,2}}^{T}\right.&A_{{2,2}}^{T}&\left.A_{{3,2}}^{T}\right|&y^{T}\geq c_{2}^{T}\end{array}

\begin{array}[]{c|c|cc}\left\lfloor A_{{1,3}}^{T}\right.&A_{{2,3}}^{T}&\left.A_{{3,3}}^{T}\right\rfloor&y^{T}\leq c_{2}^{T}\end{array}

y_{1}\in R^{{t_{1}}},\, y_{2}\geq 0,\, y_{3}\leq 0.

Reguły przechodzenia od zadania pierwotnego do dualnego przedstawia tabela:

Jeżeli P ma n zmiennych to D jest opisane przez n nierówności (równań). Jeżeli P jest opisane t nierównościami to D ma t zmiennych.

\begin{array}[]{|c|c| }\hline&\\
Pierwotne&Dualne\\
&\\
\hline min&max\\
max&min\\
\text{i-ta nierówność zgodna z typem}&\text{i-ta zmienna }\geq 0\\
\text{j-ta nierówność niezgodna z typem}&\text{j-ta zmienna }\leq 0\\
\text{k-ta nierówność jest równaniem}&\text{k-ta zmienna nieograniczona}\\
\text{i-ta zmienna }\geq 0&\text{i-ta nierówność zgodna z typem}\\
\text{j-ta zmienna }\leq 0&\text{j-ta nierówność niezgodna z typem}\\
\text{k-ta zmienna nieograniczona}&\text{k-ta nierówność jest
równaniem}\\
\hline\end{array}

gdzie:

\begin{array}[]{c}\text{dla zadań typu Max}\\
a^{{T}}x\leq b\text{ - nierówność jest zgodna z typem}\\
a^{{T}}x\geq b\text{ - nierówność jest  niezgodna z typem}\\
\text{dla zadań typu  Min}\\
a^{{T}}x\geq b\text{ - nierówność jest  zgodna z typem}\\
a^{{T}}x\leq b\text{ - nierówność jest niezgodna z typem}\end{array}

Przykładami par zadań wzajemnie dualnych są:

P: max\quad cx^{{T}}    D: min\quad by^{{T}}

Ax^{T}\leq b^{T}      A^{{T}}y^{T}\geq c^{T}

x\geq 0        y\geq 0

lub

P: max\quad cx^{{T}}    D: min\quad by^{{T}}

Ax^{T}=b^{T}      A^{{T}}y^{T}\geq c^{T}

x\geq 0        y\in R^{t}

Przykład 8.1

Jeżeli zadanie pierwotne P ma postać:

Max\quad x_{{0}}=2x_{{1}}+x_{{2}}-x_{{3}}

x_{{1}}+x_{{2}}\geq-3

x_{{1}}+3x_{{2}}+x_{{3}}\geq 2

-x_{{1}}+2x_{{3}}=7

x_{{2}}+x_{{3}}\leq 5

x_{{1}}\geq 0,\quad x_{{3}}\leq 0

b^{T}=\left[\begin{array}[]{c}-3\\
2\\
7\\
5\end{array}\right]\qquad A=\left[\begin{array}[]{rrr}1&1&0\\
1&3&1\\
-1&0&2\\
0&1&1\end{array}\right]\qquad c=(2,1,-1)

to zadanie dualne D ma postać:

Min\, y_{{0}}=-3y_{{1}}+2y_{{2}}+7y_{{3}}+5y_{{4}}

y_{{1}}+y_{{2}}-y_{{3}}\geq 2\qquad\leftarrow zgodna z typem gdyż x_{{1}}\geq 0

y_{{1}}+3y_{{2}}+y_{{4}}=1\qquad\leftarrow gdyż x_{{2}} nieograniczone

y_{{2}}+2y_{{3}}+y_{{4}}\leq-1\qquad\leftarrow niezgodna z typem gdyż x_{{3}}\leq 0

y_{{1}}\leq 0\qquad\leftarrow gdyż x_{{1}}+x_{{2}}\geq-3 niezgodna z typem

y_{{2}}\leq 0\qquad\leftarrow gdyż x_{{1}}+3x_{{2}}+x_{{3}}\geq 2 niezgodna z typem

y_{{3}}\in R\qquad\leftarrow gdyż -x_{{1}}+2x_{{3}}=7

y_{{4}}\geq 0\qquad\leftarrow gdyż x_{{2}}+x_{{3}}\leq 5 zgodna z typem.

Twierdzenie 8.1

Zadanie dualne do dualnego jest równoważne zdaniu pierwotnemu.

Przykład 8.2

Rozważmy zadanie pierwotne P:

Max\quad c^{{T}}x

Ax\leq b

x\geq 0

\downarrow

D  Min\quad b^{{T}}y

A^{{T}}y\geq c

y\geq 0

\downarrow

D' \qquad-Max(-b\prime)^{{T}}y

(-A^{{T}})y\leq-c

y\geq 0

\downarrow

D(D')   -Min(-c^{{T}}z)

(-A^{{T}})^{{T}}z\geq(-b^{{T}})^{{T}}

z\geq 0

\downarrow

P'  Max\quad c^{{T}}z

Az\leq b

z\geq 0

P'=P

Definicja 8.2

Zadania P_{1} i P_{2} nazywamy równoważnymi jeżeli można od jednego do drugiego przejść stosując następujące reguły:

1) Mnożenie nierówności (równania ) przez liczbę r\neq 0.

1') Mnożenie zmiennej przez liczbę r\neq 0.

2) Zastąpienie nierówności \sum _{{i=1}}^{n}\, a_{i}x_{i}\leq b parą

\left\{\begin{array}[]{l}\sum _{{i=1}}^{n}\, a_{i}x_{i}+x_{{n+1}}=b\\
x_{{n+1}}\geq 0\end{array}\right..

2a) Zastąpienie pary

\left\{\begin{array}[]{l}\sum _{{i=1}}^{n}\, a_{i}x_{i}+x_{{n+1}}=b\\
x_{{n+1}}\geq 0\end{array}\right.

nierównością \sum _{{i=1}}^{n}\, a_{i}x_{i}\leq b.

3) Zastąpienie równania \sum _{{i=1}}^{n}\, a_{i}x_{i}=b parą

\left\{\begin{array}[]{l}\sum _{{i=1}}^{n}\, a_{i}x_{i}\leq b\\
\sum _{{i=1}}^{n}\,-a_{i}x_{i}\leq-b\end{array}\right..

3a) Zastąpienie pary

\left\{\begin{array}[]{l}\sum _{{i=1}}^{n}\, a_{i}x_{i}\leq b\\
\sum _{{i=1}}^{n}\,-a_{i}x_{i}\leq-b\end{array}\right..

równaniem \sum _{{i=1}}^{n}\, a_{i}x_{i}=b.

4) Zastąpienie zmiennej nieograniczonej x_{i} parą x_{i}=x_{i}^{+}-x_{i}^{-}, gdzie \left\{\begin{array}[]{l}x_{i}^{+}\geq 0\\
x_{i}^{-}\geq 0\end{array}\right..

5) Zastąpienie problemu \{ x_{0}=cx^{T}+b_{0}\,|\, x\in D\} problemem

\{ x_{0}=cf(x)^{T}+b_{0}\,|\, f(x)\in f(D)\}, gdzie f jest automorfizmem afinicznym.

Twierdzenie 8.2

Jeżeli zadania P_{1} i P_{2} są równoważne to dualne do nich zadania D_{1} i D_{2} też są równoważne.

Zakładamy, że zadania pierwotne są typu Max.

Ad 1). Niech w zadaniu P_{1} j- tą nierówność zgodną z typem mnożymy przez liczbę r\neq 0. Wtedy w zadaniu dualnym j- ta kolumna zostanie pomnożona przez tę samą liczbę r. Zastępując w zadaniu dualnym zmienną y_{j}:=ry^{{\prime}}_{j} otrzymamy ten sam rezultat. Ponadto znak j- tej nierówności zmienia się taj samo jak znak nierówności r(y_{j}\geq 0). W przypadku nierówności niezgodnej z typem lub równania rezultat jest analogiczny.

Ad 2). Niech w zadaniu P_{1} j- ta nierówność ma postać \sum _{{i=1}}^{n}\, a_{i}x_{i}\leq b zaś w równoważnym zadaniu P_{2} będzie zastąpiona parą

\left\{\begin{array}[]{l}\sum _{{i=1}}^{n}\, a_{i}x_{i}+x_{{n+1}}=b\\
x_{{n+1}}\geq 0\end{array}\right..

Wtedy w zadaniach dualnych: W zadaniu D_{1} zmienna y_{j}\geq 0 zaś w zadaniu D_{2} zmienna y_{j}\in\mathbb{R} i dochodzi nowa nierówność, wyznaczona przez n+1- szą kolumnę zadania P_{2}, jest nią y_{j}\geq 0. Zatem otrzymujemy to samo zadanie.

Ad 3,4). Niech w zadaniu P_{1} j- ta równość ma postać \sum _{{i=1}}^{n}\, a_{i}x_{i}=b zaś w zadaniu P_{2} j- ta równość została zastąpiona parą:

\left\{\begin{array}[]{l}\sum _{{i=1}}^{n}\, a_{i}x_{i}\leq b\\
\sum _{{i=1}}^{n}\,-a_{i}x_{i}\leq-b\end{array}\right..

Wtedy w zadaniach dualnych: W zadaniu D_{1} zmienna y_{j}\in\mathbb{R} jest nieograniczona zaś w zadaniu D_{2} zmienna y_{j} została zastąpiona parą y_{j}^{+}\geq 0,\  y_{j}^{-}\geq 0. Ponadto w zadaniu P_{2} dodatkowa nierówność ma współczynniki przeciwne do j- tej więc zadanie D_{2} można uzyskać z zadania D_{1} podstawiając y_{j}=y_{j}^{+}-y_{j}^{-}0.

Ad 5). Ponieważ każdy automorfizm afiniczny jest złożeniem automorfizmu liniowego i przesunięcia, dowód rozbijemy na dwie części osobno dla automorfizmu liniowego i osobno dla przesunięcia. Przyjmijmy, że zadanie pierwotne ma postać P_{1}=\{ Max\, x_{0}=cx^{T}+b_{0}\,|\, Ax^{T}\leq b^{T}\}. wtedy zadanie dualne ma postać D_{1}=\{ Min\, y_{0}=by^{T}+b_{0}\,|\, A^{T}y^{T}=c^{T},\, y\geq 0\}.

1^{0} Niech f będzie automorfizmem liniowym zadanym macierzą B. Wtedy f(x)^{T}=Bx^{T} i zadanie

P_{1}=\{ Max\, x_{0}=cf(x)^{T}+b_{0}\,|\, Af(x)^{T}\leq b^{T}\}=\{ Max\, x_{0}=cBx^{T}+b_{0}\,|\, ABx^{T}\leq b^{T}\}.

Zatem zadanie dualne ma postać

D_{2}=\{ Min\, y_{0}=by^{T}+b_{0}\,|\, B^{T}A^{T}y^{T}=B^{T}c^{T},\, y\geq 0\}.

Zadanie D_{2} powstało z zadania D_{1} przez operacje elementarne na wierszach ( równaniach ).

2^{0} Niech f(x)=x+d dla pewnego d\in\mathbb{R}^{n}. Wtedy

P_{1}=\{ Max\, x_{0}=cf(x)^{T}+b_{0}\,|\, Af(x)^{T}\leq b^{T}\}=
\{ Max\, x_{0}=cx^{T}+cd^{T}+b_{0}\,|\, Ax^{T}+Ad^{T}\leq b^{T}\}=\{ Max\, x_{0}=cx^{T}+cd^{T}+b_{0}\,|\, Ax^{T}\leq b^{T}-Ad^{T}\}.

Zatem zadanie dualne ma postać

D_{2}=\{ Min\, y_{0}=(b-dA^{T})y^{T}+cd^{T}+b_{0}\,|\, A^{T}y^{T}=c^{T},\, y\geq 0\}.

Zadania D_{1} i D_{2} są równoważne ponieważ w obszarze dopuszczalnym A^{T}y^{T}=c^{T} co po przemnożeniu przez d daje dA^{T}y^{T}=dc^{T}=cd^{T}.

Twierdzenie 8.3 (Słabe twierdzenie o dualności)

Jeżeli p jest punktem dopuszczalnym zadania pierwotnego P: Max\ \{ x_{0}=cx^{{T}}\,|\, Ax^{T}\leq b^{T},\, x\geq 0\} zaś q jest punktem dopuszczalnym zadania dualnego D: Min\quad\{ y_{0}=by^{{T}}\,|\, A^{T}y^{T}\geq c^{T},\, y\geq 0\} to

x_{0}(p)=c^{{T}}p\leq b^{{T}}q=y_{0}(q)

Ponadto jeżeli cp^{{T}}=bq^{{T}} to p jest punktem optymalnym P, zaś q jest punktem optymalnym D.

Niech p i q będą punktami dopuszczalnymi zadań P i Q odpowiednio. Wówczas:

Ap^{{T}}\leq b^{{T}}    A^{{T}}q^{{T}}\geq c^{{T}}

p\geq 0      q\geq 0

co możemy zapisać jako:

(Ap^{{T}}-b^{{T}})\leq\theta=\left[\begin{array}[]{c}0\\
0\\
\vdots\\
\par
\end{array}\right]    (A^{{T}}q^{{T}}-c^{{T}})\geq\theta=\left[\begin{array}[]{c}0\\
0\\
\vdots\\
\par
\end{array}\right]

p\geq 0      q\geq 0

Mnożąc na krzyż otrzymujemy;

q(Ap^{T}-b^{{T}})\leq 0\in\mathbb{R}     p(A^{{T}}q^{{T}}-c^{{T}})\geq 0\in\mathbb{R}

Wyliczamy

qAp^{T}\leq qb^{T}     pA^{{T}}q^{{T}}\geq pc^{{T}}

Co daje

cp^{{T}}=pc^{{T}}\leq pA^{{T}}q^{{T}}=qAp^{T}\leq qb^{T}=bq^{T}

Część druga

cp^{{T}}=bq^{{T}} to \forall _{{x}} z obszaru dopuszczalnego cx^{{T}}\leq bq^{{T}}=cp^{{T}}\Rightarrow p optymalny i z drugiej strony identycznie by^{{T}}\geq cp^{{T}}=bq^{{T}}\Rightarrow q optymalny

Wniosek 8.1

Jeżeli zadanie P jest nieograniczone to D jest sprzeczne.

Przypuśćmy że D nie jest sprzeczne \Rightarrow istnieje q w obszarze dopuszczalnym zadania D

\forall _{{x}} dopuszczalnego cx^{{T}}\leq bq^{{T}}\Rightarrow P ograniczone

Wniosek 8.2

Jeżeli D jest nieograniczone to P sprzeczne.

Niestety zadania P i D mogą być naraz sprzeczne:

Przykład 8.3

P=max\quad x_{{1}}+x_{{2}}

\qquad-x_{{1}}+x_{{2}}\leq-1

\qquad x_{{1}}-x_{{2}}\leq-1

\qquad x_{{1}},x_{{2}}\geq 0

\qquad\Downarrow

\qquad 0\leq-2

D\quad min-y_{{{}_{{1}}}}-y_{{{}_{{2}}}}

-y_{{1}}+y_{{2}}\geq 1

y_{{1}}-y_{{2}}\geq 1

y_{{1}},y_{{2}}\geq 0

\qquad\Downarrow

0\geq 2

Lemat 8.1 (Lemat Farkas'a)

Spośród układów:

1) Ax^{{T}}=b^{T}\wedge x\geq 0

2) yA\geq 0\wedge by^{{T}}<0

dokładnie jeden ma rozwiązanie.

Przypuśćmy że 1) i 2) mają rozwiązania x_{{0}} i y_{{0}}. Wtedy

x_{{0}}\geq 0 i y_{{0}}A\geq\theta więc y_{{0}}Ax_{{0}}^{{T}}\geq 0. Ale y_{{0}}Ax_{{0}}^{{T}}=y_{{0}}b^{{T}}<0. Sprzeczność.

Przypuśćmy że 1) nie ma rozwiązania. Stosujemy pierwszą fazę z dwufazowej metody sympleks.

Rozwiązujemy zadanie opisane tablicą \left[\begin{array}[]{rr|r}0\ldots 0&1\ldots 1&0\\
\hline A&I&b^{T}\end{array}\right],

gdzie zapisane wierszami A=\left[\begin{array}[]{c}w_{{1}}\\
w_{{2}}\\
\vdots\\
w_{{t}}\end{array}\right] i b^{T}=\left[\begin{array}[]{c}b_{{1}}\\
b_{{2}}\\
\vdots\\
b_{{t}}\end{array}\right].

Końcowa tablica ma postać \left[\begin{array}[]{rr|r}d_{1}\ldots d_{n}&k_{1}\ldots k_{t}&b_{0}\\
\hline A^{{\prime}}&D&b^{{\prime}}^{{\, T}}\end{array}\right], gdzie
wiersz (d_{1}\ldots d_{n})\geq 0 i b_{0}<0. Ale wiersz ten jest kombinacją liniową wierszy macierzy A. Oznacza to, że istnieje ciąg y=(y_{1},y_{2},\ldots,y_{t}) taki, że (d_{1}\ldots d_{n})=\sum _{{i=1}}^{t}\, y_{i}w_{i} oraz b_{0}=\sum _{{i=1}}^{t}\, y_{i}b_{i}. Otrzymaliśmy rozwiązanie 2) yA\geq 0\wedge by^{{T}}<0.

Podamy teraz pełną wersję twierdzenia 2.5.

Twierdzenie 8.4

Rozpatrujemy zadanie optymalizacji liniowej:

Max\  x_{0}=c\bullet x\,, gdzie x\in W i W jest opisane układem nierówności: \left\{\begin{array}[]{c}w_{{1}}\bullet x\,\leq b_{{1}}\\
w_{{2}}\bullet x\,\leq b_{{2}}\\
\vdots\\
w_{{t}}\bullet x\,\leq b_{{t}}\end{array}\right..

Niech p\in W będzie takim punktem, że w_{{i}}\bullet p\,=b_{{i}}, dla i=1,2,...,j oraz w_{{i}}\bullet x\,<b_{{i}}, dla i>j. Wówczas:

p jest punktem optymalnym tego zadania wtedy i tylko wtedy gdy dla pewnych liczb rzeczywistych r_{1}\geq 0,r_{2}\geq 0,...,r_{j}\geq 0 zachodzi c=\sum _{{i=1}}^{j}\  r_{i}w_{i}.

Niech B=\left[\begin{array}[]{c}w_{{1}}\\
w_{{2}}\\
\vdots\\
w_{j}\end{array}\right] będzie macierzą pochodzącą od pierwszych j nierówności. Wówczas p nie jest punktem optymalnym wtedy i tylko wtedy gdy kiedy istnieje wektor \alpha taki, że p+\alpha\in W i x_{0}(p+\alpha)>x_{0}(p). Ponieważ długość wektora \alpha nie gra roli to tylko j pierwszych nierówności opisujących W ma znaczenie. Przekształćmy warunki:

\left\{\begin{array}[]{c}w_{{1}}\bullet(p+\alpha)\,\leq b_{{1}}=w_{{1}}\bullet p\\
w_{{2}}\bullet(p+\alpha)\,\leq b_{{2}}=w_{{2}}\bullet p\\
\vdots\\
w_{{j}}\bullet(p+\alpha)\leq b_{{j}}=\, w_{{j}}\bullet p\end{array}\right.

c\bullet(p+\alpha)>c\bullet p do:

B\alpha^{T}\leq 0 i c\alpha^{T}>0.

Przyjmując oznaczenia A=B^{T} i y=-\alpha otrzymujemy:

yA\geq 0\wedge cy^{{T}}<0 czyli drugi układ z lematu Farkasa.

A zatem układ Ax^{{T}}=c^{T}\wedge x\geq 0 nie ma rozwiązań. Oznacza to, że nie istnieje ciąg liczb nieujemnych r_{1}\geq 0,r_{2}\geq 0,...,r_{j}\geq 0 taki, że dla x=(r_{1},r_{2},...,r_{j}) xB=c czyli c\neq\sum _{{i=1}}^{j}\  r_{i}w_{i}.

Twierdzenie 8.5 (Silne twierdzenie o dualności)

Jeżeli jedno z zadań P lub D ma rozwiązanie to drugie też ma rozwiązanie i wartość funkcji celu są równe.

Przyjmijmy, że zadanie pierwotne P:

\{ Max\quad x_{0}=cx^{{T}}\,|\, Ax^{{T}}\leq b^{{T}}\} ma punkt optymalny p taki, że w_{{i}}\bullet p\,=b_{{i}}, dla i=1,2,...,j oraz w_{{i}}\bullet x\,<b_{{i}}, dla i>j, gdzie A=\left[\begin{array}[]{c}w_{{1}}\\
w_{{2}}\\
\vdots\\
w_{t}\end{array}\right]\in\mathbb{R}^{n}_{t}. Wówczas na mocy poprzedniego twierdzenia istnieje ciąg liczb nieujemnych r_{1}\geq 0,r_{2}\geq 0,...,r_{j}\geq 0 taki, że c=\ \sum _{{i=1}}^{j}\  r_{i}w_{i}.

Zadaniem dualnym jest D: \{ Min\quad y_{0}=by^{{T}}\,|\, A^{T}y^{{T}}=c^{T},\, y\geq 0\}.

Niech q=(r_{1},r_{2},...,r_{j},0,0,...,0)\in\mathbb{R}^{t}. Wówczas q\geq 0

i qA=(r_{1},r_{2},...,r_{j},0,0,...,0)\left[\begin{array}[]{c}w_{{1}}\\
w_{{2}}\\
\vdots\\
w_{t}\end{array}\right]=\sum _{{i=1}}^{j}\  r_{i}w_{i}=c. Więc A^{T}q^{{T}}=c^{T}, co oznacza, że q jest punktem dopuszczalnym zadania D.

Ale y_{0}(q)=bq^{T}=\sum _{{i=1}}^{t}\, b_{i}r_{i}=\sum _{{i=1}}^{j}\, b_{i}r_{i}=\sum _{{i=1}}^{j}\ (w_{i}p^{T})r_{i}=\\
=\sum _{{i=1}}^{j}\ (r_{i}w_{i})p^{T}=cp^{T}=x_{0}(p).

Teraz ze słabego twierdzenia o dualności wynika optymalność punktu q.

Twierdzenie 8.6 (Twierdzenie o równowadze (Kuhn, Tucker))

Punkt dopuszczalny p zadania P (Max\quad x_{0}=cx^{{T}}\,|\, Ax^{{T}}\leq b^{{T}},x\geq 0\,) jest punktem optymalnym wtedy i tylko wtedy gdy istnieje punkt dopuszczalny q zadania D

(Min\  y_{0}=by^{{T}}\,|\, A^{{T}}y^{{T}}\geq c^{{T}},y\geq 0\,) taki, że:

1) q(Ap^{{T}}-b^{{T}})=0

2) (qA-c)p^{{T}}=0

Warunek 2) możemy równoważnie zapisać jako:

2a) p(A^{{T}}q^{{T}}-c^{{T}})=0

Niech p będzie punktem optymalnym zadania P. Wówczas na mocy silnego twierdzenia o dualności (twierdzenia 8.5) istnieje rozwiązanie q optymalne dla zadania D. Podobnie jak w dowodzie słabego twierdzenia o dualności ( twierdzenie 8.3) uzyskujemy podwójną równość.

qb^{{T}}=qAp^{T}=cp^{{T}}.

Z pierwszej wyciągając q przed nawias otrzymujemy q(Ap^{T}-b^{T})=0,

zaś z drugiej wyciągając p^{T} przed nawias otrzymujemy (qA-c)p^{T}=0.

Podkreślmy, jeżeli p jest punktem optymalnym zadania P a q jest punktem optymalnym zadania D to spełnione są warunki równowagi q(Ap^{T}-b^{T})=0 i (qA-c)p^{T}=0.

Przypuśćmy, że zachodzą warunki 1) i 2)

wtedy z  1) otrzymujemy q^{{T}}Ap=b^{{T}}q

2) otrzymujemy c^{{T}}p=q^{{T}}Ap. Zatem

\Rightarrow b^{{T}}q=c^{{T}}p i na mocy słabego twierdzenia o dualności p i q optymalne.

Bezpośrednio z twierdzenia i dowodu otrzymujemy:

Wniosek 8.3

Jeżeli punkt p jest optymalny to zbiór punktów optymalnych zadania D jest równy zbiorowi punktów dopuszczalnych q zadania D spełniających warunki równowagi.

Uwaga 8.1

Niech p=(p_{1},p_{2},...,p_{n}) będzie punktem dopuszczalnym zadania P zaś q=(q_{1},q_{2},...,q_{t}) będzie punktem dopuszczalnym zadania D. Jeżeli punkty te spełniają warunki równowagi to:

1) Jeżeli q_{j}\neq 0 to punkt p spełnia j - tą nierówność jako równanie.

2) Jeżeli punkt p spełnia j - tą nierówność na ”ostro” to q_{i}=0.

3) Jeżeli p_{i}\neq 0 to punkt q spełnia i - tą nierówność jako równanie.

4) Jeżeli punkt q spełnia i - tą nierówność na ”ostro” to p_{i}=0.

Ad 1,2) Jeżeli q_{j}>0 to j - tą nierówność zadania P jest zgodna z typem co daje q_{j}(w_{j}p^{t}-b_{j})\leq 0. Zaś gdy q_{j}< to j - tą nierówność zadania P jest niezgodna z typem co daje q_{j}(w_{j}p^{T}-b_{j})\leq 0. (w_{j} oznacza j-ty wiersz macierzy A).

Teraz q(Ap^{t}-b^{T})=\sum _{{j=1}}^{t}\, q_{j}(w_{j}p^{T}-b_{j})=0 jest sumą liczb niedodatnich. Oznacza to, że każdy składnik musi być zerem czyli q_{j}=0 lub w_{j}p^{T}=b_{j}. Daje to warunki 1) i 2).

Punkty 3) i 4) można analogicznie wyprowadzić z drugiego warunku równowagi.

Przykład 8.4

P:   Max\quad x_{{1}}+5x_{{2}}-2x_{{3}}

2x_{{1}}+3x_{{2}}-x_{{3}}\leq 5    =

3x_{{1}}+5x_{{2}}-2x_{{3}}=7       =

x_{{1}}+2x_{{3}}\geq 6         >\qquad\Rightarrow y_{{3}}=0

x_{{i}}\geq 0

Sprawdzamy czy p=(0,3,4) jest optymalny?

Szukamy w tym celu punktu q=(y_{{1}},y_{{2}},y_{{3}}) spełniającego oba warunki równowagi a potem sprawdzimy czy któryś ze znalezionych punktów jest dualnie dopuszczalny. Aby sprawdzić pierwszy warunek podstawiamy punkt p do nierówności. Ponieważ trzecia nierówność spełniona jest na ostro to trzecia współrzędna punktu q musi być zerowa.

Ap-b=\left[\begin{array}[]{c}0\\
0\\
>0\end{array}\right]

Budujemy zadanie dualne.

D:\qquad Min\quad 5y_{{1}}+7y_{{2}}+6y_{{3}}

2y_{{1}}+3y_{{2}}+y_{{3}}\geq 1          cokolwiek

3y_{{1}}+5y_{{2}}\geq 5            =

-y_{{1}}-2y_{{2}}+2y_{{3}}\geq-2         =

y_{{1}}\geq 0,\  y_{{2}}\in R,\  y_{{3}}\leq 0

Aby punkt q spełniał drugi warunek równowagi to ponieważ punkt p ma drugą i trzecią współrzędną niezerową to punkt q musi spełniać drugą i trzecią nierówność zadania dualnego jak równość. Po opuszczeniu trzeciej, zerowej współrzędnej otrzymujemy:

\left\{\begin{array}[]{c}3y_{{1}}+5y_{{2}}=5\\
-y_{{1}}-2y_{{2}}=-2\end{array}\right.\Rightarrow\left\{\begin{array}[]{c}y_{{1}}=0\\
y_{{2}}=1\end{array}\right.

Zatem q=(0,1,0) lub nie istnieje.

Ponieważ q=(0,1,0) jest dopuszczalny dla zadania dualnego, więc p jest optymalny.

Ponadto q jest optymalny dla D.

Zadania

Ćwiczenie 8.1

Rozważmy zagadnienie programowania liniowego:

Max x_{0}=3x_{1}-4x_{2}+2x_{3}-x_{4} , gdy

2x_{1}+3x_{2}-2x_{3}-x_{4}\geq 4

x_{1}-2x_{2}+x_{3}-2x_{4}=-8

6x_{1}-3x_{2}-5x_{3}+5x_{4}\leq 1

x_{1}\leq 0, x_{2}\geq 0, x_{3}\in R, x_{4}\leq 0

a) Zbadaj, czy (0,3,-2,0) jest wierzchołkiem obszaru dopuszczalnego.

b) Opisz jedną z krawędzi przechodzi przez punkt (0,3,-2,0).

c) Napisz zadanie dualne.

d) Stosując warunki równowagi sprawdź czy \left(0,3,-2,0\right) jest punktem optymalnym?

e) Opisz wszystkie punkty optymalne zadania dualnego.

f) Zbadaj jaki wymiar ma zbiór punktów optymalnych zadania pierwotnego.

Ćwiczenie 8.2

Rozważmy zagadnienie programowania liniowego:

Max x_{0}=x_{1}-7x_{2}-3x_{3}+x_{4} , gdy

x_{1}+x_{2}+x_{3}+x_{4}\geq 2

2x_{1}-5x_{2}-6x_{3}+2x_{4}\leq 6

x_{1}+2x_{2}-3x_{3}+x_{4}=3

x_{1}\geq 0, x_{2}\leq 0, x_{3}\geq 0, x_{4}\in R

a) Napisz zadanie dualne.

b) Sprawdź czy \left(1,0,0,2\right) jest wierzchołkiem obszaru dopuszczalnego.

c) Zbadaj ile krawędzi zawiera w sobie punkt \left(1,0,0,2\right).

d) Stosując warunki równowagi sprawdź czy \left(1,0,0,2\right) jest punktem optymalnym zadania.

e) Opisz wszystkie punkty optymalne zadania pierwotnego.

f) Opisz wszystkie punkty optymalne zadania dualnego.

Ćwiczenie 8.3

Rozważmy zagadnienie programowania liniowego:

Max x_{0}=3x_{1}-3x_{2}-7x_{3}+x_{4} , gdy

x_{1}+3x_{2}-4x_{3}+5x_{4}\leq 10

-x_{1}+2x_{2}+3x_{3}+3x_{4}\geq-5

2x_{1}+3x_{2}-6x_{3}-2x_{4}=10

x_{1}\in R, x_{2}\geq 0, x_{3}\leq 0 , x_{4}\geq 0 .

a) Napisz zadanie dualne.

b) Stosując warunki równowagi sprawdź czy \left(2,0,-1,0\right) jest punktem optymalnym zadania.

c) Napisz taką funkcję celu by zbiorem punktów optymalnych była krawędź zawierająca punkt \left(2,0,-1,0\right).

Ćwiczenie 8.4

Rozważmy zagadnienie programowania liniowego:

Max x_{0}=3x_{1}-x_{2}-6x_{3} , gdy

2x_{1}+3x_{2}-2x_{3}+x_{4}\geq 6

-3x_{1}+5x_{2}+3x_{3}-2x_{4}=-9

-x_{1}+6x_{2}+4x_{3}\leq-3

x_{1}\geq 0, x_{2}\leq 0, x_{3}\in R\leq 0 x_{4}\leq 0

a) Napisz zadanie dualne.

b) Sprawdź czy \left(2,0,-1,0\right) jest wierzchołkiem obszaru dopuszczalnego.

c) Opisz dowolną krawędź zawierającą z punkt \left(2,0,-1,0\right).

d) Stosując warunki równowagi sprawdź czy \left(2,0,-1,0\right) jest punktem optymalnym zadania.

e) Znajdź oszacowanie z dołu na funkcję celu zadania dualnego.

Treść automatycznie generowana z plików źródłowych LaTeXa za pomocą oprogramowania wykorzystującego LaTeXML.

Projekt współfinansowany przez Unię Europejską w ramach Europejskiego Funduszu Społecznego.

Projekt współfinansowany przez Ministerstwo Nauki i Szkolnictwa Wyższego i przez Uniwersytet Warszawski.