LIP:Kapitola3: Porovnání verzí

Z WikiSkripta FJFI ČVUT v Praze
Přejít na: navigace, hledání
(Založena nová stránka: % následující řádky upravují pouze zobrazení stránky na wiki na obsah dokumentu nemají vliv - prosím neměnit ! %\parentlatexfile{LIPskriptum} %% odkaz na hlavn…)
 
Řádka 1: Řádka 1:
 +
\section{Simplexová metoda}
 +
 +
Simplexová metoda se používá k~řešení úlohy v~kanonickém tvaru
 +
\begin{align*}
 +
\min z& =cx\\
 +
\A x& = b\\
 +
x& \ge 0.
 +
\end{align*}
 +
 +
Tabulka simplexové metody: Matici soustavy rovnic $\A x=b$
 +
\[
 +
\begin{array}{lllllllllllcl}
 +
-z &    &    &        &    & + & a_{0,m+1} &+& \cdots &+& a_{0n} &= &a_{00}\\
 +
  & x_1 &    &        &    & + & a_{1,m+1} &+& \cdots &+& a_{1n} &= &a_{10}\\
 +
  &    & x_2 &        &    & + & a_{2,m+1} &+& \cdots &+& a_{2n} &= &a_{20}\\
 +
  &    &    & \ddots &    &  &          & &        & &        &\vdots  &\\
 +
  &    &    &        & x_m & + & a_{m,m+1} &+& \cdots &+& a_{mn} &= &a_{m0}
 +
\end{array}
 +
\]
 +
zapisujeme do tabulky
 +
\[
 +
\left(
 +
\begin{array}{c|cccccc}
 +
a_{00} & 0 & \hdots & 0 & a_{0,m+1} & \hdots & a_{0n}\\
 +
\hline
 +
a_{10} & 1 & \hdots & 0 & a_{1,m+1} & \hdots & a_{1n}\\
 +
\vdots & \vdots & \ddots & \vdots & \vdots & & \vdots\\
 +
a_{m0} & 0 & \hdots & 1 & a_{m,m+1} & \hdots & a_{mn}\\
 +
\end{array}
 +
\right)
 +
\]
 +
 +
Pokud $a_{i0}\ge 0$ pro $i\in\hat m$, nazýváme tabulku {\bf primárně
 +
přípustnou}, je-li $a_{0i}\ge 0$, nazýváme tabulku {\bf duálně
 +
přípustnou}.
 +
 +
Je-li tabulka primárně přípustná, vyjadřuje přípustné řešení primární
 +
úlohy.
 +
 +
 +
\subsection{Algoritmus simplexové metody}
 +
 +
\begin{enumerate}
 +
\item Vyjdu z~primárně přípustné tabulky.
 +
\item Je-li tabulka i~duálně přípustná, je optimální a končím.
 +
\item Pokud není duálně přípustná, mezi sloupci, kde $a_{0i}<0$ vyberu
 +
nějaký {\bf vedoucí sloupec} ($s$-tý).
 +
\item Vyberu {\bf vedoucí řádek}: najdu
 +
\[\min\left\{\left.
 +
\frac{a_{i0}}{a_{is}}\right|
 +
a_{is}>0
 +
\right\}=\frac{a_{r0}}{a_{rs}}\ge 0\]
 +
(tzv. {\bf prověrka poměrů}) a jako vedoucí zvolím $r$-tý. $x_r$ bude
 +
nová nebazická proměnná a položím
 +
\[x_s=\frac{a_{r0}}{a_{rs}}.\]
 +
Prvek $a_{rs}$ nazýváme {\bf vedoucí prvek} ({\bf pivot}).
 +
Pokud jsou všechny $a_{is}\le 0$, není účelová funkce $z$ omezená,
 +
takže končím.
 +
\end{enumerate}
 +
Pokud je v~prvním sloupci nějaká nula, prověrka poměrů dá nulu a jsem
 +
v~blbé situaci, protože nemůžu bezprostředně přejít k~jinému vrcholu.
 +
 +
\subsection{Časová náročnost}
 +
Teoreticky je exponenciální: maximálně $\binom{m}{n}$.
 +
\[n!\approx\frac{n^n}{e^n}\sqrt{2\pi n}\]
 +
\[\binom{n}{\frac n2}=\frac{n!}{\left(\left(\frac n2\right)!\right)^2}
 +
\approx\frac{\frac{n^n}{e^n}\sqrt{2\pi n}}
 +
{\frac{\left(\frac{n}{2}\right)^n}{e^n}\pi n}= 2^n\sqrt{\frac{2}{\pi
 +
n}},\]
 +
tj. řádově $2^n$. V~praxi se to ale chová polynomiálně, obvykle
 +
stačí cca. $2m$ až $3m$ iterací.
 +
 +
\subsection{Nalezení počátečního přípustného bazického řešení}
 +
\begin{enumerate}
 +
\item
 +
Do každé rovnice přidáme tzv. {\bf umělou proměnnou} $x_i'\ge 0$.
 +
Dostanu tak soustavu
 +
\begin{align*}
 +
x_1'+\sum_{j=1}^n a_{1j}x_j&=b_1\\
 +
&\xvdots\\
 +
x_m'+\sum_{j=1}^n a_{mj}x_j&=b_m\\
 +
\min\xi&=\min\sum_{j=1}^m x_j'
 +
\end{align*}
 +
položím $x_1',\dots,x_m'=b_1,\dots,b_m$, $x_j=0$ pro $j\in\hat n$.
 +
\begin{enumerate}
 +
\item Je-li $\xi_{min}>0$, neexistuje přípustné řešení výchozí úlohy.
 +
\item Je-li $\xi_{min}=0$, je $x$ přípustné řešení.
 +
\end{enumerate}
 +
\item Nerovnice typu $\A x\le b$, $b\ge 0$, $x\ge 0$ převedu na rovnice
 +
se slabou proměnnou a slabé proměnné položím rovny $b$. {\bf Slabé
 +
proměnné nejsou v~účelové funkci !}
 +
\item Nerovnice typu
 +
\[\sum_{j=1}^n a_{ij}x_j\ge b_i,\quad i\in k,\ b_i\ge 0\]
 +
převedu na rovnice se slabou proměnnou a do každé z~nich přidám {\bf
 +
stejnou} umělou proměnnou $x'$:
 +
\[x'+\sum_{j=1}^n a_{ij}x_j-s_i=b_i,\quad s_i\ge 0,\ x'\ge 0.\]
 +
Buď $\max\{b_i|i\in\hat k\}=b_l$. Soustavu nerovnic převedeme na novou
 +
soustavu
 +
\begin{align*}
 +
x'+\sum_{j=1}^n a_{lj}x_j-s_l&=b_l\\
 +
\sum_{j=1}^n(a_{lj}-a_{ij})x_j-s_l+s_i&=
 +
\underbrace{b_l-b_i}_{\ge 0},\quad i\in\hat k\sm\{l\}.
 +
\end{align*}
 +
Proměnnou $s_l$ položím rovnou nule a proměnné $x'$ a $s_i$
 +
dopočítám. Minimalizuji funkci $\xi=x'$. Neuškodí zopakovat, že {\bf v
 +
účelové funkci se v~každém případě vyskytují pouze umělé proměnné}.
 +
\end{enumerate}
 +
Pokud mám soustavu, kde jsou rovnice i~nerovnice, lze tyto postupy
 +
samozřejmě kombinovat.
 +
 +
\subsection{Zacyklení --- jak z~toho ven}
 +
 +
Zacyklením nazýváme situaci, kdy se při prověrce poměrů vyjde
 +
