Obsah:
Definícia - Čo znamená simplexná metóda?
Simplexná metóda v matematickej optimalizácii je známy algoritmus používaný na lineárne programovanie. Podľa časopisu Computing in Science & Engineering je táto metóda považovaná za jeden z 10 najlepších algoritmov, ktoré vznikli v priebehu dvadsiateho storočia.
Simplexná metóda predstavuje organizovanú stratégiu hodnotenia vrcholov realizovateľného regiónu. To pomáha zistiť optimálnu hodnotu objektívnej funkcie.
George Dantzig vyvinul simplexnú metódu v roku 1946.
Táto metóda je známa aj ako simplexný algoritmus.
Techopedia vysvetľuje simplexnú metódu
Simplexná metóda sa používa na odstránenie problémov v lineárnom programovaní. Postupne skúma susedné vrcholy uskutočniteľného súboru, aby sa zabezpečilo, že v každom novom vrchole sa funkcia objektívu zvýši alebo nebude ovplyvnená. Všeobecne je simplexná metóda extrémne výkonná, ktorá zvyčajne trvá najviac 2 až 3 m iterácie (tu m označuje rozsah obmedzení rovnosti) a konverguje v očakávanom polynomickom čase pre špecifické rozdelenie náhodného vstupu.
Simplexná metóda používa systematickú stratégiu na generovanie a testovanie riešení vertexu kandidátov na lineárny program. Pri každej iterácii vyberie premennú, ktorá môže urobiť najväčšiu zmenu smerom k minimálnemu riešeniu. Táto premenná potom nahradí jednu zo svojich kovariantov, ktorá ju najviac obmedzuje, čím posunie simplexnú metódu do inej časti sady riešení a smerom ku konečnému riešeniu.
Simplexná metóda je navyše schopná vyhodnotiť, či v skutočnosti neexistuje žiadne riešenie. Možno pozorovať, že algoritmus je chamtivý, pretože sa pri každej iterácii rozhodne pre najlepšiu voľbu bez potreby informácií z predchádzajúcich alebo budúcich iterácií.
Niekedy sa hlavná dátová štruktúra použitá simplexovou metódou nazýva slovník. Slovníky obsahujú ilustráciu množín rovníc, ktoré sú správne vyladené podľa existujúceho základu. Slovníky sa dajú použiť na intuitívne pochopenie toho, prečo všetky premenné vstupujú a opúšťajú základ.
