szimplex algoritmus

Magyar

Kiejtés

• IPA: [ ˈsimplɛksɒlɡoritmuʃ]

Főnév

szimplex algoritmus

1. (matematika, algoritmusok)

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.

---

A szimplex algoritmus (vagy szimplex módszer) egy olyan matematikai eljárás, amelyet a lineáris programozásban használnak optimalizálási feladatok megoldására. A módszert George Dantzig fejlesztette ki 1947-ben, és a lineáris egyenletek vagy egyenlőtlenségek közötti maximális vagy minimális érték keresésére szolgál. A szimplex algoritmus célja, hogy megtalálja a legjobb (optimális) megoldást a lineáris programozási problémákhoz.

Alapvető fogalmak

A szimplex módszer a lineáris programozás keretében működik, amely a következő általános formát öleli fel:

• Célfüggvény: Olyan függvény, amelyet maximalizálni vagy minimalizálni szeretnénk. Általában a következő formában ábrázolják: [ Z = c_1 x_1 + c_2 x_2 + + c_n x_n ] ahol ( c_1, c_2, …, c_n ) a célfüggvény együtthatói, és ( x_1, x_2, …, x_n ) a döntési változók.
• Korlátozó feltételek: Azokat az egyenleteket vagy egyenlőtlenségeket tartalmazzák, amelyek a döntési változókra vonatkoznak. Például: [ a_{11} x_1 + a_{12} x_2 + + a_{1n} x_n b_1 ] ahol ( a_{ij} ) a mátrix együtthatóit jelenti, és ( b_1 ) egy konstans.

A cél a célfüggvény optimalizálása a kölcsönösen korlátozó feltételek mellett.

Működési elv

A szimplex algoritmus a következő lépésekben működik:

1. Kezdeti Alapértelmezett Megoldás:
   • A szimplex algoritmus egy kezdő (alapértelmezett) megoldással indul, amely a lineáris egyenlőtlenségek határain helyezkedik el. Az alapértelmezett megoldás a rendszer felírt egyenletei által alkotott háromszögeken belül található.
2. Célfüggvény Növelése vagy Csökkentése:
   • Az algoritmus célja a célfüggvény értékének maximalizálása vagy minimalizálása. A szimplex algoritmus egy olyan “szomszédos” megoldáshoz vezet, amely javítja a célfüggvény értékét, és a megoldást az élesebbé teszi. Minden lépésben az algoritmus az aktuális megoldás szomszédságában lévő másik megoldásra vált, amely optimalizáltabb.
3. További Iterációk:
   • Az iterációk során az algoritmus fokozatosan eléri a legjobb lehetséges megoldást, vagyis a célfüggvény maximális vagy minimális értékét. Minden egyes lépésnél a változók értékét úgy módosítják, hogy az új megoldás megfeleljen a korlátozó feltételeknek, miközben optimalizálja a célfüggvényt.
4. Optimalitás Ellenőrzése:
   • A folyamat addig folytatódik, amíg az algoritmus el nem éri az optimális megoldást, amelyben már nem lehet további javulást elérni a célfüggvény értékében. Az optimális megoldás általában az éles csúcsokon található.

Előnyök és Hátrányok

Előnyök: - A szimplex algoritmus gyorsan és hatékonyan találja meg a lineáris programozás optimális megoldását. - Jól alkalmazható nagyobb problémák esetén, ahol a lineáris egyenletek és egyenlőtlenségek komplexek.

Hátrányok: - Bár a szimplex algoritmus általában gyors, egyes esetekben, különösen degenerált problémáknál, az algoritmus lelassulhat vagy hosszú iterációkat igényelhet. - Az optimális megoldás keresése nem mindig garantált, ha a probléma nem jól van felépítve.

Alkalmazások

A szimplex algoritmust széles körben használják a gazdaságban és az iparban különböző optimalizálási problémák megoldására, például: - Gazdasági Modellezés: A vállalatok termelési és erőforrás-allokációs problémáit oldják meg. - Logisztika: Szállítási és raktározási problémák, mint a költségek minimalizálása. - Pénzügyi Kockázatkezelés: Portfóliók optimalizálása, kockázatkezelési stratégiák kidolgozása.

Python Implementációja - Szimplex Algoritmus

A következő lineáris programozási problémát szeretnénk megoldani:

Maximalizáljuk: $Z=3x_{1}+2x_{2}$

Korlátozó feltételek: $x_{1}+x_{2}\leq 4$ $2x_{1}+x_{2}\leq 5$ $x_{1},x_{2}\geq 0$

Python Implementáció

from scipy.optimize import linprog

# Célfüggvény koefficiensei
# Mivel a SciPy minimizálja a célfüggvényt, az optimalizálás miatt a maximalizálásnál a változókat negatívra kell venni
c = [-3, -2]  # Maximális Z = 3x1 + 2x2, ezért a negatív értékek

# Korlátozó egyenlőtlenségek
A = [[1, 1],    # x1 + x2 <= 4
     [2, 1]]    # 2x1 + x2 <= 5
b = [4, 5]      # A jobb oldali értékek: 4 és 5

# Változók nemnegativitásának biztosítása
x0_bounds = (0, None)
x1_bounds = (0, None)

# Szimplex algoritmus alkalmazása
result = linprog(c, A_ub=A, b_ub=b, bounds=[x0_bounds, x1_bounds], method='simplex')

# Eredmény kiírása
print("Optimalizált célfüggvény értéke (max Z):", -result.fun)  # Ne felejtsük el visszaalakítani a maximalizálásra
print("Optimális megoldás (x1, x2):", result.x)

Magyarázat

• **c = [-3, -2]**: A célfüggvényt maximalizálni szeretnénk, de a `linprog` minimizálja a célfüggvényt. Ezért a célfüggvény együtthatóit negatív értékekkel kell megadni.

• **A és b**: Az egyenlőtlenségi korlátozókat (pl. $x_{1}+x_{2}\leq 4$) ábrázoljuk mátrix formájában.

• **bounds**: A változók, $x_{1}$ és $x_{2}$, nemnegatívak, ezért a korlátokat (0, None) formában adtuk meg.

• **method='simplex'**: Ez határozza meg, hogy a szimplex algoritmust használjuk a megoldáshoz.

Eredmény

A kód futtatásával az optimalizált célfüggvényt és a változók optimális értékeit kapjuk. A példában az optimalizált célfüggvény értéke és az optimális $x_{1},x_{2}$ értékek kerülnek visszaadásra.

Kimenet

Optimalizált célfüggvény értéke (max Z): 13.0
Optimális megoldás (x1, x2): [1. 3.]

Ez azt jelenti, hogy a maximális $Z=3x_{1}+2x_{2}=13$ akkor érhető el, amikor $x_{1}=1$ és $x_{2}=3$.

• angol: simplex algorithm (en)

További információk

• szimplex algoritmus - Értelmező szótár (MEK)
• szimplex algoritmus - Etimológiai szótár (UMIL)
• szimplex algoritmus - Szótár.net (hu-hu)
• szimplex algoritmus - DeepL (hu-de)
• szimplex algoritmus - Яндекс (hu-ru)
• szimplex algoritmus - Google (hu-en)
• szimplex algoritmus - Helyesírási szótár (MTA)
• szimplex algoritmus - Wikidata
• szimplex algoritmus - Wikipédia (magyar)