
Network flows in scheduling problems
Rubín, Daniel ; Branda, Martin (advisor) ; Lachout, Petr (referee)
The goal of scheduling problems is to assign machines to a prespecified jobs which require processing. Standard approach leads to integer programming pro blems where machine assignment is represented by binary variables. However, the resulting problems are of high time complexity. Formulating the scheduling problems in terms of network flows shows to be a more effective approach. The aim of this thesis is to introduce basic scheduling tasks and methods used to formulate them in terms of network flows. By means of total unimodularity, we show that network flow algorithms are suitable for solving such problems. Finally, the results are demonstrated in a numerical study. 1


Market model with random inputs
Krch, Ivan ; Lachout, Petr (advisor) ; Večeř, Jan (referee)
The thesis deals with market models with random inputs represented by the newsvendor problem for which the randomness is given through a random number of customers. Presented work is divided into three chapters. In the first chapter we present the elementar newsvendor problem as stochastic programming problem with a fixed recourse. In the second chapter we present the multiplayer game theory adapted to the newsvendors problem. Moreover, in the second chapter we extend the problem by the second newsvendor on the market and in the third chapter we generalize the problem for n newsvendors on the market. We deal with the situations that arise in the chapters two and three from the game theory point of view and we study characteristics of a Nash equilibrium. Presented theory is demonstrated on illustrative examples in the ends of the two last chapters. 1


Assignment problem with application to heath service
Tlapák, Martin ; Kopa, Miloš (advisor) ; Lachout, Petr (referee)
This bachelor's thesis deals with the theory of the nurse scheduling problem using the theory of integer programming. That is why we define basic concepts and present basic theorem of integer programming. We present the algorithm made for solving integer programming. Next we define a basic concept of as sigment problem. We show how to solve assigment problem by the Hungarian method. Finally we solve the real nurse scheduling problem. The nurse's pref erences are included in our model. We are finding solution which is suitable for the labour code of the Czech Republic and the special requests of the stressful workplace. 1


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


Optimization problems with chance constraints
Drobný, Miloslav ; Adam, Lukáš (advisor) ; Lachout, Petr (referee)
Autor se v diplomové práci zabývá optimalizačními úlohami s pravděpodob nostními omezeními. Konkrétně pak situacemi, kdy není známo pravděpo dobnostní rozdělení přítomného náhodného efektu. K řešení těchto problém· lze přistoupit metodami optimistických a pesimistických scénář·, kdy z dané rodiny možných pravděpodobnostních rozdělení vybíráme bu¤ nejpříznivější možnou variantu, nebo naopak tu nejméně výhodnou. Optimalizační úlohy s pravděpodobnostními omezeními formulovanými pomocí výše zmíněných přístup· byly za učinění jistých předpoklad· transformovány do jednoduš ších a řešitelných optimalizačních úloh. Dosažené výsledky byly aplikovány na reálná data z oblastí optimalizace portfolia a zpracování obrazu. 1


Multistage nested distance in stochastic optimization
Horejšová, Markéta ; Vitali, Sebastiano (advisor) ; Lachout, Petr (referee)
Multistage stochastic optimization is used to solve many reallife problems where decisions are taken at multiple times, e.g., portfolio selection problems. Such problems need the definition of stochastic processes, which are usually approxim ated by scenario trees. The choice of the size of the scenario trees is the result of a compromise between the best approximation and the possibilities of the com puter technology. Therefore, once a master scenario tree has been generated, it can be needed to reduce its dimension in order to make the problem computation ally tractable. In this thesis, we introduce several scenario reduction algorithms and we compare them numerically for different types of master trees. A simple portfolio selection problem is also solved within the study. The distance from the initial scenario tree, the computational time, and the distance between the optimal objective values and solutions are compared for all the scenario reduction algorithms. In particular, we adopt the nested distance to measure the distance between two scenario trees. 1


