Optimeerimisprobleemide

Optimeerimisprobleemide uurimine keskendub parima lahenduse leidmisele kindlate eesmärkide ja piirangute all. Need probleemid võivad olla nii pidevate kui ka diskreetsete muutujate küsimus ning neid esitatakse tavaliselt kui otsustusprobleeme, mille objektifunktsioon tuleb maksimeerida või minimoida.

Formaalne mudel sisaldab otsustusmuutujaid x, eesmärkfunktsiooni f(x) ning piiranguid Ax ≤ b ja x ≥ 0. Kui muutujaid on pidevad, võivad probleemid olla lineaar- või mitte-lineaarsed; kui muutujaid on diskreetseid, on tegemist täisarvuliste või kombineeritud optimeerimisega. Mõned probleemid on polünoomiliselt lahendatavad (nt lineaarprogrammeerimine), teised on NP-hard või NP-kõrgendatud klassi kuuluvad.

Lahendusmeetodid jagunevad täpseteks ja heuristilisteks. Täpsed meetodid hõlmavad lineaar- ja integer programmingu lahendust (nt simplex, interior-point, branch-and-bound), samas kui heuristikad ja metaheuristikad (nt tabu otsing, simuleeritud annealing, geneetilised algoritmid) võimaldavad leida head lahendused suurtele probleemidele.

Optimeerimisprobleemidel on lai rakendusvaldkond: logistika ja tootmine, energiavarustus, transport, telekommunikatsioon ja rahanduse portfellihaldus. Klassikalised näited hõlmavad knapsack-probleemi, traveling salesman probleemi (TSP) ja vehicle routing probleemi (VRP). Nende lahendused aitavad tõsta efektiivsust, vähendada kulusid ja parandada otsuste kvaliteeti.