nula. V~následujícím kroku se pak nezmění hodnota účelové funkce,
 +
protože se k~ní tato nula přičte.
 +
 +
\begin{define}
 +
Buď $x\in\R^n$, $x\not=0$. Vektor $x$ nazýváme {\bf lexikograficky
 +
kladný} ($x\lexgr 0$), právě když první nenulová složka vektoru $x$ je
 +
kladná. Pro dva různé vektory $x,y$ definujeme $x\lexgr y$, právě když
 +
$x-y\lexgr 0$.
 +
\end{define}
 +
 +
\begin{description}
 +
\item[Dantzig] Vycházíme z~toho, že prvky nultého řádku jsou
 +
jednoznačně určeny volbou báze. Vedoucí sloupec volím stejně,
 +
tj. sloupec, v~jehož prvním řádku je záporné číslo.
 +
 +
Volba vedoucího řádku: Na počátku musí být všechny řádky
 +
lexikograficky kladné (s~výjimkou nultého). Pokud nejsou, přečísluji
 +
neznámé tak, aby jednotková matice byla nalevo. Kandidáta na vedoucí
 +
řádek pak hledám mezi řádky, kde $a_{is}>0$. Pro každé $a_{is}>0$
 +
vezmu vektor $(a_{i0},a_{i1},\dots,a_{in})$ a vydělím $a_{is}$. Získám
 +
tak vektory
 +
\[\left(
 +
\frac{a_{i0}}{a_{is}},\frac{a_{i1}}{a_{is}},\dots,\frac{a_{in}}{a_{is}}
 +
\right).\]
 +
Z~těchto vektorů vyberu lexikograficky nejmenší ($r$-tý) a za vedoucí
 +
řádek zvolím $r$-tý řádek.
 +
\begin{proof}
 +
Dokážeme, že v~každé další tabulce bude nultý řádek lexikograficky
 +
větší a že řádky $1$ až $m$ zůstanou lexikograficky kladné.
 +
 +
Platí, že $a_{rs}>0$. Chceme dokázat, že pro $i$-tý řádek platí
 +
\[(a_{i0},\dots,a_{in})-\frac{a_{is}}{a_{rs}}
 +
(a_{r0},\dots,a_{rs})\lexgr 0.\]
 +
Pokud $a_{is}=0$, je to zřejmé. Je-li $a_{is}<0$, přičítám k~lexikograficky kladnému řádku lexikograficky kladný řádek, tedy $i$-tý
 +
řádek zůstane lexikograficky kladný. Pokud $a_{is}>0$, vydělím
 +
nerovnici $a_{is}$ a dostanu
 +
\[
 +
\left(\frac{a_{i0}}{a_{is}},\dots,\frac{a_{in}}{a_{is}}\right)
 +
\lexgr
 +
\left(\frac{a_{r0}}{a_{rs}},\dots,\frac{a_{rn}}{a_{rs}}\right).
 +
\]
 +
Protože jsem volil vedoucí řádek tak, aby vektor napravo byl
 +
lexikograficky nejmenší, je nerovnost splněna.
 +
 +
Pro nultý řádek nastává případ $a_{0s}<0$, přičítám k~němu
 +
lexikograficky kladný vektor, takže bude lexikograficky větší.
 +
\end{proof}
 +
 +
\item[Bland] Za vedoucí sloupec se zvolí sloupec odpovídající proměnné
 +
s~nejmenším indexem, stejně tak pro vedoucí řádek (vybírám řádek {\bf
 +
odpovídající proměnné s~nejmenším indexem}, nikoliv řádek s~nejmenším
 +
indexem) --- tzv. Blandovo pravidlo \uv{nejmenších indexů}.
 +
\begin{theorem}
 +
Při použití Blandova pravidla \uv{nejmenších indexů} nedojde k~zacyklení.
 +
\begin{proof}
 +
Větu dokážeme sporem. Předpokládejme, že máme degenerovanou úlohu,
 +
posloupnost tabulek je nekonečná a žádná z~tabulek není
 +
optimální. Proměnné rozdělíme na tři typy:
 +
\begin{enumerate}[1)]
 +
\item nikdy nejsou v~bázi,
 +
\item jsou stále v~bázi,
 +
\item vyskytují se jak v~bázi tak mimo bázi --- \uv{běhny}.
 +
\end{enumerate}
 +
Označme
 +
\begin{itemize}
 +
\item $x_t$ běhnu s~největším indexem,
 +
\item$D$ tabulku, v~níž je $x_t$ bazická, ale v~následující není
 +
bazická,
 +
\item $x_s$ proměnnou, která je v~D nebazická, ale v~následující je
 +
bazická,
 +
\item $D^*$ tabulku, v~níž je $x_t$ nebazická, ale v~následující je
 +
bazická,
 +
\item $v$ prvek $a_{00}$ všech tabulek (nemění se),
 +
\item $B=\{i\in\hat n|x_i\text{ je v $D$ bazická}\}$.
 +
\item Pokud řádek vektoru $b$ nebo matice $\A$ indexuji indexem $i\in
 +
B$ nějaké bazické proměnné, myslí se tím ten řádek, ve kterém je v
 +
$i$-tém sloupci jednotka.
 +
\end{itemize}
 +
Tabulka $D$ má tvar
 +
\begin{align*}
 +
z&=v+\sum_{j\not\in B}c_j x_j\\
 +
x_i&=b_i-\sum_{j\not\in B}a_{ij}x_j,\quad i\in B,
 +
\end{align*}
 +
nultý řádek tabulky $D^*$ má tvar
 +
\[z=v+\sum_{j=1}^n c_j^* x_j.\]
 +
Položme $x_s=y\in\R$, $x_j=0$ pro $j\not\in B$, $j\not=s$. Pak
 +
$x_i=b_i-a_{is}y$ pro $i\in B$ a
 +
\[z=v+c_sy=v+c_s^* y+
 +
\sum_{i\in B}c_i^*\underbrace{(b_i-a_{is}y)}_{x_i}.\]
 +
Pro každé $y\in\R$ pak platí
 +
\[\left(c_s-c_s^*+\sum_{i\in B}c_i^* a_{is}\right)y=
 +
\sum_{i\in B}c_i^* b_i.\]
 +
To je ale možné jen v~případě, že koeficienty u~$y$ jsou nulové, tedy
 +
\[c_s-c_s^*+\sum_{i\in B}c_i^* a_{is}=0.\]
 +
Platí, že $c_s<0$, protože $x_s$ jde v~$D$ do báze. Naopak $c_s^*\ge
 +
0$, protože do báze jde v~$D^*$ $x_t$ a kdyby $c_s^*<0$, podle
 +
Blandova pravidla by do báze šla $x_s$. Tedy $c_s-c_s^*<0$, z~čehož
 +
plyne, že alespoň jeden sčítanec v~sumě je kladný. Tedy existuje $i$
 +
takové, že $c_i^*a_{is}>0$.
 +
 +
Dokážeme, že $x_i$ je běhna a $i<t$. Protože $a_{ts}>0$ (je to pivot)
 +
a $c_t^*<0$ ($x_t$ jde do báze), je $c_t^* a_{ts}<0$. Je proto $i<t$,
 +
neboť $c_i^*a_{is}>0$.
 +
 +
Proměnná $x_i$ nemůže být v~$D^*$ bazická, protože $c_i^*\not=0$. Je
 +
to tedy běhna s~indexem menším než $t$.
 +
 +
Proměnná $x_i$ je ve všech tabulkách nulová. Pokud není v~bázi, je to
 +
jasné a když jde do báze, zůstane nulová, protože prověrka poměrů dá
 +
