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 – 6. Dwufazowa metoda sympleks – MIM UW

Zagadnienia

6. Dwufazowa metoda sympleks

6.1. Szukanie wierzchołka startowego

Jeżeli zadanie PL opisane jest macierzą, która nie ma postaci tablicy sympleks, to by móc stosować metodę sympleks stosujemy chwyt genialny w swej prostocie - dopisujemy macierz jednostkową. Dokładniej:

Dwufazowa metoda sympleks

Badamy zadanie:

Max\quad x_{{0}}=cx

Ax=b

x\geq 0

macierzą układu jest [A|b]

Mnożąc w razie potrzeby niektóre równania przez -1 możemy przyjąć, że b\geq 0. Aby uzyskać TS dopisujemy macierz jednostkową i otrzymujemy tablicę sympleks TS=[A|I|b].

Odpowiada temu układ równań

Ax+Iy=b

gdzie y=\left[\begin{array}[]{c}y_{{1}}\\
y_{{2}}\\
\vdots\\
y_{{t}}\end{array}\right]\quad A=\left[\begin{array}[]{cccc}a_{{1,1}}&a_{{1,2}}&\ldots&a_{{1,n}}\\
\vdots&\vdots&\ddots&\vdots\\
a_{{t,1}}&a_{{t,2}}&\ldots&a_{{1t,n}}\end{array}\right]

Pierwsza faza

Rozwiązujemy  zadanie PL\left(\ast\right):\  Max\  y_{{0}}=-y=-y_{1}-y_{2}-...-y_{t}

Ax+Iy=b

x\geq 0\quad y\geq 0

zadanie \left(\ast\right) jest ograniczone ponieważ y\geq 0\Rightarrow y_{{0}}\leq 0. Dodatkowo jeżeli p należy do obszaru dopuszczalnego zadania pierwotnego, czyli Ap=b p\geq 0 to

\overline{p}=(p,0,...,0) jest punktem optymalnym \left(\ast\right) gdyż

[A|I]\overline{p}=A\left[\begin{array}[]{c}p_{1}\\
\vdots\\
p_{n}\end{array}\right]+I\left[\begin{array}[]{c}0\\
\vdots\\
\par
\end{array}\right]=b

zaś y_{{0}}(\overline{p})=0

I Przypadek:

Jeżeli w rozwiązaniu optymalnym zadania \left(\ast\right) y_{{0max}}<0 to wielościan W=\{ x\in R^{n}\,|\, Ax=b\; x\geq 0\} jest zbiorem pustym (zadanie pierwotnie sprzeczne).

II Przypadek:

Jeżeli y_{{0max}}=0 to TS opisująca wierzchołek optymalny zadania \left(\ast\right) pozwala nam opisać wierzchołek zadania pierwotnego.

T=[\overline{A}|D|\overline{b}]

a) Jeżeli wszystkie zmienne y_{{1}},y_{{2}},...,y_{{t}} są niebazowe to macierz powstała po wykreśleniu kolumn z nimi związanych jest TS opisująca wierzchołek obszaru dopuszczalnego zadania pierwotnego.

Rzeczywiście. Jeżeli (p_{{1}},..,p_{{n}},y_{{1}},...,y_{{t}}) jest wierzchołkiem opisanym [\overline{A}|D|\overline{b}] to y_{{1}}=0,...,y_{{t}}=0, \overline{A}p=\overline{b}

(\overline{A} zawiera macierz jednostkową)

[\overline{A}|\overline{b}] powstała z [A|b] przez operacje elementarne na wierszach, więc opisuje ten sam wielościan.

b) Niech y_{{i}} będzie zmienną bazowa. Przyjmijmy, że kolumna odpowiadająca y_{{i}} ma jedynkę w j-tym wierszu i pozostałe współrzędne =0.

1^{{0}}  jeżeli wiersz j-ty ma tylko jeden element niezerowy ( j\,- ty wiersz \overline{A} jest zerowy ) to znaczy, że [A|b] i A były układem zależnym. Taki wiersz i kolumny można wykreślić ( w praktyce zostaje).

2^{{0}}  Jeżeli oprócz jedynki odpowiadającej y_{i} istnieje a_{{j,r}}\neq 0 w j-tym wierszu macierzy \overline{A} to wybieramy go jako element centralny i po przekształceniach elementarnych otrzymujemy TS, w której y_{{j}} jest niebazowe, zaś x_{{r}} jest dołączone do bazy.

Po wykonaniu I fazy otrzymujemy TS opisującą wierzchołek obszaru dopuszczalnego T lub informację, że zadanie było sprzeczne.

Druga faza:

Najpierw budujemy wiersz kosztów zredukowanych

