Optimalizace toků jako úloha LP
| Název práce: | Optimalizace toků jako úloha LP |
|---|---|
| Autor(ka) práce: | Doubrava, Jiří |
| Typ práce: | Bakalářská práce |
| Vedoucí práce: | Kalčevová, Jana |
| Oponenti práce: | Flusserová, Lenka |
| Jazyk práce: | Česky |
| Abstrakt: | Tato práce se zabývá problematikou optimalizace toků v síti se zaměřením na řešení pomocí lineárního programování. Teoretická část je rozdělena na tři hlavní části: maximální tok, minimální tok a maximální tok s minimálními náklady. První část je zaměřena na teoretickou podstatu problematiky maximálního toku a hlavně na tyto algoritmy: Fordův-Fulkersonův, Dinicův/Edmondsův-Karpův, Algoritmus tří Indů a Goldbergův push-relabel algoritmus. Jejich vysvětlení je pak doplněno názornými příklady. V dalších kapitolách jsou popsány úlohy hledání minimálního toku a maximálního toku s minimálními náklady s jednoduchými algoritmy pro jejich řešení, opět vysvětlenými na názorných příkladech. Praktická část práce obsahuje programové řešení úlohy hledání maximálního toku zpracované v aplikaci MaxTok, kterou lze nalézt na přiloženém CD. |
| Klíčová slova: | push-relabel algoritmus; Dinicův/Edmondsův-Karpův algoritmus; Fordův-Fulkersonův algoritmus; maximální tok |
| Název práce: | Optimalization of flows in the network using the linear programming |
|---|---|
| Autor(ka) práce: | Doubrava, Jiří |
| Typ práce: | Bachelor thesis |
| Vedoucí práce: | Kalčevová, Jana |
| Oponenti práce: | Flusserová, Lenka |
| Jazyk práce: | Česky |
| Abstrakt: | This thesis deals with optimization of flows in a network with focus on solutions based on linear programming. The theoretical part is divided into three main sections: maximal flow, minimal flow and maximal flow with minimal costs. The first part focuses on theoretical basics of maximal flow problem and mainly on these algorithms: Ford-Fulkerson, Dinic/Edmonds-Karp, Three Indians algorithm and Goldberg push-relabel algorithm. These are explained on examples. The other chapters explain the minimal flow and the maximal flow with minimal costs problems with simple algorithms for their solutions, again explained on some examples. The practical part includes software solution of maximal flow problem in application MaxTok, which can be found on attached CD. |
| Klíčová slova: | push-relabel algorithm; Ford-Fulkerson algorithm; maximal flow; Dinic/Edmonds-Karp algorithm |
Informace o studiu
| Studijní program / obor: | Kvantitativní metody v ekonomice/Matematické metody v ekonomii |
|---|---|
| Typ studijního programu: | Bakalářský studijní program |
| Přidělovaná hodnost: | Bc. |
| Instituce přidělující hodnost: | Vysoká škola ekonomická v Praze |
| Fakulta: | Fakulta informatiky a statistiky |
| Katedra: | Katedra ekonometrie |
Informace o odevzdání a obhajobě
| Datum zadání práce: | 27. 10. 2009 |
|---|---|
| Datum podání práce: | 17. 5. 2010 |
| Datum obhajoby: | 8. 6. 2010 |
| Identifikátor v systému InSIS: | https://insis.vse.cz/zp/22481/podrobnosti |