nulu a nulová zůstane i~dál, protože nultý sloupec se nemění. V~tabulce $D$ má hodnotu $b_i$, takže $b_i=0$.
 +
 +
Z~toho, že $x_i$ je běhna plyne, že $c_i^*>0$, jinak bych musel do
 +
báze podle Blandova pravidla zařadit $x_i$ a ne $x_t$. Protože
 +
$c_i^*>0$, je i $a_{is}>0$. Z~toho plyne, že řádek odpovídající $i$-té
 +
proměnné je rovněž kandidátem na vedoucí řádek. Prověrka poměrů dá
 +
nulu ($b_i=0$ a podle předpokladu i $b_t=0$), podle Blandova pravidla
 +
vybírám řádek odpovídající proměnné s~nejmenším indexem, takže
 +
v~tabulce $D$ se měl volit řádek odpovídající $i$-té proměnné, což je
 +
spor.
 +
\end{proof}
 +
\end{theorem}
 +
\end{description}
 +
 +
\subsection{Maticový zápis simplexového algoritmu}
 +
 +
Soustavu rovnic simplexové metody
 +
\begin{align*}
 +
z&=cx-a_{00}\\
 +
0&=-b+\A x
 +
\end{align*}
 +
lze zapsat maticově jako
 +
\[
 +
\begin{pmatrix}
 +
a_{00} & c \\
 +
b & \A
 +
\end{pmatrix}
 +
\begin{pmatrix}
 +
-1\\x
 +
\end{pmatrix}=
 +
\begin{pmatrix}
 +
z\\ 0
 +
\end{pmatrix}.
 +
\]
 +
Buďte $\A=(\B|\mathbf N)$, kde $\B$ je regulární, $c=(c_\B,c_{\mathbf
 +
N})$, $x=
 +
\begin{pmatrix}
 +
x_\B\\x_{\mathbf N}
 +
\end{pmatrix}
 +
$. Dosazením a vynásobením soustavy
 +
\[
 +
\left.
 +
\begin{pmatrix}
 +
a_{00} & c_\B & c_{\mathbf N} \\
 +
b & \B & \mathbf N
 +
\end{pmatrix}
 +
\begin{pmatrix}
 +
-1\\x_\B\\x_{\mathbf N}
 +
\end{pmatrix}=
 +
\begin{pmatrix}
 +
z\\ 0
 +
\end{pmatrix}
 +
\qquad
 +
\right|
 +
\cdot
 +
\begin{pmatrix}
 +
1 & -c_\B\B^{-1}\\
 +
0 & \B^{-1}
 +
\end{pmatrix}
 +
\text{ zleva}
 +
\]
 +
dostaneme
 +
\[
 +
\begin{pmatrix}
 +
a_{00}-c_B\B^{-1}b & 0 & c_{\mathbf N}-c_B\B^{-1}\mathbf N \\
 +
\B^{-1}b & \E & \B^{-1}\mathbf N
 +
\end{pmatrix}
 +
\begin{pmatrix}
 +
-1\\x_\B\\x_{\mathbf N}
 +
\end{pmatrix}=
 +
\begin{pmatrix}
 +
z\\ 0
 +
\end{pmatrix},\]
 +
tj. tabulku simplexové metody.
 +
 +
Označme $c_\B\B^{-1}=\pi$. Je-li $c_{\mathbf N}-\pi\mathbf N\ge 0$, je
 +
tabulka duálně přípustná. Označme $\overline{c_j}=c_j-\pi\A_{\bullet
 +
j}$ koeficienty v~nové matici (platí i~pro $c_\B$). Pak
 +
$\overline{c_j}\ge 0$, právě když $\pi\A_{\bullet j}\le c_j$ pro každé
 +
$j\in\hat n$ a to právě když $\pi\A\le c$. Pak ale $\pi$ splňuje
 +
soustavu omezení duální úlohy $y\A\le c$. Protože
 +
$w=yb-a_{00}=\pi b-a_00=c_\B\B^{-1}b-a_{00}$, jsou hodnoty účelové
 +
funkce stejné a proto je řešení optimální.
 +
 +
\subsection{Duální simplexová metoda}
 +
Vychází se z~{\bf duálně přípustné tabulky}.
 +
\begin{enumerate}
 +
\item Pokud je tabulka i~primárně přípustná, končím.
 +
\item Určím vedoucí řádek $r$, který má v~nultém sloupci záporné
 +
číslo. Prověrkou poměrů najdu vedoucí sloupec (kandidáti $a_{ri}<0$),
 +
pokud je každé $a_{ri}\ge 0$, neexistuje přípustné řešení. Hledám
 +
minimum
 +
\[\min_{a_{rj}<0}\abs{\frac{a_{0j}}{a_{rj}}}=\abs{\frac{a_{0s}}{a_{rs}}},\]
 +
za vedoucí sloupec zvolím $s$.
 +
\end{enumerate}
 +
 +
\subsection{Modifikovaná (redukovaná) simplexová metoda}
 +
 +
V~modifikované metodě se počítají pouze prvky, které jsou právě
 +
potřeba. Vychází se vždy z~počáteční tabulky. V~paměti mám
 +
výchozí tabulku a matici $\B^{-1}$. Nové prvky se počítají
 +
následujícími vztahy:
 +
\begin{align*}
 +
\overline b&=\B^{-1}b &
 +
\overline{\A}_{\bullet j}&=\B^{-1}\A_{\bullet j} &
 +
\overline{c}_j&=c_j-\pi\A_{\bullet j},\ \pi=c_\B\B^{-1}
 +
\end{align*}
 +
Pro $k+1.$ tabulku potřebujeme spočítat nebazická $\overline{c}_j$,
 +
mezi nimi vybereme $s$-tý vedoucí sloupec $\B^{-1}\A_{\bullet s}$ a
 +
provedeme prověrku poměrů s~$\overline{b}$. Matici $\B^{-1}$ poté
 +
vynásobíme zleva elementárními maticemi, které provedou řádkové
 +
úpravy stejné jako v~původní simplexové metodě. Postup opakujeme,
 +
dokud není $c\ge 0$.
 +
 +
\subsection{Primárně duální simplexová metoda}
 +
Tato metoda kombinuje primární i~duální simplexovou metodu. Její
 +
výhodou je, že není nutné začínat bazickým přípustným řešením, ovšem
 +
účelová funkce musí být omezená, aby měla přípustné řešení i~duální
 +
úloha.
 +
 +
Nechť primární a duální úloha mají tvar
 +
\begin{align}
 +
\label{pd_prim}\min z&=cx & \A x&=b,\quad b\ge 0 & x&\ge 0,\\
 +
\label{pd_dual}\max w&=yb & y\A&\le c.
 +
\end{align}
 +
Nejprve nalezneme přípustné řešení duální úlohy.
 +
\begin{enumerate}
 +
\item Buď je $c\ge 0$, v~tom případě vyhovuje řešení $\pi=0$.
 +
\item Existuje $j\in\hat n$ takové, že $c_j<0$. V~tom případě budeme
 +
řešit upravenou úlohu
 +
\begin{equation}
 +
\begin{split}
 +
\min z&=cx\\
 +
\A x&=b,\quad b\ge 0\\
 +
\sum_{i=1}^n x_i+x_{n+1}&=\alpha\\
 +
x&\ge 0,\\
 +
\end{split}
 +
\end{equation}
 +
resp.
 +
\begin{equation}
 +
\begin{split}
 +
\max w&=yb\\
 +
a_{11}y_1+a_{21}y_2+\dots+a_{m1}y_m+y_{m+1}&\le c_1\\
 +
