Az elfogadható megoldások területe
Az optimalizálás elméletében a megvalósítható tartomány , megvalósítható halmaz , keresési tér vagy megoldási tér egy optimalizálási probléma összes lehetséges pontjának (változóértékeinek) halmaza, amely kielégíti a probléma korlátait . Ezek a megszorítások tartalmazhatnak egyenlőtlenségeket , egyenlőségeket és azt a követelményt, hogy a megoldás egész szám legyen [1] [2] . A megvalósítható megoldások területe a probléma megoldására jelöltek keresésének kezdeti területe, és ez a terület a keresés során szűkíthető.
Vegyük például a feladatot
Minimalizálja
változókra vonatkozó korlátozásokkal és
és
Ebben az esetben a megvalósítható megoldások területe olyan párok halmaza ( x 1 , x 2 ), amelyeknél az x 1 értéke nem kisebb, mint 1 és nem több, mint 10, és az x 2 értéke nem kisebb, mint 5 és nem több, mint 12. Vegye figyelembe, hogy a megvalósítható megoldások halmazát a célfüggvénytől elkülönítve tekintjük, amely meghatározza az optimalizálási kritériumot, és amely a fenti példában egyenlő
Sok probléma esetén a megengedett megoldási tartomány magában foglalja azt a megkötést, hogy egy vagy több változó nem lehet negatív. A tiszta egészszámú programozás problémáiban a megvalósítható megoldások halmaza egész számokból (vagy valamilyen részhalmazból) áll. A lineáris programozási feladatokban a megvalósítható megoldások tartománya egy konvex politóp - egy többdimenziós térben lévő régió, amelynek határait hipersíkok alkotják [1] .
A kényszer-elégedettség az a folyamat, amikor egy pontot találunk a megvalósítható megoldások tartományában.
Kapcsolódó definíciók
Az egyenlőtlenségi megszorítások értelmében egy pont lehet belső pont (érvényes pont), határpont (érvényes pont), vagy külső pont (érvénytelen pont). Aktív vagy kötelező megkötés az, amely egy adott pontban egyenlőséggé változik [1] . Egyes algoritmusok használhatják az aktív kényszer fogalmát egy hatékonyabb algoritmus felépítéséhez (lásd a változó alapú módszert .
Ha egy feladathoz nem létezik érvényes pont, akkor a feladat érvénytelennek minősül .
A feltételes optimum egy lokális optimum, amely a megengedhető terület határán fekszik [1] .
A megvalósítható megoldások konvex tartománya
A megvalósítható megoldások konvex tartománya olyan megoldások halmaza, amelyben a két megvalósítható megoldást összekötő szakasz csak érvényes pontokat tartalmaz, és nem halad át egyetlen érvénytelen ponton sem. A megvalósítható megoldások konvex halmaza számos problématípusban felmerül, beleértve a lineáris programozási problémákat is, és különösen érdekes, mert ha a probléma egy konvex célfüggvény optimalizálása , akkor általában egy ilyen probléma könnyebben megoldható egy konvex célfüggvényen. konvex megoldáshalmaz, és bármely lokális optimum globális optimum is lesz .
Elfogadható megoldások hiánya
Ha az optimalizálási probléma korlátai együttesen inkonzisztensek, akkor nincs olyan pont, amely minden feltételnek eleget tesz, és akkor a megvalósítható megoldások tartománya üres . Ebben az esetben a problémának nincs megoldása, és azt mondják, hogy elfogadhatatlan [1] .
Az elfogadható megoldások korlátos és korlátlan tartományai
Az elfogadható megoldások köre lehet korlátozott vagy korlátlan . Például az { x ≥ 0, y ≥ 0} megszorítások által definiált megvalósítható megoldások halmaza korlátlan, mivel bizonyos irányokba korlátlanul lehet haladni, miközben a megvalósítható megoldások tartományában maradunk. Ezzel szemben az { x ≥ 0, y ≥ 0, x + 2 y ≤ 4} kényszerek által alkotott megvalósítható megoldások halmaza korlátos, mivel bármely irányú mozgás korlátos. Az n változós lineáris programozási feladatokban a megvalósítható megoldások tartományának korlátosságának szükséges, de nem elégséges feltétele legalább n + 1 kényszer megléte.
Ha a megvalósítható megoldások halmaza korlátlan, akkor a célfüggvény viselkedésétől függően az optimális megoldás létezhet vagy nem. Például, ha a halmazt az { x ≥ 0, y ≥ 0} megszorítások határozzák meg, akkor az x + y optimalizálási feladatnak nincs megoldása, mivel bármely jelölt javítható x vagy y növelésével , de az x + y minimalizálás . feladatnak van optimális megoldása (és mégpedig az ( x , y ) = (0, 0) pontban).