En algoritm för linjära optimeringsproblem

Sammanfattning

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.