a_{12}y_1+a_{22}y_2+\dots+a_{m2}y_m+y_{m+1}&\le c_2\\
 +
&\xvdots\\
 +
a_{1n}y_1+a_{2n}y_2+\dots+a_{mn}y_m+y_{m+1}&\le c_n\\
 +
y_{m+1}&\le 0,
 +
\end{split}
 +
\end{equation}
 +
kde $\alpha$ je \uv{hodně velké} číslo (např. maximální hodnota,
 +
kterou počítač snese). Potom $\pi_j=0$ pro $j\in\hat m$,
 +
$\pi_{m+1}=\min_{j\in\hat n}c_j<0$.
 +
\end{enumerate}
 +
Nechť $\pi$ je přípustné řešení úlohy \eqref{pd_dual}. Potom podle
 +
věty o~slabé komplementaritě jsou $\pi$ a $x$ optimální řešení
 +
\eqref{pd_dual} resp. \eqref{pd_prim}, právě když $\pi(\A x-b)=0$ a
 +
$(c-\pi\A)x=0$. První rovnost platí vždy, protože v~primární úloze
 +
jsou pouze rovnice, v~druhé rovnosti jsou $(c-\pi\A)$ i $x$
 +
nezáporné. Aby mohla rovnost platit, musí být všechny složky
 +
skalárního součinu nulové.
 +
 +
Je-li $c_j-\pi\A_{\bullet j}>0$, pak $x_j=0$. Definujme
 +
$\J=\{j\in\hat n|c_j-\pi\A_{\bullet j}=0\}$. Pak pro každé
 +
$j\not\in\J$ je $x_j=0$.
 +
 +
Chceme nakombinovat vektor $b$ ze sloupců matice $\A$ s~indexy z~$\J$.
 +
Budeme řešit pomocnou úlohu
 +
\begin{equation}
 +
\label{pd_pom1}
 +
\begin{split}
 +
\min \xi&=\sum_{i=1}^n x_i'\\
 +
\sum_{j\in\J} a_{ij}x_j+x_i'&=b_i\\
 +
x_j&\ge 0,\\
 +
x_i'&\ge 0.
 +
\end{split}
 +
\end{equation}
 +
Funkce $\xi$ je omezená zdola (nezáporná), existuje přípustné řešení
 +
$x_i'=b_i$ pro $i\in\hat m$ a $x_j=0$ pro $j\in\J$. Úlohu vyřeším
 +
\uv{klasickou} simplexovou metodou. Mohou nastat dva případy:
 +
\begin{enumerate}
 +
\item Je $\xi_{min}=0$, potom řešení $x$ je optimální.
 +
\item Je $\xi_{min}>0$, v~tom případě dál řeším úlohu duální
 +
k~\eqref{pd_pom1}:
 +
\end{enumerate}
 +
\begin{equation}
 +
\label{pd_pom2}
 +
\begin{split}
 +
\max w&=yb\\
 +
y\A_{\bullet j}&\le 0,\quad j\in\J\\
 +
y_i&\le 1,\quad i\in\hat m.
 +
\end{split}
 +
\end{equation}
 +
Nechť $\opi$ je optimální řešení \eqref{pd_pom2}. Rozlišíme
 +
opět dva případy:
 +
\begin{enumerate}
 +
\item $\opi\A_{\bullet j}\le 0$ pro všechna $j\not\in\J$. Potom
 +
$\opi\A\le 0$. Dokážeme, že \eqref{pd_prim} nemá přípustné
 +
řešení.
 +
 +
Z~toho, že $\opi\A\le 0$ vyplývá, že
 +
$\pi+\beta\opi$, kde $\beta\ge 0$, je přípustné řešení
 +
\eqref{pd_dual}.
 +
\[(\pi+\beta\opi)\A_{\bullet j}=
 +
\underbrace{\pi\A_{\bullet j}}_{\le c_j}+
 +
\underbrace{\beta\opi\A_{\bullet j}}_{\le 0}\le c_j.\]
 +
Protože podle věty o~dualitě je $\opi b=w_{max}=\xi_{min}>0$, je
 +
\[w=(\pi+\beta\opi)b=
 +
\underbrace{\pi b}_{\text{konst.}}+
 +
\beta\underbrace{\opi b}_{> 0}\]
 +
a pro $\beta\to +\infty$ se $w$ blíží $+\infty$.
 +
 +
\item Existuje $j_0\not\in\J$ takové, že
 +
$\opi\A_{\bullet j_0}>0$. Označme
 +
\[\theta=\min\left\{
 +
\left.
 +
\frac{c_j-\pi\A_{\bullet j}}{\opi\A_{\bullet j}}
 +
\right|
 +
\opi\A_{\bullet j}>0
 +
\right\}>0.\]
 +
Dokážeme, že $\pi'=\pi+\theta\opi$ je \uv{lepší} řešení
 +
\eqref{pd_dual} než bylo $\pi$.
 +
\[
 +
(\pi+\theta\opi)\A_{\bullet j}=\pi\A_{\bullet j}+
 +
\theta\opi\A_{\bullet j}\le
 +
\begin{cases}
 +
\pi\A_{\bullet j}\le c_j\text{ pro $\opi
 +
\A_{\bullet j}\le 0$}\\
 +
\pi\A_{\bullet j}+\frac{c_j-\pi\A_{\bullet j}}
 +
{\opi\A_{\bullet j}}\opi\A_{\bullet j}=c_j
 +
\text{ pro $\opi\A_{\bullet j}>0$},
 +
\end{cases}
 +
\]
 +
takže $\pi'$ je přípustné. Dále platí $\pi'b=\pi
 +
b+\theta\opi b>\pi b$, protože $\theta>0$ a $\opi b>0$.
 +
 +
Vrátím se na začátek, najdu nové $\J$ a opakuji proces.
 +
\end{enumerate}
 +
 +
\subsection{Dopravní problém}
 +
 +
Mám $m$ skladů a $n$ odběratelů. Označme
 +
\begin{itemize}
 +
\item $a_i$, $i\in m$ počet jednotek v~$i$-tém skladu,
 +
\item $b_j$, $j\in n$ požadavek $j$-tého odběratele,
 +
\item $c_{ij}$ přepravní náklad na jednotku z~$i$ do $j$,
 +
\item $x_{ij}$ neznámé --- kolik se přepravuje z~$i$ do $j$.
 +
\end{itemize}
 +
Budeme nejprve předpokládat, že nabídka a poptávka jsou
 +
stejné, tedy
 +
\[\sum_{i=m}^n a_i=\sum_{j=1}^n b_j=A\ge 0.\]
 +
Dopravní problém lze zapsat jako úlohu LP takto:
 +
\begin{align*}
 +
\min z&=\sum_{i=1}^m\sum_{j=1}^n c_{ij}x_{ij},\quad
 +
\text{kde $c_{ij}>0$}\\
 +
\sum_{i=1}^m x_{ij}&=b_j,\quad\text{kde $j\in\hat n$}\\
 +
\sum_{j=1}^n x_{ij}&=a_i,\quad\text{kde $i\in\hat m$}\\
 +
x_{ij}&\ge 0
 +
\end{align*}
 +
Máme soustavu $m+n$ rovnic a $mn$ proměnných. Rovnice jsou lineárně
 +
závislé, o~tom se lze přesvědčit sečtením prvních $n$ rovnic a
 +
odečtením dalších $m$ rovnic. Vynecháním kterékoli z~nich dostaneme
 +
systém $n-1$ nezávislých rovnic.
 +
 +
\begin{theorem}
 +
Dopravní problém má přípustné řešení a účelová funkce je omezená
 +
