Zagadnienia

6.1 Szukanie wierzchołka startowego
6.2 Modyfikacje dwufazowej metody sympleks
- Zadania

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:

$Max$ $x_{{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:

$Max$ $x_{{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.

$Max$ $x_{{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:

$Max$ $x_{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]$