optimization problem

optimization problem (tsz. optimization problems)

1. (informatika) optimalizálási feladat

Az optimization problem (optimalizálási feladat) célja, hogy megtaláljuk egy függvény legjobb (legkisebb vagy legnagyobb) értékét egy adott feltételrendszer mellett. Ezek a problémák a matematika, mérnöki tudományok, gazdaságtan, mesterséges intelligencia, és ipari rendszerek egyik legfontosabb alkalmazási területei.

Általános formája:

$${\displaystyle {\text{Minimize / Maximize: }}f(x){\text{subject to: }}x\in S}$$

• ${\textstyle f(x)}$: célfüggvény (objective function)
• ${\textstyle x}$: változók vektora (decision variables)
• ${\textstyle S}$: megengedett tartomány (constraint set)

• Minimization: költségek, veszteség, energia csökkentése
• Maximization: profit, teljesítmény, hatékonyság növelése

A legtöbb matematikai módszer minimálásra van kitalálva – ha maximálni akarunk, átalakítjuk:

$${\displaystyle \max f(x)=-\min}$$

$${\displaystyle g_{i}(x)\leq 0\quad (1\leq i\leq m)}$$

$${\displaystyle h_{j}(x)=0\quad (1\leq j\leq p)}$$

$${\displaystyle x_{i}\geq 0}$$

Ezek együtt határozzák meg a megengedett megoldáshalmazt.

• A célfüggvény és korlátok lineárisak

• Példa:

  Értelmezés sikertelen (formai hiba): {\displaystyle \max Z = 3x + 2y \\ \text{s.t. } x + 2y \leq 6, \quad x, y \geq 0 }

Megoldható szimplex algoritmussal vagy belsőpontos módszerrel.

• A változók csak egész számok lehetnek
• Kombinatorikus problémákra ideális

• A célfüggvény vagy valamelyik korlát nem lineáris
• Tipikus a gazdaságban, gépi tanulásban

• A probléma több lépésből áll, állapot–döntés rendszerrel
• Visszalépéses módszer (Bellman-egyenlet)

• Cél: megtalálni a globális optimumot, nem csak a helyit
• Alkalmaz: genetikus algoritmus, szimulált hűtés, Monte Carlo

Az optimalizálási probléma egy térbeli táj:

• A célfüggvény egy felszín
• A korlátok egy tartományt határoznak meg
• A cél: a felszínen a legalacsonyabb vagy legmagasabb pontot megtalálni a tartományon belül

Feladat:

• Maximalizáljuk a profitot: ${\textstyle Z=50x+40y}$

• Erőforrás-korlátok:

  Értelmezés sikertelen (formai hiba): {\displaystyle 2x + y \leq 100 \\ x + 2y \leq 80 \\ x, y \geq 0 }

Lépések:

1. Ábrázolás → megengedett tartomány
2. Sarokpontok meghatározása
3. Célfüggvény kiértékelése sarokpontokon
4. Ahol ${\textstyle Z}$ maximális → megoldás

• Minden helyi minimum globális is
• Megoldása stabil és számítható

• Lehet több helyi minimum → nehéz a globális optimumot megtalálni

• Termelés optimalizálása
• Logisztika – útvonaloptimalizálás, raktározás
• Pénzügy – portfólió kiválasztás
• Mesterséges intelligencia – gépi tanulási modellek optimalizálása
• Energetika – hálózatok költségminimalizálása

Elem	Leírás
Célfüggvény	Amit minimalizálunk vagy maximalizálunk
Döntési változók	A megoldásban szereplő ismeretlenek
Korlátok	A döntésekre vonatkozó feltételek
Megoldás	Olyan ${\textstyle x}$, ami teljesíti a korlátokat és optimalizálja ${\textstyle f(x)}$
Optimum	A legjobb lehetséges célérték

A matematikai optimalizálás elengedhetetlen eszköz a modern tudományban és technológiában, a döntéshozatal formalizálására, erőforrások hatékony elosztására, és intelligens rendszerek tervezésére.

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