Zagadnienia

9.1 Dualna metoda sympleks.

9. Dualna metoda sympleks

9.1. Dualna metoda sympleks.

Badamy zadanie:

$P$ $Max\quad x_{{0}}=c^{{T}}x$

$Ax=b$

$x\geq 0$

$\qquad TS=\left[\begin{array}[]{c|c}-c_{{N}}&0\\ \hline A&b\end{array}\right]$

przypomnijmy definicję 5.1. $TS$ jest pierwotnie dopuszczalna (przedstawia wierzchołek obszaru dopuszczalnego) $\Leftrightarrow b\geq 0$

$TS$ jest dualnie dopuszczalna (przedstawia wierzchołek zadania dualnego) $\Leftrightarrow c\leq 0\quad(-c_{{N}}\geq 0)$

$TS$ przedstawia wierzchołek optymalny jest pierwotnie i dualnie dopuszczalna.

Przykład 9.1

$P$ $Min\quad x_{{0}}=2x_{{1}}+3x_{{2}}$

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

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

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

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

(typowy przykład zagadnienia diety)

$\begin{array}[]{rrrrrr|r}x_{{0}}&x_{{1}}&x_{{2}}&x_{{3}}&x_{{4}}&x_{{5}}&ww\\ 1&-2&-3&0&0&0&0\\ \hline 0&1&1&-1&0&0&2\\ 0&3&2&0&-1&0&7\\ 0&2&1&0&0&-1&4\end{array}$

$TS\ \ \ \ \begin{array}[]{rrrrr|r}-2&-3&0&0&0&0\\ \hline-1&-1&1&0&0&-2\\ -3&-2&0&1&0&-7\\ -2&-1&0&0&1&-4\end{array}$

jest dualnie dopuszczalna.

Rozpatrzmy teraz zadanie dualne:

$D$ $Max\quad y_{{0}}=2y_{{1}}+7y_{{2}}+4y_{{3}}$

$y_{{1}}+3y_{{2}}+2y_{{3}}\leq 2$

$y_{{1}}+2y_{{2}}+y_{{3}}\leq 3$

$y_{1}\geq 0$ , $y_{2}\geq 0$ , $y_{3}\geq 0$ .

I równoważne mu:

$D^{\ast}$ $Min-y_{{0}}=-2y_{{1}}-7y_{{2}}-4y_{{3}}$

$TS^{\ast}\ \ \qquad\begin{array}[]{rrrrr|r}2&7&4&0&0&0\\ \hline 1&3&2&1&0&2\\ 1&2&1&0&1&3\end{array}$

Jeżeli wykreślimy kolumny związane ze zmiennymi bazowymi to $-TS^{{T}}=TS^{\ast}$

Prześledźmy metodę sympleks na tych dwóch tablicach równocześnie.

Dualne Pierwotne

$\begin{array}[]{rrrrr|r}2&7&4&0&0&0\\ \hline(1)&3&2&1&0&2\\ 1&2&1&0&1&3\end{array}\qquad\qquad\begin{array}[]{rrrrr|r}-2&-3&0&0&0&0\\ \hline(-1)&-1&1&0&0&-2\\ -3&-2&0&1&0&-7\\ -2&-1&0&0&1&-4\end{array}$

$\begin{array}[]{rrrrr|r}0&1&0&-2&0&-4\\ \hline 1&(3)&2&1&0&2\\ 0&-1&-1&-1&1&1\end{array}\qquad\begin{array}[]{rrrrr|r}0&-1&-2&0&0&4\\ \hline 1&1&-1&0&0&2\\ 0&1&(-3)&1&0&-1\\ 0&1&-2&0&1&0\end{array}$

$\begin{array}[]{rrrrr|r}-\frac{1}{3}&0&-\frac{2}{3}&-\frac{1}{3}&0&-4\frac{2}{3}\\ \hline\frac{1}{3}&1&\frac{2}{3}&\frac{1}{3}&0&\frac{2}{3}\\ \frac{1}{3}&0&-\frac{1}{3}&-\frac{2}{3}&1&\frac{5}{3}\end{array}\qquad\begin{array}[]{rrrrr|r}0&-\frac{5}{3}&0&-\frac{2}{3}&0&4\frac{2}{3}\\ \hline 1&\frac{2}{3}&0&-\frac{1}{3}&0&\frac{7}{3}\\ 0&-\frac{1}{3}&1&-\frac{1}{3}&0&\frac{1}{3}\\ 0&\frac{1}{3}&0&-\frac{2}{3}&1&\frac{2}{3}\end{array}$

