|
|
Collection of Solved Linear Programming Problems
Ďuricová, Alexandra ; Šindelářová, Irena (advisor) ; Kořenář, Václav (referee)
The target of this bachelor thesis is to build new examples of linear programming. The examples in this work include all the formalities which are necessary for the correct interpretation. The entering tasks designed are based on real problems and consist of as much real values as possible. The work is divided into nine chapters and eight of them represent one area of linear programming. The first chapter is a short introduction into the theory of linear programming. The second chapter consists of two parts representing integer and non-integer programming. This chapter is the largest and contains 9 examples. The following four chapters consist of examples of non-integer programming and the last three chapters contain examples of integer programming.
|
|
|
Solving the Battleship Solitaire puzzle as an integer programming problem
Přibylová, Lenka ; Jablonský, Josef (advisor) ; Fábry, Jan (referee)
The bachelor thesis deals with the Battleship Solitaire puzzle. It introduces the history and the rules of this puzzle, which are thereafter used to formulate the puzzle as an integer programming problem. Two mathematical models based on different approaches are created, a cell-based model and a ship-based model. In order to determine whether a puzzle has a unique solution an objective function is added to each model. Both models are developed in LINGO modeling language and tested with different grid sizes. The test results show that even though the ship-based model uses fewer variables and constraints, it is too demanding in terms of data processing. It results in longer solving times and the model fails to find a solution for larger grids. Solving the problem using the cell-based model is significantly faster. The solution was found even for larger grids, though the solving time was very long.
|
|
|
The Asymptotic Integer Algorithm
Murinová, Michaela ; Kalčevová, Jana (advisor) ; Jablonský, Josef (referee)
This work is dealing with the tasks of integer programming and with the methods for their solving. The most famous methods are "branch and bounds method" and the Gomory's method of cut algorithms. The purpose of this work is to get readers acquainted with the alternative method of asymptotic integer algorithm. This method is based on the similar idea as the rounding procedure. The main idea is to enable the nonbasic variables gain a non-zero value. It leads to cutting the continuous (noninteger) solution space on the graphics illustration, while no integer solution should be lost. This method is presented on the example, which is a part of the main chapter and furthermore on its own example in the third chapter.
|
|
|
Traveling Tournament Problem
Šimpach, Ondřej ; Jablonský, Josef (advisor) ; Rada, Miroslav (referee)
Traveling Tournament Problem is the optimization problem of sport calendar which requires finding the minimum sum of possible travel distances between the teams tournament matches. The tournament is most common type of "double round robin" where distance is crucial for the teams. Concurrently with the issue of finding the optimal solution to a suitable arrangement of sports teams in the table together with respecting the highest possible number of criteria appealing by stakeholders to organizers such as managers of teams and television and radio companies. Thesis provides insight into the complexity of solving large problems, recommendation for their solutions and possible starting-points. In the end there is an alternative option for calculations tournament schedules in the Czech environment event the distances are not so important in this case.
|
|
|
The Generalized Distribution Problem Approach
Fuksová, Lucie ; Lagová, Milada (advisor) ; Kalčevová, Jana (referee)
The generalized distribution problem is task from linear programming approach which belongs to the distribution problems with specific mathematical model. For solution this problems we need to use another methods than the universal simplex method. A typical example is the transportation problem. The generalized distribution problem differs from it only in a small difference in mathematical model, but compared to the traffic problem has computational difficulties. To build the model and its solution is necessary to calculate the transmission coefficients, the so-called "performance factors". This work will prepare the answers for problem formulations and mathematical model and will describe the procedures that can solve problems of similar type. Methods used in the thesis are modified distribution method and the simplex method. To calculate solutions will be used the optimization software Lingo.
|
|
|
Optimization of ideal nutriment
Šádová, Eva ; Kuncová, Martina (advisor) ; Šindelářová, Irena (referee)
The thesis describes a way of searching the best bill of fare for certain patient in hospital. The target is to set up and then to solve an optimization model. Criterion of performance is to minimize spending on selected foodstuff. The first part describes a theory of optimization models, the second is about nutrition and the third aims to solve a model and to interpret the results.
|
|
|
Solving recreational mathematics problems as discrete optimization problems
Verner, Jan ; Jablonský, Josef (advisor) ; Fábry, Jan (referee)
The work is focused on the role of discrete linear programming and recreational mathematics. The aim of this work is to acquaint the reader with recreational mathematics and formulations of recreational mathematics problems as integer linear programming problems. This is demonstrated on two board games problems, which are described by a mathematical model and solved with the MPL optimization software. One main part involves the analysis and solution of a Peg solitaire game version, the reader is also been acquainted with.
|
|
|
Knapsack problem
Šemnická, Eliška ; Kalčevová, Jana (advisor) ; Šmídová, Milada (referee)
In the study are described integer programming, particular problems, as assignment problem, cover problem and city transportation problem, and method of solving these kinds of problems. It is depictured Lang and Doig method. Then is described knapsack problem and its types. A reader can find a method for solving zero-to-one problems, especially Balas method for minimisation of a target function. There is introduced a financial problem of optimisation portfolio in the study which is formulated as a zero-to-one problem and solved by Balas method.
|
|
|
Testing software for mixed integer programming
Kmetonyová, Daniela ; Jablonský, Josef (advisor) ; Kalčevová, Jana (referee)
Táto diplomová práca porovnáva tri vybrané optimalizačné softvéry z hľadiska rýchlosti výpočtu a presnosti riešenia úloh zmiešaného celočíselného programovania a užívateľskej prístupnosti ovládania softvéru. Ďalej obsahuje popis fungovania a použité postupy pri výpočte jednotlivých testovaných softvérov, a to hlavne s dôrazom na riešenie zmiešaných celočíselných úloh. Testované boli softvéry ? CPLEX 10.1, Xpress 18.00 a MOSEK 5.0. Na testovanie boli použité úlohy z knižnice MIPLIB 2003.
|
|
|
Systém pro řešení úloh celočíselného programování v prostředí MS Excel
Škarvan, Martin ; Jablonský, Josef (advisor) ; Fábry, Jan (referee)
Diplomová práce se zabývá nejznámějšími úlohami celočíselného programování a typickými úlohami z teorie grafů. Zahrnuje formulace matematických modelů, pojednává o metodách řešení těchto úloh a uvádí přehled v současné době nejpoužívanějšího software určeného k jejich optimalizaci. Těžiště práce spočívá v aplikaci vytvořené v prostředí MS Excel a napojené na optimalizační prostředí systému MPL for Windows. Tento celek umožňuje řešit typové celočíselné úlohy a představuje praktickou ukázku způsobu vnoření matematických modelů do vlastních aplikací.
|
guest ::
