optimointiongelmaa

Optimointiongelma on matemaattinen ongelma, jossa etsitään parasta mahdollista ratkaisua annettujen kriteerien ja rajoitteiden puitteissa. Tavoitteena on usein minimoida kustannukset tai maksimoida hyöty tai suorituskyky, ja ratkaisu määritellään muuttujien arvoilla, jotka toteuttavat annetut rajoitteet.

Formaali kuvaus: Minimoi tai maksimoi objektiivinen funktio f(x) tason x ∈ D puitteissa, missä D on päätösmuuttujien sallima alue rajoitteineen. Rajoitteet voivat olla suoria ehtoja (esimerkiksi Ax ≤ b, x ≥ 0) tai yleisemmistä epälineaarisista ehdoista koostuvia. Esimerkki lineaarinen optimointi: minimoida c^T x s.t. Ax ≤ b, x ≥ 0. Integroitu optimointi tarkoittaa, että muuttujat ovat kokonaislukuja: x ∈ Z^n.

Luokat: lineaarinen optimointi (LP), ei-lineaarinen optimointi (NLP), kokonaislukuoptimointi (IP) sekä näiden yhdistelmät. Konveksissa ongelmissa on tavallisesti yksittäinen globaali ratkaisu; ei-konveksit ongelmat voivat sisältää useita paikallisia optima ja ovat yleisesti ratkaisuvaikeampia.

Menetelmät: Tarkat menetelmät LP:lle ovat yksinkertaisen ohjelman (simplex) ja interior-point -menetelmät. NLP:ssä käytetään gradientti- ja Newtonpohjaisia menetelmiä sekä sovellettuja konveksisuus- tai ei-konveksisuuslajeja. Kokonaislukumenetelmät kuten branch-and-bound ja branch-and-cut. Lisäksi heuristiset menetelmät, kuten geneettiset algoritmit, simuloitu jäähdytys ja paikallinen haku, voivat tuottaa hyviä ratkaisuja suurissa ongelmissa. Usein käytetään myös yhdistelmiä menetelmiä ja heuristiikkoja.

Sovelluksia esiintyy monilla aloilla: logistiikassa ja tuotannossa (reitin suunnittelu ja aikataulutus), taloudessa ja rahoituksessa (portfolion optimointi), energiassa sekä verkosto- ja suunnitteluprojekteissa sekä koneoppimisessa (hyperparametrien optimointi). Yksinkertainen esimerkki on knapsack-ongelma.