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.