Max\quad x_{{0}}=cx

Koszty zredukowane to x_{{0}}=dx+b_{{0}} gdzie d=(d_{{1}},...,d_{{n}}) to d_{{j}}=0 gdy x_{{j}} - bazowa. Wektor d wyliczamy wstawiając do równania x_{{0}}=cx

równania x_{{j}}=\overline{b_{{j}}}-a_{{ji}}x_{{i}} pochodzące z TS [A^{*}|b^{*}] = \left[\begin{array}[]{cccc|c}a_{{1,1}}&a_{{1,2}}&...&a_{{1_{{n}}}}&b_{{1}}^{*}\\
\vdots&\vdots&\ddots&\vdots&\vdots\\
a_{{t,1}}&a_{{t,2}}&...&a_{{t,n}}&b_{t}^{*}\end{array}\right]

Dalej zadanie rozwiązujemy prosta metodą sympleks.

Przykład 6.1

Badamy zadanie:

Maxx_{{0}}=7x_{{1}}+2x_{{2}}-3x_{{3}}-x_{{4}}

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

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

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

I faza:

Wprowadzamy sztuczne zmienne y_{1} i y_{2} i funkcje celu i otrzymujemy:

Max\  y_{{0}}=-y_{{1}}-y_{{2}}

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

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

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

Zamieniamy teraz funkcję celu podstawiając: y_{1}=-(8x_{1}+3x_{{2}}-5x_{{3}}+x_{{4}}-4) i y_{2}=-(3x_{{1}}+x_{{2}}-2x_{{3}}-x_{{4}}-1).

Otrzymujemy:

y_{0}-(8x_{1}+3x_{{2}}-5x_{{3}}+x_{{4}}-4)-(3x_{{1}}+x_{{2}}-2x_{{3}}-x_{{4}}-1)=0

y_{{0}}-11x_{{1}}-4x_{{2}}+7x_{{3}}=-5 Zadanie opisujemy tablicą:

\overset{\text{baza sztuczna}}{\begin{array}[]{rrrrrr|r}x_{{1}}&x_{{2}}&x_{{3}}&x_{{4}}&y_{{1}}&y_{{2}}&\\
-11&-4&7&0&0&0&-5\\
\hline 8&3&-5&1&1&0&4\\
3&(1)&-2&-1&0&1&1\end{array}}

Opuściliśmy tu kolumnę odpowiadającą zmiennej y_{0} bo, jak wcześniej zauważyliśmy, kolumna ta nie ulega zmianie podczas rozwiązywania.

Wybieramy kolumnę poprawiającą x_{2}.

Min\left\{\frac{4}{3},\frac{1}{1}\right\}=1 i element centralny zaznaczamy nawiasem

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

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

Zmienne sztuczne wypadły z bazy więc możemy je wykreślić. Pozostała tablica opisuje wierzchołek startowy (0,3,1,0).

Wracamy do pierwotnej funkcji celu i liczymy koszty zredukowane:

x_{{0}}=7x_{{1}}+2x_{{2}}-3x_{{3}}-x_{{4}}=7x_{{1}}+2(-x_{{1}}-7x_{{4}}+3)-3(x_{{1}}-4x_{{4}}+1)-x_{{4}}=2x_{1}-3x_{4}+3

i otrzymujemy tablicę sympleks:

\begin{array}[]{cccc|c}-2&0&0&3&3\\
\hline-1&0&1&4&1\\
(1)&1&0&7&3\end{array}

Pierwsza kolumna wyznacza krawędź poprawiającą. Idąc nią otrzymujemy.

\begin{array}[]{rrrr|r}0&2&0&17&9\\
\hline 0&1&1&11&4\\
1&1&0&7&3\end{array}

Ta tablica opisuje jedyny wierzchołek optymalny (3,0,4,0),

w którym Max\, x_{0}=9

Przykład 6.2

Rozwiążmy zadanie:

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

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

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

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

I faza:

Wprowadzamy sztuczne zmienne y_{1} i y_{2} i funkcje celu

Max\  y_{{0}}=-y_{{1}}-y_{{2}}

0=y_{{0}}+y_{{1}}+y_{{2}}=y_{0}-(2x_{{1}}+x_{{2}}-x_{{3}}+6x_{{4}}-3)-(x_{{1}}+x_{{2}}-3x_{{3}}-x_{{4}}-5)

y_{0}-3x_{{1}}-2x_{{2}}+4x_{{3}}-5x_{{4}}=-8

co daje tablicę sympleks

\left[\begin{array}[]{rrrcrr|r}-3&-2&4&-5&0&0&-8\\
\hline 2&1&-1&(6)&1&0&3\\
1&1&-3&-1&0&1&5\end{array}\right]

