En algoritm för linjära optimeringsproblem

Nedanstående innehåll är skapat av Mimers Brunns besökare. Kommentera arbete

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 s...