szó jelentését keresi. A DICTIOUS-ban nem csak a
szó összes szótári jelentését megtalálod, hanem megismerheted az etimológiáját, a jellemzőit és azt is, hogyan kell a
szót egyes és többes számban mondani. Minden, amit a
szóról tudni kell, itt található. A
szó meghatározása segít abban, hogy pontosabban és helyesebben fogalmazz, amikor beszélsz vagy írsz. A
és más szavak definíciójának ismerete gazdagítja a szókincsedet, és több és jobb nyelvi forráshoz juttat.
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.
.
- Célfüggvény (objective function): Egy lineáris függvény, amit maximalizálni vagy minimalizálni szeretnénk. Pl.
.
- 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:
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:
Feltételek:
Megoldás:
- A megengedett tartományt grafikus módszerrel ábrázoljuk.
- A csúcspontokat kiszámoljuk.
- Minden csúcspontnál kiszámítjuk
értékét.
- A legnagyobb
é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?