Zdrojový kód
%\wikiskriptum{01LIP}
\section{Princip dekompozice}
Řešme opět úlohu
\begin{align*}
\min z&=cx\\
\A x&=b\\
x&\ge 0
\end{align*}
a předpokládejme, že matice $\A$ má tvar
\[
\A=
\begin{pmatrix}
\L_1 & \L_2 & \cdots & \L_p\\
\A_1 & & & \\
& \A_2 & & 0 \\
& & \ddots & \\
& 0 & & \A_p
\end{pmatrix}.
\]
To v~praxi nastane například když matice $\L_j$ popisují procesy v~rámci
celého závodu a matice $\A_j$ jeho části. Dále nechť
$\L_j\in\R^{m_0,n_j}$, $\A_j\in\R^{m_j,n_j}$, $c=(c_1,\dots,c_p)$, $c_j\in\R^{n_j}$,
\begin{align*}
b&=
\begin{pmatrix}
b_0\\b_1\\ \vdots \\b_p
\end{pmatrix},\quad b_j\in\R^{m_j,1},&
x&=
\begin{pmatrix}
x_1\\x_2\\ \vdots \\x_p
\end{pmatrix},\quad x_j\in\R^{n_j,1}.
\end{align*}
Úlohu přepíšeme pomocí nového značení.
\begin{align*}
\min z&=\sum_{j=1}^p c_jx_j\\
\sum_{j=1}^p \L_jx_j&=b_0\\
\A_jx_j&=b_j,\quad j\in\hat p\\
x_j&\ge 0,\quad j\in\hat p.
\end{align*}
Označme $\S_j\equiv\A_jx_j=b_j,\ x_j\ge 0$ pro $j\in\hat
p$. Předpokládejme, že $\S_j$ jsou neprázdné a omezené. Protože $\S_j$
je konvexní, platí, že $\S_j=\kob{x_{1j},\dots,x_{s_j j}}$, kde
$x_{1j},\dots,x_{s_j j}$ jsou jeho vrcholy. Potom složky řešení $x$
lze vyjádřit jako konvexní kombinace
\begin{align*}
x_j&=\sum_{i=1}^{s_j}\lambda_{ij}x_{ij},\quad j\in\hat p&
\sum_{i=1}^{s_j}\lambda_{ij}=1,\quad\lambda_{ij}\ge 0.
\end{align*}
Účelovou funkci $z$ lze dále zapsat jako
\[
z=\sum_{j=1}^p c_j\sum_{i=1}^{s_j}\lambda_{ij}x_{ij}=
\sum_{j=1}^p\sum_{i=1}^{s_j}
\underbrace{c_{j}x_{ij}}_{\text{ozn. }c_{ij}}
\lambda_{ij}
\]
a první část soustavy rovnic jako
\[
\sum_{j=1}^p\L_jx_j=\sum_{j=1}^p\L_j\sum_{i=1}^{s_j}\lambda_{ij}x_{ij}=
\sum_{j=1}^p\sum_{i=1}^{s_j}
\underbrace{\L_jx_{ij}}_{l_{ij}}
\lambda_{ij}=b_0.
\]
Tím jsme problém převedli na hledání
\begin{align*}
\min z&=\sum_{j=1}^{p}\sum_{i=1}^{s_j}c_{ij}\lambda_{ij}\\
\sum_{j=1}^{p}\sum_{i=1}^{s_j}l_{ij}\lambda_{ij}&=b_0\\
\sum_{i=1}^{s_j}\lambda_{ij}&=1,\quad j\in\hat p\\
\lambda_{ij}&\ge 0.
\end{align*}
Původní počet rovnic byl $m_0+\sum_{j=1}^p m_j$, teď máme pouze
$m_0+p$ rovnic. Počet proměnných byl $\sum_{j=1}^p n_j$, teď jich je
$\sum_{j=1}^p s_j$. To je obvykle víc, což ale není tak podstatné,
protože náročnost určuje převážně počet rovnic.
Problém je ale s~nalezením vrcholů, abychom měli koeficienty $c_{ij}$
a $l_{ij}$. Naštěstí jich stačí pro začátek najít pouze $m_0+p$. Z
počáteční tabulky tak budeme mít k~dispozici pouze $m_0+p$ sloupců,
které budou tvořit matici $\B$. Pak použijeme redukovanou
simplexovou metodu. Matice celé soustavy bude mít na počátku tvar
\[
\left(
\begin{array}{ccccccccccc}
c_{11} & c_{21} & \hdots & c_{s_1 1} & \hdotsfor{3} & c_{1p} & c_{2p} &
\hdots & c_{s_pp}\\
l_{11} & l_{21} & \hdots & l_{s_1 1} & \hdotsfor{3} & l_{1p} & l_{2p} &
\hdots & l_{s_pp}\\
1 & 1 & \hdots & 1 & 0 & \hdots & 0 & 0 & 0 & \hdots & 0\\
0 & 0 & \hdots & 0 & 1 & \hdots & 1 & 0 & 0 & \hdots & 0\\
\hdotsfor{11}\\
0 & 0 & \hdots & 0 & 0 & \hdots & 0 & 1 & 1 & \hdots & 1
\end{array}
\right).
\]
Označme $(\pi,\opi)$ vektor $\pi$ (viz Modifikovaná simplexová
metoda), $\opi=(\opi_1,\dots,\opi_p)$. Potom další vektor $c$ se
vypočte pomocí vztahu
\[
\overline{c_{ij}}=c_{ij}-(\pi,\opi)
\begin{pmatrix}
l_{ij}\\e_j^T
\end{pmatrix}
=c_{ij}-\pi l_{ij}-\opi_j,
\]
kde $e_j$ je $j$-tý vektor ze standardní báze. Problém je ale v~tom,
jak najít vedoucí sloupec, když jiná $c_{ij}$ než ta bazická
neznám. Pomocí simplexové metody proto najdeme-
\[\min_i(c_{ij}-\pi l_{ij}-\opi_j)\]
při pevně zvoleném $j$, což je ekvivalentní hledání minima
\[
\min_i(c_{ij}-\pi l_{ij})=\min_i(c_jx_{ij}-\pi L_jx_{ij})=
\min_i(c_j-\pi L_j)x_{ij}=\min_{x_j\in\S_{j}}(c_j-\pi L_j)x_j.
\]
To najdeme simplexovou metodou, nakonec odečteme ještě $\opi_j$. To
provádíme postupně pro $j\in 1,\dots,p$, dokud není minimum
záporné. Pokud se záporné minimum nenajde, je tabulka optimální.
