Kazalo:
Opredelitev - Kaj pomeni Simplex metoda?
Simplex metoda pri matematični optimizaciji je dobro znan algoritem, ki se uporablja za linearno programiranje. Kot piše v reviji Computing in Science & Engineering, ta metoda velja za enega izmed prvih 10 algoritmov, ki so nastali v dvajsetem stoletju.
Simplex metoda predstavlja organizirano strategijo za ocenjevanje vertikalnih regij, ki so izvedljiva. To pomaga ugotoviti optimalno vrednost ciljne funkcije.
George Dantzig je leta 1946 razvil simplex metodo.
Metoda je znana tudi kot algoritem simpleksa.
Tehopedia razlaga Simplex metodo
Za odpravo težav v linearnem programiranju se uporablja simpleks metoda. Preiskuje sosednja vertika izvedljivega niza, da se zagotovi, da se pri vsaki novi točki ciljna funkcija poveča ali ne vpliva nanjo. Na splošno je metoda simpleksa izredno močna, ki ponavadi traja največ 2 m do 3 m iteracij (tukaj m označuje območje omejitev enakosti) in se konvergira v predvidenem polinomskem času za posebne porazdelitve naključnega vnosa.
Simplex metoda uporablja sistematično strategijo za ustvarjanje in testiranje kandidatnih rešitev na linearnem programu. Pri vsaki ponovitvi izbere spremenljivko, ki lahko spremeni največjo možno rešitev. Ta spremenljivka nato nadomesti enega od svojih spremenljivk, ki ga najbolj drastično omeji in s tem preusmeri simpleksno metodo na drug del rešitve in proti končni rešitvi.
S pomočjo simpleks metode lahko ocenimo, ali rešitve resnično ne obstaja. Opazimo lahko, da je algoritem pohleven, saj se pri vsaki iteraciji odloči za najboljšo možnost, brez povpraševanja po informacijah iz prejšnjih ali prihodnjih iteracij.
Včasih se glavna podatkovna struktura, ki jo uporablja metoda simplex, imenuje slovar. Slovarji vključujejo prikaz enačb, ki so pravilno nastavljene na obstoječo osnovo. Slovarje je mogoče uporabiti za intuitivno razumevanje, zakaj vse spremenljivke vstopijo in zapustijo osnovo.
