Algoritmy pro řešení stochastických dvoustupňových úloh

Abstract

V této práci se zabýváme algoritmy pro řešení dvoustupňových stochastických úloh. V první kapitole jsou uvedeny teoretické vlastnosti účelové funkce a množiny omezení, jenž jsou nezbytné pro pochopení fungování algoritmů. V závěru jsou diskutovány podmínky optimality. Druhá kapitola se zabývá algoritmy pro řešení úloh s lineární účelovou funkcí. V první části je podrobně vysvětlena základní forma L-shaped algoritmu. Druhá část je věnována algoritmu stochastické dekompozice včetně popisu regularizované verze. Poslední kapitola práce slouží k praktickému porovnání uvedených algoritmů na třech aplikačních příkladech. Každá úloha je nejprve teoreticky popsána a poté vyřešena oběma uvedenými algoritmy.

The thesis deals with the algorithms for two-stage 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 two-stage linear programs with fixed recourse. In the first section the basic L-shaped 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.