Från Rilpedia

Du har inte behörighet att redigera denna sida, av följande anledning:

Du kan se och kopiera denna sidas källtext:

<noinclude>{{rpsv.from.wpsv}}</noinclude>'''Simplexmetoden''' eller '''simplexalgoritmen''' är en metod inom [[optimeringslära]]n för att effektivt lösa [[LP-problem|linjärprogrammeringsproblem]]. Metoden uppfanns av den amerikanske [[matematiker]]n [[George Dantzig]] och är i dag den i särklass mest använda algoritmen för att lösa LP-problem 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 flera i det degenererade fallet) [[baslösning]](ar). 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 [[baslösning|tillåten baslösning]] <math> x^0 </math> till ett LP-problem kan en [[söriktning]] <math> d^0 </math> bestämmas för varje icke-basvariabler. Riktningen svarar mot att variabeln i fråga tillåts växa och övriga variblers värden erhålls ur bivillkoren den tidigare icke-basvariabel som tillåts bli nollskild kallas för '''ingående basvariabel'''. Om det tillåtna området är begränsad finns det en största steglängd <math> t^0 </math> för vilken den nya punkten <math> x^1 = x^0 + t^0 * d^0 </math> är en tillåten punkt (dvs alla variabler <math> \ge 0 </math>) den variabel som först når noll begränsar steglängden och kallas '''utgående basvariabel'''. Om <math> d^i </math> och <math> t^i </math> väljs på detta sätt i varje iteration kommer den nya lösningen <math> x^{i+1} </math> att vara en tillåten baslösning Att på detta sätt röra sig mellan olika lösningar kallas för basbyte. Simplexmetoden iterar 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 bra att välja den riktning som snabbast förbättrar målfunktionen man säger att den har bäst '''reducerande kostnad''', det är emmellertid inte garanterat att det ger den enklaste lösningen). Eftersom målfunktion ständigt förbättras och antalet baslösningar är ändligt (om än stort) är simplexmetoden garanterad att finna lösningen. För att lösa ett generellt [[LP-problem]] måste det först överföras till [[standardform]] därefter måste en [[baslösning|tillåten baslösning]] identfieras. ==Algoritmen== *(Försteg) Börja med en tillåten baslösning <math> x^0 </math> sätt iterationsräknaren k till 0. *(Steg 1) Beräkna reducerande kostnader för alla icke-basvariabler eventuellt genom omskrivning av målfunktion. *Sätt den variabel med bäst reducerande kostnadad till inkommande variabel. '''Om ingen förbättrande finns är lösningen funnen'''. *Beräkna sökriktning <math> d^k </math> och bestäm steglängden <math> t^k </math> till det största tal för vilket <math> x^{k} + d^kt^k</math> är en tillåten lösning. (om t tillåts gå mot oändligheten har problemet obegränsad bra lösning). *Sätt <math> x^{k+1} = x^k + d^kt^k </math> stega vidare k := k+1 och gå till steg 1. ==Illustrerande exempel== Betrakta LP-problemet [[Fil:LP-problem.jpg|thumb|400px|Ett mycket litet exempel på ett [[LP-problem]]]] <math> \mbox{max z} = x_1 + 4x_2 \,</math> <math> \mbox{då} \qquad\ 2x_1 + 3x_2 \le 6 </math> Bivillkor 1 :::::<math> x_1 \le 2 </math> Bivillkor 2 ::::<math> x_1,x_2 \ge 0 </math> Som kan överföras på standarform genom introduktion av slackvariablerna <math> a_1 </math> och <math> a_2 </math> enligt: <math> \mbox{max z} = 4x_1 + x_2 \,</math> <math> \mbox{då} \qquad\ 2x_1 + 3x_2 + a_1 = 6 </math> :::::<math> x_1 + a_2 = 2 \,</math> ::::<math> x_1,x_2,a_1,a_2 \ge 0 </math> Vi kan enkelt identifiera ur figuren att <math> x_1=x_2=0 </math> är en tillåten lösning som ger upphov till ekvationssystemet <math> 0 + 0 +a_1 = 6 \,</math> <math> 0 + a_2 = 2 \,</math> vilket ger upphov till baslösningen där <math> a_1,a_2 </math> är basvariabler lika med 6 respektive 2 och <math> x_1,x_2 </math> är icke basvariabler ( = 0). Ur målfunktion kan vi utläsa att en ökning av <math> x_1 </math> innebär en ökning av z med 4 enheter/enhet samt att motsvarande värde för <math> x_2 </math> är ett (de reducerande kostnaderna är 4 respektive 1). Eftersom båda icke-basvariabler ger förbättrande sökrikningar tar vi den snabbaste och väljer <math> x_1 </math> som inkommande basvariabel. Ur omskrivningen av bivillkoren erhålles <math> a_1 = 6 - 2x_1 - 3x_2 </math> <math> a_2 = 2 - x_1 </math> Vilket motsvarar en sökriktning längs <math> x_2 </math>, <math> d^0 </math> = [0 1 -2 -1] och vi ser att <math> a_2 </math> först kommer nå noll när <math> x_1 </math> ökar (detta sker för <math> x_1 = 2 </math> så <math> t^0 = 2 </math>) dvs <math> a_2 </math> blir utgående basvariabel och vår nya baslösning blir att <math> a_1,x_1 </math> är basvariabler lika med 4 respektive 2 och <math> a_2,x_2 </math> är ickebasvariabler ( = 0). Inför nästa iteration måste målfunktionen uttryckas i icke-basvariabler (så att vi kan se hur de påverkar) detta görs med hjälp av ekvationerna i bivillkoren. <math> z = 8 - 4a_2 + x_2 </math> Här erhålles att <math> x_2 </math> genererar en förbättrande riktning medans <math> a_2 </math> inte gör det. Vi kan också se att optimallösningen kommer vara minst 8 eftersom det är en konstantterm i målfunktion i sig inte ett viktigt resultat men bra för kontroll senare. proceduren upprepas och vi når i <math> x_1 = 2 x_2 = 2/3, a_1 = a_2 = 0 </math> omskrivningen av målfunktion ger <math> z = 10 - 4a_2 - a_1/3 </math> Här kan ingen förbättrande sökriktning hittas (om <math> a_1 </math> eller <math> a_2 </math> ökar minskar z) vilket innebär att baslösningen är optimalösningen och funktionsvärdet är 10. ==Källor== Lundgren, Jan & Rönnqvist, Mikael & Värbrand Peter: Optimeringslära, 2003, upplaga 3:1. ISBN 978-91-44-05314-1. [[Kategori:Algoritmer|Simplexmetoden]] [[Kategori:Optimeringslära|Simplexmetoden]] [[ar:طريقة التبسيط (برمجة)]] [[cs:Simplexový algoritmus]] [[de:Simplex-Verfahren]] [[en:Simplex algorithm]] [[es:Algoritmo simplex]] [[fr:Algorithme du simplexe]] [[he:שיטת הסימפלקס]] [[it:Algoritmo del simplesso]] [[ja:シンプレックス法]] [[ko:심플렉스법]] [[nl:Simplexmethode]] [[no:Simplex-algoritmen]] [[pl:Algorytm sympleksowy]] [[pt:Algoritmo simplex]] [[ru:Симплекс-метод]] [[sk:Simplexová metóda]] [[sr:Симплекс алгоритам]] [[uk:Симплекс-метод]] [[zh:单纯形法]]

Tillbaka till Simplexmetoden.