456-0340/01 – Optimalizační úlohy (OU)

Garantující katedraKatedra informatikyKredity4
Garant předmětudoc. RNDr. Petr Hliněný, Ph.D.Garant verze předmětudoc. RNDr. Petr Hliněný, Ph.D.
Úroveň studiapregraduální nebo graduálníPovinnostpovinně volitelný
Ročník2Semestrletní
Jazyk výukyčeština
Rok zavedení2003/2004Rok zrušení2005/2006
Určeno pro fakultyFEIUrčeno pro typy studiamagisterské
Rozsah výuky pro formy studia
Forma studiaZp.zak.Rozsah
prezenční Zápočet a zkouška 2+2
kombinovaná Zápočet a zkouška 2+2

Cíle předmětu vyjádřené dosaženými dovednostmi a kompetencemi

Cílem předmětu je poskytnout studentům základní přehled kombinatorických, lineárních a celočíselných optimalizačních úloh, včetně běžných metod jejich řešení a vysvětlení. Na přednáškách budou vysvětleny matematické principy využívané při řešení těchto optimalizačních úloh a na cvičeních bude látka doplněna ukázkami prakticky motivovaných úloh a použití optimalizačního softwaru.

Vyučovací metody

Anotace

Studenti se seznámí s běžnými typy optimalizačních úloh (kombinatorické, lineární a celočíselné optimalizace) a naučí se některé základní metody jejich řešení. Důraz bude kladen především na vysvětlení a pochopení simplexové metody pro lineární optimalizaci a metody větvení a mezí pro celočíselnou optimalizaci. Zmíněny budou také některé jiné specifické problémy jako třeba toky v sítích nebo problémy rozvrhování a obchodního cestujícího. Jedná se o přehledový předmět. Na přednáškách budou vysvětleny matematické principy využívané při řešení těchto optimalizačních úloh a na cvičeních bude látka doplněna ukázkami prakticky motivovaných úloh a použití optimalizačního softwaru.

Povinná literatura:

Jaroslav Janáček: Matematické Programování. EDIS Žilinská Univerzita, 2003. Petr Hliněný, Optimalizační úlohy, http://www.cs/hlineny/vyuka/OU-slides/, 2005.

Doporučená literatura:

Forma způsobu ověření studijních výsledků a další požadavky na studenta

Podmínky udělení zápočtu: Podmínkou zápočtu je aktivní účast na alespoň polovině cvičení a úspěšné vyřešení tam zadaných praktických optimalizačních úloh.

E-learning

Další požadavky na studenta

Prerekvizity

Předmět nemá žádné prerekvizity.

Korekvizity

Předmět nemá žádné korekvizity.

Osnova předmětu

Přednášky: Hladový algoritmus a jeho použití v příkladech. Toky v sítích: formulace a použití. Dualita toků a řezů. Úloha lineární optimalizace: formulace a aplikace. Konvexita a dualita v lineární optimalizaci. Vysvětlení simplexové metody pro řešení lineární optimalizace. Implementace simplexové metody, umělé proměnné. Degenerované úlohy, prevence zacyklení a délka výpočtu. Další aplikace: toky, dopravní úloha a maticové hry. Úloha celočíselné nebo diskrétní optimalizace. Obecné vysvětlení metody větvení a mezí, relaxace úlohy. Implementace metody větvení a mezí. Specifické varianty úlohy: rozvrhování a obchodní cestující. Cvičení: Na cvičeních se prakticky řeší zadané optimalizační úlohy, většinou za pomoci výpočetní techniky.

Podmínky absolvování předmětu

Kombinovaná forma (platnost od: 1960/1961 letní semestr)
Název úlohyTyp úlohyMax. počet bodů
(akt. za podúlohy)
Min. počet bodůMax. počet pokusů
Zápočet a zkouška Zápočet a zkouška 100 (145) 51 3
        Zkouška Zkouška 100  0 3
        Zápočet Zápočet 45  0 3
Rozsah povinné účasti:

Zobrazit historii

Podmínky absolvování předmětu a účast na cvičeních v rámci ISP:

Zobrazit historii

Výskyt ve studijních plánech

Akademický rokProgramObor/spec.Spec.ZaměřeníFormaJazyk výuky Konz. stř.RočníkZLTyp povinnosti
2004/2005 (N2646) Informační technologie (2612T025) Informatika a výpočetní technika P čeština Ostrava 3 povinně volitelný stu. plán
2004/2005 (N2646) Informační technologie (2612T025) Informatika a výpočetní technika K čeština Ostrava 3 povinně volitelný stu. plán
2003/2004 (N2646) Informační technologie (2612T025) Informatika a výpočetní technika P čeština Ostrava 2 povinně volitelný stu. plán
2003/2004 (N2646) Informační technologie (2612T025) Informatika a výpočetní technika K čeština Ostrava 2 povinně volitelný stu. plán

Výskyt ve speciálních blocích

Název blokuAkademický rokForma studiaJazyk výuky RočníkZLTyp blokuVlastník bloku

Hodnocení Výuky

Předmět neobsahuje žádné hodnocení.