simplexmódszer

A simplex módszer a lineáris programozási feladatok megoldására kifejlesztett, széles körben használt algoritmus. Egy olyan feladatot céloz meg, amelyben egy lineáris célfüggvényt maximalizálni vagy minimalizálni kell lineárisan összefüggő feltételek között. A megengedett megoldások halmaza egy konvex polytope, és a megoldási tér élén haladva a módszer a lehetséges optimumhoz visz bennünket. A simplex a szomszédos alapmegoldások (BFS) között mozog úgy, hogy az objektívérték javuljon vagy legalább ne romoljon.

A művelet során kiválasztunk egy belépő változót és egy távozó változót, majd pivotálással frissítjük az alapváltozók összetételét. Ezt a pivotálást addig ismételjük, amíg található olyan lépés, amely javítja a célfüggvényt, vagy amíg elő nem állnak a lehetséges stagnáló állapotok. A módszer több variánsa ismert: prím simplex, duális simplex és a revisált (revíziós) simplex. Degeneráció vagy ciklikus viselkedés esetén speciális szabályokat alkalmazhatnak, például Bland-féle sorrendet.

Történet: George Dantzig fejlesztette ki 1947-ben. A gyakorlati alkalmazásokban gyakran gyorsan talál megoldást, de elméleti szempontból előfordulhat, hogy a legrosszabb esetben exponenciális lépésszám szükséges. Alternatív megközelítések közé tartoznak a belső pontú módszerek, amelyek polinomiális időben futnak és nagyobb problémákra is alkalmazhatók. A simplex módszer így továbbra is alapvető eszköz marad, különösen kis- és közepes méretű problémákban, ahol a probléma geometriája kedvező.