stosując prosty algorytm metody sympleks otrzymujemy kolejno:

\left[\begin{array}[]{rcrrrr|r}-\frac{4}{3}&-\frac{7}{6}&\frac{19}{6}&0&\frac{5}{6}&0&-\frac{11}{2}\\
\hline\frac{1}{3}&\left(\frac{1}{6}\right)&-\frac{1}{6}&1&\frac{1}{6}&0&\frac{1}{2}\\
\frac{4}{3}&\frac{7}{6}&-\frac{19}{6}&0&\frac{1}{6}&1&\frac{11}{2}\end{array}\right]

\left[\begin{array}[]{rrrrrr|r}1&0&2&7&2&0&-2\\
\hline 2&1&-1&6&1&0&3\\
-1&0&-2&-7&-1&1&2\end{array}\right]

Nad kreską są same liczby nieujemne a funkcja celu jest równa -2 zatem zadanie jest sprzeczne (obszar dopuszczalny jest zbiorem pustym).

6.2. Modyfikacje dwufazowej metody sympleks

1. Metoda częściowej bazy sztucznej

W metodzie dwufazowej wystarczy dodać tylko tyle zmiennych sztucznych, by otrzymać macierz jednostkową.

np.

Maxx_{{0}}=cx

A_{{1}}x\leq b_{{1}}

A_{{2}}x=b_{{2}}

x\geq 0

W tym przypadku mamy t_{{1}} zmiennych bazowych i gdy b_{1}\geq 0 dodajemy tylko t_{{2}} zmiennych sztucznych.

Max\quad x_{{0}}=cx

A_{{1}}x+I_{{t_{{1}}}}\overline{x}=b_{{1}}

A_{{2}}x+I_{{t_{{2}}}}y=b_{{2}}

x\geq 0

\overline{x}\geq 0

y\geq 0

W przypadku rzeczywistych obliczeń ( na maszynach) zwykle nie stosuje się częściowej bazy sztucznej. Nie trzeba wówczas wyszukiwać w macierzy A kolumn zero - jedynkowych.

2. Można obie fazy rozwiązać na jednej TS. W zadaniu:

Max\quad x_{{0}}=cx

Ax=b

x\geq 0

Rozważamy obie funkcje celu jednocześnie.

Max\quad x_{{0}}=cx

Max\quad y_{{0}}=-y

Ax+Iy=b

x\geq 0\qquad y\geq 0

Budujemy tablicę sympleks mającą dwa wiersze nad kreską.

TS=\overline{B^{{-1}}}\cdot\left[\begin{array}[]{c|c|cccc|ccc|c}x_{0}&y_{0}&x_{1}&x_{2}&\ldots&x_{n}&y_{1}&\ldots&y_{t}&ww\\
1&0&&&-c&&0&...&0&0\\
0&1&0&0&...&0&1&...&1&0\\
\hline 0&0&&&A&&&I&&b\end{array}\right],

gdzie

\overline{B}=\left[\begin{array}[]{c|c|c}1&0&0...0\\
0&1&1...1\\
\hline 0&0&I\end{array}\right]

W fazie 1 maksymalizujemy y_{{0}} i w rezultacie otrzymujemy, że zadanie jest sprzeczne lub TS opisująca wierzchołek startowy (łącznie z kosztami zredukowanymi funkcji x_{{0}}).

Ta metoda nigdy nie prowadzi do zmniejszenia liczby operacji (np. wyszło, że zadanie jest sprzeczne, więc naliczyliśmy się zupełnie niepotrzebnie).

Przykład 6.3

Badamy zadanie:

Maxx_{0}=7x_{1}+2x_{2}-3x_{3}-x_{4}

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

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

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

I faza:

Wprowadzamy sztuczne zmienne y_{1} i y_{2} i funkcje celu

Max\  y_{0}=-y_{1}-y_{2}

y_{0}+y_{1}+y_{2}=0

y_{0}-(8x_{1}+3x_{2}-5x_{3}+x_{4}-4)-(3x_{1}+x_{2}-2x_{3}-x_{4}-1)=0

y_{0}-11x_{1}-4x_{2}+7x_{3}=-5

\stackrel{\text{baza sztuczna}}{\left[\begin{array}[]{rrrrrr|rr|r}y_{0}&x_{0}&x_{1}&x_{2}&x_{3}&x_{4}&y_{1}&y_{2}&WW\\
1&0&-11&-4&7&0&0&0&-5\\
0&1&-7&-2&3&1&0&0&0\\
\hline 0&0&8&3&-5&1&1&0&4\\
0&0&3&(1)&-2&-1&0&1&1\end{array}\right]}Wybieramy kolumnę poprawiającą x_{2}.

