Optimalizační metody 15.5.2019 2. záp. písemka
Napsal: 16. 5. 2019 09:05
2. písemka z lineárního programování
Písemku vypracovávejte samostatně. Nezapoměňte všude uvádět postupy, může vás to zachránit v případě numerické chyby. Všechna tvrzení je třeba řádně zdůvodnit, věty z přednášky či cvičení však dokazovat nemusíte, vždy pouze uveďte, co a kde používáte.
Příklady mohou být rozdílně složité a proto doporučujeme nejdříve pročíst všechna zadání a začít od těch, které vám budou připadat jednodušší. Hodně štěstí!
Jméno/Přezdívka:
Příklad první
Formulujte pomocnou úlohu simplexové metody a s její pomocí nalezněte přípustné bázické řešení lineárního programu, nebo ukažte, že je program nepřípustný:
Příklad druhý
Pomocí simplexové metody vyřešte následující úlohu lineárního programování:
Jako výchozí přípustné řešení užijte vektor .
Příklad třetí
Problém Minimálního pokrytí grafu klikami je zadán následovně: Pro daný neorientovaný graf chceme nalézt co nejméně klik (uplných podgrafů) tak, že každý vrchol zadaného grafu bude patřit do nějaké kliky a zároveň každá taková klika používá pouze hrany z grafu.
Dualizujte následující relaxovaný celočíselný program pro tento problém ( je počet vrcholů a značí množinu ):
Příklad čtvrtý
Pro zadaný lineární program nalezněte optimální řešení s využitím toho, že optimální řešení duálního programu je :
Součástí zadání byly ještě nějaké užitečné věty a definice.
Písemku vypracovávejte samostatně. Nezapoměňte všude uvádět postupy, může vás to zachránit v případě numerické chyby. Všechna tvrzení je třeba řádně zdůvodnit, věty z přednášky či cvičení však dokazovat nemusíte, vždy pouze uveďte, co a kde používáte.
Příklady mohou být rozdílně složité a proto doporučujeme nejdříve pročíst všechna zadání a začít od těch, které vám budou připadat jednodušší. Hodně štěstí!
Jméno/Přezdívka:
Příklad první
Formulujte pomocnou úlohu simplexové metody a s její pomocí nalezněte přípustné bázické řešení lineárního programu, nebo ukažte, že je program nepřípustný:
Příklad druhý
Pomocí simplexové metody vyřešte následující úlohu lineárního programování:
Jako výchozí přípustné řešení užijte vektor .
Příklad třetí
Problém Minimálního pokrytí grafu klikami je zadán následovně: Pro daný neorientovaný graf chceme nalézt co nejméně klik (uplných podgrafů) tak, že každý vrchol zadaného grafu bude patřit do nějaké kliky a zároveň každá taková klika používá pouze hrany z grafu.
Dualizujte následující relaxovaný celočíselný program pro tento problém ( je počet vrcholů a značí množinu ):
Příklad čtvrtý
Pro zadaný lineární program nalezněte optimální řešení s využitím toho, že optimální řešení duálního programu je :
Součástí zadání byly ještě nějaké užitečné věty a definice.