Optimális megoldás (optimalizálás)

Optimális megoldás — az operációkutatásban, az optimalizálásban és a döntéselméletben olyan megengedett megoldás (azaz amely kielégíti a feladat összes feltételét), amely a célfüggvény extrém (maximális vagy minimális, a feladat megfogalmazásától függően) értékét biztosítja.

Az optimális megoldás megkeresése a legtöbb optimalizálási feladat megoldásának elsődleges célja.

Lényege és jellemzői

Az optimális megoldás két kulcstulajdonsággal rendelkezik:

1. Megengedettség: Ki kell elégítenie a modell változóira vonatkozó összes feltételt. Más szóval, az optimális megoldás mindig a megengedett megoldások tartományába (MMT) tartozik. 2. Extrémitás a célfüggvény szerint: Az összes megengedett megoldás közül a legjobb (maximális vagy minimális) értékét biztosítja a célfüggvénynek, amely az optimalitás kritériumát formalizálja.

Nem minden megengedett megoldás optimális, de minden optimális megoldásnak feltétlenül megengedettnek kell lennie.

Kapcsolat a megengedett megoldások tartományával

A megengedett megoldások tartománya (MMT) mindazon alternatívák (változóértékek halmazainak) összessége, amelyek kielégítik a feladat feltételeit. Az optimális megoldás az a pont (vagy pontok) ebben a tartományban, ahol a célfüggvény eléri extrémumát. Ha az MMT üres, akkor a feladatnak sem megengedett, sem pedig optimális megoldása nincs.

A célfüggvény és a feltételek szerepe

• A feltételek határozzák meg a lehetséges megoldások halmazát (MMT).
• A célfüggvény határozza meg, hogy ezek közül a lehetséges megoldások közül melyik a legjobb (optimális).

Célfüggvény nélkül nem lehet meghatározni, hogy a megengedett megoldások közül melyik az optimális. Feltételek nélkül a feladat triviális lehet, vagy nem rendelkezhet véges optimális megoldással (például egy lineáris függvény maximalizálása feltételek nélkül).

Az optimális megoldás egyértelműsége

Az optimális megoldás nem mindig egyértelmű. Egyes feladatokban (például a lineáris programozásban, ha a célfüggvény párhuzamos az egyik aktív feltétellel) végtelen sok optimális megoldás létezhet, amelyek azonos célfüggvényértékkel rendelkeznek. Az optimum pontjában (pontjaiban) azonban a célfüggvény értéke mindig egyedi (ha az optimum létezik).

Meghatározási módszerek

Az optimális megoldások megkeresésére az operációkutatásban különböző matematikai módszereket alkalmaznak, a modell típusától függően:

• Szimplex-módszer (lineáris programozáshoz)
• Gradiens-módszerek és egyéb numerikus módszerek (nemlineáris programozáshoz)
• Korlátozás és szétválasztás módszere, metszősíkok módszerei (egészértékű programozáshoz)
• Dinamikus programozás módszerei

Modellfüggőség

Fontos megérteni, hogy egy megoldás csak az elfogadott matematikai modell keretein belül optimális. Ha a modell nem tükrözi megfelelően a valós helyzetet (helytelenül van megválasztva a célfüggvény, fontos feltételek vagy összefüggések nincsenek figyelembe véve), akkor a formálisan megtalált optimális megoldás a gyakorlatban hatástalannak vagy akár tévesnek bizonyulhat.

Optimalitás többkritériumos feladatokban

Több célfüggvénnyel rendelkező feladatokban (többkritériumos optimalizálás) az egyetlen optimális megoldás fogalmát gyakran a Pareto-optimalitás fogalma váltja fel. A Pareto-optimális megoldás olyan megengedett megoldás, amelynél nem lehet javítani az egyik célfüggvény értékén anélkül, hogy legalább egy másik célfüggvény értéke ne romlana.

Irodalom

• Vencel, J. Sz. Operációkutatás: feladatok, elvek, módszertan. — Moszkva: Nauka, 1988.
• Taha, Hamdy A. Operations Research: An Introduction. — Pearson. (10th ed., 2017)
• Hillier, Frederick S.; Lieberman, Gerald J. Introduction to Operations Research. — McGraw-Hill Education. (11th ed., 2021)

Lásd még

• Operációkutatás
• Optimalizálás
• Matematikai modell
• Célfüggvény
• Feltételek
• Megengedett megoldások tartománya
• Megengedett megoldás
• Kritérium
• Döntéselmélet
• Többkritériumos optimalizálás
• Pareto-optimalitás
• Extrémum