dual simplex method

Angol

Főnév

dual simplex method (tsz. dual simplex methods)

(informatika) A duális szimplex módszer egy alternatív eljárás a lineáris programozási feladatok megoldására, amelyet akkor használunk, ha van egy duálisan megvalósítható, de prímálisan nem megvalósítható kezdő megoldásunk. Ez az eljárás akkor különösen hasznos, ha például egy korábbi megoldást egy új feltétel miatt módosítani kell, és nem akarjuk újraindítani az egész primal szimplex folyamatot.

🧭 Mi a különbség a Primal és a Duális Szimplex között?

	Primal Szimplex	Duális Szimplex
Kezdő állapot	Prímálisan megvalósítható, de nem optimális	Duálisan megvalósítható, de nem prímálisan az
Mit javít?	Duális megvalósíthatóságot	Prímális megvalósíthatóságot
Célfüggvény	Egyre jobb célérték felé lép	Célérték is javulhat, de elsődlegesen a megvalósíthatóságon dolgozik
Pivotálás	Belépő változó: legnegatívabb csökkentett költség	Kilépő változó: negatív jobb oldali elem

📘 Alapötlet

A duális szimplex módszer úgy működik, hogy mindig duálisan megvalósítható marad (azaz az alsó sorban nincsen negatív csökkentett költség), de ha a jobb oldali tag negatív, akkor prímálisan nem megvalósítható az aktuális bázismegoldás. Az algoritmus iterál, és a pivotálás során javítja a megvalósíthatóságot.

🧮 Lépések részletesen

1. Kezdeti szimplex tábla

Tételezzük fel, hogy a tábla duálisan megvalósítható, azaz minden célfüggvény alatti érték (csökkentett költség) nem negatív. Azonban az egyik vagy több jobb oldali érték negatív: ez a kiindulási helyzet a duális szimplexhez.

2. Iterációs lépések

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

Megkeressük azt a sort, ahol a jobb oldali érték a legnegatívabb. Ez lesz a kilépő sor. Jelölje ez a sor az i-edik sort.

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

Megnézzük az i-edik sorban az összes negatív együtthatót, és ezek közül kiválasztjuk azt a változót (oszlopot), amelyiknél a hányados:

${\frac {c_{j}}{a_{ij}}}\quad {\text{(csak ahol }}a_{ij}<0)$

a legkisebb.

Ez garantálja, hogy a célfüggvény nem rontódik és a duális megvalósíthatóság megmarad.

c) Pivotálás

Pivot elem = ${\textstyle a_{ij}}$
Az i-edik sort osztjuk a pivot elemmel
A többi sort módosítjuk, hogy a pivot oszlopban 0 legyen
A jobb oldali értékek is frissülnek

d) Megállási feltétel

Ha minden jobb oldali érték nem negatív, akkor a prímális megvalósíthatóság is teljesül, és mivel a célfüggvény csökkentett költségei már nem negatívak voltak, elértük az optimális megoldást.

🔁 Pseudokód

1. Állítsuk be a duálisan megvalósítható, de prímálisan nem megvalósítható kezdő táblát
2. Amíg van negatív jobb oldali érték:
    a. Válaszd ki a legnegatívabb b_i-t → kilépő sor
    b. A kilépő sorban nézd meg azokat az a_ij elemeket, ahol a_ij < 0
    c. Számítsd: min(c_j / a_ij) ezekre → ez lesz a belépő oszlop
    d. Pivotálj
3. Ha minden jobb oldali tag ≥ 0 → optimális megoldás

🧠 Példafeladat

Legyen:

Maximalizálandó:

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

Feltételek:

Értelmezés sikertelen (formai hiba): {\displaystyle \begin{align*} -x_1 + 2x_2 &\le 4 \\ 2x_1 + x_2 &\le 6 \\ x_1, x_2 &\ge 0 \end{align*} }

Ha valamilyen módosítás miatt az egyik jobb oldali érték negatívvá válik (pl. egy új feltétel hozzáadása), akkor a primal szimplex nem indulhat el. Viszont a duális szimplex módszer ezt a helyzetet kezeli, és iterálva újra megtalálja az optimális bázist, miközben javítja a megvalósíthatóságot.

⚙️ Alkalmazási területek

Modifikált LP problémák új korlátokkal
Branch-and-Bound módszerekben (pl. integer programming)
Post-optimalizáció: kis változások gyors újraszámolása

✅ Előnyök és hátrányok

Előnyök:

Hatékony, ha a kezdő bázis nem prímálisan megvalósítható
Post-optimalizálásra nagyon gyors
Egyes esetekben kevesebb iteráció, mint a primal szimplexnél

Hátrányok:

Bonyolultabb a pivotválasztás logikája
Nehéz jó kezdőmegoldást találni, ha az nincs megadva

🧾 Összegzés

A duális szimplex módszer egy erőteljes technika, amely a lineáris programozásban akkor hasznos, ha a megoldás duálisan kielégítő, de nem prímálisan. Ahelyett, hogy megjavítaná a célfüggvényt (mint a primal), megpróbálja helyreállítani a megvalósíthatóságot, miközben a célérték nem romlik. Ez különösen hatékony, ha egy már kiszámolt LP modellt kisebb módosítás után kell újraoptimalizálni.

További információk

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