|
|
A knapsack problem
Piskačová, Nikola ; Kopa, Miloš (advisor) ; Lachout, Petr (referee)
This work deals with the theory of integer programming. In the first part, there are defined the basic concepts and there are mentioned the two most used methods for solving integer problems. Namely, it is the Branch and Bound method and the Cutting Plane method. In the second chapter, there is described the Knapsack Problem and its various formulations. This problem is a special case of integer optimalization. Next, there is a practical part, where a real problem is solved. The problem is how to place the products in shelves in equipment in the most effectively way. In this chapter is described how to process input data, create a model and solve the problem. In the second part of the practical part, the basics of stochastic optimalization and solution of these problems by the Scenario method are presented. This method is used to solve the previously mentioned problem if the delivery days are random. The aim of this work is to show the applicability of formulations of Knapsack Problem and to compare the obtained results. 1
|
|
|
Analýza trasování a vytíženosti manipulantů v lisovací hale
Bark, Ondřej ; Borovička, Adam (advisor) ; Fábry, Jan (referee)
The diploma thesis focuses on tracing in layout by handlers between assembly lines in new plant for corporation Continental Automotive Czech Republic ltd, where boosters are produced. The theoretical part involves definitions of logistics, supply chain, material flow and handling equipment. Furthermore, methods of mathematic programming and software equipment are described, such as quadratic assignment problem, knapsack problem, travelling salesman problem from graph theory. In the practical part the situation in corporation has been analyzed and the data prepared for further examination. Then layout of plant and internal processes are evaluated and an appropriate model or concept of solution is selected. Subsequently, application in MS Excel is created with support of VBA scripts (3 kinds of layouts). The user manipulates with application followed by Solver for implementation of a new solution into practice. Finally, the models are interpreted and verified by Lingo. The focus of the thesis is the design of a layout change of a new plant including the description of tracing.
|
|
|
The multiple knapsack problem in use
Procházková, Lucie ; Sekničková, Jana (advisor) ; Suchánková, Tereza (referee)
In the area of integer linear programming problems is placed the knapsack problem, including its modifications. Among them is the multiple knapsack problem which is the subject of this thesis. In connection with the interpretation of results is necessary to extend the knapsack problem to integer conditions that are most often transformed into a bivalent conditions. This greatly increases the computational complexity of these tasks. Despite the fact that solutions exist for the exact algorithms, often in the calculation of some large problems can not be used. Approximate and sufficiently accurate results can be achieved by using heuristics and other techniques that have been created for this purpose. Subchapters in the first part further describe the variation of the knapsack problem, in the second part subchapters followed, and present some possible use in practice.
|
|
|
Generalized assignment problem
Kocourková, Markéta ; Sekničková, Jana (advisor) ; Nečas, Dalibor (referee)
The generalized assignment problem is a topic of this thesis. The knapsack problem in general belongs to among classical operation research problems and belongs to the category of integer linear programming. It is very often formulated as a binary problem or 0-1. There are several types of knapsack problems which are described in this thesis. Some of the knapsack problems are so large and although exist exact algorithms for finding optimal solution, heuristics are rather used. They are not so exact but they find solution much earlier. Therefore some of the knapsack problems belong to NP-hard problems. This thesis is focused on one type particularly, the generalized assignment problem, which is demonstrated on practical example how the problem can be used.
|
|
|
Optimal composition of groceries for mountain trip
Fesenko, Anastasiya ; Kalčevová, Jana (advisor) ; Flusserová, Lenka (referee)
This work is aimed towards the application of knapsack problem in practical example of packing of groceries for mountain trip. The knapsack problem is one of the tasks of integral programming; those are the models that can only variably accept the integral value. The solutions of integral tasks are usually very meticulous. That is why for their solution special algorithms were created, which are capable of discovering an integral solution of such tasks, for example, branch and bound method, Balas method etc. These types of algorithms are defined in the first part of this work. While writing this thesis a considerable emphasis was put into application of its result in practice. Hence, for achieving applicability practical tasks are solved from various angles and therefore various aims have been set forth in each solution option. The results of each option are interpreted and then the differences are explained.
|
|
|
The multiple knapsack problem
Černý, Vít ; Kalčevová, Jana (advisor) ; Suchánková, Tereza (referee)
The knapsack problem is one of the classical operations research problems. It belongs to the category of integer linear programming problems and is most often formulated as a binary problem. This thesis describes different categories of the problem and also some methods for finding their solution. Although there are precise algorithms for finding reliable optimal solution, some of the knapsack problems are so large that it would be impossible to follow the exact algorithms. Therefore, more complex knapsack problems belong to the complexity class of NP-complete. Yet there are a variety of heuristics and methods developed, which can lead to a sufficiently good solution in a relatively short time and relatively simple way. This paper focuses particularly on one of the problems described, the multiple knapsack problem. It is showed on a practical example how the problem can be solved.
|
|
|
The Multi-Dimensional Knapsack Problem
Ficová, Pavla ; Kalčevová, Jana (advisor) ; Černohous, Roman (referee)
This work deals with multi-dimensional knapsack problem. Knapsack problem coincides with the category of integer linear programming. Thanks to the necessity of integer result it used to be more difficult to find the solution, by meeting all limitations. A lot of statisticians and mathematicians from all over the world are engaged in inventing an exact algorithm for calculation of these problems. As at now, there have been various accesses and heuristics concerning how to solve these problems or at least how to get as close to the optimal solution as possible. Problems with many variables are impossible to solve by hand calculations, the model is too complex and number of iterations is really high. Extensive exercises can be solved by advanced software in several minutes or longer. This work is trying to describe the problems, clear up and show practical application of knapsack problem in a real situation.
|
|
|
The Optimization Methods with Utilization of the Simulation in MS Exel
Škulavíková, Štěpánka ; Kuncová, Martina (advisor) ; Fábry, Jan (referee)
Thesis is based on original self-made application programmed at VBA in MS Excel 2007. The reason to build this application was integration of simulation Monte Carlo and chosen optimization methods. The application allows do simulation of the knapsack problem and of the assignment problem with uncertainty. The parameters of these models are possible to set up as changing values in dependence of chosen probability distribution. Output of the simulation is a probability recommendation which objects should be used. Choose of objects depend on optimized models. Results of both models are represented by statistical indexes, tables of parameters and graph.
|
|
|
Speciální algoritmy některých úloh operačního výzkumu
Klaschková, Alena ; Šindelářová, Irena (advisor) ; Zouhar, Jan (referee)
Práce sumarizuje a dává do souvislostí vybrané úlohy operačního výzkumu, pro něž byly vyvinuty speciální optimalizační algoritmy či heuristiky kromě obecných algoritmů řešících problémy lineárního programování nebo diskrétního programování, s důrazem na praktické možnosti řešení těchto problémů danými algoritmy. Zabývá se běžnými úlohami lineárního programování s omezenými proměnnými, úlohami teorie grafů (toky, cesta grafem, kostra grafu), úlohou batohu, dopravním problémem, přiřazovacím problémem a úlohou obchodního cestujícího a srovnává speciální algoritmy s obecnými.
|
guest ::
