| |
| |
| |
| |
| |
|
Dualita v úlohách vícekriteriálního programování
Kůrka, Michal ; Grygarová, Libuše (vedoucí práce) ; Zimmermann, Karel (oponent)
Tato diplomová práce se skládá z teoretické a praktické části. V teoretické části jsou porovnány různé přístupy k dualitě ve vícekriteriálním programování. Zaměříme se na duální úlohu formulovanou Bitranem a zobecníme předpoklady, za kterých pro tuto duální úlohu platí věta o silné dualitě. Ukážeme, že tuto duální úlohu lze získat jako speciální případ schématu exaktní duality, které navrhl Dolecki, a že na ni lze nahlížet jako na zobecnění duální úlohy Wolfeho typu, kterou popisuje Nehse. V praktické části uvádíme algoritmus pro výpočet množiny slabě effi cientních řešení úlohy konkávní vícekriteriální maximalizace, jejíž množina přípustných řešení je kompaktní a konvexní. Tento algoritmus je založen na konstrukci skalárního ekvivalentu k původní vícekriteriální úloze a využívá vlastností jemu příslušné duální úlohy. Popíšeme implementaci algoritmu a její použití ilustrujeme na příkladu.
|
|
Metody řešení vybraných dopravních problémů a jejich implementace.
Drobný, Michal ; Grygarová, Libuše (vedoucí práce) ; Zimmermann, Karel (oponent)
S různými typy dopravních problémů se v praxi setkáváme velmi často. Tento problém lze chápat především jako rozvoz zboží od dodavatelů k odběratelům s cílem minimalizace distribučních nákladů. Reálné dopravní problémy se od těch obecných liší především uvažovanými restrikcemi, což mohou být například kapacity vozidel a objednávek, časová okna a různá další speciální distribuční omezení. Problematiku dopravního problému formuloval již F. L. Hitchcock v roce 1941 a od té doby bylo popsáno mnoho stochastických a nedeterministických metod pro řešení dopravního problému, nicméně při zavedení distribučních restrikcí pro řešení reálných problémů jsou tyto metody obtížně aplikovatelné. Tato práce poskytuje kompilaci nejznámějších deterministických metod vhodných pro řešení dopravních problémů, přičemž metody vhodné pro řešení reálných dopravních problémů jsou popsány podrobněji. Postup řešení pro vybrané metody je demonstrován na jednoduchých příkladech a výsledky porovnány s výsledky řešení ostatních metod. Na základě analýzy těchto metod jsou navrženy nové metody pro řešení reálných dopravních problémů, které jsou implementovány a jejich výsledky porovnány s metodami, které poskytuje komerční softwarový produkt.
|
|
Optimization Problems under (max; min) - Linear Constraint and Some Related Topics
Gad, Mahmoud Attya Mohamed ; Zimmermann, Karel (vedoucí práce) ; Gavalec, Martin (oponent) ; Grygarová, Libuše (oponent)
Název práce: Optimalizační problémy při (max,min)-lineárních omezeních a některé související úlohy. Author: Mahmoud Gad Katedra/Ústav: Katedra Pravděpodobnosti a matematické statistiky Vedoucí dizertační práce: 1. Prof. RNDr. Karel Zimmermann, DrSc 2. Prof. Dr. Assem Tharwat, Cairo University Egypt . Abstrakt: Úlohy na algebraických strukturách, v nichž dvojice operací (max, +) nebo (max, min) nahrazují operace sčítání a násobení v klasické lineární algebře se objevují v literatuře přibližně od šedesátých let minulého století. První výsledky s využitím těchto struktur publikovali A. Shimbel v práci [37] s aplikacemi v komunikačních sítích, a dále R. A. Cunnighame-Green [12,13], N. Vorobjov [40] a B. Giffler [18] s aplikacemi na rozvrhování práce strojů a v teorii spolehlivosti. Ucelená systematická teorie takových algebraických struktur byla publikována pravděpodobně poprvé v práci [14]. V nedávno publikované knize [4] lze nalézt nejnovější stav výzkumu teorie a algoritmů ve struktuře s operacemi (max,+). Protože operace maxima, která v uvedených strukturách nahrazuje operaci sčítání, není grupovou, ale pouze pologrupovou operací, je podstatný rozdíl mezi řešením soustav s proměnnými pouze na jedné straně rovnic resp. nerovností a soustav, v nichž se proměnné nacházejí na obou stranách těchto vztahů....
|
|
Metody řešení vybraných dopravních problémů a jejich implementace.
Drobný, Michal ; Grygarová, Libuše (vedoucí práce) ; Zimmermann, Karel (oponent)
S různými typy dopravních problémů se v praxi setkáváme velmi často. Tento problém lze chápat především jako rozvoz zboží od dodavatelů k odběratelům s cílem minimalizace distribučních nákladů. Reálné dopravní problémy se od těch obecných liší především uvažovanými restrikcemi, což mohou být například kapacity vozidel a objednávek, časová okna a různá další speciální distribuční omezení. Problematiku dopravního problému formuloval již F. L. Hitchcock v roce 1941 a od té doby bylo popsáno mnoho stochastických a nedeterministických metod pro řešení dopravního problému, nicméně při zavedení distribučních restrikcí pro řešení reálných problémů jsou tyto metody obtížně aplikovatelné. Tato práce poskytuje kompilaci nejznámějších deterministických metod vhodných pro řešení dopravních problémů, přičemž metody vhodné pro řešení reálných dopravních problémů jsou popsány podrobněji. Postup řešení pro vybrané metody je demonstrován na jednoduchých příkladech a výsledky porovnány s výsledky řešení ostatních metod. Na základě analýzy těchto metod jsou navrženy nové metody pro řešení reálných dopravních problémů, které jsou implementovány a jejich výsledky porovnány s metodami, které poskytuje komerční softwarový produkt.
|
|
Dualita v úlohách vícekriteriálního programování
Kůrka, Michal ; Zimmermann, Karel (oponent) ; Grygarová, Libuše (vedoucí práce)
Tato diplomová práce se skládá z teoretické a praktické části. V teoretické části jsou porovnány různé přístupy k dualitě ve vícekriteriálním programování. Zaměříme se na duální úlohu formulovanou Bitranem a zobecníme předpoklady, za kterých pro tuto duální úlohu platí věta o silné dualitě. Ukážeme, že tuto duální úlohu lze získat jako speciální případ schématu exaktní duality, které navrhl Dolecki, a že na ni lze nahlížet jako na zobecnění duální úlohy Wolfeho typu, kterou popisuje Nehse. V praktické části uvádíme algoritmus pro výpočet množiny slabě effi cientních řešení úlohy konkávní vícekriteriální maximalizace, jejíž množina přípustných řešení je kompaktní a konvexní. Tento algoritmus je založen na konstrukci skalárního ekvivalentu k původní vícekriteriální úloze a využívá vlastností jemu příslušné duální úlohy. Popíšeme implementaci algoritmu a její použití ilustrujeme na příkladu.
|