zdola, úloha má tedy i~optimální řešení.
 +
\begin{proof}
 +
Úlohu řeší například
 +
\[x_{ij}=\frac{a_ib_j}{A}.\qed\]
 +
\noqed
 +
\end{proof}
 +
\end{theorem}
 +
 +
Nalezení počátečního přípustného bazického řešení, metoda
 +
severozápadního rohu: Mějme matici proměnných
 +
\[
 +
\begin{pmatrix}
 +
x_{11} & x_{12} & \hdots & x_{1n}\\
 +
x_{21} & x_{22} & \hdots & x_{2n}\\
 +
\hdotsfor{4}\\
 +
x_{m1} & x_{m2} & \hdots & x_{mn}
 +
\end{pmatrix}.
 +
\]
 +
Na počátku položme $a'_i=a_i$, $b'_i=b_i$. Začneme u~proměnné
 +
$x_{11}$.
 +
\begin{enumerate}
 +
\item Pokud je $a'_1>b'_1$, položíme $a'_1\leftarrow a'_1-b'_1$,
 +
$b'_1\leftarrow 0$ a pokračujeme u~$x_{12}$.
 +
\item Je-li $a'_1<b'_1$, položíme $b'_1\leftarrow b'_1-a'_1$,
 +
$a'_1\leftarrow 0$ a pokračujeme u~$x_{21}$.
 +
\item Je-li $a'_1=b'_1$, položíme $a'_1\leftarrow 0$,
 +
$b'_1\leftarrow 0$ a pokračujeme u~$x_{22}$.
 +
\end{enumerate}
 +
Takto nalezené řešení je bazické.
 +
 +
Odstranění předpokladu rovnosti nabídky a poptávky: Je-li
 +
\[\sum_{i=1}^n a_i<\sum_{j=1}^n b_j,\]
 +
přidám $m+1.$ sklad a položím
 +
\[a_{m+1}=\sum_{j=1}^n b_j-\sum_{i=1}^n a_i,\quad c_{m+1,j}=0\text
 +
{ pro každé $j\in\hat n$}.\]
 +
Analogicky pro převis nabídky.
 +
 
% následující řádky upravují pouze zobrazení stránky na wiki na obsah dokumentu nemají vliv - prosím neměnit !
 
% následující řádky upravují pouze zobrazení stránky na wiki na obsah dokumentu nemají vliv - prosím neměnit !
 
%\parentlatexfile{LIPskriptum} %%  odkaz na hlavní dokument
 
%\parentlatexfile{LIPskriptum} %%  odkaz na hlavní dokument
 
%\parentlatexpreamble{LIP:preamble}
 
%\parentlatexpreamble{LIP:preamble}
 
%\usewikiobsah{LIP:Obsah}
 
%\usewikiobsah{LIP:Obsah}

Verze z 15. 2. 2010, 16:27

\section{Simplexová metoda}

Simplexová metoda se používá k~řešení úlohy v~kanonickém tvaru \begin{align*} \min z& =cx\\ \A x& = b\\ x& \ge 0. \end{align*}

Tabulka simplexové metody: Matici soustavy rovnic $\A x=b$ \[ \begin{array}{lllllllllllcl} -z & & & & & + & a_{0,m+1} &+& \cdots &+& a_{0n} &= &a_{00}\\

  & x_1 &     &        &     & + & a_{1,m+1} &+& \cdots &+& a_{1n} &= &a_{10}\\
  &     & x_2 &        &     & + & a_{2,m+1} &+& \cdots &+& a_{2n} &= &a_{20}\\
  &     &     & \ddots &     &   &           & &        & &        &\vdots  &\\
  &     &     &        & x_m & + & a_{m,m+1} &+& \cdots &+& a_{mn} &= &a_{m0}

\end{array} \] zapisujeme do tabulky \[ \left( \begin{array}{c|cccccc} a_{00} & 0 & \hdots & 0 & a_{0,m+1} & \hdots & a_{0n}\\ \hline a_{10} & 1 & \hdots & 0 & a_{1,m+1} & \hdots & a_{1n}\\ \vdots & \vdots & \ddots & \vdots & \vdots & & \vdots\\ a_{m0} & 0 & \hdots & 1 & a_{m,m+1} & \hdots & a_{mn}\\ \end{array} \right) \]

Pokud $a_{i0}\ge 0$ pro $i\in\hat m$, nazýváme tabulku {\bf primárně přípustnou}, je-li $a_{0i}\ge 0$, nazýváme tabulku {\bf duálně přípustnou}.

Je-li tabulka primárně přípustná, vyjadřuje přípustné řešení primární úlohy.


\subsection{Algoritmus simplexové metody}

\begin{enumerate} \item Vyjdu z~primárně přípustné tabulky. \item Je-li tabulka i~duálně přípustná, je optimální a končím. \item Pokud není duálně přípustná, mezi sloupci, kde $a_{0i}<0$ vyberu nějaký {\bf vedoucí sloupec} ($s$-tý). \item Vyberu {\bf vedoucí řádek}: najdu \[\min\left\{\left. \frac{a_{i0}}{a_{is}}\right| a_{is}>0 \right\}=\frac{a_{r0}}{a_{rs}}\ge 0\] (tzv. {\bf prověrka poměrů}) a jako vedoucí zvolím $r$-tý. $x_r$ bude nová nebazická proměnná a položím \[x_s=\frac{a_{r0}}{a_{rs}}.\] Prvek $a_{rs}$ nazýváme {\bf vedoucí prvek} ({\bf pivot}). Pokud jsou všechny $a_{is}\le 0$, není účelová funkce $z$ omezená, takže končím. \end{enumerate} Pokud je v~prvním sloupci nějaká nula, prověrka poměrů dá nulu a jsem v~blbé situaci, protože nemůžu bezprostředně přejít k~jinému vrcholu.

\subsection{Časová náročnost} Teoreticky je exponenciální: maximálně $\binom{m}{n}$. \[n!\approx\frac{n^n}{e^n}\sqrt{2\pi n}\] \[\binom{n}{\frac n2}=\frac{n!}{\left(\left(\frac n2\right)!\right)^2} \approx\frac{\frac{n^n}{e^n}\sqrt{2\pi n}} {\frac{\left(\frac{n}{2}\right)^n}{e^n}\pi n}= 2^n\sqrt{\frac{2}{\pi n}},\] tj. řádově $2^n$. V~praxi se to ale chová polynomiálně, obvykle stačí cca. $2m$ až $3m$ iterací.

