En algoritm för linjära optimeringsproblem
Linjär optimeringSimplexAlgoritmLPMatlabInre punktOptimumKarmarkarsTeknisk-vetenskapligaBeräkningarTBVLinear programmingOptimizationInterior-PointOROperations researchMathematical programmingScientific computing
Denna uppsats behandlar en algoritm som löser linjära optimeringsproblem. Algoritmen bygger på en liknande idé som simplexalgoritmen men i denna kan startvärdet även vara en punkt inom tillåtet område eller på randen till detta område. Det behöver inte nödvändigtvis vara en hörnpunkt, vilket simplexalgoritmen kräver. Under algoritmens gång kommer iterationsvärdena att ligga på randen till det tillåtna området för att slutligen hamna i ett hörn. Därefter går iterationsvärdena från hörn till hörn tills slutligen optimum har nåtts. Den förväntade tiden det tar för datorn att lösa linjära optimeringsproblem med denna algoritm tycks vara polynomisk med avseende på problemets storlek. Inledningsvis beskrivs vad ett linjärt optimeringsproblem är för någonting och olika former av dessa. Därefter följer en beskrivning hur denna algoritm fungerar. I slutet av rapporten görs jämförelser med motsvarande befintligt program i Matlab. Längst bak i uppsatsen finns datorimplementering av algoritmen skrivet i Matlab-kod. Där finns även olika versioner som löser samma typ av problem men skrivet på olika former.