Tartalomjegyzék:
Meghatározás - Mit jelent a simplex módszer?
A simplex módszer a matematikai optimalizálásban egy jól ismert algoritmus, amelyet a lineáris programozáshoz használnak. A Computing in Science & Engineering folyóirat szerint ezt a módszert a huszadik század során keletkező tíz legjobb algoritmus egyikének tekintik.
A simplex módszer szervezett stratégiát mutat be a megvalósítható régió csúcsainak értékelésére. Ez segít kitalálni a célfüggvény optimális értékét.
George Dantzig 1946-ban fejlesztette ki a simplex módszert.
A módszert simplex algoritmusnak is nevezik.
A Techopedia magyarázza a simplex módszert
A simplex módszert használják a problémák kiküszöbölésére a lineáris programozás során. Megvizsgálja a megvalósítható halmaz szomszédos csúcsait egymás után, hogy megbizonyosodjon arról, hogy minden új csúcsnál a célfüggvény növekszik vagy nem változik. Általában véve a simplex módszer rendkívül nagy teljesítményű, amely általában legfeljebb 2–3 m hosszú iterációt vesz igénybe (itt m jelöli az egyenlőségi korlátozások tartományát), és a várható polinomiális időben konvergál a véletlenszerű bemenet specifikus eloszlására.
A simplex módszer szisztematikus stratégiát alkalmaz a jelölt csúcsmegoldások generálására és tesztelésére egy lineáris programhoz. Minden iterációnál kiválasztja azt a változót, amely a legnagyobb módosítást képes elvégezni a minimális megoldás felé. Ez a változó ezután kicseréli annak egyik változóját, amely a legdrasztikusabban korlátozza azt, és ezáltal a simplex módszert a megoldáskészlet másik részére és a végső megoldás felé tolja át.
Ezenkívül a simplex módszer képes felmérni, hogy nem létezik-e megoldás. Megfigyelhető, hogy az algoritmus kapzsi, mivel minden iterációnál a legjobb megoldást választja, nincs szükség információra a korábbi vagy a jövőbeni iterációkból.
Időnként a simplex módszer által alkalmazott fő adatstruktúrát szótárnak nevezik. A szótárak tartalmazzák azokat a egyenleteket, amelyek megfelelően meg vannak hangolva a meglévő alaphoz. A szótárak segítségével intuitív megértést lehet adni arról, hogy miért jelenik meg minden változó az alapból.
