optimeringsopgave

En optimeringsopgave er en matematisk problemstilling, hvor målet er at finde værdier for ukendte variabler, der enten minimerer eller maksimerer en målfunktion, under givne begrænsninger. Formålet er at finde den bedste eller mest effektive løsning inden for rammerne af problemet.

Problemerne kan opdeles efter struktur og egenskaber i lineære og ikke-lineære, kontinuerte og diskrete, samt enkeltmålede eller multi-mål (multikriterie) optimering. De kan være deterministiske eller stokastiske og konvekse eller ikke-konvekse.

En typisk opgave består af beslutningsvariable, en målfunktion og et sæt begrænsninger. Den del af løsningsområdet, der opfylder begrænsningerne, kaldes den feasible region.

Løsningsmetoderne opdeles ofte i eksakte metoder og heuristikker. Eksakte metoder søger sikre globale optima og inkluderer lineær programmering, heltalsprogrammering, gren-og-bund (branch-and-bound) og cutting-plane-metoder. For ikke-lineære eller ikke-konvekse problemer kan man anvende global eller lokal optimering gennem metoder som konveks optimering, interior-point-teknikker og dynamisk programmering.

Heuristiske og metaheuristiske metoder bruges når problemet er for stort eller komplekst til eksakte løsninger. Eksempler: genetiske algoritmer, simuleret annealing, tabu-søgning og partikel-sværmsoptimering.

Dualitet og konveksitet spiller ofte en rolle: for konvekse kontinuerte problemer giver stærk dualitet og KKT-betingelser ofte nødvendige og tilstrækkelige betingelser for optimalitet. Anvendelser omfatter logistik, produktion, netværk, energi og finansielt porteføljevalg. Et simpelt eksempel er et transportproblem, der minimerer samlede omkostninger under efterspørgsels- og kapacitetsbegrænsninger.