linear programming

linear programming (tsz. linear programmings)

1. (informatika) lineáris programozás

A lineáris programozás (Linear Programming, LP) egy matematikai optimalizálási módszer, amelynek célja egy lineáris célfüggvény maximumának vagy minimumának meghatározása, adott lineáris egyenlőtlenségi vagy egyenlet-rendszerek által megszabott feltételek (korlátozások) mellett. A lineáris programozás kulcsszerepet játszik az operációkutatásban, logisztikában, gazdaságban, pénzügyekben, ipari termelésben és sok más döntéshozatali folyamatban, ahol korlátos erőforrások optimális kihasználása a cél.

1. Döntési változók: Azok a változók, amelyeket optimalizálunk. Pl. ${\textstyle x_{1},x_{2},\dots ,x_{n}}$.
2. Célfüggvény (objective function): Egy lineáris függvény, amit maximalizálni vagy minimalizálni szeretnénk. Pl. ${\textstyle \max Z=5x_{1}+3x_{2}}$.
3. Feltételek (korlátozó feltételek, constraint-ek): Lineáris egyenletek vagy egyenlőtlenségek, amelyek korlátozzák a döntési változók értékét.
4. Megengedett tartomány (feasible region): Az a pontkészlet, ahol a feltételek teljesülnek.
5. Optimális megoldás: A célfüggvény olyan értéke, amely a megengedett tartományban maximális vagy minimális.

$${\displaystyle {\begin{aligned}{\text{Maximalizálni:}}\quad &Z=c_{1}x_{1}+c_{2}x_{2}+\dots +c_{n}x_{n}\\{\text{Feltéve, hogy:}}\quad &{\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}}\end{aligned}}}$$

Kétváltozós esetben használható. A megoldást a feltételek által kijelölt sokszög (megengedett tartomány) határán keressük, és a célfüggvény meredeksége mentén mozgatott egyenes alapján választjuk ki az optimális pontot.

George Dantzig által kifejlesztett algoritmus, amely a megengedett tartomány csúcspontjai között iterálva halad az optimális megoldás felé. Működése:

• Átalakítja a problémát standard alakba.
• Kezdeti alapmegoldást választ.
• Pivotálással javítja a célértéket.
• Megáll, ha nincs több pozitív (vagy negatív) javítási lehetőség.

Ha nincs nyilvánvaló kezdeti megoldás, segédváltozók segítségével először keres egy induló megoldást (1. fázis), majd alkalmazza a szimplexet a valódi célfüggvényre (2. fázis).

Alternatív módszer, amely a megengedett tartomány belsejében haladva közelíti az optimumot. Nagy dimenziós problémáknál hatékonyabb lehet, mint a szimplex.

• Gyártás és termelés: nyersanyagelosztás, termelési mennyiségek optimalizálása.
• Szállítmányozás: szállítási költségek minimalizálása (szállítási probléma).
• Pénzügyek: portfólió optimalizálása, kockázat minimalizálás.
• Hálózattervezés: áramlás maximalizálás, útvonal kiválasztás.
• Logisztika: készletszint optimalizálás, raktárgazdálkodás.

• A megoldás, ha létezik, mindig a megengedett tartomány egyik csúcspontján található.
• A feltételek konvex halmazt definiálnak, tehát ha van megoldás, az globálisan optimális.
• Lehet egyetlen optimális megoldás, végtelen sok optimális megoldás, nincs megoldás (ellentmondó feltételek) vagy nem korlátos optimum (nincs maximum/minimum, az érték végtelenbe nőhet).

• Egészértékű programozás (Integer Programming): a változóknak egész számoknak kell lenniük.
• Vegyes egészértékű programozás (Mixed Integer Programming): néhány változó egész, mások valósak.
• Paraméteres LP: a korlátok vagy a célfüggvény paraméterei változnak.
• Duaalitás: minden LP problémához tartozik egy ún. duál probléma, amely új nézőpontból írja le ugyanazt az optimalizálási feladatot.

Feladat: Maximalizálni: ${\textstyle Z=3x+5y}$

Feltételek:

$${\displaystyle {\begin{cases}2x+3y\leq 12\\x+y\leq 5\\x\geq 0,y\geq 0\end{cases}}}$$

Megoldás:

• A megengedett tartományt grafikus módszerrel ábrázoljuk.
• A csúcspontokat kiszámoljuk.
• Minden csúcspontnál kiszámítjuk ${\textstyle Z}$ értékét.
• A legnagyobb ${\textstyle Z}$ értéket adó pont az optimális megoldás.

A lineáris programozás egy rendkívül fontos és gyakran alkalmazott eszköz az optimalizálási feladatok megoldására. Egyszerű, mégis hatékony formája miatt ipari és tudományos területeken is elterjedt. A szimplex módszer és a belső pontos algoritmusok lehetővé teszik nagy méretű feladatok gyors és pontos megoldását. A lineáris programozás nemcsak egy matematikai módszer, hanem egy gondolkodásmód is: hogyan lehet egy korlátokkal teli rendszerben a lehető legjobban dönteni?

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