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