Lineaariohjelmointi

Lineaariohjelmointi on optimointimuoto, jossa sekä tavoitefunktio että rajoitteet ovat lineaarisia. Tavoitteena on maksimoida tai minimoida lineaarinen arvo päätösvälin x suhteen, ja päätökset sekä resurssit kuvataan matriisien ja vektoreiden avulla. Muuttujat ovat yleisesti ei-negatiivisia.

Yleinen matemaattinen muoto on maksimoida c^T x s.t. Ax ≤ b ja x ≥ 0, missä c ∈ R^n, A ∈ R^{m×n} ja b ∈ R^m. Joissakin tapauksissa rajoitteisiin sisältyvät myös yhtäläisyydet, jotka voidaan muuntaa epäyhtälöiksi lisämuuttujien avulla.

Lineaariohj. ominaisuuksia ovat muun muassa dualisuus: jokaiselle primaariohjelmalle on muodostettavissa vastaava duali-ongelma, ja vahva dualiteetti pätee tyypillisesti. Tämä mahdollistaa tulosten tulkinnan, herkkyysanalyysin ja eri rajoitteiden vaikuttavuuden arvioinnin.

Ratkaisumenetelmät jakautuvat perinteiseen simplex-menetelmään sekä nykyaikaisempiin sisärajamenetelmiin ja muihin tehokkaisiin algoritmeihin. Käytännössä lineaariohjelmia ratkaistaan erilaisten ohjelmisto- ja kirjastopakettien avulla.

Sovelluskohteita ovat esimerkiksi tuotannon suunnittelu, toimitusketjun optimointi, kustannusten minimointi, ruokavalio- ja ravitsemusmallit sekä verkko- ja rahoitusmallit. Historian merkkipaalu on Dantzigin kehittelemä simplex-menetelmä vuonna 1947.

---