LIP:Kapitola3

\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}{lclllllllllll} &a_{00} &= -z & & & & & + & a_{0,m+1} x_{m+1} &+& \cdots &+& a_{0n} x_n\\ &a_{10} &= & x_1 & & & & + & a_{1,m+1} x_{m+1} &+& \cdots &+& a_{1n} x_n\\ &a_{20} &= & & x_2 & & & + & a_{2,m+1} x_{m+1} &+& \cdots &+& a_{2n} x_n\\

       &\vdots&     &     &        &\ddots&  &                   & &        & &       \\

&a_{m0} &= & & & & x_m & + & a_{m,m+1} x_{m+1} &+& \cdots &+& a_{mn} x_n \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 (z kandidátů) zvolí sloupec odpovídající proměnné s~nejmenším indexem. Mezi kandidáty na vyřazení z~báze při rovnosti prověrky poměrů vezmeme proměnnou s nejmenším indexem. \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$. 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$. 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$ 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}