--- title: "Lineáris programozás" source: "https://systems-analysis.info/int/Line%C3%A1ris_programoz%C3%A1s" wiki: "systems-analysis.info/int" article: "Lineáris_programozás" language: "hu" categories: - "Category:Hungarian" - "Category:Mathematical modeling" - "Category:Operations research" revision_id: 3872 wiki_created_at: 2026-09-06T23:27:20Z wiki_modified_at: 2026-09-06T23:27:20Z downloaded_at: 2026-09-07T22:59:31Z --- # 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