Оптимизациони проблем

У математици и рачунарству, оптимизациони проблем је проблем проналажења најбољег од свих могућих решења. Формално речено, оптимизациони проблем $A$ је четворка $(I,f,m,g)$, где је

• $I$ скуп инстанци;
• за дату инстанцу $x\in I$, $f(x)$ је скуп свих могућих решења;
• за дату инстанцу $x$ и могуће решење $y$ за $x$, $m(x,y)$ означава меру за $y$, која је обично позитиван реални број.
• $g$ је циљна функција, и то обично $\min$ или $\max$.

Тада је циљ за неку инстанцу $x$ пронаћи оптимално решење, то јест могуће решење $y$ за које је

$m(x,y)=g\{m(x,y')\mid y'\in f(x)\}.$

За сваки оптимизациони проблем постоји одговарајући проблем одлучивања, који поставља питање да ли постоји могуће решење за неку конкретну меру $m_{0}$. На пример, ако је дат граф $G$ који садржи чворове $u$ и $v$, оптимизациони проблем би могао да буде наћи пут од $u$ до $v$ који пролази кроз најмање грана. Одговор на овај проблем би могао да буде на пример 4. Одговарајући проблем одлучивања би био да ли постоји путања од $u$ до $v$ која пролази кроз 10 или мање грана? Одговор на овај проблем је једноставно да или не.

Види још

• Оптимизација (математика)
• Проблем одлучивања