01LIP:Kapitola5: Porovnání verzí
Z WikiSkripta FJFI ČVUT v Praze
(Založena nová stránka: %\wikiskriptum{01LIP} \section{Celočíselné programování} Řešíme úlohu \begin{align*} \min z&=cx\\ \A x&=b\\ x&\ge 0\\ x&\in\Z^{n,1}. \end{align*} \subsection{Gom...) |
(Žádný rozdíl)
|
Aktuální verze z 1. 8. 2010, 02:40
[ 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 | 02:38 | ||
Řídící stránka | editovat | Definiční stránka dokumentu a vložených obrázků | Admin | 7. 9. 2015 | 14:46 | ||
Header | editovat | Hlavičkový soubor | Admin | 1. 8. 2010 | 02:39 | header.tex | |
Kapitola1 | editovat | Úvod | Admin | 1. 8. 2010 | 02:40 | kapitola1.tex | |
Kapitola2 | editovat | Dualita v LP | Pohanjur | 3. 7. 2011 | 21:33 | kapitola2.tex | |
Kapitola3 | editovat | Simplexová metoda | Karel.brinda | 13. 9. 2010 | 18:32 | kapitola3.tex | |
Kapitola4 | editovat | Princip dekompozice | Admin | 1. 8. 2010 | 02:40 | kapitola4.tex | |
Kapitola5 | editovat | Celočíselné programování | Admin | 1. 8. 2010 | 02:40 | kapitola5.tex | |
Kapitola6 | editovat | Aplikace lineárního programování v teorii her | Admin | 1. 8. 2010 | 02:41 | kapitola6.tex |
Zdrojový kód
%\wikiskriptum{01LIP} \section{Celočíselné programování} Řešíme úlohu \begin{align*} \min z&=cx\\ \A x&=b\\ x&\ge 0\\ x&\in\Z^{n,1}. \end{align*} \subsection{Gomoryho algoritmus} Nejdřív vyřeším úlohu bez podmínky celočíselnosti. Pokud je řešení celočíselné, končím. Pokud ne, vyberu jakoukoli rovnici, ve které je na levé straně tabulky simplexové metody necelé číslo --- tzv. {\bf vytvořující rovnice}. Označme \[B=\{j\in\hat n|x_j\text{ je bazická v~optimální tabulce neceločíselné úlohy}\}.\] Vytvořující rovnice má tvar \[x+\sum_{j\not\in B}a_jx_j=a_0,\] kde $a_0\not\in\Z$, neboli \[x=a_0-\sum_{j\not\in B}a_jx_j.\] Číslo \[a_0-\sum_{j\not\in B}a_jx_j\] tedy musí být celé pro každé přípustné řešení celočíselné úlohy. Označme $f_0=a_0-[a_0]$, tedy $f_0\in\la 0,1)$, $f_j=a_j-[a_j]$ pro $j\not\in B$, tedy $f_j\in\la 0,1)$. Předchozí výraz lze pak přepsat \[f_0+[a_0]-\sum_{j\not\in B}(f_j+[a_j])x_j\in\Z,\] to je ekvivalentní \[f_0-\sum_{j\not\in B}f_jx_j\in\Z\] pro každé přípustné řešení celočíselné úlohy. Suma může nabývat pouze hodnot $f_0,f_0+1,f_0+2,\dots$. Do soustavy rovnic proto přidáme rovnici \[\sum_{j\not\in B}f_jx_j\ge f_0.\] Všechna celočíselná řešení zůstala, ale množina neceločíselných řešení se zmenšila, například původní optimální řešení tam už nepatří. Nerovnici převedeme na rovnici \[\sum_{j\not\in B}f_jx_j-s=f_0,\quad s\ge 0,s\in\Z\] a rovnici vynásobíme $-1$ \[s-\sum_{j\not\in B}f_jx_j=-f_0,\quad s\ge 0,s\in\Z.\] K~tabulce tak přibude řádek. Nová tabulka není primárně přípustná, ale je duálně přípustná, takže se použije duální simplexová metoda. Je možné dokázat, že po konečném počtu kroků nalezneme přípustné řešení. \subsection{Smíšené programování} Řešíme úlohu \begin{align*} \min z&=cx\\ \A x&=b\\ x&\ge 0\\ x_j&\in\Z,\quad j\in\J\subset\hat n,\ \J\not=\hat n. \end{align*} Nejdřív opět vyřešíme neceločíselnou úlohu. Nechť optimální tabulka nesplňuje podmínku celočíselnosti. Buď opět $B$ množina indexů bazických proměnných. Nechť vytvořující rovnice má tvar \[x+\sum_{j\not\in B}a_jx_j=a_0,\quad a_0\not\in\Z,\] \[x=a_0-\sum_{j\not\in B}a_jx_j.\] Pak musí pro každé přípustné řešení smíšené úlohy platit \[a_0-\sum_{j\not\in B}a_jx_j\in\Z.\] Buď $f_0=a_0-[a_0]\in(0,1)$, potom předchozí podmínka je ekvivalentní s \[f_0-\sum_{j\not\in B}a_jx_j\in\Z.\] Buďte dále $\J^+=\{j\not\in B|a_j\ge 0\}$, $\J^-=\{j\not\in B|a_j<0\}$, je $\hat n\sm B=\J^+\cup\J^-$ Pokud je \[\sum_{j\not\in B}a_jx_j\ge 0,\] musí suma nabývat hodnot $f_0,f_0+1,f_0+2,\dots$, tedy \[\sum_{j\not\in B}a_jx_j\ge f_0.\] Pokud je \[\sum_{j\not\in B}a_jx_j<0,\] musí nabývat hodnot $f_0-1,f_0-2,\dots$, tedy \[\sum_{j\not\in B}a_jx_j\le f_0-1.\] \[\sum_{j\in\J^+}a_jx_j\ge\sum_{j\in\J^+}a_jx_j+\sum_{j\in\J^-}a_jx_j= \sum_{j\not\in B}a_jx_j\ge f_0\] \[\sum_{j\in\J^-}a_jx_j\le\sum_{j\not\in B}a_jx_j\le f_0-1\iff \sum_{j\in\J^-}\frac{f_0}{f_0-1}a_jx_j\ge f_0.\] Protože ve druhé podmínce je $(f_0/(f_0-1))a_j>0$ ($a_j<0$ a $f_0\in\la 0,1)$), k~soustavě přidáme novou podmínku (spadla z nebe, nicméně snadno ověříme, že je ve shodě s výše uvedenými nerovnostmi) \[\sum_{j\in\J^+}a_jx_j+ \sum_{j\in\J^-}\frac{f_0}{f_0-1}a_jx_j\ge f_0,\] ovšem převedenou na rovnici %\[\sum_{j\not\in B}a_jx_j+ %\sum_{j\in\J^-}\frac{f_0}{f_0-1}a_jx_j-s=f_0.\] \[-\sum_{j\in\J^+}a_jx_j -\sum_{j\in\J^-}\frac{f_0}{f_0-1}a_jx_j+s=-f_0,\] kde $s\ge 0$. Dále, stejně jako v~předchozím případě, pokračujeme duální simplexovou metodou. Pokud vezmeme v~úvahu i celočíselnost jiných proměnných, lze vyrobit lepší podmínku: \begin{enumerate} \item Je-li $x_j\in\Z$ a $a_j\in\Z$, lze sčítanec vynechat. \item Je-li $x_j\in\Z$ a $a_j\not\in\Z$, potom \begin{enumerate} \item pro $j\in\J^+$ lze $a_j$ nahradit $f_j=a_j-[a_j]$, \item pro $j\in\J^-$ lze za celý koeficient dosadit $f_j$ nebo jen za $a_j$ dosadit $f_j-1$. Porovnáme \[\min\left\{ f_j,\frac{f_0}{f_0-1}(f_j-1) \right\}.\] Zřejmě $\min=f_j$, právě když $f_j\le f_0$. \end{enumerate} \end{enumerate} Koeficienty $f^*$ v~podmínce \[\sum_{j\not\in B}f_j^* x_j\ge f_0\] tedy volíme následovně: $$ f_j^* = \begin{cases} a_j & \dots x_j\not\in\Z,\ a_j\ge 0\\ \frac{f_0}{f_0-1}a_j & \dots x_j\not\in\Z,\ a_j<0\\ 0 & \dots x_j\in\Z,\ a_j\in\Z\\ f_j & \dots x_j\in\Z,\ f_j\le f_0\\ \frac{f_0}{f_0-1}(f_j-1) & \dots x_j\in\Z,\ f_j>f_0 \end{cases} $$ \subsection{Plně celočíselný algoritmus lineárního programování} Algoritmus řeší úlohu LP v~kanonickém tvaru, která zůstává celočíselná, vychází se z~{\bf duálně přípustné tabulky}. Z~toho budeme vycházet při tvorbě přídavné podmínky. Tu je nutné vytvořit tak, aby byl pivot roven $-1$ a vyhnuli jsme se tak dělení. Při odvozování se bude hodit \begin{theorem} Nechť $y\in\R$, $\lambda>0$. Potom existuje $r\in\la 0,\lambda)$ takové, že \[y=\left[\frac{y}{\lambda}\right]\lambda+r.\] \end{theorem} Označíme opět \[B=\{j\in\hat n|x_j\text{ je bazická}\}.\] \[a_0=x+\sum_{j\not\in B}a_jx_j\] \[a_0=\left[\frac{a_0}{\lambda}\right]\lambda+r_0= x+\sum_{j\not\in B}\left( \left[\frac{a_j}{\lambda}\right]\lambda+r_j \right)x_j\] \[x+\sum_{j\not\in B}r_jx_j=r_0+\lambda\underbrace{\left( \left[\frac{a_0}{\lambda}\right]-\sum_{j\not\in B}\left[ \frac{a_j}{\lambda}\right]x_j \right)}_s\] Pro přípustné řešení je $s\in\Z$ a $s\ge 0$, neboť levá strana je nezáporná a $r_0<\lambda$. Kdyby $s\le-1$, byla by pravá strana záporná. \[s=\left[\frac{a_0}{\lambda}\right]- \sum_{j\not\in B}\left[\frac{a_j}{\lambda}\right]x_j\] Alespoň jedno $a_j<0$, jinak by úloha neměla přípustné řešení, neboť $a_0<0$. Číslo $\lambda$ musíme zvolit dostatečně vysoké, aby byla v~sumě alespoň jedna $-1$. Současně je ale vhodné zvolit $\lambda$ co nejmenší možné, aby algoritmus rychle konvergoval. Neexistuje univerzální recept, jak $\lambda$ volit. Obvykle vyhovuje následující postup. Nechť vedoucí řádek má tvar \[a_{v0}=x+\sum_{j\not\in B}a_{vj}x_j\] a nechť $s$ je lexikograficky nejmenší sloupec ze sloupců, pro které je $a_{vj}<0$. Pro $j$ taková, že $a_{vj}<0$ definujeme \[\mu_j=\left[\frac{a_{0j}}{a_{0s}}\right]\in\N,\] $\mu_j\in\N$ díky tomu, že sloupec $s$ je lexikograficky nejmenší. Pokud je $a_{0s}=0$, zvolíme rovnou $\lambda=-a_{vs}$. Buď \[\lambda_j=-\frac{a_{vj}}{\mu_j}\] a \[\lambda=\max\{\lambda_j|a_{vj}<0\}\ge 1,\] neboť $a_{vj}<0$ a tedy $a_{vj}\le -1$, protože $a_{vj}\in\Z$. Protože je $\mu_s=1$, je $\lambda_s=-a_{vs}\ge 1$. Pokud $\lambda=1$, je $\lambda_s=1$ a není nutné přidávat další podmínku, protože už tam $-1$ mám. \begin{enumerate} \item Ověříme, že pivot je $-1$. \[-1\ge\left[\frac{a_{vs}}{\lambda}\right]\ge \left[\frac{a_{vs}}{\lambda_s}\right]=[-\mu_s]=-1\implies \left[\frac{a_{vs}}{\lambda}\right]=-1.\] \item Ověříme soulad s~prověrkou poměrů. Hledá se minimum z poměrů v absolutní hodnotě, takže musí platit \[\frac{a_{0s}}{\left[\frac{a_{vs}}{\lambda}\right]}\ge \frac{a_{0j}}{\left[\frac{a_{vj}}{\lambda}\right]} \iff a_{0s}\le\frac{a_{0j}}{-\left[\frac{a_{vj}}{\lambda}\right]} \iff -\left[\frac{a_{vj}}{\lambda}\right]\le\frac{a_{0j}}{a_{0s}}. \] Protože je \[ -\left[\frac{a_{vj}}{\lambda}\right]\le -\left[\frac{a_{vj}}{\lambda_j}\right]= -[-\mu_j]=\mu_j= \left[\frac{a_{0j}}{a_{0s}}\right]\le \frac{a_{0j}}{a_{0s}}, \] nerovnost platí. \end{enumerate}