Název:
Bendersova dekompozice v optimalizaci
Překlad názvu:
Benders decomposition in optimization
Autoři:
Minaříková, Michaela ; Branda, Martin (vedoucí práce) ; Rusý, Tomáš (oponent) Typ dokumentu: Bakalářské práce
Rok:
2018
Jazyk:
cze
Abstrakt: [cze][eng] Práce pojednává o Bendersově dekompozici v optimalizaci, konkrétně ve sto- chastickém lineárním programování. Čtenář je nejdříve seznámen s důležitými pojmy používanými v dekompozičním algoritmu. Následně je vysvětleno, jak lze úlohu stochastického lineárního programování přeformulovat na tvar vhodný pro Bendersův algoritmus. V třetí kapitole je dekompoziční algoritmus, založený na řezech přípustnosti a optimality, vysvětlen včetně podmínek konvergence algo- ritmu. Pro dvoustupňové stochastické lineární programování je uvedena modi- fikace algoritmu. V průběhu práce je Bendersův algoritmus ilustrován na dvou menších příkladech. 1The Bachelor thesis is dealing with Benders decomposition in optimization, especially in stochastic linear programming. In the begining the reader will be introduced to the important terms used in the decomposition algorithm. Con- sequently it is demonstrated how to reformulate the problem of stochastic linear programming to a special structure suitable for Benders decomposition. In the third chapter, the decomposition algorithm, using the feasibility and optimality cuts, is explained including conditions of convergence of the algorithm. There follows modification of algorithm for two stage stochastic linear programming. Finally, we illustrate Benders algorithm on two smaller problems. 1
Klíčová slova:
Bendersova dekompozice; stochastické lineární programování; řez optimality; řez přípustnosti; Benders decomposition; feasibility cut; optimality cut; stochastic linear programming