--- title: "Egészértékű programozás" source: "https://systems-analysis.info/int/Eg%C3%A9sz%C3%A9rt%C3%A9k%C5%B1_programoz%C3%A1s" wiki: "systems-analysis.info/int" article: "Egészértékű_programozás" language: "hu" categories: - "Category:Hungarian" - "Category:Operations research" revision_id: 1822 wiki_created_at: 2026-09-06T22:54:36Z wiki_modified_at: 2026-09-06T22:54:36Z downloaded_at: 2026-09-07T22:48:03Z --- # Egészértékű programozás **Egészértékű programozás** (**EP**; angol *integer programming, IP*) — a matematikai optimalizálás azon ága, amelyben olyan feladatokat vizsgálnak, ahol a változók egy része vagy mindegyike csak egész értéket vehet fel[\[1\]](https://systems-analysis.info/int/Eg%C3%A9sz%C3%A9rt%C3%A9k%C5%B1_programoz%C3%A1s#cite_note-ru-wiki-ip-1). A legtöbbet tanulmányozott speciális eset az **egészértékű lineáris programozás** (**ELP**; angol *integer linear programming, ILP*), amelyben a célfüggvény és a feltételek lineárisak. A lineáris programozástól eltérően, ahol a változók tetszőleges valós értéket felvehetnek, az egészértékűségi követelmény az EP-feladatokat lényegesen nehezebbé teszi[\[2\]](https://systems-analysis.info/int/Eg%C3%A9sz%C3%A9rt%C3%A9k%C5%B1_programoz%C3%A1s#cite_note-wolsey-book-2). Az egészértékű programozás széles körben alkalmazható a közgazdaságtanban, a logisztikában, a termelésirányításban és más területeken, ahol a változók természetüknél fogva diszkrétek (például a legyártott termékek száma vagy a dolgozók száma)[\[3\]](https://systems-analysis.info/int/Eg%C3%A9sz%C3%A9rt%C3%A9k%C5%B1_programoz%C3%A1s#cite_note-pisaruk-book-3). ## Meghatározás és terminológia Az egészértékű lineáris programozás általános feladata a következőképpen írható fel: Keressük azt a $x$ vektort, amely: maximalizálja (vagy minimalizálja) $c^{T}x$ a következő feltételek mellett: $Ax \leq b$ $x \geq 0$ $x \in {\mathbb{Z}}^{n}$ (a $x$ vektor összes komponense egész szám) itt $x$ a változók vektora, $c$ és $b$ vektorok, $A$ pedig az együtthatók mátrixa[\[4\]](https://systems-analysis.info/int/Eg%C3%A9sz%C3%A9rt%C3%A9k%C5%B1_programoz%C3%A1s#cite_note-conforti-book-4). A változókra vonatkozó követelményektől függően a következő feladattípusokat különböztetjük meg: - **Teljesen egészértékű programozás**: minden változónak egésznek kell lennie. - **Vegyes egészértékű programozás** (angol *mixed-integer programming, MIP*): csak a változók egy része kell, hogy egész legyen. - **Bináris (0-1) programozás**: a változók csak 0 vagy 1 értéket vehetnek fel, ami lehetővé teszi az „igen/nem" típusú logikai döntések modellezését. ## Legfontosabb tulajdonságok és bonyolultság ### Számítási bonyolultság Az egészértékű lineáris programozás feladata általános esetben NP-nehéz[\[5\]](https://systems-analysis.info/int/Eg%C3%A9sz%C3%A9rt%C3%A9k%C5%B1_programoz%C3%A1s#cite_note-karp-1972-5). Ez azt jelenti, hogy nem létezik ismert algoritmus, amely tetszőleges EP-feladat pontos optimális megoldását polinomiális idő alatt meg tudná találni. A bonyolultság a feladat kombinatorikus természetéből adódik, mivel a lehetséges egészértékű megoldások száma a változók számának növekedésével exponenciálisan nőhet. ### Kapcsolat a lineáris programozással (LP-relaxáció) Bármely EP-feladathoz megfogalmazható annak **lineáris relaxációja** — egy lineáris programozási (LP) feladat, amelyből elhagyjuk a változók egészértékűségének követelményét. Az LP-relaxáció megoldásának két fontos tulajdonsága van: 1. Lényegesen gyorsabban megtalálható (polinomiális idő alatt). 2. Az LP-relaxáció célfüggvényének optimális értéke korlátot ad (maximalizálási feladatnál felső, minimalizálási feladatnál alsó korlátot) az eredeti egészértékű feladat optimális értékére[\[2\]](https://systems-analysis.info/int/Eg%C3%A9sz%C3%A9rt%C3%A9k%C5%B1_programoz%C3%A1s#cite_note-wolsey-book-2). Azonban az LP-relaxáció töredékes megoldásának a legközelebbi egész számokra való egyszerű kerekítése általában nem vezet az egészértékű feladat optimális, sőt megengedett megoldásához sem[\[1\]](https://systems-analysis.info/int/Eg%C3%A9sz%C3%A9rt%C3%A9k%C5%B1_programoz%C3%A1s#cite_note-ru-wiki-ip-1). ### A teljes unimodularitás tulajdonsága Létezik az ELP-feladatoknak egy fontos osztálya, amelyek ugyanolyan könnyen megoldhatók, mint az LP-relaxációjuk. Ezek olyan feladatok, amelyekben a feltételek $A$ mátrixa **teljesen unimoduláris** (azaz bármely négyzetes részmátrixának determinánsa 0, +1 vagy −1). Ha a $A$ mátrix teljesen unimoduláris és a $b$ vektor egészértékű, akkor az LP-relaxáció megengedett megoldásainak poliéderének összes csúcsa automatikusan egész lesz. Következésképpen a szimplex-módszerrel talált megoldás egészértékű lesz[\[4\]](https://systems-analysis.info/int/Eg%C3%A9sz%C3%A9rt%C3%A9k%C5%B1_programoz%C3%A1s#cite_note-conforti-book-4). Ilyen feladatok például a szállítási feladat és a hozzárendelési feladat. ## Megoldási módszerek Az általános EP-feladatok megoldásához, amelyek nem rendelkeznek a teljes unimodularitás tulajdonságával, pontos módszereket dolgoztak ki az implicit felsorolás elvén alapulva. - **Korlátozás és szétválasztás módszere** (angol *Branch and Bound*) — a fő pontos módszer, amely a megengedett megoldások halmazának szisztematikus részhalmazokra bontásán (szétválasztás) és azon részhalmazok elhagyásán alapul, amelyek biztosan nem tartalmaznak optimális megoldást. A részhalmazok ígéretességének értékelésére LP-relaxációt alkalmaznak[\[6\]](https://systems-analysis.info/int/Eg%C3%A9sz%C3%A9rt%C3%A9k%C5%B1_programoz%C3%A1s#cite_note-en-wiki-ip-6). - **Vágósíkok módszere** (Gomory-módszer; angol *Cutting Plane Method*) — iteratív megközelítés, amely fokozatosan új lineáris feltételeket („vágásokat") ad a feladathoz. Ezek a vágások „levágják" az LP-relaxáció töredékes megoldásait anélkül, hogy egyetlen megengedett egészértékű megoldást is érintenének, és fokozatosan közelítik az LP-relaxáció megengedett megoldásainak tartományát az egészértékű megoldások konvex burkához[\[6\]](https://systems-analysis.info/int/Eg%C3%A9sz%C3%A9rt%C3%A9k%C5%B1_programoz%C3%A1s#cite_note-en-wiki-ip-6). A modern megoldók általában hibrid algoritmusokat alkalmaznak, mint például a **korlátozás, szétválasztás és vágás módszere** (angol *Branch and Cut*), amely mindkét megközelítés előnyeit ötvözi. ## Példák és alkalmazási területek Az egészértékű programozás számos klasszikus kombinatorikus optimalizálási feladat modellezését teszi lehetővé. - *Hátizsák-feladat*: klasszikus 0-1 programozási feladat, amelyben maximális összértékű tárgyak halmazát kell kiválasztani úgy, hogy az össztömegre vonatkozó korlátot ne lépjük túl. - *Az utazó ügynök feladata*: a legrövidebb, adott városokon áthaladó útvonal keresésének feladata. Egészértékű programozási feladatként fogalmazható meg, ahol a változók a gráf éleinek a végső útvonalba való felvételét jelölik. Rugalmasságának köszönhetően az EP az operációkutatás egyik legnépszerűbb eszköze, és a következő területeken talál alkalmazásra: - **Logisztika és ellátási lánc menedzsment**: szállítási útvonalak optimalizálása, raktárak elhelyezése, készletgazdálkodás. - **Termelésirányítás**: gyártási menetrendek összeállítása, erőforrások elosztása, gépek terhelése. - **Pénzügyek és közgazdaságtan**: befektetési portfólió kialakítása, tőkebefektetések tervezése. - **Telekommunikáció és energetika**: kommunikációs hálózatok tervezése, erőművek üzemeltetésének tervezése. ## Lásd még - Lineáris programozás - Korlátozás és szétválasztás módszere ## Megjegyzések 1. ↑ [1.0](https://systems-analysis.info/int/Eg%C3%A9sz%C3%A9rt%C3%A9k%C5%B1_programoz%C3%A1s#cite_ref-ru-wiki-ip_1-0) [1.1](https://systems-analysis.info/int/Eg%C3%A9sz%C3%A9rt%C3%A9k%C5%B1_programoz%C3%A1s#cite_ref-ru-wiki-ip_1-1) "Целочисленное программирование". *Википедия*. [1] 2. ↑ [2.0](https://systems-analysis.info/int/Eg%C3%A9sz%C3%A9rt%C3%A9k%C5%B1_programoz%C3%A1s#cite_ref-wolsey-book_2-0) [2.1](https://systems-analysis.info/int/Eg%C3%A9sz%C3%A9rt%C3%A9k%C5%B1_programoz%C3%A1s#cite_ref-wolsey-book_2-1) Wolsey, Laurence A. (2020). *Integer Programming* (2nd ed.). John Wiley & Sons. 3. [↑](https://systems-analysis.info/int/Eg%C3%A9sz%C3%A9rt%C3%A9k%C5%B1_programoz%C3%A1s#cite_ref-pisaruk-book_3-0) Писарук Н.Н. (2010). *Модели и методы смешанного целочисленного программирования*. Минск: БГУ. 4. ↑ [4.0](https://systems-analysis.info/int/Eg%C3%A9sz%C3%A9rt%C3%A9k%C5%B1_programoz%C3%A1s#cite_ref-conforti-book_4-0) [4.1](https://systems-analysis.info/int/Eg%C3%A9sz%C3%A9rt%C3%A9k%C5%B1_programoz%C3%A1s#cite_ref-conforti-book_4-1) Conforti, M., Cornuéjols, G., & Zambelli, G. (2014). *Integer Programming*. Springer. 5. [↑](https://systems-analysis.info/int/Eg%C3%A9sz%C3%A9rt%C3%A9k%C5%B1_programoz%C3%A1s#cite_ref-karp-1972_5-0) Karp, Richard M. (1972). "Reducibility among Combinatorial Problems". In: *Complexity of Computer Computations*. Springer. 6. ↑ [6.0](https://systems-analysis.info/int/Eg%C3%A9sz%C3%A9rt%C3%A9k%C5%B1_programoz%C3%A1s#cite_ref-en-wiki-ip_6-0) [6.1](https://systems-analysis.info/int/Eg%C3%A9sz%C3%A9rt%C3%A9k%C5%B1_programoz%C3%A1s#cite_ref-en-wiki-ip_6-1) "Integer programming". *Wikipedia*. [2]