Optimaliseringsprobleem

In de wiskunde en de informatica is een optimaliseringsprobleem het probleem van het vinden van de beste oplossing uit alle haalbare oplossingen. Optimaliseringsproblemen kunnen worden onderverdeeld in twee categorieën naargelang de variabelen continu of discreet zijn. Een optimaliseringsprobleem met discrete variabelen staat bekend als een combinatorisch optimaliseringsprobleem. In een combinatorisch optimaliseringsprobleem zijn wij op zoek naar een object, zoals een geheel getal, permutatie of grafiek uit een eindige (of eventueel aftelbaar oneindige) verzameling.

Continu optimaliseringsprobleem

De standaardvorm van een (continu) optimaliseringsprobleem is

${\begin{aligned}&{\underset {x}{\operatorname {minimaliseer} }}&&f(x)\\&\operatorname {m.b.t.} &&g_{i}(x)\leq 0,\quad i=1,\dots ,m\\&&&h_{i}(x)=0,\quad i=1,\dots ,p\end{aligned}}$

waar

• $f(x):\mathbb {R} ^{n}\to \mathbb {R}$ de objectieve functie is, die over de variabele $x$ dient te worden geminimaliseerd,
• $g_{i}(x)\leq 0$, de ongelijkheidsrestricties worden genoemd en
• $h_{i}(x)=0$, de gelijkheidsrestricties worden genoemd.

Volgens afspraak definieert de standaardvorm een minimalisatieprobleem. Een maximalisatieprobleem kan worden behandeld door de objectieve functie te ontkennen.

Zie ook

• Wiskundige optimalisatie
• Beslissingsprobleem