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 – 9. Dualna metoda sympleks – MIM UW

Zagadnienia

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.

Ćwiczenie 9.1

Opisz dualny algorytm metody sympleks na przykładzie zadania:

Min x_{0}=5x_{1}+x_{2}+11x_{3} , gdy:

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

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

6x_{1}+2x_{2}+15x_{3}\geq 40

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

Ćwiczenie 9.2

Opisz dualny algorytm metody sympleks na przykładzie zadania:

Min x_{0}=2x_{1}+4x_{2}+7x_{3} , gdy:

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

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

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

x_{1}\geq 0, x_{2}\geq 0, x_{3}\geq 0.

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.