Tiesinio programavimo uždavinys 4.
S
1
S
2
S
3
5
10
10
G
1
15
7
5
4
G
1
10
5
4
2
Tikslo funkcija:
$z_{ij}=$ $7x_{11}+5x_{12}+4x_{13}+5x_{21}+4x_{22}+2x_{23};$
$\begin{cases}x_{11}+x_{12}+x_{13}=15,\\x_{21}+x_{22}+x_{23}=10,\\x_{11}+x_{21}=5,\\x_{12}+x_{22}=10,\\x_{13}+x_{23}=10,\\x_{11}\geqslant0;x_{12}\geqslant0;x_{13}\geqslant0;x_{21}\geqslant0;x_{22}\geqslant0;x_{23}\geqslant0;\end{cases}$
$Rasti\;min\;z_{ij}=min(7x_{11}+5x_{12}+4x_{13}+5x_{21}+4x_{22}+2x_{23});$
$\left(\begin{array}{rrrrrr|r}1 &1 &1 &0 &0 &0 &15 \\0 &0 &0 &1 &1 &1 &10 \\1 &0 &0 &1 &0 &0 &5 \\0 &1 &0 &0 &1 &0 &10 \\0 &0 &1 &0 &0 &1 &10\end{array}\right)$ $\left.\begin{array}{c}\leftarrow \\\; \\\; \\\; \\\leftarrow \end{array}\right.\sim$ $\left(\begin{array}{rrrrrr|r}0 &0 &1 &0 &0 &1 &10 \\0 &0 &0 &1 &1 &1 &10 \\1 &0 &0 &1 &0 &0 &5 \\0 &1 &0 &0 &1 &0 &10 \\1 &1 &1 &0 &0 &0 &15\end{array}\right)$ $\left.\begin{array}{c}\; \\\leftarrow \\\; \\\leftarrow \\\;\end{array}\right.\sim$
$\sim\left(\begin{array}{rrrrrr|r}0 &0 &1 &0 &0 &1 &10 \\0 &1 &0 &0 &1 &0 &10 \\1 &0 &0 &1 &0 &0 &5 \\0 &0 &0 &1 &1 &1 &10 \\1 &1 &1 &0 &0 &0 &15\end{array}\right)$ $\left.\begin{array}{c}\leftarrow \\\; \\\leftarrow \\\; \\\;\end{array}\right.\sim$ $\left(\begin{array}{rrrrrr|r}1 &0 &0 &1 &0 &0 &5 \\0 &1 &0 &0 &1 &0 &10 \\0 &0 &1 &0 &0 &1 &10 \\0 &0 &0 &1 &1 &1 &10 \\1 &1 &1 &0 &0 &0 &15\end{array}\right)$ $\left.\begin{array}{c}\;\times\text{(-1)} \\\; \\\; \\\; \\\leftarrow \text{+} \end{array}\right.\sim$
$\sim\left(\begin{array}{rrrrrr|r}1 &0 &0 &1 &0 &0 &5 \\0 &1 &0 &0 &1 &0 &10 \\0 &0 &1 &0 &0 &1 &10 \\0 &0 &0 &1 &1 &1 &10 \\0 &1 &1 &-1 &0 &0 &10\end{array}\right)$ $\left.\begin{array}{c}\; \\\;\times\text{(-1)} \\\; \\\; \\\leftarrow \text{+} \end{array}\right.\sim$ $\left(\begin{array}{rrrrrr|r}1 &0 &0 &1 &0 &0 &5 \\0 &1 &0 &0 &1 &0 &10 \\0 &0 &1 &0 &0 &1 &10 \\0 &0 &0 &1 &1 &1 &10 \\0 &0 &1 &-1 &-1 &0 &0\end{array}\right)$ $\left.\begin{array}{c}\; \\\; \\\;\times\text{(-1)} \\\; \\\leftarrow \text{+} \end{array}\right.\sim$
$\sim\left(\begin{array}{rrrrrr|r}1 &0 &0 &1 &0 &0 &5 \\0 &1 &0 &0 &1 &0 &10 \\0 &0 &1 &0 &0 &1 &10 \\0 &0 &0 &1 &1 &1 &10 \\0 &0 &0 &-1 &-1 &-1 &-10\end{array}\right)$ $\left.\begin{array}{c}\; \\\; \\\; \\\;\times\text{1} \\\leftarrow \text{+} \end{array}\right.\sim$ $\left(\begin{array}{rrrrrr|r}1 &0 &0 &1 &0 &0 &5 \\0 &1 &0 &0 &1 &0 &10 \\0 &0 &1 &0 &0 &1 &10 \\0 &0 &0 &1 &1 &1 &10 \\0 &0 &0 &0 &0 &0 &0\end{array}\right)$ $\left.\begin{array}{c}\; \\\; \\\; \\\;\end{array}\right.\sim$
$\sim\left(\begin{array}{rrrrrr|r}1 &0 &0 &1 &0 &0 &5 \\0 &1 &0 &0 &1 &0 &10 \\0 &0 &1 &0 &0 &1 &10 \\0 &0 &0 &1 &1 &1 &10\end{array}\right)$ $;\;\;\;\;\begin{cases}x_{11}+x_{21}=5,\\x_{12}+x_{22}=10,\\x_{13}+x_{23}=10,\\x_{21}+x_{22}+x_{23}=10;\\\end{cases}\Rightarrow$ $\;\;\;\;\begin{cases}x_{11}+x_{21}=5,\\x_{12}=10-x_{22},\\x_{13}=10-x_{23},\\x_{21}=10-x_{22}-x_{23};\\\end{cases}\Rightarrow$
$\;\;\;\;\begin{cases}x_{11}=5-(10-x_{22}-x_{23}),\\x_{12}=10-x_{22},\\x_{13}=10-x_{23},\\x_{21}=10-x_{22}-x_{23};\\\end{cases}\Rightarrow$ $\;\;\;\;\begin{cases}x_{11}=-5+x_{22}+x_{23},\\x_{12}=10-x_{22},\\x_{13}=10-x_{23},\\x_{21}=10-x_{22}-x_{23};\\\end{cases}\Rightarrow$ $\;\;\;\;\begin{cases}x_{11}=-5+x_{22}+x_{23},\\x_{12}=10-x_{22},\\x_{13}=10-x_{23},\\x_{21}=10-x_{22}-x_{23},\\x_{22}\geqslant0,\\x_{23}\geqslant0;\end{cases}$
$min\;z_{ij}=min(7x_{11}+5x_{12}+4x_{13}+5x_{21}+4x_{22}+2x_{23})=\\=min(7(-5+x_{22}+x_{23})+5(10-x_{22})+4(10-x_{23})+5(10-x_{22}-x_{23})+4(x_{22})+2(x_{23}))=x_{22} + 105;$
x
22
turi būti kuo mažesnis ir neneigiamas, todėl x
22
= 0.
x
23
eliminuotas iš išraiškos, todėl galibūti bet koks, kad kiti kintamieji gautųsi neneigiami.
Primame x
23
= 5. Tada min z=105.
Kiekiai
S
1
S
2
S
3
G
1
0
10
5
G
1
5
0
5
Kainos
S
1
S
2
S
3
G
1
0
50
20
G
1
25
0
10