Simplexmenetelmän

Simplexmenetelmä on tehokas algoritmi lineaaristen optimointiongelmien ratkaisemiseksi. Lineaarinen optimointi tarkoittaa optimiarvon löytämistä lineaariselle kohdefunktiolle, kun rajoitukset ovat myös lineaarisia epäyhtälöitä tai yhtälöitä. Simplexmenetelmän kehitti George Dantzig vuonna 1947.

Menetelmä toimii tutkimalla lineaarisen optimointiongelman sallitun ratkaisualueen kärkipisteitä. Sallittu ratkaisualue on monikulmio tai polytooppi, joka muodostuu rajoitusehtojen leikkauksista. Simplexmenetelmä aloittaa jostakin sallitusta kärkipisteestä ja siirtyy sitten iteratiivisesti naapurikärkipisteeseen, joka parantaa kohdefunktion arvoa. Tätä prosessia jatketaan, kunnes optimaalinen ratkaisu on löydetty, jolloin mikään naapurikärkipiste ei enää paranna arvoa.

Algoritmi käsitellään tyypillisesti taulukkomuodossa, jota kutsutaan simplex-taulukoksi. Taulukkoon sisällytetään kohdefunktio ja rajoitusehdot muokattuina yhtälöiksi. Simplex-taulukon avulla voidaan systemaattisesti määrittää, mikä muuttuja tulee sisään ratkaisuun ja mikä poistuu, sekä laskea uudet arvot taulukkoon.

Simplexmenetelmä on yleisesti käytetty optimointitekniikka, jolla on sovelluksia monilla aloilla, kuten tuotannonsuunnittelussa, logistiikassa ja taloustieteessä. Vaikka se on tehokas monissa tapauksissa, sen teoreettinen pahimman tapauksen aikavaativuus voi olla eksponentiaalinen. Käytännössä se kuitenkin toimii yleensä erittäin nopeasti.