\subsection{Nalezení počátečního přípustného bazického řešení} \begin{enumerate} \item Do každé rovnice přidáme tzv. {\bf umělou proměnnou} $x_i'\ge 0$. Dostanu tak soustavu \begin{align*} x_1'+\sum_{j=1}^n a_{1j}x_j&=b_1\\ &\xvdots\\ x_m'+\sum_{j=1}^n a_{mj}x_j&=b_m\\ \min\xi&=\min\sum_{j=1}^m x_j' \end{align*} položím $x_1',\dots,x_m'=b_1,\dots,b_m$, $x_j=0$ pro $j\in\hat n$. \begin{enumerate} \item Je-li $\xi_{min}>0$, neexistuje přípustné řešení výchozí úlohy. \item Je-li $\xi_{min}=0$, je $x$ přípustné řešení. \end{enumerate} \item Nerovnice typu $\A x\le b$, $b\ge 0$, $x\ge 0$ převedu na rovnice se slabou proměnnou a slabé proměnné položím rovny $b$. {\bf Slabé proměnné nejsou v~účelové funkci !} \item Nerovnice typu \[\sum_{j=1}^n a_{ij}x_j\ge b_i,\quad i\in k,\ b_i\ge 0\] převedu na rovnice se slabou proměnnou a do každé z~nich přidám {\bf stejnou} umělou proměnnou $x'$: \[x'+\sum_{j=1}^n a_{ij}x_j-s_i=b_i,\quad s_i\ge 0,\ x'\ge 0.\] Buď $\max\{b_i|i\in\hat k\}=b_l$. Soustavu nerovnic převedeme na novou soustavu \begin{align*} x'+\sum_{j=1}^n a_{lj}x_j-s_l&=b_l\\ \sum_{j=1}^n(a_{lj}-a_{ij})x_j-s_l+s_i&= \underbrace{b_l-b_i}_{\ge 0},\quad i\in\hat k\sm\{l\}. \end{align*} Proměnnou $s_l$ položím rovnou nule a proměnné $x'$ a $s_i$ dopočítám. Minimalizuji funkci $\xi=x'$. Neuškodí zopakovat, že {\bf v účelové funkci se v~každém případě vyskytují pouze umělé proměnné}. \end{enumerate} Pokud mám soustavu, kde jsou rovnice i~nerovnice, lze tyto postupy samozřejmě kombinovat.

\subsection{Zacyklení --- jak z~toho ven}

Zacyklením nazýváme situaci, kdy se při prověrce poměrů vyjde nula. V~následujícím kroku se pak nezmění hodnota účelové funkce, protože se k~ní tato nula přičte.

\begin{define} Buď $x\in\R^n$, $x\not=0$. Vektor $x$ nazýváme {\bf lexikograficky kladný} ($x\lexgr 0$), právě když první nenulová složka vektoru $x$ je kladná. Pro dva různé vektory $x,y$ definujeme $x\lexgr y$, právě když $x-y\lexgr 0$. \end{define}

\begin{description} \item[Dantzig] Vycházíme z~toho, že prvky nultého řádku jsou jednoznačně určeny volbou báze. Vedoucí sloupec volím stejně, tj. sloupec, v~jehož prvním řádku je záporné číslo.

Volba vedoucího řádku: Na počátku musí být všechny řádky lexikograficky kladné (s~výjimkou nultého). Pokud nejsou, přečísluji neznámé tak, aby jednotková matice byla nalevo. Kandidáta na vedoucí řádek pak hledám mezi řádky, kde $a_{is}>0$. Pro každé $a_{is}>0$ vezmu vektor $(a_{i0},a_{i1},\dots,a_{in})$ a vydělím $a_{is}$. Získám tak vektory \[\left( \frac{a_{i0}}{a_{is}},\frac{a_{i1}}{a_{is}},\dots,\frac{a_{in}}{a_{is}} \right).\] Z~těchto vektorů vyberu lexikograficky nejmenší ($r$-tý) a za vedoucí řádek zvolím $r$-tý řádek. \begin{proof} Dokážeme, že v~každé další tabulce bude nultý řádek lexikograficky větší a že řádky $1$ až $m$ zůstanou lexikograficky kladné.

Platí, že $a_{rs}>0$. Chceme dokázat, že pro $i$-tý řádek platí \[(a_{i0},\dots,a_{in})-\frac{a_{is}}{a_{rs}} (a_{r0},\dots,a_{rs})\lexgr 0.\] Pokud $a_{is}=0$, je to zřejmé. Je-li $a_{is}<0$, přičítám k~lexikograficky kladnému řádku lexikograficky kladný řádek, tedy $i$-tý řádek zůstane lexikograficky kladný. Pokud $a_{is}>0$, vydělím nerovnici $a_{is}$ a dostanu \[ \left(\frac{a_{i0}}{a_{is}},\dots,\frac{a_{in}}{a_{is}}\right) \lexgr \left(\frac{a_{r0}}{a_{rs}},\dots,\frac{a_{rn}}{a_{rs}}\right). \] Protože jsem volil vedoucí řádek tak, aby vektor napravo byl lexikograficky nejmenší, je nerovnost splněna.

Pro nultý řádek nastává případ $a_{0s}<0$, přičítám k~němu lexikograficky kladný vektor, takže bude lexikograficky větší. \end{proof}

\item[Bland] Za vedoucí sloupec se zvolí sloupec odpovídající proměnné s~nejmenším indexem, stejně tak pro vedoucí řádek (vybírám řádek {\bf odpovídající proměnné s~nejmenším indexem}, nikoliv řádek s~nejmenším indexem) --- tzv. Blandovo pravidlo \uv{nejmenších indexů}. \begin{theorem} Při použití Blandova pravidla \uv{nejmenších indexů} nedojde k~zacyklení. \begin{proof} Větu dokážeme sporem. Předpokládejme, že máme degenerovanou úlohu, posloupnost tabulek je nekonečná a žádná z~tabulek není optimální. Proměnné rozdělíme na tři typy: \begin{enumerate}[1)] \item nikdy nejsou v~bázi, \item jsou stále v~bázi, \item vyskytují se jak v~bázi tak mimo bázi --- \uv{běhny}. \end{enumerate} Označme \begin{itemize} \item $x_t$ běhnu s~největším indexem, \item$D$ tabulku, v~níž je $x_t$ bazická, ale v~následující není bazická, \item $x_s$ proměnnou, která je v~D nebazická, ale v~následující je bazická, \item $D^*$ tabulku, v~níž je $x_t$ nebazická, ale v~následující je bazická, \item $v$ prvek $a_{00}$ všech tabulek (nemění se), \item $B=\{i\in\hat n|x_i\text{ je v $D$ bazická}\}$. \item Pokud řádek vektoru $b$ nebo matice $\A$ indexuji indexem $i\in B$ nějaké bazické proměnné, myslí se tím ten řádek, ve kterém je v $i$-tém sloupci jednotka. \end{itemize} Tabulka $D$ má tvar \begin{align*} z&=v+\sum_{j\not\in B}c_j x_j\\ x_i&=b_i-\sum_{j\not\in B}a_{ij}x_j,\quad i\in B, \end{align*} nultý řádek tabulky $D^*$ má tvar \[z=v+\sum_{j=1}^n c_j^* x_j.\] Položme $x_s=y\in\R$, $x_j=0$ pro $j\not\in B$, $j\not=s$. Pak $x_i=b_i-a_{is}y$ pro $i\in B$ a \[z=v+c_sy=v+c_s^* y+ \sum_{i\in B}c_i^*\underbrace{(b_i-a_{is}y)}_{x_i}.\] Pro každé $y\in\R$ pak platí \[\left(c_s-c_s^*+\sum_{i\in B}c_i^* a_{is}\right)y= \sum_{i\in B}c_i^* b_i.\] To je ale možné jen v~případě, že koeficienty u~$y$ jsou nulové, tedy \[c_s-c_s^*+\sum_{i\in B}c_i^* a_{is}=0.\] Platí, že $c_s<0$, protože $x_s$ jde v~$D$ do báze. Naopak $c_s^*\ge 0$, protože do báze jde v~$D^*$ $x_t$ a kdyby $c_s^*<0$, podle Blandova pravidla by do báze šla $x_s$. Tedy $c_s-c_s^*<0$, z~čehož plyne, že alespoň jeden sčítanec v~sumě je kladný. Tedy existuje $i$ takové, že $c_i^*a_{is}>0$.

Dokážeme, že $x_i$ je běhna a $i<t$. Protože $a_{ts}>0$ (je to pivot) a $c_t^*<0$ ($x_t$ jde do báze), je $c_t^* a_{ts}<0$. Je proto $i<t$, neboť $c_i^*a_{is}>0$.

