Lineær programmering

Lineær programmering (LP eller lineær optimalisering) er ein matematisk metode for å avgjere den beste (minste ressurskrevjande) metoden i ein matematisk modell. Lineær programmering er eit spesialtilfelle av matematisk programmering.

Meir formelt er lineær programmering ein teknikk for optimalisering av ein lineær objektiv funksjon, som er underlagt vilkåra lineær likskap og lineær ulikskap.

Lineær programmering er problem som kan uttrykkast på kanonisk form:

${\begin{aligned}&{\text{maksimer}}&&\mathbf {c} ^{\mathrm {T} }\mathbf {x} \\&{\text{for}}&&A\mathbf {x} \leq \mathbf {b} \\&{\text{og}}&&\mathbf {x} \geq \mathbf {0} \end{aligned}}$

der x representerer variabelvektoren (som skal finnast), c og b er vektorar av (kjende) koeffisientar og A er ei (kjend) matrise av koeffisientar.

Lineær programmering vert nytta innan mange fagfelt, men mest vidstrekt i økonomi og ein del i ingeniørvitskap. Industriar som nyttar lineær programmering omfattar transport, energi, telekommunikasjon og produksjon.

Kjelder

• Denne artikkelen bygger på «Linear programming» frå Wikipedia på engelsk, den 12. januar 2012.