optimaliseringsproblemer

Optimaliseringsproblemer er matematisk modellering av beslutninger der målet er å finne de beste verdiene for beslutningsvariabler under gitte begrensninger. En typisk modell består av en målfunksjon som skal maksimeres eller minimeres, et sett av variabler og en gruppe begrensninger som definerer et mulighetsrom. Løsningen er den variabelkombinasjonen som gir optimale resultater innenfor de tillatte rammer. For ikke-konvekse problemer skiller man ofte mellom globale og lokale optimum.

Kategorier: Lineære problemer har lineær målfunksjon og lineære begrensninger. Ikke-lineære problemer kan være kontinuerlige eller diskrete. Blandede problemstillinger involverer både kontinuerlige og heltallsvariabler. Det finnes deterministiske varianter og stokastiske eller robuste varianter som tar høyde for usikkerhet. Vanlige modeller inkluderer lineær programmering, heltallsprogrammering og blandede heltallsprogrammeringer, samt ikke-lineære og konvekse problemer. Eksempler på praktiske problemer er knapsack, transport og ruteplanlegging, samt produksjonsplanlegging.

Løsningsstrategier: For lineære og konvekse problemer finnes effektive metoder som Simplex og innsidepunktmetoder. Heltalls- og blandede heltallsproblemer krever ofte grentest-og-begrensning (branch-and-bound) eller kuttegrense-teknikker, eventuelt heuristikker eller metaheuristikker ved store eller komplekse tilfeller. Stokastiske problemer bruker scenarioanalyse, scenario-programmering eller robust optimering.

Anvendelser: logistikk, produksjon, energisystemer, finans og telekommunikasjon. Mange optimaliseringsproblemer er NP-harde i generell form, men spesialtilfeller og moderne algoritmer gir ofte praktiske løsninger i industrien.