Linear programming

Ovaj rad obrađuje teoriju linearnog programiranja. Na početku je izložena potrebna teorija iz područja linearne algebre: vektorski prostori s posebnim naglaskom na Euklidski prostor Rn, sustavi linearnih jednadžbi i nejednadžbi te traženje njihovih (bazičnih) rješenja. Središnji je dio posvećen samoj definiciji problema linearnog programiranja (u općem, standardnom i kanonskom obliku), pojmu dualnosti i nizu uz to vezanih teorema o egzistenciji (optimalnog) rješenja. Slijede osnove teorije konveksnih skupova i intuitivna grafička metoda. Naposljetku, opisana je najpoznatija metoda rješavanja problema linearnog programiranja - simpleks metoda. Obje su metode ilustrirane odgovarajućim primjerima.This thesis studies the theory of linear programming. The first part gives insight into necessary linear algebra theory: vector spaces (especially Euclidean space Rn), systems of linear equations and inequalities and their solving method. The central part focuses on definition of linear program (in standard, canonical and general form), concept of duality and (optimal) so lution existence theorems. The thesis then presents the basics of convex set theory necessary for following intuitive graphical method. Finally, the best known method for solving linear problems, the simplex method, is demonstra ted. The linear programming solving methods are illustrated with appropriate examples