Min\left\{\frac{4}{3},\frac{1}{1}\right\}=1 i element centralny zaznaczamy nawiasem

\left[\begin{array}[]{rrrrrr|rr|r}1&0&1&0&-1&-4&0&4&-1\\
0&1&-1&0&-1&-1&0&2&2\\
\hline 0&0&-1&0&\left(1\right)&4&1&-3&1\\
0&0&3&1&-2&-1&0&1&1\end{array}\right]

\left[\begin{array}[]{rrrrrr|rr|r}1&0&0&0&0&0&1&1&0\\
0&1&-2&0&0&3&1&-1&3\\
\hline 0&0&-1&0&1&4&1&-3&1\\
0&0&1&1&0&7&2&-5&3\end{array}\right]

Koniec fazy pierwszej. Wszystkie sztuczne zmienne są niebazowe wykreślamy wiersze i kolumny związane ze sztucznymi zmiennymi.

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

Kolumna x_{1} wyznacza krawędź poprawiającą. Idąc nią otrzymujemy.

\left[\begin{array}[]{cccccc}1&0&2&0&17&9\\
\hline 0&0&1&1&11&4\\
0&1&1&0&7&3\end{array}\right]

Ta tablica opisuje jedyny wierzchołek optymalny (3,0,4,0),

w którym x_{{max}}=9

3 Metoda dużego M.

Czasami potrafimy oszacować wartość x_{{0}} i max\quad x_{{i}}. Szczególnie w zagadnieniach całkowitoliczbowych np. transport ciężarówkami i gdy wśród warunków są 0\leq x_{{i}}\leq b_{{i}}.

Aby rozwiązać zadanie: Max\quad x_{{0}}=cx

Ax=b

x\geq 0

wybieramy liczbę M dostatecznie dużą i rozpatrujemy zadanie Max\quad\overline{x_{{0}}}=cx-My

Ax+Iy=b

x\geq 0\qquad y\geq 0.

Teraz poprawione zadanie opisane jest tablicą sympleks:

TS=\left[\begin{array}[]{c|c|c}-c-dM&0...0&-M\cdot\sum{b_{{i}}}\\
\hline A&I&b\end{array}\right],

gdzie wektor d jest sumą wierszy macierzy A.

Rozwiązanie zawsze istnieje, ale czasami w opisie kosztów zredukowanych wierzchołka optymalnego występuje M - oznacza to, że zadanie wyjściowe jest sprzeczne. W stosunku do poprzednich metod zyskujemy to, że mamy jedną fazę i jedną funkcję celu.

Przykład 6.4

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

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

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

x_{i}\geq 0

Sprowadzamy do zadania:

Max\quad\overline{x_{0}}=x_{1}-2x_{2}-3x_{4}-My_{1}-My_{2}

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

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

x_{i}\geq 0, y\geq 0

Otrzymujemy następujące tablice sympleks:

\left[\begin{array}[]{r|rrrr|rr|r}x_{0}&x_{1}&x_{2}&x_{3}&x_{4}&y_{1}&y_{2}&ww\\
1&-1&2&0&3&M&M&0\\
\hline 0&1&-1&-1&0&1&0&1\\
0&-1&1&2&-1&0&1&1\end{array}\right]

\left[\begin{array}[]{r|rrrr|rr|r}1&-1&2&-M&3+M&0&0&-2M\\
\hline 0&1&-1&-1&0&1&0&1\\
0&-1&1&(2)&-1&0&1&1\end{array}\right]

\left[\begin{array}[]{r|rrrr|rr|r}1&-1-\frac{1}{2}M&2+\frac{1}{2}M&0&3+\frac{1}{2}M&0&\frac{1}{2}M&-\frac{3}{2}M\\
\hline 0&(\frac{1}{2})&-\frac{1}{2}&0&-\frac{1}{2}&1&\frac{1}{2}&\frac{3}{2}\\
0&-\frac{1}{2}&\frac{1}{2}&1&-\frac{1}{2}&0&\frac{1}{2}&\frac{1}{2}\end{array}\right]

\left[\begin{array}[]{r|rrrr|rr|r}1&0&1&0&2&2+M&M+1&3\\
\hline 0&1&-1&0&-1&2&1&3\\
0&0&0&1&-1&1&1&2\end{array}\right]

Rozwiązaniem jest wierzchołek (3,0,2,0), w którym funkcja celu osiąga wartość 3.

Zadania

Ćwiczenie 6.1

Opisz dwufazowy algorytm metody sympleks na przykładzie zadania:

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

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

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

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

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

Ćwiczenie 6.2

Opisz dwufazowy algorytm metody sympleks na przykładzie zadania:

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

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

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

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

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.