mathematical optimization

Angol

Főnév

mathematical optimization (tsz. mathematical optimizations)

(informatika) A matematikai optimalizálás célja egy függvény legjobb (maximum vagy minimum) értékének megtalálása egy adott feltételrendszer mellett. Ez az érték lehet például a költség minimalizálása, a profit maximalizálása, vagy egy rendszer teljesítményének optimalizálása.

Más néven: matematikai programozás, numerikus optimalizálás vagy egyszerűen optimalizálás.

2. Általános formája

Matematikailag az optimalizálási probléma általános alakja:

${\begin{aligned}{\text{Cél:}}\quad &\min _{x\in \mathbb {R} ^{n}}f(x)\\{\text{Mellett:}}\quad &g_{i}(x)\leq 0\quad {\text{(egyenlőtlenségek)}}\\&h_{j}(x)=0\quad {\text{(egyenlőségek)}}\\&x\in X\subseteq \mathbb {R} ^{n}\end{aligned}}$

ahol:

${\textstyle x}$ : döntési változók vektora (pl. ár, mennyiség, idő)
${\textstyle f(x)}$ : célfüggvény (amit minimalizálni vagy maximalizálni akarunk)
${\textstyle g_{i}(x)}$ : egyenlőtlenségi korlátok (pl. erőforrás korlát)
${\textstyle h_{j}(x)}$ : egyenlőségi korlátok (pl. egyensúlyi feltétel)
${\textstyle X}$ : a változók értelmezési tartománya (pl. nemnegatív számok)

3. Optimalizálási problémák típusai

a) Lineáris programozás (LP)

Minden függvény lineáris.
Gyors, stabil algoritmusok léteznek: Simplex, interior point.

b) Egészértékű programozás (IP / ILP)

Változók csak egész értékeket vehetnek fel (pl. 0 vagy 1).
Nagyon fontos pl. menetrendkészítésnél.

c) Nemlineáris programozás (NLP)

A célfüggvény vagy valamelyik korlát nemlineáris.
Nehezebb, gyakran iteratív numerikus módszerek kellenek.

d) Kombinatorikus optimalizálás

A megoldási tér véges, de nagyon nagy (pl. gráfproblémák: útvonal, párosítás).
Ide tartozik a Travelling Salesman Problem, hátizsákprobléma, hozzárendelési feladat.

e) Dinamikus optimalizálás

Időfüggő döntések sorozata.
Dinamikus programozással vagy vezérléselmélettel oldható.

4. Példák a gyakorlatból

Terület	Példa
Ipar	Gyártásütemezés, termelési költség minimalizálása
Logisztika	Szállítási költség csökkentése, raktárak elosztása
Informatika	Memóriahasználat optimalizálása, gépi tanulási hiperparaméterek
Közgazdaságtan	Portfólió optimalizálás, haszonmaximalizálás
Energia	Hálózati veszteség csökkentése, megújuló források elosztása
Közlekedés	Útvonaltervezés, forgalomirányítás

5. A megoldások jellege

⚫ Globális optimum

A függvény valódi legkisebb vagy legnagyobb értéke az összes lehetséges pont közül.

⚪ Lokális optimum

A függvény csak egy kis környezetében legjobb – de nem feltétlenül a teljes tartományban.

6. Optimalitási feltételek

Elsőrendű feltétel (gradiens):

$\nabla f(x^{*})=0$

Korlátos problémánál: KKT-feltételek (Karush–Kuhn–Tucker)

Szükséges feltételek nemlineáris, egyenlőtlenséges feladatokhoz.
A Lagrange-függvény bevezetése révén kezelik a korlátokat.

7. Megoldási módszerek

Módszer	Típus	Előny
Simplex	Lineáris	Hatékony gyakorlatban
Interior Point	Lineáris / konvex	Nagyméretű feladatokra
Newton-módszer	Nemlineáris, lokális	Gyors konvergencia
Gradiensek	Nemlineáris, konvex	Kevés memóriaigény
Heurisztikák	Kombinatorikus	Nagy problémákra közelítő megoldások
Evolúciós algoritmusok	Általános	Globális optimum keresésére alkalmas

8. Konvexitás szerepe

🔵 Konvex optimalizálás:

Ha a célfüggvény és a megengedett tartomány konvex, akkor minden lokális optimum globális is.
Nagyon sok algoritmus jól működik konvex esetben.

🔴 Nemkonvex optimalizálás:

Több lokális optimum → nehezebb globális megoldást találni.
Gyakran csak heurisztikus vagy sztochasztikus megközelítésekkel oldható meg (pl. genetikus algoritmusok).

9. Optimalizálás Pythonban – példa

from scipy.optimize import linprog

# Max: 3x + 5y → Min: -3x - 5y
c = [-3, -5]
A = [[1, 0], [0, 2], [3, 2]]
b = [4, 12, 18]

res = linprog(c, A_ub=A, b_ub=b, method='highs')
print("Optimális megoldás:", res.x)
print("Optimális érték:", -res.fun)

10. Összefoglalás

A matematikai optimalizálás mindenütt jelen van, ahol racionális döntések szükségesek. A cél mindig az, hogy valamely erőforrást a lehető leghatékonyabban használjunk ki.

Legfontosabb kulcspontok:

Optimalizálás = legjobb döntés egy szabályrendszer szerint
Függhet az időtől, lehet lineáris vagy nemlineáris
A megoldási módszerek széles tárháza áll rendelkezésre
Széles alkalmazási kör: ipar, közgazdaságtan, mesterséges intelligencia, robotika

További információk

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