Szimplex algoritmus

A Wikipédiából, a szabad enciklopédiából

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[szerkesztés | forrásszöveg szerkesztése]

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: yai = 1. Ekkor yb < 0. Ha még yai > 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 yai < 0. Itt is érdemes a Bland-szabály alapján a legkisebb ilyen indexet választani. Most B-ben kicseréli ai-t aj-re. Ezután az így kapott bázissal folytatja a próbálkozást.

Példa[szerkesztés | forrásszöveg szerkesztése]

A szimplex algoritmussal eldönthető, hogy a b pont benne van-e a sík p1, …, pn 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 p1, …, pn pontoktól.

Bland-szabály[szerkesztés | forrásszöveg szerkesztése]

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 p1, p3, p5 szabályos háromszög, és benne ennek kicsinyített és elforgatott p2, p4, p6 mása. Véletlenszerű választás esetén a szimplex módszer rendre a pi, pi+1, pi+2 pontokat választhatja.

Forrás[szerkesztés | forrásszöveg szerkesztése]

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