Lineáris programozás

Lineáris programozás — a matematikai programozás egyik ága és a kutatásmódszertan (operations research) széles körben alkalmazott eszköze, amely egy lineáris függvény szélsőértékének (maximumának vagy minimumának) meghatározását célzó feladatok elméletével és megoldási módszereivel foglalkozik, lineáris feltételek mellett.

A lineáris programozás (LP) az egyik legerőteljesebb és leggyakrabban alkalmazott eszköz optimalizálási feladatok megoldásához a közgazdaságtanban, az irányításban, a tervezésben, a logisztikában és számos más területen.

Tárgya és rendeltetése

A lineáris programozás alapfeladata — a korlátozott erőforrások elosztásának legjobb (optimális) módját megtalálni valamely cél elérése érdekében, amennyiben mind a cél, mind az erőforrás-felhasználásra vonatkozó feltételek lineáris összefüggésekkel kifejezhetők.

• A lineáris programozás lehetővé teszi olyan gyakorlati feladatok megoldását, mint:
• Optimális termelési tervezés.
• Szállítási folyamatok optimalizálása (szállítási feladat).
• Befektetések optimális elosztása.
• Anyagok optimális szabása. Hozzárendelési feladat.

Az LP feladat matematikai megfogalmazása

A lineáris programozás standard feladata a következőképpen fogalmazható meg:

Meg kell találni a döntési változók azon értékeit, amelyek maximalizálják vagy minimalizálják a lineáris célfüggvényt. Eközben a döntési változókra lineáris egyenletek és/vagy lineáris egyenlőtlenségek rendszeréből álló feltételek vonatkoznak. Általában a döntési változók nemnegatívitási feltételét is megköveteljük (értékeiknek nullánál nagyobbnak vagy egyenlőnek kell lenniük), amelyet a feladat fizikai vagy gazdasági értelme gyakran indokol.

Matematikailag ez lineáris függvényekkel és lineáris egyenlet-/egyenlőtlenség-rendszerekkel való munkát jelent.

Az LP alapfogalmai

• Döntési változók (irányítható változók): Azok a mennyiségek, amelyek értékeit a feladat megoldása során meg kell határozni (például különböző termékek gyártási volumene, különböző célokra fordított erőforrások mennyisége).
• Célfüggvény: A döntési változók lineáris függvénye, amelynek értékét maximalizálni vagy minimalizálni kell. Számszerűen fejezi ki a feladat célját (például teljes nyereség, összköltség).
• Feltételek: Lineáris egyenletek és/vagy egyenlőtlenségek rendszere, amelyeket a döntési változóknak ki kell elégíteniük. A feltételek az erőforrás-korlátokat, technológiai követelményeket, tervfeladatokat és a feladat egyéb körülményeit tükrözik.
• Megengedett megoldások tartománya (MMT): Mindazon döntésiváltozó-értékkombinációk halmaza, amelyek a feladat összes feltételét kielégítik. Geometriailag a többdimenziós térben az MMT konvex sokszöget (poliédert) alkot, amely esetleg nem korlátos vagy üres.
• Megengedett megoldás: A döntési változók bármely, az MMT-hez tartozó értékkombinációja.
• Optimális megoldás: Az a megengedett megoldás, amelynél a célfüggvény eléri szélsőértékét (maximumát vagy minimumát). Ha az optimális megoldás létezik, az mindig az MMT határán helyezkedik el, legalább az MMT konvex sokszögének egyik csúcsában (az LP alaptétele).

Az LP feladatok megoldási módszerei

Az LP feladatok megoldásának több alapvető módszere létezik:

• Grafikus módszer: Két döntési változót tartalmazó feladatoknál alkalmazható. Lehetővé teszi az MMT és a célfüggvény szemléletes ábrázolását a síkban, és az optimális megoldás megtalálását az MMT csúcsainak elemzése vagy a célfüggvény szintvonalának mozgatása révén.
• Szimplex-módszer: George Dantzig által kidolgozott általános célú iteratív algoritmus. A módszer az MMT egyik csúcsáról a szomszédos csúcsra lép, minden lépésnél javítva a célfüggvény értékét, amíg meg nem találja az optimális megoldást. Ez az LP feladatok megoldásának klasszikus és legelterjedtebb módszere.
• Belső pontos módszerek: A szimplex-módszernél később megjelent alternatív algoritmusok. Ezek az optimális megoldás felé az MMT belsejében haladnak, nem annak határain. Ezek a módszerek különösen hatékonyak nagyon nagy méretű LP feladatok megoldásában.

Dualitás a lineáris programozásban

Minden LP feladathoz (amelyet primál feladatnak nevezünk) rendelhető egy másik LP feladat, amelyet duális feladatnak hívunk. A primál és a duális feladat szorosan összefügg egymással:

Az egyik feladat megoldása információt nyújt a másik megoldásáról. Mindkét feladatban az optimális célfüggvényértékek megegyeznek (ha léteznek). A duális feladat változóinak fontos közgazdasági értelmezésük van — az erőforrások árnyékárait (vagy duális értékeléseit) fejezik ki, megmutatva, hogy a primál feladat optimális célfüggvényértéke mennyivel változik, ha a megfelelő erőforrásra vonatkozó feltétel kis mértékben módosul.

Az LP alkalmazásai

A lineáris programozás széles körű alkalmazást talál:

• A közgazdaságtanban és az üzleti életben (termelési tervezés, logisztika, pénzügy, marketing).
• Az iparban (technológiai folyamatok optimalizálása, készletgazdálkodás, anyagszabás).
• A közlekedésben (útvonalak, menetrendek optimalizálása). A mezőgazdaságban (vetésterületek, takarmányadagok optimalizálása).
• Az energetikában (erőmű-kapacitások terhelésének optimalizálása).

Irodalom

• Dantzig, Gy. Lineáris programozás, alkalmazásai és általánosításai. — M.: Progressz, 1966.
• Judin, D. B., Gols'tejn, E. G. Lineáris programozás (elmélet, módszerek és alkalmazások). — M.: Nauka, 1969.
• Taha, Hamdy A. Operations Research: An Introduction. — Pearson. (10th ed., 2017)
• Hillier, Frederick S.; Lieberman, Gerald J. Introduction to Operations Research. — McGraw-Hill Education. (11th ed., 2021)

Lásd még

• Operációkutatás
• Optimalizálás
• Célfüggvény
• Feltételek
• Megengedett megoldások tartománya
• Optimális megoldás