linear optimization

linear optimization (tsz. linear optimizations)

1. (informatika) lineáris optimalizálás

A lineáris optimalizáció (angolul linear optimization vagy linear programming) az optimalizálás egyik legfontosabb és leggyakrabban alkalmazott ága, ahol a cél egy lineáris függvény (célfüggvény) maximalizálása vagy minimalizálása lineáris korlátozó feltételek mellett. Az elnevezés arra utal, hogy minden egyenlet és egyenlőtlenség lineáris, és az összes változó folytonos (azaz nem korlátozott egész értékekre).

A lineáris optimalizáció olyan matematikai probléma, amely:

• döntési változókat tartalmaz (pl. ${\textstyle x_{1},x_{2},\dots ,x_{n}}$),
• egy lineáris célfüggvényt, amelyet optimalizálni (maximalizálni vagy minimalizálni) kell,
• valamint lineáris feltételeket (egyenletek vagy egyenlőtlenségek), amelyek korlátozzák a változók lehetséges értékeit.

Egy lineáris optimalizálási feladat (szokásos alakban) így néz ki:

Maximalizálni:

$${\displaystyle Z=c_{1}x_{1}+c_{2}x_{2}+\ldots +c_{n}x_{n}}$$

Feltéve, hogy:

$${\displaystyle {\begin{cases}a_{11}x_{1}+a_{12}x_{2}+\dots +a_{1n}x_{n}\leq b_{1}\\a_{21}x_{1}+a_{22}x_{2}+\dots +a_{2n}x_{n}\leq b_{2}\\\vdots \\a_{m1}x_{1}+a_{m2}x_{2}+\dots +a_{mn}x_{n}\leq b_{m}\\x_{1},x_{2},\dots ,x_{n}\geq 0\end{cases}}}$$

Ahol:

• ${\textstyle x_{i}}$ a döntési változók
• ${\textstyle c_{i}}$ a célfüggvény együtthatói (pl. haszon, költség)
• ${\textstyle a_{ij}}$ a korlátmátrix elemei
• ${\textstyle b_{j}}$ az egyenlőtlenségek jobb oldali értékei

A lineáris optimalizáció számos gyakorlati területen hasznosítható:

• Gyártás és termelés – gépidő, anyagfelhasználás optimalizálása
• Szállítmányozás és logisztika – szállítási költségek csökkentése
• Pénzügy – portfólió optimalizálás, költségcsökkentés
• Hálózattervezés – erőforrás-elosztás
• Energia – erőművek termelésének optimalizálása

• Csak 2 változós esetben használható
• A korlátokat ábrázoljuk a síkban
• A célfüggvényt párhuzamos egyenesek mentén mozgatva keressük meg a legjobb pontot (az egyik csúcspontban lesz az optimum)

• Átalakítja a problémát standard alakba
• Kezdeti bázismegoldást választ (általában a sarokpontban)
• Pivotálással végighalad a bázisok között a célfüggvény javítása érdekében
• Megáll, ha az optimum elérhető (nincs javító irány)

• Az optimumot nem a szélen, hanem a megengedett tartomány belsejében keresik
• Nagy dimenziós problémáknál gyorsabb lehet

Feladat: Egy gyár 2 terméket gyárt. Termék A 4 munkaórát és 3 alapanyagot igényel, termék B 2 munkaórát és 5 alapanyagot. Összesen 100 munkaóra és 150 alapanyag áll rendelkezésre. Termék A egységnyeresége: 6 egység, B-é: 8 egység. Mennyi terméket gyártsunk, hogy a nyereség maximális legyen?

Változók:

• ${\textstyle x}$: termék A darabszáma
• ${\textstyle y}$: termék B darabszáma

Célfüggvény:

$${\displaystyle \max Z=6x+8y}$$

Feltételek:

$${\displaystyle {\begin{cases}4x+2y\leq 100\quad {\text{(munkaóra)}}\\3x+5y\leq 150\quad {\text{(alapanyag)}}\\x,y\geq 0\end{cases}}}$$

Ez egy lineáris optimalizálási probléma, megoldható grafikus módszerrel vagy szimplex algoritmussal.

• Egyedüli optimális megoldás: egy pont, ahol a célérték maximális/minimális
• Több optimális megoldás: az optimum több pontban is elérhető (pl. egy szakasz mentén)
• Nincs megoldás: ha a feltételek ellentmondanak egymásnak (infeasible)
• Nem korlátos megoldás: ha a célfüggvény értéke végtelenbe nőhet

Az az eloszlás vagy megoldás, amely hosszú távon stabil — például hálózatokban vagy Markov-láncokban.

Megmutatja, hogy az optimális megoldás hogyan változik, ha a modell paraméterei (pl. erőforrások mennyisége vagy haszonérték) változnak. Kritikus a gazdasági döntéshozatalban.

• Egészértékű lineáris programozás (ILP): ha a változók csak egész számok lehetnek.
• Vegyes egészértékű programozás (MILP): ha csak néhány változó korlátozott egész értékekre.
• Többcélú optimalizálás (multi-objective LP): ha több célfüggvényt kell egyidejűleg kezelni.
• Paraméteres programozás: amikor a feltételek vagy a célfüggvény paraméterei változnak.

Lineáris optimalizálás gyakorlati megoldásához elterjedt programcsomagok:

• Excel Solver
• LINDO / LINGO
• GLPK
• IBM CPLEX
• Gurobi
• MATLAB / Octave

Ezek automatikusan megoldják a modelleket, és gyakran szenzitivitási riportot is generálnak.

A lineáris optimalizáció az optimalizálás egyik legegyszerűbb, de leghatékonyabb formája, amelyet széles körben használnak az iparban, gazdaságban, tudományban és technológiában. A feladat célja egy lineáris célfüggvény optimalizálása (maximum vagy minimum) úgy, hogy az összes lineáris korlátot teljesítjük.

• Könnyen modellezhető valós problémák
• Hatékony algoritmusok léteznek
• Átlátható, értelmezhető eredmények
• Szoftveresen jól támogatott

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