460-4108/01 – Operační výzkum II (OV II)

Garantující katedraKatedra informatikyKredity4
Garant předmětudoc. MSc. Donald David Davendra, Ph.D.Garant verze předmětudoc. MSc. Donald David Davendra, Ph.D.
Úroveň studiapregraduální nebo graduálníPovinnostvolitelný odborný
Ročník2Semestrzimní
Odkaz na webJazyk výukyčeština
Rok zavedení2015/2016Rok zrušení
Určeno pro fakultyFEIUrčeno pro typy studianavazující magisterské
Výuku zajišťuje
Os. čís.JménoCvičícíPřednášející
DAV0026 doc. MSc. Donald David Davendra, Ph.D.
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 10+0

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

Kurz bude vyučovat pokročilé techniky operačního výzkumu. Přednášky budou rozšiřovat základní algoritmus simplex o aplikaci omezených proměnných a revidovaný algoritmus simplex pro vyšší rychlost. Goal programming uvede aplikaci formulace více účelů v lineárním programování. Bude probráno celočíselné programování, které je rozšířením lineárního programování, ve kterém jsou všechny proměnné celočíselné. Celočíselné programování je důležitou technikou pro řešení přiřazovacích problémů. 3 závěrečná témata pokryjí branch and bound algoritmus pro celočíselné programování, cutting plane metodu, ve které mohou být využity zlomky v průběžných cestách, a konečně síťové modely pro celočíselné programování, se zaměřením na přepravní a přiřazovací problémy.

Vyučovací metody

Přednášky
Cvičení (v učebně)

Anotace

Kurz bude vyučovat pokročilé techniky operačního výzkumu. Přednášky budou rozšiřovat základní algoritmus simplex o aplikaci omezených proměnných a revidovaný algoritmus simplex pro vyšší rychlost. Goal programming uvede aplikaci formulace více účelů v lineárním programování. Bude probráno celočíselné programování, které je rozšířením lineárního programování, ve kterém jsou všechny proměnné celočíselné. Celočíselné programování je důležitou technikou pro řešení přiřazovacích problémů. 3 závěrečná témata pokryjí branch and bound algoritmus pro celočíselné programování, cutting plane metodu, ve které mohou být využity zlomky v průběžných cestách, a konečně síťové modely pro celočíselné programování, se zaměřením na přepravní a přiřazovací problémy.

Povinná literatura:

1. Taha Hamdy (2010) Operations Research: An Introduction (9th Edition). ISBN-13: 978-0132555937. 2. Winston Wayne (2003) Operations Research: Applications and Algorithms. ISBN-13: 978-0534380588.

Doporučená literatura:

1. Pinedo M. (2012) Scheduling: Theory, Algorithms, and Systems. Springer. ISBN-13: 978-1461419860

Způsob průběžné kontroly znalostí během semestru

Podmínky udělení zápočtu: Vypracování úloh, které jsou součástí programu cvičení.

E-learning

Další požadavky na studenta

Další požadavky na studenta nejsou kladeny.

Minimální znalostní požadavky

Prerekvizity

Kód předmětuZkratkaNázevPovinnost
460-4062 OV Operační výzkum Doporučená

Korekvizity

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

Osnova předmětu

Kurz bude vyučovat pokročilé techniky operačního výzkumu. Přednášky budou rozšiřovat základní algoritmus simplex o aplikaci omezených proměnných a revidovaný algoritmus simplex pro vyšší rychlost. Goal programming uvede aplikaci formulace více účelů v lineárním programování. Bude probráno celočíselné programování, které je rozšířením lineárního programování, ve kterém jsou všechny proměnné celočíselné. Celočíselné programování je důležitou technikou pro řešení přiřazovacích problémů. 3 závěrečná témata pokryjí branch and bound algoritmus pro celočíselné programování, cutting plane metodu, ve které mohou být využity zlomky v průběžných cestách, a konečně síťové modely pro celočíselné programování, se zaměřením na přepravní a přiřazovací problémy. Témata probraná v přednáškách budou: 1. Omezené proměnné – Simplex algoritmus 2. Jednodimenzionální Cutting Stock problém 3. Dantzig-Wolfe algoritmus rozkladu 4. Primal-Dual algoritmus 5. Goal Programming – formulace 6. Celočíselné programování 7. Branch and Bound algoritmus 8. Cutting Plane algoritmus    9. Modely přepravních sítí   10. Model sítě přiřazení   11. Problém nejkratší cesty   12. Successive Shortest Path problém   13. Maximum Flow problém   14. Minimum Cost Flow problém Cvičení (PC učebna): 1. Vývoj rámce pro algoritmus simplex 2. Aplikace algoritmu simplex pro omezené proměnné 3. Programování Dantzig-Wolfe dekompozičního algoritmu 4. Programování Primal-Dual algoritmu 5. Úvod do celočíselného programování 6. Programování jednoduchého modelu celočíselného programování 7. Aplikace celočíselného programování na problém plánování 8. Aplikace celočíselného programování na logistický problém 9. Úvod do Branch and Bound algorithm 10. Programování Branch and Bound algoritmu 11. Aplikace Branch and Bound algoritmu na problém plánování 12. Aplikace Branch and Bound algoritmu na problém směrování 13. Programování Cutting Plane algoritmu 14. Aplikace Cutting Plane algoritmu na problém celočíselného programování

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

Prezenční forma (platnost od: 2015/2016 zimní semestr)
Název úlohyTyp úlohyMax. počet bodů
(akt. za podúlohy)
Min. počet bodů
Zápočet a zkouška Zápočet a zkouška 100 (100) 51
        Zápočet Zápočet 45  20
        Zkouška Zkouška 55  6
Rozsah povinné účasti:

Zobrazit historii

Výskyt ve studijních plánech

Akademický rokProgramOborSpec.FormaJazyk výuky Konz. stř.RočníkZLTyp povinnosti
2017/2018 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika P čeština Ostrava 2 volitelný odborný stu. plán
2017/2018 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika K čeština Ostrava 2 volitelný odborný stu. plán
2016/2017 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika P čeština Ostrava 2 volitelný odborný stu. plán
2016/2017 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika K čeština Ostrava 2 volitelný odborný stu. plán
2015/2016 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika P čeština Ostrava 2 volitelný odborný stu. plán
2015/2016 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika K čeština Ostrava 2 volitelný odborný stu. plán

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

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