szimplexmódszer

A szimplexmódszer egy iteratív algoritmus a lineáris programozási feladatok megoldására. Elsőként George Dantzig publikálta 1947-ben. Lényege, hogy a feladat megengedett tartományának (mely egy konvex poliéder) csúcsain lépkedve keresi a optimális megoldást. A módszer kiindul egy megengedett alapsokartból (egy csúcsból), és a célfüggvény értékét javítva halad egyik csúcsból a másikba, amíg egy optimális megoldáshoz nem ér. A lépések során a be- és kivezető változók meghatározása és a táblázat átalakítása kulcsfontosságú. A szimplexmódszer garantáltan megtalálja az optimális megoldást, ha létezik, véges sok lépésben. Azonban bizonyos esetekben, például degenerált feladatoknál, a módszer ciklikusságba eshet, bár erre speciális technikák léteznek. A módszer széles körben alkalmazható gazdasági és mérnöki problémák optimalizálásában, erőforrásallokációban és menetrendkészítésben.