Området för tillåtna lösningar

Området för tillåtna lösningar (även mängden av tillåtna lösningar, eng. Feasible region, feasible set) — inom operationsanalys, optimering och matematisk modellering är detta mängden av alla möjliga lösningar (uppsättningar av variabelvärden) som uppfyller alla begränsningar som imposed på problemet.

Området för tillåtna lösningar utgör det underrum inom vilket sökningen efter den optimala lösningen sker. Varje lösning som befinner sig utanför detta område är otillåten.

Definition och bildning

Området för tillåtna lösningar bildas som snittet av de mängder som definieras av varje enskild begränsning i problemet. Begränsningarna kan ges i form av:

• Olikheter: Fastställer övre eller nedre gränser för variablernas värden eller deras kombinationer (t.ex. "förbrukningen av resurs A får inte överstiga 100 enheter", "antalet producerade varor måste vara minst 50 stycken").
• Likheter: Kräver att ett villkor uppfylls exakt (t.ex. "den totala transportvolymen ska vara lika med 1000 ton", "balansen mellan inkommande och utgående flöden är noll").
• Villkor på variablernas tecken: Ofta måste variablerna vara icke-negativa, heltalsvärda eller tillhöra en viss diskret mängd.

En punkt (eller en vektor av variabelvärden) tillhör området för tillåtna lösningar om och endast om den samtidigt uppfyller alla dessa begränsningar.

Geometrisk tolkning

Området för tillåtna lösningar har ofta en åskådlig geometrisk tolkning, särskilt i problem med ett litet antal variabler:

• I tvådimensionellt rum (2 variabler): Varje linjär olikhetsbegränsning definierar ett halvplan. Området för tillåtna lösningar utgörs av snittet av dessa halvplan — en konvex polygon (möjligen obegränsad eller tom).
• I tredimensionellt rum (3 variabler): Varje linjär olikhetsbegränsning definierar ett halvrum. Området för tillåtna lösningar är snittet av dessa halvrum — en konvex polyeder.
• I flerdimensionellt rum: Området för tillåtna lösningar, definierat av linjära begränsningar, är en konvex polyeder (polytop).

Vid icke-linjära begränsningar kan området för tillåtna lösningar ha en mer komplex form och vara icke-konvext.

Rollen i optimering

Området för tillåtna lösningar spelar en grundläggande roll inom optimering:

1. Definition av sökrummet: Den optimala lösningen till problemet (om den existerar) befinner sig alltid inuti området för tillåtna lösningar eller på dess rand. Optimeringsalgoritmer söker extremvärdet för målfunktionen just inom detta område. 2. Kontroll av lösningarnas existens: Om området för tillåtna lösningar är en tom mängd (dvs. begränsningarna motsäger varandra) har problemet inga tillåtna lösningar och följaktligen heller ingen optimal lösning. 3. Påverkan på den optimala lösningen: Formen och storleken på området för tillåtna lösningar påverkar direkt möjligheten att uppnå extremvärdet för målfunktionen och värdet av detta extremum.

Egenskaper hos området för tillåtna lösningar (i linjärprogrammeringsproblem)

I linjärprogrammeringsproblem (LP), där alla begränsningar och målfunktionen är linjära, har området för tillåtna lösningar viktiga egenskaper:

• Konvexitet: Om två punkter tillhör området för tillåtna lösningar, tillhör även hela linjestycket som förbinder dessa punkter området. Denna egenskap garanterar att den optimala lösningen (om den existerar och är unik) befinner sig i ett av hörnen på polyedern som utgör området för tillåtna lösningar.
• Slutenhet: Området för tillåtna lösningar inkluderar sina ränder (på grund av icke-strikta olikheter ≤, ≥ och likheter).

Området för tillåtna lösningar kan vara:

• Begränsat: Har ändliga dimensioner.
• Obegränsat: Sträcker sig oändligt i en eller flera riktningar.
• Tomt: Innehåller inte en enda punkt.

Litteratur

• Ventzel E. S. Operationsanalys: problem, principer, metodologi. — Moskva: Nauka, 1988.
• Akof R., Sasieni M. Grunderna i operationsanalys. — Moskva: 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)

Se även

• Operationsanalys
• Optimering
• Matematisk modell
• Begränsningar
• Tillåten lösning
• Optimal lösning
• Målfunktion
• Linjär programmering
• Konvex mängd