Macierzowy opis słownika

Dla potrzeb niniejszego rozdziału słownik który do tej pory zapisywaliśmy jako

$$\begin{array}{lccclr} x_i & = & b^*_i & - & \sum_{j \noti... ...z & = & z^* & + & \sum_{j \notin B}\bar{c}_j x_j \end{array}$$ (5.1)

gdzie $B$ jest zbioremm indeksów bazowych, będzie nam wygodniej zapisywać w postaci

$$\begin{array}{rrrrrr} \sum_{j \notin B}\bar{a}_{ij}x_j & ... ... &z & = & z^* + & \sum_{j \notin B}\bar{c}_j x_j \end{array}$$ (5.2)

W szczególności pierwszy słownik jest postaci

$$\begin{array}{rrrrrr} \sum_{j \notin B}a_{ij}x_j & + x_i ... ...hline &z & = & z^* + & \sum_{j \notin B}c_j x_j \end{array}$$ (5.3)

ponieważ zaś w pierwszym słowniku zbiór indeksów bazowych
$B=\{ n+1,...,n+m\}$, słownik ten wygląda następująco

$$\begin{array}{rrrrrr} \sum_{j=1}^na_{ij}x_j & + x_i & = b... ...\\ \hline &z & = & z^* & + \sum_{j=1}^n c_j x_j \end{array}$$ (5.4)

W zapisie macierzowym to oczywiście

$$\begin{array}{rclcl} {\bf A}^*{\bf x} & = & {\bf b} \\ \hline z & = & z^* & + & {\bf cx}_N \end{array}$$ (5.5)

gdzie

$${\bf A}^*=\left[ \begin{array}{ccccccc} a_{11} & ... & a_{1... ...a_{m1} & ... & a_{mn} & 0 & 0 & ... & 1 \end{array} \right],$$

$${\bf b}= \left[ \begin{array}{c} \ b_1 \\ .\\ .\\ .\... ...rray}{c} x_1\\ .\\ .\\ .\\ x_n \end{array} \right]$$

Ten sam słownik możemy zapisać także tak:

$$\begin{array}{rcccc} {\bf A}{\bf x}_N & + & {\bf I}_m{\bf... ... {\bf b} \\ \hline z & = & z^* & + & {\bf cx}_N \end{array}$$ (5.6)

gdzie ${\bf I}_m$ jest macierzą jednostkową o $m$ wierszach i $m$ kolumnach, zaś

$${\bf x}_B = \left[ \begin{array}{l} x_{n+1}\\ .\\ .\\ .\\ x_{n+m} \end{array} \right]$$

Przykład 5.1   Czytelnik który rozwiązał ćwiczenie stwierdził z pewnością, że z pierwszego słownika

$$\begin{array}{lcrrrrrrcr} & 2x_1 - & x_2 + & x_3 + & x_4 ... ..._6 & = & -4 \\ \hline z =& 2x_1 + & x_2 + & x_3 \end{array}$$ (5.7)

w którym rozwiązanie bazowe $x_1=x_2=x_3=0, \ x_4=12, \ x_5=10,\linebreak x_6=-4$ nie jest rozwiązaniem dopuszczalnym, otrzymał słownik w którym w którym rozwiązanie bazowe jest dopuszczalne, mianowicie

$$\begin{array}{lrrrrrrrcr} x_1 =& 4 - & x_2 + & x_3 + & x... ...& x_6 \\ \hline z =& 8 - & x_2 - & x_3 + & 2x_6 \end{array}$$ (5.8)

Zmiennymi bazowymi słownika () są $x_1, x_2$ i $x_6$. Macierzowo słownik () można zapisać następująco

$$\begin{array}{lclcl} {\bf x}_B & = & {\bf b}^* & - & {\bf... ...N \\ \hline z& = & z^* & + & {\bf c}^*{\bf x}_N \end{array}$$ (5.9)

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]$, zaś ${\bf x}_N = \left[ \begin{array}{c} x_2\\ x_3\\ x_6 \end{array} \right]$

$\Box$. Jak można wyrazić słownik () przy pomocy słownika () lub ()? W tym celu wystarczy zauważyć następujące fakty:

1. W macierzy ${\bf A}^*$ zmiennym bazowym $x_1, x_4, x_5$ odpowiadają pierwsza, czwarta i piąta kolumna.
2. Pierwszy wiersz słownika () (to znaczy wszystko co ponad kreską w tym wzorze), można zapisać w postaci
   

   $${\bf A}_B{\bf x}_B + {\bf A}_N{\bf x}_N = {\bf b}$$ (5.10)

   
   
   gdzie macierz ${\bf A}_B$ jest utworzona przez kolumny macierzy ${\bf A}^*$ odpowiadające zmiennym bazowym, zaś ${\bf A}_B$ powstaje z ${\bf A}^*$ przez wybranie kolumn odpowiadających zmiennym niebazowym. Wtedy ${\bf x}_B$ i ${\bf x}_N$ są utworzone, odpowiednio, ze współrzędnych będących bazowymi i niebazowymi współrzędnymi wektora ${\bf x}$.

Przykład 5.1 (c.d.)   Dla zmiennych bazowych $x_1, x_4, x_5$ mamy:

$${\bf A}_B = \left[ \begin{array}{ccc} 2 & 1 & 0 \\ 1 & 0 ... ...[ \begin{array}{c} x_2\\ x_3\\ x_6 \end{array} \right]$$

Ponieważ w naszym przykładzie macierz ${\bf A}_B$ jest nieosobliwa, możemy z równania () obliczyć ${\bf x}_B$

$${\bf x}_B = {\bf A}_B^{-1} ({\bf b} - {\bf A}_N{\bf x_N})\ \$$ (5.11)

Nieosobliwość macierzy ${\bf A}_B$ w przykładzie nie jest przypadkowa. Udowodnimy następujące twierdzenie.

Twierdzenie 5.1   Jeśli dany jest słownik postaci

$$\begin{array}{rclcl} {\bf A}_B{\bf x}_B & = & b & - &{\bf... ...= & {\bf c}_B{\bf x}_B & + & {\bf c}_N{\bf x}_N \end{array}$$ (5.12)

gdzie ${\bf x}_B=[x_k]_{k\in B}, \ {\bf x}_N = [x_k]_{k \notin B}$, $B$ - zbiór indeksów zmiennych bazowych, to macierz ${\bf A}_B$ jest nieosobliwa.

Dowód. Dla wykazania naszego twierdzenia wystarczy udowodnić, że równanie ${\bf A}{\bf x}_B = {\bf b}$ ma dokładnie jedno rozwiązanie.
Niesprzeczność równania ${\bf A}_B {\bf x}_B = {\bf b}$ jest oczywista: niech ${\bf x^*} = {\bf x^*}_B + {\bf x^*}_N$ będzie dopuszczalnym rozwiązaniem bazowym - czyli takim, że ${\bf x^*}_N={\bf0}$. Wstawiając ${\bf x^*}$ do () otrzymamy ${\bf A}_B{\bf B x^*}_B = {\bf b}$. Przypuśćmy, że ${\bf\bar{x}}_B \in {\bf R^n}$ także spełnia równanie ${\bf A}_B{\bf\bar{x}}_B = {\bf b}$. Kładąc ${\bf\bar{x}_N}={\bf0}$ i następnie ${\bf\bar{x}}={\bf\bar{x}}_B+ {\bf\bar{x}}_N$ otrzymamy ${\bf A}{\bf\bar{x}} = {\bf A}_B{\bf\bar{x}_B} + {\bf A_B}{\bf\bar{x}_N} = {\bf b}$.
Tak więc ${\bf\bar{x}}$ jest rozwiązaniem dopuszczalnym, co więcej, skoro $\bar{\bf x}_N={\bf0}$, jest to dopuszczalne rozwiązanie bazowe (dla zmiennych bazowych $(x_k)_k\in B$), czylo ${\bf\bar{x}}_B={\bf x}^*_B.$

Definicja 5.1   Macierz ${\bf A}_B$ powstałą z ${\bf A}$ przez usunięcie kolumn odpowiadających zmiennym niebazowym nazywamy macierzą bazową.

Oznaczmy przez $\tilde{\bf c}$ wektor $\tilde{\bf c}= (c_1,...,c_n,0,...,0) =(\tilde{c}_1,...,\tilde{c}_{n+m})$. Niech ${\bf c}_N$ oznacza wektor ${\bf R^n}$ którego współrzędne są współrzędnymi wektora $\tilde{\bf c}$ odpowiadającymi zmiennym niebazowym, ${\bf c}_N = (\tilde{c}_i)_{i \notin B}$, zaś ${\bf c}_B$ niech będzie wektorem ${\bf R^n}$ którego współrzędne są współczynnikami przy zmiennych bazowych w funkcji celu (w wyjściowej postaci). Inaczej:

$${\bf c}_B = (\tilde{c}_j)_{j \in B}$$

We wzorze () możemy teraz zastąpić ${\bf cx}_N$ przez

$${\bf c}_B{\bf x}_B + {\bf c}_N{\bf x}_N$$

i otrzymamy

$$z = z^* + {\bf c}_B{\bf x}_B + {\bf c}_N{\bf x}_N$$

Po zastąpieniu ${\bf x}_B$ przez ${\bf B}^{-1}{\bf b} - {\bf A}_N{\bf x}_N)$ otrzymamy

$$z=z^*+{\bf c}_B{\bf B}^{-1}({\bf b} - {\bf A}_N{\bf x}_N)+{\bf c}_N{\bf x}_N$$

$$z=z^*+{\bf c}_B{\bf B}^{-1}{\bf b} + ({\bf c}_N - {\bf c}_B{\bf B}^{-1}{\bf A}_N){\bf x}_N$$

(gdzie ${\bf B}$ jest macierzą bazową).
Ostatecznie, postacią słownika przy bazie ${\bf B}$ jest

$$\begin{array}{lcl} {\bf x}_B & = & {\bf B}^{-1}({\bf b} -... ... c}_N - {\bf c}_B{\bf B}^{-1}{\bf A}_N){\bf x}_N \end{array}$$ (5.13)

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$. Zmienną wchodzącą będzie więc $x_6$. Równie łatwo zauważyć, że zmienną wychodzącą jest $x_4$. W nowym słowniku zmiennymi bazowymi będą więc $x_1, x_5$ i $x_6$, zmiennymi niebazowymi $x_2, x_3, x_4$. Wobec tego macierzą bazową ${\bf B}$ jest macierz złożona z pierwszej, piątej i szóstej kolumny macierzy

$$A= \left[ \begin{array}{rrrrrr} 2 & -1 & 1 & 1 & 0 & 0 \\ ... ... 0 & 1 & 0 \\ -1 & -1 & 1 & 0 & 0 & 1 \end{array} \right]$$

czyli

$$B=\left[ \begin{array}{rrr} 1 & 0 & 0\\ 1 & 1 & 0 \\ ... ... & 1 & 1 \\ 2 & 1 & 0 \\ -1 & 1 & 0 \end{array} \right]$$

${\bf c}_B=[2,0,0]$, ${\bf c}_N=[1,1,0]$.
Obliczmy najpierw wektor

$${\bf y} = {\bf c}_B{\bf B}^{-1}$$

z równania ${\bf yB}={\bf c}_B$

$$[y_1,y_2,y_3]\left[ \begin{array}{rrr} 2 & 0 & 0\\ 1 & 1 & 0\\ -1 & 0 & 1 \end{array} \right] = [2,0,0]$$

$$\left\{ \begin{array}{rrrr} 2y_1 & + y_2 & -y_3 & =2\\ & y_2 &&=0\\ && y_3 & =0 \end{array} \right.$$

$y_1=1, y_2=y_3=0$

$${\bf c}_B{\bf B}^{-1}{\bf A}_N = [2,0,0] \left[ \begin{arra... ...\\ 2 & 1 & 0 \\ -1 & 1 & 0 \end{array} \right] = [-2,2,2]$$

$${\bf c}_N - {\bf c}_B{\bf B}^{-1}{\bf A}_N = [1,1,0] - [-2,2,2] = [3,-1,-2]$$

Stąd oczywiście zmienną wchodzącą jest koniecznie $x_2$ (jedyną dodatnią współrzędną wektora $[3,-1,-2]$ jest $3$, współrzędna odpowiadająca zmiennej $x_2$.
Źeby wyznaczyć zmienną wychodzącą, musimy w pierwszym równaniu () wyznaczyć wektor ${\bf B}^{-1}{\bf b}$ i pierwszą kolumnę (tę odpowiadającą zmiennej $x_2$) macierzy ${\bf B}^{-1}{\bf A}_N$.

$$\left\{ \begin{array}{rrrr} 2a &&& = 12\\ a & +b & & =10\\ -a && +c & =-4 \end{array} \right.$$

$a=6, \ b = 4, \ c = 2,$ a więc

$${\bf B}^{-1}{\bf b} = \left[ \begin{array}{c} 6\\ 4\\ 2 \end{array} \right]$$

Z kolei pierwszą kolumną $\left[ \begin{array}{c} k_1 \\ k_2 \\ k_3 \end{array} \right]$ macierzy ${\bf D}={\bf B}^{-1}{\bf A}_N$ wyznaczymy z równania ${\bf BD}={\bf A}_N$, a więc

$$\left[ \begin{array}{rrr} 2 & 0 & 0 \\ 1 & 1 & 0 \\ -... ...left[ \begin{array}{r} -1 \\ 2 \\ -1 \end{array} \right]$$

(po lewej stronie tej równości jest iloczyn macierzy ${\bf B}$ przez pierwszą kolumnę macierzy ${\bf D}={\bf B}^{-1}{\bf A}_N$, z prawej pierwsza kolumna ${\bf A}_N$).

$$\left\{ \begin{array}{rrrr} 2k_1 &&& =-1\\ k_1 & + k_2 && =2\\ -k_1 && + k_3 & = -1 \end{array} \right.$$

$k_1= -\frac{1}{2}$, $k_2=\frac{5}{2}$, $k_3 = - \frac{3}{2}$.
Pomijając nieistotne dla nas zmienne niebazowe $x_3$ i $x_4$ równanie ${\bf x}_B={\bf B}^{-1}{\bf b} - {\bf B}^{-1}{\bf A}_N{\bf x}_N$ słownika () oznacza w w naszym przypadku

$$\begin{array}{rcrr} x_1 & = & 6 + \frac{1}{2}x_2 & ...\\ ... ...x_2 & ...\\ x_6 & = & 2 + \frac{3}{2}x_2 & ... \end{array}$$

Jedynym współczynnikiem ujemnym przy $x_2$ jest $-\frac{5}{2}$ i zmienną wychodząca jest $x_5$.
Tak więc nowymi zmiennmi bazowymi są

$x_1,x_2,x_6$, a zmiennymi niebazowymi

$x_3,x_4,x_5$. Nowe macierze i wektory ${\bf B}, {\bf A}_N, {\bf c}_B, {\bf c}_N$ to teraz

${\bf B} = \left[ \begin{array}{rrr} 2 & -1 & 0 \\ 1 & 2 & 0\\ -1 & -1 & 1 ... ...& 1 \\ 1 & 0 & 0 \end{array} \right], {\bf c}_B=[2,1,0], {\bf c}_N=[1,0,0].$

Znowu liczymy ${\bf y}=[y_1,y_2,y_3]$ z równania ${\bf y}={\bf c}_B{\bf B}^{-1}$, czyli ${\bf y}{\bf B}={\bf c}_B$.

$$[y_1,y_2,y_3]\left[ \begin{array}{rrr} 2 & -1 & 0 \\ 1 & 2 & 0 \\ -1 & -1 & 1 \end{array}\right] = [2,1,0]$$

$$\left\{ \begin{array}{rrrrl} 2y_1 & + 2y_2 & - y_3 & = 2\\ -y_1 & +2y_2 & -y_3 & =1 \\ && y_3 & = 0 \end{array} \right.$$

$$\left\{ \begin{array}{rrl} -y_1 & + 2y_2 & =1 \\ & 5y_2 & =4 \end{array}\right.$$

$$y_2=\frac{4}{5}, \ \ y_1 = \frac{8}{5}-1 = \frac{3}{5}$$

Teraz liczymy ${\bf c}_B{\bf B}^{-1}{\bf A}_N = {\bf y}{\bf A}_N = [\frac{3}{5},\frac{4}{5},0... ...0 & 1 \\ 1 & 0 & 0 \end{array}\right] = [\frac{7}{5}, \frac{3}{5},\frac{4}{5}]$ i ostatecznie otrzymamy

$${\bf c}_N - {\bf c}_B{\bf B}^{-1}{\bf A}_N = [1,0,0]- [\frac{... ...ac{3}{5},\frac{4}{5}] = [-\frac{2}{5},-\frac{3}{5}-\frac{4}{5}]$$

. Stąd oczywiście wniosek, że nasze rozwiązanie bazowe jest optymalne. W rozwiązaniu tym oczywiście $x_3=x_4=x_5=0$. Czytelnik zechce obliczyć wartości zmiennych bazowych $x_1, x_2$ i $x_6$ z równania

$$\left[ \begin{array}{c} x_1\\ x_2\\ x_6 \end{array} \right] = {\bf A}_B^{-1}{\bf b}$$

Wartość optymalna funkcji celu $z=z^*+{\bf c}_B^{-1}{\bf b}= 0+[\frac{3}{5},\frac{4}{5},0]\left[ \begin{array}{r} 12\\ 10 \\ -4 \end{array} \right] = \frac{36}{5} + \frac{40}{5} = \frac{76}{5}$