Unimodulární matice a jejich využití v operačním výzkumu
| Název práce: | Unimodulárne matice v operačnom výskume |
|---|---|
| Autor(ka) práce: | Liška, Andrej |
| Typ práce: | Bakalářská práce |
| Vedoucí práce: | Pelikán, Jan |
| Oponenti práce: | Ivánek, Jiří |
| Jazyk práce: | Slovensky |
| Abstrakt: | Úloha celočíselného programovania je NP obtiažny problém (NP-hard), neexistuje teda polynomiálny algoritmus pre riešenie tejto úlohy. Pritom väčšina optimalizačných úloh operačného výskumu riešiacich úlohy ekonomickej praxe vedú na úlohy celočíselného programovania. Pokiaľ ale úloha celočíselného programovania je taká, že obmedzujúce podmienky v tvare rovníc a nerovností obsahujú unimodolárnu maticu, je možné úlohu celočíselného programovania riešiť polynomiálne, metódami lineárneho programovania. Charakteristické problémy obsahujúce totálne unimodulárnu maticu sú napríklad dopravný problém, priraďovací problém, alebo problém maximálneho toku. Existujú aj problémy, ktoré je možné relaxovať na úlohu s unimodulárnou maticou a pomocou tejto relaxácie nájsť suboptimálne riešenie alebo zefektívniť metódu riešení celočíselnej úlohy, napríklad metódu vetvenia a hraníc (branch and bound). Do tejto skupiny spadá napríklad problém obchodného cestujúceho. Z bežného života je potom možné prispieť k riešeniu veľkého množstva reálnych problémov. |
| Klíčová slova: | operačný výskum; totálne unimodulárne matice; celočíselné lineárne programovanie |
| Název práce: | Unimodulární matice a jejich využití v operačním výzkumu |
|---|---|
| Autor(ka) práce: | Liška, Andrej |
| Typ práce: | Bakalářská práce |
| Vedoucí práce: | Pelikán, Jan |
| Oponenti práce: | Ivánek, Jiří |
| Jazyk práce: | Slovensky |
| Abstrakt: | Úloha celočíselného programování je NP obtížný problém (NP-hard), neexistuje tedy polynomiální algoritmus pro řešení této úlohy. Přitom většina optimalizačních úloh operačního výzkumu řešících úlohy ekonomické praxe vedou na úlohy celočíselného programování. Pokud ale úloha celočíselného programování je taková, že omezující podmínky ve tvaru rovnic a nerovností obsahují unimodolární matici, lze úlohu celočíselného programování řešit polynomiálně metodami lineárního programování. Charakteristické problémy obsahující totálně unimodulární matici jsou například dopravní problém, přiřazovací problém, nebo problém maximálního toku. Existují i problémy, které je možné relaxovat na úlohu s unimodulární maticí a pomocí této relaxace najít suboptimální řešení, nebo zefektivnit metodu řešení celočíselné úlohy například metodu větvení a hranic (branch and bound). Do této skupiny spadá například problém obchodního cestujícího. Z běžného života je pak možné přispět k řešení velkého množství reálných problémů. |
| Klíčová slova: | totálně unimodulární matice; celočíselné lineární programování; operační výzkum |
| Název práce: | Unimodular matrices in operations research |
|---|---|
| Autor(ka) práce: | Liška, Andrej |
| Typ práce: | Bachelor thesis |
| Vedoucí práce: | Pelikán, Jan |
| Oponenti práce: | Ivánek, Jiří |
| Jazyk práce: | Slovensky |
| Abstrakt: | Linear programming problem is NP-hard, i.e. there is no polynomial algorithm to find a solution for any particular linear programming problem. Nevertheless the majority of optimization problems in operational research lead to linear programming problems. In case the linear programming problem‘s constraints, in form of equations and inequations, involve unimodular matrix, it can be solved using polynomial methods of linear programming. Transportation problem, assignment problem or maximum flow problem can be considered as examples of characteristic problems involving unimodular matrix. There are also problems that can relax to a problem with its respective unimodular matrix. Then using relaxation one can obtain a sub-optimal solution or implement, e.g. branch and bound method to optimize the solution method. The latter forms a set of problems such as travelling salesman problem. Therefore the contribution to solving some of the real-life problem is undeniable. |
| Klíčová slova: | linear integer programming; operational research; totally unimodular matrices |
Informace o studiu
| Studijní program / obor: | Aplikovaná informatika/Informační média a služby |
|---|---|
| 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: | 28. 1. 2020 |
|---|---|
| Datum podání práce: | 10. 5. 2020 |
| Datum obhajoby: | 22. 6. 2020 |
| Identifikátor v systému InSIS: | https://insis.vse.cz/zp/72278/podrobnosti |