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.