PA163: Domácí úkol 2.12.2019
10 bodů
1. Zakreslete graf stavového prostoru pro řešení problému
• proměnné: XI e {1, 3}, X2, X3, X4, X5 € {1, 2}
• omezení: cl : XI ^ X3,    c2 : XI ^ X5,    c3 : X3 7^ X5
algoritmem Gaschnigova backjumpingu při uspořádání proměnných XI, X2, X3, X4, X5 a při uspořádání hodnot od nejmenší k největší. U všech uzlů, které nejsou konzistentní, uveďte omezení, které nekonzistenci způsobilo. U všech uzlů i, kde dojde ke skoku zpět uveďte hodnotu latesti. 2 body
2. Na prvním stromě ukažte, které větve projde algoritmus omezení počtu návratů (bounded-backtrack search) BBS(12) a jak se započítávají návraty.
Na druhém stromě uveďte průchod stromu pro algoritmus improved limited discrepancy search ILDS(3) a v jakém pořadí jsou nalezena řešení.
U obou algoritmů použijte výběr hodnot zleva.
lbod
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 připravený v Optimization Studiu, 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". Všechna vstupní data musí být uvedena v souborech prijmeni.dat.
Problém: Cílem je rozvrhování lékařských vyšetření pacientů v nemocnici. Každý pacient musí absolvovat vyšetření zadaného typu, která probíhají na různých pracovištích. Cílem řešení je pro každé vyšetření pacienta určit, ve kterém čase bude probíhat a které pracoviště bude vyšetření realizovat. Jsou zadány následující požadavky.
(a) Vyšetření jednoho pacienta se nesmí překrývat.
(b) Vyšetření na jednom pracovišti se nesmí překrývat.
(c) Každý typ vyšetření má stanovenu délku provádění a pracoviště, na kterých může být prováděno.
(d) Některý typ vyšetření musí proběhnout před realizací jiného typu vyšetření (pokud je pacient absolvuje oba). Jsou proto zadány dvojice typů vyšetření určující, které vyšetření musí být realizováno před zahájením dalšího vyšetření.
Vyšetření pacientů se závažnějším typem onemocnění by měla být dokončena dříve, aby mohli dříve nastoupit na operaci. Cílem je tedy minimalizovat vážený součet dokončení nejpozdějších vyšetření pacientů.
Příklad jednoduchého zadání s řešením (neodevzdává se!):
• počet pacientů 2, počet typů vyšetření 2, počet pracovišť 2;
• doby trvání vyšetření daného typu: 1, 2;
• pracoviště pro vyšetření daného typu: 1:1,2, 2:1;
• typy vyšetření pro pacienty: 1:1,2, 2:1;
• priority pacientů: 1,10;
• precedence pro dané typy vyšetření: 1 před 2;
• optimální řešení s kvalitou 13: pacient, vyšetření, čas, pracoviště 1,1,0,1; 1,2,1,2; 2,1,0,2 nebo druhé optimální řešení 1,1,0,2; 1,2,1,2; 2,1,0,1
Příklad zadání pro odevzdání:
• počet pacientů 10, počet typů vyšetření 3, počet pracovišť 4;
• doby trvání vyšetření daného typu: 2, 2, 3;
• pracoviště pro vyšetření daného typu: 1:1,3, 2:2,4, 3:1,2,3;
• typy vyšetření pro pacienty: 1:1,2, 2:2,3, 3:1,3,4:1,2,3, 5:1,2,3, 6:2, 7:1, 8:1,2, 9:3,10:2,3;
• priority pacientů: 1,10,10,100,100,10,10,10,1,1;
• precedence pro dané typy vyšetření: 1 před 2, 2 před 3. 7 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 15.12.
• První dva příklady uložte do odevzdávárny „Domácí úkol 2: 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 odevzdejte originál na nejbližší přednášce (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 2: příklad 3" dle pokynů u tohoto příkladu.
Pro řešení v OPL odevzdáváte soubor prijmeni.zip.
2