Analysis of portfolio efficiency sets
Fehérová, Veronika ; Kopa, Miloš (advisor) ; Lachout, Petr (referee)
Pøedlo¾ená práce se zabývá dvìma pøístupy øe¹ení problému volby portfolia. Prvním jsou čmeanriskÿ modely, které minimalizují riziko pro pøedem zvolený výnos nebo maximalizují výnos pro pevnì stanovené riziko. Druhým je princip stochastické dominance, úzce související s teorií u¾itku. Cílem této diplomové práce je zkoumat vztah mezi mno¾inami e cientních portfolií, které jsou øe¹e ním v obou pøístupech. Pro kvanti kaci rizika se kromì základních mìr jako jsou rozptyl, V aR nebo CV aR v práci uva¾ují i spektrální míry, zohledòující sub jektivní postoj investora k riziku. Uká¾eme, za platnosti jakých podmínek jsou modely minimalizující spektrální míry konzistentní se stochastickou dominancí druhého øádu (SSD). Aplikujeme KopaPostùv test, který je jedním z více testù na SSD e cienci portfolia, na reálná data z americké burzy cenných papírù a SSD e cientní portfolia porovnáme s e cientními portfoliami získanými minimalizací CV aRu uva¾ovaného na rùznych hladinách spolehlivosti. 1


Stochastic Catastrophe Model Cusp
Voříšek, Jan ; Vošvrda, Miloslav (advisor) ; Lukáš, Ladislav (referee) ; Lachout, Petr (referee)
Title: Stochastic Catastrophe Model Cusp Author: Jan Voříšek Department: Department of Probability and Mathematical Statistics Supervisor: Prof. Ing. Miloslav Vošvrda, CSc., Czech Academy of Sciences, Institute of Information Theory and Automation Abstract: The goal of this thesis is to analyze the stochastic cusp model. This task is divided into two main topics. The first of them concentrates on the stationary density of the cusp model and statistical testing of its bimodality, where power and size of the proposed tests are simulated and compared with the dip test of unimodality. The second main topic deals with the transition density of the stochastic cusp model. Comparison of approximate maximum likelihood approach with traditional finite difference and numerical simulations indicates its advantage in terms of speed of estimation. An approximate Fisher information matrix of general stochastic process is derived. An application of the cusp model to the exchange rate with timevarying parameters is estimated, the extension of the cusp model into stochastic bimodality model is proposed, and the measure of probability of intrinsic crash of the cusp model is suggested. Keywords: stochastic cusp model, bimodality testing, transition density ap proximation


Algorithms for solving twostage stochastic programs
Vlčková, Ivona ; Kopa, Miloš (advisor) ; Lachout, Petr (referee)
The thesis deals with the algorithms for twostage stochastic programs. The first chapter considers the basic properties and theory. Specifically, we introduce the properites of the feasibility region and the objective function. Further, optimality conditions are discussed. In the second chapter we present algoritms which can be used to solve twostage linear programs with fixed recourse. In the first section the basic Lshaped method is described in detail. The second section provides an explanation of the Stochastic Decomposition algorithm with the inclusion of a regularization term. The last chapter presents computational results. Three practical examples are provided both with a brief description of the problem and solutions by the studied algorithms.


New Trends in Stochastic Programming
Szabados, Viktor ; Kaňková, Vlasta (advisor) ; Lachout, Petr (referee)
Stochastic methods are present in our daily lives, especially when we need to make a decision based on uncertain events. In this thesis, we present basic approaches used in stochastic tasks. In the first chapter, we define the stochastic problem and introduce basic methods and tasks which are present in the literature. In the second chapter, we present various problems which are nonlinearly dependent on the probability measure. Moreover, we introduce deterministic and nondeterministic multicriteria tasks. In the third chapter, we give an insight on the concept of stochastic dominance and we describe the methods that are used in tasks with multidimensional stochastic dominance. In the fourth chapter, we capitalize on the knowledge from chapters two and three and we try to solve the role of portfolio optimization on real data using different approaches. 1
