optimeringsproblem

Et optimeringsproblem er en matematisk problemstilling der målet er å finne beslutningsvariabler som gir den beste verdien av en objektiv funksjon, gitt visse begrensninger. Løsningen må ligge innenfor en tillatt mengde kalt mulighetsområdet. Objektivfunksjonen kan enten minimeres eller maksimeres, og begrensningene kan være likninger eller ulikheter som må oppfylles. Den resulterende mengden av løsninger kalles mulighetsområdet.

Vanlige typer inkluderer lineære optimeringsproblemer (LP), ikke-lineære optimeringsproblemer (NLP), konvekse optimeringsproblemer, og heltallsproblemer der noen variabler må være heltall. Enkeltmål og multiobjektive problemstillinger finnes også, ofte ved bruk av Pareto-optimalitet og søken etter løsninger som balanserer flere mål.

Metoder inkluderer eksakte metoder og heuristikker. For lineære problemstillinger brukes ofte simplexmetoden eller interior-point-metoder. Heltallsproblemer håndteres med branch-and-bound, kutting-plane-metoder og andre kombinatoriske metoder. Ikke-lineære optimeringsproblemer kan løses med gradientbaserte metoder, Newtons metode eller sekvensiell kvadratisk programmering. Det finnes også heuristiske og metaheuristiske tilnærminger som genetiske algoritmer, simulert annealing og tabu-søk, samt dynamisk programmering i spesifikke problemklasser.

Anvendelser spenner fra logistikk og produksjon til energi, transport, finans og ingeniørfag. Et enkelt eksempel er å minimere kostnaden c^T x under begrensningene Ax ≤ b og x ≥ 0, der løsningen velger hvor mye av hver aktivitet man bør gjøre for å holde kostnaden lavest mulig.