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í
Převeďte následující lineární program do rovnicového tvaru, tj. do tvaru za podmínek ,.
Příklad druhý
Navrhněte celočíselný lineární program, který vyřeší problém Set Splitting:
Jsou dány podmnožiny množiny a váhy prvků . Cílem je nalézt množinu s co nejmenší váhou, která dělí každou množinu (tedy pro každé platí, že a ). Váha množiny je součet vah jejich prvků.
Příklad třetí
Newyorská radnice se pro zvýšení bezpečnosti rozhodla postavit novou policejní stanici. Za účelem určení vhodné polohy stanice vytipovala radnice míst, kde je pravděpodobně kriminální aktivita. Místa se nacházejí na souřadnicích pro .
- Vaším úkolem je navrhnout lineární program, který určí umístění stanice minimalizující průměrnou dojezdovou dobu na tato místa. Dojezdová doba je přímo úměrná vzdálenosti bodů v Manhattanské metrice, tj. vzdálenost bodů a je .
- Jak by se změnil lineární program, pokud bychom minimalizovali maximální dojezdovou dobu?
Nechť jsou konvexní množiny. Dokažte, že pro libovolné je množina konvexní, přičemž:
Příklad pátý
Máme mnohostěn v určený jako konvexní obal vrcholů
Pro čtveřici vrcholů spočtěte rovnicový popis nadroviny, na které všechny 4 body leží. Rozhodněte také, zda je tato nadrovina sečná, tečná, nebo mimoběžná vůči zadanému mnohostěnu.
Užitečné definice a věty:
D: Množina je afinní prostor, pokud je tvaru pro nějaký vektorový prostor a vektor . Dimenze afinního prostoru je rovna dimenzi jeho přidruženého vektorového prostoru .
D: Konvexní mnohostěn v je průnik konečně mnoha poloprostorů. Alternativně můžeme říci, že konvexní mnohostěn je množina bodů tvaru pro nějakou reálnou matici a reálný vektor .
D: Dimenze mnohostěnu je rovna dimenzi nejmenšího afinního prostoru , který obsahuje celý mnohostěn .
D: Množina se nazývá konvexní množinou, pokud . Jinak rečeno, každá úsečka se dvěma konci v musí mít každý bod obsažený v .
D: Mějme mnohostěn a nadrovinu . Podle průniku s mnohostěnem označujeme nadrovinu jako
- tečnou, pokud celé leží v jednom z uzavřených poloprostorů určených a průnik je neprázdný,
- sečnou, pokud je průnik s každým z otevřených poloprostorů určených neprázdný, a nebo
- mimoběžnou, pokud není ani tečná ani sečná.
T: (Věta o oddělování) Buď omezená uzavřená konvexní množina a uzavřená konvexní množina. Pokud , tak existuje nadrovina taková, že a (tj. odděluje a ).
V příloze jsou ještě nějaké další písemky, na které jsem narazil při učení na zápočtovou písemku.