Optimizacioni problem

U matematici i računarstvu, optimizacioni problem je problem pronalaženja najboljeg od svih mogućih rešenja. Formalno rečeno, optimizacioni problem $A$ je četvorka $(I,f,m,g)$, gde je

• $I$ skup instanci;
• za datu instancu $x\in I$, $f(x)$ je skup svih mogućih rešenja;
• za datu instancu $x$ i moguće rešenje $y$ za $x$, $m(x,y)$ označava meru za $y$, koja je obično pozitivan realni broj.
• $g$ je ciljna funkcija, i to obično $\min$ ili $\max$.

Tada je cilj za neku instancu $x$ pronaći optimalno rešenje, to jest moguće rešenje $y$ za koje je

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

Za svaki optimizacioni problem postoji odgovarajući problem odlučivanja, koji postavlja pitanje da li postoji moguće rešenje za neku konkretnu meru $m_{0}$. Na primer, ako je dat graf $G$ koji sadrži čvorove $u$ i $v$, optimizacioni problem bi mogao da bude naći put od $u$ do $v$ koji prolazi kroz najmanje grana. Odgovor na ovaj problem bi mogao da bude na primer 4. Odgovarajući problem odlučivanja bi bio da li postoji putanja od $u$ do $v$ koja prolazi kroz 10 ili manje grana? Odgovor na ovaj problem je jednostavno da ili ne.

Vidi još

• Optimizacija (matematika)
• Problem odlučivanja