PA163: Domácí úkol 22.10.2019
10 bodů
1. Ukažte podrobně, jak pracuje algoritmus AC-3 na následujícím příkladu:
• proměnná X má doménu {0,1,2,3}, proměnná Y má doménu {1,2,3,4} a proměnné Z, V mají doménu {0,1, 2},
• X = Y, X < V, Z Ý Y.
Jaké by nastaly rozdíly při použití algoritmu AC-1?
2 body
2. Ukažte podrobně, jak pracuje algoritmus PC-2 na následujícím příkladu:
• proměnná A má doménu {0,1,2, 3,4}, proměnná B má doménu {1, 2, 3,4, 5} a proměnná C mají doménu {2,3,4},
• A = B, A > C.
3 body
3. Napište řešení následujícího příkladu v OPL. Kód řádně okomentujte komentáři bez diakritiky, na prvním řádku každého souboru uveďte (v komentářích) Vaše jméno a příjmení. Odevzdejte zip soubor prijmeni.zip, ve kterém bude adresář nazvaný prijmeni se soubory prijmeni.dat, prijmeni.mod, .project a .oplproject.
Projekt v (IBM ILOG CPLEX) Optimization Studiu pojmenujte „prijmeni". Soubor prijmeni.zip připravte v Optimization Studiu pomocí Soubor -> Exportovat -> Obecné -> Archivní soubor. Všechna vstupní data musí být uvedena v souboru prijmeni.dat.
Problém: Máme zadáno několik servisních poboček (servisů), které odebírají zboží z distribučních center. Cílem řešení je určit, která distribuční centra budou nově otevřena. Chceme přitom maximalizovat zisk z nově otevřených distribučních center, přičemž je zadána (1) cena za otevření každého z distribučních center a (2) možný zisk z otevření jednotlivých distribučních center pro každý servis. Servisy přitom mohou využívat jen některá z distribučních center a je tak stanoven limit na minimální počet nově otevřených distribučních center pro každý servis. Pro každý servis zároveň musíme dosáhnout stanovený minimální zisk z otevřených center.
Řešení otestujte na následujícím problému (tj. musíte použít odpovídající datovou sadu prijmeni.dat, kterou odevzdejte jako součást řešení):
• počet možných distribučních center: 8,
• počet servisů: 3,
• minimální počet nově otevřených center pro každý servis: 2,
• minimální zisk z otevřených center pro každý servis: 5,
• cena za otevření prvních čtyř center: 3, druhých čtyř center: 5,
• první servis může použit centra 1,2,4,7 se ziskem 2,3,2,4; druhý servis může použit centra 1,6,7,8 se ziskem 2,2,3,2; třetí servis může použit centra 2,3,5 se ziskem 5,6,2.
5 bodů
Pokyny pro odevzdání
• Dodržujte prosím všechny pokyny pro odevzdávání, jinak riskujete, že domácí úkol nebude opravován a obdržíte nulový počet bodů.
• Úlohy jsou odevzdávány pomocí dvou odevzdáváren do 3.11.2019.
• První a druhý příklad uložte do odevzdávárny Domácí úkol 1: příklad 1 a 2. Všechny strany musí obsahovat vaše jméno a číslo stránky v záhlaví dokumentu.
Řešení 1. a 2. příkladu je preferováno v elektronické formě
- elektronická řešení 1. a 2. příkladu odevzdávejte výhradně v PDF, odevzdávaný soubor pojmenujte prijmeni.pdf,
- pokud vyřešíte 1. a 2. příklad na papíře, musíte odevzdat do stanoveného termínu kopii úlohy do odevzdávárny, v tom případě ale také hned na nejbližší přednášce odevzdejte originál (pokud tak neučiníte, příklady vám nebudou započítány). Odevzdávaný soubor pojmenujte prijmeni.*.
• Řešení 3. příkladu je vyžadováno pouze v elektronické formě. Třetí příklad uložte do odevzdávárny Domácí úkol 1: příklad 3 dle pokynů u tohoto příkladu.
Pro řešení v OPL odevzdáváte soubor prijmeni.zip.
2