szimplex algoritmus

Magyar

Kiejtés

• IPA: [ ˈsimplɛksɒlɡoritmuʃ]

Főnév

szimplex algoritmus

1. (matematika, algoritmusok)

A szimplex algoritmus, más néven szimplex módszer a lineáris programok optimumának megtalálására szolgáló, egyben annak létezését is vizsgáló módszer. Használják linearizált nemlineáris programok megoldására is. Műveletideje akár exponenciális is lehet, mivel csúcsról csúcsra jár, és egy konvex poliédernek exponenciálisan sok csúcsa lehet. Erre példa a kocka.

Bizonyítható vele az az állítás is, hogy ha az $Ax=b$, $x_{i}\geq 0$ rendszernek akkor és csak akkor van olyan megoldása, amelyben A x pozitív változóinak megfelelő oszlopai lineárisan függetlenek, ha nincs olyan y, hogy $yA\geq 0$, $yb<0$, és A-nak van rang(A,b)-1 független oszlopa, amire y merőleges. Röviden, vagy a primál, vagy a duál feladatnak van bázismegoldása. Általánosabb alakra is kiterjeszthető; ha például vannak egyenlőségek is, akkor az egyenlőségeket leíró P mátrixból annyi oszlopot teszünk a bázisba, amennyit csak lehet. A továbbiakban ezek az oszlopok nem mozognak.

• angol: simplex algorithm (en)