Proměnná $x_i$ nemůže být v~$D^*$ bazická, protože $c_i^*\not=0$. Je to tedy běhna s~indexem menším než $t$.

Proměnná $x_i$ je ve všech tabulkách nulová. Pokud není v~bázi, je to jasné a když jde do báze, zůstane nulová, protože prověrka poměrů dá nulu a nulová zůstane i~dál, protože nultý sloupec se nemění. V~tabulce $D$ má hodnotu $b_i$, takže $b_i=0$.

Z~toho, že $x_i$ je běhna plyne, že $c_i^*>0$, jinak bych musel do báze podle Blandova pravidla zařadit $x_i$ a ne $x_t$. Protože $c_i^*>0$, je i $a_{is}>0$. Z~toho plyne, že řádek odpovídající $i$-té proměnné je rovněž kandidátem na vedoucí řádek. Prověrka poměrů dá nulu ($b_i=0$ a podle předpokladu i $b_t=0$), podle Blandova pravidla vybírám řádek odpovídající proměnné s~nejmenším indexem, takže v~tabulce $D$ se měl volit řádek odpovídající $i$-té proměnné, což je spor. \end{proof} \end{theorem} \end{description}

\subsection{Maticový zápis simplexového algoritmu}

Soustavu rovnic simplexové metody \begin{align*} z&=cx-a_{00}\\ 0&=-b+\A x \end{align*} lze zapsat maticově jako \[ \begin{pmatrix} a_{00} & c \\ b & \A \end{pmatrix} \begin{pmatrix} -1\\x \end{pmatrix}= \begin{pmatrix} z\\ 0 \end{pmatrix}. \] Buďte $\A=(\B|\mathbf N)$, kde $\B$ je regulární, $c=(c_\B,c_{\mathbf N})$, $x= \begin{pmatrix} x_\B\\x_{\mathbf N} \end{pmatrix} $. Dosazením a vynásobením soustavy \[ \left. \begin{pmatrix} a_{00} & c_\B & c_{\mathbf N} \\ b & \B & \mathbf N \end{pmatrix} \begin{pmatrix} -1\\x_\B\\x_{\mathbf N} \end{pmatrix}= \begin{pmatrix} z\\ 0 \end{pmatrix} \qquad \right| \cdot \begin{pmatrix} 1 & -c_\B\B^{-1}\\ 0 & \B^{-1} \end{pmatrix} \text{ zleva} \] dostaneme \[ \begin{pmatrix} a_{00}-c_B\B^{-1}b & 0 & c_{\mathbf N}-c_B\B^{-1}\mathbf N \\ \B^{-1}b & \E & \B^{-1}\mathbf N \end{pmatrix} \begin{pmatrix} -1\\x_\B\\x_{\mathbf N} \end{pmatrix}= \begin{pmatrix} z\\ 0 \end{pmatrix},\] tj. tabulku simplexové metody.

Označme $c_\B\B^{-1}=\pi$. Je-li $c_{\mathbf N}-\pi\mathbf N\ge 0$, je tabulka duálně přípustná. Označme $\overline{c_j}=c_j-\pi\A_{\bullet j}$ koeficienty v~nové matici (platí i~pro $c_\B$). Pak $\overline{c_j}\ge 0$, právě když $\pi\A_{\bullet j}\le c_j$ pro každé $j\in\hat n$ a to právě když $\pi\A\le c$. Pak ale $\pi$ splňuje soustavu omezení duální úlohy $y\A\le c$. Protože $w=yb-a_{00}=\pi b-a_00=c_\B\B^{-1}b-a_{00}$, jsou hodnoty účelové funkce stejné a proto je řešení optimální.

\subsection{Duální simplexová metoda} Vychází se z~{\bf duálně přípustné tabulky}. \begin{enumerate} \item Pokud je tabulka i~primárně přípustná, končím. \item Určím vedoucí řádek $r$, který má v~nultém sloupci záporné číslo. Prověrkou poměrů najdu vedoucí sloupec (kandidáti $a_{ri}<0$), pokud je každé $a_{ri}\ge 0$, neexistuje přípustné řešení. Hledám minimum \[\min_{a_{rj}<0}\abs{\frac{a_{0j}}{a_{rj}}}=\abs{\frac{a_{0s}}{a_{rs}}},\] za vedoucí sloupec zvolím $s$. \end{enumerate}

\subsection{Modifikovaná (redukovaná) simplexová metoda}

V~modifikované metodě se počítají pouze prvky, které jsou právě potřeba. Vychází se vždy z~počáteční tabulky. V~paměti mám výchozí tabulku a matici $\B^{-1}$. Nové prvky se počítají následujícími vztahy: \begin{align*} \overline b&=\B^{-1}b & \overline{\A}_{\bullet j}&=\B^{-1}\A_{\bullet j} & \overline{c}_j&=c_j-\pi\A_{\bullet j},\ \pi=c_\B\B^{-1} \end{align*} Pro $k+1.$ tabulku potřebujeme spočítat nebazická $\overline{c}_j$, mezi nimi vybereme $s$-tý vedoucí sloupec $\B^{-1}\A_{\bullet s}$ a provedeme prověrku poměrů s~$\overline{b}$. Matici $\B^{-1}$ poté vynásobíme zleva elementárními maticemi, které provedou řádkové úpravy stejné jako v~původní simplexové metodě. Postup opakujeme, dokud není $c\ge 0$.

\subsection{Primárně duální simplexová metoda} Tato metoda kombinuje primární i~duální simplexovou metodu. Její výhodou je, že není nutné začínat bazickým přípustným řešením, ovšem účelová funkce musí být omezená, aby měla přípustné řešení i~duální úloha.

Nechť primární a duální úloha mají tvar \begin{align} \label{pd_prim}\min z&=cx & \A x&=b,\quad b\ge 0 & x&\ge 0,\\ \label{pd_dual}\max w&=yb & y\A&\le c. \end{align} Nejprve nalezneme přípustné řešení duální úlohy. \begin{enumerate} \item Buď je $c\ge 0$, v~tom případě vyhovuje řešení $\pi=0$. \item Existuje $j\in\hat n$ takové, že $c_j<0$. V~tom případě budeme řešit upravenou úlohu \begin{equation} \begin{split} \min z&=cx\\ \A x&=b,\quad b\ge 0\\ \sum_{i=1}^n x_i+x_{n+1}&=\alpha\\ x&\ge 0,\\ \end{split} \end{equation} resp. \begin{equation} \begin{split} \max w&=yb\\ a_{11}y_1+a_{21}y_2+\dots+a_{m1}y_m+y_{m+1}&\le c_1\\ a_{12}y_1+a_{22}y_2+\dots+a_{m2}y_m+y_{m+1}&\le c_2\\ &\xvdots\\ a_{1n}y_1+a_{2n}y_2+\dots+a_{mn}y_m+y_{m+1}&\le c_n\\ y_{m+1}&\le 0, \end{split} \end{equation} kde $\alpha$ je \uv{hodně velké} číslo (např. maximální hodnota, kterou počítač snese). Potom $\pi_j=0$ pro $j\in\hat m$, $\pi_{m+1}=\min_{j\in\hat n}c_j<0$. \end{enumerate} Nechť $\pi$ je přípustné řešení úlohy \eqref{pd_dual}. Potom podle věty o~slabé komplementaritě jsou $\pi$ a $x$ optimální řešení \eqref{pd_dual} resp. \eqref{pd_prim}, právě když $\pi(\A x-b)=0$ a $(c-\pi\A)x=0$. První rovnost platí vždy, protože v~primární úloze jsou pouze rovnice, v~druhé rovnosti jsou $(c-\pi\A)$ i $x$ nezáporné. Aby mohla rovnost platit, musí být všechny složky skalárního součinu nulové.

