OPTPV_20141118 03

Zhrnutie prednášky

Prednáška sa zaoberá javom degenerácie a cyklenia pri simplexovej metóde na konkrétnom príklade úlohy s tromi nerovnostnými obmedzeniami prevedenými na rovnosti. Ukazuje sa, ako počas iterácií môže niektorá bazická premenná nadobudnúť nulovú hodnotu, čo je definícia degenerovaného riešenia. Na príklade sa demonštruje, že jedna pivotovacia operácia môže viesť k rovnakému riešeniu ako predtým, pričom sa iba zamenia voľné a bazické premenné bez zlepšenia účelovej funkcie. Vysvetľuje sa, že degenerácia je v lineárnom programovaní častá a spomaľuje algoritmus, zatiaľ čo skutočné nekonečné cyklenie je extrémne zriedkavé, najmä vďaka zaokrúhľovacím chybám pri numerickom výpočte s desatinnými číslami namiesto presných zlomkov.

• - Degenerácia nastáva, keď niektorá bazická premenná v simplexovej iterácii nadobudne hodnotu nula
• - Pri zhodných pomeroch v ratio teste musí solver voliť pivot heuristicky/náhodne
• - Degenerované riešenie môže viesť k tomu, že ďalšia iterácia neprinesie zlepšenie účelovej funkcie
• - Opakované vracanie sa k rovnakému riešeniu cez viacero iterácií sa nazýva cyklenie
• - V teórii môže simplexová metóda pri degenerácii skončiť v nekonečnej slučke
• - V praxi je cyklenie extrémne zriedkavé, hoci degenerácia je bežná a len spomaľuje výpočet
• - Numerické zaokrúhľovanie pri reprezentácii čísel s pohyblivou desatinnou čiarkou často prakticky eliminuje riziko cyklenia

Zhrnutie pripravené s pomocou AI z prepisu videa.