Program for graphical solution of linear programming problems

Author: Jakub Matějka Department of Econometrics Supervisor: Mgr. Jana Sekničková, Ph. D. A common procedure for finding optimal solutions for linear programming problems is to use the simplex method. This algorithm is currently taught at many universities and implemented in many optimization software. To make it easier to understand the whole issue, a graphical solution to linear programming tasks is also used. The goal of the thesis is to write an application in Python that will render a graphical solution for linear programming tasks. For tasks with two variables, it displays a set of permissible solutions, including a cost function, lists all basic permissible solutions, including the cost function values at the given points, and displays the corresponding simplex table. One of the modifications of the simplex method is used for the calculation – the multiplicative simplex method, which is much more suitable for computer implementation than the classic simplex method, mainly due to the speed of calculation and conversion of simplex tables. The thesis also contains a description of methods for solving linear programming tasks and a summary of currently available software of a similar type. It also includes analysing parts of the code and the application. A separate section is devoted to problems that arose during the writing of the program. The end of the thesis describes possible extensions of the application in the future.Autor: Jakub Matějka Katedra Ekonometrie Vedoucí bakalářské práce: Mgr. Jana Sekničková, Ph.D. Běžným postupem při hledání optimálních řešení úloh lineárního programování je použití simplexové metody. Tento algoritmus je v současné době vyučován na mnoha vysokých školách a implementován v mnoha optimalizačních softwarech. Pro snazší pochopení celé problematiky používají vyučující také grafické řešení úloh lineárního programování. Cílem práce je napsat v jazyce Python program, který bude vykreslovat grafické řešení úloh lineárního programování. Pro úlohy se dvěma proměnnými zobrazí množinu přípustných řešení včetně účelové funkce, vypíše všechna základní přípustná řešení včetně hodnot účelové funkce v daných bodech a zobrazí odpovídající simplexovou tabulku. Pro výpočet je použita jedna z modifikací simplexové metody – multiplikativní simplexová metoda, která je pro počítačovou implementaci mnohem vhodnější než klasická simplexová metoda, zejména z důvodu rychlosti výpočtu a přepočtu simplexových tabulek. Práce také obsahuje popis metod řešení úloh lineárního programování a souhrn momentálně dostupných softwarů podobného typu. Součástí je rozbor částí kódu a programu jako celku. Samostatná část je věnována problémům, které během psaní programu vznikly. V závěru práce jsou popsána možná rozšíření programu v budoucnosti