Linjärprogrammering

Den här artikeln behöver källhänvisningar för att kunna verifieras. (2022-12) Åtgärda genom att lägga till pålitliga källor (gärna som fotnoter). Uppgifter utan källhänvisning kan ifrågasättas och tas bort utan att det behöver diskuteras på diskussionssidan.

LP-problem; Linjärprogrammeringsproblem är en typ av optimeringsproblem med den egenskapen att målfunktionen och samtliga bivillkor är linjära funktioner. LP-problemen betraktas inom optimeringsläran som förhållandevis lätta även om de i praktiska tillämpningar endast i sällsynta fall kan lösas utan datorstöd (då till exempel med hjälp av simplexmetoden)

Det generella LP-problemet kan skrivas som:

${\displaystyle {\mbox{minimera}}\qquad z=\sum _{j=i}^{n}c_{j}x_{j}}$

Under bivillkoren:

${\displaystyle \left\{{\begin{matrix}a_{1,1}x_{1}+a_{1,2}x_{2}+\cdots +a_{1,n}x_{n}\leq b_{1}\\a_{2,1}x_{1}+a_{2,2}x_{2}+\cdots +a_{2,n}x_{n}\leq b_{2}\\\vdots \\a_{m,1}x_{1}+a_{m,2}x_{2}+\cdots +a_{m,n}x_{n}\leq b_{m}\end{matrix}}\right.}$

Där z är målfunktionen som ska optimeras, variablerna ${\displaystyle x_{j}}$ är de n-stycken beslut som ska fattas så att olikheterna är uppfyllda och ${\displaystyle c_{j}}$ är kostnaderna för varje beslut. Bivillkoren kan skrivas kompaktare som:

${\displaystyle \sum _{j=1}^{n}a_{i,j}x_{j}\leq b_{i},\quad i=1,...,m}$

eller på matrisform; låt A vara m × n-matrisen med elementet ${\displaystyle a_{k,l}}$ på rad k, kolonn l, låt ${\displaystyle \mathbf {x} =(x_{1},x_{2},...x_{n})}$ och ${\displaystyle \mathbf {b} =(b_{1},b_{2},...,b_{n})}$, då alla bivillkoren ovan kan uttryckas som att

${\displaystyle A\mathbf {x} \leq \mathbf {b} .}$

Standardform

Standardformen för ett LP-problem är en omskrivning av problemet så att samtliga variabler är icke-negativa samt att samtliga bivillkor formulerats som likhetsvillkor. Det sistnämnda kan uppnås genom att icke-negativa slackvariabler introduceras i samtliga olikhetsvillkor där slackvariabeln utjämnar likheten.

Exempelvis kan olikheten:

${\displaystyle x_{1}+x_{2}\leq 5}$

skrivas som:

${\displaystyle x_{1}+x_{2}+a_{1}=5}$

där ${\displaystyle a_{1}}$ är en icke-negativ slackvariabel som kan betraktas som kvarvarande frihet.

Icke-negativitet för alla variabler uppnås genom variabelbyte då variabler ${\displaystyle x_{1}\leq 0}$ ersätts med ${\displaystyle y_{1}=-x_{1}}$ och fria (icke-teckenbegränsade) variabler delas i två variabler dvs. ${\displaystyle x_{1}=y_{1}-y_{2}}$ där ${\displaystyle y_{1}}$ kommer att vara noll när ${\displaystyle x_{1}\leq 0}$ och ${\displaystyle y_{2}}$ kommer att vara noll när ${\displaystyle x_{1}\geq 0}$. Båda de nya variablerna är dock icke-negativa emedan ${\displaystyle x_{1}}$ var fri.

Omskrivning på standardform innebär inte sällan att antalet variabler ökar betydligt vilket givetvis kan försvåra beräkningarna men då LP-problem i praktiska sammanhang nästan uteslutande löses med datorstöd är detta ett litet pris att betala för att kunna använda generella algoritmer som till exempel simplexmetoden.

Baslösning

Baslösningar är ett sätt att vid lösningen av LP-problem beskriva extremlösningar (hörnpunkter i definitionsmängden). Baslösningar används bl.a. av simplexmetoden för att systematiskt avsöka extrempunkterna.

För ett LP-problem skrivit på standardform kan alla lösningar tecknas som en vektor av problemets samtliga variabler (även slackvariabler).

Ur ett ekvationssystem (här på matrisform A är en n*m-matris) Ax = b erhålles en baslösning om n-m variabler sätts till 0 och det kvarvarande ekvationssystemet löses.

Här kallas de variabler som löses ut för basvariabler och då de entydigt bestämmer hörnpunkten, övriga variabler (som är noll) kallas icke-basvariabler eller ibland nollvariabler.

Speciellt är en baslösning där alla element i vektorn är icke-negativa en tillåten baslösning dvs. den uppfyller bivillkoren för LP-problemet.

En baslösning är degenererad om någon av basvariablerna beräknats till noll dvs. om andra variabler kunde väljas som icke-basvariabler och ändå generera samma hörnpunkt.

Egenskaper

Det tillåtna området (de punkter: (${\displaystyle x_{1},\;x_{2},\;...\;x_{n}}$) som satsiferar samtliga bivillkor) till ett LP-problem kommer alltid vara en konvex mängd. Denna egenskap följer direkt av att bivillkoren är linjära.

Denna egenskap tillsammans med målfunktionens linjäritet medför att lokala optima även är globala och leder fram till Linjärprogrammeringens fundamentalsats.