primal simplex method

Angol

Főnév

primal simplex method (tsz. primal simplex methods)

(informatika) A Primal Szimplex módszer egy klasszikus, széles körben alkalmazott eljárás a lineáris programozási feladatok megoldására. A cél egy lineáris célfüggvény optimalizálása (maximalizálása vagy minimalizálása), lineáris egyenlőtlenségek (korlátok) mellett. A módszert George Dantzig fejlesztette ki az 1940-es évek végén, és azóta is az egyik legismertebb algoritmus az optimalizálás területén.

🔢 1. A lineáris programozás alapjai

Egy tipikus lineáris programozási probléma a következő formában adható meg:

Maximalizáljuk:

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

Korlátok:

Értelmezés sikertelen (formai hiba): {\displaystyle \begin{align*} a_{11}x_1 + a_{12}x_2 + \dots + a_{1n}x_n &\le b_1 \\ a_{21}x_1 + a_{22}x_2 + \dots + a_{2n}x_n &\le b_2 \\ \vdots \\ a_{m1}x_1 + a_{m2}x_2 + \dots + a_{mn}x_n &\le b_m \\ x_1, x_2, \dots, x_n &\ge 0 \end{align*} }

A cél: megtalálni azokat a változók értékeit, amelyek kielégítik a korlátokat, és maximalizálják a célfüggvényt.

🧮 2. A standard forma

A szimplex módszer működéséhez először standard formára kell hozni a feladatot:

Minden korlát egyenlőtlenségből egyenlőséget csinálunk szabad változók (s_i) bevezetésével:

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

A célfüggvényt szintén egyenletként kezeljük, a z változó bevezetésével.

🧭 3. A módszer lépései

1. Kezdő bázismegoldás kiválasztása

A bevezetett szabad változók (pl. ${\textstyle s_{1},s_{2},\dots }$ ) alkotják a kezdő bázist. Ezek értékei a ${\textstyle b_{i}}$ konstans tagok lesznek, míg a döntési változók (pl. ${\textstyle x_{1},x_{2},\dots }$ ) értéke kezdetben nulla.

2. Szimplex tábla felépítése

A teljes egyenletrendszert táblázatos formában rögzítjük. Ez az úgynevezett szimplex tábla, amely tartalmazza:

A bázisváltozók indexeit
A változók együtthatóit (bal oldal)
A jobb oldali konstansokat
Az alul található sor pedig a célfüggvény „csökkentett költségeit” mutatja.

3. Bázisfrissítés ciklusa (iteráció)

A következő iterációs lépések hajtódnak végre:

a) Belépő változó (pivot oszlop) kiválasztása

Olyan nem-bázis változót keresünk, amelynek a célfüggvény alatti együtthatója negatív. Ez azt jelenti, hogy ennek növelésével javítható a célérték (maximalizálásnál).

b) Kilépő változó (pivot sor) kiválasztása

Megnézzük, melyik sorban tudjuk a legjobban növelni az új változót anélkül, hogy a többi változó negatívvá válna:

Értelmezés sikertelen (ismeretlen „\middle” függvény): {\displaystyle \min_i \left\{ \frac{b_i}{a_{ij}} \;\middle|\; a_{ij} > 0 \right\} }

Ez a minimum hányados szabály.

c) Pivotálás

A kijelölt pivot elem köré Gauss-eliminációs lépéseket hajtunk végre:

A pivot sor normálása (pivot elem = 1)
A többi sor módosítása úgy, hogy a pivot oszlopban minden más elem 0 legyen

d) Ellenőrzés

Ha az összes nem-bázis változó alatt nem negatív érték szerepel a célfüggvény sorában, akkor elértük az optimumot.

📊 4. Geometriai értelmezés

A szimplex módszer a megoldási tartomány (amely egy konvex poliéder) csúcsai között lépeget úgy, hogy minden egyes lépésben javítja vagy nem rontja a célfüggvény értékét. Az algoritmus garantáltan eljut egy optimális csúcsponthoz, ha létezik megoldás.

⚠️ 5. Speciális esetek

Több optimális megoldás: ha több változó is nulla csökkentett költséggel rendelkezik
Nem korlátos megoldás: ha egy változót korlátlanul növelhetünk a célérték növelésével
Degeneráltság: ha egy bázismegoldásban több változó értéke is nulla – ez ciklusokhoz vezethet
Kétfázisú szimplex: ha nincs nyilvánvaló kezdő megoldás, segédváltozók segítségével építjük fel az induló bázist

🧠 6. Példa

Maximalizáljuk:

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

Feltételek:

Értelmezés sikertelen (formai hiba): {\displaystyle \begin{align*} 2x_1 + x_2 &\le 18 \\ 2x_1 + 3x_2 &\le 42 \\ 3x_1 + 1x_2 &\le 24 \\ x_1, x_2 &\ge 0 \end{align*} }

Átalakítás:

Bevezetjük a szabad változókat:

Értelmezés sikertelen (formai hiba): {\displaystyle \begin{align*} 2x_1 + x_2 + s_1 &= 18 \\ 2x_1 + 3x_2 + s_2 &= 42 \\ 3x_1 + x_2 + s_3 &= 24 \end{align*} }

A kezdő bázis: ${\textstyle s_{1},s_{2},s_{3}}$ , és ${\textstyle x_{1},x_{2}}$ nem bázis változók, értékük 0.

A szimplex tábla felépül, és az iteráció során belép egy változó a bázisba (pl. ${\textstyle x_{1}}$ ), egy másik kilép (pl. ${\textstyle s_{3}}$ ). A pivotálás után új táblát kapunk, és ez folytatódik mindaddig, amíg az alsó sorban nincs negatív érték.

🧾 7. Pseudokód

Cél: Maximalizálni z = cx
1. Hozd standard formára a problémát
2. Állítsd fel a kezdő szimplex táblát
3. Ismételd:
    a. Válaszd ki a legnegatívabb oszlopot (belépő változó)
    b. Számítsd ki a minimum hányadost (kilépő változó)
    c. Pivotálj (normalizálás és sorok kioltása)
    d. Ha nincs negatív elem az alsó sorban → kész, optimális megoldás

📌 8. Előnyök és hátrányok

Előnyök:

Hatékony a gyakorlatban
Könnyen implementálható
Egyszerű geometriai jelentés

Hátrányok:

Rossz esetben exponenciális futásidejű
Ciklikus viselkedés lehetséges (degeneráltság)

✅ Összegzés

A Primal Szimplex módszer egy robusztus, gyakran alkalmazott algoritmus lineáris programozási feladatok megoldására. Lépésről lépésre egy alap-megoldástól eljut az optimális megoldásig oly módon, hogy közben mindig csak egy változót módosít a bázisban. Fontos szerepet tölt be az operációkutatásban, gazdasági modellezésben és ipari alkalmazásokban.

További információk

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