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'>&#160;</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^*&lt;0$, podle</div></td><td class='diff-marker'>&#160;</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^*&lt;0$, podle</div></td></tr> <tr><td class='diff-marker'>&#160;</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^*&lt;0$, z~čehož</div></td><td class='diff-marker'>&#160;</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^*&lt;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'>&#160;</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}&gt;0$.</div></td><td class='diff-marker'>&#160;</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}&gt;0$.</div></td></tr> <tr><td class='diff-marker'>&#160;</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>&#160; &#160;</div></td><td class='diff-marker'>&#160;</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>&#160; &#160;</div></td></tr> <tr><td class='diff-marker'>&#160;</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&lt;t$. Proměnná $x_i$ nemůže být v~$D^*$</div></td><td class='diff-marker'>&#160;</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&lt;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}&gt;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}&gt;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'>&#160;</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^*&lt;0$ ($x_t$ jde do báze), je $c_t^* a_{ts}&lt;0$. Je proto $i&lt;t$,</div></td><td class='diff-marker'>&#160;</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^*&lt;0$ ($x_t$ jde do báze), je $c_t^* a_{ts}&lt;0$. Je proto $i&lt;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}&gt;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}&gt;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'>&#160;</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>&#160; &#160;</div></td><td class='diff-marker'>&#160;</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>&#160; &#160;</div></td></tr> <tr><td class='diff-marker'>&#160;</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'>&#160;</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'>&#160;</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'>&#160;</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'>&#160;</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'>&#160;</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">&#160;</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">&#160;</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'>&#160;</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'>&#160;</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'>&#160;</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'>&#160;</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'>&#160;</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'>&#160;</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'>&#160;</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'>&#160;</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">&#160;</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'>&#160;</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>&#160; &#160;</div></td><td class='diff-marker'>&#160;</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>&#160; &#160;</div></td></tr> <tr><td class='diff-marker'>&#160;</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'>&#160;</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'>&#160;</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'>&#160;</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'>&#160;</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'>&#160;</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&amp; =cx\\ \A x&amp; = b\\ x&amp; \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&amp; =cx\\<br /> \A x&amp; = b\\<br /> x&amp; \ge 0.<br /> \end{align*}<br /> <br /> Tabulka simplexové metody: Matici soustavy rovnic $\A x=b$<br /> \[<br /> \begin{array}{lclllllllllll}<br /> &amp;a_{00} &amp;= -z &amp; &amp; &amp; &amp; &amp; + &amp; a_{0,m+1} x_{m+1} &amp;+&amp; \cdots &amp;+&amp; a_{0n} x_n\\<br /> &amp;a_{10} &amp;= &amp; x_1 &amp; &amp; &amp; &amp; + &amp; a_{1,m+1} x_{m+1} &amp;+&amp; \cdots &amp;+&amp; a_{1n} x_n\\<br /> &amp;a_{20} &amp;= &amp; &amp; x_2 &amp; &amp; &amp; + &amp; a_{2,m+1} x_{m+1} &amp;+&amp; \cdots &amp;+&amp; a_{2n} x_n\\<br /> &amp;\vdots&amp; &amp; &amp; &amp;\ddots&amp; &amp; &amp; &amp; &amp; &amp; \\<br /> &amp;a_{m0} &amp;= &amp; &amp; &amp; &amp; x_m &amp; + &amp; a_{m,m+1} x_{m+1} &amp;+&amp; \cdots &amp;+&amp; a_{mn} x_n<br /> \end{array}<br /> \]<br /> zapisujeme do tabulky<br /> \[<br /> \left(<br /> \begin{array}{c|cccccc}<br /> a_{00} &amp; 0 &amp; \hdots &amp; 0 &amp; a_{0,m+1} &amp; \hdots &amp; a_{0n}\\<br /> \hline<br /> a_{10} &amp; 1 &amp; \hdots &amp; 0 &amp; a_{1,m+1} &amp; \hdots &amp; a_{1n}\\<br /> \vdots &amp; \vdots &amp; \ddots &amp; \vdots &amp; \vdots &amp; &amp; \vdots\\<br /> a_{m0} &amp; 0 &amp; \hdots &amp; 1 &amp; a_{m,m+1} &amp; \hdots &amp; 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}&lt;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}&gt;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&amp;=b_1\\<br /> &amp;\xvdots\\<br /> x_m'+\sum_{j=1}^n a_{mj}x_j&amp;=b_m\\<br /> \min\xi&amp;=\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}&gt;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&amp;=b_l\\<br /> \sum_{j=1}^n(a_{lj}-a_{ij})x_j-s_l+s_i&amp;=<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}&gt;0$. Pro každé $a_{is}&gt;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}&gt;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}&lt;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}&gt;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}&lt;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&amp;=v+\sum_{j\not\in B}c_j x_j\\<br /> x_i&amp;=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&lt;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^*&lt;0$, podle<br /> Blandova pravidla by do báze šla $x_s$. Tedy $c_s-c_s^*&lt;0$, z~čehož<br /> plyne, že alespoň jeden sčítanec v~sumě je kladný. Tedy existuje $i$<br /> takové, že $c_i^*a_{is}&gt;0$.<br /> <br /> Dokážeme, že $x_i$ je běhna a $i&lt;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}&gt;0$ (je to pivot)<br /> a $c_t^*&lt;0$ ($x_t$ jde do báze), je $c_t^* a_{ts}&lt;0$. Je proto $i&lt;t$,<br /> neboť $c_i^*a_{is}&gt;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^*&gt;0$, jinak bych musel do<br /> báze podle Blandova pravidla zařadit $x_i$ a ne $x_t$. Protože<br /> $c_i^*&gt;0$, je i $a_{is}&gt;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&amp;=cx-a_{00}\\<br /> 0&amp;=-b+\A x<br /> \end{align*}<br /> lze zapsat maticově jako<br /> \[<br /> \begin{pmatrix}<br /> a_{00} &amp; c \\<br /> b &amp; \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} &amp; c_\B &amp; c_{\mathbf N} \\<br /> b &amp; \B &amp; \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 &amp; -c_\B\B^{-1}\\<br /> 0 &amp; \B^{-1}<br /> \end{pmatrix}<br /> \text{ zleva}<br /> \]<br /> dostaneme<br /> \[<br /> \begin{pmatrix}<br /> a_{00}-c_B\B^{-1}b &amp; 0 &amp; c_{\mathbf N}-c_B\B^{-1}\mathbf N \\<br /> \B^{-1}b &amp; \E &amp; \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}&lt;0$),<br /> pokud je každé $a_{ri}\ge 0$, neexistuje přípustné řešení. Hledám<br /> minimum<br /> \[\min_{a_{rj}&lt;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&amp;=\B^{-1}b &amp;<br /> \overline{\A}_{\bullet j}&amp;=\B^{-1}\A_{\bullet j} &amp;<br /> \overline{c}_j&amp;=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&amp;=cx &amp; \A x&amp;=b,\quad b\ge 0 &amp; x&amp;\ge 0,\\<br /> \label{pd_dual}\max w&amp;=yb &amp; y\A&amp;\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&lt;0$. V~tom případě budeme<br /> řešit upravenou úlohu<br /> \begin{equation}<br /> \begin{split}<br /> \min z&amp;=cx\\<br /> \A x&amp;=b,\quad b\ge 0\\<br /> \sum_{i=1}^n x_i+x_{n+1}&amp;=\alpha\\<br /> x&amp;\ge 0,\\<br /> \end{split}<br /> \end{equation}<br /> resp.<br /> \begin{equation}<br /> \begin{split}<br /> \max w&amp;=yb\\<br /> a_{11}y_1+a_{21}y_2+\dots+a_{m1}y_m+y_{m+1}&amp;\le c_1\\<br /> a_{12}y_1+a_{22}y_2+\dots+a_{m2}y_m+y_{m+1}&amp;\le c_2\\<br /> &amp;\xvdots\\<br /> a_{1n}y_1+a_{2n}y_2+\dots+a_{mn}y_m+y_{m+1}&amp;\le c_n\\<br /> y_{m+1}&amp;\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&lt;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}&gt;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&amp;=\sum_{i=1}^n x_i'\\<br /> \sum_{j\in\J} a_{ij}x_j+x_i'&amp;=b_i\\<br /> x_j&amp;\ge 0,\\<br /> x_i'&amp;\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}&gt;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&amp;=yb\\<br /> y\A_{\bullet j}&amp;\le 0,\quad j\in\J\\<br /> y_i&amp;\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}&gt;0$, je<br /> \[w=(\pi+\beta\opi)b=<br /> \underbrace{\pi b}_{\text{konst.}}+<br /> \beta\underbrace{\opi b}_{&gt; 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}&gt;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}&gt;0<br /> \right\}&gt;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}&gt;0$},<br /> \end{cases}<br /> \]<br /> takže $\pi'$ je přípustné. Dále platí $\pi'b=\pi<br /> b+\theta\opi b&gt;\pi b$, protože $\theta&gt;0$ a $\opi b&gt;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&amp;=\sum_{i=1}^m\sum_{j=1}^n c_{ij}x_{ij},\quad<br /> \text{kde $c_{ij}&gt;0$}\\<br /> \sum_{i=1}^m x_{ij}&amp;=b_j,\quad\text{kde $j\in\hat n$}\\<br /> \sum_{j=1}^n x_{ij}&amp;=a_i,\quad\text{kde $i\in\hat m$}\\<br /> x_{ij}&amp;\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} &amp; x_{12} &amp; \hdots &amp; x_{1n}\\<br /> x_{21} &amp; x_{22} &amp; \hdots &amp; x_{2n}\\<br /> \hdotsfor{4}\\<br /> x_{m1} &amp; x_{m2} &amp; \hdots &amp; 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&gt;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&lt;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&lt;\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