https://wikiskripta.fjfi.cvut.cz/wiki/index.php?title=01LIP:Kapitola2&feed=atom&action=history 01LIP:Kapitola2 - Historie editací 2024-03-29T07:09:40Z Historie editací této stránky MediaWiki 1.25.2 https://wikiskripta.fjfi.cvut.cz/wiki/index.php?title=01LIP:Kapitola2&diff=4285&oldid=prev Pohanjur v 3. 7. 2011, 19:33 2011-07-03T19:33:34Z <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 3. 7. 2011, 19:33</td> </tr><tr><td colspan="2" class="diff-lineno" id="L128" >Řádka 128:</td> <td colspan="2" class="diff-lineno">Řádka 128:</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 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{remark}</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{remark}</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>&#160; Hodnota účelové funkci na <del class="diffchange diffchange-inline">množine </del>optimálních řešení je konstantní.</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>&#160; Hodnota účelové funkci na <ins class="diffchange diffchange-inline">množině </ins>optimálních řešení je konstantní.</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>&#160; Nechť množina optimálních řešení dané úlohy LP obsahuje alespoň dva prvky. Pro spor předpokládejme že existují dvě optimální řešení $\x_1 ,\x_2$&#160; takové, že $z(\x_1) \neq z(\x_2)$. Bez ujmy na obecnosti nechť $z(\x_2) &gt; z(\x_1)$.</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; Nechť množina optimálních řešení dané úlohy LP obsahuje alespoň dva prvky. Pro spor předpokládejme že existují dvě optimální řešení $\x_1 ,\x_2$&#160; takové, že $z(\x_1) \neq z(\x_2)$. Bez ujmy na obecnosti nechť $z(\x_2) &gt; z(\x_1)$.</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>&#160; Nechť $\y_1 ,\y_2$ jsou příslušná optimální řešení úlohy duální. Pak platí $c\x_1 \textless \y_2 b$ což je spor s <del class="diffchange diffchange-inline">předchozí </del>větou.</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>&#160; Nechť $\y_1 ,\y_2$ jsou příslušná optimální řešení úlohy duální. Pak platí $c\x_1 \textless \y_2 b$ což je spor s větou <ins class="diffchange diffchange-inline">2.1 </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>\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 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{remark}</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{remark}</div></td></tr> </table> Pohanjur https://wikiskripta.fjfi.cvut.cz/wiki/index.php?title=01LIP:Kapitola2&diff=4284&oldid=prev Pohanjur v 3. 7. 2011, 19:30 2011-07-03T19:30:25Z <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 3. 7. 2011, 19:30</td> </tr><tr><td colspan="2" class="diff-lineno" id="L44" >Řádka 44:</td> <td colspan="2" class="diff-lineno">Řádka 44:</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>podmínka nezápornosti, tudíž se nerovnosti nenaruší.</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>podmínka nezápornosti, tudíž se nerovnosti nenaruší.</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 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 style="font-weight: bold; text-decoration: none;">\begin{remark}</del></div></td><td colspan="2">&#160;</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 style="font-weight: bold; text-decoration: none;"> Hodnota účelové funkci na množine optimálních řešení je konstantní.</del></div></td><td colspan="2">&#160;</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 style="font-weight: bold; text-decoration: none;">\begin{proof}</del></div></td><td colspan="2">&#160;</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 style="font-weight: bold; text-decoration: none;"> Nechť množina optimálních řešení dané úlohy LP obsahuje alespoň dva prvky. Pro spor předpokládejme že existují dvě optimální řešení $\x_1 ,\x_2$&#160; takové, že $z(\x_1) \neq z(\x_2)$. Bez ujmy na obecnosti nechť $z(\x_2) &gt; z(\x_1)$.</del></div></td><td colspan="2">&#160;</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 style="font-weight: bold; text-decoration: none;"> Nechť $\y_1 ,\y_2$ jsou příslušná optimální řešení úlohy duální. Pak platí $c\x_1 \textless \y_2 b$ což je spor s předchozí větou.</del></div></td><td colspan="2">&#160;</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 style="font-weight: bold; text-decoration: none;">\end{proof}</del></div></td><td colspan="2">&#160;</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 style="font-weight: bold; text-decoration: none;">\end{remark}</del></div></td><td colspan="2">&#160;</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{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>\end{theorem}</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 colspan="2" class="diff-lineno" id="L134" >Řádka 134:</td> <td colspan="2" class="diff-lineno">Řádka 127:</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>\noqed</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>\noqed</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;">\begin{remark}</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;"> Hodnota účelové funkci na množine optimálních řešení je konstantní.</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;">\begin{proof}</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;"> Nechť množina optimálních řešení dané úlohy LP obsahuje alespoň dva prvky. Pro spor předpokládejme že existují dvě optimální řešení $\x_1 ,\x_2$&#160; takové, že $z(\x_1) \neq z(\x_2)$. Bez ujmy na obecnosti nechť $z(\x_2) &gt; z(\x_1)$.</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;"> Nechť $\y_1 ,\y_2$ jsou příslušná optimální řešení úlohy duální. Pak platí $c\x_1 \textless \y_2 b$ což je spor s předchozí větou.</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;">\end{proof}</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;">\end{remark}</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>\end{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>\end{theorem}</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> </table> Pohanjur https://wikiskripta.fjfi.cvut.cz/wiki/index.php?title=01LIP:Kapitola2&diff=4283&oldid=prev Pohanjur v 3. 7. 2011, 19:27 2011-07-03T19:27:55Z <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 3. 7. 2011, 19:27</td> </tr><tr><td colspan="2" class="diff-lineno" id="L44" >Řádka 44:</td> <td colspan="2" class="diff-lineno">Řádka 44:</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>podmínka nezápornosti, tudíž se nerovnosti nenaruší.</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>podmínka nezápornosti, tudíž se nerovnosti nenaruší.</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;">\begin{remark}</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;"> Hodnota účelové funkci na množine optimálních řešení je konstantní.</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;">\begin{proof}</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;"> Nechť množina optimálních řešení dané úlohy LP obsahuje alespoň dva prvky. Pro spor předpokládejme že existují dvě optimální řešení $\x_1 ,\x_2$&#160; takové, že $z(\x_1) \neq z(\x_2)$. Bez ujmy na obecnosti nechť $z(\x_2) &gt; z(\x_1)$.</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;"> Nechť $\y_1 ,\y_2$ jsou příslušná optimální řešení úlohy duální. Pak platí $c\x_1 \textless \y_2 b$ což je spor s předchozí větou.</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;">\end{proof}</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;">\end{remark}</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>\end{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>\end{theorem}</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> </table> Pohanjur https://wikiskripta.fjfi.cvut.cz/wiki/index.php?title=01LIP:Kapitola2&diff=3618&oldid=prev Karel.brinda v 13. 9. 2010, 11:52 2010-09-13T11:52:17Z <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:52</td> </tr><tr><td colspan="2" class="diff-lineno" id="L6" >Řádka 6:</td> <td colspan="2" class="diff-lineno">Řádka 6:</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>\min z&amp;=\sum_{j=1}^n c_jx_j &amp; \max w&amp;=\sum_{i=1}^m y_ib_i\\</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>\min z&amp;=\sum_{j=1}^n c_jx_j &amp; \max w&amp;=\sum_{i=1}^m y_ib_i\\</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>\sum_{j=1}^n a_{ij}x_j&amp;\ge b_i,\ i\in\I\subset\hat m &amp; y_i&amp;\ge 0,\ i\in\I\subset\hat m\\</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>\sum_{j=1}^n a_{ij}x_j&amp;\ge b_i,\ i\in\I\subset\hat m &amp; y_i&amp;\ge 0,\ i\in\I\subset\hat m\\</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>\sum_{j=1}^n a_{ij}x_j&amp;= b_i,\ i\in\hat m\sm\I &amp; y_i&amp;\<del class="diffchange diffchange-inline">lesseqgtr 0</del>,\ i\in\hat m\sm\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>\sum_{j=1}^n a_{ij}x_j&amp;= b_i,\ i\in\hat m\sm\I &amp; y_i&amp;\<ins class="diffchange diffchange-inline">in\R</ins>,\ i\in\hat m\sm\I\\</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>x_j&amp;\ge 0,\ j\in\J\subset\hat n &amp; \sum_{i=1}^m y_ia_{ij}&amp;\le c_j,\ j\in\J\subset\hat n\\</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>x_j&amp;\ge 0,\ j\in\J\subset\hat n &amp; \sum_{i=1}^m y_ia_{ij}&amp;\le c_j,\ j\in\J\subset\hat n\\</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>x_j&amp;\<del class="diffchange diffchange-inline">lesseqgtr 0</del>,\ j\in\hat n\sm\J &amp; \sum_{i=1}^m y_ia_{ij}&amp;= c_j,\ j\in\hat n\sm\J\\</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>x_j&amp;\<ins class="diffchange diffchange-inline">in\R</ins>,\ j\in\hat n\sm\J &amp; \sum_{i=1}^m y_ia_{ij}&amp;= c_j,\ j\in\hat n\sm\J\\</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{align*}</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{align*}</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> </table> Karel.brinda https://wikiskripta.fjfi.cvut.cz/wiki/index.php?title=01LIP:Kapitola2&diff=3617&oldid=prev Karel.brinda v 13. 9. 2010, 11:49 2010-09-13T11:49:45Z <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:49</td> </tr><tr><td colspan="2" class="diff-lineno" id="L368" >Řádka 368:</td> <td colspan="2" class="diff-lineno">Řádka 368:</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>soustavy $\A x=b$. Potom</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>soustavy $\A x=b$. Potom</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>\[</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>\[</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>\h\left(\subm{\A}{<del class="diffchange diffchange-inline">1</del>,\dots,<del class="diffchange diffchange-inline">k</del>}{1,\dots,k}\right)=k<del class="diffchange diffchange-inline">=</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>\h\left(\subm{\A}{<ins class="diffchange diffchange-inline">i_1</ins>,\dots,<ins class="diffchange diffchange-inline">i_k</ins>}{1,\dots,k}\right) = k.</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">\h\left(\subm{\A}{i_1,\dots,i_k}{1,\dots,k}\right)</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></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>\]</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>\]</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>Soustava rovnic</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>Soustava rovnic</div></td></tr> </table> Karel.brinda https://wikiskripta.fjfi.cvut.cz/wiki/index.php?title=01LIP:Kapitola2&diff=3613&oldid=prev Karel.brinda: Doplnění vypadlého indexu 2010-09-12T21:27:11Z <p>Doplnění vypadlého indexu</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 12. 9. 2010, 21:27</td> </tr><tr><td colspan="2" class="diff-lineno" id="L206" >Řádka 206:</td> <td colspan="2" class="diff-lineno">Řádka 206:</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>\right)\ge</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>\right)\ge</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>\sum_{j=1}^k\alpha_j f(v_j)\ge</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>\sum_{j=1}^k\alpha_j f(v_j)\ge</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>\sum_{j=1}^k\<del class="diffchange diffchange-inline">alpha</del>\min_{j\in\hat k}f(v_j)=</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>\sum_{j=1}^k\<ins class="diffchange diffchange-inline">alpha_j</ins>\min_{j\in\hat k}f(v_j)=</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>\min_{j\in\hat k} f(v_j)\underbrace{\sum_{j=1}^k\alpha_j}_{=1}=</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>\min_{j\in\hat k} f(v_j)\underbrace{\sum_{j=1}^k\alpha_j}_{=1}=</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>\min_{j\in\hat k} f(v_j)=f(v_{j_0}).\qed</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>\min_{j\in\hat k} f(v_j)=f(v_{j_0}).\qed</div></td></tr> </table> Karel.brinda https://wikiskripta.fjfi.cvut.cz/wiki/index.php?title=01LIP:Kapitola2&diff=3561&oldid=prev Tomsus: chybky 2010-08-31T22:22:24Z <p>chybky</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 31. 8. 2010, 22:22</td> </tr><tr><td colspan="2" class="diff-lineno" id="L4" >Řádka 4:</td> <td colspan="2" class="diff-lineno">Řádka 4:</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{align*}</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{align*}</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>\text{Primární&#160; úloha:} &amp;&amp; \text{Duální úloha:}&amp;\\</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>\text{Primární&#160; úloha:} &amp;&amp; \text{Duální úloha:}&amp;\\</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>\min z&amp;=\sum_{j=1}^n <del class="diffchange diffchange-inline">x_jx_j </del>&amp; \max w&amp;=\sum_{i=1}^m y_ib_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>\min z&amp;=\sum_{j=1}^n <ins class="diffchange diffchange-inline">c_jx_j </ins>&amp; \max w&amp;=\sum_{i=1}^m y_ib_i\\</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>\sum_{<del class="diffchange diffchange-inline">i</del>=1}^n a_{ij}x_j&amp;\ge b_i,\ i\in\I\subset\hat m &amp; y_i&amp;\ge 0,\ i\in\I\subset\hat m\\</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>\sum_{<ins class="diffchange diffchange-inline">j</ins>=1}^n a_{ij}x_j&amp;\ge b_i,\ i\in\I\subset\hat m &amp; y_i&amp;\ge 0,\ i\in\I\subset\hat m\\</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>\sum_{<del class="diffchange diffchange-inline">i</del>=1}^n a_{ij}x_j&amp;= b_i,\ i\in\hat m\sm\I &amp; y_i&amp;\lesseqgtr 0,\ i\in\hat m\sm\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>\sum_{<ins class="diffchange diffchange-inline">j</ins>=1}^n a_{ij}x_j&amp;= b_i,\ i\in\hat m\sm\I &amp; y_i&amp;\lesseqgtr 0,\ i\in\hat m\sm\I\\</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>x_j&amp;\ge 0,\ j\in\J\subset\hat n &amp; \sum_{i=1}^m y_ia_{ij}&amp;\le c_j,\ j\in\J\subset\hat n\\</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>x_j&amp;\ge 0,\ j\in\J\subset\hat n &amp; \sum_{i=1}^m y_ia_{ij}&amp;\le c_j,\ j\in\J\subset\hat n\\</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>x_j&amp;\lesseqgtr 0,\ j\in\hat n\sm\J &amp; \sum_{i=1}^m y_ia_{ij}&amp;= c_j,\ j\in\hat n\sm\J\\</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>x_j&amp;\lesseqgtr 0,\ j\in\hat n\sm\J &amp; \sum_{i=1}^m y_ia_{ij}&amp;= c_j,\ j\in\hat n\sm\J\\</div></td></tr> </table> Tomsus https://wikiskripta.fjfi.cvut.cz/wiki/index.php?title=01LIP:Kapitola2&diff=3200&oldid=prev Admin: Založena nová stránka: %\wikiskriptum{01LIP} \section{Dualita v~LP} \begin{align*} \text{Primární úloha:} && \text{Duální úloha:}&\\ \min z&=\sum_{j=1}^n x_jx_j & \max w&=\sum_{i=1}^m y_... 2010-08-01T00:40:18Z <p>Založena nová stránka: %\wikiskriptum{01LIP} \section{Dualita v~LP} \begin{align*} \text{Primární úloha:} &amp;&amp; \text{Duální úloha:}&amp;\\ \min z&amp;=\sum_{j=1}^n x_jx_j &amp; \max w&amp;=\sum_{i=1}^m y_...</p> <p><b>Nová stránka</b></p><div>%\wikiskriptum{01LIP}<br /> \section{Dualita v~LP}<br /> <br /> \begin{align*}<br /> \text{Primární úloha:} &amp;&amp; \text{Duální úloha:}&amp;\\<br /> \min z&amp;=\sum_{j=1}^n x_jx_j &amp; \max w&amp;=\sum_{i=1}^m y_ib_i\\<br /> \sum_{i=1}^n a_{ij}x_j&amp;\ge b_i,\ i\in\I\subset\hat m &amp; y_i&amp;\ge 0,\ i\in\I\subset\hat m\\<br /> \sum_{i=1}^n a_{ij}x_j&amp;= b_i,\ i\in\hat m\sm\I &amp; y_i&amp;\lesseqgtr 0,\ i\in\hat m\sm\I\\<br /> x_j&amp;\ge 0,\ j\in\J\subset\hat n &amp; \sum_{i=1}^m y_ia_{ij}&amp;\le c_j,\ j\in\J\subset\hat n\\<br /> x_j&amp;\lesseqgtr 0,\ j\in\hat n\sm\J &amp; \sum_{i=1}^m y_ia_{ij}&amp;= c_j,\ j\in\hat n\sm\J\\<br /> \end{align*}<br /> <br /> Úloha ve {\bf standardním tvaru}: samé nerovnice<br /> \begin{align*}<br /> \min z&amp; =cx &amp; \max w&amp; =yb\\<br /> \A x&amp; \ge b &amp; y\A&amp; \le c\\<br /> x&amp; \ge 0 &amp; y&amp; \ge 0.<br /> \end{align*}<br /> <br /> Úloha v~{\bf kanonickém tvaru}: samé rovnice, nezápornost<br /> \begin{align*}<br /> \min z&amp; =cx &amp; \max w&amp; =yb\\<br /> \A x&amp; = b &amp; y\A&amp; \le c\\<br /> x&amp; \ge 0 &amp; y&amp; \lesseqgtr 0.<br /> \end{align*}<br /> <br /> \begin{theorem}<br /> \label{v_pd}<br /> Nechť je dána dvojice (duálních) úloh LP, nechť $\x$<br /> (resp. $\y$) je přípustné řešení primární, resp. duální<br /> úlohy. Potom platí: $\y b\le c\x$.<br /> \begin{proof}<br /> Pro úlohu ve standardním tvaru:<br /> \begin{align*}<br /> \A\x&amp;\ge b &amp; \y\A\le c\\<br /> \x&amp;\ge 0 &amp; \y\ge 0<br /> \end{align*}<br /> vynásobením $\x$ zprava a $\y$ zleva dostaneme<br /> \begin{align*}<br /> \y\A\x&amp;\ge\y b &amp; \y\A\x\le c\x,<br /> \end{align*}<br /> tedy $\y b\le\y\A\x\le c\x$. Pokud není úloha ve standardním tvaru, nic<br /> se nemění, je nutné si uvědomit, že nerovnici odpovídá v~duální úloze<br /> podmínka nezápornosti, tudíž se nerovnosti nenaruší.<br /> \end{proof}<br /> \end{theorem}<br /> <br /> \begin{theorem}[o~dualitě]<br /> Nechť je dána dvojice úloh LP ve standardním tvaru. Potom nastává<br /> právě jedna z~následujících možností:<br /> \begin{enumerate}[(i)]<br /> \item Obě úlohy mají optimální řešení a hodnoty účelových funkcí na<br /> nich jsou si rovny.<br /> \item Jedna z~úloh nemá žádné přípustné řešení, druhá má přípustné<br /> řešení, ale nemá optimální řešení.<br /> \item Žádná z~úloh nemá přípustné řešení.<br /> \end{enumerate}<br /> \begin{proof}<br /> Řešme soustavu nerovnic<br /> \begin{align*}<br /> \A x-tb&amp;\ge 0 &amp; x&amp;\ge 0\\<br /> -y\A+tc&amp;\ge 0 &amp; y&amp;\ge 0\\<br /> yb-cx&amp;\ge 0 &amp; t&amp;\ge 0.<br /> \end{align*}<br /> Nechť $x_0,y_0,t_0$ je řešením této soustavy (existenci zaručuje věta<br /> \ref{v_lin_ner}).<br /> \begin{enumerate}<br /> \item Nechť $t_0&gt;0$. Pak<br /> \begin{align*}<br /> \A x_0&amp;\ge t_0 b &amp; \implies &amp;&amp; \A\frac{x_0}{t_0}&amp;\ge b\\<br /> y_0\A&amp;\le t_0 c &amp; \implies &amp;&amp; \frac{y_0}{t_0}\A&amp;\le c<br /> \end{align*}<br /> $\frac{x_0}{t_0}$ a $\frac{y_0}{t_0}$ jsou přípustná řešení primární,<br /> resp. duální úlohy. Dokážeme, že jsou optimální:<br /> \[<br /> y_0 b\ge c x_0\implies\frac{y_0}{t_0}b\ge c\frac{x_0}{t_0}.<br /> \]<br /> Protože ale podle věty \ref{v_pd} je<br /> \[\frac{y_0}{t_0}b\le c\frac{x_0}{t_0},\]<br /> je<br /> \[\frac{y_0}{t_0}b= c\frac{x_0}{t_0},\]<br /> takže tato řešení jsou optimální a hodnoty účelové funkce se na nich<br /> rovnají.<br /> \item Buď $t_0=0$. Dokážeme, že v~tomto případě nemohou mít obě úlohy<br /> současně přípustné řešení. Platí, že<br /> \begin{align*}<br /> \A x_0&amp;\ge 0 &amp; x_0&amp;\ge 0\\<br /> y_0\A&amp;\le 0 &amp; y_0&amp;\ge 0.<br /> \end{align*}<br /> Předpokládejme, že existují přípustná řešení obou úloh, označme je<br /> $\x$, $\y$. Vynásobením nerovnic dostaneme<br /> \begin{align*}<br /> 0&amp;\ge y_0\A &amp; \A\x&amp;\ge b &amp; \implies &amp;&amp; 0&amp;\ge y_0\A\x\ge y_0 b\\<br /> 0&amp;\le \A x_0 &amp; \y\A&amp;\le c &amp; \implies &amp;&amp; 0&amp;\le \y\A x_0\le c x_0,<br /> \end{align*}<br /> tedy $c x_0\ge y_0 b$. Z~věty \ref{v_lin_ner} ale okamžitě vyplývá, že $y_0 b-c<br /> x_0+t_0&gt;0$, tedy $y_0 b&gt;c x_0$, což je spor.<br /> <br /> Nechť $\x$ je přípustné řešení primární úlohy, nechť duální nemá<br /> přípustné řešení. Dokážeme, že účelová funkce není omezená. Uvažujme<br /> vektor $\x+\alpha x_0$, kde $\alpha\ge 0$. Platí, že<br /> \[\x+\alpha x_0\ge0,\quad<br /> \underbrace{\A\x}_{\ge b}+<br /> \underbrace{\alpha\A x_0}_{\ge 0}\ge b,\]<br /> takže $\x+\alpha x_0$ je přípustné řešení primární úlohy pro libovolné<br /> $\alpha\ge 0$.<br /> Protože $0\ge y_0\A\x\ge y_0 b&gt;c x_0$, tedy $c x_0&lt;0$, je<br /> \[\lim_{\alpha\to +\infty}c(\x+\alpha x_0)=<br /> \lim_{\alpha\to\infty}c\x+\alpha c x_0=-\infty.\]<br /> \item Případ (iii) může nastat například v~úloze<br /> \[<br /> \A=<br /> \begin{pmatrix}<br /> -1 &amp; 0 \\<br /> 0 &amp; 1<br /> \end{pmatrix},<br /> \quad<br /> b=\begin{pmatrix}<br /> 1\\ 1<br /> \end{pmatrix},<br /> \quad<br /> c=(1,-1),<br /> \]<br /> kde podmínky $-x_1\ge 1\wedge x_1\ge 0$ a<br /> $y_2\le -1\wedge y_2\ge 0$ evidentně nelze splnit.\qed<br /> \end{enumerate}<br /> \noqed<br /> \end{proof}<br /> \end{theorem}<br /> <br /> \begin{theorem}[o~slabé komplementaritě]<br /> Nechť je dána dvojice (duálních) úloh LP, nechť $\x$<br /> (resp. $\y$) jsou přípustná řešení primární (resp. duální)<br /> úlohy. Potom $\x$ a $\y$ jsou optimální, právě když<br /> $\y(\A\x-b)=0$ a<br /> $(c-\y\A)\x=0$.<br /> \begin{proof}<br /> Označme $\alpha=\y(\A\x-b)$, $\beta=(c-\y\A)\x$. Platí, že<br /> $\alpha+\beta=c\x-\y b$.<br /> \begin{enumerate}[1)]<br /> \item $\Rightarrow$: Platí, že $\alpha\ge 0$ a $\beta\ge 0$. Pro<br /> standardní tvar je to jasné (nerovnice násobím kladnými čísly), jinak<br /> ale zápornými čísly násobím vždy jen rovnice, takže i~v~tom případě je<br /> to korektní.<br /> <br /> Pro optimální řešení platí $\alpha+\beta=c\x-\y<br /> b=0$, takže $\alpha=\beta=0$.<br /> \item $\Leftarrow$: $c\x=\y b$, takže řešení je optimální.\qed<br /> \end{enumerate}<br /> \noqed<br /> \end{proof}<br /> \end{theorem}<br /> <br /> \begin{dusl}<br /> Platí<br /> \begin{align*}<br /> \y_i&gt;0&amp;\implies \A_{i\bullet}\x=b_i &amp; <br /> \y\A_{\bullet i}&lt;c_i&amp;\implies \x_i=0 \\<br /> \A_{i\bullet}\x&gt;b_i&amp;\implies\y_i=0 &amp;<br /> \x_i&gt;0&amp;\implies\y\A_{\bullet i}=c_i.<br /> \end{align*}<br /> To mi umožňuje při znalosti optimálního řešení primární úlohy nalézt<br /> řešení duální. Nulové složky $y$ určím rovnou, ostatní řešením<br /> soustavy rovnic $\y\A_{\bullet i}=c_i$.<br /> <br /> Tímto způsobem lze testovat i~optimalitu řešení: Pokud se mi k~$\x$<br /> podaří tímto způsobem najít $\y$, které je přípustné, je $\x$<br /> optimální.<br /> \end{dusl}<br /> <br /> \begin{theorem}[o~silné komplementaritě]<br /> Nechť je dána dvojice úloh LP ve standardním tvaru, nechť obě úlohy<br /> mají přípustná řešení. Potom existují optimální řešení $\x$ resp. $\y$<br /> taková, že<br /> \begin{align*}<br /> \A\x-b+\y^T&amp;&gt;0\\<br /> c-\y\A+\x^T&amp;&gt;0.<br /> \end{align*}<br /> \begin{proof}<br /> Důsledek věty \ref{v_lin_ner} a důkazu věty o~dualitě.<br /> \end{proof}<br /> \end{theorem}<br /> <br /> \begin{define}<br /> Krajním bodem (vrcholem) konvexní množiny nazýváme takový bod této<br /> množiny, který není konvexní kombinací dvou jiných různých bodů této<br /> množiny.<br /> \end{define}<br /> <br /> \begin{lemma}<br /> Množina vzniklá průnikem poloprostorů je konvexním obalem svých<br /> vrcholů.<br /> \end{lemma}<br /> <br /> \begin{theorem}<br /> Nechť $f$ je konkávní funkce definovaná na konvexním mnohostěnu<br /> $T$. Potom tato funkce nabývá svého minima v~krajním bodě $T$.<br /> \begin{proof}<br /> Označme $v_1,\dots,v_k$ vrcholy $T$. Pak podle předchozího lemmatu je<br /> $T=\kob{v_1,\dots,v_k}$.<br /> Buď $x\in T$. Pak<br /> \[x=\sum_{j=1}^k\alpha_j v_j,\quad \alpha\ge 0,<br /> \quad\sum_{j=1}^k\alpha_j=1.\]<br /> \[f(x)=f\left(<br /> \sum_{j=1}^k\alpha_j v_j<br /> \right)\ge<br /> \sum_{j=1}^k\alpha_j f(v_j)\ge<br /> \sum_{j=1}^k\alpha\min_{j\in\hat k}f(v_j)=<br /> \min_{j\in\hat k} f(v_j)\underbrace{\sum_{j=1}^k\alpha_j}_{=1}=<br /> \min_{j\in\hat k} f(v_j)=f(v_{j_0}).\qed<br /> \]<br /> \noqed<br /> \end{proof}<br /> \end{theorem}<br /> <br /> \begin{define}<br /> Nechť je dána soustava lineárních rovnic $\A x=b$, nechť $\x$ je její<br /> řešení. Řekneme, že $\x$ je bazické řešení, právě když sloupce matice<br /> $\A$ odpovídající nenulovým složkám $\x$ jsou lineárně nezávislé.<br /> \end{define}<br /> <br /> \begin{remark}<br /> V~lineárním programování je $\A\in\R^{m,n}$, $\A x=b$, $m&lt;n$,<br /> $\h(\A)=m$. Buď $\A=(\B|\mathbf N)$, kde $\B$ je regulární. Pak<br /> \[x=\begin{pmatrix}<br /> x_\B\\x_{\mathbf N}<br /> \end{pmatrix},\]<br /> kde $x_{\mathbf N}=0$, $x_\B=\B^{-1}b$. Pokud jsou všechny složky<br /> $x_\B\not=0$ , nazýváme takové řešení {\bf nedegenerované}, jinak {\bf<br /> degenerované}.<br /> \end{remark}<br /> <br /> \begin{theorem}<br /> Každá řešitelná soustava lineárních rovnic má bazické řešení.<br /> \begin{proof}<br /> Soustavu převedu na horní stupňovitý tvar, složky řešení odpovídající<br /> vedlejším sloupcům položím rovny nule, ostatní dopočítám. Získané<br /> řešení je bazické.<br /> \end{proof}<br /> \end{theorem}<br /> <br /> \begin{theorem}<br /> Má-li soustava lineárních rovnic nezáporné řešení, má i~bazické<br /> nezáporné řešení.<br /> \begin{proof}<br /> Indukcí podle počtu sloupců $n$.<br /> \begin{enumerate}[1)]<br /> \item Buď $n=1$, $x_1\A_{\bullet 1}=b$. Je-li $\A_{\bullet 1}\not=0$,<br /> je $x_1$ bazické. Pokud $\A_{\bullet 1}=0$, musí být $b=0$ a $x_1=0$<br /> je bazické řešení.<br /> \item Buď<br /> \[\x=<br /> \begin{pmatrix}<br /> \x_1\\\vdots\\\x_n<br /> \end{pmatrix}<br /> \ge 0\]<br /> nezáporné řešení soustavy<br /> \[\sum_{j=1}^n\A_{\bullet j} x_j=b.\]<br /> \begin{enumerate}[A)]<br /> \item Existuje $j_0\in\hat n$ takové, že $\x_{j_0}=0$. Pak soustava<br /> \[\sum_{\substack{j=1\\j\not=j_0}}^n\A_{\bullet j} x_j=b\]<br /> o~$n-1$ sloupcích má nezáporné řešení a podle indukčního předpokladu<br /> má i~bazické nezáporné řešení.<br /> \item $\x_j&gt;0$ pro každé $j\in\hat n$:<br /> \begin{enumerate}[a)]<br /> \item $(\A_{\bullet j})_{j\in\hat n}$ je lineárně nezávislý, tedy<br /> řešení je bazické.<br /> \item $(\A_{\bullet j})_{j\in\hat n}$ je lineárně závislý. Uvažujme<br /> netriviální lineární kombinaci<br /> \[\sum_{j=1}^n\lambda_j\A_{\bullet j}=0.\]<br /> Bez újmy na obecnosti můžeme předpokládat, že existuje alespoň jedno<br /> $j\in\hat n$ tak, že $\lambda_j&gt;0$ (pokud ne, můžeme sumu vynásobit<br /> $-1$ a stále bude rovna nule). Položme<br /> \[\max_{j\in\hat n}\frac{\lambda_j}{\x_j}=<br /> \frac{\lambda_{j_0}}{\x_{j_0}}&gt;0.\]<br /> Nulovou netriviální kombinaci vynásobíme<br /> $-\frac{\x_{j_0}}{\lambda_{j_0}}$ a přičteme k~ní soustavu rovnic:<br /> \[\sum_{j=1}^n\left(<br /> \x_j-\frac{\lambda_j\x_{j_0}}{\lambda_{j_0}}<br /> \right)\A_{\bullet j}=b,\]<br /> \[\sum_{j=1}^n<br /> \underbrace{\frac{\x_j\x_{j_0}}{\lambda_{j_0}}}_{&gt;0}<br /> \underbrace{<br /> \left(<br /> \frac{\lambda_{j_0}}{\x_{j_0}}-\frac{\lambda_j}{\x_j}<br /> \right)}_{\ge 0}<br /> \A_{\bullet j}=b.\]<br /> Alespoň $j_0$-tý sčítanec je nulový. Našli jsme tak nezáporné řešení<br /> soustavy o~$n-1$ sloupcích, podle indukčního předpokladu existuje<br /> i~bazické nezáporné řešení.<br /> \qed<br /> \end{enumerate}<br /> \end{enumerate}<br /> \end{enumerate}<br /> \noqed<br /> \end{proof}<br /> \end{theorem}<br /> <br /> \begin{theorem}<br /> Nechť <br /> $T=\{x \in R^{n,1} | \A_{i\bullet}x \le b_i,\ i\in \J \subset \hat m \wedge \A_{i\bullet}x = b_i, i \in \hat m - \J\}$,<br /> $m\ge n$, $\x\in T$. Potom $\x$ je krajní bod $T$, právě když existují<br /> navzájem různé indexy $i_1,\dots,i_n\in\hat m$ takové, že $\x$ je<br /> jediným řešením soustavy lineárních rovnic $\A_{i\bullet}x=b_i$,<br /> $i\in\{i_1,\dots,i_n\}$ (tzn. submatice<br /> \[\subm{\A}{i_1,\dots,i_n}{1,\dots,n}=\overline\A\]<br /> je regulární).<br /> \begin{proof}<br /> \begin{enumerate}[1)]<br /> \item $\Leftarrow$: Buďte $x_1,x_2\in T$, $x_1\not=x_2$ takové, že<br /> $\x=\alpha x_1+(1-\alpha)x_2$,<br /> \[\overline b=\begin{pmatrix}<br /> b_{i_1}\\\vdots\\b_{i_n}<br /> \end{pmatrix}.\]<br /> Pak<br /> \[\overline b=\overline\A\x=\alpha\overline\A x_1+<br /> (1-\alpha)\overline\A x_2\le\alpha\overline b+<br /> (1-\alpha)\overline b=\overline b,\]<br /> tedy $\overline\A x_1=\overline b$ a $\overline\A x_2=\overline b$,<br /> což je spor s~jednoznačností řešení.<br /> \item $\Rightarrow$: Položme $\I=\{i\in\hat m|\A_{i\bullet}\x=b_i\}$<br /> \begin{enumerate}[a)]<br /> \item Dokážeme, že $\I$ je neprázdná. Předpokládejme, že $\I=\emptyset$,<br /> tj. $\A_{i\bullet}\x&lt;b_i$ pro každé $i\in\hat m$. Buď <br /> $\tilde x\in\R^{n,1}$, libovolné, $\tilde x\not=0$. Zvolme<br /> $x_1=\x+\epsilon\tilde x$, $x_2=\x-\epsilon\tilde x$,<br /> $\epsilon&gt;0$. Pak pro dostatečně malé $\epsilon$ platí<br /> $\A_{i\bullet}x_{1,2}=<br /> \A_{i\bullet}\x\pm\epsilon\A_{i\bullet}\tilde x\le b_i$ pro každé<br /> $i\in\hat m$.<br /> Pak ale $x_1,x_2\in T$, $x_1\not=x_2$ a $\x=\frac12 x_1+\frac12 x_2$,<br /> tedy $\x$ není krajní bod, což je spor.<br /> \item Dokážeme, že $\abs{\I}\ge n$. Předpokládejme, že<br /> $\abs{\I}&lt;n$. Pak musí existovat $\tilde x\not=0$ takové, že<br /> $\A_{i\bullet}\tilde x=0$ pro $i\in\I$, neboť matice soustavy má<br /> hodnost menší než $n$. Zvolme opět $x_1=\x+\epsilon\tilde x$,<br /> $x_2=\x-\epsilon\tilde x$. Dosazením dostaneme stejnou nerovnost jako<br /> v~předchozím případě (rovnosti se nenaruší, protože<br /> $\A_{i\bullet}\tilde x=0$) a opět dojdeme ke sporu.<br /> \item $\h((\A_{i\bullet})_{i\in\I})=n$, právě když<br /> $\lob{(\A_{i\bullet})_{i\in\I}}=\R^n$. Hodnost dokážeme stejně jako v~předchozím případě, pak můžeme vybrat $n$-člennou bázi.\qed<br /> \end{enumerate}<br /> \end{enumerate}<br /> \noqed<br /> \end{proof}<br /> \end{theorem}<br /> <br /> \begin{dusl}<br /> Buď<br /> \[<br /> T\equiv\left|<br /> \begin{split}<br /> \A x&amp;=b\\<br /> x&amp;\ge 0.<br /> \end{split}<br /> \right.<br /> \]<br /> Pak $\x$ je bazické nezáporné řešení soustavy $\A x=b$, právě když<br /> $\x$ je krajní bod $T$.<br /> \begin{proof}<br /> \begin{enumerate}[1)]<br /> \item $\Rightarrow$: Bez újmy na obecnosti můžeme předpokládat, že<br /> prvních $k$ sloupců matice $\A$ je LN. Buď<br /> \[\x=\begin{pmatrix}<br /> \x_1\\\vdots\\\x_n<br /> \end{pmatrix},\]<br /> kde $\x_i&gt;0$ pro $i\in\hat k$, $\x_i=0$ pro $i&gt;k$ bazické řešení<br /> soustavy $\A x=b$. Potom<br /> \[<br /> \h\left(\subm{\A}{1,\dots,k}{1,\dots,k}\right)=k=<br /> \h\left(\subm{\A}{i_1,\dots,i_k}{1,\dots,k}\right).<br /> \]<br /> Soustava rovnic<br /> \begin{align*}<br /> \A_{{i_j}\bullet}x_j&amp;=b_{i_j},\ j\in\hat k\\<br /> x_j&amp;=0,\ j&gt;k~\end{align*}<br /> má podle Frobeniovy věty jediné řešení $\x$, tedy $\x$ je krajní bod<br /> $T$.<br /> \item $\Leftarrow$: Buď $\x$ krajní bod $T$. <br /> <br /> Buď $\x_i&gt;0$ pro $i\in\hat k$, $\x_i=0$ pro $i&gt;k$.<br /> \[<br /> \left(<br /> \begin{array}{c|ccc}<br /> \\<br /> \text{regulární} &amp; &amp; 0\\<br /> \\<br /> \hline<br /> &amp; 1 &amp; \\<br /> 0 &amp; &amp; \ddots \\<br /> &amp; &amp; &amp; 1<br /> \end{array}<br /> \right).<br /> \]<br /> Levý horní blok má nezávislé sloupce, tudíž prvních $k$ sloupců matice<br /> $\A$ je lineárně nezávislých.\qed<br /> \end{enumerate}<br /> \noqed<br /> \end{proof}<br /> \end{dusl}<br /> <br /> \begin{theorem}<br /> Nechť je dána úloha LP v~kanonickém tvaru<br /> ($\min z=cx$, $\A x=b$, $x\ge 0$), nechť množina přípustných řešení je<br /> neprázdná a omezená. Potom existuje bazické optimální řešení této<br /> úlohy.<br /> \begin{proof}<br /> Množina je neprázdná a omezená $\implies$ je to konvexní mnohostěn<br /> $\implies$ lineární funkce nabývá minima v~krajním bodě $\implies$<br /> existuje bazické optimální řešení.<br /> \end{proof}<br /> \end{theorem}<br /> <br /> \begin{define}<br /> Pojmem {\bf řešit úlohu LP} rozumíme buď<br /> \begin{enumerate}[(i)]<br /> \item najít minimum $z$ a bod, v~němž $z$ minima nabývá nebo<br /> \item ukázat, že $z$ není omezená zdola nebo<br /> \item množina přípustných řešení je prázdná.<br /> \end{enumerate}<br /> \end{define}</div> Admin