Przykład 5.1
Czytelnik który rozwiązał ćwiczenie
![[*]](file:/usr/local/lib/latex2html/icons/crossref.gif)
stwierdził z pewnością,
że z pierwszego słownika
(5.7) |
![\begin{displaymath}
\begin{array}{lcrrrrrrcrl}
& 2x_1 - & x_2 + & x_3 + & x_4...
...z =& 2x_1 + & x_2 + & x_3&&&& \rightarrow & \max
\end{array}
\end{displaymath}](img494.gif) |
w którym rozwiązanie bazowe
![$x_1=x_2=x_3=0, \ x_4=12, \ x_5=10,\linebreak
x_6=-4$](img495.gif)
nie jest rozwiązaniem dopuszczalnym, otrzymał słownik
w którym rozwiązanie bazowe jest dopuszczalne, mianowicie
(5.8) |
![\begin{displaymath}
\begin{array}{lrrrrrrrcr}
x_1 =& 4 - & x_2 + & x_3 + & x...
...& x_6 \\ \hline
z =& 8 - & x_2 - & x_3 + & 2x_6
\end{array}
\end{displaymath}](img496.gif) |
Zmiennymi bazowymi słownika (
![[*]](file:/usr/local/lib/latex2html/icons/crossref.gif)
) są
![$x_1, x_4$](img497.gif)
i
![$x_5$](img109.gif)
.
Macierzowo słownik (
![[*]](file:/usr/local/lib/latex2html/icons/crossref.gif)
) można zapisać następująco
(5.9) |
![\begin{displaymath}
\begin{array}{lclcl}
{\bf x}_B & = & {\bf b}^* & - & {\bf...
...N \\ \hline
z& = & z^* & + & {\bf c}^*{\bf x}_N
\end{array}
\end{displaymath}](img498.gif) |
gdzie
![${\bf P} = \left[
\begin{array}{rrr}
1 & -1 & -1 \\
-3 & 3 & 2 \\
1 & 2 & ...
...rray}{c}
4\\
4\\
6
\end{array}
\right], \ z^*=8, \ {\bf c}^* = [-1,-1,2]$](img499.gif)
, zaś
![${\bf x}_N = \left[
\begin{array}{c}
x_2\\
x_3\\
x_6
\end{array}
\right] $](img500.gif)
Przykład 5.1 (c.d.)
Dla zmiennych bazowych
![$x_1, x_4, x_5$](img502.gif)
mamy:
Ponieważ w naszym przykładzie macierz
![${\bf A}_B$](img504.gif)
jest nieosobliwa,
możemy z równania (
![[*]](file:/usr/local/lib/latex2html/icons/crossref.gif)
) obliczyć
(5.11) |
![\begin{displaymath}
{\bf x}_B = {\bf A}_B^{-1} ({\bf b} - {\bf A}_N{\bf x_N})\ \
\end{displaymath}](img508.gif) |
Przykład 5.1 (dokończenie)
W ostatnim słowniku naszego przykładu jedynym współczynnikiem dodatnim funkcji
celu jest współczynnik przy
![$x_6$](img70.gif)
. Zmienną wchodzącą będzie więc
![$x_6$](img70.gif)
.
Równie łatwo zauważyć, że zmienną wychodzącą jest
![$x_4$](img198.gif)
.
W nowym słowniku zmiennymi bazowymi będą więc
![$x_1, x_5$](img541.gif)
i
![$x_6$](img70.gif)
,
zmiennymi niebazowymi
![$x_2, x_3, x_4$](img542.gif)
. Wobec tego macierzą bazową
![${\bf B}$](img539.gif)
jest macierz złożona z pierwszej, piątej i szóstej kolumny macierzy
czyli
![${\bf c}_B=[2,0,0]$](img545.gif)
,
![${\bf c}_N=[1,1,0]$](img546.gif)
.
Obliczmy najpierw wektor
z równania
Stąd oczywiście zmienną wchodzącą jest koniecznie
![$x_2$](img10.gif)
(jedyną dodatnią współrzędną wektora
![$[2,0,-1]$](img554.gif)
jest
![$2$](img64.gif)
,
współrzędna odpowiadająca zmiennej
![$x_2$](img10.gif)
).
Źeby wyznaczyć zmienną wychodzącą, musimy w pierwszym równaniu
(
![[*]](file:/usr/local/lib/latex2html/icons/crossref.gif)
) wyznaczyć wektor
![${\bf B}^{-1}{\bf b}$](img555.gif)
i
pierwszą kolumnę
(tę odpowiadającą zmiennej
![$x_2$](img10.gif)
) macierzy
![${\bf B}^{-1}{\bf A}_N$](img556.gif)
.
![$a=6, \ b = 4, \ c = 2,$](img558.gif)
a więc
Z kolei pierwszą kolumną
![$\left[ \begin{array}{c} k_1 \\ k_2 \\ k_3 \end{array}
\right]$](img560.gif)
macierzy
![${\bf D}={\bf B}^{-1}{\bf A}_N$](img561.gif)
wyznaczymy z równania
![${\bf BD}={\bf A}_N$](img562.gif)
, a więc
(po lewej stronie tej równości jest iloczyn macierzy
![${\bf B}$](img539.gif)
przez pierwszą kolumnę macierzy
![${\bf D}={\bf B}^{-1}{\bf A}_N$](img561.gif)
,
z prawej pierwsza kolumna
![${\bf A}_N$](img564.gif)
).
![$k_1= -\frac{1}{2}$](img566.gif)
,
![$k_2=\frac{5}{2}$](img567.gif)
,
![$k_3 = - \frac{3}{2}$](img568.gif)
.
Pomijając nieistotne dla nas zmienne niebazowe
![$x_3$](img11.gif)
i
![$x_4$](img198.gif)
równanie
![${\bf x}_B={\bf B}^{-1}{\bf b} - {\bf B}^{-1}{\bf A}_N{\bf x}_N$](img569.gif)
słownika
(
![[*]](file:/usr/local/lib/latex2html/icons/crossref.gif)
) oznacza w w naszym przypadku
Jedynym współczynnikiem ujemnym przy
![$x_2$](img10.gif)
jest
![$-\frac{5}{2}$](img571.gif)
i zmienną wychodząca jest
![$x_5$](img109.gif)
.
Tak więc nowymi zmiennmi bazowymi są
, a zmiennymi niebazowymi
. Nowe macierze i wektory
to teraz
-
Znowu liczymy
![${\bf y}=[y_1,y_2,y_3]$](img574.gif)
z równania
![${\bf y}={\bf c}_B{\bf B}^{-1}$](img575.gif)
, czyli
![${\bf y}{\bf B}={\bf c}_B$](img576.gif)
.