simplex algorithm

simplex algorithm (tsz. simplex algorithms)

1. (informatika) szimplex algoritmus

A Simplex algoritmus egy klasszikus iteratív módszer, amit lineáris programozási feladatok (LP feladatok) megoldására használnak. A lineáris programozás célja egy lineáris célfüggvény optimalizálása (maximalizálása vagy minimalizálása), lineáris egyenlőtlenségekkel korlátozott feltételek mellett.

A Simplex algoritmust George Dantzig fejlesztette ki 1947-ben, és azóta is a legszélesebb körben használt módszer a gyakorlatban LP-problémák megoldására.

Maximalizálni:

$${\displaystyle z=c_{1}x_{1}+c_{2}x_{2}+\dots +c_{n}x_{n}}$$

$${\displaystyle {\begin{aligned}a_{11}x_{1}+a_{12}x_{2}+\dots +a_{1n}x_{n}&\leq b_{1}\\a_{21}x_{1}+a_{22}x_{2}+\dots +a_{2n}x_{n}&\leq b_{2}\\\vdots \\a_{m1}x_{1}+a_{m2}x_{2}+\dots +a_{mn}x_{n}&\leq b_{m}\\x_{1},x_{2},\dots ,x_{n}&\geq 0\end{aligned}}}$$

Ez geometriailag egy konvex sokszög (polytop), aminek csúcspontjai lehetnek az optimális megoldások.

A Simplex nem próbál végig minden pontot, hanem a megengedett tartomány (megoldástér) szélein „sétál végig” egy adott irányban. A megoldás mindig egy sarkalatos ponton (vertex) van, ezért csak ezek vizsgálata szükséges.

1. Kezdj egy bázismegoldással (pl. ahol a legtöbb változó nulla)
2. Válassz egy javító irányt, amely növeli a célfüggvény értékét
3. Haladj ebben az irányban a legközelebbi sarkpontig
4. Ismételd, amíg nem lehet tovább javítani

Az egyenlőtlenségeket egyenlőséggé alakítjuk szabad (slack) változók hozzáadásával:

$${\displaystyle a_{11}x_{1}+\dots +a_{1n}x_{n}+s_{1}=b_{1}}$$

Így kapunk egy egyenletrendszert, amit mátrix alakban írhatunk fel.

Ez egy táblázat, amely tartalmazza:

• a változók együtthatóit,
• a célfüggvény együtthatóit,
• a megoldás aktuális értékeit.

1. Válaszd ki a belépő változót: az a nem-alapváltozó, amelynek legnagyobb negatív együtthatója van a célfüggvény sorában.
2. Válaszd ki a kilépő változót: ez az a sor, amelyre a RHS / belépő oszlop érték a legkisebb pozitív → pivot sor.
3. Pivot művelet: alakítsd át a táblát úgy, hogy a belépő változó együtthatója 1 legyen, és a többieké 0.
4. Ismételd, amíg nincs negatív együttható a célfüggvény sorában → elértük az optimumot.

Maximalizáld:

$${\displaystyle z=3x_{1}+2x_{2}}$$

Feltételek:

$${\displaystyle {\begin{aligned}2x_{1}+x_{2}&\leq 14\\4x_{1}+3x_{2}&\leq 28\\x_{1},x_{2}&\geq 0\end{aligned}}}$$

Átalakítva slack változókkal:

$${\displaystyle {\begin{aligned}2x_{1}+x_{2}+s_{1}&=14\\4x_{1}+3x_{2}+s_{2}&=28\\\end{aligned}}}$$

Simplex táblázattal iterálva eljuthatunk a megoldáshoz: ${\textstyle x_{1}=4,x_{2}=6,z=3\times 4+2\times 6=12+12=24}$

• Gyártástervezés (termelési egységek optimalizálása)
• Szállítási problémák (mint a szállítási feladat)
• Költségminimalizálás
• Erőforrás-elosztás

• Degeneráció: ha egy alapszinten több változó is nulla, az algoritmus “beragadhat”.
• Ciklus: elméletileg előfordulhat, de ritka.
• Több optimális megoldás: ha több alapszint adja ugyanazt az optimális értéket.
• Nincs megoldás: ha az LP modell nem korlátos vagy ellentmondásos.

• Determinista és pontos
• Átlátható és jól követhető lépésről lépésre
• Gyakorlati LP problémákban nagyon hatékony

• Elméletben exponenciális idő, de gyakorlatban gyors
• Nagyméretű problémák esetén jobb a belső-pontos (interior point) módszer

• Revised Simplex: memóriában hatékonyabb változat
• Dual Simplex: ha a kezdeti megoldás nem megengedett
• Interior Point: más módszer LP-re, különösen nagy problémák esetén

A Simplex algoritmus egy megbízható, matematikailag elegáns eszköz, amely:

• LP problémákra optimális megoldást keres,
• Geometriailag a csúcspontok mentén lépked,
• Iteratív táblázatkezeléssel működik,
• Nagyon széles körben használják gazdaságban, iparban és kutatásban.

• simplex algorithm - Szótár.net (en-hu)
• simplex algorithm - Sztaki (en-hu)
• simplex algorithm - Merriam–Webster
• simplex algorithm - Cambridge
• simplex algorithm - WordNet
• simplex algorithm - Яндекс (en-ru)
• simplex algorithm - Google (en-hu)
• simplex algorithm - Wikidata
• simplex algorithm - Wikipédia (angol)