Simplexmetoden

Simplexmetoden eller simplexalgoritmen är en metod inom optimeringsläran för att effektivt lösa linjärprogrammeringsproblem. Metoden uppfanns av den amerikanske matematikern George Dantzig och är i dag den i särklass mest använda algoritmen för att lösa LP-problem och som nästan helt dominerar den kommersiella marknaden.

Enligt linjärprogrammeringens fundamentalsats erhålles alltid optimum i minst en hörnpunkt till den tillåtna mängden och dessa hörn motsvaras av en (eller i det degenererade fallet flera) baslösningar. Simplexmetoden söker den bästa lösningen genom att systematisk flytta sig från en baslösning till en annan närliggande på ett sådant sätt att målfunktionsvärdet förbättras. Den söker inte igenom samtliga hörnpunkter då det även för förhållandevis "små" LP-problem finns oerhört många, men eftersom problemet är konvext kommer den hörnpunkt för vilka ingen närliggande hörnpunkt har ett bättre målfunktionsvärde att vara optimallösningen till problemet.

Basbyten

Givet en tillåten baslösning ${\displaystyle x^{0}}$ till ett LP-problem kan en sökriktning ${\displaystyle d^{0}}$ bestämmas för varje icke-basvariabel. Riktningen svarar mot att variabeln i fråga tillåts växa och övriga variblers värden erhålls ur bivillkoren för den tidigare icke-basvariabel som tillåts bli nollskild och som kallas för ingående basvariabel.

Om det tillåtna området är begränsat finns det en största steglängd ${\displaystyle t^{0}}$ för vilken den nya punkten ${\displaystyle x^{1}=x^{0}+t^{0}*d^{0}}$ är en tillåten punkt (det vill säga alla variabler ${\displaystyle \geq 0}$); den variabel som först når noll begränsar steglängden och kallas utgående basvariabel. Om ${\displaystyle d^{i}}$ och ${\displaystyle t^{i}}$ väljs på detta sätt i varje iteration kommer den nya lösningen ${\displaystyle x^{i+1}}$ att vara en tillåten baslösning. Att på detta sätt röra sig mellan olika lösningar kallas för basbyte.

Simplexmetoden itererar på samma sätt mellan tillåtna baslösningar med det tillägget att sökriktningen endast får väljas så att målfunktionen förbättras (inte sällan finns flera alternativ, det har då visat sig lämpligt att välja den riktning som snabbast förbättrar målfunktionen; man säger att den har mest reducerad kostnad^[1], det är emellertid inte garanterat att det ger den enklaste lösningen).

Eftersom målfunktionen ständigt förbättras och antalet baslösningar är ändligt (om än stort), är det säkert att simplexmetoden finner lösningen.

För att lösa ett generellt LP-problem måste det först överföras till standardform och därefter måste en tillåten baslösning identfieras.

Algoritmen

• (Försteg) Börja med en tillåten baslösning ${\displaystyle x^{0}}$ och sätt iterationsräknaren k till 0.
• (Steg 1) Beräkna reducerade kostnader för alla icke-basvariabler eventuellt genom omskrivning av målfunktionen.
• Sätt den variabel med mest reducerad kostnad till inkommande variabel. Om ingen förbättrande variabel finns är lösningen funnen.
• Beräkna sökriktning ${\displaystyle d^{k}}$ och bestäm steglängden ${\displaystyle t^{k}}$ till det största tal för vilket ${\displaystyle x^{k}+d^{k}t^{k}}$ är en tillåten lösning. (om t tillåts gå mot oändligheten har problemet obegränsad bra lösning).
• Sätt ${\displaystyle x^{k+1}=x^{k}+d^{k}t^{k}}$ och stega vidare med k := k+1 och gå till steg 1.

Exempel

Betrakta LP-problemet

Maximera ${\displaystyle z=4x_{1}+x_{2}}$

då

