Sisäpistemenetelmät lineaarisessa optimoinnissa

Abstract

Sisäpistemenetelmät ovat menetelmäluokka optimointiongelmien ratkaisemiseen. Tässä tutkielmassa keskitytään sisäpistemenetelmiin lineaarisessa optimoinnissa ja käydään läpi tiettyjen menetelmien idea. Käytetyin sisäpistemenetelmä on ei-sallittu primaali-duaalimenetelmä, joka voidaan toteuttaa erittäin tehokkaasti. Sisäpistemenetelmien lisäksi lineaarinen optimointiongelma voidaan ratkaista Simplex-menetelmällä, ja molemmat tavat ovat laajalti käytössä. Myös sisäpistemenetelmien tehokas toteutus ja niiden hyvät ja huonot puolet Simplex-menetelmään verrattuna ovat tutkielmassa käsiteltäviä aiheita.

Interior point methods are a class of methods for solving optimization problems. In this thesis we focus on interior point methods in linear programming and go through the ideas of certain methods. The most used interior point method is an infeasible primal-dual method, which can be implemented very efficiently. In addition to interior point methods, linear programs can be solved by the Simplex method, and both ways are widely used. Ef- ficient implementation of interior point methods and their pros and cons in comparison with the Simplex method are also topics covered in the thesis.