Zagadnienia

8.1 Teoria dualności.
- Zadania

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.

Optymalizacja I

Zagadnienia

8. Teoria dualności

8.1. Teoria dualności.

Definicja 8.1

Przykład 8.1

Twierdzenie 8.1

Przykład 8.2

Definicja 8.2

Twierdzenie 8.2

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

Wniosek 8.1

Wniosek 8.2

Przykład 8.3

Lemat 8.1 (Lemat Farkas'a)

Twierdzenie 8.4

Twierdzenie 8.5 (Silne twierdzenie o dualności)

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

Wniosek 8.3

Uwaga 8.1

Przykład 8.4

Zadania

Ćwiczenie 8.1

Ćwiczenie 8.2

Ćwiczenie 8.3

Ćwiczenie 8.4