Je-li $c_j-\pi\A_{\bullet j}>0$, pak $x_j=0$. Definujme $\J=\{j\in\hat n|c_j-\pi\A_{\bullet j}=0\}$. Pak pro každé $j\not\in\J$ je $x_j=0$.

Chceme nakombinovat vektor $b$ ze sloupců matice $\A$ s~indexy z~$\J$. Budeme řešit pomocnou úlohu \begin{equation} \label{pd_pom1} \begin{split} \min \xi&=\sum_{i=1}^n x_i'\\ \sum_{j\in\J} a_{ij}x_j+x_i'&=b_i\\ x_j&\ge 0,\\ x_i'&\ge 0. \end{split} \end{equation} Funkce $\xi$ je omezená zdola (nezáporná), existuje přípustné řešení $x_i'=b_i$ pro $i\in\hat m$ a $x_j=0$ pro $j\in\J$. Úlohu vyřeším \uv{klasickou} simplexovou metodou. Mohou nastat dva případy: \begin{enumerate} \item Je $\xi_{min}=0$, potom řešení $x$ je optimální. \item Je $\xi_{min}>0$, v~tom případě dál řeším úlohu duální k~\eqref{pd_pom1}: \end{enumerate} \begin{equation} \label{pd_pom2} \begin{split} \max w&=yb\\ y\A_{\bullet j}&\le 0,\quad j\in\J\\ y_i&\le 1,\quad i\in\hat m. \end{split} \end{equation} Nechť $\opi$ je optimální řešení \eqref{pd_pom2}. Rozlišíme opět dva případy: \begin{enumerate} \item $\opi\A_{\bullet j}\le 0$ pro všechna $j\not\in\J$. Potom $\opi\A\le 0$. Dokážeme, že \eqref{pd_prim} nemá přípustné řešení.

Z~toho, že $\opi\A\le 0$ vyplývá, že $\pi+\beta\opi$, kde $\beta\ge 0$, je přípustné řešení \eqref{pd_dual}. \[(\pi+\beta\opi)\A_{\bullet j}= \underbrace{\pi\A_{\bullet j}}_{\le c_j}+ \underbrace{\beta\opi\A_{\bullet j}}_{\le 0}\le c_j.\] Protože podle věty o~dualitě je $\opi b=w_{max}=\xi_{min}>0$, je \[w=(\pi+\beta\opi)b= \underbrace{\pi b}_{\text{konst.}}+ \beta\underbrace{\opi b}_{> 0}\] a pro $\beta\to +\infty$ se $w$ blíží $+\infty$.

\item Existuje $j_0\not\in\J$ takové, že $\opi\A_{\bullet j_0}>0$. Označme \[\theta=\min\left\{ \left. \frac{c_j-\pi\A_{\bullet j}}{\opi\A_{\bullet j}} \right| \opi\A_{\bullet j}>0 \right\}>0.\] Dokážeme, že $\pi'=\pi+\theta\opi$ je \uv{lepší} řešení \eqref{pd_dual} než bylo $\pi$. \[ (\pi+\theta\opi)\A_{\bullet j}=\pi\A_{\bullet j}+ \theta\opi\A_{\bullet j}\le \begin{cases} \pi\A_{\bullet j}\le c_j\text{ pro $\opi \A_{\bullet j}\le 0$}\\ \pi\A_{\bullet j}+\frac{c_j-\pi\A_{\bullet j}} {\opi\A_{\bullet j}}\opi\A_{\bullet j}=c_j \text{ pro $\opi\A_{\bullet j}>0$}, \end{cases} \] takže $\pi'$ je přípustné. Dále platí $\pi'b=\pi b+\theta\opi b>\pi b$, protože $\theta>0$ a $\opi b>0$.

Vrátím se na začátek, najdu nové $\J$ a opakuji proces. \end{enumerate}

\subsection{Dopravní problém}

Mám $m$ skladů a $n$ odběratelů. Označme \begin{itemize} \item $a_i$, $i\in m$ počet jednotek v~$i$-tém skladu, \item $b_j$, $j\in n$ požadavek $j$-tého odběratele, \item $c_{ij}$ přepravní náklad na jednotku z~$i$ do $j$, \item $x_{ij}$ neznámé --- kolik se přepravuje z~$i$ do $j$. \end{itemize} Budeme nejprve předpokládat, že nabídka a poptávka jsou stejné, tedy \[\sum_{i=m}^n a_i=\sum_{j=1}^n b_j=A\ge 0.\] Dopravní problém lze zapsat jako úlohu LP takto: \begin{align*} \min z&=\sum_{i=1}^m\sum_{j=1}^n c_{ij}x_{ij},\quad \text{kde $c_{ij}>0$}\\ \sum_{i=1}^m x_{ij}&=b_j,\quad\text{kde $j\in\hat n$}\\ \sum_{j=1}^n x_{ij}&=a_i,\quad\text{kde $i\in\hat m$}\\ x_{ij}&\ge 0 \end{align*} Máme soustavu $m+n$ rovnic a $mn$ proměnných. Rovnice jsou lineárně závislé, o~tom se lze přesvědčit sečtením prvních $n$ rovnic a odečtením dalších $m$ rovnic. Vynecháním kterékoli z~nich dostaneme systém $n-1$ nezávislých rovnic.

\begin{theorem} Dopravní problém má přípustné řešení a účelová funkce je omezená zdola, úloha má tedy i~optimální řešení. \begin{proof} Úlohu řeší například \[x_{ij}=\frac{a_ib_j}{A}.\qed\] \noqed \end{proof} \end{theorem}

Nalezení počátečního přípustného bazického řešení, metoda severozápadního rohu: Mějme matici proměnných \[ \begin{pmatrix} x_{11} & x_{12} & \hdots & x_{1n}\\ x_{21} & x_{22} & \hdots & x_{2n}\\ \hdotsfor{4}\\ x_{m1} & x_{m2} & \hdots & x_{mn} \end{pmatrix}. \] Na počátku položme $a'_i=a_i$, $b'_i=b_i$. Začneme u~proměnné $x_{11}$. \begin{enumerate} \item Pokud je $a'_1>b'_1$, položíme $a'_1\leftarrow a'_1-b'_1$, $b'_1\leftarrow 0$ a pokračujeme u~$x_{12}$. \item Je-li $a'_1<b'_1$, položíme $b'_1\leftarrow b'_1-a'_1$, $a'_1\leftarrow 0$ a pokračujeme u~$x_{21}$. \item Je-li $a'_1=b'_1$, položíme $a'_1\leftarrow 0$, $b'_1\leftarrow 0$ a pokračujeme u~$x_{22}$. \end{enumerate} Takto nalezené řešení je bazické.

Odstranění předpokladu rovnosti nabídky a poptávky: Je-li \[\sum_{i=1}^n a_i<\sum_{j=1}^n b_j,\] přidám $m+1.$ sklad a položím \[a_{m+1}=\sum_{j=1}^n b_j-\sum_{i=1}^n a_i,\quad c_{m+1,j}=0\text { pro každé $j\in\hat n$}.\] Analogicky pro převis nabídky.

% následující řádky upravují pouze zobrazení stránky na wiki na obsah dokumentu nemají vliv - prosím neměnit ! %\parentlatexfile{LIPskriptum} %% odkaz na hlavní dokument %\parentlatexpreamble{LIP:preamble} %\usewikiobsah{LIP:Obsah}