Lineaarprogrammeerimine

Lineaarprogrammimine on optimeerimise haru, mis tegeleb lineaarsete eesmärkide maksimeerimise või minimeerimisega ning kus otsused kirjeldatakse lineaarsete piirangute kaudu. Lahendused on reeglina pidevad, kui otsuste suhted ja piirangud on lineaarsed.

Standardvorm: maksimeeri z = c^T x, tingimused Ax ≤ b ja x ≥ 0. A on m×n, b ∈ R^m ja c ∈ R^n. Lahenduste kogum ehk sobivusruum on konveksne polütoop, mis määrab kõigi lubatud otsuste kombinatsioonide väärtused.

Dual: iga lineaarprogrammil on kaasas vastav dual. Primaarne probleem on maksimeerida z = c^T x subject to Ax ≤ b, x ≥ 0; dualne probleem on minimaalseerib b^T y subject to A^T y ≥ c, y ≥ 0. Kui vähemalt üks lahend on rahuldav ja lahendus on bounded, kehtib tugev dualiteet.

Algoritmid: kõige laialdasemalt kasutatav meetod on lihtneiksus (simpleks), mis liigub piiratud lahenduspunktide vahel ja parandab eesmärkväärtust, kuni optimaalne lahend leitakse. Õhukesi meetodeid pakuvad sisemise punkti meetodid (näiteks Karmarkari meetod), mis töötavad hästi suurte probleemide puhul ning võivad pakkuda skaleeritavust ja numerilisi eeliseid.

Rakendused hõlmavad tootmis- ja tarneahela planeerimist, transporti ja logistikat, võrguoptimeerimist, energia ja ressursihalduse ning finantsportfellide optimeerimist. Lineaarprogrammimine eeldab pidevaid muutujad ja lineaarsed seosed; kui probleem on mitte-lineaarne, tuleb kasutada teisi meetodeid või lineaariseerida mudel. Ajalugu: George Dantzig tutvustas lihtsaiksust 1947. aastal, mille järel teised meetodid ja dualiteedi teooria on oluliselt arenenud.