Megengedett megoldások tartománya

A megengedett megoldások tartománya (MMT) (más néven a megengedett megoldások halmaza, angolul Feasible region, feasible set) — az operációkutatásban, az optimalizálásban és a matematikai modellezésben ez azon összes lehetséges megoldás (változóértékek halmazainak) összessége, amelyek minden, a feladatra rótt feltételt kielégítenek.

Az MMT azt a részterét képezi a megoldástérnek, amelyen belül az optimális megoldást keressük. Minden, e tartományon kívül eső megoldás nem megengedett.

Meghatározás és kialakítás

A megengedett megoldások tartománya a feladat egyes feltételei által meghatározott halmazok metszeteként alakul ki. A feltételek a következő formákban jelenhetnek meg:

• Egyenlőtlenségek: Felső vagy alsó határokat állapítanak meg a változók értékeire vagy azok kombinációira (például „az A erőforrás felhasználása nem haladhatja meg a 100 egységet", „a legyártott termékek mennyisége legalább 50 darab legyen").
• Egyenlőségek: A feltétel pontos teljesítését követelik meg (például „az összes szállított mennyiség egyenlő 1000 tonnával", „a bejövő és kimenő folyamatok egyenlege nulla").
• Változókra vonatkozó előjelfeltételek: A változóknak gyakran nemnegatívaknak, egészeknek kell lenniük, vagy adott diszkrét halmazhoz kell tartozniuk.

Egy pont (vagy változóértékek vektora) pontosan akkor tartozik az MMT-hez, ha egyszerre eleget tesz ezen feltételek mindegyikének.

Geometriai értelmezés

Az MMT-nek szemléletes geometriai értelmezése van, különösen kevés változót tartalmazó feladatok esetén:

• Kétdimenziós térben (2 változó): Minden lineáris egyenlőtlenség-feltétel egy félsíkot határoz meg. Az MMT ezen félsíkok metszete — egy konvex sokszög (amely lehet nem korlátos vagy üres is).
• Háromdimenziós térben (3 változó): Minden lineáris egyenlőtlenség-feltétel egy félteret határoz meg. Az MMT ezen félterek metszete — egy konvex poliéder.
• Többdimenziós térben: A lineáris feltételekkel meghatározott MMT konvex poliéder (politóp).

Nemlineáris feltételek esetén az MMT bonyolultabb alakú lehet, és nem feltétlenül konvex.

Szerepe az optimalizálásban

A megengedett megoldások tartománya alapvető szerepet játszik az optimalizálásban:

1. A keresési tér meghatározása: A feladat optimális megoldása (ha létezik) mindig az MMT belsejében vagy határán található. Az optimalizáló algoritmusok a célfüggvény szélsőértékét éppen ebben a tartományban keresik. 2. A megoldások létezésének vizsgálata: Ha az MMT üres halmaz (azaz a feltételek ellentmondanak egymásnak), akkor a feladatnak nincs megengedett megoldása, és következésképpen optimális megoldása sem. 3. Hatás az optimális megoldásra: Az MMT alakja és mérete közvetlenül befolyásolja a célfüggvény szélsőértékének elérhetőségét és e szélsőérték nagyságát.

Az MMT tulajdonságai (lineáris programozási feladatokban)

Lineáris programozási (LP) feladatokban, ahol minden feltétel és a célfüggvény is lineáris, az MMT fontos tulajdonságokkal rendelkezik:

• Konvexitás: Ha két pont az MMT-hez tartozik, akkor az e pontokat összekötő teljes szakasz szintén az MMT-hez tartozik. Ez a tulajdonság garantálja, hogy az optimális megoldás (ha létezik és egyértelmű) az MMT poliéderének egyik csúcsán található.
• Zártság: Az MMT tartalmazza saját határait (a nem szigorú ≤, ≥ egyenlőtlenségek és az egyenlőségek miatt).

Az MMT lehet:

• Korlátos: Véges méretű.
• Nem korlátos: Egy vagy több irányban a végtelenbe terjed.
• Üres: Egyetlen pontot sem tartalmaz.

Irodalom

• Ventcel, J. Sz. Operációkutatás: feladatok, elvek, módszertan. — Moszkva: Nauka, 1988.
• Ackoff, R., Sasieni, M. Az operációkutatás alapjai. — Moszkva: Mir, 1971.
• 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
• Matematikai modell
• Feltételek
• Megengedett megoldás
• Optimális megoldás
• Célfüggvény
• Lineáris programozás
• Konvex halmaz