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'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>\end{proof}</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>\end{proof}</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>\begin{remark}</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>\begin{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>  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>  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'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>\begin{proof}</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>\begin{proof}</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>  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$  takové, že $z(\x_1) \neq z(\x_2)$. Bez ujmy na obecnosti nechť $z(\x_2) > z(\x_1)$.</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>  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$  takové, že $z(\x_1) \neq z(\x_2)$. Bez ujmy na obecnosti nechť $z(\x_2) > 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>  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>  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'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>\end{proof}</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>\end{proof}</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>\end{remark}</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>\end{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'> </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'> </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'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>\end{proof}</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>\end{proof}</div></td></tr>
<tr><td 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"> </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"> </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"> </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$  takové, že $z(\x_1) \neq z(\x_2)$. Bez ujmy na obecnosti nechť $z(\x_2) > z(\x_1)$.</del></div></td><td colspan="2"> </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"> </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"> </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"> </td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>\end{theorem}</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>\end{theorem}</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>   </div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>   </div></td></tr>
<tr><td 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'> </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'> </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'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>\end{proof}</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>\end{proof}</div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">\begin{remark}</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"> Hodnota účelové funkci na množine optimálních řešení je konstantní.</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">\begin{proof}</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"> 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$  takové, že $z(\x_1) \neq z(\x_2)$. Bez ujmy na obecnosti nechť $z(\x_2) > z(\x_1)$.</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"> 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"> </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"> </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'> </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'> </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'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>   </div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>   </div></td></tr>
</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'> </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'> </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'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>\end{proof}</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>\end{proof}</div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">\begin{remark}</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"> Hodnota účelové funkci na množine optimálních řešení je konstantní.</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">\begin{proof}</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"> 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$  takové, že $z(\x_1) \neq z(\x_2)$. Bez ujmy na obecnosti nechť $z(\x_2) > z(\x_1)$.</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"> 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"> </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"> </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'> </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'> </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'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>   </div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>   </div></td></tr>
</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'> </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&=\sum_{j=1}^n c_jx_j & \max w&=\sum_{i=1}^m y_ib_i\\</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>\min z&=\sum_{j=1}^n c_jx_j & \max w&=\sum_{i=1}^m y_ib_i\\</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>\sum_{j=1}^n a_{ij}x_j&\ge b_i,\ i\in\I\subset\hat m & y_i&\ge 0,\ i\in\I\subset\hat m\\</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>\sum_{j=1}^n a_{ij}x_j&\ge b_i,\ i\in\I\subset\hat m & y_i&\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&= b_i,\ i\in\hat m\sm\I & y_i&\<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&= b_i,\ i\in\hat m\sm\I & y_i&\<ins class="diffchange diffchange-inline">in\R</ins>,\ i\in\hat m\sm\I\\</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>x_j&\ge 0,\ j\in\J\subset\hat n & \sum_{i=1}^m y_ia_{ij}&\le c_j,\ j\in\J\subset\hat n\\</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>x_j&\ge 0,\ j\in\J\subset\hat n & \sum_{i=1}^m y_ia_{ij}&\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&\<del class="diffchange diffchange-inline">lesseqgtr 0</del>,\ j\in\hat n\sm\J & \sum_{i=1}^m y_ia_{ij}&= 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&\<ins class="diffchange diffchange-inline">in\R</ins>,\ j\in\hat n\sm\J & \sum_{i=1}^m y_ia_{ij}&= c_j,\ j\in\hat n\sm\J\\</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>\end{align*}</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>\end{align*}</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>   </div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>   </div></td></tr>
</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'> </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'> </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'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>\[</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>\[</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="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'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>\]</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>\]</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>Soustava rovnic</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>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'> </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'> </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'> </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'> </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'> </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'> </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'> </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'> </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'> </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'> </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'> </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í  úloha:} && \text{Duální úloha:}&\\</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>\text{Primární  úloha:} && \text{Duální úloha:}&\\</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&=\sum_{j=1}^n <del class="diffchange diffchange-inline">x_jx_j </del>& \max w&=\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&=\sum_{j=1}^n <ins class="diffchange diffchange-inline">c_jx_j </ins>& \max w&=\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&\ge b_i,\ i\in\I\subset\hat m & y_i&\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&\ge b_i,\ i\in\I\subset\hat m & y_i&\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&= b_i,\ i\in\hat m\sm\I & y_i&\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&= b_i,\ i\in\hat m\sm\I & y_i&\lesseqgtr 0,\ i\in\hat m\sm\I\\</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>x_j&\ge 0,\ j\in\J\subset\hat n & \sum_{i=1}^m y_ia_{ij}&\le c_j,\ j\in\J\subset\hat n\\</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>x_j&\ge 0,\ j\in\J\subset\hat n & \sum_{i=1}^m y_ia_{ij}&\le c_j,\ j\in\J\subset\hat n\\</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>x_j&\lesseqgtr 0,\ j\in\hat n\sm\J & \sum_{i=1}^m y_ia_{ij}&= c_j,\ j\in\hat n\sm\J\\</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>x_j&\lesseqgtr 0,\ j\in\hat n\sm\J & \sum_{i=1}^m y_ia_{ij}&= 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:} && \text{Duální úloha:}&\\ \min z&=\sum_{j=1}^n x_jx_j & \max w&=\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:} && \text{Duální úloha:}&\\<br />
\min z&=\sum_{j=1}^n x_jx_j & \max w&=\sum_{i=1}^m y_ib_i\\<br />
\sum_{i=1}^n a_{ij}x_j&\ge b_i,\ i\in\I\subset\hat m & y_i&\ge 0,\ i\in\I\subset\hat m\\<br />
\sum_{i=1}^n a_{ij}x_j&= b_i,\ i\in\hat m\sm\I & y_i&\lesseqgtr 0,\ i\in\hat m\sm\I\\<br />
x_j&\ge 0,\ j\in\J\subset\hat n & \sum_{i=1}^m y_ia_{ij}&\le c_j,\ j\in\J\subset\hat n\\<br />
x_j&\lesseqgtr 0,\ j\in\hat n\sm\J & \sum_{i=1}^m y_ia_{ij}&= 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& =cx & \max w& =yb\\<br />
\A x& \ge b & y\A& \le c\\<br />
x& \ge 0 & y& \ge 0.<br />
\end{align*}<br />
<br />
Úloha v~{\bf kanonickém tvaru}: samé rovnice, nezápornost<br />
\begin{align*}<br />
\min z& =cx & \max w& =yb\\<br />
\A x& = b & y\A& \le c\\<br />
x& \ge 0 & y& \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&\ge b & \y\A\le c\\<br />
\x&\ge 0 & \y\ge 0<br />
\end{align*}<br />
vynásobením $\x$ zprava a $\y$ zleva dostaneme<br />
\begin{align*}<br />
\y\A\x&\ge\y b & \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&\ge 0 & x&\ge 0\\<br />
-y\A+tc&\ge 0 & y&\ge 0\\<br />
yb-cx&\ge 0 & t&\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>0$. Pak<br />
\begin{align*}<br />
\A x_0&\ge t_0 b & \implies && \A\frac{x_0}{t_0}&\ge b\\<br />
y_0\A&\le t_0 c & \implies && \frac{y_0}{t_0}\A&\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&\ge 0 & x_0&\ge 0\\<br />
y_0\A&\le 0 & y_0&\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&\ge y_0\A & \A\x&\ge b & \implies && 0&\ge y_0\A\x\ge y_0 b\\<br />
0&\le \A x_0 & \y\A&\le c & \implies && 0&\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>0$, tedy $y_0 b>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>c x_0$, tedy $c x_0<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 & 0 \\<br />
0 & 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>0&\implies \A_{i\bullet}\x=b_i & <br />
\y\A_{\bullet i}<c_i&\implies \x_i=0 \\<br />
\A_{i\bullet}\x>b_i&\implies\y_i=0 &<br />
\x_i>0&\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&>0\\<br />
c-\y\A+\x^T&>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<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>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>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}}>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}}}_{>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<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>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}<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&=b\\<br />
x&\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>0$ pro $i\in\hat k$, $\x_i=0$ pro $i>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&=b_{i_j},\ j\in\hat k\\<br />
x_j&=0,\ j>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>0$ pro $i\in\hat k$, $\x_i=0$ pro $i>k$.<br />
\[<br />
\left(<br />
\begin{array}{c|ccc}<br />
\\<br />
\text{regulární} & & 0\\<br />
\\<br />
\hline<br />
& 1 & \\<br />
0 & & \ddots \\<br />
& & & 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