Szimplex algoritmus

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.

Menete

Gauss-eliminációval megpróbálja megoldani az $Ax=b$ rendszert. Ha nem sikerül, akkor talál egy y-t, hogy $yA=0$ és $yb\neq 0$. Ha $yb>0$, akkor y helyett -y-t veszi. Ezzel már be is bizonyította, hogy a primál feladat nem oldható meg.

Ha $Ax=b$ megoldható, akkor a Gauss-elimináció kiválaszt rangnyi független sort; a szimplex algoritmus ezután ezeket viszi tovább, a többivel nem foglalkozik. Kiválaszt A oszlopaiból egy B bázist, és Gauss-eliminációval megoldja a $Bx=b$ rendszert. Ezt nullákkal kiegészítve $Ax=b$ egy megoldását kapjuk. Ellenőrzi, hogy nincs-e x-nek negatív koordinátája.

Ha van x-nek negatív koordinátája, akkor a szimplex algoritmus kiválaszt egyet. Különféle szabályok léteznek erre a választásra. A Bland-szabály szerint a legkisebb indexűt veszi. Ezzel elkerülhető, hogy a szimplex algoritmus végtelen ciklusba kerüljön. A kiválasztott indexet jelölje i. Az algoritmus kiszámítja azt az y-t, ami B minden oszlopára merőleges, kivéve az i-edikre: ya_i = 1. Ekkor yb < 0. Ha még ya_i > 0, akkor y duál bázismegoldás, és az algoritmus véget ér.

Ha nem így van, akkor a szimplex algoritmus választ egy olyan indexet, ahol ya_i < 0. Itt is érdemes a Bland-szabály alapján a legkisebb ilyen indexet választani. Most B-ben kicseréli a_i-t a_j-re. Ezután az így kapott bázissal folytatja a próbálkozást.

Példa

A szimplex algoritmussal eldönthető, hogy a b pont benne van-e a sík p₁, …, p_n pontjainak konvex burkában. Az A mátrix a pontok koordinátáit, mint oszlopokat tartalmazza, kiegészítve egy csupa egyesekből álló sorral. Hasonlóan, a b a b pont koordinátáit tartalmazza, egy utolsó egyessel kiegészítve. A primál bázismegoldás egy háromszöget ad, amiben benne van a b pont; a duál megoldás egy egyenessel választja el a b pontot a p₁, …, p_n pontoktól.

Bland-szabály

A Bland-szabály szerint mindig a legkisebb i és j indexet kell választani. Ha véletlenszerűen választ, akkor többször is ugyanazokat a csúcsokat látogatja meg, és makacsul nem találja meg az egyértelmű optimumot.

Például, ha van egy p₁, p₃, p₅ szabályos háromszög, és benne ennek kicsinyített és elforgatott p₂, p₄, p₆ mása. Véletlenszerű választás esetén a szimplex módszer rendre a p_i, p_i+1, p_i+2 pontokat választhatja.

Források

• Frank András: Operációkutatás