OPTPV_20141104 02

Zhrnutie prednášky

Prednáška sa venuje geometrickej interpretácii úloh lineárneho programovania a základom simplexovej metódy. Na jednoduchom príklade s dvoma optimalizačnými premennými je ukázané, že prípustná množina tvorí konvexný útvar a optimálne riešenie sa vždy nachádza v jednom z jeho vrcholov, pričom zmena účelovej funkcie môže zmeniť polohu optima. Keďže počet vrcholov rastie exponenciálne s počtom premenných (2^n), naivné prehľadanie všetkých vrcholov je v praxi nepoužiteľné pre úlohy so stovkami až tisíckami premenných. Preto sa predstavuje simplexová metóda, ktorú vyvinul George Dantzig počas druhej svetovej vojny pre potreby armádnej logistiky a ktorá inteligentne prechádza len časťou vrcholov smerom k optimu. Nasleduje postup prevodu ľubovoľnej úlohy lineárneho programovania na Dantzigovu štandardnú formu pomocou slackových premenných (odstránenie nerovností) a rozkladu premenných na kladnú a zápornú časť (odstránenie obmedzenia nezápornosti), vrátane konkrétneho číselného príkladu.

• - Optimálne riešenie lineárneho programu leží vždy v jednom z vrcholov prípustnej množiny (konvexného útvaru definovaného obmedzeniami).
• - Zmena účelovej funkcie môže zmeniť polohu optimálneho vrcholu, prípadne spôsobiť, že optimum leží na celej hrane.
• - Naivné preskúmanie všetkých vrcholov je nepoužiteľné, keďže ich počet rastie ako 2 na počet premenných.
• - Simplexovú metódu vyvinul George Dantzig počas 2. svetovej vojny pre optimalizáciu vojenskej logistiky armády USA.
• - Simplex efektívne prechádza len vybranými vrcholmi smerom k optimálnemu riešeniu bez prehľadania celého priestoru.
• - Prevod úlohy do Dantzigovej štandardnej formy vyžaduje zavedenie nezáporných slackových premenných na prevod nerovností na rovnosti.
• - Premenné bez obmedzenia znamienka sa nahrádzajú rozdielom dvoch nových nezáporných premenných (x = x+ − x−).

Zhrnutie pripravené s pomocou AI z prepisu videa.