möjlighetsmängden

Möjlighetsmängden, eller den genomförbara mängden, är i optimeringssammanhang uppsättningen av alla beslutsvärden x som uppfyller samtliga begränsningar i ett givet problem. Den definierar vad som är tillåtet när beslut ska fattas, och den beror endast på constraints, inte på målfunktionen.

Exempelvis i linjär programmering är möjlighetsmängden ofta definierad som

{ x ∈ R^n | Ax ≤ b, x ≥ 0 },

där A och b beskriver konstanterna i begränsningarna. Möjlighetsmängden kan vara tom om begränsningarna är motstridiga, eller oändlig om det finns utrymme för godtyckligt stora värden. Den kan vara mycket sammansatt och i praktiken stor eller obegränsad.

Egenskaper. Om begränsningarna är linjära (eller generellt konvexa) blir möjlighetsmängden konvex. Vid linjär programmering bildar den ofta en polyhedron, och om den är begränsad blir den en polytope. I allmänhet är mängden slutet (om varje begränsning är sluten) eller öppen beroende på hur villkoren formulerats.

Användning. Huvudfunktionen är att definiera vad som är tillåtet när man söker en optimal lösning. Målfunktionen optimeras över denna mängd, och ofta uppnås optimala lösningar vid speciella punkter av mängden (till exempel hörnpunkter i konvexa fall). I vissa problem är även lösningen helt enkelt att hitta en tex möjlighet att uppfylla alla begränsningar (feasibility problem).