linear programming

Angol

Főnév

linear programming (tsz. linear programmings)

(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.

Alapfogalmak

Döntési változók: Azok a változók, amelyeket optimalizálunk. Pl. $x_{1}, x_{2}, \dots, x_{n}$ .
Célfüggvény (objective function): Egy lineáris függvény, amit maximalizálni vagy minimalizálni szeretnénk. Pl. $max Z = 5 x_{1} + 3 x_{2}$ .
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.
Megengedett tartomány (feasible region): Az a pontkészlet, ahol a feltételek teljesülnek.
Optimális megoldás: A célfüggvény olyan értéke, amely a megengedett tartományban maximális vagy minimális.

Lineáris programozási probléma általános alakja:

$\begin{matrix} Maximalizálni: & Z = c_{1} x_{1} + c_{2} x_{2} + \dots + c_{n} x_{n} \\ Feltéve, hogy: & {\begin{matrix} a_{11} x_{1} + a_{12} x_{2} + \dots + a_{1 n} x_{n} \leq b_{1} \\ a_{21} x_{1} + a_{22} x_{2} + \dots + a_{2 n} x_{n} \leq b_{2} \\ ⋮ \\ a_{m 1} x_{1} + a_{m 2} x_{2} + \dots + a_{m n} x_{n} \leq b_{m} \\ x_{1}, x_{2}, \dots, x_{n} \geq 0 \end{matrix} \end{matrix}$

Megoldási módszerek

1. Grafikus módszer

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.

2. Szimplex módszer (Simplex Method)

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.

3. Kétfázisú módszer (Two-phase method)

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).

4. Belső pontos módszerek (Interior Point Methods)

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.

Tipikus alkalmazások

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.

Tulajdonságok

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).

Kiterjesztések

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.

Példa

Feladat: Maximalizálni: $Z = 3 x + 5 y$

Feltételek:

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

Megoldás:

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

Összefoglalá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?

További információk

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)