lineaariohjelmoinnin

Lineaariohjelmointi on optimointimuoto, jossa etsitään päätösmuuttujien arvoja, jotka maksimoivat tai minimoivat lineaarisen tavoitefunktion rajoitteiden puitteissa. Päätösmuuttujat ovat yleensä ei-negatiivisia, ja ne voivat kuvata esimerkiksi tuotantomääriä, kuljetettavaa määrää tai muita resursseja. Tavoite ja rajoitteet muodostuvat lineaarisista suhteista.

Standardimuodossa ongelma esitetään usein seuraavasti: maksimoida c^T x tai minimoida c^T x niin, että Ax ≤ b ja x ≥ 0, missä x on päätösmuuttujien vektori, A on rajoitteiden matriisi ja b oikea puoli. Rajoitteet voivat olla ≤, = tai ≥, ja ongelman voi muuntaa standardimuotoon tarvittaessa.

Geometrisesti ratkaisu sijaitsee rajatun alueen kulmapisteessä useimmiten, ja optimaalinen arvo saavutetaan näissä pisteissä. Lineaariohjelmoinnilla on sekä primääri- että duali-ongelmat; vahva dualiteetti toteaa, että optima primäärissä ja dualissa ovat yhtä suuria, kun ratkaisut ovat kelvollisia.

Menetelmät: klassinen Simplex-algoritmi liikuttaa ratkaisua kulmista toiseen kohti optimaalista pistettä. Nykyään käytetään yleisesti sisäpäinmenetelmiä (interior-point), jotka toimivat hyvin suurissa ongelmissa ja joille on kehitetty tehokkaita toteutuksia. Numeriset ongelmat voivat olla degeneroituneita tai epärealistisia, mikä vaatii huolellista numeerista käsittelyä.

Sovelluksia ovat tuotanto- ja toimitusketjun suunnittelu, kuljetus- ja jakelutehtävät, ruokavalio- ja portfolion optimointi sekä monet muut operatiivisen päätöksenteon ongelmat. Mikäli muuttujien on oltava kokonaislukuja, kyseessä on integer linear programming.

Historia: Lineaariohjelmointi kehittyi 1940- ja 1950-luvuilla, ja George Dantzigin kehittämä Simplex-algoritmi julkaistiin 1957.