oplossingsgebied

In wiskundige optimalisatie verwijst het oplossingsgebied, ook wel de feasible set genoemd, naar de verzameling van alle mogelijke waarden voor de besluitvariabelen die voldoen aan alle beperkingen van het probleem. Het oplossingsgebied beschrijft dus het domein waarin een oplossing mogelijk is en is onafhankelijk van de gekozen doelstelling.

Bij lineaire programmering bestaan de beperkingen uit lineaire ongelijkheden en gelijkheden, waardoor het oplossingsgebied een convexe polyedron (of polytope) in de variabelenruimte is. Als de variabelen daarnaast niet-negatief moeten zijn, verkrijgt men een begrensde variant daarvan. In algemene zin kan het oplossingsgebied ook onbegrensd zijn.

Als er geen punt bestaat dat aan alle beperkingen voldoet, is het oplossingsgebied leeg en is het probleem infeasibel.

Het oplossingsgebied zelf bevat geen informatie over de doelstelling. De doelstelling bepaalt welk punt in het oplossingsgebied optimaal is, bijvoorbeeld bij het minimaliseren of maximaliseren van een kosten- of winstfunctie.

Afhankelijk van de aard van de variabelen kan het oplossingsgebied continu zijn (alle reële waarden) of discrete punten bevatten (bij integer- of combinatoriële variabelen). In lineaire en continue varianten is het oplossingsgebied convex, wat de toepasbaarheid van efficiënte algoritmen vergemakkelijkt.

Berekeningen en algoritmen richten zich op het vinden van een optimale oplossing binnen het oplossingsgebied. Voorbeelden zijn de simplex-methode en interior-point methoden bij continue problemen, en branch-and-bound bij discrete problemen. Een typisch LP-snippet is: maximize c^T x onder Ax ≤ b, x ≥ 0, waarbij het oplossingsgebied {x ≥ 0 | Ax ≤ b} de feasible set vormt.