Optimointitehtävä

Optimointitehtävä on matemaattinen tehtävä, jossa etsitään muuttujien arvoja x siten, että tavoitefunktio f(x) saa parhaan mahdollisen arvon ja kaikki annetut rajoitteet toteutuvat. Tehtävä voidaan muodostaa joko minimointina tai maksimointina. Yleinen muoto on: minimoidaan f(x) subjekti rajoitteille gi(x) ≤ 0, hi(x) = 0 sekä mahdollisesti x kuuluu tiettyyn domainiin D. Tämän seurauksena määritellään kelvollinen (feasible) joukko F = { x ∈ D : gi(x) ≤ 0, hi(x) = 0 } ja halutaan löytää optimaali ratkaisu x* joko F:n sisäpuolelta tai sen reunalta.

Tyyppiluokittelut ja ominaisuudet. Optimointitehtävät jaetaan usein lineaarisiin ja ei-lineaarisiin sekä jatkuviin että diskreetteihin (integroituihin) muuttujiiin. Lineaarinen optimointi (LP) käyttää lineaarisia f, gi ja hi -funktioita; sen ominaisuuksiin kuuluu usein tehokas ratkaisumekanismi ja dualiteetti. Ei-lineaarisissa ongelmissa funktiot voivat olla monimutkaisempia, jolloin ratkaisumenetelmät kuten ei-lineaarinen ohjelmointi (NLP) ja konveksi optimointi ovat keskeisiä. Diskreettien muuttujien sisältämät ongelmat (esimerkiksi integer programming) ovat usein vaikeampia (NP-hard).

Ratkaisumenetelmät. Tarkkoja ratkaisuja voidaan hakea ε-säädöillä ja algoritmeilla kuten simplex- tai interior-point -menetelmillä LP:ssä sekä branch-and-bound - ja leikkausmenetelmillä integer-ongelmissa. Ei-lineaarisissa ongelmissa käytetään usein gradientti- tai KKT-optimaalisuusehtojen mukaista ratkaisua sekä konveksia lähestymistapoja. Epätarkkoja, mutta käytännöllisiä lähestymistapoja ovat heuristikat ja metaheuristiikat, esimerkiksi evoluutioprotokollat tai simuloitu annealing.

Sovellukset. Optimointitehtäviä käytetään laajasti esimerkiksi tuotanto- ja jakelun optimoinnissa, aikataulutuksessa, suunnittelussa, resurssien jaon ongelmissa sekä taloudessa ja insinööritieteissä. Tehtävä on keskeinen osa operaatioiden tutkimusta ja päätöksentekoprosesseja.