01LIP:Kapitola4
Z WikiSkripta FJFI ČVUT v Praze
Verze z 1. 8. 2010, 01:40, kterou vytvořil Admin (diskuse | příspěvky) (Založena nová stránka: %\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...)
| [ znovu generovat, | výstup z překladu ] | Kompletní WikiSkriptum včetně všech podkapitol. | |
| PDF Této kapitoly | [ znovu generovat, | výstup z překladu ] | Přeložení pouze této kaptioly. |
| ZIP | Kompletní zdrojový kód včetně obrázků. |
Součásti dokumentu 01LIP
| součást | akce | popis | poslední editace | soubor | |||
|---|---|---|---|---|---|---|---|
| Hlavní dokument | editovat | Hlavní stránka dokumentu 01LIP | Admin | 1. 8. 2010 | 01:38 | ||
| Řídící stránka | editovat | Definiční stránka dokumentu a vložených obrázků | Admin | 7. 9. 2015 | 13:46 | ||
| Header | editovat | Hlavičkový soubor | Admin | 1. 8. 2010 | 01:39 | header.tex | |
| Kapitola1 | editovat | Úvod | Admin | 1. 8. 2010 | 01:40 | kapitola1.tex | |
| Kapitola2 | editovat | Dualita v LP | Pohanjur | 3. 7. 2011 | 20:33 | kapitola2.tex | |
| Kapitola3 | editovat | Simplexová metoda | Karel.brinda | 13. 9. 2010 | 17:32 | kapitola3.tex | |
| Kapitola4 | editovat | Princip dekompozice | Admin | 1. 8. 2010 | 01:40 | kapitola4.tex | |
| Kapitola5 | editovat | Celočíselné programování | Admin | 1. 8. 2010 | 01:40 | kapitola5.tex | |
| Kapitola6 | editovat | Aplikace lineárního programování v teorii her | Admin | 1. 8. 2010 | 01:41 | kapitola6.tex | |
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í.
