OPTPV_20141104 03

Zhrnutie prednášky

Prednáška sa venuje simplexovej metóde na riešenie úloh lineárneho programovania, jej algoritmu a implementácii v softvéri. Vysvetľuje sa exponenciálna zložitosť metódy v najhoršom prípade a možnosť cyklovania, ktoré nezaručuje konvergenciu. Podrobne sa opisuje postup zostavenia simplexovej tabuľky, výber otočnej premennej (stĺpca a riadku) a vykonávanie elementárnych riadkových operácií. Následne sa preberá praktické riešenie úloh lineárneho programovania v prostredí Matlab pomocou funkcie linprog, vrátane požadovaného štandardného tvaru vstupných údajov a výstupných argumentov (optimálne riešenie, hodnota účelovej funkcie, stav riešenia).

• - Simplexová metóda má v najhoršom prípade exponenciálnu zložitosť
• - Bez opatrení metóda môže cyklovať a nezaručuje konvergenciu
• - Algoritmus: prevod úlohy do štandardného tvaru, vytvorenie simplexovej tabuľky, kontrola optimálnosti
• - Výber pivotného stĺpca podľa najmenšieho záporného koeficientu v poslednom riadku
• - Výber pivotného riadku podľa najmenšieho kladného pomeru pravej strany a pivotného koeficientu
• - V Matlabe rieši úlohy lineárneho programovania funkcia linprog, ktorá implementuje simplexovú aj iné metódy
• - Vstup do linprog vyžaduje minimalizačný tvar úlohy s definovanými obmedzeniami rovnosti, nerovnosti a hranicami premenných

Zhrnutie pripravené s pomocou AI z prepisu videa.