01LIP:Kapitola5

Z WikiSkripta FJFI ČVUT v Praze
Přejít na: navigace, hledání
PDF [ 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.
ZIPKompletní zdrojový kód včetně obrázků.

Součásti dokumentu 01LIP

součástakcepopisposlední editacesoubor
Hlavní dokument editovatHlavní stránka dokumentu 01LIPAdmin 1. 8. 201001:38
Řídící stránka editovatDefiniční stránka dokumentu a vložených obrázkůAdmin 7. 9. 201513:46
Header editovatHlavičkový souborAdmin 1. 8. 201001:39 header.tex
Kapitola1 editovatÚvodAdmin 1. 8. 201001:40 kapitola1.tex
Kapitola2 editovatDualita v LPPohanjur 3. 7. 201120:33 kapitola2.tex
Kapitola3 editovatSimplexová metodaKarel.brinda 13. 9. 201017:32 kapitola3.tex
Kapitola4 editovatPrincip dekompoziceAdmin 1. 8. 201001:40 kapitola4.tex
Kapitola5 editovatCeločíselné programováníAdmin 1. 8. 201001:40 kapitola5.tex
Kapitola6 editovatAplikace lineárního programování v teorii her Admin 1. 8. 201001: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}