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.

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.

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

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\le b$

$x\ge 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.

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

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.

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

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

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