${\displaystyle 2x_{1}+3x_{2}\leq 6\qquad }$Bivillkor 1

${\displaystyle x_{1}\leq 2\qquad }$Bivillkor 2

${\displaystyle x_{1},\ x_{2}\geq 0}$

som kan överföras på standarform genom introduktion av slackvariablerna ${\displaystyle a_{1}}$ och ${\displaystyle a_{2}}$ enligt

Maximera ${\displaystyle z=4x_{1}+x_{2}}$

då

${\displaystyle 2x_{1}+3x_{2}+a_{1}=6}$

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

${\displaystyle x_{1},\ x_{2},\ a_{1},\ a_{2}\geq 0}$

Vi kan enkelt identifiera ur figuren att ${\displaystyle x_{1}=x_{2}=0}$ är en tillåten lösning som ger upphov till ekvationssystemet

${\displaystyle 0+0+a_{1}=6\,}$

${\displaystyle 0+a_{2}=2\,}$

vilket ger upphov till baslösningen där ${\displaystyle a_{1},\ a_{2}}$ är basvariabler lika med 6 respektive 2 och ${\displaystyle x_{1},\ x_{2}}$ är icke basvariabler ( = 0).

Ur målfunktionen kan vi utläsa att en ökning av ${\displaystyle x_{1}}$ innebär en ökning av z med 4 enheter samt att motsvarande värde för ${\displaystyle x_{2}}$ är ett (de reducerade kostnaderna är 4 respektive 1). Eftersom båda icke-basvariabler ger förbättrande sökrikningar väljs den snabbaste förbättringen och således väljs ${\displaystyle x_{1}}$ som inkommande basvariabel.

Ur omskrivningen av bivillkoren erhålles

${\displaystyle a_{1}=6-2x_{1}-3x_{2}}$

${\displaystyle a_{2}=2-x_{1}}$

Vilket motsvarar en sökriktning längs ${\displaystyle x_{1}}$, ${\displaystyle d^{0}}$ = [1 0 -2 -1]

och vi ser att ${\displaystyle a_{2}}$ först kommer att nå noll när ${\displaystyle x_{1}}$ ökar (detta sker för ${\displaystyle x_{1}=2}$ så ${\displaystyle t^{0}=2}$) det vill säga att ${\displaystyle a_{2}}$ blir utgående basvariabel och vår nya baslösning blir att ${\displaystyle a_{1},\ x_{1}}$ är basvariabler lika med 4 respektive 2 och att ${\displaystyle a_{2},\ x_{2}}$ är icke-basvariabler ( = 0).

Inför nästa iteration måste målfunktionen uttryckas i icke-basvariabler (så att vi kan se hur de påverkar) , vilket görs med hjälp av ekvationerna i bivillkoren.

${\displaystyle z=8-4a_{2}+x_{2}}$

Här erhålles att ${\displaystyle x_{2}}$ genererar en förbättrande riktning medan ${\displaystyle a_{2}}$ inte gör det. Vi kan också se att optimallösningen kommer att vara minst 8 eftersom det är en konstantterm i målfunktionen, vilket i sig inte är ett viktigt resultat men bra för senare kontroll.

Proceduren upprepas och vi når i ${\displaystyle x_{1}=2}$, ${\displaystyle x_{2}=2/3}$, ${\displaystyle a_{1}=a_{2}=0}$ och en omskrivning av målfunktion ger

${\displaystyle z=8-4a_{2}-a_{1}/3}$

Här kan ingen förbättrande sökriktning hittas (om ${\displaystyle a_{1}}$ eller ${\displaystyle a_{2}}$ ökar minskar z), vilket innebär att baslösningen är optimalösningen och att funktionsvärdet är 8,667.

Källor

• Lundgren, Jan & Rönnqvist, Mikael & Värbrand Peter: Optimeringslära, 2003, upplaga 3:1. ISBN 978-91-44-05314-1.

Noter