Optimeerimisprobleemid

Optimeerimisprobleemid on ülesanded, kus tuleb leida parim võimalik lahendus piiratud võimaluste hulgast. Eesmärk võib olla maksimeerida kasumit, minimeerida kulu, vähendada aega või suurendada efektiivsust. Iga probleem mudeldatakse otsustamismuutujate x kaudu ning sellel on objektiivfunktsioon f(x) ja piirangud g_i(x) ≤ b_i (või mõnikord võrranded). Lubatud lahenduste kogum moodustab lahenduste ruumi; parim lahendus rahuldab piirangud ja optimeerib eesmärki.

Tüübid: Lineaarprogrammeerimine (LP) — objektiv ja piirangud on lineaarvõrrandite või -võrrandite süsteem; Mitte-lineaarne programmeerimine (NLP); Täisarvuline optimeerimine (IP) ja MILP; Kombinatoorne optimeerimine; Stohhastiline optimeerimine; Dünaamiline optimeerimine.

Lahendused: Täpseid lahendusi pakuvad meetodid nagu lihtsaks LP puhul ning branch-and-bound ja lõikamisvõtted IP/MILP korral; samuti dünaamilised ja stohastilised meetodid. Ligikaudseid lahendusi annavad heuristikad ja metaheuristikad (nt geneetilised algoritmid, simuleeritud annealing, tabu-otsing).

Rakendused hõlmavad transporti ja logistikat, tootmisplaneerimist, tööjaotust, ajastamist, portfooliooptimeerimist ning võrkude ja energiainfrastruktuuri disaini.

Keerukus: Paljud optimeerimisprobleemid on NP-kõrged või NP-hard ning universaalset kiiret lahendust ei ole olemas.

Ajalugu: Optimeerimisprobleemide teooria on keskne osa operatsioonide uuringutest (OR) 20. sajandil ning seda on edasi arendanud matemaatika ja inseneriteadused.