Otrzymaliśmy rozwiązania

$q=(0,\frac{2}{3},0,0,\frac{5}{3})$ dla zadania dualnego i $p=(\frac{7}{3},0,\frac{1}{3},0,\frac{2}{3})$ dla zadania pierwotnego. Ale wartości funkcji celu są równe

$-y_{{0}}=-4\frac{2}{3}$

$y_{{0}}=4\frac{2}{3}=x_{0}$

Algorytm dualnej metody sympleks

(dla Max):

Na starcie mamy TS dualnie dopuszczalną (tzn. $-c_{{N}}\geq 0$ )

$TS=\begin{array}[]{c|c}-c_{{N}}&b_{{0}}\\ \hline\mathbf{A}&b\end{array}$ gdzie elementy macierzy $A$ oznaczamy:

$a_{{i,j}},1\leq i\leq n,\, 1\leq j\leq t$ zaś kolumny $b$ oznaczamy $b_{{i}},1\leq j\leq t$ .

$1^{{\circ}}$ Test optymalności. Jeżeli $b\geq 0$ to stop (tablica przedstawia

wierzchołek optymalny)

$2^{{\circ}}$ Wybieramy wiersz główny $i$ , taki, że $b_{{i}}<0$

$3^{{\circ}}$ Test sprzeczności: jeżeli w i-tym wierszu

wszystkie wyrazy są $\geq 0$ to stop (zadanie sprzeczne)

Ponieważ i-ty wiersz reprezentuje równanie

$\sum _{{j=1}}^{{n}}a_{{i,j}}x_{{j}}=b_{{i}}$ , w którym

$a_{{i,j}}\geq 0\quad x_{{j}}\geq 0$ oraz $b_{{i}}<0$

$4^{{\circ}}$ Wybór elementu centralnego:

Liczymy minimum $Min\{\left|\frac{c_{j}}{a_{{i,j}}}\right|\,:\, 1\leq j\leq t,\, a_{{i,j}}<0\}$ .

Jako element centralny wybieramy dowolne $a_{{i,j}}$ na którym

osiągalne jest minimum.

$5^{{\circ}}$ Eliminacja Gaussa-Jordana

$6^{{\circ}}$ Wracamy do $1^{{\circ}}$

Rzeczywiście $5^{{\circ}}$ daje $TS$ dualnie dopuszczalną:

nad kreską otrzymujemy $W_{{0}}-\frac{d_{{j}}}{a_{{i,j}}}W_{{i}}$ ,

gdzie $W_{{0}}=(d_{{1}},d_{{2}},...,d_{{n}})$ zatem w k-tej kolumnie otrzymujemy

$d_{{k}}-\frac{d_{{j}}}{a_{{i,j}}}\cdot a_{{ik}}$

Jeżeli $a_{{i,k}}\geq 0$ to $\frac{d_{{j}}}{a_{{ij}}}\cdot a_{{ik}}\leq 0$ bo $a_{{i,j}}\leq 0$ i $d_{{k}}-\frac{d_{{j}}}{a_{{i,j}}}\cdot a_{{i,k}}\geq 0$ .

Jeżeli $a_{{i,k}}<0$ to $\left|\frac{d_{{j}}}{a_{{ik}}}\right|\geq\left|\frac{d_{{j}}}{a_{{ij}}}\right|$

$\frac{d_{{j}}}{a_{{i,k}}}\leq\frac{d_{{j}}}{a_{{i,j}}}$ więc

$d_{{k}}\geq\frac{d_{{j}}}{a_{{i,j}}}\cdot a_{{i,k}}$

Porównanie metody sympleks prostej i dualnej

1) zadanie opisane $TS$ dualnie dopuszczalną może mieć rozwiązanie lub być sprzeczne, ale nie może być nieograniczone.

1') zadanie opisane $TS$ pierwotnie dopuszczalną może mieć rozwiązanie lub być nieograniczone ale nie może być sprzeczne ( $TS$ opisuje wierzchołek dopuszczalny)

2) Dualna metoda sympleks daje rozwiązanie (algorytm się kończy) ponieważ ma tyle kroków ile prosta metoda sympleks na zadaniu dualnym.

3) Przy zadaniu Max

W dualnej metodzie sympleks wartość funkcji celu maleje, ( w pierwotnej rośnie).

Dualna metoda sympleks jest używana tylko jako narzędzie pomocnicze, ponieważ niedokończone obliczenia nie dają przybliżonego rozwiązania, a tylko oszacowanie funkcji celu.