Rešene naloge pri predmetu OPERACIJSKE RAZISKAVE Študijsko gradivo za študente 2. letnika Finančne matematike Janoš Vidali Ljubljana, 2021 NASLOV: Rešene naloge pri predmetu OPERACIJSKE RAZISKAVE PODNASLOV: Študijsko gradivo za študente 2. letnika Finančne matematike AVTOR: Janoš Vidali IZDAJA: 1. izdaja ZALOŽNIK: samozaložba KRAJ: Ljubljana LETO IZIDA: 2021 AVTORSKE PRAVICE: Janoš Vidali CENA: publikacija je brezplačna NATIS: elektronsko gradivo, dostopno na naslovu https://jaanos.github.io/or-zbirka/pdf/or-gradivo.pdf To gradivo je ponujeno pod licenco Creative Commons Priznanje avtorstva – Deljenje pod enakimi pogoji 4.0 Slovenija (ali novejšo različico). To pomeni, da se tako besedilo, slike, grafi in druge sestavine dela lahko prosto distribuirajo, reproducirajo, uporabljajo, priobčujejo javnosti in predelujejo pod pogojem, da se jasno in vidno navede avtorja in naslov tega dela in da se v primeru spre-membe, preoblikovanja ali uporabe tega dela v svojem delu lahko distribuira predelava le pod licenco, ki je enaka tej. Podrobnosti licence so dostopne na spletni strani https://creativecommons.si ali na Inštitutu za intelektualno lastnino, Streliška 1, 1000 Ljubljana. Kataložni zapis o publikaciji (CIP) pripravili v Narodni in univerzitetni knjižnici v Ljubljani COBISS.SI-ID 53559811 ISBN 978-961-07-0416-4 (pdf) 1 Kazalo Predgovor 3 1 Naloge 4 1.1 Zahtevnost algoritmov . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.2 Celoštevilsko linearno programiranje . . . . . . . . . . . . . . . . . . 6 1.3 Teorija odločanja . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.4 Dinamično programiranje . . . . . . . . . . . . . . . . . . . . . . . . . 18 1.5 Algoritmi na grafih . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 1.6 CPM/PERT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 1.7 Upravljanje zalog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 2 Rešitve 43 2.1 Zahtevnost algoritmov . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 2.2 Celoštevilsko linearno programiranje . . . . . . . . . . . . . . . . . . 47 2.3 Teorija odločanja . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 2.4 Dinamično programiranje . . . . . . . . . . . . . . . . . . . . . . . . . 73 2.5 Algoritmi na grafih . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 2.6 CPM/PERT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 2.7 Upravljanje zalog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 Literatura 126 2 Predgovor Na pobudo izr. prof. dr. Arjane Žitnik, ki od študijskega leta 2017/18 predava predmet Operacijske raziskave za študente 2. letnika Finančne matematike, sem kot asistent pri tem predmetu začel zbirati naloge iz vaj, kolokvijev in izpitov ter njihove rešitve. Pričujočo zbirko sestavljajo predvsem naloge, ki sem jih sam sestavil (ali dopolnil) od študijskega leta 2016/17 naprej, ko sem prevzel vodenje vaj pri tem predmetu. V pripravi je tudi obsežnejša zbirka, ki bo zajemala tudi naloge, ki so se pojavile na vajah, kolokvijih in izpitih v prejšnjih letih. Na tem mestu bi se rad zahvalil prof. Arjani Žitnik za spodbudo, mojemu predhodniku na asistentskem mestu Davidu Gajserju, ki je sestavil nalogi 6.1 in 6.3, ter študentom, ki so prispevali nekatere rešitve, in sicer Evi Deželak (rešitve nalog 3.7, 5.1, 5.2, 5.3 in 5.10), Nejcu Ševerkarju (rešitvi nalog 5.5 in 5.9), Anji Trobec (rešitev naloge 6.7) in Janu Šifrerju (popravek rešitve naloge 5.5). Omenim naj še, da sta nalogi 4.1 in 5.3 vzeti iz vira [1], ki je služil tudi kot navdih za nekatere naloge iz razdelka 1.5. 3 1 Naloge 1.1 Zahtevnost algoritmov Naloga 1.1. Vir: Vaje OR 21.2.2018 Naj bo A[1... n][1... n] matrika (tj., seznam seznamov) dimenzij n × n. Dan je spodnji program: for i = 1,..., n do for j = i + 1,..., n do A[ i ][ j ] ← A[ j ][ i] end for end for (a) Kaj počne zgornji program? (b) Oceni število korakov, ki jih opravi zgornji program, v odvisnosti od parametra n. Naloga 1.2. Vir: Vaje OR 21.2.2018 Naj bo `[1... n] seznam, ki ima na začetku vse vrednosti nastavljene na 0. Dan je spodnji program: i ← 1 while i ≤ n do `[ i ] ← 1 − `[ i ] if `[ i ] = 1 then i ← 1 else i ← i + 1 end if end while (a) Kaj se dogaja, ko teče zgornji program? (b) Oceni število korakov, ki jih opravi zgornji program, v odvisnosti od parametra n. Naloga 1.3. Vir: Vaje OR 21.2.2018 Algoritem BUBBLESORT uredi vhodni seznam `[1... n] tako, da zamenjuje sosed-nje elemente v nepravem vrstnem redu: function BUBBLESORT( `[1 . . . n]) z ← n while z > 1 do y ← 1 for i = 2,..., z do if `[ i − 1] > `[ i ] then `[ i − 1], `[ i ] ← `[ i ], `[ i − 1] 4 y ← i end if end for z ← y − 1 end while end function (a) Izvedi algoritem na seznamu [7,11,16,7,5]. (b) Določi časovno zahtevnost algoritma. Naloga 1.4. Vir: Vaje OR 12.10.2016 Algoritem MERGESORT uredi vhodni seznam tako, da ga najprej razdeli na dva dela, nato vsakega rekurzivno uredi, nazadnje pa zlije dobljena urejena seznama. (a) S psevdokodo zapiši algoritem MERGESORT. (b) Izvedi algoritem na seznamu [7,11,16,7,5,0,14,1,19,13]. (c) Določi časovno zahtevnost algoritma. Naloga 1.5. Vir: Vaje OR 21.2.2018 Število n želimo razcepiti na dva netrivialna celoštevilska faktorja, kar storimo s sledečim algoritmom: function RAZCEP( n) p for i = 2,...,b n c do if n/ i je celo število then return ( i , n/ i ) end if end for return n je praštevilo end function Določi časovno zahtevnost algoritma. Ali je ta algoritem polinomski? Naloga 1.6. Vir: Vaje OR 21.2.2018 p Zapiši rekurziven algoritem, ki na vhod dobi celo število n in teče v času O( n). Uporaba korenjenja ni dovoljena. 5 1.2 Celoštevilsko linearno programiranje Naloga 2.1. Vir: Vaje OR 12.10.2016 Napiši linearni program, ki modelira iskanje največjega prirejanja v dvodelnem grafu. Naloga 2.2. Vir: Izpit OR 15.12.2016 Na oddelku za matematiko je zaposlenih n asistentov, ki jim moramo dodeliti vaje pri m predmetih. Za asistenta i (1 ≤ i ≤ n) naj bosta ai in bi najmanjše in največje število ur, ki jih lahko izvaja, ter Ni ⊆ {1,2,..., m} množica predmetov, ki jih ne želi izvajati. Za predmet j (1 ≤ j ≤ m) naj bo cj število skupin za vaje pri predmetu, ter u j število ur vaj na skupino. Poleg tega vemo, da sta asistenta p in q skregana, zato pri nobenem predmetu ne smeta oba izvajati vaj. Predmete želimo asistentom dodeliti tako, da bomo ob upoštevanju njihovih želja minimizirali največje število različnih predmetov, ki smo jih dodelili posamezenmu asistentu. Zapiši celoštevilski linearni program, ki modelira zgoraj opisani problem. Namig: napiši program s spremenljivko t , ki je dopusten natanko tedaj, ko vsak asistent dobi največ t različnih predmetov, in potem minimimiziraj t. Naloga 2.3. Vir: Izpit OR 31.1.2017 Imamo m opravil, ki jih želimo razporediti med n strojev. Vsak stroj lahko hkrati opravlja le eno opravilo, vsa opravila pa trajajo eno časovno enoto, neodvisno od stroja. Če stroj i (1 ≤ i ≤ n) uporabimo za vsaj eno opravilo, plačamo ceno ci (cena ostane enaka, če na istem stroju naredimo več opravil). Skupni stroški ne smejo preseči količine C . Dani sta še množici parov P in S, pri čemer ( j, k) ∈ P pomeni, da mora biti opravilo j dokončano pred začetkom opravila k, ( j, k) ∈ S pa pomeni, da se opravili j in k ne smeta izvajati hkrati. Imamo še dodaten pogoj, ki zahteva, da je lahko v posamezni časovni enoti lahko aktivnih največ A strojev. Minimizirati želimo čas dokončanja zadnjega stroja. Zapiši celoštevilski linearni program, ki modelira zgoraj opisani problem. Naloga 2.4. Vir: Izpit OR 10.7.2017 Za hitrejše nalaganje posnetkov na YouTubu se uporabljajo krajevni strežniki, do katerih lahko uporabniki na določeni lokaciji hitreje dostopajo kakor do glavnega strežnika, ki vsebuje vse posnetke. Vendar pa imajo krajevni strežniki omejen prostor, zato je potrebno ugotoviti, kateri posnetki naj se naložijo na katere krajevne strežnike. Denimo, da imamo poleg glavnega strežnika še k krajevnih strežnikov, m in-ternetnih ponudnikov in n posnetkov. Naj bo ch (1 ≤ h ≤ k) prostor v megabajtih, ki je na voljo na krajevnem strežniku h. Z indeksom 0 označimo glavni strežnik – lahko torej predpostavljaš c 0 = ∞. Nadalje naj bo sj (1 ≤ j ≤ n) velikost posnetka j , prav tako v megabajtih, `hi (0 ≤ h ≤ k, 1 ≤ i ≤ m) latenca (zakasnitev pri pre-nosu v milisekundah) ponudnika i do strežnika h, in ri j (1 ≤ i ≤ m, 1 ≤ j ≤ n) 6 število zahtevkov za posnetek j , ki jih pričakujejo od ponudnika i . Vsi parametri so cela števila. Pri vsakem zahtevku bo posnetek poslan iz strežnika z najmanjšo latenco, ki vsebuje želeni posnetek. Lahko predpostavljaš, da ima za vsakega ponudnika glavni strežnik največjo latenco (torej ` 0 i ≥ `hi za vsaka 1 ≤ h ≤ k, 1 ≤ i ≤ m). Določiti želimo, katere posnetke naj naložimo na posamezen krajevni strežnik, da minimiziramo vsoto pričakovanih latenc pri vseh zahtevkih. Posamezen posnetek lahko seveda naložimo tudi na več krajevnih strežnikov, ali pa na nobenega (v tem primeru bo poslan iz glavnega strežnika). Zapiši celoštevilski linearni program, ki modelira zgoraj opisani problem. Naloga 2.5. Vir: Izpit OR 29.8.2017 Distributer ima A zabojev avokadov in B zabojev banan, ki jih bo prodal n tr-govcem. Trgovec i (1 ≤ i ≤ n) plača ai evrov za zaboj avokadov in bi evrov za zaboj banan, skupaj pa bo porabil največ ci evrov. Distributer bo zaboje dostavil s tovornjaki, v katerih je lahko največ K zabojev (ne glede na vsebino). Če nekemu trgovcu dostavi t zabojev, bo torej opravljenih d t/ K e voženj. Vsaka vožnja do trgovca i (ne glede na to, koliko je poln tovornjak) ga stane di evrov. Poleg tega bo trgovec p kupil samo banane ali samo avokade, trgovec q pa bo kupil vsaj en zaboj avokadov, če bo tudi trgovec r kupil vsaj en zaboj avokadov. Distributer želi zaboje razdeliti med trgovce tako, da bo maksimiziral svoj dobiček – torej vsoto cen, ki jih plačajo trgovci, zmanjšano za stroške dostave. Lahko predpostavljaš, da so vse cene pozitivne. Zapiši celoštevilski linearni program, ki modelira zgoraj opisani problem. Naloga 2.6. Vir: Kolokvij OR 23.4.2018 Pri izvedbi projekta bo potrebno narediti n nalog, ki jih bomo dodelili delavcem. Vsako nalogo bo opravil natanko en delavec, vsak delavec pa lahko hkrati izvaja samo eno nalogo. Naj bo ti ∈ N število časovnih enot, ki ga posamezen delavec potrebuje za dokončanje naloge i (1 ≤ i ≤ n). Vsaka naloga mora biti opravljena v enem kosu (če torej začnemo z nalogo i v času s, bo ta dokončana v času s + ti , brez možnosti prekinitve in kasnejšega dokončanja). Celoten projekt mora biti dokončan v času T . Dana je še množica parov S, kjer ( i , j ) ∈ S pomeni, da se naloga j ne sme začeti, preden se zaključi naloga i (lahko se pa j začne izvajati v trenutku, ko se i konča). Delavce bomo najeli preko podjetja za posredovanje dela, to pa nam zaračuna fiksno ceno na najetega delavca (za ustrezna plačila delavcem bodo tako poskrbeli oni). Minimizirati želimo torej število najetih delavcev. Zapiši celoštevilski linearni program, ki modelira zgoraj opisani problem. 7 Naloga 2.7. Vir: Izpit OR 11.6.2018 Avtobusno podjetje želi uvesti novo avtobusno linijo. Dan je neusmerjen enostaven graf G = ( V, E), katerega vozlišča predstavljajo postajališča, povezave pa ceste med njimi. Za vsako povezavo uv ∈ E poznamo še čas cuv ∈ N, v katerem avtobus pride od u do v. Dan je še seznam postajališč p 1, p 2,... pn ∈ V , ki jih linija mora obiskati v tem vrstnem redu – začeti mora v p 1 in končati v pn, na poti med dvema postajališčema iz seznama pa lahko obišče tudi druga postajališča. Linija lahko vsako postajališče obišče največ enkrat (ko doseže končno postajališče, se vrne po isti poti do začetnega). Skupno trajanje vožnje (v eno smer) je lahko največ T . Podjetje želi določiti linijo tako, da bo obiskala čim več postaj. Zapiši celoštevilski linearni program, ki modelira zgoraj opisani problem. Namig: poskrbi, da linija nima ciklov. Naloga 2.8. Vir: Izpit OR 5.7.2018 Nogometni klub pred novo sezono prenavlja svoj igralski kader. Naj bo A množica trenutnih igralcev kluba, B pa množica igralcev, za katere se v klubu zanimajo ( A in B sta disjunktni množici). Za vsakega igralca i ∈ A imajo s strani kluba j (1 ≤ j ≤ n) ponudbo v višini pi j ∈ N (če se klub j ne zanima za igralca i, lahko predpostaviš pi j = 0), za vsakega igralca i ∈ B pa bodo morali plačati odkupnino ri ∈ N, če ga hočejo pripeljati v klub. Vsakega igralca i ∈ A lahko seveda prodamo kvečjemu enemu klubu. Skupni stroški trgovanja (tj., razlika stroškov nakupov in dobička od odprodaj) ne smejo preseči S, število igralcev v klubu pa mora ostati enako kot pred trgovanjem. Za vsakega igralca i ∈ A ∪ B poznamo njegov količnik kvalitete qi , vsak pa pripada natanko eni izmed množic G (vratarji), D (branilci), M (vezni igralci) in F (napadalci). Število igralcev kluba v vsaki izmed teh množic se lahko spremeni (poveča ali zmanjša) za največ 1. Poleg tega lahko igralca a, b ∈ A prodamo le istemu klubu – ali pa oba igralca ostaneta v klubu. Doseči želimo, da bo kvaliteta kluba čim večja – maksimizirati želimo torej vsoto količnikov qi za igralce v klubu. Zapiši celoštevilski linearni program, ki modelira zgoraj opisani problem. Naloga 2.9. Vir: Kolokvij OR 19.4.2019 Na turnirju poleg tebe sodeluje še n igralcev, pri čemer se bo vsak igralec soočil z vsakim drugim igralcem v enem dvoboju. Vsak igralec na začetku dobi M žetonov, za katere se (po začetni fazi zbiranja informacij) vnaprej odloči, kako jih bo razdelil med dvoboje. V dvoboju zmaga igralec z večjim številom vloženih žetonov. Če oba igralca vložita enako število žetonov, je izid dvoboja izenačen. Zmagovalec dvoboja dobi 3 točke, poraženec 0 točk, v primeru izenačenega izida pa vsak dvobojevalec dobi 1 točko. Cilj vsakega igralca je zbrati čim večje število točk. (a) Denimo, da za vsakega igralca izveš, kako namerava igrati. Naj bo torej ci število žetonov, ki jih bo i -ti nasprotnik (1 ≤ i ≤ n) vložil v dvoboj proti tebi. 8 Svojo strategijo želiš načrtovati tako, da bi dosegel čim večje število točk. Zapiši celoštevilski linearni program, ki modelira ta problem. (b) Celoštevilskemu linearnemu programu iz prejšnje točke dodaj omejitve, ki modelirajo sledeče pogoje: • Proti nobenemu od nasprotnikov iz množice A ne smeš doseči izenačenega izida. • Izgubiš lahko kvečjemu proti dvema nasprotnikoma iz množice B. • Če izgubiš proti nasprotniku u, moraš proti nasprotnikoma v in w doseči vsaj 4 točke. • Več kot t žetonov lahko vložiš v največ k dvobojev. • Izgubiti moraš vsaj ` dvobojev. Naloga 2.10. Vir: Izpit OR 3.6.2019 V trgovini z oblačili sestavljajo ponudbo za poletno sezono. Odločijo se lahko za nakup kolekcij n različnih proizvajalcev, pri čemer za posamezen izvod kolekcije i -tega proizvajalca (1 ≤ i ≤ n) plačajo ceno ci evrov, od nje pa si obetajo zaslužek di evrov. Kolekcijo i-tega proizvajalca lahko kupijo v največ ki izvodih (vsak izvod je nedeljiva enota), z njeno prisotnostjo v ponudbi (ne glede na količino) pa si obetajo povečano vidnost in s tem dodaten zaslužek ei evrov (npr. iz prodaje stalne ponudbe in starih zalog). Za nakup kolekcij imajo na voljo C evrov, iz marketinških razlogov pa želijo kupiti kolekcije največ K različnih proizvajalcev. Poleg tega proizvajalec p zahteva, da če kupijo kak izvod njegove kolekcije, je morajo kupiti v vsaj toliko izvodih kot kolekciji proizvajalcev q in r skupaj (če pa ne kupijo nobenega izvoda kolekcije proizvajalca p, te omejitve ni). V trgovini želijo maksimizirati pričakovani dobiček (tj., razliko zaslužka od prodaje s stroški nakupa). Zapiši celoštevilski linearni program, ki modelira zgoraj opisani problem. Naloga 2.11. Vir: Izpit OR 27.8.2019 Glasbeni festival bo trajal m dni, vsak dan pa bo nastopilo k glasbenih skupin. Organizator izbira nastopajoče izmed n glasbenih skupin (kjer je n > km). Na voljo ima M evrov za plačilo glasbenikom, pri čemer i -ta skupina (1 ≤ i ≤ n) računa mi evrov za nastop, pripeljala pa bo ai j obiskovalcev, če bo nastopila j -ta po vrsti v dnevu (1 ≤ j ≤ k). Vsaka skupina lahko seveda nastopi samo enkrat, prav tako naenkrat nastopa samo ena skupina. V posameznem dnevu se skupine zvrstijo glede na njihovo ceno (tj., zadnja nastopa skupina, ki največ računa), organizator pa želi zagotoviti, da bo vsak dan festivala prišlo vsaj toliko ljudi kot prejšnji dan. Skupina r pogojuje svoj nastop s tem, da skupina s ne nastopa na festivalu. Skupina t bo nastopila samo kot glavna skupina (tj., zadnja v posameznem 9 dnevu), razen če nastopi neposredno pred skupino u (lahko predpostaviš, da velja mt ≤ mu) – ali pa sploh ne bo nastopila. Skupini v in w ne smeta nastopati na isti dan, saj se njuni oboževalci med seboj ne marajo. Organizator želi določiti spored tako, da bo na festival prišlo čim več ljudi. Zapiši celoštevilski linearni program, ki modelira opisani problem. Naloga 2.12. Vir: Izpit OR 22.6.2020 Iz kriznih žarišč COVID-19 po svetu se na Kitajsko vrača n strokovnjakov, ki jih želijo oblasti razporediti po m karantenskih centrih s kapacitetami k 1, k 2,..., km, P pri čemer velja m k h=1 h ≥ n. S pomočjo naprednih tehnologij so za vsak par strokovnjakov i , j ∈ {1,2,..., n} izračunali verjetnost pi j ∈ [0,1], da je prišlo do prenosa virusa med i in j (lahko predpostaviš, da za vsaka i , j velja pi j = p ji ter pii = 0). Poiskati želijo tako razporeditev, da bo vsota vrednosti pi j vseh parov ( i , j ), ki bodo nastanjeni v istem karantenskem centru, čim manjša. Pri tem imajo nekaj omejitev. Identificirali so množico A strokovnjakov, ki so se nahajali na območjih, kjer je prišlo do mutacije virusa – ti ne smejo biti nastanjeni skupaj s strokovnjaki izven množice A (lahko so pa člani množice A nastanjeni po različnih centrih). Poleg tega so sestavili množico B parov strokovnjakov v bližnjem sorodstvu – za vsak par ( i , j ) ∈ B velja, da mora biti nastanjen v istem centru. Zapiši celoštevilski linearni program, ki modelira opisani problem. Namig: uporabi spremenljivke, ki za par oseb povedo, ali se nastanita v nekem centru. 10 +1 min? bus 1, 6 K FF 6 min 5 min bus 1, 6 bus 14 +3 min? +2 min? ŠD FE 4 min 4 min peš 2 min FMF bus 1 Slika 1: Shema možnih poti za nalogo 3.1. 1.3 Teorija odločanja Naloga 3.1. Vir: Izpit OR 15.12.2016 Mudi se ti na izpit, a ravno v trenutku, ko prideš na postajo Konzorcij, odpelje avtobus številka 1. Na prikazovalniku se izpiše, da bo naslednji avtobus številka 1 prispel čez 10 minut, naslednji avtobus številka 6 čez 6 minut, naslednji avtobus številka 14 pa čez 2 minuti. Avtobusa 1 in 6 ob ugodnih semaforjih potrebujeta 6 minut do postaje pri FE, pri čemer se lahko čas vožnje zaradi rdeče luči na semaforju pri FF podaljša za 1 minuto. Verjetnosti, da bo rdečo luč imel avtobus 1, da bo rdečo luč imel avtobus 6, ter da bosta oba avtobusa imela zeleno luč, so enake 1/3 (zaradi majhnega razmaka se ne more zgoditi, da bi oba avtobusa naletela na rdečo luč). Avtobus številka 1 nadaljuje pot do postaje pri FMF, za kar potrebuje še 2 minuti. Avtobus številka 14 potrebuje 5 minut do postaje pri študentskih domovih, od tam pa greš peš do postaje pri FE, za kar potrebuješ še 4 minute. Pri tem prečkaš železnico – če mimo pripelje vlak (kar se zgodi z verjetnostjo 0.05), se čas hoje podaljša za 3 minute. Ko prideš na postajo pri FE (ne glede na to, ali si prišel z avtobusom 6 ali 14), te čakajo še 4 minute hoje do FMF, vendar moraš najprej prečkati Tržaško cesto. Če je na semaforju rdeča luč (kar se zgodi z verjetnostjo 0.9, neodvisno od drugih dogodkov), se lahko odločiš, da 2 minuti počakaš na zeleno luč in potem nadaljuješ peš, ali pa da greš nazaj do postaje in počakaš na avtobus številka 1 (ki bo, tako kot prej, vozil še 2 minuti do FMF). Kakšne bodo tvoje odločitve, da bo pričakovano trajanje poti do FMF čim krajše? Nariši odločitveno drevo in odločitve sprejmi na podlagi izračunanih verjetnosti! Glej sliko 1 za shemo možnih poti. 11 Naloga 3.2. Vir: Izpit OR 31.1.2017 Dve podjetji bosta predstavili konkurenčna izdelka. Možnost imaš kupiti delnice prvega podjetja za ceno 10000e ali delnice drugega podjetja po ceni 5000e, lahko pa se seveda odločiš tudi, da delnic ne kupiš. Ocenjuješ, da bo z verjetnostjo 0.4 uspelo prvo podjetje, z verjetnostjo 0.1 bo uspelo drugo podjetje, z verjetnostjo 0.5 pa ne bo uspelo nobeno izmed njiju (ne more se zgoditi, da bi obe uspeli). Ob uspehu prvega podjetja se bo vrednost njihovih delnic potrojila, ob uspehu drugega podjetja pa se bo vrednost njihovih delnic popeterila – če si lastiš delnice uspešnega podjetja, jih torej lahko prodaš, pri čemer bo torej dobiček enak dvakratniku oziroma štirikratniku vloženega zneska. Delnic neuspešnega podjetja ne bo želel nihče kupiti, tako da je v tem primeru vloženi znesek izgubljen. Za mnenje lahko povprašaš tržnega izvedenca, ki bo po opravljeni raziskavi povedal, katero od dveh podjetij ima večje možnosti za uspeh. Če bo uspešno prvo podjetje, bo to pravilno napovedal z verjetnostjo 0.8, če pa bo uspešno drugo podjetje, bo to pravilno napovedal z verjetnostjo 0.7. V primeru, ko podjetji ne bosta uspeli, bo z verjetnostjo 0.4 večje možnosti pripisal prvemu, z verjetnostjo 0.6 pa drugemu podjetju. Za svoje mnenje izvedenec računa 1000e. Kakšne bodo tvoje odločitve, da bo tvoj pričakovani dobiček po odprodaji delnic čim večji? Nariši odločitveno drevo in odločitve sprejmi na podlagi izračunanih verjetnosti. Pričakovani dobiček tudi izračunaj. Naloga 3.3. Vir: Izpit OR 10.7.2017 Proti računalniškemu programu igraš Texas hold ’em poker. Pravila igre tukaj niso pomembna. Ker imaš dostop do kode programa, poznaš logiko, po kateri se ravna. V trenutni igri si vložil 30 žetonov, enako tudi nasprotnik. Nasprotnik z verjetnostjo 0.6 meni, da so odprte karte ugodnejše zate, z verjetnostjo 0.4 pa, da so ugodnejše zanj (sam si ne ustvariš nobenega mnenja). V prvem primeru je verjetnost, da so dejansko tvoje karte boljše, enaka 0.8, v drugem pa le 0.1. Nasprotnik se bo sedaj odločil, ali naj vloži še 10 žetonov. Sam se lahko nato odločiš, ali boš vložil 0, 10 ali 20 žetonov (skupni vložek bo torej 30, 40 ali 50 žetonov). Če je tvoj vložek manjši od nasprotnikovega, je igra izgubljena in izgubiš do sedaj vloženo. Če je tvoj vložek enak nasprotnikovemu, z nasprotnikom pogle-data karte in tako določita zmagovalca. Če je tvoj vložek višji od nasprotnikovega, ima ta možnost odstopiti (tako pridobiš nasprotnikov vložek), ali pa izenačiti, nakar se zmagovalec določi na podlagi kart. Če zmagaš, pridobiš nasprotnikov vložek, če izgubiš, pa izgubiš svojega. V spodnji tabeli so zbrane verjetnosti dogodkov v odvisnosti od nasprotnikovega mnenja glede kart. Verjetnosti navedenih dogodkov pri istem mnenju so med seboj neodvisne. 12 p 50 G D 1 − p −10 0.6 −5 B 4 p 30 H 0.4 E 1 −4 p −30 A −5 2 p 25 F C 1 −2 p −10 0 Slika 2: Odločitveno drevo za nalogo 3.4. dogodek \ nasprotnikovo mnenje ugodnejše karte zate za nasprotnika dejansko imaš boljše karte 0.8 0.1 nasprotnik vloži 10 žetonov po razkritju karte 0.3 0.8 nasprotnik izenači skupni vložek 40 žetonov 0.2 0.7 nasprotnik izenači skupni vložek 50 žetonov 0.1 0.8 Na primer: Pr[nasprotnik izenači skupni vložek 40 žetonov | | nasprotnikovo mnenje je “ugodnejše karte zate”] = 0.2. Kakšne bodo tvoje odločitve, da bo tvoj pričakovani dobiček po koncu igre čim večji? Nariši odločitveno drevo in odločitve sprejmi na podlagi izračunanih verjetnosti. Pričakovani dobiček tudi izračunaj. Naloga 3.4. Vir: Izpit OR 29.8.2017 Dano je odločitveno drevo s slike 2, pri čemer velja 0 ≤ p ≤ 1/4. Pričakovano vrednost želimo maksimizirati. Poišči optimalne odločitve in pričakovano vrednost v odvisnosti od vrednosti parametra p. Naloga 3.5. Vir: Kolokvij OR 23.4.2018 Mladi podjetnik je razvil inovativen izdelek in se odloča za nadaljnje korake pri njegovem trženju. Naenkrat lahko naroči izdelavo 500 izdelkov po ceni 10000e ali 1000 izdelkov po ceni 18000e, lahko se pa odloči tudi, da izdelave ne naroči. Podjetnik ocenjuje, da je izdelek tržno zanimiv z verjetnostjo 0.8. Odloča se, ali naj posamezen izdelek prodaja po ceni 50e ali 60e, pri čemer so v spodnji tabeli zbrana pričakovana števila prodanih kosov v odvisnosti od teh pogojev. 13 cena 50e cena 60e tržno zanimiv 650 550 tržno nezanimiv 250 100 Predpostavi, da se bodo prodali vsi izdelani kosi, če je število teh manjše od pričakovane prodaje pri danih pogojih. (a) Kako naj se podjetnik odloči, da bo pričakovani zaslužek čim večji? Nariši odločitveno drevo in ga uporabi pri sprejemanju odločitev. (b) V zadnjem trenutku je podjetnik izvedel, da bo Podjetniški pospeševalnik ob-javil razpis za nagrado za najboljši izdelek. Razpisni pogoji zahtevajo, da se za potrebo kontrole kvalitete izdela vsaj 1000 izdelkov, od katerih komisija izbere 20 za dejansko kontrolo, z ostalimi pa lahko prijavitelj prosto razpolaga. Če podjetnik zmaga, bo dobil nagrado v višini k, pri čemer k ∈ [1000e,5000e] še ni znan, poleg tega pa si obeta tudi 20% povečanje pričakovanega števila prodanih kosov (v vseh zgoraj omenjenih pogojih). Če ne zmaga, se pričako-vanja ne spremenijo. Podjetnik ocenjuje, da je verjetnost zmage enaka 0.6, če je izdelek tržno zanimiv, in 0.1, če izdelek ni tržno zanimiv. Naj se podjetnik prijavi na razpis? Nariši odločitveno drevo in odločitve sprejmi v odvisnosti od parametra k! Naloga 3.6. Vir: Izpit OR 11.6.2018 Podajamo se na pot v mesto na drugi strani gorovja. Lahko se odločimo za pot po cesti okoli gorovja, za kar bomo porabili 12 ur. Vendar pa nas najkrajša pot vodi čez prelaz, ki je eno uro stran od začetne lokacije. Žal pa so razmere v gorah nepredvidljive: ocenjujemo, da bo z verjetnostjo 0.2 prelaz čist in ga bomo lahko prevozili v 5 urah, z verjetnostjo 0.1 bo delno zasnežen in ga bomo prevozili v 9 urah, z verjetnostjo 0.7 pa bo neprevozen, zaradi česar se bomo morali vrniti na začetek in iti okoli gorovja (skupno trajanje poti bo v tem primeru torej 14 ur). Edini, ki nam lahko kakorkoli pomaga pri oceni vremenskih razmer na prelazu, je lokalni vrač, ki pa živi v dolini pod goro in ne uporablja sodobne teh-nologije, s katero bi ga lahko kontaktirali. Rade volje pa nam bo povedal, ali na gori vlada mir, če se na poti do prelaza ustavimo pri njem. Pogojne verjetnosti njegovega odgovora v odvisnosti od razmer na prelazu so podane v spodnji tabeli. ¡ ¯ ¢ P vračev odgovor ¯ razmere na prelazu čist delno zasnežen neprevozen na gori vlada mir 0.9 0.5 0.1 na gori divja vojna 0.1 0.5 0.9 Do vrača imamo eno uro vožnje, do prelaza pa potem še eno uro. Če se po obisku vrača odločimo za pot okoli gorovja, bomo za nadaljnjo pot porabili 12 ur. Kako se bomo odločili? Nariši odločitveno drevo in ga uporabi pri sprejemanju odločitev. Izračunaj tudi pričakovano trajanje poti. Glej sliko 3 za shemo možnih poti. 14 konec 11 ur 5 ali 9 ur (če je prevozen) vrač 1 ura 1 ura prelaz 1 ura 1 ura 1 ura začetek Slika 3: Shema možnih poti za nalogo 3.6. p 50 F 1 D − p −10 0.9 −5 B 30 1 − p G 0.1 E p −30 A −5 40 p + 20 0.5 C 0.5 0 Slika 4: Odločitveno drevo za nalogo 3.7. Naloga 3.7. Vir: Izpit OR 28.8.2018 Dano je odločitveno drevo s slike 4, pri čemer velja 0 ≤ p ≤ 1. Pričakovano vrednost želimo maksimizirati. Poišči optimalne odločitve in pričakovano vrednost v odvisnosti od vrednosti parametra p. 15 Naloga 3.8. Vir: Kolokvij OR 19.4.2019 V manjšem podjetju so razvili nov okus sadnega soka. Proizvedli so ga že 100000 litrov, ko so prejeli ponudbo multinacionalke, da odkupijo vso razpoložljivo količino po ceni 1e na liter. Če se ne odločijo za odprodajo, bodo sok sami pakirali in ponudili na trgu po ceni 3e na liter. Zagon pakiranja stane 1000e, pakiranje enega litra soka pa 0.5e. V podjetju ocenjujejo, da bo z verjetnostjo 0.7 produkt uspešen in ga bodo vsega prodali, z verjetnostjo 0.3 pa bo neuspešen in ga bodo prodali le 10000 litrov. Pri podjetju imajo na voljo ravno dovolj časa, da pred odločitvijo pakirajo in na regionalnem trgu ponudijo 1000 litrov soka po akcijski ceni 2.5e na liter. Ocenjujejo, da bi v primeru uspeha produkta z verjetnostjo 0.8 tudi akcija uspela in bi tako razprodali akcijske zaloge, v primeru neuspeha produkta pa bi se to zgodilo le z verjetnostjo 0.1. Če akcija ne bi uspela, bi prodali le 100 litrov soka. Če se po akcijski ponudbi odločijo za samostojno prodajo, bodo seveda morali še enkrat plačati stroške zagona pakiranja, v nasprotnem primeru pa bo multinacionalka odkupila preostalih 99000 litrov še nepakiranega soka. Opomba: količina, prodana v akcijski ponudbi, je vključena v končno prodano količino. Če torej v akciji prodajo vseh 1000 litrov soka po ceni 2.5e na liter, ga bodo v primeru neuspeha produkta v redni prodaji prodali le še 9000 litrov po ceni 3e na liter, v primeru uspeha pa še 99000 litrov. Kako naj se pri podjetju odločijo, da bo pričakovani zaslužek čim večji? Nariši odločitveno drevo in ga uporabi pri sprejemanju odločitev. Naloga 3.9. Vir: Izpit OR 3.6.2019 Podjetje je od konkurenta v finančnih težavah odkupilo tovarno čokolade, ki že nekaj časa ni bila v uporabi. Ker že prejemajo nova naročila, želijo v naslednjih 8 tednih proizvesti čim večjo količino čokolade. Ocenjujejo, da so z verjetnostjo 0.4 stroji v dobrem stanju in lahko proizvedejo 10000 kg čokolade na teden, z verjetnostjo 0.6 pa so v slabem stanju in lahko proizvedejo le 1000 kg čokolade na teden. Odločijo se lahko, da pred zagonom proizvodnje na strojih izvedejo servis. Izvedba servisa lahko poteka gladko in konča v enem tednu, ali pa se pojavijo težave in tako servis traja tri tedne (za proizvodnjo tako ostane le še 7 oziroma 5 tednov). Če so stroji v dobrem stanju, bo servis z verjetnostjo 0.9 potekal gladko, z verjetnostjo 0.1 pa se bodo pojavile težave – v obeh primerih pa bodo stroji po servisu ostali v dobrem stanju. Če so stroji v slabem stanju, bo servis z verjetnostjo 0.2 potekal gladko in jih tedaj z verjetnostjo 0.7 spravil v dobro stanje, z verjetnostjo 0.8 pa se bodo pojavile težave – tedaj je verjetnost, da bodo stroji po servisu v dobrem stanju, enaka 0.5. Po zagonu proizvodnje te zaradi previsokih stroškov ni mogoče predčasno prekiniti; stroški servisa pa niso pomembni, saj ga bodo morali izvesti kasneje, če se zanj ne odločijo takoj. Kako naj se v podjetju odločijo? Nariši odločitveno drevo in ga uporabi pri sprejemanju odločitev. Izračunaj tudi pričakovano količino proizvedene čoko-16 p 160 F D 1 − p 40 0.7 60 B 0.3 100 p + 30 2 p 120 A G 1 E − 2 p 20 0.6 50 C 0.4 70 Slika 5: Odločitveno drevo za nalogo 3.10. lade. Naloga 3.10. Vir: Izpit OR 19.6.2019 Dano je odločitveno drevo s slike 5, pri čemer velja 0 ≤ p ≤ 1/2. Pričakovano vrednost želimo minimizirati. Poišči optimalne odločitve in pričakovano vrednost v odvisnosti od vrednosti parametra p. Naloga 3.11. Vir: Izpit OR 4.6.2020 Na trajektu stoji 200 avtomobilov, vozovnica pa stane 35e. Pri družbi, ki upravlja trajekt, se lahko odločijo prodati 200, 201, 202 ali 203 vozovnice. Naj bo pi verjetnost, da i avtomobilov z vozovnicami ne pride do trajekta (tj., p 0 je verjetnost, da vsi pridejo): i 0 1 2 3 pi 0.3 0.4 0.2 0.1 Z vsakim avtomobilom, ki pride do trajekta in se ne more vkrcati, ima družba 60e stroškov (skupaj torej 25e izgube). (a) Koliko vozovnic naj proda družba, da bo imela čim večji dobiček? (b) Na trajektu je na voljo še eno mesto, ki pa ni najbolj varno1 – avtomobil, ki se pelje na njem, bo z verjetnostjo 0.001 (neodvisno od ostalih dejavnikov) med potjo padel v morje. V tem primeru ima družba dodatnih 40000e stroškov. Ali se družbi izplača uporabiti to mesto? Koliko vozovnic naj tedaj proda? 1Seveda bo to mesto ostalo prazno, če bo to mogoče. 17 1.4 Dinamično programiranje Naloga 4.1. Vir: [1, Exercise 6.14] Imamo pravokoten kos blaga dimenzij m × n, kjer sta m in n pozitivni celi števili, ter seznam k izdelkov, pri čemer potrebujemo za izdelek h pravokoten kos blaga dimenzij ah × bh ( ah, bh sta pozitivni celi števili), ki ga prodamo za ceno ch > 0. Imamo stroj, ki lahko poljuben kos blaga razreže na dva dela bodisi vodoravno, bodisi navpično. Začetni kos blaga želimo razrezati tako, da bomo lahko naredili izdelke, ki nam bodo prinašali čim večji dobiček. Pri tem smemo izdelati poljubno število kosov posameznega izdelka. Kose blaga lahko seveda tudi obračamo (tj., za izdelek h lahko narežemo kos velikosti ah × bh ali bh × ah). Zapiši rekurzivne enačbe za reševanje danega problema. Razloži, kaj predstavljajo spremenljivke, v kakšnem vrstnem redu jih računamo, ter kako dobimo optimalno rešitev. Naloga 4.2. Vir: Izpit OR 15.12.2016 Oceni časovno zahtevnost algoritma, ki sledi iz rekurzivnih enačb za nalogo 4.1. Reši problem za podatke m = 5, n = 3, k = 4, ( ah) kh=1 = (2,3,1,2), ( bh) kh=1 = (2,1,4,3) in ( ch) kh=1 = (6,3,5,7). Naloga 4.3. Vir: Izpit OR 31.1.2017 Dano je zaporedje n realnih števil a 1, a 2,..., an. Želimo poiskati strnjeno pod-zaporedje z največjim produktom – t.j., taka indeksa i , j (1 ≤ i ≤ j ≤ n), da je produkt ai ai+1 ··· aj−1 aj čim večji. (a) Zapiši rekurzivne enačbe za reševanje danega problema. Razloži, kaj predstavljajo spremenljivke, v kakšnem vrstnem redu jih računamo, ter kako dobimo optimalno rešitev. Namig: posebej obravnavaj pozitivne in negativne delne produkte. (b) Oceni časovno zahtevnost algoritma, ki sledi iz zgoraj zapisanih enačb. (c) S svojim algoritmom reši problem za zaporedje 0.9, −2, −0.6, −0.5, −2, 5, 0.1, 3, 0.5, −3 . Naloga 4.4. Vir: Izpit OR 10.7.2017 V podjetju imajo na voljo m milijonov evrov sredstev, ki jih bodo vložili v razvoj nove aplikacije. Denar bodo porazdelili med tri skupine. Naj bodo x 1, x 2 in x 3 količine denarja (v milijonih evrov), ki jih bodo dodelili razvijalcem, oblikovalcem in marketingu. Vrednosti x 1, x 2, x 3 niso nujno cela števila. Razvijalci morajo dobiti vsaj a 1 milijonov evrov, potencial, ki ga ustvarijo, pa je p 1 = n 1 + k 1 x 1. Oblikovalci morajo dobiti vsaj a 2 milijonov evrov, potencial, ki ga ustvarijo, pa je p 2 = n 2 + k 2 x 2. Marketing mora dobiti vsaj a 3 milijonov evrov, ustvari pa faktor 18 p 3 = n 3 + k 3 x 3. Pričakovani dobiček v milijonih evrov se izračuna po formuli d = ( p 1 + p 2) p 3. V podjetju bi radi sredstva porazdelili med skupine tako, da bo pričakovani dobiček čim večji. (a) Zapiši rekurzivne enačbe za reševanje danega problema. (b) Z zgoraj zapisanimi enačbami reši problem pri podatkih m = 15, a 1 = 4, n 1 = 3, k 1 = 1.5, a 2 = 3, n 2 = 4, k 2 = 2, a 3 = 2, n 3 = 0.4 in k 3 = 0.3. Naloga 4.5. Vir: Izpit OR 29.8.2017 V veliki multinacionalni korporaciji želijo, da bi se zakonodaja spremenila v njihov prid. V ta namen so najeli m lobistov, ki se bodo pogajali z n političnimi strankami, da pridobijo njihovo podporo pri spremembi zakonodaje. Vsak lobist se bo pogajal s samo eno stranko; k vsaki stranki lahko pošljejo več lobistov. Naj bo pi j (0 ≤ i ≤ m, 1 ≤ j ≤ n) verjetnost, da pridobijo podporo stranke j , če se z njo pogaja i lobistov (lahko predpostaviš pi−1, j ≤ pi j za vsaka i, j). Verjetnosti za različne stranke so med seboj neodvisne. Maksimizirati želijo verjetnost, da bodo lobisti pridobili podporo vseh n političnih strank. (a) Zapiši rekurzivne enačbe za reševanje danega problema. (b) Naj bo m = 6 in n = 3. K vsaki stranki želijo poslati vsaj enega lobista (tj., p 0 j = 0 za vsak j ), vrednosti pi j za i ≥ 1 pa so podane v spodnji tabeli. pi j 1 2 3 1 0.2 0.4 0.3 2 0.5 0.5 0.4 3 0.7 0.5 0.8 4 0.8 0.6 0.9 Za dane podatke reši problem z zgoraj zapisanimi enačbami. Naloga 4.6. Vir: Kolokvij OR 23.4.2018 Imamo zaporedje n polj, pri čemer je na i -tem polju zapisano število ai . Na voljo imamo še b n/2c domin, z vsako od katerih lahko pokrijemo dve sosednji polji. Vsaka domina je sestavljena iz dveh delov: na enem je znak +, na drugem pa znak −. Posamezno polje lahko pokrijemo z le eno domino; če sta pokriti dve sosednji polji, morata biti pokriti z različnima znakoma (bodisi z iste, bodisi z druge domine). Iščemo tako postavitev domin, ki maksimizira vsoto pokritih števil, pomnoženih z znakom na delu domine, ki pokriva število. Pri tem ni potrebno, da uporabimo vse domine. Primer je podan na sliki 6. (a) Zapiši rekurzivne enačbe za reševanje danega problema. Razloži, kaj predstavljajo spremenljivke, v kakšnem vrstnem redu jih računamo, ter kako dobimo optimalno rešitev. Namig: posebej obravnavaj dva primera glede na postavitev zadnje domine. 19 + − − + − + 6 3 −4 2 −3 5 9 1 2 Slika 6: Primer dopustnega (ne nujno optimalnega) pokritja za nalogo 4.6. Vsota tega pokritja je 3−(−4)−5+9−1+2 = 12. Če bi eno od zadnjih dveh domin obrnili (zamenjala bi se znaka), dobljeno pokritje ne bi bilo dopustno, saj bi dve zaporedni polji bili pokriti z enakima znakoma. (b) Oceni časovno zahtevnost algoritma, ki sledi iz zgoraj zapisanih enačb. (c) S svojim algoritmom poišči optimalno pokritje za primer s slike 6. Naloga 4.7. Vir: Izpit OR 5.7.2018 Vlagatelj ima na voljo 50 milijonov evrov sredstev, ki jih lahko porabi za donosno, a tvegano naložbo. Ocenjuje, da bi se mu ob uspehu naložbe vložek povrnil petkratno, verjetnost uspeha pa ocenjuje na 0.6. Zaradi tveganja se lahko odloči za zavarovanje naložbe, pri čemer ima ponudbi dveh zavarovalnic, ki mu proti plačilu ustrezne premije ponujata povračilo dela vložka, če bo naložba neuspešna. Vlagatelj lahko del sredstev obdrži tudi zase (tj., ga ne porabi za naložbo ali premijo). Naj bodo torej x 1, x 2, x 3 vrednosti v milijonih evrov, ki zaporedoma predstavljajo količine, ki jih vlagatelj obrži zase, porabi za naložbo, in plača za zavarovalniško premijo. Pričakovana vrednost naložbene strategije vlagatelja (tj., količina denarja, ki jo ima na koncu) je potem x 1 + x 2(0.6 · 5 + 0.4 q( x 3)), kjer q( x 3) predstavlja delež vložka, ki ga glede na vloženo premijo zavarovalnica povrne ob neuspehu naložbe. Vlagatelj ima dve ponudbi konkurenčnih zavarovalnic. Zavarovalnica Zvezna d.z.z. za premijo v višini x 3 milijonov evrov ponuja povračilo deleža 0.15 x 3 celotne naložbe v primeru neuspeha, pri čemer je največja možna premija 4 milijone evrov. Zavarovalnica Diskretna d.d.z. pa ponuja le tri možne premije: premija delež povračila ob neuspešni naložbi 1 milijon evrov 0.1 2 milijona evrov 0.35 3 milijoni evrov 0.5 Pogodbo smemo skleniti samo pri eni zavarovalnici. (a) Zapiši definicijo funkcije q( x) skupaj z izbiro najugodnejše zavarovalnice pri vsakem x. 20 (b) Zapiši rekurzivne formule za določitev strategije vlaganja, ki nam bo prinesla največji pričakovani dobiček. (c) S pomočjo zgornjih rekurzivnih enačb ugotovi, kako naj ravna vlagatelj, da bo imel čim večji dobiček. Naloga 4.8. Vir: Izpit OR 28.8.2018 Pri direkciji za ceste načrtujejo nov avtocestni odsek dolžine M kilometrov. Ob cesti želijo zgraditi počivališča tako, da je razdalja med dvema zaporednima počivališčema največ K kilometrov. Prav tako mora biti prvo počivališče največ K kilometrov od začetka, zadnje pa največ K kilometrov od konca avtocestnega odseka. Naj bodo x 1 < x 2 < ··· < xn možne lokacije počivališč (v kilometrih od začetka avtocestnega odseka), in ci (1 ≤ i ≤ n) cena izgradnje počivališča na lokaciji xi . Postavitev počivališč želijo izbrati tako, da bo skupna cena izgradnje čim manjša. (a) Zapiši rekurzivne enačbe za reševanje danega problema. Razloži, kaj predstavljajo spremenljivke, v kakšnem vrstnem redu jih računamo, ter kako dobimo optimalno rešitev. (b) Oceni časovno zahtevnost algoritma, ki sledi iz zgoraj zapisanih enačb. (c) S pomočjo rekurzivnih enačb reši zgornji problem za podatke M = 100, ( xi )8 i=1 = (5,12,22,34,49,65,83,91), K = 30, ( ci )8 i=1 = (18,11,21,16,23,15,19,13). Naloga 4.9. Vir: Kolokvij OR 19.4.2019 Gradimo avtocesto skozi puščavo in želimo zagotoviti, da bo v celoti pokrita z mobilnim signalom. Cesta je ravna in dolga n milj ( n ∈ Z), na vsako miljo pa imamo možnost postaviti bazno postajo z dosegom 1 miljo. Cena postavitve bazne postaje na i -ti milji je podana s parametrom ai (0 ≤ i ≤ n). Predpostaviš lahko, da so vse cene pozitivne. Pri obstoječi infrastrukturi je pokrita le začetna točka avtoceste (tj., milja 0). Poiskati želimo torej čim cenejšo postavitev baznih postaj, da je vsaka točka avtoceste pokrita s signalom. Primer: če postavimo postaji na milji 0 in 3, potem je interval (1, 2) nepokrit. Če pa npr. postajo namesto na milji 0 postavimo na milji 1, smo tako v celoti pokrili interval [0,4]. (a) Zapiši rekurzivne enačbe za reševanje danega problema. Razloži, kaj predstavljajo spremenljivke, v kakšnem vrstnem redu jih računamo, ter kako dobimo optimalno rešitev. 21 (b) Oceni časovno zahtevnost algoritma, ki sledi iz zgoraj zapisanih enačb. (c) S svojim algoritmom poišči optimalno postavitev postaj za n = 10 ter ( ai )10 i =0 = (4, 6, 1, 10, 14, 21, 15, 6, 10, 3, 2). (d) Denimo, da lahko postavimo tudi večje bazne postaje z dosegom 2 milji, pri čemer je cena postavitve take postaje na i -ti milji podana s parametrom bi (0 ≤ i ≤ n). Zapiši rekurzivne enačbe, ki bodo upoštevale tudi to možnost. (e) Problem iz točke (d) reši s podatki iz točke (c) in ( bi )10 i =0 = (10, 12, 3, 18, 24, 25, 20, 11, 16, 7, 4). Naloga 4.10. Vir: Izpit OR 19.6.2019 Za novo postavljeno obrtno cono želimo napeljati vodovodno omrežje. Imamo n delavnic v ravni vrsti, za i -to delavnico pa imamo podano porabo vode pi . Iz javnega vodovoda bodo napeljali cev, preko katere bo priteklo dovolj vode za vseh n delavnic, mi pa želimo postaviti razdelilnike, ki bodo poskrbeli za ustrezno raz-delitev vode med delavnice. Vsak razdelilnik ima eno vhodno cev in dve izhodni, vsaka od njiju pa bo pripeljala vodo do zaporednih delavnic (po potrebi preko nadaljnjih razdelilnikov). Cena postavitve razdelilnika je sorazmerna porabi delavnic, ki jim služi. Razdelilnike želimo postaviti tako, da bo skupna cena čim manjša. Primer: na sliki 7 je prikazana možna postavitev razdelilnikov za tri delavnice. Odločimo se lahko, ali bomo najprej razdelili vodo delavnici 1 in delavnicama 2,3, ali pa bomo vodo peljali naprej do delavnic 1,2 in do delavnice 3 (ne moremo pa deliti na delavnici 1,3 in delavnico 2). Če se odločimo za prvi primer, potem do delavnice 1 ne potrebujemo drugih razdelilnikov, še enega pa moramo postaviti, da razdelimo vodo do delavnic 2 in 3. Cena postavitve prvega razdelilnika je tako p 1 + p 2 + p 3 (ne glede na odločitev), za drugega pa je v tem primeru cena p 2 + p 3. P (a) Naj bo c i i = p h=1 h (0 ≤ i ≤ n). Zapiši rekurzivne enačbe za čim učinkovitejši izračun teh vrednosti. (b) Zapiši rekurzivne enačbe za reševanje danega problema. Razloži, kaj predstavljajo spremenljivke, v kakšnem vrstnem redu jih računamo, ter kako dobimo optimalno rešitev. Kakšna je časovna zahtevnost algoritma? Namig: pomagaj si z vrednostmi ci iz prejšnje točke. (c) S pomočjo rekurzivnih enačb reši zgornji problem za n = 6 in ( pi )6 i=1 = (4,19,17,7,5,9). 22 p 1 + p 2 + p 3 p 1 p 2 + p 3 p 2 p 3 Slika 7: Primer postavitve razdelilnikov za nalogo 4.10.   0 2 −7 −1      −6 −9 −3 8      7 2 −8 −2     −7 −7 6 0 Slika 8: Primer matrike dimenzij 4 × 4 za nalogo 4.11 skupaj z dopustno (ne nujno optimalno!) rešitvijo. Vsota obiskanih mest je v tem primeru 0 + 7 + 2 + (−2) + 0 = 7. Naloga 4.11. Vir: Izpit OR 4.6.2020 Dana je matrika A dimenzij m × n. Iščemo tako zaporedje skokov po matriki, pri čemer začnemo levo zgoraj in končamo desno spodaj, v vsakem koraku pa sko- čimo za vsaj eno mesto desno ali dol, pri katerem je vsota obiskanih mest čim več- ja. Drugače povedano, iščemo tako zaporedje indeksov ( i 1, j 1),( i 2, j 2),...( ik, jk) (za nek k ≥ 1), za katere velja ( i 1, j 1) = (1,1), ( ik, jk) = ( m, n) in ( ih < ih+1 ∧ jh = P j k h+1)∨( ih = ih+1 ∧ jh < jh+1) za vse h (2 ≤ h ≤ k), ki maksimizira vsoto A . h=1 ih, jh Primer je podan na sliki 8. (a) Zapiši začetne pogoje in rekurzivne enačbe za reševanje opisanega problema ter določi, v kakšnem vrstnem redu računamo spremenljivke in kako dobimo maksimalno vsoto. Kakšna je časovna zahtevnost algoritma, ki sledi iz rekurzivnih enačb? (b) Reši problem za matriko s slike 8 z uporabo rekurzivnih enačb. Naloga 4.12. Vir: Izpit OR 27.8.2019 Vlagatelj ima na voljo m kapitala, del katerega bo vložil v eno izmed dveh konkurenčnih podjetij, ki razvijata podobna produkta (v obe ne more vložiti), preostanek pa bo namenil za marketinško kampanjo, ki bo promovirala produkt izbranega podjetja. Naj bodo x 1, x 2 in x 3 količine denarja (te so lahko poljubna nenegativna realna števila), ki jih bo vložil v prvo oziroma drugo podjetje in v 23 marketing, ter določimo ( n p i + ki xi , če xi ≥ ai , in i = ( i = 1,2,3) 0 sicer kot faktor, ki ga ustvari vsako izmed njih. Pričakovani dobiček se izračuna po formuli d = ( p 1 + p 2) p 3, pri čemer bo eden od p 1 in p 2 enak 0. Vlagatelj bi rad sredstva porazdelil tako, da bo pričakovani dobiček čim večji. (a) Zapiši enačbe za reševanje danega problema. Lahko predpostaviš, da velja pi ≥ 0 za vse vrednosti xi ( i = 1,2,3). (b) Z zgoraj zapisanimi enačbami reši problem pri podatkih m = 10, a 1 = 4, n 1 = 8, k 1 = 4, a 2 = 5, n 2 = 12, k 2 = 2, a 3 = 3, n 3 = 4 in k 3 = 1. 24 a b c d e f g h i Slika 9: Graf za nalogi 5.1 in 5.3. 3 7 a b c 9 9 7 1 6 e d 1 4 8 f g h 5 1 Slika 10: Graf za nalogo 5.2. 1.5 Algoritmi na grafih Naloga 5.1. Vir: Vaje OR 30.11.2016 Na grafu s slike 9 izvedi iskanje v širino. V primerih, ko imaš več enakovrednih izbir, upoštevaj abecedni vrstni red. Za vsako povezavo določi, ali se nahaja v drevesu iskanja v širino. Naloga 5.2. Vir: Vaje OR 7.12.2016 S pomočjo Dijkstrovega algoritma določi razdalje od vozlišča a do ostalih vozlišč v grafu s slike 10. Naloga 5.3. Vir: [1, Exercise 3.1] Na grafu s slike 9 izvedi iskanje v globino. V primerih, ko imaš več enakovrednih izbir, upoštevaj abecedni vrstni red. Za vsako povezavo določi, ali se nahaja v drevesu iskanja v globino. Naloga 5.4. Vir: Vaje OR 21.5.2018 S pomočjo Bellman-Fordovega algoritma določi razdalje od vozlišča a do ostalih vozlišč v grafu s slike 11. 25 3 7 a b c 9 9 −7 1 6 e d 1 4 8 f g h −5 −1 Slika 11: Graf za nalogo 5.4. 6 b c 2 2 −2 −2 a d 3 0 6 7 −1 h e 6 1 6 6 g f 6 Slika 12: Graf za nalogo 5.5. Naloga 5.5. Vir: Vaje OR 7.12.2016 Dan je usmerjen acikličen graf s slike 12. (a) Poišči topološko ureditev vozlišč zgornjega grafa. (b) Poišči najkrajšo pot od vozlišča g do vozlišča e. (c) Poišči najdaljšo pot od vozlišča g do vozlišča e. Naloga 5.6. Vir: Izpit OR 15.12.2016 Lovec na zaklade se z bogatim ulovom vrača iz Kalifornije nazaj domov v Chicago, pri čemer mora seveda prečkati Divji zahod. Potoval bo s kočijo, pri čemer bo vsak dan potoval med dvema mestoma in nato prespal. Zaradi varnosti se bo držal samo državnih cest, ki so varne. Toda mesta, kjer bo prespal, niso povsem varna. Za vsako mesto pozna verjetnosti, da ga tam ne bodo oropali (te so med 26 RE SLC OM 0.7 0.9 0.4 1 CH SF 1 0.8 0.7 0.9 SL DE KC LV 0.5 0.7 0.6 0.7 ME AQ OC LA 1 0.8 0.6 0.8 PH EP DA Slika 13: Graf za nalogo 5.6. seboj neodvisne). Tako bi želel načrtovati najvarnejšo pot domov – torej pot z največjo verjetnostjo, da ga pri nobenem postanku ne bodo oropali. (a) Mesta in ceste med njimi lahko predstavimo z vozlišči in povezavami v ne-usmerjenem grafu G, verjetnosti pa kot teže vozlišč. Opiši, kako lahko za dani graf G z uteženimi vozlišči učinkovito poiščemo ustrezno pot med danima vozliščema s in t z uporabo variante Dijkstrovega algoritma, ter utemelji njegovo ustreznost. Lahko predpostaviš, da sta teži začetnega in končnega vozlišča enaki 1. (b) Reši problem za graf s slike 13, pri čemer naj se pot začne v LA in konča v CH. Zadostovalo bo, če verjetnosti računaš na 3 decimalke natančno. Naloga 5.7. Vir: Izpit OR 10.7.2017 Z električnim vozilom se odpravljamo na počitnice. Vozilo moramo vsako noč napolniti, zato smo si pripravili seznam krajev in cestnih povezav med njimi, ki jih lahko prevozimo v enem dnevu. Poiskati želimo pot od začetne točke do destinacije, ki bo imela čim manjše število postankov (tj., bo trajala čim manj dni). (a) Predstavi problem v jeziku grafov in predlagaj algoritem za njegovo reševanje. (b) Na koncu počitnic razmišljamo o poti nazaj. Spet bi radi naredili čim manj postankov, a se pri tem ne želimo ustaviti v nobenem kraju, kjer smo se ustavili na poti naprej. Dopolni zgornji algoritem, da bo našel še ustrezno pot nazaj. (c) S pomočjo zgornjih algoritmov poišči najkrajšo pot od LJ do AM in najkrajšo pot nazaj v grafu s slike 14, ki ne gre čez kraje iz prejšnje poti. 27 27 24 16 11 8 21 20 14 6 BX AM BL PR BS 22 4 28 23 9 7 18 16 12 17 8 PA LU BN WI BU 12 15 30 21 24 18 11 30 13 MO VE LJ ZG 19 15 10 25 20 0 10 Slika 14: Graf za nalogi 5.7 (brez uteži) in 5.10. Naloga 5.8. Vir: Kolokvij OR 11.6.2018 Dan je povezan neusmerjen enostaven graf G = ( V, E) (tj., brez zank in večkratnih povezav). Prerezno vozlišče v grafu G je tako vozlišče u ∈ V , da graf G − u (tj., graf G brez vozlišča u in povezav s krajiščem v u) ni več povezan. Poiskati želimo seznam prereznih vozlišč grafa G. Pri iskanju si bomo pomagali s preiskovanjem v globino. Ob prvem obisku vozlišča u s predhodnikom v se tako pokliče funkcija PREVISIT( u, v), ob njegovem zadnjem obisku pa funkcija POSTVISIT( u, v). Če je u koren preiskovalnega drevesa, potem ima v vrednost NULL. Predpostavi, da imaš v obeh funkcijah dostop do seznama izhod, kamor bo treba dodati najdena presečna vozlišča. Prav tako imata lahko obe funkciji dostop do drugih pomožnih spremenljivk. Naj bo ù globina vozlišča u v drevesu iskanja v globino (tj., razdalja od korena do u v drevesu iskanja v globino). Za vsako vozlišče u definiramo vrednost pu kot najmanjšo globino vozlišč, ki so v grafu G sosedna (ali enaka) vozlišču u ali njegovim potomcem v drevesu iskanja v globino. (a) Za graf na sliki 15 nariši drevo iskanja v globino (v njem označi tudi povratne povezave, npr. s črtkano črto) in določi njegova prerezna vozlišča. Upoštevaj abecedni vrstni red obiskovanja vozlišč. Za vsako vozlišče u določi še vrednosti ù in pu. Namig: vrednosti pu najprej določi za vozlišča z večjo globino. (b) Napiši rekurzivno formulo za vrednost pu. Namig: loči med sosedi v vozlišča u v grafu G (pišeš lahko u ∼ v) in njegovimi neposrednimi nasledniki w v preiskovalnem drevesu ( u → w). (c) Natančno opiši funkcijo PREVISIT( u, v) (z besedami ali psevdokodo), ki poskrbi za izračun vrednosti ù. 28 a b c d e f g h i j Slika 15: Graf za nalogo 5.8. (d) Natančno opiši funkcijo POSTVISIT( u, v) (z besedami ali psevdokodo), ki naj za vozlišče u izračuna vrednost pu in ugotovi, ali je u prerezno vozlišče, in ga v tem primeru doda v izhod. Predpostavi, da imaš globine vozlišč že poračunane. Namig: obravnavaj dve možnosti – ko je u koren drevesa, in ko u ni koren drevesa. Kako v vsakem od teh primerov ugotoviš, ali je u prerezno vozlišče? (e) Oceni časovno zahtevnost celotnega algoritma. Naloga 5.9. Vir: Izpit OR 5.7.2018 Dan je utežen usmerjen acikličen graf s slike 16. (a) Poišči topološko ureditev grafa s slike 16. (b) Poišči najcenejšo pot od vozlišča s do vozlišča t v grafu s slike 16. (c) Naj bo G = ( V, E) usmerjen acikličen graf z nenegativno uteženimi povezavami ter s, t ∈ V njegovi vozlišči. Algoritem A se po grafu G sprehaja po naslednjem pravilu: začne v vozlišču s, v vsakem koraku pa se iz vozlišča u premakne v njegovega izhodnega soseda v z verjetnostjo ` p uv uv = P , u→ w ùw kjer je ùv teža povezave od u do v. Algoritem A se ustavi, ko doseže vozlišče t. Natančno opiši (z besedami ali psevdokodo), kako bi v času O( m) (kjer je m = | V | + | E|) za vsako vozlišče u ∈ V določil verjetnost qu, da algoritem A obišče vozlišče u. Verjetnosti za graf s slike 16 ni potrebno računati. 29 6 6 a d g 1 2 4 4 3 5 3 6 4 3 s b e h t 1 4 2 5 6 4 1 1 c f i 2 5 Slika 16: Graf za nalogo 5.9. Naloga 5.10. Vir: Izpit OR 28.8.2018 Odpravljamo se na pot, ki bo trajala več dni. Pripravili smo si seznam krajev in povezav med njimi, ki jih lahko prevozimo v enem dnevu. Za vsako povezavo poznamo stroške prevoza, prav tako pa za vsak kraj poznamo še stroške nočitev. Poiskati želimo čim cenejšo pot od začetne točke do destinacije (tj., skupna cena prevozov in nočitev naj bo čim manjša). (a) Predstavi problem v jeziku grafov in predlagaj čim bolj učinkovit algoritem za njegovo reševanje. (b) S pomočjo zgornjega algoritma poišči najcenejšo pot od LJ do BX v grafu s slike 14. Na povezavah so napisani stroški prevozov med krajema (veljajo za obe smeri), pri vozliščih pa stroški prenočitve v kraju. Naloga 5.11. Vir: Izpit OR 29.8.2017 Peter zaključuje študij na Fakulteti za alternativno znanost. Opravil je že vse obvezne predmete, za pristop k zaključnemu izpitu pa mora opraviti še nekaj izbirnih predmetov. To bi rad storil čim hitreje. V tabeli 1 so našteti izbirni predmeti skupaj s trajanjem (v tednih, od pristopa do uspešnega opravljanja) in predmeti, h katerim lahko pristopi po uspešnem opravljanju. K predmetom a, c in f lahko pristopi že takoj, za pristop k ostalim predmetom pa zadostuje, če je opravljen eden od pogojev. (a) Topološko uredi ustrezni graf in ga nariši. (b) Katere predmete naj Peter opravi, da bo lahko čim prej pristopil k zaključ- nemu izpitu? Koliko časa bo za to potreboval? Natančno opiši postopek iskanja odgovora. 30 Oznaka Predmet Trajanje Zadosten pogoj za a Alternativna zgodovina 5 i , j b Astrološki praktikum 7 d, g c Diskretna numerologija 9 b d Filozofija magije 4 z e Kvantno pravo 8 b, h f Postmoderna ekonomija 4 e g Telepatija in telekineza 5 z h Teorija antigravitacije 4 h i Teorije zarote 5 h j Ufologija II 10 k k Uvod v kriptozoologijo 6 z z Zaključni izpit / / Tabela 1: Podatki za nalogo 5.11. Naloga 5.12. Vir: Kolokvij OR 3.6.2019 Dan je neusmerjen utežen graf G = ( V, E) z nenegativnimi cenami povezav Le ( e ∈ E). Naj bosta A in B disjunktni množici povezav, tako da velja E = A ∪ B. Želimo najti najcenejšo alternirajočo pot med danima vozliščema s, t ∈ V – torej takšno, v kateri se povezave iz A in iz B izmenjujejo (ni pomembno, ali začnemo oziroma končamo s povezavo iz množice A ali B). Posamezno vozlišče se lahko v alternirajoči poti pojavi tudi večkrat. (a) Predlagaj čim učinkovitejši algoritem za reševanje danega problema. Kakšna je njegova časovna zahtevnost? Namig: grafu G priredi usmerjen graf G 0, v katerem bodo vse poti od s do t ustrezale alternirajočim potem v G. Po potrebi lahko vozlišča tudi podvojiš. (b) S svojim algoritmom poišči najcenejšo alternirajočo pot od s do t v grafu s slike 17. Povezave iz množice A so označene s polno, povezave iz množice B pa s črtkano črto. Iz rešitve naj bo jasno, kako poteka izvajanje algoritma. Naloga 5.13. Vir: Kolokvij OR 3.6.2019 Neodvisna množica vozlišč grafa G = ( V, E) je taka množica S ⊆ V , da sta poljubni vozlišči iz množice S nesosedni v G, torej uv 6∈ E za vsaka u, v ∈ S. Dano je drevo T = ( V, E) in uteži vozlišč cv ( v ∈ V ). V drevesu T želimo najti najtežjo neodvisno množico – torej tako množico vozlišč S ⊆ V , ki maksimizira P vsoto njihovih uteži, torej vrednost u∈ S cu. (a) Denimo, da je drevo T podano kot neusmerjen graf, predstavljen s seznami sosedov. Razloži, kako lahko sestaviš slovar pred, ki za vsako vozlišče v ∈ V določa njegovega prednika, če za koren izbereš vozlišče r ∈ V . Koren r je 31 r 4 2 1 s w 7 2 12 1 10 3 t v 11 1 2 u Slika 17: Graf za nalogo 5.12(b). lahko izbran poljubno, zanj pa velja pred[ r ] = NULL. Kako iz seznamov sosedov in slovarja pred ugotovimo, katera vozlišča so neposredni nasledniki danega vozlišča v drevesu? (b) Napiši rekurzivne enačbe za reševanje problema najtežje neodvisne množice v drevesu T . Razloži, kaj predstavljajo spremenljivke, v kakšnem vrstnem redu jih računamo, ter kako dobimo optimalno rešitev. Predpostaviš lahko, da imaš poleg seznamov sosedov in uteži vozlišč drevesa T na voljo tudi slovar pred kot v točki (a). Namig: za vsako vozlišče uporabi dve spremenljivki – eno za primer, ko je vozlišče izbrano, in eno za primer, ko ni. (c) Natančno opiši postopek (z besedami ali psevdokodo), ki iz zgoraj izračunanih vrednosti sestavi najtežjo neodvisno množico v T . (d) Oceni časovno zahtevnost algoritma iz točk (b) in (c). (e) S svojim algoritmom poišči najtežjo neodvisno množico na drevesu s slike 18. Iz rešitve naj bo jasno, kako poteka izvajanje algoritma. Naloga 5.14. Vir: Izpit OR 19.6.2019 Trg mobilne telefonije je zelo konkurenčen, zato si mobilni operaterji na vse kriplje prizadevajo pridobiti stranke svojih konkurentov. Tako zelo, da lahko v ne-katerih primerih stranka s prehodom h konkurentu celo zasluži. Da pa vendarle operaterji sami ne bi imeli prevelike izgube, stranke zadržujejo z različnimi vezavami, poleg tega pa novim strankam (tistim, ki še niso imele mobilnega telefona) krepko zaračunajo priklop. Stanje trga zberemo v utežen usmerjen graf G = ( V, E), kjer vozlišča predstavljajo operaterje, utež Luv povezave uv ∈ E pomeni strošek prehoda od operaterja u k operaterju v, utež cv vozlišča v ∈ V pa pomeni strošek, ki nastane tekom 32 8 a 1 b 9 c 1 d 1 e 4 f 8 g 4 h 9 i 4 j 2 k Slika 18: Drevo za nalogo 5.13(e). trajanja vezave pri operaterju v (ko preidemo k operaterju v, imamo torej cv dodatnih stroškov). Če povezave uv ni v grafu, potem neposreden prehod od u k v ni mogoč. Uteži vozlišč so nenegativne, uteži povezav pa so lahko tudi negativne (tj., če ob prehodu zaslužimo). Poiskati želimo najcenejše zaporedje prehodov med operaterji (tj., tako, pri katerem imamo najmanj stroškov), če začnemo pri operaterju s in končamo pri operaterju t. (a) Predlagaj čim bolj učinkovit algoritem za reševanje zgornjega problema. Kak- šna je njegova časovna zahtevnost? Lahko predpostaviš, da velja cs = ct = 0. (b) Denimo, da trenutno še nimamo mobilnega telefona. Naši izračuni kažejo, da je dolgoročno najugodnejša ponudba operaterja Rega, tako da bi radi s čim manjšimi stroški postali njihov naročnik. S pomočjo algoritma iz točke (a) poišči ustrezno zaporedje prehodov na grafu s slike 19. Naloga 5.15. Vir: Izpit OR 4.6.2020 Dana sta neutežen neusmerjen graf G = ( V, E) z n vozlišči in m povezavami ter vozlišče s ∈ V . Za vsako vozlišče v ∈ V nas zanima, koliko najkrajših poti od s do v je v grafu G (tj., koliko je takšnih poti od s do v, katerih dolžina je enaka razdalji med s in v v grafu G). (a) Čim bolj natančno opiši algoritem, ki reši zgornji problem v času O( m). (b) Uporabi svoj algoritem, da za vsako vozlišče v grafu s slike 20 poiščeš število najkrajših poti od vozlišča i . Natančno zabeleži, kaj se zgodi v vsakem koraku algoritma. 33 20 10 15 20 10 0 Sodafon Bobitel TeleJanez 85 65 45 −5 5 brez 95 60 Rega Z 0 50 5 0 5 20 − −15 10 − Fenmobil 30 Slika 19: Graf za nalogo 5.14. a b c d e f g h i Slika 20: Graf za nalogo 5.15. Naloga 5.16. Vir: Izpit OR 22.6.2020 Večja skupina prijateljev želi preživeti počitnice na jadrnici. Ker pa je na sami jadrnici le manjše število ležišč, so se odločili, da bodo prenočevali na kopnem vzdolž poti (vključno z začetnim in končnim krajem). Sestavili so usmerjen acikli- čen graf G = ( V, E) z n vozlišči in m povezavami, v katerem vozlišča predstavljajo kraje, kjer se lahko ustavijo, vozlišči u, v ∈ V pa sta povezani z usmerjeno povezavo uv ∈ E, če lahko v enem dnevu plujejo od kraja u do kraja v. Začetna in končna točka poti sta predstavljeni z vozliščema s, t ∈ V . Poleg tega za vsako vozlišče u ∈ V poznajo še število ku, ki predstavlja, koliko oseb lahko prespi v kraju u. Sestaviti želijo tako pot od s do t, da bo lahko na jadrnici potovalo čim več prijateljev (tj., maksimizirati želijo minimalno vrednost ku vseh obiskanih krajev u na poti). Dolžina poti pri tem ni pomembna. 34 14 16 RI ZD 20 13 17 KP ŠI ST 12 20 PU ML DO HV DU 18 15 19 Slika 21: Graf za nalogo 5.16(b). (a) Natančno opiši čim učinkovitejši algoritem (z besedami ali psevdokodo) za reševanje zgornjega problema in določi njegovo časovno zahtevnost. (b) Uporabi svoj algoritem, da v grafu G = ( V, E) s slike 21 poiščeš tako pot od KP do DU, da bo lahko na jadrnici potovalo čim večje število prijateljev. Vrednosti ku ( u ∈ V ) so zapisane ob vsakem vozlišču. Natančno zabeleži, kaj se zgodi v vsakem koraku algoritma. 35 faza opis trajanje pogoj min. trajanje cena za dan manj a gradnja kleti 10 dni / 7 dni 200 b gradnja pritličja 6 dni a 5 dni 100 c gradnja prvega nadstropja 7 dni b, f 5 dni 150 d gradnja strehe 8 dni c, e 6 dni 160 e gradnja desnega podpornega stebra 13 dni a 9 dni 250 f gradnja glavnega podpornega stebra 14 dni / 11 dni 240 g gradnja baročnega stolpa pred hišo 30 dni / 25 dni 300 Tabela 2: Podatki za nalogi 6.1 (prvi štirje stolpci) in 6.2. 1.6 CPM/PERT Naloga 6.1. Vir: Kolokvij OR 9.5.2013 Gradbinec in samooklicani arhitekt Brezzobec se je odločil, da bo postavil zelo posebno hišo. Gradnja bo imela sedem glavnih faz, ki so opisane v tabeli 2. (a) Kdaj je lahko hiša najhitreje zgrajena? Katere faze so kritične? (b) Koliko je kritičnih poti in katere so? (c) Katero opravilo je najmanj kritično? Najmanj kritično je opravilo, katerega trajanje lahko največ podaljšamo, ne da bi vplivali na trajanje gradnje. (d) Brezzobčev brat je ponudil pomoč pri največ eni fazi gradnje. Slovi po tem, da pri fazi, pri kateri pomaga, zmanjša čas izvajanja za 10%. Pri kateri fazi naj pomaga, da bo čas gradnje čim krajši? Naloga 6.2. Vir: Vaje OR 28.5.2018 Brezzobčev bratranec ima podjetje, ki lahko pomaga pri gradnji, vendar za vsak dan krajšanja posamezne faze zahteva ustrezno plačilo (glej zadnja dva stolpca tabele 2). Brezzobca zanima način, kako bi s čim manjšimi stroški čas gradnje zmanjšal na 27 dni. Zapiši linearni program za ta problem. Naloga 6.3. Vir: Izpit OR 19.5.2015 Dinamika priprave dveh palačink z dvema kuharjema je opisana v tabeli 3. (a) Topološko uredi ustrezni graf in ga nariši. (b) Določi kritična opravila in kritično pot ter trajanje priprave. (c) Katero opravilo je najmanj kritično? 36 aktivnost trajanje predhodna opravila a nakup moke, jajc in mleka 5 min c b rezanje sira 3 min / c vožnja do trgovine 5 min / d čiščenje mešalnika 2 min e e mešanje sestavin 5 min a f pečenje prve palačinke 2 min e g mazanje prve palačinke z marmelado 1 min f , j h pečenje palačinke (s sirom) 3 min b, f i pomivanje posode 8 min g , h j odpiranje marmelade 1 min / Tabela 3: Podatki za naloge 6.3, 6.4 in 6.5. Naloga 6.4. Vir: Vaje OR 18.5.2020 Določi skupne, proste, varnostne in neodvisne rezerve opravil iz naloge 6.3. Naloga 6.5. Vir: Vaje OR 14.12.2016 Določi razpored opravil iz naloge 6.3, pri čemer en kuhar prevzame opravila na kritični poti, drugi pa naj čim kasneje začne in čim prej konča. Naloga 6.6. Vir: Izpit OR 31.1.2017 Izdelati želimo terminski plan za izdelavo spletne aplikacije. V tabeli 4 so zbrana opravila pri izdelavi. (a) Topološko uredi ustrezni graf in ga nariši. (b) Določi kritična opravila in kritično pot ter čas izdelave. (c) Katero opravilo je najmanj kritično? Najmanj kritično je opravilo, katerega trajanje lahko najbolj podaljšamo, ne da bi vplivali na trajanje izdelave. Naloga 6.7. Vir: Kolokvij OR 11.6.2018 Izdelati želimo terminski plan za organizacijo konference. V tabeli 5 so zbrana opravila pri organizaciji. (a) Topološko uredi ustrezni graf in ga nariši. Za trajanja opravil vzemi pričakovana trajanja po modelu PERT. (b) Določi pričakovano kritično pot in čas izdelave. (c) Katero opravilo je (ob zgornjih predpostavkah) najmanj kritično? Najmanj kritično je opravilo, katerega trajanje lahko najbolj podaljšamo, ne da bi vplivali na celotno trajanje izvedbe. 37 opravilo opis trajanje pogoji a natančna opredelitev funkcionalnosti 15 dni / b programiranje uporabniškega vmesnika 40 dni k c programiranje skrbniškega vmesnika 25 dni a, m d programiranje strežniškega dela 30 dni a, m e integracija uporabniškega vmesnika s strežnikom 20 dni b, d f alfa testiranje 20 dni c, e g beta testiranje 30 dni f , h h pridobivanje testnih uporabnikov 45 dni a i vnos zadnjih popravkov 10 dni g j izdelava uporabniške dokumentacije 35 dni b k dizajniranje uporabniškega vmesnika 15 dni a ` nabava računalniške opreme 20 dni / m postavitev strežnikov 10 dni ` Tabela 4: Podatki za nalogo 6.6. Minimalno Najbolj verjetno Maksimalno Opravilo Pogoji trajanje trajanje trajanje a Izbira lokacije / 10 dni 13 dni 22 dni b Rezervacija sob za goste f 13 dni 22 dni 25 dni c Dogovarjanje za cene hotelskih sob a 3 dni 6 dni 9 dni d Naročilo hrane in pijače a 6 dni 15 dni 21 dni e Priprava letakov c, j 5 dni 8 dni 11 dni f Pošiljanje letakov e 4 dni 4 dni 4 dni g Priprava zbornika s povzetki d, j 22 dni 28 dni 31 dni h Določitev glavnega govorca / 5 dni 8 dni 14 dni i Planiranje poti za glavnega govorca a, h 11 dni 14 dni 17 dni j Določitev ostalih govorcev h 12 dni 15 dni 21 dni k Planiranje poti za ostale govorce a, j 9 dni 12 dni 18 dni Tabela 5: Podatki za nalogo 6.7. (d) Določi variance trajanj opravil in oceni verjetnost, da bo izvedba trajala manj kot 55 dni. Naloga 6.8. Vir: Izpit OR 28.8.2018 Pri izdelavi letala imamo faze, opisane v tabeli 6. (a) S pomočjo topološke ureditve ustreznega grafa določi kritična opravila in čas izdelave. Uporabi podatke iz stolpca “trajanje”. (b) Katero opravilo je najmanj kritično? Najmanj kritično jo opravilo, katerega trajanje lahko najbolj podaljšamo, ne da bi vplivali na trajanje izdelave. 38 opravilo opis trajanje pogoji najmanjše trajanje cena za dan manj a izgradnja nosu 40 dni / 36 dni 1 000 b izgradnja trupa s krili 50 dni / 48 dni 1 500 c izgradnja repa 35 dni / 31 dni 800 d vgraditev pilotske kabine 30 dni a 28 dni 1 200 e opremljanje potniške kabine 18 dni f , g 16 dni 500 f povezovanje nosu s trupom 10 dni a, b 9 dni 1 100 g povezovanje repa s trupom 12 dni b, c 10 dni 1 300 h vgraditev motorjev 20 dni b 18 dni 1 400 Tabela 6: Podatki za nalogo 6.8. (c) Naročnik bi rad, da letalo izdelamo v 75 dneh. Posamezna opravila lahko skrajšamo tako, da zanje zadolžimo več delavcev. Seveda prinese tako kraj- šanje dodatne stroške, poleg tega pa za vsako opravilo poznamo najmanjše možno trajanje (glej zadnja dva stolpca v zgornji tabeli). Zapiši linearni program, s katerim modeliramo iskanje razporeda opravil, ki nam prinese čim manjše stroške. Linearnega programa ne rešuj. Naloga 6.9. Vir: Kolokvij OR 3.6.2019 Izdelati želimo terminski plan za izgradnjo manjšega stanovanjskega naselja. V tabeli 7 so zbrana opravila pri gradnji. (a) Topološko uredi ustrezni graf in ga nariši. Za trajanja opravil vzemi pričakovana trajanja po modelu PERT. (b) Določi pričakovano kritično pot in čas izdelave. (c) Katero opravilo je (ob zgornjih predpostavkah) najmanj kritično? Najmanj kritično je opravilo, katerega trajanje lahko najbolj podaljšamo, ne da bi vplivali na celotno trajanje izvedbe. (d) Določi variance trajanj opravil in oceni verjetnost, da bo gradnja trajala manj kot 180 dni. Naloga 6.10. Vir: Izpit OR 19.6.2019 Gradbeno podjetje gradi avtocestni odsek na težavnem terenu. Identificirali so faze gradnje, ki so zbrane v tabeli 8. (a) S pomočjo topološke ureditve ustreznega grafa določi kritična opravila in čas izdelave. Uporabi podatke iz stolpca “trajanje”. (b) Katero opravilo je najmanj kritično? Najmanj kritično jo opravilo, katerega trajanje lahko najbolj podaljšamo, ne da bi vplivali na trajanje izdelave. 39 Minimalno Najbolj verjetno Maksimalno Opravilo Pogoji trajanje trajanje trajanje a pridobitev gradbenega dovoljenja / 14 dni 14 dni 23 dni b pridobitev uporabnega dovoljenja f , g 18 dni 21 dni 30 dni c izgradnja komunalne infrastrukture a 40 dni 45 dni 59 dni d postavitev temeljev a, i 28 dni 37 dni 46 dni e izgradnja podpornega zidu a 7 dni 8 dni 12 dni f izgradnja severne stolpnice c, d 63 dni 78 dni 99 dni g izgradnja južne stolpnice d, e 75 dni 84 dni 99 dni h izgradnja otroškega igrišča a, i 20 dni 29 dni 29 dni i odstranitev rastja / 19 dni 22 dni 25 dni Tabela 7: Podatki za nalogo 6.9. opravilo opis trajanje pogoji najmanjše trajanje cena za dan manj a izgradnja južnega priključka 45 dni / 40 dni 300 b izgradnja severnega priključka 20 dni / 15 dni 200 c vrtanje tunelske cevi 90 dni a, b 70 dni 700 d postavitev zahodnega stebra viadukta 25 dni a 22 dni 1 100 e postavitev vzhodnega stebra viadukta 30 dni c 26 dni 1 500 f gradnja cestišča na viaduktu 35 dni d, e 28 dni 900 g ureditev napeljave v tunelu 80 dni c 65 dni 400 h asfaltiranje viadukta 10 dni f 8 dni 150 Tabela 8: Podatki za nalogo 6.10. (c) Naročnik bi rad, da podjetje odsek zgradi v 200 dneh. Posamezna opravila lahko skrajšajo tako, da zanje zadolžijo več delavcev. Seveda prinese tako kraj- šanje dodatne stroške, poleg tega pa za vsako opravilo poznamo najmanjše možno trajanje (glej zadnja dva stolpca v tabeli 8). Zapiši linearni program, s katerim modeliramo iskanje razporeda opravil, ki nam prinese čim manjše stroške. Linearnega programa ne rešuj. 40 1.7 Upravljanje zalog Naloga 7.1. Vir: Vaje OR 6.6.2018 Marta izdeluje nakit iz školjk v delavnici, ki jo najema v bližini ljubljanske tržnice, in ga prodaja po vnaprej dogovorjeni ceni. Povpraševanje je 10 kosov na teden, stroški skladiščenja so 0.2e za kos na teden. Zagonski stroški izdelovanja nakita so 150e. Marta lahko na teden izdela 12.5 kosa nakita. Dovoli si, da pride do primanjkljaja, pri čemer jo ta stane 0.8e za kos nakita na teden. Kako naj Marta organizira proizvodnjo in skladiščenje, da bo imela čim manj stroškov? Naloga 7.2. Vir: Kolokvij OR 11.6.2018 Vulkanizer v svoji delavnici izdeluje in prodaja avtomobilske pnevmatike. Glede na trenutno povpraševanje vsak teden proda 60 pnevmatik, v istem času pa jih lahko izdela 90. Cena zagona proizvodnje je 180e, cena skladiščenja posamezne pnevmatike pa je 0.5e na teden. (a) Denimo, da primanjkljaja ne dovolimo. Izračunaj dolžino cikla proizvodnje in prodaje pnevmatik, pri kateri so stroški najmanjši. Kako veliko skladišče mora vulkanizer imeti? Izračunaj tudi enotske stroške. (b) Kako dolgo naj pri zgornji rešitvi traja proizvodnja? Koliko pnevmatik naj vulkanizer naredi v vsakem ciklu? (c) Vulkanizer je ocenil, da bi ga primanjkljaj ene pnevmatike stal 2e na teden. Kakšna naj bosta dolžina cikla in velikost skladišča, da bodo stroški čim manjši? Izračunaj tudi enotske stroške in določi največji primanjkljaj. Naloga 7.3. Vir: Izpit OR 5.7.2018 V trgovini s pohištvom vsak mesec prodajo 20 sedežnih garnitur. Z vsakim naročilom imajo 750e stroškov, pri tem pa vse naročeno blago dobijo hkrati. Skladiščenje posamezne sedežne garniture jih stane 10e na mesec, primanjkljaj za en kos pa jih stane 50e na mesec. (a) Kako pogosto naj v trgovini naročajo sedežne garniture, da bodo stroški čim manjši? Kako veliko skladišče morajo imeti? Izračunaj tudi enotske stroške. (b) Izračunaj največji dovoljeni primanjkljaj. Koliko sedežnih garnitur naj vsakič naročijo? (c) V trgovini dobijo ponudbo za uporabo drugega skladišča, v katerem imajo za posamezno sedežno garnituro le 6e stroškov na mesec, vendar lahko hrani največ 40 sedežnih garnitur. Kako naj organizirajo naročanje, če namesto prvotnega uporabljajo to skladišče? Ali se jim ga splača uporabiti? Namig: izpelji formulo za enotske stroške in poišči optimalen interval naročanja pri fiksni velikosti skladišča. 41 Naloga 7.4. Vir: Izpit OR 22.6.2020 V šiviljski delavnici so začeli proizvajati zaščitne maske. Vsak dan lahko izdelajo 400 mask, prodajo pa jih 300. Cena zagona proizvodnje je 240e, cena skladiščenja ene maske za en dan pa je 0.1e. (a) Denimo, da primanjkljaj ni dovoljen. Kako pogosto naj zaženejo proizvodnjo in koliko časa naj ta teče? Koliko mask naj izdelajo v posameznem ciklu ter kako veliko skladišče potrebujejo? (b) Obravnavajmo še primer, ko dovolimo primanjkljaj, ki nas stane 0.4e na dan za eno masko. Izračunaj podatke iz prejšnje točke še za ta primer. Kolikšen je največji dovoljeni primanjklaj? 42 2 Rešitve 2.1 Zahtevnost algoritmov Naloga 1.1. (a) Program prepiše vnose v matriki A nad diagonalo na ustrezno mesto pod diagonalo tako, da je po izvedbi programa matrika A simetrična. (b) Kot korak bomo upoštevali posamezno izvedbo notranje zanke for, kjer ko-piramo vrednost v matriki na drugo mesto – ob predpostavki, da je velikost vnosov omejena (npr. 32-bitna cela števila), bo trajanje take operacije omejeno s konstanto. Preštejmo število takih korakov: n X n X n X n−1 X n( n − 1) 1 = ( n − i) = i = i =1 j= i+1 i =1 i =0 2 Lahko bi seveda upoštevali še korake, ki so potrebni za vzdrževanje števcev zank (inicializacija števca, povečevanje števca, preverjanje konca zanke), a bi spet dobili kvadratni polinom v n. Tako lahko rečemo, da je število korakov omejeno z O( n 2). Naloga 1.2. (a) V vsakem obhodu zanke while se vrednost `[ i ] spremeni iz 0 v 1 ali obratno. Če se vrednost spremeni na 1, se i nastavi na 1, sicer se pa poveča za 1. Izpišimo si vrednosti v seznamu ` in spremenljivke i ob koncu vsakega obhoda zanke while tekom izvajanja algoritma, recimo za n = 4: obhod `[4...1] i obhod `[4...1] i 1 0001 1 16 1001 1 2 0000 2 17 1000 2 3 0010 1 18 1010 1 4 0011 1 19 1011 1 5 0010 2 20 1010 2 6 0000 3 21 1000 3 7 0100 1 22 1100 1 8 0101 1 23 1101 1 9 0100 2 24 1100 2 10 0110 1 25 1110 1 11 0111 1 26 1111 1 12 0110 2 27 1110 2 13 0100 3 28 1100 3 14 0000 4 29 1000 4 15 1000 1 30 0000 5 43 Če pogledamo samo tiste obhode, na koncu katerih velja i = 1, opazimo, da vrednosti v seznamu ` predstavljajo dvojiške zapise števil od 1 do 2 n − 1 v ostalih pa se najmanj pomembna 1 zamenja z 0. Algoritem torej simulira dvojiški števec z n mesti. (b) Algoritem obišče vseh 2 n − 1 števil, poleg tega pa mora vsakič poskrbeti za zamenjavo vseh enic za najmanj pomembno ničlo. Ob upoštevanju, da obstaja 2 n− i števil z najmanj pomembno ničlo na i -tem mestu, za vrednost 2 n − 1 pa je potrebno nadomestiti vseh n mest, je skupno število korakov enako à ! n X n X n X n + ( i · 2 n− i ) = 1 + 2 n− i = i =1 j =1 i = j à ! n X n− j X n X = 1 + 2 i = 2 n− j+1 = 2 n+1 − 2. j =1 i =0 j =1 Časovna zahtevnost algoritma je torej O(2 n). Naloga 1.3. (a) Izpišimo vrednosti spremenljivk ob koncu vsakega obhoda zanke for oziroma while, ko se prejšnja konča. obhod while i y z `[1 . . . 5] 1 2 1 5 [7,11,16,7,5] 1 3 1 5 [7,11,16,7,5] 1 4 4 5 [7,11,7,16,5] 1 5 5 5 [7,11,7,5,16] 1 5 4 [7,11,7,5,16] 2 2 1 4 [7,11,7,5,16] 2 3 3 4 [7,7,11,5,16] 2 4 4 4 [7,7,5,11,16] 2 4 3 [7,7,5,11,16] 3 2 1 3 [7,7,5,11,16] 3 3 3 3 [7,5,7,11,16] 3 3 2 [7,5,7,11,16] 4 2 2 2 [5,7,7,11,16] 4 2 1 [5,7,7,11,16] (b) Naj bodo z 1, z 2,..., zk vrednosti, ki jih zavzame spremenljivka z ob vsakem vstopu v zanko while. Očitno velja zi −1 ≥ zi+1 za vsak i, tako da velja k ≤ n−1. Največje število korakov je torej n X n( n − 1) ( z − 1) = . z=2 2 44 Tako število korakov dosežemo, če je seznam ` na začetku urejen padajoče – tako vsakič pride do zamenjave v zadnjem koraku zanke for, zato se z vsakič zmanjša za 1. Časovna zahtevnost algoritma je torej O( n 2). Naloga 1.4. (a) function MERGESORT( `[1 . . . n]) if n ≤ 1 then return ` end if m ← d n 2 e ` 1 ← MERGESORT( `[1... m]) ` 2 ← MERGESORT( `[ m + 1... n]) i , j ← 1,1 ` 0 ← [] while i ≤ m ∧ j ≤ n − m do if ` 1[ i ] ≤ ` 2[ j ] then ` 0. append( ` 1[ i ]) i ← i + 1 else ` 0. append( ` 2[ j ]) j ← j + 1 end if end while pripni ` 1[ i ... m] na konec ` 0 pripni ` 2[ j ... n − m] na konec ` 0 return ` 0 end function (b) Izvajanje algoritma je prikazano na sliki 22. Nad črtkano črto je prikazano rekurzivno razbijanje seznamov, pod njo pa zlivanje dobljenih urejenih pod-seznamov. (c) Funkcija obsega dva rekurzivna klica na seznamih polovične dolžine ter zdru- ževanje obeh dobljenih seznamov v enega. Naj bo T ( n) čas izvajanja algoritma pri vhodnem seznamu dolžine n. Ker združevanje poteka v linearnem času, velja rekurzivna zveza ³ n ´ T ( n) = O( n) + 2 T . 2 Po krovnem izreku lahko izpeljemo, da je časovna zahtevnost algoritma O( n log n). Naloga 1.5. p Algoritem teče v času O( n). Ker je vhod algoritma število n, ki je zapisano kot zaporedje ` = O(log n) bitov, vidimo, da algoritem teče v času O(2 `/2) in torej ni polinomski v dolžini vhoda. 45 [7,11,16,7,5,0,14,1,19,13] [7,11,16,7,5] [0,14,1,19,13] [7,11,16] [7,5] [0,14,1] [19,13] [7,11] [16] [7] [5] [0,14] [1] [19] [13] [7] [11] [0] [14] [7,11] [0,14] [7,11,16] [5,7] [0,1,14] [13,19] [5,7,7,11,16] [0,1,13,14,19] [0,1,5,7,7,11,13,14,16,19] Slika 22: Diagram izvajanja algoritma za nalogo 1.4(b). Naloga 1.6. p Po krovnem izreku ima časovno zahtevnost O( n) algoritem, katerega čas izvajanja T ( n) je opisan z rekurzivno zvezo ³ n ´ T ( n) = O(1) + 2 T . 4 Zapišimo tak algoritem: function KORENSKI( `[1 . . . n]) if n ≥ 4 then m ← b n 4 c KORENSKI( `[1... m]) KORENSKI( `[ n − m + 1... n]) end if end function 46 2.2 Celoštevilsko linearno programiranje Naloga 2.1. Naj bo G = ( V, E) dvodelen graf. Lahko torej zapišemo V = A ∪ B tako, da sta množici A in B disjunktni ter za vsako povezavo uv ∈ E velja u ∈ A, v ∈ B. Mno- žica M ⊂ E je prirejanje, če nobeni dve povezavi iz M nimata skupnega krajišča. Iščemo največje prirejanje M max. Za vsako povezavo uv ∈ E bomo uvedli spremenljivko xuv, katere vrednost interpretiramo kot (1, povezava uv je v množici M x max, in uv = 0 sicer. Zapišimo celoštevilski linearni program. X max xuv p.p. uv∈ E ∀ uv ∈ E : 0 ≤ xuv ≤ 1, xuv ∈ Z X ∀ u ∈ A : xuv ≤ 1 uv∈ E X ∀ v ∈ B : xuv ≤ 1 uv∈ E Naloga 2.2. Za i -tega asistenta (1 ≤ i ≤ n) in j -ti predmet (1 ≤ j ≤ m) bomo uvedli spremenljivki xi j in yi j , kjer je xi j število skupin, ki jih i-temu asistentu dodelimo pri j -tem predmetu, vrednost yi j pa interpretiramo kot (1, i-ti asistent bo izvajal vaje pri j-tem predmetu, in yi j = 0 sicer. Poleg tega bomo uvedli še spremenljivko t, s katero omejimo največje število različnih predmetov pri posameznem asistentu. Zapišimo celoštevilski linearni program. min t p.p. ∀ i ∈ {1,..., n} ∀ j ∈ {1,..., m} : xi j ≥ 0, xi j ∈ Z ∀ i ∈ {1,..., n} ∀ j ∈ {1,..., m} : 0 ≤ yi j ≤ 1, yi j ∈ Z xi j = 0 natanko tedaj, ko yi j = 0: ∀ i ∈ {1,..., n} ∀ j ∈ {1,..., m} : yi j ≤ xi j ≤ cj yi j Omejimo število ur za vsakega asistenta: m X ∀ i ∈ {1,..., n} : ai ≤ u j xi j ≤ bi j =1 47 Neželenih predmetov ne dodelimo: X ∀ i ∈ {1,..., n} : yi j = 0 j ∈ Ni Za vsak predmet dodelimo potrebno število skupin: n X ∀ j ∈ {1,..., m} : xi j = cj i =1 Nobenega predmeta ne dodelimo asistentoma p in q: ∀ j ∈ {1,..., m} : yp j + yq j ≤ 1 Število različnih predmetov na asistenta omejimo s t: n X ∀ i ∈ {1,..., n} : yi j ≤ t j =1 Naloga 2.3. Za stroj i (1 ≤ i ≤ n) bomo uvedli spremenljivko xi , dodatno za opravilo j in časovno enoto h (1 ≤ h, j ≤ m) pa še spremenljivko yi jh. Njihove vrednosti interpretiramo kot (1, če stroj i izvede vsaj eno opravilo, in xi = 0 sicer; (1, če stroj i izvede opravilo j v časovni enoti h, in ter yi jh = 0 sicer. Dodatno bomo uvedli še spremenljivko t, katere vrednost bo enaka časovni enoti dokončanja zadnjega stroja. Zapišimo celoštevilski linearni program. min t p.p. ∀ i ∈ {1,..., n} : 0 ≤ xi ≤ 1, xi ∈ Z ∀ i ∈ {1,..., n} ∀ j, h ∈ {1,..., m} : 0 ≤ yi jh ≤ 1, yi jh ∈ Z Vsako opravilo se izvede natanko enkrat: n X m X ∀ j ∈ {1,..., m} : yi jh = 1 i =1 h=1 Vsako stroj lahko hkrati opravlja največ eno opravilo: m X ∀ i ∈ {1,..., n} ∀ h ∈ {1,..., m} : yi jh ≤ 1 j =1 Omejitev stroškov obratovanja: m X m X ∀ i ∈ {1,..., n} : yi jh ≤ mxi j =1 h=1 n X cixi ≤ C i =1 48 Vrstni red opravil: n X m X ∀( j, k) ∈ P : h( yikh − yi jh) ≥ 1 i =1 h=1 Hkratnost opravil: n X ∀( j, k) ∈ S ∀ h ∈ {1,..., m} : ( yi jh + yikh) ≤ 1 i =1 Omejitev hkrati aktivnih strojev: n X m X ∀ h ∈ {1,..., m} : yi jh ≤ A i =1 j=1 Omejitev časa dokončanja: ∀ i ∈ {1,..., n} ∀ j, h ∈ {1,..., m} : hyi jh ≤ t Naloga 2.4. Za vsak strežnik h (0 ≤ h ≤ k), ponudnika i (1 ≤ i ≤ m) in posnetek j (1 ≤ j ≤ n) bomo uvedli spremenljivko xhi j , za strežnik h (1 ≤ h ≤ k) in posnetek j (1 ≤ j ≤ n) pa dodatno še spremenljivko yhj . Njihove vrednosti interpretiramo kot (1, ponudniku i pošiljamo posnetek j iz strežnika h, in xhi j = 0 sicer; (1, posnetek j naložimo na strežnik h, in ter yhj = 0 sicer. Zapišimo celoštevilski linearni program. k X m X n X min ri j `hi xhi j p.p. h=0 i=1 j=1 ∀ h ∈ {0,..., k} ∀ i ∈ {1,..., m} ∀ j ∈ {1,..., n} : 0 ≤ xhi j ≤ 1, xhi j ∈ Z ∀ h ∈ {1,..., k} ∀ j ∈ {1,..., n} : 0 ≤ yhj ≤ 1, yhj ∈ Z Omejitev prostora: n X ∀ h ∈ {1,..., k} : s j yhj ≤ ch j =1 Za dostavo mora biti posnetek prisoten na strežniku: ∀ h ∈ {0,..., k} ∀ i ∈ {1,..., m} ∀ j ∈ {1,..., n} : xhi j ≤ yhj Strežnika za posnetek ne uporabimo, če se nahaja na strežniku z manjšo latenco: ∀ h, t ∈ {0,..., k} ∀ i ∈ {1,..., m} ∀ j ∈ {1,..., n} : ( `hi − `ti )( xhi j + yt j ) ≤ 1 Vsak posnetek pošiljamo ponudniku iz natanko enega strežnika: m X ∀ h ∈ {0,..., k} ∀ j ∈ {1,..., n} : xhi j = 1 i =1 49 Naloga 2.5. Za i -tega trgovca (1 ≤ i ≤ n) bomo uvedli spremenljivke xi , yi in zi , pri čemer sta xi in yi število zabojev avokadov oziroma banan, ki jih distributer proda i-temu trgovcu, in zi število voženj tovornjakov, ki bodo sadje dostavili do i-tega trgovca. Poleg tega bomo uvedli še spremenljivki u in v, ki ju interpretiramo kot (1, trgovec p kupi avokade, in u = 0 sicer; (1, trgovec p kupi banane, in ter v = 0 sicer. Zapišimo celoštevilski linearni program. n X max ( ai xi + bi yi − di zi ) p.p. i =1 ∀ i ∈ {1,..., n} : 0 ≤ xi ≤ 1, xi ∈ Z ∀ i ∈ {1,..., n} : 0 ≤ yi ≤ 1, yi ∈ Z ∀ i ∈ {1,..., n} : 0 ≤ zi ≤ 1, zi ∈ Z 0 ≤ u ≤ 1, u ∈ Z 0 ≤ v ≤ 1, v ∈ Z Skupno število zabojev: n X xi ≤ A i =1 n X yi ≤ B i =1 Omejitev porabe trgovca: ∀ i ∈ {1,..., n} : ai xi + bi yi ≤ ci Število tovornjakov: ∀ i ∈ {1,..., n} : xi + yi ≤ K zi Trgovec p ne kupi obojega: xp ≤ Au yp ≤ Bv u + v ≤ 1 Trgovec q kupi avokade, če jih tudi r : xr ≤ Axq 50 Naloga 2.6. Očitno bomo potrebovali največ n delavcev, zato bomo za h-tega delavca (1 ≤ h ≤ n), i -to nalogo (1 ≤ i ≤ n) in k-to časovno enoto (1 ≤ k ≤ T ) uvedli spremenljivko xhik, katere vrednost interpretiramo kot (1; h-ti delavec začne izvajati i-to nalogo v k-ti časovni enoti, in xhik = 0 sicer. Poleg tega bomo uvedli še spremenljivko r , ki šteje število delavcev. Zapišimo celoštevilski linearni program, pri čemer uporabimo oznako Ti = T − ti + 1 za zadnji možen čas začetka i-te naloge. min r p.p. ∀ h, i ∈ {1,..., n} ∀ k ∈ {1,..., T } : 0 ≤ xhik ≤ 1, xhik ∈ Z r ≥ 0, r ∈ Z Vsako nalogo opravi natanko en delavec in jo pravočasno konča: n X Ti X ∀ i ∈ {1,..., n} : xhik = 1 h=1 k=1 Vsak delavec lahko hkrati izvaja samo eno nalogo: n X k+ ti−1 X ∀ h, i ∈ {1,..., n} ∀ k ∈ {1,..., Ti } : ( ti − 2) xhik + xhj` ≤ ti − 1 j =1 `= k Vrstni red opravljanja nalog: à ! n X Tj X ∀( i, j ) ∈ S ∀ k ∈ {1,..., Ti } : xhik − xhj` ≤ 0 h=1 `= k+ ti Štetje delavcev: ∀ h, i ∈ {1,..., n} ∀ k ∈ {1,..., T } : hxhik ≤ r Naloga 2.7. Naj bo m število vozlišč grafa G. Očitno bo linija obiskala največ m postaj, zato bomo za postajališče u ∈ V in i ∈ {1,..., m} uvedli spremenljivko xui , za vsako povezavo uv ∈ E pa še spremenljivko yuv. Njihove vrednosti interpretiramo kot (1; postajališče u obiščemo i-to po vrsti, in xui = 0 sicer; (1; postajališči u in v obiščemo zaporedoma, in ter yuv = 0 sicer. 51 Zapišimo celoštevilski linearni program. X n X max xui p.p. u∈ V i=1 ∀ u ∈ V ∀ i ∈ {1,..., m} : 0 ≤ xui ≤ 1, xui = Z ∀ uv ∈ E : 0 ≤ yuv ≤ 1, yuv = Z Vsako postajališče obiščemo največ enkrat: m X ∀ u ∈ V : xui ≤ 1 i =1 Naenkrat obiščemo največ eno postajališče: X ∀ i ∈ {1,..., m} : xui ≤ 1 u∈ V Indeksov ne izpuščamo: X X ∀ i ∈ {2,..., m} : xui ≤ xu, i−1 u∈ V u∈ V Nesosedna postajališča niso zaporedna: ∀ uv 6∈ E ∀ i ∈ {2,..., m} : xu, i−1 + xui + xv, i−1 + xvi ≤ 1 Začnemo v postajališču p 1: xp 1,1 = 1 Postajališča iz seznama si sledijo v podanem vrstnem redu: m X ∀ i ∈ {1,..., m} ∀ j ∈ {2,..., n} : xp x j −1, i ≤ p j , h h= i+1 Končamo v postajališču pn: X m X ∀ i ∈ {1,..., m} : ( m − i) xp x n , i + uh ≤ m − i u∈ V h= i+1 Časovna omejitev: ∀ uv ∈ E ∀ i ∈ {2,..., m} : xu, i−1 + xui + xv, i−1 + xvi ≤ yuv + 1 X cuvyuv ≤ T uv∈ E Naloga 2.8. Za igralca i ∈ A in j -ti klub (1 ≤ j ≤ n) bomo uvedli spremenljivko xi j , za igralca i ∈ B pa spremenljivko yi . Njihove vrednosti interpretiramo kot (1; igralca i prodamo j-temu klubu, in xi j = 0 sicer; (1; odkupimo ogralca i ter yi = 0 sicer. 52 Zapišimo celoštevilski linearni program. X X n X max qi yi − qi xi j p.p. i ∈ B i ∈ A j=1 ∀ i ∈ A ∀ j ∈ {1,..., n} : 0 ≤ xi j ≤ 1, xi j ∈ Z ∀ i ∈ B : 0 ≤ yi ≤ 1, y ∈ Z Vsakega igralca prodamo največ enemu klubu: n X ∀ i ∈ A : xi j ≤ 1 j =1 Omejitev stroškov: X X n X ri yi − pi j xi j ≤ S i ∈ B i ∈ A j=1 Skupno število igralcev: X X n X yi − xi j = 0 i ∈ B i ∈ A j=1 Število igralcev za vsako pozicijo: X X n X −1 ≤ yi − xi j ≤ 1 i ∈ B∩ G i ∈ A∩ G j=1 X X n X −1 ≤ yi − xi j ≤ 1 i ∈ B∩ D i ∈ A∩ D j=1 X X n X −1 ≤ yi − xi j ≤ 1 i ∈ B∩ M i ∈ A∩ M j=1 X X n X −1 ≤ yi − xi j ≤ 1 i ∈ B∩ F i ∈ A∩ F j=1 Igralca a in b gresta v isti klub: ∀ j ∈ {1,..., n} : xa j = xbj Naloga 2.9. (a) Naj bo xi število žetonov, ki jih vložimo v dvoboj z i-tim nasprotnikom (1 ≤ i ≤ n). Poleg tega bomo uvedli še spremenljivke yi in zi (1 ≤ i ≤ n), katerih vrednosti interpretiramo kot (1, če ne izgubimo proti i-temu nasprotniku, in yi = 0 sicer; ter (1, če premagamo i-tega nasprotnika, in zi = 0 sicer. 53 Zapišimo celoštevilski linearni program. n X max ( yi + 2 zi ) p.p. i =1 ∀ i ∈ {1,..., n} : xi ≥ 0, xi ∈ Z ∀ i ∈ {1,..., n} : 0 ≤ yi ≤ 1, yi ∈ Z ∀ i ∈ {1,..., n} : 0 ≤ zi ≤ 1, zi ∈ Z Porabimo M žetonov: n X xi = M i =1 yi = 1 natanko tedaj, ko xi ≥ ci : ∀ i ∈ {1,..., n} : ci yi ≤ xi ≤ ci − 1 + M yi zi = 1 natanko tedaj, ko xi > ci : ∀ i ∈ {1,..., n} : ( ci + 1) zi ≤ xi ≤ ci + M zi (b) Zapišimo še dodatne omejitve. Proti nasprotnikom iz A ne igramo izenačeno: ∀ i ∈ A : yi ≤ zi Največ dva poraza proti nasprotnikom iz B:X yi ≥| B|−2 i ∈ B Če izgubimo proti u, dosežemo vsaj 4 točke proti v in w: 4 yu + yv + yw + 2 zv + 2 zw ≥ 4 Največ k dvobojev z več kot t žetoni: ∀ i ∈ {1,..., n} : 0 ≤ ri ≤ 1, ri ∈ Z ∀ i ∈ {1,..., n} : xi ≤ t + Mri n X ri ≤ k i =1 Vsaj ` porazov: n X yi ≤ n− ` i =1 54 Naloga 2.10. Za i -to kolekcijo (1 ≤ i ≤ n) bomo uvedli spremenljivki xi in yi , kjer je xi število kupljenih izvodov i -te kolekcije, vrednost yi pa interpretiramo kot (1, kupimo vsaj en izvod i-te kolekcije, in yi = 0 sicer. Zapišimo celoštevilski linearni program. n X max (( di − ci ) xi + ei yi ) p.p. i =1 Omejitev števila izvodov: ∀ i ∈ {1,..., n} : 0 ≤ xi ≤ ki , xi ∈ Z ∀ i ∈ {1,..., n} : 0 ≤ yi ≤ 1, yi ∈ Z Povezava med xi in yi : ∀ i ∈ {1,..., n} : yi ≤ xi ≤ ki yi Omejitev kapitala za nakup: n X cixi ≤ C i =1 Omejitev števila proizvajalcev: n X yi ≤ K i =1 Omejitev proizvajalca p: xq + xr − xp ≤ ( kq + kr )(1 − yp) Naloga 2.11. Za h-ti dan (1 ≤ h ≤ m), i-to skupino (1 ≤ i ≤ n) in j -ti termin (1 ≤ j ≤ k) bomo uvedli spremenljivko xhi j , katere vrednost interpretiramo kot (1, i-ta skupina nastopi j-ta v h-tem dnevu festivala, in xhi j = 0 sicer. Zapišimo celoštevilski linearni program. m X n X k X max ai j xhi j p.p. h=1 i=1 j=1 ∀ h ∈ {1,..., m} ∀ i ∈ {1,..., n} ∀ j ∈ {1,..., j } : 0 ≤ xhi j ≤ 1, xhi j ∈ Z Vsaka skupina nastopi največ enkrat: ∀ i ∈ {1,..., n} : 55 m X k X xhij ≤1 h=1 j=1 Naenkrat nastopa ena skupina: ∀ h ∈ {1,..., m} ∀ j ∈ {1,..., k} : n X xhij =1 i =1 Omejitev plačila: m X n X k X mixhij ≤ M h=1 i=1 j=1 Vrstni red v dnevu: ∀ h ∈ {1,..., m} ∀ j ∈ {2,..., k} : n X mi( xhij − xh, i, j−1)≥0 i =1 Razporeditev po dnevih: ∀ h ∈ {2,..., n} : n X k X aij( xhij − xh−1, i, j)≥0 i =1 j=1 r ne nastopa, če nastopa s: m X k X ( xhrj + xhsj)≤1 h=1 j=1 t ne nastopa, če ni zadnja ali pred u: ∀ h ∈ {1,..., m} : k−1 X k X k−1 X k−1 X xht j ≤ j xhuj − j xht j ≤ k − ( k − 1) xht j j =1 j =2 j =1 j =1 v in w ne nastopata na isti dan: ∀ h ∈ {1,..., m} : k X ( xhvj + xhwj)≤1 j =1 Naloga 2.12. Za h-ti center (1 ≤ h ≤ m) ter i-tega in j -tega strokovnjaka (1 ≤ i, j ≤ n) bomo uvedli spremenljivko xhi j , katere vrednost interpretiramo kot   1, i-ti in j -ti strokovnjak sta oba nastanjena xhi j = v h-tem karantenskem centru, in  0 sicer. Informacija o tem, ali je i -ti strokovnjak nastanjen v h-tem centru, hrani spremenljivka xhii (1 ≤ h ≤ m, 1 ≤ i ≤ n). 56 Zapišimo celoštevilski linearni program. m X n X n X min pi j xhi j p.p. h=1 i=1 j=1 ∀ h ∈ {1,..., m} ∀ i, j ∈ {1,..., n} : 0 ≤ xhi j ≤ 1, xhi j ∈ Z Vsak strokovnjak je nastanjen v natanko enem centru: m X ∀ i ∈ {1,..., n} : xhii = 1 h=1 Kapacitete centrov: n X ∀ h ∈ {1,..., m} : xhii ≤ kh i =1 Povezava med xhii in xhi j : ∀ h ∈ {1,..., m} ∀ i, j ∈ {1,..., n} : 2 xhi j ≤ xhii + xhj j ≤ xhi j + 1 Območja z mutacijo: m X ∀ i ∈ A ∀ j 6∈ A : xhi j = 0 h=1 Sorodniki: m X ∀( i, j ) ∈ B : xhi j = 1 h=1 57 18:00 2/3 18:20 zelena: FF1 19:00 rdeča: 1/3 zelena: 1/10 FE 16:00 18:00 18:00 1 2/3 zelena: peš 17:48 rdeča: zelena: 1/2 FF6 9/10 FF1 19:00 avtobus čakamo 1 rdeča: 1/2 17:50 17:54 rde 18:00 18:30 6 ča: 1/3 zelena: 1/10 FE 17:00 19:00 peš avtobus rdeča: 9/10 18:00 čakamo 1 16:52.5 18:00 avtobus zelena: 1/10 FE 18:00 14 vlak: 1/20 18:18 rdeča: peš vlak 9/10 20:00 18:00 n 16:48 16:52.5 i vlaka: 18:20 čaka zelena: 2/3 19/2 zelena: 1/10 mo 0 FE 15:00 1 FF1 19:00 r rdeča: 1/3 deč peš 18:20 a: 9/10 17:00 18:00 17:00 čakamo zelena: 2/3 1 FF1 19:00 rdeča: 1/3 18:20 Slika 23: Odločitveno drevo za nalogo 3.1. 2.3 Teorija odločanja Naloga 3.1. Izračunamo lahko, da pot z avtobusom 1 traja 18 minut oziroma minuto dlje ob rdečem semaforju pri FF, pot z avtobusom 6 in naknadno pešačenje traja 16 minut ter minuto dlje ob rdečem semaforju pri FF in še dve minuti dlje ob rdečem semaforju pri FE, pot z avtobusom 14 in naknadno pešačenje pa traja 15 minut ter tri minute dlje ob čakanju na vlak in še dve minuti dlje ob rdečem semaforju pri FE. Če gremo na avtobus 6 in pri FF naletimo na zeleno luč, potem je verjetnost, da tudi avtobus 1 tam naleti na zeleno luč, enaka 1/3 1 P(avtobus 1 ima zeleno pri FF | avtobus 6 ima zeleno pri FF) = = . 2/3 2 S temi podatki lahko narišemo odločitveno drevo s slike 23, s katerega je razvidno, da pričakovani čas trajanja minimiziramo, če gremo na avtobus 14, potem pa v primeru čakanja na vlak in rdeče luči pri FE počakamo na avtobus 1, sicer pa pot nadaljujemo peš. Pričakovani čas trajanja poti je tako 16 minut in 52.5 sekund. 58 Naloga 3.2. Naj bo A dogodek, da izvedenec pripiše večje možnosti prvemu podjetju, ter B 1, B 2 in B 0 dogodki, da uspe prvo, drugo oziroma nobeno podjetje. Izračunajmo verjetnosti za mnenje izvedenca ter uspešnosti podjetij v odvisnosti od njega. P( A) = 0.4 · 0.8+ 0.1 · 0.3+0.5 · 0.4 = 0.55 P( A) = 0.4 · 0.2+ 0.1 · 0.7+0.5 · 0.6 = 0.45 0.5 · 0.4 4 P( B 0 | A) = = 0.55 11 0.4 · 0.8 32 P( B 1 | A) = = 0.55 55 0.1 · 0.3 3 P( B 2 | A) = = 0.55 55 0.5 · 0.6 2 P( B 0 | A) = = 0.45 3 0.4 · 0.2 8 P( B 1 | A) = = 0.45 45 0.1 · 0.7 7 P( B 2 | A) = = 0.45 45 S pomočjo zgoraj izračunanih verjetnosti lahko narišemo odločitveno drevo s slike 24. Odločimo se torej za mnenje izvedenca – če je to naklonjeno prvemu podjetju, kupimo njegove delnice, sicer pa ne kupimo ničesar. Pričakovan dobiček je 3100e. Naloga 3.3. Naj bo A dogodek, da nasprotnik na začetku vloži 10 žetonov, Bn dogodek, da odgovorimo z n žetoni ( n ∈ {0,10,20}), C dogodek, da nasprotnik za tem izenači, in D dogodek, da dobimo igro. Izračunajmo ustrezne pogojne verjetnosti. P( A) = 0.6 · 0.3 + 0.4 · 0.8 = 0.5 P( A) = 0.6 · 0.7 + 0.4 · 0.2 = 0.5 0.6 · 0.3 · 0.1 + 0.4 · 0.8 · 0.8 P( C | A ∩ B 20) = = 0.548 0.5 0.6 · 0.3 · 0.9 + 0.4 · 0.8 · 0.2 P( C | A ∩ B 20) = = 0.452 0.5 0.6 · 0.7 · 0.2 + 0.4 · 0.2 · 0.7 P( C | A ∩ B 10) = = 0.28 0.5 0.6 · 0.7 · 0.8 + 0.4 · 0.2 · 0.3 P( C | A ∩ B 10) = = 0.72 0.5 0.6 · 0.7 · 0.1 + 0.4 · 0.2 · 0.8 P( C | A ∩ B 20) = = 0.212 0.5 0.6 · 0.7 · 0.9 + 0.4 · 0.2 · 0.2 P( C | A ∩ B 20) = = 0.788 0.5 0.6 · 0.3 · 0.8 + 0.4 · 0.8 · 0.1 P( D | A ∩ B 10) = = 0.352 0.5 59 −1000e 19000e 6454.55e ne kupi uspešno: 0.582 −11000e kupi prvo neuspešno: 0.418 6454.55e kupi 19000e vo: 0.55 drugo pr uspešno: 0.055 za −4636.36e −6000e 3100e neuspešno: 0.945 za drugo: −1000e 19000e enje mn 0.4 ne kupi 5 uspešno: 0.178 −11000e 3100e kupi prvo neuspešno: 0.822 −1000e −5666.67e kupi 19000e drugo uspešno: 0.156 br −2111.11e −6000e ez neuspešno: 0.844 mnenja 0e 20000e 0.4 ne kupi uspešno: −10000e kupi prvo neuspešno: 0.6 2000e 2000e kupi 20000e dr 0.1 ugo uspešno: −5000e neuspešno: 0.9 −2500e Slika 24: Odločitveno drevo za nalogo 3.2. 0.6 · 0.3 · 0.2 + 0.4 · 0.8 · 0.9 P( D | A ∩ B 10) = = 0.648 0.5 0.6 · 0.3 · 0.1 · 0.8 + 0.4 · 0.8 · 0.8 · 0.1 P( D | A ∩ B 20 ∩ C) = ≈ 0.146 0.5 · 0.548 0.6 · 0.3 · 0.1 · 0.2 + 0.4 · 0.8 · 0.8 · 0.9 P( D | A ∩ B 20 ∩ C) = ≈ 0.854 0.5 · 0.548 0.6 · 0.7 · 0.8 + 0.4 · 0.2 · 0.1 P( D | A ∩ B 0) = = 0.688 0.5 0.6 · 0.7 · 0.2 + 0.4 · 0.2 · 0.9 P( D | A ∩ B 0) = = 0.312 0.5 0.6 · 0.7 · 0.2 · 0.8 + 0.4 · 0.2 · 0.7 · 0.1 P( D | A ∩ B 10 ∩ C) = = 0.52 0.5 · 0.28 0.6 · 0.7 · 0.2 · 0.2 + 0.4 · 0.2 · 0.7 · 0.9 P( D | A ∩ B 10 ∩ C) = = 0.48 0.5 · 0.28 0.6 · 0.7 · 0.1 · 0.8 + 0.4 · 0.2 · 0.8 · 0.1 P( D | A ∩ B 20 ∩ C) = ≈ 0.377 0.5 · 0.212 60 11.28 zmagamo: 0.688 30 imo izgubimo: 0.312 −30 ne vlož 22.048 22.048 višamo 10 odstopi: 0.72 30 40 o: 0.52 izena zmagam či: 0.5 viša 0.28 −40 ži: mo izbugimo: 0.48 vlo 20 odstopi: 0.788 1.6 ne 30 50 10.364 mo: 0.377 21.04 izena zmaga či: 0.212 −50 izgubimo: 0.623 −12.264 vi −30 ša 10: 0.5 opimo 40 odst mo: 0.352 zmaga −40 izenačimo izgubimo: 0.648 −1.32 −11.84 viša 40 50 mo 1 mo: 0.146 0 odstopi: 0.452 zmaga −50 izenači: 0.548 izgubimo: 0.854 −1.32 −35.401 Slika 25: Odločitveno drevo za nalogo 3.3. 0.6 · 0.7 · 0.1 · 0.2 + 0.4 · 0.2 · 0.8 · 0.9 P( D | A ∩ B 20 ∩ C) = ≈ 0.623 0.5 · 0.212 S pomočjo zgoraj izračunanih verjetnosti lahko narišemo odločitveno drevo s slike 25. Opazimo, da se nam v vsakem primeru izplača višati za 10 žetonov (tj., če nasprotnik na začetku vloži 10 žetonov, odgovorimo z 20 žetoni). Pričakovani dobiček je 10.364 žetonov. Naloga 3.4. Izračunajmo najprej pričakovane vrednosti v vozliščih F , G in H odločitvenega drevesa s slike 2. F = 25 · 2 p − 10 · (1 − 2 p) = 70 p − 10 G = 50 · p − 10 · (1 − p) = 60 p − 10 H = 30 · 4 p − 30 · (1 − 4 p) = 240 p − 30 Obravnavajmo najprej odločitve v vozliščih C , D in E. Za pot od vozlišča C k vozlišču F se odločimo, če velja 70 p − 10 ≥ 0 oziroma p ≥ 1/7. Za pot od vozlišča D k vozlišču G se odločimo, če velja 60 p − 10 ≥ −5 oziroma p ≥ 1/12. Za pot od vozlišča E k vozlišču H se odločimo, če velja 240 p − 30 ≥ −5 oziroma 61 p ≥ 5/48. Sedaj lahko izračunamo pričakovano vrednost v vozlišču B v odvisnosti od parametra p. 1 0 ≤ p < ⇒ B = 0.6 · (−5) + 0.4 · (−5) = −5 12 1 5 ≤ p < ⇒ B = 0.6 · (60 p − 10) + 0.4 · (−5) = 36 p − 8 12 48 5 1 ≤ p ≤ ⇒ B = 0.6 · (60 p − 10) + 0.4 · (240 p − 30) = 132 p − 18 48 4 Obravnavajmo sedaj še odločitev v vozlišču A – za pot k vozlišču B se odločimo, če velja: 1 0 ≤ p < : −5 ≥ 0 ⇒ ⊥ 12 1 5 ≤ p < : 36 p − 8 ≥ 0 ⇒ ⊥ 12 48 5 1 3 1 ≤ p < : 132 p − 18 ≥ 0 ⇒ ≤ p < 48 7 22 7 1 1 1 1 ≤ p ≤ : 132 p − 18 ≥ 70 p − 10 ⇒ ≤ p ≤ 7 4 7 4 Odločamo se torej po sledečem pravilu. • Če je 0 ≤ p < 3/22, se odločimo za pot preko vozlišča C v list z vrednostjo 0. • Če je 1/7 ≤ p < 3/22, se odločimo za pot preko vozlišča B. – Če pridemo v vozlišče D, se odločimo za pot preko vozlišča G. – Če pridemo v vozlišče E, se odločimo za pot preko vozlišča H. Pričakovana vrednost je 132 p − 18 ∈ [0,15]. Proces odločanja je prikazan na sliki 26. Naloga 3.5. (a) Izračunajmo pričakovane dobičke pri različnih pogojih: Izdela 500, prodaja po 50e, tržno zanimiv: −10000e + 500 · 50e = 15000e Izdela 500, prodaja po 50e, tržno nezanimiv: −10000e + 250 · 50e = 2500e Izdela 500, prodaja po 60e, tržno zanimiv: −10000e + 500 · 60e = 20000e Izdela 500, prodaja po 60e, tržno nezanimiv: −10000e + 100 · 60e = −4000e 62 60 p − 10 p 50 G 1/12 ≤ p ≤ 1/4 D 1 − p −10 0.6 0 ≤ p < 1/12 −5 B 240 p − 30 4 p 30 H 2 ≤ p ≤ 1/4 0.4 5/48 ≤ p ≤ 1/4 3/2 E 1 −4 p −30 0 A ≤ p 0 < 5/48 −5 ≤ p 70 p < − 10 2 p 25 3/22 F 1/7 ≤ p ≤ 1/4 C 1 −2 p −10 0 ≤ p < 1/7 0 Slika 26: Odločitveno drevo za nalogo 3.4 v odvisnosti od vrednosti parametra p. Izdela 1000, prodaja po 50e, tržno zanimiv: −18000e + 650 · 50e = 14500e Izdela 1000, prodaja po 50e, tržno nezanimiv: −18000e + 250 · 50e = −5500e Izdela 1000, prodaja po 60e, tržno zanimiv: −18000e + 550 · 60e = 15000e Izdela 1000, prodaja po 60e, tržno nezanimiv: −18000e + 100 · 60e = −12000e Odločitveno drevo je prikazano na sliki 27. Podjetnik naj se odloči, da naroči izdelavo 500 izdelkov, te pa prodaja po ceni 60e. Pričakovani dobiček je tedaj 15200e. (b) Najprej določimo verjetnosti, ki jih bomo potrebovali za odločitev. P(zmaga) = 0.6 · 0.8 + 0.1 · 0.2 = 0.5 P(ne zmaga) = 0.4 · 0.8 + 0.9 · 0.2 = 0.5 0.6 · 0.8 P(zanimiv | zmaga) = = 0.96 0.5 0.1 · 0.2 P(ni zanimiv | zmaga) = = 0.04 0.5 0.4 · 0.8 P(zanimiv | ne zmaga) = = 0.64 0.5 63 0.9 · 0.2 P(ni zanimiv | ne zmaga) = = 0.36 0.5 Sedaj izračunajmo pričakovane dobičke pri različnih pogojih po zmagi na razpisu. Opazimo, da v nobenem pogoju pričakovano število prodanih izdelkov ne bo preseglo količine 980 izdelkov, kolikor jih ostane po kontroli kvalitete. Če ne zmaga na razpisu, so pričakovani dobički enaki tistim iz točke (a) pri izdelavi 1000 kosov. Zmaga, prodaja po 50e, tržno zanimiv: −18000e + 650 · 50e · 1.2 + k = 21000e + k Zmaga, prodaja po 50e, tržno nezanimiv: −18000e + 250 · 50e · 1.2 + k = −3000e + k Zmaga, prodaja po 60e, tržno zanimiv: −18000e + 550 · 60e · 1.2 + k = 21600e + k Zmaga, prodaja po 60e, tržno nezanimiv: −18000e + 100 · 60e · 1.2 + k = −10800e + k Z zgornjimi podatki lahko narišemo odločitveno drevo s slike 28. Izračunajmo pričakovane dobičke v vozliščih E, F, G, H. E =0.96 · (21000e + k) + 0.04 · (−3000e + k) = 20040e + k F =0.96 · (21600e + k) + 0.04 · (−10800e + k) = 20304e + k G = 0.64 · 14500e − 0.36 · 5500e = 7300e H = 0.64 · 15000e − 0.36 · 12000e = 5280e Očitno je v vozlišču C ugodnejša pot k vozlišču F , v vozlišču D pa je ugodnejša pot k vozlišču G – velja torej C = 20304e + k in D = 7300e. Sedaj lahko izračunamo še pričakovano vrednost v vozlišču B. k B = 0.5 · (20304e + k) + 0.5 · 7300e = 13802e + 2 Podjetnik naj se torej prijav na razpis, če velja 13802e + k/2 ≥ 15200e oziroma k ≥ 2796e. Če nato zmaga na razpisu, naj izdelke prodaja po ceni 60e, v nasprotnem primeru pa naj jih prodaja po ceni 50e. Pričakovani dobiček je tedaj 13802e + k/2 ∈ [15200e,16302e]. Če velja k < 2796e, naj se podjetnik ne prijavi na razpis. Tako kot v točki (a) naj naroči izdelavo 500 izdelkov, te pa prodaja po ceni 60e. Pričakovani dobiček je tedaj 15200e. 64 12500e zanimiv: 0.8 15000e 50e nez a po animiv: 0.2 2500e 15200e prodaj 15200e zanimiv: 0.8 20000e prodaja po 60e neza a 500 nimiv: 0 izdel .2 −4000e 15200e izdela 0 0e izdel 14500e a 10 : 0.8 00 prodaja po 50e zanimiv −5500e nezanimiv: 0.2 10500e pr 10500e odaja 15000e po : 0.8 60e zanimiv −12000e nezanimiv: 0.2 9600e Slika 27: Odločitveno drevo za nalogo 3.5(a). 20040e + k zanimiv: 0.96 15200e E 21000e + k 50e ne po zanimiv: 0.04 −3000e+ k 20304e + k prodaja 20304e + k se ne prijavi 1000e ≤ k < 2796e zanimiv: 0.96 A C F 21600e + k se prodaja po 60e 2 pr ne 79 zan i : 0.5 imiv 6 javi e : 0.04 ≤ zmaga −10800e + k k ≤ 5000e B 13802e + k/2 ne zmag 14500e a: : 0.64 0.5 prodaja po 50e zanimiv D G −5500e nezanimiv: 0.36 7300e pr 7300e odaja 15000e po : 0.64 60e zanimiv H −12000e nezanimiv: 0.36 5280e Slika 28: Odločitveno drevo za nalogo 3.5(b) v odvisnosti od vrednosti parametra k. 65 Naloga 3.6. Če se odločimo za pot okoli gorovja, bomo porabili 12 ur, če se pa odločimo za pot čez prelaz, bomo porabili 6, 10 oziroma 14 ur, če je ta čist, delno zasnežen oziroma neprevozen. Če se pred tem odločimo za obisk vrača, se čas potovanja podaljša za eno uro. Pričakovano število ur potovanja, če ne obiščemo vrača in se odločimo za pot čez prelaz, je enako 0.2 · 6 + 0.1 · 10 + 0.7 · 14 = 12, kar je ravno enako kot pot okoli gorovja. Izračunajmo še verjetnosti za primer, da se odločimo za obisk vrača. 3 P(mir) = 0.9 · 0.2 + 0.5 · 0.1 + 0.1 · 0.7 = 107 P(vojna) = 0.1 · 0.2 + 0.5 · 0.1 + 0.9 · 0.7 = 10 0.9 · 0.2 3 P(čist | mir) = = 3/10 5 0.5 · 0.1 1 P(delno zasnežen | mir) = = 3/10 6 0.1 · 0.7 7 P(neprevozen | mir) = = 3/10 30 0.1 · 0.2 1 P(čist | vojna) = = 7/10 35 0.5 · 0.1 1 P(delno zasnežen | vojna) = = 7/10 14 0.9 · 0.7 9 P(neprevozen | vojna) = = 7/10 10 S pomočjo zgoraj izračunanih verjetnosti lahko narišemo odločitveno drevo s slike 29. Opazimo, da se nam izplača iti k vraču ter se odločiti za pot čez prelaz, če nam pove, da na gori vlada mir, in za pot okoli gorovja v nasprotnem primeru. Naloga 3.7. Izračunajmo najprej pričakovane vrednosti v vozliščih C , F in G odločitvenega drevesa s slike 4. C = 0.5 · (40 p + 20) = 20 p + 10 F = 50 · p − 10 · (1 − p) = 60 p − 10 G = −30 · p + 30 · (1 − p) = −60 p + 30 Obravnavajmo najprej odločitev v vozlišču D. Za pot k vozlišču F se odločimo, če velja 60 p − 10 ≥ −5 oziroma p ≥ 1/12. Obravnavajmo sedaj še odločitev v vozlišču E. Za pot k vozlišču G se odločimo, če velja −60 p + 30 ≥ −5 oziroma p ≤ 7/12. 66 6 12 čist: 1/5 zasnežen: 1/1010 12 prelaz neprevozen: 7/10 14 7 čist: 3/5 k vraču okoli zasnežen: 1/6 12 11 gremo 11.96 ne prelaz 9.53 neprevozen: 7/30 15 9.53 gr okol emo : 3/10 i 13 7 k v mir ra čist: 1/35 ču zasnežen: 1/1411 prelaz 11.96 vojna: 14.49 nep 7 rev /10 ozen: 9/10 15 13 okoli 13 Slika 29: Odločitveno drevo za nalogo 3.6. Pričakovana vrednost v vozlišču B bo sledeča. 1 p < : 0.9 · (−5) + (−60 p + 30) · 0.1 = −1.5 − 6 p 12 1 7 ≤ p ≤ : 0.9 · (60 p − 10) + 0.1 · (−60 p + 30) = −6 + 48 p 12 12 7 p > : 0.9 · (60 p − 10) + 0.1 · (−5) = −9.5 + 54 p 12 Obravnavajmo sedaj še odločitev v vozlišču A. 1 0 ≤ p < : max{−1.5 − 6 p,20 p + 10} = 20 p + 10 12 ( 1 7 20 p + 10 p < 4 ≤ p ≤ : max{−6 + 48 p,20 p + 10} = 7 12 12 −6 + 48 p p ≥ 47 7 p > : max{−9.5 + 54 p,20 p + 10} = −9.5 + 54 p 12 Proces odločanja je prikazan na sliki 30. Naloga 3.8. Če se podjetje odloči za samostojno prodajo (brez predhodne akcijske ponudbe), bo ob uspehu imelo 100000·(3e−0.5e)−1000e = 249000e dobička, ob neuspehu pa 10000 ·3e−100000·0.5e−1000e = −21000e, torej 21000e izgube. Ker je pričakovani dobiček enak 0.7 · 249000e − 0.3 · 21000e = 168000e, 67 60 p − 10 p 50 F p ≥ 1/12 1 D − p −10 0.9 p < 1/12 −5 B −60 p + 30 30 1 − p 4/7 G 0. p ≥ 1 p ≤ 7/12 E p −30 p A > 7/12 −5 p <4/7 20 p+10 40 p + 20 0.5 C 0.5 0 Slika 30: Odločitveno drevo za nalogo 3.7 v odvisnosti od vrednosti parametra p. kar je več kot 100000 · 1e = 100000e, kolikor bi zaslužili ob prodaji multinacionalki, se podjetju v primeru, da se ne odločijo za akcijsko ponudbo, bolj izplača samostojna prodaja. Izračunajmo še dobičke, če se odločijo za akcijsko ponudbo: Akcija uspe, produkt uspe: 1000 · 2.5e + 99000 · 3e − 100000 · 0.5e − 2 · 1000e = 247500e Akcija uspe, produkt ne uspe: 1000 · 2.5e + 9000 · 3e − 100000 · 0.5e − 2 · 1000e = −22500e Akcija uspe, prodajo multinacionalki: 1000 · (2.5e − 0.5e) + 99000 · 1e − 1000e = 100000e Akcija ne uspe, produkt uspe: 100 · 2.5e + 99900 · 3e − 100000 · 0.5e − 2 · 1000e = 247950e Akcija ne uspe, produkt ne uspe: 100 · 2.5e + 9900 · 3e − 100000 · 0.5e − 2 · 1000e = −22050e Akcija ne uspe, prodajo multinacionalki: 100 · 2.5e − 1000 · 0.5e − 1000e + 99000 · 1e = 97750e Izračunajmo še verjetnosti uspeha akcije ter uspešnosti produkta ob vsaki napovedi. P(akcija uspešna) = 0.7 · 0.8 + 0.3 · 0.1 = 0.59 68 247500e 233771.2e uspeh: 0.949 o 233771.2e prodajaj sami neuspeh: 0.051 −22500e 9 prodaj a: 0.5 o multinacionalki 100000e uspešn 178002.5e 247950e o 70145.1e n uspeh: 0.341 euspešn akcij o a: 0.4 sami prodajaj neuspeh izvedejo 1 : 0.659 −22050e pr 97750e odajo multina 178002.5e cionalki 97750e ne 249000e izv 0.7 edej 168000e uspeh: o akc o ije prodajaj sami neuspeh: 0.3 −21000e pr 168000e odajo multinacionalki 100000e Slika 31: Odločitveno drevo za nalogo 3.8. P(akcija neuspešna) = 0.7 · 0.2 + 0.3 · 0.9 = 0.41 0.7 · 0.8 56 P(produkt uspe | akcija uspešna) = = ≈ 0.949 0.59 59 0.3 · 0.1 3 P(produkt ne uspe | akcija uspešna) = = ≈ 0.051 0.59 59 0.7 · 0.2 14 P(produkt uspe | akcija neuspešna) = = ≈ 0.341 0.41 41 0.3 · 0.9 27 P(produkt ne uspe | akcija neuspešna) = = ≈ 0.659 0.41 41 S pomočjo zgoraj izračunanih verjetnosti lahko narišemo odločitveno drevo s slike 31. Opazimo, da se podjetju izplača izvesti akcijo, saj je pričakovani dobiček v tem primeru 178002.5e. Če akcija uspe, naj se odločijo za samostojno prodajo, če pa ne uspe, pa naj zaloge prodajo multinacionalki. Naloga 3.9. Izračunajmo verjetnosti za potek servisa in stanje strojev po izvedenem servisu. P(servis poteka gladko) = 0.9 · 0.4 + 0.2 · 0.6 = 0.48 P(servis se zavleče) = 0.1 · 0.4 + 0.8 · 0.6 = 0.52 69 70000 kg 65275 kg dobro stanje: 0.925 slabo o: 0.48 stanje: 0.075 7000 kg gladk 46532 kg vis t ser ežav 50000 kg jo e: avi 0.52 dobro stanje: 0.538 opr 29230.77 kg slabo stanje: 46532 kg 0.462 5000 kg ne opravijoser 80000 kg visa dobro stanje: 0.4 36800 kg slabo stanje: 0.6 8000kg Slika 32: Odločitveno drevo za nalogo 3.9. 0.9 · 0.4 + 0.2 · 0.6 · 0.7 P(stroji v dobrem stanju | servis poteka gladko) = = 0.925 0.48 0.2 · 0.6 · 0.3 P(stroji v slabem stanju | servis poteka gladko) = = 0.075 0.48 0.1 · 0.4 + 0.8 · 0.6 · 0.5 P(stroji v dobrem stanju | servis se zavleče) = ≈ 0.538 0.52 0.8 · 0.6 · 0.5 P(stroji v slabem stanju | servis se zavleče) = ≈ 0.462 0.52 S pomočjo zgoraj izračunanih verjetnosti lahko narišemo odločitveno drevo s slike 32. Opazimo, da se podjetju izplača opraviti servis, pričakovana količina proizvedene čokolade pa je tedaj 46532 kg. Naloga 3.10. Izračunajmo najprej pričakovane vrednosti v vozliščih F in G odločitvenega drevesa s slike 5. F = 160 · p + 40 · (1 − p) = 120 p + 40 G = 120 · 2 p + 20 · (1 − 2 p) = 200 p + 20 Obravnavajmo najprej odločitev v vozlišču D. Za pot k vozlišču F se odločimo, če velja 120 p + 40 < 60 oziroma p < 1/6. 70 Obravnavajmo sedaj še odločitev v vozlišču E. Za pot k vozlišču G se odločimo, če velja 200 p + 20 < 50 oziroma p < 3/20. Pričakovana vrednost v vozlišču B bo sledeča. 1 p < : 0.7 · (120 p + 40) + 0.3 · (100 p + 30) = 114 p + 37 61 p ≥ : 0.7 · 60 + 0.3 · (100 p + 30) = 30 p + 51 6 Izračunajmo še pričakovano vrednost v vozlišču C . 3 p < : 0.6 · (200 p + 20) + 0.4 · 70 = 120 p + 40 20 3 p ≥ : 0.6 · 50 + 0.4 · 70 = 58 20 Nazadnje obravnavajmo še odločitev v vozlišču A. 3 0 ≤ p < : min{114 p + 37,120 p + 40} = 114 p + 37 20 3 1 ≤ p < : min{114 p + 37,58} = 114 p + 37 20 6 ( 1 1 30 p + 51 p < 7 ≤ p ≤ : min{30 p + 51,58} = 30 6 2 58 p ≥ 730 Proces odločanja je prikazan na sliki 33. Ker velja 7 , opazimo, da v 30 > 3 20 primeru p ≥ 7 iz vozlišča E nikoli ne izberemo poti proti vozlišču G. 30 Naloga 3.11. (a) Naj bo Xk (200 ≤ k ≤ 203) dobiček, če družba proda k vozovnic. E( X 200) = 200 · 35e = 7000e E( X 201) = 201 · 35e − 0.3 · 60e = 7017e E( X 202) = 202 · 35e − (0.3 · 2 + 0.4) · 60e = 7010e E( X 203) = 203 · 35e − (0.3 · 3 + 0.4 · 2 + 0.2) · 60e = 6991e Vidimo, da se družbi najbolj izplača prodati 201 vozovnico. (b) Naj bo Yk (200 ≤ k ≤ 203) dobiček, če družba proda k vozovnic, pri čemer lahko uporabi tudi dodatno mesto. E( Y 200) = 200 · 35e = 7000e E( Y 201) = 201 · 35e − 0.3 · 0.001 · 40000e = 7023e E( Y 202) = 202 · 35e − 0.3 · 60e − 0.7 · 0.001 · 40000e = 7024e E( Y 203) = 203 · 35e − (0.3 · 2 + 0.4) · 60e − 0.9 · 0.001 · 40000e = 7009e Največji pričakovan dobiček je dosežen pri prodaji 202 vozovnic. Ker je ta večji kot v primeru, ko se dodatno mesto ne uporabi, se družbi torej to mesto izplača uporabiti. 71 120 p + 40 p 160 F p < 1/6 D 1 − p 40 0.7 p ≥ 1/6 60 B 0 0.3 100 p 7/3 + 30 p < 200 p + 20 2 p 120 A G p < 3/20 1 E − 2 p 20 p ≥7/3 0.6 p ≥ 3/20 50 0 C 0.4 70 Slika 33: Odločitveno drevo za nalogo 3.10 v odvisnosti od vrednosti parametra p. 72 2.4 Dinamično programiranje Naloga 4.1. Naj bo pi j največji dobiček, ki ga lahko iztržimo z rezanjem kosa blaga dimenzij i × j (1 ≤ i ≤ m, 1 ≤ j ≤ n). Določimo rekurzivne enačbe. ¡© ¯ ª pi j = max c ¯ h 1 ≤ h ≤ k ∧ ( ah , bh ) ∈ {( i , j ), ( j , i )}} © ¯ ª ∪ p ¯ ` j + pi − `, j 1 ≤ ` ≤ i /2 © ¯ ª ¢ ∪ p ¯ ì + pi , j − ` 1 ≤ ` ≤ j /2 ∪ {0} Prva množica tukaj obravnava primere, ko imamo kos blaga želene velikosti, naslednji dve pa obravnavata vodoravne oziroma navpićne reze. Zadnja množica poskrbi, da je vrednost p 11 definirana tudi v primeru, ko nam kos blaga velikosti 1 × 1 ne prinese dobička. Vrednosti pi j računamo v leksikografskem vrstnem redu indeksov (npr. najprej naraščajoče po i , nato pa naraščajoče po j ). Maksimalni dobiček dobimo kot p∗ = pmn. Naloga 4.2. Algoritem, ki izhaja iz rekurzivnih enačb, ima časovno zahtevnost O( mn( m + n + k)). Z ustrezno podatkovno strukturo (zgoščena tabela) je mogoče časovno zahtevnost izboljšati na O( mn( m + n) + k). Izračunajmo vrednosti pi j (1 ≤ i ≤ m,1 ≤ j ≤ n) po rekurzivnih enačbah iz rešitve naloge 4.1. Pri tem upoštevamo, da velja pi j = p ji , tako da bomo izračunali samo primere z i ≥ j . p 11 = max{0} = 0 p 21 = max{0 + 0,0} = 0 p 22 = max{6,0 + 0,0} = 6 izdelek 1 p 31 = max{3,0 + 0,0} = 3 izdelek 2 p 32 = max{7,0 + 6,3 + 3,0} = 7 izdelek 4 p 33 = max{3 + 7,0} = 10 razrez na 1 × 3 in 2 × 3 p 41 = max{5,0 + 3,0 + 0,0} = 5 izdelek 3 p 42 = max{0 + 7,6 + 6,5 + 5,0} = 12 razrez na 2 × 3 in 2 × 2 p 43 = max{3 + 10,7 + 7,5 + 12,0} = 17 razrez na 4 × 1 in 4 × 2 p 51 = max{0 + 5,0 + 3,0} = 5 razrez na 1 × 1 in 4 × 1 p 52 = max{0 + 12,6 + 7,5 + 5,0} = 13 razrez na 2 × 2 in 3 × 2 p 53 = max{3 + 17,7 + 10,5 + 13,0} = 20 razrez na 1 × 3 in 4 × 3 Maksimalni dobiček je torej p∗ = p 53 = 20, dosežemo pa ga tako, da iz prvotnega kosa blaga dimenzij 5 × 3 odrežemo kos dimenzij 1 × 3 za izdelek s ceno 3, nato od preostanka dimenzij 4 × 3 odrežemo kos dimenzij 4 × 1 za izdelek s ceno 5, 73 nazadnje pa preostanek dimenzij 4 × 2 razrežemo na dva kosa dimenzij 2 × 2 za izdelka s ceno 6. Naloga 4.3. (a) Naj bo xi največji produkt strnjenega podzaporedja, ki se konča pri številu ai , in yi najmanjši tak produkt. Določimo začetne pogoje in rekurzivne enačbe. x 1 = y 1 = a 1 xi = max{ ai , ai xi−1, ai yi−1} (2 ≤ i ≤ n) yi = min{ ai , ai xi−1, ai yi−1} (2 ≤ i ≤ n) Vrednosti xi in yi računamo naraščajoče po indeksu i. Največji produkt strnjenega podzaporedja dobimo kot x∗ = max{ xi | 1 ≤ i ≤ n}. (b) Za izračun vrednosti xi in yi pri vsakem i potrebujemo konstantno časa. Ker naredimo n takih korakov, je časovna zahtevnost algoritma O( n). (c) Izračunajmo vrednosti xi in yi (2 ≤ i ≤ 10). x 2 = max{−2,−2 · 0.9,−2 · 0.9} = −1.8 y 2 = min{−2,−2 · 0.9,−2 · 0.9} = −2 x 3 = max{−0.6,−0.6 · −1.8,−0.6 · −2} = 1.2 y 3 = min{−0.6,−0.6 · −1.8,−0.6 · −2} = −0.6 x 4 = max{−0.5,−0.5 · 1.2,−0.5 · −0.6} = 0.3 y 4 = min{−0.5,−0.5 · 1.2,−0.5 · −0.6} = −0.6 x 5 = max{−2,−2 · 0.3,−2 · −0.6} = 1.2 y 5 = min{−2,−2 · 0.3,−2 · −0.6} = −2 x 6 = max{5,5 · 1.2,5 · −2} = 6 y 6 = min{5,5 · 1.2,5 · −2} = −10 x 7 = max{0.1,0.1 · 6,0.1 · −10} = 0.6 y 7 = min{0.1,0.1 · 6,0.1 · −10} = −1 x 8 = max{3,3 · 0.6,3 · −1} = 3 y 8 = min{3,3 · 0.6,3 · −1} = −3 x 9 = max{0.5,0.5 · 3,0.5 · −3} = 1.5 y 9 = min{0.5,0.5 · 3,0.5 · −3} = −1.5 x 10 = max{−3,−3 · 1.5,−3 · −1.5} = 4.5 y 10 = min{−3,−3 · 1.5,−3 · −1.5} = −4.5 Q Največji produkt strnjenega zaporedja je torej x∗ = 6 = 6 a i =2 i . 74 Naloga 4.4. (a) Za izračun pričakovanega dobička bomo definirali funkcije vi ( z) ( i = 1,2,3). Zapišimo njihove definicije. v 1( z) = n 1 + k 1 z © ¯ ª v 2( z) = max v 1( z − y) + n 2 + k 2 y ¯ a 2 ≤ y ≤ z − a 1 © ¯ ª v 3( z) = max v 2( z − y) · ( n 3 + k 3 y) ¯ a 3 ≤ y ≤ z − a 1 − a 2 Pričakovani dobiček dobimo tako, da izračunamo v 3( m). (b) Vstavimo podatke v zgornje formule. v 1( z) = 3 + 1.5 z © ¯ ª v 2( z) = max 3 + 1.5( z − y) + 4 + 2 y ¯ 3 ≤ y ≤ z − 4 © ¯ ª = max 7 + 1.5 z + 0.5 y ¯ 3 ≤ y ≤ z − 4 = 5 + 2 z ( z ≥ 7) © ¯ ª v 3(15) = max (5 + 2(15 − y)) · (0.4 + 0.3 y) ¯ 2 ≤ y ≤ 8 © ¯ ª = max −0.6 y 2 + 9.7 y + 14 ¯ 2 ≤ y ≤ 8 Naj bo f ( y) = −0.6 y 2 + 9.7 y + 14 – gre za kvadraten polinom z negativnim vodilnim členom, tako da ima maksimum tam, kjer je odvod ničeln. 0 = f 0( y) = −1.2 y + 9.7 y = 9.7/1.2 > 8 Opazimo torej, da maksimum leži desno od intervala [2,8], kar pomeni, da velja v 3(15) = f (8) = 53.6. Podjetje bo torej maksimiziralo pričakovani dobiček na 53.8 milijonov evrov, če dodeli 8 milijonov evrov marketingu, 3 milijone evrov oblikovalcem in 4 milijone evrov razvijalcem. Naloga 4.5. (a) Naj bo qi j največja verjetnost, ki jo lahko dosežejo, da pridobijo podporo prvih j strank, če k njim pošljejo i lobistov. Določimo začetne pogoje in rekurzivne enačbe. qi 1 = pi 1 (1 ≤ i ≤ m) © ¯ ª qi j = max q ¯ h, j −1 pi− h, j 0 ≤ h ≤ i (2 ≤ j ≤ n,0 ≤ i ≤ m) Vrednosti qi j računamo v leksikografskem vrstnem redu glede na ( j, i). Največjo verjetnost, da pridobijo podporo vseh n strank, dobimo kot q∗ = qmn. 75 (b) Ker velja p 0 j = 0 za vsak j , bo veljalo qi j = 0 za vse i < j . Tako lahko v zgornji rekurzivni enačbi upoštevamo le primere z j − 1 ≤ h ≤ i − 1. Izračunajmo torej vrednosti qi 2 (2 ≤ i ≤ 5) in q∗ = q 63. q 22 = 0.2 · 0.4 = 0.08 q 32 = max{0.2 · 0.5,0.5 · 0.4} = 0.2 q 42 = max{0.2 · 0.5,0.5 · 0.5,0.7 · 0.4} = 0.28 q 52 = max{0.2 · 0.6,0.5 · 0.5,0.7 · 0.5,0.8 · 0.4} = 0.35 q 63 = max{0.08 · 0.9,0.2 · 0.8,0.28 · 0.4,0.35 · 0.3} = 0.16 Največja verjetnost je torej q∗ = q 63 = 0.16. Poiščimo še optimalno razporeditev lobistov. q 63 = q 32 p 33 3 lobisti k tretji stranki q 32 = q 21 p 12 1 lobist k drugi stranki q 21 = p 21 2 lobista k prvi stranki Naloga 4.6. (a) Naj bosta pi in qi največji vsoti za ustrezne postavitve domin do i-tega polja, pri čemer na i -tem polju dovolimo le del domine z znakom + oziroma − (tj., prepovemo − oziroma +, dovolimo pa, da i-to polje ni pokrito). Določimo začetne pogoje in rekurzivne enačbe. p 0 = p 1 = 0, pi = max{ pi−1, qi−1, pi−2 − ai−1 + ai } (2 ≤ i ≤ n) q 0 = q 1 = 0, qi = max{ pi−1, qi−1, qi−2 + ai−1 − ai } (2 ≤ i ≤ n) Vrednosti pi in qi (0 ≤ i ≤ n) računamo naraščajoče po indeksu i. Največjo vsoto dobimo kot p∗ = max{ pn, qn}. (b) Za izračun vrednosti pi in qi pri vsakem i potrebujemo konstantno časa. Ker naredimo n takih korakov, je časovna zahtevnost algoritma O( n). (c) Izračunajmo vrednosti pi in qi (2 ≤ i ≤ 9). p 2 = max{0,0,0 − 6 + 3} = 0 q 2 = max{0,0,0 + 6 − 3} = 3 p 3 = max{0,3,0 − 3 + (−4)} = 3 q 3 = max{0,3,0 + 3 + (−4)} = 7 p 4 = max{3,7,0 − (−4) + 2} = 7 q 4 = max{3,7,3 + (−4) − 2} = 7 p 5 = max{7,7,3 − 2 + (−3)} = 7 q 5 = max{7,7,7 + 2 − (−3)} = 12 p 6 = max{7,12,7 − (−3) + 5} = 15 q 6 = max{7,12,7 + (−3) − 5} = 12 p 7 = max{15,12,7 − 5 + 9} = 15 q 7 = max{15,12,7 + 5 − 9} = 15 p 8 = max{15,15,15 − 9 + 1} = 15 q 8 = max{15,15,15 + 9 − 1} = 23 76 + − + − + − 6 3 −4 2 −3 5 9 1 2 Slika 34: Optimalno pokritje za nalogo 4.6(c). p 9 = max{15,23,15 − 1 + 2} = 23 q 9 = max{15,23,15 + 1 − 2} = 23 Optimalno pokritje ima torej vsoto p∗ = max{ p 9, q 9} = 23. Poglejmo, kam moramo postaviti domine. p∗ = p 9 = q 8 = q 6 + a 7 − a 8 [+ −] na (7,8) q 6 = q 5 = q 3 + a 4 − a 5 [+ −] na (4,5) q 3 = q 1 + a 2 − a 3 [+ −] na (2,3) Postavitev je prikazana na sliki 34. Naloga 4.7. (a) Zapišimo definicijo funkcije q( x) za 0 ≤ x ≤ 4. q( x) = max({0.15 x} ∪ {0.1 | x = 1} ∪ {0.35 | x = 2} ∪ {0.5 | x = 3})    0.35 x = 2 (Diskretna d.d.z.) = 0.5 x  = 3 (Diskretna d.d.z.)  0.15 x sicer (Zvezna d.z.z.) (b) Naj bosta v 1( x) in v 2( x) največji pričakovani vrednosti naložbenih strategij, pri katerih imamo na voljo x milijonov evrov oziroma to količino v celoti vložimo v naložbo in zavarovanje. Zapišimo rekurzivni enačbi. © ¯ ª v 2( x) = max ( x − y)(3 + 0.4 q( y)) ¯ 0 ≤ y ≤ min{4, x} © ¯ ª v 1( x) = max x − y + v 2( y) ¯ 0 ≤ y ≤ x (c) Najprej izrazimo v 2( x) glede na vrednost x (0 ≤ x ≤ 50). ¡ v 2( x) = max {3.14( x − 2) | x ≥ 2} ∪ {3.2( x − 3) | x ≥ 3}∪ © ¯ ª¢ ( x − y)(3 + 0.06 y) ¯ 0 ≤ y ≤ min{4, x}, y 6∈ {2,3} Naj bo f ( y) izraz v zadnjem oklepaju. Opazimo, da gre za kvadraten polinom v y z negativnim vodilnim členom, tako da lahko s pomočjo odvajanja poiščemo njegov maksimum. f ( y) = −0.06 y 2 + (0.06 x − 3) y + 3 x 77 f 0( y) = −0.12 y + 0.06 x − 3 = 0 y = x/2 − 25 ≤ 0 Opazimo, da je maksimum vedno dosežen za vrednost y, ki ni večja od spod-nje meje ustreznega intervala, tako da je znotraj njega maksimum dosežen pri y = 0 in znaša f (0) = 3 x – tj., premije ne plačamo. S primerjavo vseh treh izrazov tako dobimo (3 x 0 ≤ x ≤ 314/7 (brez zavarovanja) v 2( x) = 3.14( x −2) 314/7< x ≤50 (Diskretna d.d.z. s premijo 2 mio evrov) Optimalno strategijo vlaganja sedaj dobimo tako, da izračunamo v 1(50). ¡© ¯ ª v 1(50) = max 50 + 2 y ¯ 0 ≤ y ≤ 314/7 ∪ © ¯ ª¢ 43.72 + 2.14 y ¯ 314/7 < x ≤ 50 Ker oba izraza naraščata z y, zadostuje preveriti njuni vrednosti pri zgornji meji ustreznega intervala. Tako opazimo, da največjo vrednost dobimo pri y = 50. Optimalna strategija vlaganja je torej taka, pri kateri vlagatelj 48 milijonov evrov vloži v naložbo, 2 milijona evrov porabi za premijo pri zavarovalnici Diskretna d.d.z., zase pa ne obdrži ničesar. Pričakovana vrednost naložbene strategije je tako v∗ = v 1(50) = 150.72 milijonov evrov. Naloga 4.8. (a) Naj bo vi najnižja cena izgradnje počivališč na odseku od začetka avtoceste do lokacije xi , če zadnje počivališče zgradimo na tej lokaciji. Zapišimo začetne pogoje in rekurzivne enačbe. v 0 = x 0 = 0 ¡© ¯ ª ¢ vi = ci + min v j ¯ 0 ≤ j ≤ i − 1, xi − xj ≤ K ∪ {∞} (1 ≤ i ≤ n) Vrednosti vi računamo naraščajoče po indeksu i. Najnižjo ceno izgradnje počivališč na celotnem odseku dobimo kot ¡© ¯ ª ¢ v∗ = min v j ¯ 0 ≤ j ≤ n, M − xj ≤ K ∪ {∞} . Če velja v∗ = ∞, potem izgradnja počivališč pod danimi pogoji ni mogoča. (b) V algoritmu izračunamo n vrednosti vi , pri čemer pri vsaki obravnavamo največ n možnosti; prav tako obravnavamo največ n možnosti pri računanju v∗. Časovna zahtevnost algoritma je torej O( n 2). (c) Izračunajmo vrednosti vi (1 ≤ i ≤ 8). Ker se lokacije zaporednih počivališč razlikujejo za manj kot K , prav tako pa sta prva in zadnja možna lokacija 78 oddaljeni manj kot K od začetka oziroma konca odseka, bodo vse vrednosti vi končne, enako pa velja tudi za v∗. x 1 = 5 v 1 = 18 + min{0} = 18 x 2 = 12 v 2 = 11 + min{0,18} = 11 x 3 = 22 v 3 = 21 + min{0,18,11} = 21 x 4 = 34 v 4 = 16 + min{18,11,21} = 27 x 5 = 49 v 5 = 23 + min{21,27} = 44 x 6 = 65 v 6 = 15 + min{44} = 59 x 7 = 83 v 7 = 19 + min{59} = 78 x 8 = 91 v 8 = 13 + min{59,78} = 72 Ker sta samo zadnji dve lokaciji oddaljeni manj kot K od konca odseka, je najmanjša cena izgradnje počivališč enaka v∗ = min{78,72} = 72. Rekonstru-irajmo še optimalno postavitev. v∗ = v 8 = c 8 + v 6 počivališče na x 8 = 91 v 6 = c 6 + v 5 počivališče na x 6 = 65 v 5 = c 5 + v 3 počivališče na x 5 = 49 v 3 = c 3 + v 0 počivališče na x 3 = 22 Naloga 4.9. (a) Naj bo pi najmanjša cena postavitve baznih postaj do i-te milje tako, da se v celoti pokrije interval [0, i ]. Določimo začetne pogoje in rekurzivne enačbe. p−1 = p 0 = 0 pi = min{ ai−1 + pi−2, ai + pi−1} (1 ≤ i ≤ n) Vrednosti pi računamo naraščajoče po indeksu i (0 ≤ i ≤ n). Najmanjšo ceno postavitve baznih postaj dobimo s p∗ = pn. (b) Za izračun vrednosti pi za posamezen i potrebujemo konstantno mnogo časa. Ker ta izračun opravimo ( n − 1)-krat, je torej časovna zahtevnost ustreznega algoritma O( n). (c) Izračunajmo vrednosti pi (1 ≤ i ≤ 10). p 1 = min{4 + 0,6 + 0} = 4 p 2 = min{6 + 0,1 + 4} = 5 p 3 = min{1 + 4,10 + 5} = 5 79 p 4 = min{10 + 5,14 + 5} = 15 p 5 = min{14 + 5,21 + 15} = 19 p 6 = min{21 + 15,15 + 19} = 34 p 7 = min{15 + 19,6 + 34} = 34 p 8 = min{6 + 34,10 + 34} = 40 p 9 = min{10 + 34,3 + 40} = 43 p 10 = min{3 + 40,2 + 43} = 43 Cena postavitve baznih postaj je torej p∗ = p 10 = 43. Poglejmo, kam moramo postaviti bazne postaje. p 10 = a 9 + p 8 postaja na 9 p 8 = a 7 + p 6 postaja na 7 p 6 = a 6 + p 5 postaja na 6 p 5 = a 4 + p 3 postaja na 4 p 3 = a 2 + p 1 postaja na 2 p 1 = a 0 postaja na 0 (d) Naj bo qi najmanjša cena postavitve baznih postaj (pri čemer dovolimo tudi večje postaje) do i -te milje tako, da se v celoti pokrije interval [0, i ]. Določimo začetne pogoje in rekurzivne enačbe. b−1 = ∞ q−3 = q−2 = q−1 = q 0 = 0 qi =min{ bi−2 +min{ qi−4, qi−3}, bi−1 +min{ qi−3, qi−2}, bi + min{ qi−2, qi−1}, ai−1 + qi−2, ai + qi−1} (1 ≤ i ≤ n) Vrednosti qi računamo naraščajoče po indeksu i (0 ≤ i ≤ n). Najmanjšo ceno postavitve baznih postaj dobimo s q∗ = qn. (e) Izračunajmo vrednosti qi (1 ≤ i ≤ 10). q 1 = min{∞ + 0,10 + 0,12 + 0,4 + 0,6 + 0} = 4 q 2 = min{10 + 0,12 + 0,3 + 0,6 + 0,1 + 4} = 3 q 3 = min{12 + 0,3 + 0,18 + 3,1 + 4,10 + 3} = 3 q 4 = min{3 + 0,18 + 3,24 + 3,10 + 3,14 + 3} = 3 q 5 = min{18 + 3,24 + 3,25 + 3,14 + 3,21 + 3} = 17 q 6 = min{24 + 3,25 + 3,20 + 3,21 + 3,15 + 17} = 23 80 q 7 = min{25 + 3,20 + 3,11 + 17,15 + 17,6 + 23} = 23 q 8 = min{20 + 3,11 + 17,16 + 23,6 + 23,10 + 23} = 23 q 9 = min{11 + 17,16 + 23,7 + 23,10 + 23,3 + 23} = 26 q 10 = min{16 + 23,7 + 23,4 + 23,3 + 23,2 + 26} = 26 Cena postavitve baznih postaj je torej q∗ = q 10 = 26. Poglejmo, kam moramo postaviti bazne postaje. q 10 = a 9 + q 8 manjša postaja na 9 q 8 = b 6 + q 4 večja postaja na 6 q 4 = b 2 + q 0 večja postaja na 2 Naloga 4.10. (a) Zapišimo začetni pogoj in rekurzivne enačbe. c 0 = 0 ci = ci−1 + pi (1 ≤ i ≤ n) Vrednosti ci (0 ≤ i ≤ n) računamo naraščajoče po indeksu i, za izračun pa porabimo O( n) časa. (b) Naj bo xi j (1 ≤ i ≤ j ≤ n) cena postavitve razdelilnikov, ki razdelijo vodo za delavnice od i do j . Zapišimo začetne pogoje in rekurzivne enačbe. xii = 0 (1 ≤ i ≤ n) © ¯ ª xi j = cj − ci ¯ −1 + min xik + xk+1, j i ≤ k < j (1 ≤ i < j ≤ n) Vrednosti xi j (1 ≤ i ≤ j ≤ n) računamo naraščajoče po razliki j − i, nato pa še naraščajoče po indeksu i . Optimalno rešitev dobimo kot x∗ = x 1 n. Časovna zahtevnost izračuna je O( n 3). (c) Najprej izračunajmo vrednosti ci (1 ≤ i ≤ 6). c 1 = 0 + 4 = 4 c 2 = 4 + 19 = 23 c 3 = 23 + 17 = 40 c 4 = 40 + 7 = 47 c 5 = 47 + 5 = 52 c 6 = 52 + 9 = 61 Sedaj izračunajmo še vrednosti xi j (1 ≤ i < j ≤ 6). x 12 = 23 − 0 + 0 + 0 = 23 81 x 23 = 40 − 4 + 0 + 0 = 36 x 34 = 47 − 23 + 0 + 0 = 24 x 45 = 52 − 40 + 0 + 0 = 12 x 56 = 61 − 47 + 0 + 0 = 14 x 13 = 40 − 0 + min{0 + 36,23 + 0} = 63 x 24 = 47 − 4 + min{0 + 24,36 + 0} = 67 x 35 = 52 − 23 + min{0 + 12,24 + 0} = 41 x 46 = 61 − 40 + min{0 + 14,12 + 0} = 33 x 14 = 47 − 0 + min{0 + 67,23 + 24,63 + 0} = 94 x 25 = 52 − 4 + min{0 + 41,36 + 12,67 + 0} = 89 x 36 = 61 − 23 + min{0 + 33,24 + 14,41 + 0} = 71 x 15 = 52 − 0 + min{0 + 89,23 + 41,63 + 12,94 + 0} = 116 x 26 = 61 − 4 + min{0 + 71,36 + 33,67 + 14,89 + 0} = 126 x 16 = 61 − 0 + min{0 + 126,23 + 71,63 + 33,94 + 14,116 + 0} = 155 Cena postavitve razdelilnikov je torej x∗ = x 16 = 155. Poglejmo, kako naj jih postavimo. x 16 = c 6 − c 0 + x 12 + x 36 delimo na 1,2 in 3 do 6 x 12 = c 2 − c 0 + x 11 + x 22 delimo na 1 in 2 x 36 = c 6 − c 2 + x 33 + x 46 delimo na 3 in 4 do 6 x 46 = c 6 − c 3 + x 45 + x 66 delimo na 4,5 in 6 x 45 = c 5 − c 3 + x 44 + x 55 delimo na 4 in 5 Postavitev je prikazana na sliki 35. Naloga 4.11. (a) Naj bo pi j največja vsota, ki jo lahko dosežemo z zaporedjem skokov od A 11 do Ai j . Določimo začetni pogoj in rekurzivne enačbe. p 11 = A 11 © ¯ ª p 1 j = A 1 j + max p ¯ 1 ` 1 ≤ ` ≤ j − 1 (2 ≤ j ≤ n) © ¯ ª pi 1 = Ai 1 + max p ¯ ` 1 1 ≤ ` ≤ i − 1 (2 ≤ i ≤ m) © ¯ ª © ¯ ª pi j = Ai j + max( p ¯ ¯ ì 1 ≤ ` ≤ j − 1 ∪ p`j 1 ≤ ` ≤ i − 1 ) (2 ≤ i ≤ m, 2 ≤ j ≤ n) Vrednosti pi j računamo v leksikografskem vrstnem redu indeksov (npr. najprej naraščajoče po i , nato pa naraščajoče po j ). Maksimalno vsoto obiskanih mest dobimo kot p∗ = pmn. Rekurzivne enačbe lahko rešimo v času O( mn( m + n)). 82 1 − 6 1 − 2 3 − 6 1 2 3 4 − 6 4 − 5 6 4 5 Slika 35: Postavitev razdelilnikov za nalogo 4.10(c).   0 2 −5 1       −6 −7 −8 9        7 9 1 7      0 2 8 9 Slika 36: Reševanje in optimalna rešitev za nalogo 4.11(b). (b) Matrika vrednosti ( pi j )4 je prikazana na sliki 36, pri čemer je pri vsaki vred-i , j =1 nosti puščica od tiste vrednosti, ki je bila uporabljena pri njenem izračunu. Z rdečo barvo je prikazano zaporedje (1,1),(1,2),(1,4),(2,4),(4,4) z največjo vsoto p∗ = 9. Naloga 4.12. (a) Naj bo di ( i = 1,2) optimalni dobiček pri vlaganju v i-to podjetje. Potem velja (max{( n d i + ki x)( n 3 + k 3( m − x)) | ai ≤ x ≤ m − a 3} , če ai ≤ m − a 3, in i = 0 sicer. Optimalni dobiček potem dobimo kot d∗ = max{ d 1, d 2}. (b) Naj bo qi ( x) ( i = 1,2) kvadratni polinom, ki nastopa v zgornjem izrazu. Da iz-računamo d 1 in d 2, bomo poiskali maksimum polinomov q 1 in q 2 v ustreznih mejah. 83 Vrednost d 1 je maksimalna vrednost izraza q 1( x) = (8 + 4 x)(4 + 10 − x) = −4 x 2 + 48 x + 112 za x ∈ [4,7]. Ker ima polinom negativen vodilni člen, je njegov globalni maksimum tam, kjer ima njegov odvod ničlo. q 01( x) = −8 x +48 = 0 x = 6 Ker maksimum leži na iskanem intervalu, velja d 1 = q 1(6) = 256. Vrednost d 2 je maksimalna vrednost izraza q 2( x) = (12 + 2 x)(4 + 10 − x) = −2 x 2 + 16 x + 168 za x ∈ [5,7]. Ker ima polinom negativen vodilni člen, je njegov globalni maksimum tam, kjer ima njegov odvod ničlo. q 02( x) = −4 x +16 = 0 x = 4 Ker maksimum leži levo od iskanega intervala, leži maksimum na njegovem levem robu, torej velja d 2 = q 2(5) = 198. Optimalni dobiček je tako d∗ = max{256,198} = 256 in ga dosežemo tako, da vložimo 6 v prvo podjetje in 4 v marketing. 84 2.5 Algoritmi na grafih Naloga 5.1. Sledili bomo naslednjemu algoritmu. function BFS( G = ( V, E), S, VISIT) visited ← slovar z vrednostjo FALSE za vsak v ∈ V pred ← slovar z vrednostjo NULL za vsak v ∈ V for s ∈ S do if ¬visited[ s] then visited[ s] ← TRUE Q ← [ s] while ¬ Q.isEmpty() do u ← Q.pop() VISIT( u,pred[ u]) for v ∈ ADJ( G, u) do if ¬visited[ v] then visited[ v] ← TRUE pred[ v] ← u Q.append( v) end if end for end while end if end for return pred end function Časovna zahtevnost preiskovanja je O( m + n) (kjer je n število vozlišč in m število povezav grafa), poleg tega pa algoritem opravi še O( n) klicev funkcije VISIT. Potek zgornjega algoritma na grafu s slike 9 (pri čemer za množico začetnih vozlišč S vzamemo množico vseh vozlišč V , za VISIT pa vzamemo NOOP, torej ne naredimo ničesar), pri čemer sledimo abecednemu vrstnemu redu vozlišč, je prikazan v tabeli 9. Gozd iskanja v širino je prikazan na sliki 37, iz katere je razvidno, da so drevesne povezave ( a, b),( b, c),( a, e),( e, f ),( f , i ),( d, g ),( d, h). Naloga 5.2. Sledili bomo naslednjemu algoritmu. Predpostavili bomo, da imamo na voljo podatkovno strukturo za prednostno vrsto, ki za vsak element hrani njegovo prioriteto (to lahko tudi spreminjamo). Podatkovna struktura ima metodo pop(), ki vrne in odstrani element z najmanjšo prioriteto skupaj z njegovo prioriteto. Tukaj bodo elementi vozlišča grafa, prioritete pa dolžine najkrajših najdenih poti od začetnega vozlišča. function DIJKSTRA( G = ( V, E), s ∈ V, L : E → R+) d ← slovar z vrednostjo ∞ za vsako vozlišče v ∈ V pred ← slovar z vrednostjo NULL za vsako vozlišče v ∈ V Q ← prednostna vrsta s prioriteto ∞ za vsako vozlišče v ∈ V (na vrhu je vozlišče z najmanjšo prioriteto) 85 s u v Q množica označenih vozlišč a [ a] { a} a a b [ b] { a, b} a a e [ b, e] { a, b, e} a b c [ e, c] { a, b, c, e} a b e { a, b, c, e} a e a [ c] { a, b, c, e} a e b { a, b, c, e} a e f [ c, f ] { a, b, c, e, f } a c b [ f ] { a, b, c, e, f } a c f { a, b, c, e, f } a f c { a, b, c, e, f } a f e { a, b, c, e, f } a f i [ i ] { a, b, c, e, f , i } a i f [ ] { a, b, c, e, f , i } b { a, b, c, e, f , i } c { a, b, c, e, f , i } d [ d] { a, b, c, d, e, f , i } d d g [ g ] { a, b, c, d, e, f , g , i } d d h [ g , h] { a, b, c, d, e, f , g , h, i } d g d [ h] { a, b, c, d, e, f , g , h, i } d g h { a, b, c, d, e, f , g , h, i } d h d { a, b, c, d, e, f , g , h, i } d h g [ ] { a, b, c, d, e, f , g , h, i } e { a, b, c, d, e, f , g , h, i } f { a, b, c, d, e, f , g , h, i } g { a, b, c, d, e, f , g , h, i } h { a, b, c, d, e, f , g , h, i } i { a, b, c, d, e, f , g , h, i } Tabela 9: Potek izvajanja algoritma za nalogo 5.1. 86 a d b e g h c f i Slika 37: Gozd iskanja v širino za nalogo 5.1. Q[ s] ← 0 while ¬ Q.isEmpty() do u, d[ u] ← Q.pop() for v ∈ ADJ( G, u) do if v ∈ Q ∧ Q[ v] > d[ u] + Luv then Q[ v] ← d[ u] + Luv pred[ v] ← u end if end for end while return ( d , pred) end function Če za prednostno vrsto uporabimo običajen slovar, je časovna zahtevnost metode pop() linearna v številu elementov slovarja, spreminjanje vrednosti v slovarje pa se opravi v konstantnem času. Časovna zahtevnost zgornjega algoritma je tako O( n 2), kjer je n število vozlišč v grafu. Če pa za prednostno vrsto vzamemo kopico, sta časovni zahtevnosti metode pop() in spreminjanja vrednosti v kopici logaritemski v velikosti kopice. Časovna zahtevnost zgornjega algoritma je v tem primeru O(( m+ n)log n), kjer je m število povezav v grafu. Potek zgornjega algoritma na grafu s slike 10, pri čemer sledimo abecednemu vrstnemu redu vozlišč, je prikazan v tabeli 10. Drevo najkrajših poti je prikazano na sliki 38. Naloga 5.3. Sledili bomo naslednjemu algoritmu. function DFS( G = ( V, E), S, PREVISIT, POSTVISIT) for v ∈ V do visited[ v] ← FALSE end for function RAZIŠ ČI( v, w ) if visited[ v] then 87 u v Q razdalje in predhodniki [( a,0)] [0,∞,∞,∞,∞,∞,∞,∞] a b [( b,3)] [0,3 a,∞,∞,∞,∞,∞,∞] a f [( b,3),( f ,6)] [0,3 a,∞,∞,∞,6 a,∞,∞] b c [( f ,6),( c,10)] [0,3 a,10 b,∞,∞,6 a,∞,∞] b e [( f ,6),( c,10),( e,12)] [0,3 a,10 b,∞,12 b,6 a,∞,∞] f g [( c,10),( e,12),( g ,14)] [0,3 a,10 b,∞,12 b,6 a,14 g ,∞] c d [( e,12),( g ,14),( d,17)] [0,3 a,10 b,17 c,12 b,6 a,14 g ,∞] e d [( d,13),( g ,14),( d,17)] [0,3 a,10 b,13 e,12 b,6 a,14 g ,∞] e g [( g ,13),( d,13),( g ,14),( d,17)] [0,3 a,10 b,13 e,12 b,6 a,13 e,∞] g f [( d,13),( g ,14),( d,17)] [0,3 a,10 b,13 e,12 b,6 a,13 e,∞] d b [( g ,14),( d,17)] [0,3 a,10 b,13 e,12 b,6 a,13 e,∞] d h [( g ,14),( d,17),( h,17)] [0,3 a,10 b,13 e,12 b,6 a,13 e,17 d] g f [( d,17),( h,17)] [0,3 a,10 b,13 e,12 b,6 a,13 e,17 d] d b [( h,17)] [0,3 a,10 b,13 e,12 b,6 a,13 e,17 d] d h [( h,17)] [0,3 a,10 b,13 e,12 b,6 a,13 e,17 d] h g [ ] [0,3 a,10 b,13 e,12 b,6 a,13 e,17 d] Tabela 10: Potek izvajanja algoritma za nalogo 5.2. a 0 3 6 3 b f 6 7 9 10 c e 12 1 1 13 d g 13 4 17 h Slika 38: Drevo najkrajših poti za nalogo 5.2. 88 a d b g c h f e i Slika 39: Gozd iskanja v globino za nalogo 5.3. return end if visited[ v] ← TRUE PREVISIT( v, w) for u ∈ ADJ( G, v) do: RAZIŠ ČI( u, v) end for POSTVISIT( v, w) end function for v ∈ S do RAZIŠ ČI( v, NULL) end for end function Časovna zahtevnost preiskovanja je O( m + n) (kjer je n število vozlišč in m število povezav grafa), poleg tega pa algoritem opravi še O( n) klicev funkcij PREVISIT in POSTVISIT. Potek zgornjega algoritma na grafu s slike 9 (pri čemer za množico začetnih vozlišč S vzamemo množico vseh vozlišč V , za PREVISIT in POSTVISIT pa vzamemo NOOP, torej ne naredimo ničesar), pri čemer sledimo abecednemu vrstnemu redu vozlišč, je prikazan v tabeli 11. Gozd iskanja v globino je prikazan na sliki 39, iz katere je razvidno, da so drevesne povezave ( a, b),( b, c),( c, f ),( f , e),( f , i ),( d, g ),( g , h). Naloga 5.4. Sledili bomo naslednjemu algoritmu. function BELLMANFORD( G = ( V, E), s ∈ V, L : E → R) d ← slovar z vrednostjo ∞ za vsako vozlišče v ∈ V pred ← slovar z vrednostjo NULL za vsako vozlišče v ∈ V 89 v u množica označenih vozlišč a { a} a b { a, b} b a { a, b} b c { a, b, c} c b { a, b, c} c f { a, b, c, f } f c { a, b, c, f } f e { a, b, c, e, f } e a { a, b, c, e, f } e b { a, b, c, e, f } e f { a, b, c, e, f } f i { a, b, c, e, f , i } i f { a, b, c, e, f , i } b e { a, b, c, e, f , i } a e { a, b, c, e, f , i } b { a, b, c, e, f , i } c { a, b, c, e, f , i } d { a, b, c, d, e, f , i } d g { a, b, c, d, e, f , g , i } g d { a, b, c, d, e, f , g , i } g h { a, b, c, d, e, f , g , h, i } h d { a, b, c, d, e, f , g , h, i } h g { a, b, c, d, e, f , g , h, i } d h { a, b, c, d, e, f , g , h, i } Tabela 11: Potek izvajanja algoritma za nalogo 5.3. 90 d[ s] ← 0 i ← 0 B ← TRUE while B do i ← i + 1 if i > | V | then return graf ima negativen cikel end if B ← FALSE for uv ∈ E do if d [ v] > d[ u] + Luv then d[ v] ← d[ u] + Luv pred[ v] ← u B ← TRUE end if end for end while return ( d , pred) end function V i -tem obhodu zanke while slovar d vsebuje dolžine tistih najkrajših poti od s do vsakega drugega vozlišča, ki vsebujejo največ i povezav. Če graf nima negativnih ciklov, je v vsaki najkrajši poti največ n − 1 povezav (kjer je n število vozlišč) in zato algoritem konča najkasneje po n-tem obhodu zanke while. V nasprotnem primeru obstaja najkrajša pot z neskončno povezavami, kar algoritem zazna ob vstopu v ( n + 1)-vi obhod zanke. Časovna zahtevnost algoritma je tako O( mn), kjer je m število povezav grafa. Potek zgornjega algoritma na grafu s slike 11 je prikazan v tabeli 12. Drevo najkrajših poti je prikazano na sliki 40. Naloga 5.5. (a) Upoštevamo, da je graf G = ( V, E) acikličen, torej za vsaki vozlišči u, v ∈ V velja u → v =⇒ postlabel( u) > postlabel( v), kjer je postlabel števec, s katerim označimo vozlišče, ko ga v algoritmu DFS docela preiščemo. Trditev lahko dokažemo z obravnavanjem dveh primerov, in sicer, ko z DFS pridemo v vozlišče u pred v, in ko pridemo v vozlišče v pred u. V prvem primeru bomo pred določitvijo pooznake vozlišču u morali obiskati vse njegove sosede, torej tudi v, ki mu bomo določili pooznako pred u. V drugem primeru pridemo prej do v, a ker je graf acikličen, od v ne bomo prišli do u, torej bomo spet v obdelali prej. Trditev nam omogoča zapis krajšega algoritma, ki bo uporabil algoritem DFS iz naloge 5.3. Njegova ideja je, da padajoče uredimo vozlišča po njihovih pooznakah in tako dobimo inverzno topološko ureditev. To dosežemo tako, da po popolni obdelavi vozlišča tega postavimo na sklad. 91 i B u v Luv razdalje in predhodniki TRUE [0,∞,∞,∞,∞,∞,∞,∞] 1 TRUE a b 3 [0,3 a,∞,∞,∞,∞,∞,∞] 1 TRUE a f 6 [0,3 a,∞,∞,∞,6 a,∞,∞] 1 TRUE b c 7 [0,3 a,10 b,∞,∞,6 a,∞,∞] 1 TRUE b e 9 [0,3 a,10 b,∞,12 b,6 a,∞,∞] 1 TRUE c d −7 [0,3 a,10 b,3 c,12 b,6 a,∞,∞] 1 TRUE d b 9 [0,3 a,10 b,3 c,12 b,6 a,∞,∞] 1 TRUE d h 4 [0,3 a,10 b,3 c,12 b,6 a,∞,7 d] 1 TRUE e d 1 [0,3 a,10 b,3 c,12 b,6 a,∞,7 d] 1 TRUE e g 1 [0,3 a,10 b,3 c,12 b,6 a,13 e,7 d] 1 TRUE f g 8 [0,3 a,10 b,3 c,12 b,6 a,13 e,7 d] 1 TRUE g f −1 [0,3 a,10 b,3 c,12 b,6 a,13 e,7 d ] 1 TRUE h g −5 [0,3 a,10 b,3 c,12 b,6 a,2 h,7 d] 2 FALSE a b 3 [0,3 a,10 b,3 c,12 b,6 a,2 h,7 d] 2 FALSE a f 6 [0,3 a,10 b,3 c,12 b,6 a,2 h,7 d] 2 FALSE b c 7 [0,3 a,10 b,3 c,12 b,6 a,2 h,7 d] 2 FALSE b e 9 [0,3 a,10 b,3 c,12 b,6 a,2 h,7 d] 2 FALSE c d −7 [0,3 a,10 b,3 c,12 b,6 a,2 h,7 d] 2 FALSE d b 9 [0,3 a,10 b,3 c,12 b,6 a,2 h,7 d] 2 FALSE d h 4 [0,3 a,10 b,3 c,12 b,6 a,2 h,7 d] 2 FALSE e d 1 [0,3 a,10 b,3 c,12 b,6 a,2 h,7 d] 2 FALSE e g 1 [0,3 a,10 b,3 c,12 b,6 a,2 h,7 d] 2 FALSE f g 8 [0,3 a,10 b,3 c,12 b,6 a,2 h,7 d] 2 TRUE g f −1 [0,3 a,10 b,3 c,12 b,1 g ,2 h,7 d] 2 TRUE h g −5 [0,3 a,10 b,3 c,12 b,1 g ,2 h,7 d] 3 FALSE a b 3 [0,3 a,10 b,3 c,12 b,1 g ,2 h,7 d] 3 FALSE a f 6 [0,3 a,10 b,3 c,12 b,1 g ,2 h,7 d] 3 FALSE b c 7 [0,3 a,10 b,3 c,12 b,1 g ,2 h,7 d] 3 FALSE b e 9 [0,3 a,10 b,3 c,12 b,1 g ,2 h,7 d] 3 FALSE c d −7 [0,3 a,10 b,3 c,12 b,1 g ,2 h,7 d] 3 FALSE d b 9 [0,3 a,10 b,3 c,12 b,1 g ,2 h,7 d] 3 FALSE d h 4 [0,3 a,10 b,3 c,12 b,1 g ,2 h,7 d] 3 FALSE e d 1 [0,3 a,10 b,3 c,12 b,1 g ,2 h,7 d] 3 FALSE e g 1 [0,3 a,10 b,3 c,12 b,1 g ,2 h,7 d] 3 FALSE f g 8 [0,3 a,10 b,3 c,12 b,1 g ,2 h,7 d] 3 FALSE g f −1 [0,3 a,10 b,3 c,12 b,1 g ,2 h,7 d] 3 FALSE h g −5 [0,3 a,10 b,3 c,12 b,1 g ,2 h,7 d] Tabela 12: Potek izvajanja algoritma za nalogo 5.4. 92 0 a 3 3 b 7 9 10 c e 12 −7 3 d 4 7 h −5 2 g −1 1 f Slika 40: Drevo najkrajših poti za nalogo 5.4. function TOPO( G = ( V, E)) toposklad ← [] function POSTVISIT( u, v) toposklad.append( u) end function DFS( G, V, NOOP, POSTVISIT) toposklad.reverse() return toposklad end function Časovna zahtevnost algoritma je O( m+ n), kjer je n število vozlišč in m število povezav grafa. Klic TOPO( G) nam vrne ureditev vozlišč [ g , a, h, b, c, f , d, e]. (b) Tukaj bomo uporabili rezultat iz prejšnje točke in osnoven koncept dinamič- nega programiranja. Označimo z Luv utež povezave u → v. Naj dG( u) predstavlja najkrajšo razda-ljo od izbranega vozlišča s do vozlišča u. dG( s) = 0 dG( u) = min( dG( v) + Lvu) ( u ∈ V \ { s}) v→ u Da bomo imeli vse potrebne dG( v) definirane pred izračunom dG( u), po-skrbimo z rezultatom iz prejšnje točke, saj pri topološki ureditvi vodijo vse 93 povezave le naprej, Po premiku na naslednje vozlišče tako ne potrebujemo kasnejših vozlišč, pač pa le prejšnja, za katera vrednost že poznamo. Imamo torej vse, kar potrebujemo za izračun najkrajše poti. Za beleženje vozlišč, skozi katera vodi ta pot, bomo uporabili seznam predhodnikov, ki bo nakazoval, katero vozlišče smo izbrali za predhodnika. pred( s) = NULL pred( u) = argmin( dG( v) + Lvu) ( u ∈ V \ { s}) v→ u Zapišimo algoritem, ki poišče razdalje od s do ostalih vozlišč. Poleg razdalj bo za vsako vozlišče povedal še, iz katerega vozlišča smo prišli do njega. function NAJKRAJŠAPOT( G = ( V, E), s, L : E → R) dG ← slovar z vrednostjo ∞ za vsako vozlišče v ∈ V dG[ s] ← 0 pred ← slovar z vrednostjo NULL za vsako vozlišče v ∈ V for u ∈ TOPO( G) do for v ∈ ADJ( G, u) do if dG [ v] > dG [ u] + Luv then dG[ v] ← dG[ u] + Luv pred[ v] ← u end if end for end for return ( dG ,pred) end function Časovna zahtevnost algoritma je O( m+ n), kjer je n število vozlišč in m število povezav grafa. Če želimo rekonstruirati pot, sledimo predhodnikom podanega končnega vozlišča t, dokler ne pridemo do s. function REKONSTRUIRAJPOT(pred, t ) u ← t pot ← [ t] while pred[ u] 6= NULL do u ← pred[ u] pot.append( u) end while pot.reverse() return pot end function Klic NAJKRAJŠAPOT( G, g , L) vrne seznam dG z razdaljami od vozlišča g do ostalih vozlišč grafa in seznam pred s prednikom vsakega vozlišča v najkrajši poti od g . Potek izvajanja algoritma je prikazan v tabeli 13. Seznam vozlišč, skozi katera je algoritem potoval, da je opravil pot od g do e, nato dobimo s klicem REKONSTRUIRAJPOT(pred, e) – to so [ g , a, b, e]. Dolžino te poti lahko preberemo kot dG[ e] = −1. 94 Pripomnimo, da algoritem deluje pravilno ne glede na položaj začetnega vozlišča s v topološki ureditvi. Za vsako vozlišče u, ki v topološki ureditvi nastopa pred s, namreč velja dG( u) = ∞, tako da se ne nastavi kot predhodnik nobenemu vozlišču. Tako se vozlišču s ne bo nastavil predhodnik. Algoritem lahko nekoliko pohitrimo tako, da gledamo vozlišča v topološki ureditvi le od s naprej, prejšnja pa ignoriramo, saj iz s ne moremo priti do njih. Prav tako bi se lahko ustavili, ko dosežemo vozlišče t. (c) Uporabimo algoritem NAJDALJŠAPOT, ki deluje na enak način kot NAJKRAJ- ŠAPOT, le da namesto ∞ vzame v dG za začetne vrednosti −∞, v zanki pa na vsakem koraku preverja pogoj dG[ v] < dG[ u] + Luv. Časovna zahtevnost algoritma tako ostane enaka. Klic REKONSTRUIRAJPOT(pred, e), kjer je dG,pred izhod klica NAJDALJŠAPOT( G, g , L), vrne pot [ g , h, b, c, f , e] dolžine 24. Potek izvajanja algoritma je prikazan v tabeli 14. Naloga 5.6. (a) Iz danega neusmerjenega grafa G = ( V, E) in funkcije uteži vozlišč c : V → [0,1] bomo konstruirali usmerjen graf G 0 = ( V, E 0), kjer je E 0 = { uv, vu | uv ∈ E} (tj., vsako neusmerjeno povezavo iz G nadomestimo z nasprotno usmerje-nima povezavama med krajiščema), in funkcijo uteži povezav L : E 0 → [0,1] s predpisom L( uv) = c( u) (tj., cena povezave je enaka ceni začetnega vozlišča v G). Na grafu G 0 s funkcijo uteži povezav L nato poženemo varianto algoritma DIJKSTRA iz naloge 5.2. function DIJKSTRAPROB( G = ( V, E), s ∈ V, L : E → [0,1]) d ← slovar z vrednostjo 0 za vsako vozlišče v ∈ V pred ← slovar z vrednostjo NULL za vsako vozlišče v ∈ V Q ← prednostna vrsta s prioriteto 0 za vsako vozlišče v ∈ V (na vrhu je vozlišče z največjo prioriteto) Q[ s] ← 1 while ¬ Q.isEmpty() do u, d[ u] ← Q.pop() for v ∈ ADJ( G, u) do if v ∈ Q ∧ Q[ v] < d[ u] · Luv then Q[ v] ← d[ u] · Luv pred[ v] ← u end if end for end while return ( d , pred) end function V primerjavi z algoritmom DIJKSTRA smo torej zamenjali seštevanje z množe-njem in obrnili primerjave, poleg tega pa smo še ustrezno spremenili začetne vrednosti. Preslikava x 7→ −log x pošlje uteži na interval [0,∞], pri čemer se urejenost obrne, množenje se pa nadomesti s seštevanjem – zgornji algoritem je torej ekvivalenten algoritmu DIJKSTRA s tako preslikanimi utežmi, in ima 95 dG ? u v dG( v) > dG( u) + Luv a b c d e f g h pred[ v] g a ∞ > 0 + (−1) −1 ∞ ∞ ∞ ∞ ∞ 0 ∞ g g d ∞ > 0 + 6 −1 ∞ ∞ 6 ∞ ∞ 0 ∞ g g f ∞ > 0 + 6 −1 ∞ ∞ 6 ∞ 6 0 ∞ g g h ∞ > 0 + 6 −1 ∞ ∞ 6 ∞ 6 0 6 g a b ∞ > −1 + 2 −1 1 ∞ 6 ∞ 6 0 6 a a c ∞ > −1 + (−2) −1 1 −3 6 ∞ 6 0 6 a a h 6 > −1 + 0 −1 1 −3 6 ∞ 6 0 −1 a h b 1 6> −1 + 3 −1 1 −3 6 ∞ 6 0 −1 a h f 6 > −1 + 6 −1 1 −3 6 ∞ 5 0 −1 h b c −3 6> 1 + 6 −1 1 −3 6 ∞ 5 0 −1 a b e ∞ > 1 + (−2) −1 1 −3 6 −1 5 0 −1 b c d 6 > −3 + 2 −1 1 −3 −1 −1 5 0 −1 c c f 5 > −3 + 6 −1 1 −3 −1 −1 3 0 −1 c f e −1 6> 3 + 6 −1 1 −3 −1 −1 3 0 −1 b d e −1 6> −1 + 7 −1 1 −3 −1 −1 3 0 −1 b Tabela 13: Potek izvajanja algoritma NAJKRAJŠAPOT za nalogo 5.5(b). dG ? u v dG( v) < dG( u) + Luv a b c d e f g h pred[ v] g a −∞ < 0 + (−1) −1 −∞ −∞ −∞ −∞ −∞ 0 −∞ g g d −∞ < 0 + 6 −1 −∞ −∞ 6 −∞ −∞ 0 −∞ g g f −∞ < 0 + 6 −1 −∞ −∞ 6 −∞ 6 0 −∞ g g h −∞ < 0 + 6 −1 −∞ −∞ 6 −∞ 6 0 6 g a b −∞ < −1 + 2 −1 1 −∞ 6 −∞ 6 0 6 a a c −∞ < −1 + (−2) −1 1 −3 6 −∞ 6 0 6 a a h 6 6< −1 + 0 −1 1 −3 6 −∞ 6 0 6 g h b 1 < 6 + 3 −1 9 −3 6 −∞ 6 0 6 h h f 6 < 6 + 6 −1 9 −3 6 −∞ 12 0 6 h b c −3 < 9 + 6 −1 9 15 6 −∞ 12 0 6 b b e −∞ < 9 + (−2) −1 9 15 6 7 12 0 6 b c d 6 < 15 + 2 −1 9 15 17 7 12 0 6 c c f 12 < 15 + 6 −1 9 15 17 7 21 0 6 c f e 7 < 21 + 6 −1 9 15 17 27 21 0 6 f d e 27 6< 17 + 7 −1 9 15 17 27 21 0 6 f Tabela 14: Potek izvajanja algoritma NAJDALJŠAPOT za nalogo 5.5(c). 96 LA SF PH LV RE EP AQ DE SLC DA OC KC OM ME SL CH 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 * 1LA 1LA 1LA * 1SF * 0.8PH 0.8PH * 0.5LV 0.5LV * 0.7RE * 0.48EP * 0.56AQ 0.56AQ 0.63SLC * * 0.504DE 0.504DE * 0.336OC * 0.3528KC * 0.2016OM * 0.384DA * * 0.31752SL * Tabela 15: Potek izvajanja algoritma za nalogo 5.6(b). tako isto časovno zahtevnost (tj., O( n 2), če za prednostno vrsto uporabimo običajen slovar, in O( m log n), če za prednostno vrsto vzamemo kopico, kjer je n število vozlišč in m število povezav v grafu). (b) Potek izvajanja zgornjega algoritma je prikazan v tabeli 15, iz katere raz-beremo, da je najvarnejša pot LA – SF – RE – SLC – DE – KC – SL – CH, z verjetnostjo, da nas ne oropajo, enako 0.31752. Naloga 5.7. (a) Konstruiramo graf G, katerega vozlišča so kraji z našega seznama, med vozliščema pa je povezava, če lahko cesto med ustreznima krajema prevozimo v enem dnevu. Če vozlišči s in t predstavljata začetno točko in destinacijo, potem lahko na grafu G izvedemo iskanje v širino z začetkom v vozlišču s ter v dobljenem drevesu poiščemo pot do vozlišča t. (b) Iz grafa G izpeljemo graf G 0, ki ga dobimo tako, da odstranimo notranja vozlišča poti iz prejšnje točke (tj., s in t pustimo v G 0). Potem lahko na grafu G 0 izvedemo iskanje v širino z začetkom v vozlišču t ter v dobljenem drevesu poiščemo pot do vozlišča s. (c) Iskanje v širino na grafu G s slike 14 nam da drevo s slike 41, s katere je razvidna pot LJ – WI – BN – LU – AM. Graf G 0 torej dobimo tako, da iz G odstranimo vozlišča WI, BN in LU. Iskanje v širino nam da drevo s slike 42, s katere je razvidna povratna pot AM – BL – PR – BS – BU – LJ. 97 LJ BU VE WI ZG BS MO BN PR PA LU BL BX AM Slika 41: Drevo iskanja v širino na grafu G za nalogo 5.7. AM BL BX PR PA BS MO BU VE LJ ZG Slika 42: Drevo iskanja v širino na grafu G 0 za nalogo 5.7. 98 Naloga 5.8. (a) Drevo iskanja v globino je prikazano na sliki 43, pri čemer sta pri vsakem vozlišču u prikazani še vrednosti ( ù, pu). Prerezna vozlišča grafa s slike 15 so a, b in c. Koren drevesa iskanja v globino a je prerezno vozlišče, ker ima več kot enega naslednika. Ostala prerezna vozlišča prepoznamo po tem, da imajo takega naslednika v drevesu iskanja v globino, da v njegovem poddrevesu ni vozlišč s prečnimi povezavami do predhodnikov obravnavanega vozlišča – drugače povedano, notranje vozlišče u v drevesu iskanja v globino je prerezno vozlišče natanko tedaj, ko obstaja njegov naslednik w, za katerega velja pw ≥ ù. (b) Zapišimo rekurzivno formulo. ¡© ¯ ª ¢ pu = min pw ¯ w ∈ V, u → w ∪ { `w | w ∈ V, u ∼ w ∨ u = w} (c) Zapišimo psevdokodo za funkcijo PREVISIT. function PREVISIT( u, v) if v = NULL then ù ← 0 else ù ← `v + 1 end if end function (d) Zapišimo psevdokodo za funkcijo POSTVISIT. function POSTVISIT( u, v) if ( v = NULL ∧ |ADJ( G, u)| > 1) ∨ ( v 6= NULL ∧ ∃ w ∈ ADJ( G, u) : pw ≤ ù) then izhod.append( u) end if ¡© ¯ ª ¢ pu ← min pw ¯ w ∈ ADJ( G, u) ∧ `w > ù ∪ { `w | w ∈ ADJ( G, u) ∨ w = u} end function (e) Iskanje v globino teče v času O( m + T ), pri čemer je m število povezav v grafu, T pa je čas, porabljen za klic funkcij PREVISIT in POSTVISIT za vsako vozlišče grafa. Funkcija PREVISIT teče v konstantnem času, klic funkcije POSTVISIT( u, v) pa teče v času O( dG( u)), kjer je dG( u) stopnja vozlišča u v grafu G. Ker je vsota stopenj vozlišč grafa enaka dvakratniku števila povezav, lahko sklenemo, da celoten algoritem teče v času O( m). Naloga 5.9. (a) Topološko ureditev dobimo z uporabo algoritma TOPO iz naloge 5.5(a). Dobimo [ s, b, a, d, h, e, c, f , i , g , t]. Graf v tej ureditvi si lahko ogledamo na sliki 44. (b) Najkrajšo pot od vozlišča s do vozlišča t lahko izračunamo z algoritmom NAJKRAJŠAPOT iz naloge 5.5(b). Ta nam vrne pot s − a − d − h − i − t dolžine 11. Delovanje algoritma si lahko ogledamo v tabeli 16. 99 (0,0) a (1,0) b e (1,0) (2,2) c (2,0) h f (2,0) d (3,2) g (3,0) (4,2) i j (5,3) Slika 43: Drevo iskanja v globino za nalogo 5.8. (c) Ker se algoritem odloča neodvisno od svojih prejšnjih odločitev, so vsi dogodki neodvisni. Verjetnost, da pridemo do vozlišča v, bo vsota verjetnosti vseh dogodkov potovanja po (različnih) poteh, ki se končajo v v. Verjetnost potovanja po določeni poti pa bo produkt verjetnosti potovanja po vsaki vsebujoči povezavi. Za verjetnosti qv v usmerjenem acikličnem grafu torej velja zveza X qv = puv qu u→ v qs = 1. Vrednosti qv bomo iskali po topološkem vrstnem redu. function DAGVERJETNOSTI( G = ( V, E), s, ` : E → R+) q ← slovar z vrednostjo 0 za vsako vozlišče v ∈ V q[ s] ← 1 for u ∈ TOPO( G) do P p ← w∈ADJ G( u) ùw for v ∈ ADJ G ( u) do q[ v] ← q[ v] + q[ u] ùv/ p end for end for return q end function Časovna zahtevnost algoritma je O( m), saj gremo po vsaki povezavi preko vsakega vozlišča enkrat, pri čemer pa moramo seveda poskrbeti, da vsote v števcu definicije vrednosti puv ne računamo vsakič sproti, pač pa to storimo pred posodabljanjem verjetnosti sosedom vozlišča u. 100 Naloga 5.10. (a) Imamo neusmerjen graf G = ( V, E) z utežmi na vozliščih cu ( u ∈ V ) in povezavah ùv ( uv ∈ E). Problem bi bilo najlažje reševati z Dijkstrovim algoritmom na usmerjenem grafu D = ( V, A), kjer je A = { uv, vu | uv ∈ E} množica usme-rjenih povezav, z utežmi Luv = ùv + cv ( uv ∈ A). (b) Potek reševanja problema je prikazan v tabeli 17. Najcenejša pot od LJ do BX je LJ – WI – BN – LU – BX s ceno 150. Naloga 5.11. (a) Ustrezni graf je prikazan na sliki 45, iz katere je razvidna topološka ureditev s, c, f , a, e, i , j, b, h, k, d, g , z. Vozlišče s je bilo dodano kot izhodiščna točka s povezavami dolžine 0 do predmetov, h katerim lahko Peter pristopi takoj. (b) S pomočjo algoritma NAJKRAJŠAPOT iz naloge 5.5(b) poiščemo razdalje od vozlišča s do ostalih vozlišč grafa – te so zbrane v tabeli 18. Iz izhoda lahko rekonstruiramo najkrajšo pot s − a − i − h − g − z dolžine 19, ki je prikazana tudi na sliki 45. Peter naj torej zaporedoma opravi predmete a, i , h in g , kar mu bo omogočilo, da po 19 tednih pristopi k zaključnemu izpitu. Naloga 5.12. (a) Definirali bomo usmerjen graf G 0 = ( V 0, E 0), kjer je V 0 = { s, t} ∪ { vA, vB | v ∈ V \ { s, t}} in E 0 = { uX vY | uv ∈ X \ Y , X , Y ∈ { A, B}, u, v 6∈ { s, t}} ∪ { svY | sv ∈ E \ Y , Y ∈ { A, B}, v 6∈ { s, t}} ∪ { uX t | ut ∈ X , X ∈ { A, B}, u 6∈ { s, t}} ∪ { st | st ∈ E}. Cene povezav ohranimo – velja torej L 0 u = L X vY uv ( uX vY ∈ E 0), L 0 sv = L Y sv ( svY ∈ E 0), L 0 uX t = Lut ( uX t ∈ E 0), L 0 st = Lut ( st ∈ E 0). Z Dijkstrovim algoritmom lahko poiščemo najkrajšo pot od s do t v grafu G 0, ki bo oblike s − w(1) X − w (2) − · · · − w ( k) − t , kjer velja Xi ∈ { A, B } (1 ≤ i ≤ 1 X 2 Xk k) in Xi+1 6= Xi = Xi+2 (1 ≤ i ≤ k − 2). Iz te poti lahko izluščimo najkrajšo alternirajočo pot s − w(1) − w(2) − ··· − w( k) − t v grafu G. Graf G 0 ima 2 n−2 vozlišč in m povezav, kjer je n število vozlišč in m število povezav v grafu G. Če v Dijkstrovem algoritmu za prednostno vrsto uporabimo kopico, je časovna zahtevnost algoritma tako O( m log n). 101 3 5 5 6 3 4 3 4 6 1 1 2 2 5 4 s b a d h e c f i g t 4 2 1 1 6 6 4 Slika 44: Predstavitev topološko urejenega grafa za nalogo 5.9(a). u v pred[ v] dG[ v] s a s 2 s b s 3 s c s 5 b a s 2 b c s 5 b e b 9 b f b 7 a d a 8 d e b 9 d g d 14 d h d 9 h e b 9 h g d 14 h i h 10 h t h 12 e c s 5 e f b 7 e g e 13 g t h 12 c f b 7 f i h 10 i t i 11 Tabela 16: Potek izvajanja algoritma NAJKRAJŠAPOT za nalogo 5.9(b). 102 u v Q BX AM BL PR BS PA LU BN WI BU MO VE LJ ZG [(LJ, 0)] ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 0 ∞ LJ VE [(VE, 35)] 35LJ LJ WI [(WI, 33), (VE, 35)] 33LJ LJ ZG [(ZG, 20), (WI, 33), (VE, 35)] 20LJ LJ BU [(ZG, 20), (BU, 25), (WI, 33), (VE, 35)] 25LJ ZG LJ [(BU, 25), (WI, 33), (VE, 35)] ZG BU [(BU, 25), (WI, 33), (VE, 35)] BU LJ [(WI, 33), (VE, 35)] BU ZG [(WI, 33), (VE, 35)] BU WI [(WI, 33), (VE, 35)] BU BS [(WI, 33), (VE, 35), (BS, 40)] 40BU WI LJ [(VE, 35), (BS, 40)] WI BU [(VE, 35), (BS, 40)] WI BS [(VE, 35), (BS, 40)] WI PR [(VE, 35), (BS, 40), (PR, 53)] 53WI WI BN [(VE, 35), (BS, 40), (PR, 53), (BN, 68)] 68WI VE LJ [(BS, 40), (PR, 53), (BN, 68)] VE MO [(BS, 40), (PR, 53), (BN, 68), (MO, 79)] 79VE BS BU [(PR, 53), (BN, 68), (MO, 79)] BS WI [(PR, 53), (BN, 68), (MO, 79)] BS PR [(PR, 53), (BN, 68), (MO, 79)] PR BS [(BN, 68), (MO, 79)] PR WI [(BN, 68), (MO, 79)] PR BL [(BN, 68), (MO, 79), (BL, 83)] 83PR BN WI [(MO, 79), (BL, 83)] BN MO [(MO, 79), (BL, 83)] BN LU [(MO, 79), (BL, 83), (LU, 101)] 101BN MO VE [(BL, 83), (LU, 101)] MO BN [(BL, 83), (LU, 101)] MO PA [(BL, 83), (LU, 101), (PA, 133)] 133MO BL PR [(LU, 101), (PA, 133)] BL AM [(LU, 101), (AM, 127), (PA, 133)] 127BL LU BN [(AM, 127), (PA, 133)] LU AM [(AM, 127), (PA, 133)] LU BX [(AM, 127), (PA, 133), (BX, 150)] 150LU LU PA [(AM, 127), (PA, 133), (BX, 150)] AM BL [(PA, 133), (BX, 150)] AM LU [(PA, 133), (BX, 150)] AM BX [(PA, 133), (BX, 150)] PA MO [(BX, 150)] PA LU [(BX, 150)] PA BX [(BX, 150)] BX AM [ ] BX LU [ ] BX PA [ ] Tabela 17: Potek izvajanja algoritma za nalogo 5.10. s c f a e i j b h k d g z 0 0 s 0 s 0 s 4 f 5 a 5 a 9 c 10 i 15 j 16 b 14 h 19 g Tabela 18: Izračunane vrednosti v algoritmu za nalogo 5.11(b). (b) Potek izvajanja Dijkstrovega algoritma na pomožnem grafu G 0 je prikazan v tabeli 19. Najkrajša pot v grafu G 0 je s − wA − rB − t dolžine 10, kar ustreza najkrajši alternirajoči poti s − w − r − t v grafu G. Naloga 5.13. (a) Algoritem BFS iz naloge 5.1 vrne želeni slovar. Ker lahko koren poljubno izberemo, lahko slovar pred dobimo s klicem BFS( T, V, NOOP). Neposredni nasledniki vozlišča u v drevesu T so tisti njegovi sosedi v ∈ ADJ( T, u), za katere velja v 6= pred[ u]. 103 c 0 9 0 4 7 s f e b d 8 4 0 8 7 5 5 a i g h z 5 4 5 6 j k 10 Slika 45: Graf in najkrajša pot za nalogo 5.11. Trenutno vozlišče s rA rB uA uB vA vB wA wB t 0 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ s 0 ∞ 4 s 10 s ∞ ∞ ∞ 1 s ∞ 12 s wA 0 ∞ 3 w 10 1 A s ∞ ∞ 2 wA s ∞ 12 s vB 0 4 v 3 10 1 B wA s ∞ ∞ 2 wA s ∞ 12 s rB 0 4 v 3 10 2 1 B wA s ∞ 5 rB wA s ∞ 10 rB rA 0 4 v 3 10 2 1 10 B wA s ∞ 5 rB wA s 6 rA rB vA 0 4 v 3 10 5 2 1 10 B wA s 7 vA rB wA s 6 rA rB wB 0 4 v 3 9 7 5 2 1 10 B wA wB vA rB wA s 6 rA rB uB 0 4 v 3 9 7 5 2 1 10 B wA wB vA rB wA s 6 rA rB uA 0 4 v 3 9 7 5 2 1 10 B wA wB vA rB wA s 6 rA rB t 0 4 v 3 9 7 5 2 1 10 B wA wB vA rB wA s 6 rA rB Tabela 19: Potek reševanja za nalogo 5.12(b). (b) Naj bosta xu in yu teži najtežje neodvisne množice S v poddrevesu s korenom u (glede na slovar pred), za katero velja u ∈ S oziroma u 6∈ S. Potem velja X xu = cu + yv in v∼ u v 6=pred[ u] X yu = max{ xv, yv}. v∼ u v 6=pred[ u] Vrednosti xu in yu računamo od listov v smeri proti korenu r (tj., v topološki ureditvi glede na pred). Težo najtežje neodvisne množice dobimo kot c∗ = 104 max{ xr , yr }. (c) Da iz vrednosti xu in yu ( u ∈ V ) izluščimo najtežjo neodvisno množico S v drevesu T , se sprehodimo od korena proti listom (npr. z iskanjem v širino) in posamezno vozlišče u dodamo v množico S, če njegov prednik ni v S in velja xu ≥ yu. function NAJTEŽJANEODVISNAMNOŽICA( T = ( V, E), r,( xu) u∈ V ,( yu) u∈ V ) S ← prazna množica function VISIT( u, v) if v 6∈ S ∧ xu ≥ yu then S.add( u) end if end function BFS( T, { r }, VISIT) return S end function (d) Naj bo n število vozlišč drevesa T . Potem ima T natanko n − 1 povezav. Za izračun najtežje neodvisne množice naredimo tri preglede v širino, pri čemer v vsakem vozlišču porabimo konstantno mnogo časa. Časovna zahtevnost celotnega algoritma je torej O( n). (e) Izračunajmo vrednosti xu in yu ( u ∈ V ), če za koren vzamemo vozlišče a. xi = 9 yi = 0 x j = 4 y j = 0 xk = 2 yk = 0 xd = 1 yd = 0 xe = 1 + 0 + 0 = 1 ye = max{9,0} + max{4,0} = 13 x f = 4 y f = 0 xg = 8 + 0 = 8 yg = max{2,0} = 2 xh = 4 yh = 0 xb = 1 + 0 + 13 + 0 = 14 yb = max{1,0} + max{1,13} + max{4,0} = 18 xc = 9 + 2 + 0 = 11 yc = max{8,0} + max{4,0} = 12 xa = 8 + 18 + 12 = 38 ya = max{14,18} + max{11,12} = 30 Teža najtežje neodvisne množice S je torej c∗ = max{ xa, ya} = 38. Poglejmo, katera vozlišča so v množici S. c∗ = xa xa = ca + yb + yc a ∈ S yb = xd + ye + xf b 6∈ S yc = xg + xh c 6∈ S xd = cd d ∈ S 105 ye = xi + xj e 6∈ S x f = cf f ∈ S xg = cg + yk g ∈ S xh = ch h ∈ S xi = ci i ∈ S x j = cj j ∈ S yk = 0 k 6∈ S Najtežja neodvisna množica je torej S = { a, d, f , g, h, i, j }. Naloga 5.14. (a) Za dani graf G = ( V, E), vozlišči s, t ∈ V , uteži povezav Luv ( uv ∈ E) in uteži vozlišč cv ( v ∈ V ) bomo izračunali nove uteži povezav ùv = Luv + cv ( uv ∈ E), ki predstavljajo skupen strošek prehoda od operaterja u k operaterju v. Ker so te uteži še vedno lahko tudi negativne, bomo v grafu G poiskali najkrajšo pot od s do t s pomočjo Bellman-Fordovega algoritma, ki teče v času O( mn), kjer je n število vozlišč in m število povezav grafa G. (b) Najprej izračunajmo nove uteži povezav. ` brez, Bobitel = 65 + 15 = 80 ` brez, Sodafon = 85 + 10 = 95 ` brez, Rega = 95 + 0 = 95 ` brez, Fenmobil = 50 + 30 = 80 ` brez, Z 0 = 60 + 5 = 65 ` brez, TeleJanez = 45 + 20 = 65 `Bobitel, Sodafon = 10 + 10 = 20 `Sodafon, Rega = −5 + 0 = −5 `Rega, Fenmobil = −15 + 30 = 15 `Fenmobil, Z 0 = −10 + 5 = −5 `Z 0, TeleJanez = 5 + 20 = 25 `TeleJanez, Bobitel = 0 + 15 = 15 `TeleJanez, Fenmobil = −20 + 30 = 10 `Fenmobil, Sodafon = 5 + 10 = 15 `Sodafon, TeleJanez = 20 + 20 = 40 Za izračun najcenejše poti od vozlišča brez do vozlišča Rega bomo sledili algoritmu BELLMANFORD iz naloge 5.4, pri čemer bomo upoštevali vrstni red povezav iz zgornjega seznama. Strnjen potek algoritma (samo koraki, kjer se 106 i u v ùv brez Bobitel Sodafon Rega Fenmobil Z 0 TeleJanez 1 brez ostali 0 80brez 95brez 95brez 80brez 65brez 65brez 1 Sodafon Rega −5 0 80brez 95brez 90 Sodafon 80brez 65brez 65brez 1 TeleJanez Fenmobil 10 0 80brez 95brez 90 Sodafon 75 TeleJanez 65brez 65brez 1 Fenmobil Sodafon 10 0 80brez 90 Fenmobil 90 Sodafon 75 TeleJanez 65brez 65brez 2 Sodafon Rega −5 0 80brez 90 Fenmobil 85 Sodafon 75 TeleJanez 65brez 65brez Tabela 20: Potek izvajanja algoritma za nalogo 5.14(b). katera od razdalj spremeni) je prikazan v tabeli 20. Za najcenejše zaporedje prehodov med operaterji tako dobimo TeleJanez, Fenmobil, Sodafon, Rega, skupni strošek pa je 75. Naloga 5.15. (a) Pomagali si bomo z iskanjem v širino. Zapišimo algoritem, ki kliče funkcijo BFS iz naloge 5.1. function ŠTEVILONAJKRAJŠIH( G = ( V, E), s) število ← slovar s ključi v ∈ V in vrednostmi 0 globina ← slovar s ključi v ∈ V in vrednostmi ∞ število[ s] ← 1 globina[ s] ← 0 function VISIT( u, v) for w ∈ ADJ( G, u) do if globina[ w ] = ∞ then globina[ w] ← globina[ u] + 1 end if if globina[ w ] = globina[ u] + 1 then število[ w] ← število[ w]+ število[ u] end if end for end function BFS( G, { s}, VISIT) return globina end function Vidimo, da s klicanjem funkcije VISIT na vsakem vozlišču vsako povezavo obravnavamo največ dvakrat, tako da je časovna zahtevnost algoritma O( m). (b) Potek izvajanja algoritma je prikazan v tabeli 21, pri čemer je bil upoštevan abecedni vrstni red obiskovanja sosedov posameznega vozlišča. Končni rezultat lahko preberemo iz zadnje vrstice tabele. 107 globina število u a b c d e f g h i a b c d e f g h i ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 0 0 0 0 0 0 0 0 0 1 i ∞ ∞ ∞ ∞ ∞ 1 1 1 0 0 0 0 0 0 1 1 1 1 f ∞ ∞ 2 ∞ 2 1 1 1 0 0 0 1 0 1 1 1 1 1 g ∞ ∞ 2 2 2 1 1 1 0 0 0 2 1 1 1 1 1 1 h ∞ ∞ 2 2 2 1 1 1 0 0 0 2 1 2 1 1 1 1 c 3 3 2 2 2 1 1 1 0 2 2 2 1 2 1 1 1 1 e 3 3 2 2 2 1 1 1 0 2 4 2 1 2 1 1 1 1 d 3 3 2 2 2 1 1 1 0 3 4 2 1 2 1 1 1 1 a 3 3 2 2 2 1 1 1 0 3 4 2 1 2 1 1 1 1 b 3 3 2 2 2 1 1 1 0 3 4 2 1 2 1 1 1 1 Tabela 21: Potek izvajanja algoritma za nalogo 5.15(b). Naloga 5.16. (a) Zgledovali se bomo po algoritmu NAJKRAJŠAPOT iz naloge 5.5. Zapišimo algoritem, ki kliče funkciji TOPO in REKONSTRUIRAJPOT iz iste naloge, poleg tega pa kliče tudi funkcijo ADJIN, ki vrne množico vozlišč v podanem usmerjenem grafu s povezavo do podanega vozlišča. function JADRNICA( G = ( V, E), s, t,( ku) u∈ V ) c ← slovar z vrednostjo −∞ za vsako vozlišče v ∈ V pred ← slovar z vrednostjo NULL za vsako vozlišče v ∈ V for u ∈ TOPO( G) do for v ∈ ADJIN( G, u) do if c[ v] > c[ u] then c[ v] ← c[ u] pred[ v] ← u end if end for if c[ u] > ku then c[ u] ← ku end if end for return REKONSTRUIRAJPOT(pred, t ) end function Algoritem opravi topološko urejanje grafa, nato vsako povezavo pregleda enkrat, nazadnje pa opravi še obratni prehod po najdeni poti, tako da je njegova časovna zahtevnost O( m). (b) Graf s slike 21 ima topološko ureditev KP, PU, RI, ML, ZD, DO, ŠI, ST, HV, DU. Izračunane vrednosti v tabelah c in pred v algoritmu iz točke (a) so prikazane v tabeli 22, iz katere je razvidno, da gre lahko na jadrnico največ 15 prijateljev, kar je mogoče doseči z izbiro poti KP – PU – ZD – DO – HV – DU. 108 KP PU RI ML ZD DO ŠI ST HV DU 20 18KP 14PU 12PU 16PU 15ZD 13ZD 13ŠI 15DO 15HV Tabela 22: Izračunane vrednosti v algoritmu za nalogo 5.16(b). 109 2.6 CPM/PERT Naloga 6.1. (a) Projekt predstavimo z usmerjenim acikličnim grafom G = ( V, E), kjer vozlišča predstavljajo opravila, posebej pa dodamo še začetno vozlišče s in končno vozlišče t. Opravilo u povežemo z opravilom v, če je u pogoj za začetek opravila v. Poleg tega vozlišče s povežemo z opravili, ki nimajo predpogojev; opravila, ki niso predpogoj za katero drugo opravilo, pa povežemo z vozliščem t. Povezave iz opravila u utežimo s trajanjem opravila u, na povezave iz s pa postavimo utež 0. Na grafu G uporabimo algoritem NAJDALJŠAPOT iz naloge 5.5(c) z začetkom v s in tako za vsako opravilo dobimo najzgodnejši čas, ko ga lahko začnemo. Dolžina najdaljše poti do vozlišča t predstavlja najkrajše možno trajanje celotnega projekta. Nato na obratnem grafu G 0 = ( V, E 0), kjer je E 0 = { vu | uv ∈ E} množica obratnih povezav z enakimi utežmi, še enkrat uporabimo algoritem NAJDALJŠAPOT, tokrat z začetkom v t, in dobljene razdalje odštejemo od najkrajšega možnega trajanja projekta. Tako za vsako opravilo dobimo še najpoznejši možen čas začetka, da se celotno trajanje projekta ne poveča. Pri kritičnih opravilih sta oba časa enaka. Projekt lahko predstavimo z uteženim grafom s slike 46, iz katerega je razvidna topološka ureditev s, a, f , g , b, e, c, d, t. V tabeli 23 so podani rezultati, dobljeni z zgornjim postopkom. Vidimo, da je najkrajše trajanje projekta 31 dni, kritična opravila pa so a, b, c, d, e. (b) Opazimo, da vsa kritična opravila ležijo na dveh poteh od s do t. Kritični poti sta torej s − a − e − d − t in s − a − b − c − d − t. (c) Iz tabele 23 je razvidno, da je najmanj kritično opravilo f , saj ga lahko brez podaljševanja celotnega trajanja podaljšamo za 2 dni, kar je več kot katerokoli drugo opravilo. (d) Skrajšati želimo katero od kritičnih opravil, ki leži na obeh kritičnih poteh (taki sta a in d), saj sicer ne bomo skrajšali celotnega trajanja projekta. Ker ima pot s− g − t dolžino 30 dni, bomo lahko celotno trajanje skrajšali za največ 1 dan. To lahko dosežemo, če skrajšamo opravilo a, ki bo tako namesto 10 trajalo 9 dni, skupaj pa bo projekt trajal 30 dni. Naloga 6.2. Zapisali bomo linearni program, ki bo za vsako opravilo imel spremenljivki xu in yu, ki določata število dni, za katerega skrajšamo trajanje opravila u, oziroma čas začetka izvajanja opravila u. min 200 xa + 100 xb + 150 xc + 160 xd + 250 xe + 240 xf + 300 xg 110 e 13 10 0 6 8 s a b c d t 10 7 0 14 0 f 30 g Slika 46: Graf odvisnosti med opravili in kritična pot za nalogo 6.1. s a f g b e c d t najzgodnejši začetek 0 0 s 0 s 0 s 10 a 10 a 16 b 23 c, e 31 d najpoznejši začetek 0 a 0 e 2 c 1 t 10 c 10 d 16 d 23 t 31 razlika 0 0∗ 2 1 0∗ 0∗ 0∗ 0∗ 0 Tabela 23: Razporejanje opravil za nalogo 6.1. Opravila brez pogojev: ya, yd, ye ≥ 0 Odvisnosti med opravili: yb − ya + xa ≥ 10 ye − ya + xa ≥ 10 yc − yb + xb ≥ 6 yd − yc + xc ≥ 7 yd − ye + xe ≥ 13 yc − yf + xf ≥ 14 Želeni čas trajanja: yd − xd ≤ 19 yg − xg ≤ −3 Minimalno trajanje opravil: 0 ≤ xa ≤ 3 0 ≤ xb ≤ 1 111 3 b h 0 2 3 0 5 2 8 s c a e f g i t 5 5 1 0 2 5 1 j d Slika 47: Graf odvisnosti med opravili in kritična pot za nalogo 6.3. 0 ≤ xc ≤ 2 0 ≤ xd ≤ 2 0 ≤ xe ≤ 4 0 ≤ xf ≤ 3 0 ≤ xg ≤ 5 Naloga 6.3. (a) Projekt lahko predstavimo z uteženim grafom s slike 47, iz katerega je razvidna topološka ureditev s, b, c, j, a, e, d, f , g , h, i , t. (b) V tabeli 24 so podani najzgodnejši začetki opravil in najpoznejši začetki, da se celotno trajanje priprave ne podaljša. Priprava bo torej trajala najmanj 28 minut, edina kritična pot pa je s − c − a − e − f − h − i − t, ki tako vsebuje tudi vsa kritična opravila. (c) Iz tabele 24 je razvidno, da je najmanj kritično opravilo j , saj lahko njegovo trajanje podaljšamo za 18 minut, ne da bi vplivali na trajanje celotnega projekta. Naloga 6.4. Skupna rezerva opravila je največji čas, za katerega lahko zamaknemo končanje opravila, ne da bi s tem vplivali na čas končanja projekta. Izračunamo jo kot minimalno razliko najkasnejšega začetka naslednika in najzgodnejšega konca predhodnika, od katere odštejemo trajanje opravila. Skupne rezerve računamo pri določitvi kritičnih in najmanj kritičnih opravil ter so za nalogo 6.3 prikazane v vrstici “razlika” tabele 24. 112 s b c j a e d f g h i t najprej 0 0 s 0 s 0 s 5 b 10 a 15 e 15 e 17 f 17 f 20 h 28 i najkasneje 0 c 14 h 0 a 18 g 5 e 10 f 26 t 15 h 19 i 17 i 20 t 28 razlika 0 14 0∗ 18 0∗ 0∗ 11 0∗ 2 0∗ 0∗ 0 proste rezerve 0 14 0 16 0 0 11 0 2 0 0 0 varnostne rezerve 0 14 0 18 0 0 11 0 0 0 0 0 neodvisne rezerve 0 14 0 16 0 0 11 0 0 0 0 0 Tabela 24: Razporejanje opravil za nalogo 6.3 in rezerve za nalogo 6.4. Prosta rezerva opravila je največji čas, za katerega lahko zamaknemo končanje opravila, če z nasledniki začnemo ob najzgodnejšem možnem času. Izračunamo jo kot minimalno razliko najzgodnejšega začetka naslednika in najzgodnejšega konca predhodnika, od katere odštejemo trajanje opravila. Varnostna rezerva opravila je največji čas, za katerega lahko zamaknemo kon- čanje opravila, ne da bi s tem vplivali na čas končanja projekta, če s predhodniki končamo ob najkasnejšem možnem času. Izračunamo jo kot minimalno razliko najkasnejšega začetka naslednika in najkasnejšega konca predhodnika, od katere odštejemo trajanje opravila. Neodvisna rezerva opravila je največji čas, za katerega lahko zamaknemo končanje opravila, če z nasledniki začnemo ob najzgodnejšem možnem času in s predhodniki končamo ob najkasnejšem možnem času. Izračunamo jo kot minimalno razliko najzgodnejšega začetka naslednika in najkasnejšega konca predhodnika, od katere odštejemo trajanje opravila. Tudi proste, varnostne in neodvisne rezerve opravil iz naloge 6.3 so prikazane v tabeli 24. Naloga 6.5. Prvi kuhar bo prevzel opravila c, a, e, f , h, i , drugi pa opravila b, j, d, g . Iz tabele 24 je razvidno, da ga najbolj omejuje razporeditev opravilo g – najhitreje ga lahko začne 17 minut po začetku priprave, in tedaj ga konča 18 minut po začetku. Taka razporeditev mu dovoljuje, da z opravilom d začne 15 minut po začetku priprave in ga konča do začetka opravila g . Opravili b in j lahko tako opravi pred tem – začne torej 11 minut po začetku priprave in obe zaključi (vrstni red ni pomemben), preden se loti opravila d. Drugi kuhar lahko tako zaporedoma izvede opravila b, j, d, g , z začetkom 11 minut po začetku priprave in s koncem 7 minut kasneje (torej brez prestanka). Naloga 6.6. (a) Projekt lahko predstavimo z uteženim grafom s slike 48, iz katerega je razvidna topološka ureditev s, a, `, h, k, m, b, d, c, j, e, f , g , i , t. (b) V tabeli 25 so podani najzgodnejši začetki opravil in najpoznejši začetki, da se celotno trajanje projekta ne podaljša. Izdelava bo torej trajala 150 dni, edina 113 45 g 30 h i 15 10 20 0 15 15 40 35 s a k b j t 40 15 20 20 0 d e f 15 10 30 25 ` m c 20 10 Slika 48: Graf odvisnosti med opravili in kritična pot za nalogo 6.6. s a ` h k m b d c j e f g i t najprej 0 0 s 0 s 15 a 15 a 20 ` 30 k 30 m 30 m 70 b 70 b 90 e 110 f 140 g 150 i najkasneje 0 a 0 k 10 m 65 g 15 b 30 d 30 e 40 e 65 f 115 t 70 f 90 g 110 i 140 t 150 razlika 0 0∗ 10 50 0∗ 10 0∗ 10 35 45 0∗ 0∗ 0∗ 0∗ 0 Tabela 25: Razporejanje opravil za nalogo 6.6. kritična pot pa je s − a − k − b − e − f − g − i − t, ki tako vsebuje tudi vsa kritična opravila. (c) Iz tabele 25 je razvidno, da je najmanj kritično opravilo h, saj lahko njegovo trajanje podaljšamo za 50 dni, ne da bi vplivali na trajanje celotnega projekta. Naloga 6.7. (a) Projekt lahko predstavimo z uteženim grafom s slike 49, iz katerega je razvidna topološka ureditev s, a, h, c, d, j, i , k, e, g , f , b, t. Uteži povezav ustrezajo pričakovanim trajanjem opravil, ki so prikazana v tabeli 26. (b) V tabeli 26 so podani najzgodnejši začetki opravil in najpoznejši začetki, da se celotno trajanje gradnje ne podaljša. Pričakovano trajanje gradnje je torej µ = 57 dni, edina kritična pot pa je s − h − j − e − f − b − t, ki tako vsebuje tudi vsa kritična opravila. (c) Iz tabele 26 je razvidno, da je najmanj kritično opravilo i , saj lahko njegovo trajanje podaljšamo za 29 dni v primerjavi s pričakovanim, ne da bi vplivali na trajanje celotnega projekta. (d) Variance trajanj opravil so prikazane v tabeli 26. Izračunajmo standardni odklon trajanja pričakovane kritične poti. p σ = 4 + 1 + 0 + 2.25 + 2.25 = 3.082 Naj bo X slučajna spremenljivka, ki meri čas izvajanja pričakovane kritične poti. Izračunajmo verjetnost končanja v roku T = 55 dni. µ ¶ T − µ P( X ≤ 55) = Φ = Φ(−0.6489) = 0.2578 σ 114 6 8 4 c e f b 14 21 14 a k 0 14 12.5 s d t 14 .5 0 15 h 14 8.5 i 14.5 .5 8. .5 27 5 15 j g 15.5 Slika 49: Graf odvisnosti med opravili in kritična pot za nalogo 6.7. s a h c d j i k e g f b t pričakovano 14 8.5 6 14.5 15.5 14 12.5 8 27.5 4 21 varianca 4 2.25 1 6.25 2.25 1 2.25 1 2.25 0 4 najprej 0 0 s 0 s 14 a 14 a 8.5 h 14 a 24 j 24 j 28.5 d 32 e 36 f 57 b najkasneje 0 h 1 d 0 j 18 e 15 g 8.5 e 43 t 44.5 t 24 f 29.5 t 32 b 36 t 57 razlika 0 1 0∗ 4 1 0∗ 29 20.5 0∗ 1 0∗ 0∗ 0 Tabela 26: Razporejanje opravil za nalogo 6.7. Naloga 6.8. (a) Projekt lahko predstavimo z uteženim grafom s slike 50, iz katerega je razvidna topološka ureditev s, a, b, c, d, f , g , h, e, t. V tabeli 27 so podani najzgodnejši začetki opravil in najpoznejši začetki, da se celotno trajanje izdelave ne podaljša. Izdelava bo trajala najmanj 88 dni, edina kritična pot pa je s − b − h − e − t, ki tako vsebuje vsa kritična opravila. (b) Iz tabele 27 je razvidno, da je najmanj kritično opravilo c, saj lahko njegovo trajanje podaljšamo za 41 dni, ne da bi vplivali na trajanje celotnega projekta. (c) Zapišimo linearni program, ki bo za vsako opravilo imel spremenljivki xu in yu, ki določata število dni, za katerega skrajšamo trajanje opravila u, oziroma čas začetka izvajanja opravila u. min 1000 xa + 1500 xb + 800 xc + 1200 xd +500 xe + 1100 xf + 1300 xg + 1400 xh 115 s a b c d f g h e t najzgodnejši začetek 0 0 s 0 s 0 s 40 a 50 b 50 b 50 b 70 h 88 e najpoznejši začetek 0 18 d 0 h 41 g 58 t 60 e 76 t 50 e 70 t 88 razlika 0 18 0∗ 41 18 10 26 0∗ 0∗ 0 Tabela 27: Razporejanje opravil za nalogo 6.8. Opravila brez pogojev: ya, yb, yc ≥ 0 Odvisnosti med opravili: yd − ya + xa ≥ 40 ye − yf + xf ≥ 10 ye − yg + xg ≥ 12 ye − yc + xc ≥ 90 y f − ya + xa ≥ 40 y f − yb + xb ≥ 50 yg − yb + xb ≥ 50 yg − yc + xc ≥ 35 yh − yb + xb ≥ 50 Želeni čas trajanja: yd − xd ≤ 45 ye − xe ≤ 57 yg − xg ≤ 63 Minimalno trajanje opravil: 0 ≤ xa ≤ 4 0 ≤ xb ≤ 2 0 ≤ xc ≤ 4 0 ≤ xd ≤ 2 0 ≤ xe ≤ 2 0 ≤ xf ≤ 1 0 ≤ xg ≤ 2 0 ≤ xh ≤ 2 116 d 40 a 40 30 0 f 50 10 18 s b e t 0 50 20 0 h 50 12 c 35 g Slika 50: Graf odvisnosti med opravili in kritična pot za nalogo 6.8. Naloga 6.9. (a) Projekt lahko predstavimo z uteženim grafom s slike 51, iz katerega je razvidna topološka ureditev s, a, i , c, d, e, h, f , g , b, t. Uteži povezav ustrezajo pričakovanim trajanjem opravil, ki so prikazana v tabeli 28. (b) V tabeli 28 so podani najzgodnejši začetki opravil in najpoznejši začetki, da se celotno trajanje gradnje ne podaljša. Pričakovano trajanje gradnje je torej µ = 166 dni, edina kritična pot pa je s − i − d − g − b − t, ki tako vsebuje tudi vsa kritična opravila. (c) Iz tabele 28 je razvidno, da je najmanj kritično opravilo h, saj lahko njegovo trajanje podaljšamo za 116.5 dni v primerjavi s pričakovanim, ne da bi vplivali na trajanje celotnega projekta. (d) Izračunajmo standardni odklon trajanja pričakovane kritične poti. p σ = 1 + 9 + 16 + 4 = 5.477 Naj bo X slučajna spremenljivka, ki meri čas izvajanja pričakovane kritične poti. Izračunajmo verjetnost končanja v roku T = 180 dni. µ ¶ T − µ P( X ≤ 180) = Φ = Φ(2.556) = 0.9947 σ 117 c .5 46 15 .5 15.5 37 a d f 0 79 22 37 22 s 15 b t .5 0 15 85 i e g .5 8.5 27.5 22 h Slika 51: Graf odvisnosti med opravili in kritična pot za nalogo 6.9. s a i c d e h f g b t pričakovano 15.5 22 46.5 37 8.5 27.5 79 85 22 varianca 2.25 1 10.03 9 0.69 2.25 36 16 4 najprej 0 0 s 0 s 15.5 a 22 i 15.5 a 22 i 62 c 59 d 144 g 166 b najkasneje 0 i 3 c 0 d 18.5 f 22 g 50.5 g 138.5 t 65 b 59 b 144 t 166 razlika 0 3 0∗ 3 0∗ 35 116.5 3 0∗ 0∗ 0 Tabela 28: Razporejanje opravil za nalogo 6.9. Naloga 6.10. (a) Projekt lahko predstavimo z uteženim grafom s slike 52, iz katerega je razvidna topološka ureditev s, a, b, d, c, e, g , f , h, t. V tabeli 29 so podani najzgodnejši začetki opravil in najpoznejši začetki, da se celotno trajanje gradnje ne podaljša. Gradnja bo trajala najmanj 215 dni, edina kritična pot pa je s − a − c − g − t, ki tako vsebuje vsa kritična opravila. (b) Iz tabele 29 je razvidno, da je najmanj kritično opravilo d, saj lahko njegovo trajanje podaljšamo za 100 dni, ne da bi vplivali na trajanje celotnega projekta. (c) Zapišimo linearni program, ki bo za vsako opravilo imel spremenljivki xu in yu, ki določata število dni, za katerega skrajšamo trajanje opravila u, oziroma čas začetka izvajanja opravila u. min 300 xa + 200 xb + 700 xc + 1100 xd +1500 xe + 900 xf + 400 xg + 150 xh 118 s a b d c e g f h t najzgodnejši začetek 0 0 s 0 s 45 a 45 a 135 c 135 c 165 e 200 f 215 g najpoznejši začetek 0 0 c 25 c 145 f 45 g 140 f 135 t 170 h 205 t 215 razlika 0 0∗ 25 100 0∗ 5 0∗ 5 5 0 Tabela 29: Razporejanje opravil za nalogo 6.10. Opravila brez pogojev: ya, yb ≥ 0 Odvisnosti med opravili: yc − ya + xa ≥ 45 yc − yb + xb ≥ 20 yd − ya + xa ≥ 45 ye − yc + xc ≥ 90 y f − yd + xd ≥ 25 y f − ye + xe ≥ 30 yg − yc + xc ≥ 90 yh − yf + xf ≥ 35 Želeni čas trajanja: yg − xg ≤ 120 yh − xh ≤ 190 Minimalno trajanje opravil: 0 ≤ xa ≤ 5 0 ≤ xb ≤ 5 0 ≤ xc ≤ 20 0 ≤ xd ≤ 3 0 ≤ xe ≤ 4 0 ≤ xf ≤ 7 0 ≤ xg ≤ 15 0 ≤ xh ≤ 2 119 45 a d 0 45 25 90 35 10 s b c e f h t 0 20 30 90 80 g Slika 52: Graf odvisnosti med opravili in kritična pot za nalogo 6.10. 120 2.7 Upravljanje zalog Naloga 7.1. Imamo sledeče podatke (pri časovni enoti 1 teden). ν = 10 s = 0.2e K = 150e λ = 12.5 p = 0.8e Izračunajmo optimalno dolžino cikla τ∗ in največjo zalogo M∗. ³ ν ´ α = ν 1 − = 10 · (1 − 0.8) = 2 λ s 0.2 β = 1 + = 1 + = 1.25 p 0.8 s r 2 K β 375 τ∗ = = ≈ 30.619 sα 0.4 s r 2 K α 600 M∗ = = ≈ 48.990 sβ 0.25 Optimalna dolžina cikla je torej približno 30.619 tednov, pri tem pa Marta potrebuje skladišče za 49 kosov nakita. Izračunajmo še število izdelanih kosov nakita q∗, trajanje proizvodnje t∗ in največji primanjkljaj m∗ v posameznem ciklu. q∗ = τ∗ ν ≈ 30.619 · 10 ≈ 306.186 q∗ 306.186 t∗ = ≈ ≈ 24.495 λ 12.5 m∗ = τ∗ α − M∗ ≈ 30.619 · 2 − 48.990 ≈ 12.247 V vsakem intervalu torej Marta izdela okoli 306 kosov nakita, pri čemer izdelo-vanje traja približno 24.495 tednov, primanjkljaj pa ne preseže 13 kosov nakita. Naloga 7.2. Imamo sledeče podatke (pri časovni enoti 1 teden). ν = 60 λ = 90 K = 180e s = 0.5e Pri teh podatkih izračunajmo še ³ µ ¶ ν ´ 2 α = ν 1 − = 60 · 1 − = 20. λ 3 121 (a) Če primanjkljaja ne dovolimo, imamo p = ∞ in torej β = 1. Izračunajmo optimalno dolžino cikla τ∗, največjo zalogo M∗ in enotske stroške S∗. s r 2 K β 360 τ∗ = = = 6 sα 10 s r 2 K α 7200 M∗ = = = 120 sβ 0.5 s2 Ksα p S∗ = = 3600e = 60e β Optimalna dolžina cikla je torej 6 tednov, pri tem pa mora vulkanizer imeti skladišče za 120 pnevmatik. Tedenski stroški proizvodnje in skladiščenja so 60e. (b) Izračunajmo še trajanje proizvodnje t∗ in število izdelanih pnevmatik q∗ v posameznem ciklu. M∗ 120 t∗ = = = 4 λ − ν 30 q∗ = τ∗ ν = t∗ λ = 6 · 60 = 360 Proizvodnja torej traja 4 tedne, skupno pa v tem času izdela 360 pnevmatik. (c) Vzamemo p = 2e in torej β = 1 + s/ p = 1.25. Izračunajmo optimalno dolžino cikla, potrebno velikost skladišča in enotske stroške še v tem primeru. s r 2 K β 450 τ∗ = = ≈ 6.708 sα 10 s r 2 K α 7200 M∗ = = ≈ 107.331 sβ 0.625 s r 2 K sα 3600 S∗ = = e ≈ 53.666e β 1.25 Optimalni interval naročanja je v tem primeru torej 6.708 tednov, pri tem pa mora vulkanizer imeti skladišče za 108 pnevmatik. Tedenski stroški proizvodnje in skladiščenja so 53.666e. Izračunajmo še največji primanjkljaj m∗ v posameznem ciklu. m∗ = τ∗ α − M∗ ≈ 6.708 · 20 − 107.331 ≈ 26.833 Največji primanjkljaj torej ne preseže 27 pnevmatik. 122 Naloga 7.3. Imamo sledeče podatke (pri časovni enoti 1 mesec). ν = 20 K = 750e s = 10e p = 50e Pri teh podatkih izračunajmo še s 10 β = 1 + = 1 + = 1.2. p 50 Ker artiklov ne proizvajamo (tj., ob dostavi imamo na voljo celotno količino naročila), vzamemo λ = ∞ in torej α = ν. (a) Izračunajmo optimalno dolžino cikla τ∗, največjo zalogo M∗ in enotske stroš- ke S∗. s r 2 K β 1800 τ∗ = = = 3 sα 200 s r 2 K α 30000 M∗ = = = 50 sβ 12 s r 2 K sα 300000 S∗ = = e = 500e β 1.2 Optimalna dolžina cikla je torej 3 mesece, pri tem pa mora trgovina imeti skladišče za 50 sedežnih garnitur. Mesečni stroški nabave in skladiščenja so 60e. (b) Izračunajmo še največji primanjkljaj m∗ in velikost naročila q∗. m∗ = τ∗ α − M∗ = 3 · 20 − 50 = 10 q∗ = τ∗ ν = 3 · 20 = 60 (c) Drugo skladišče lahko hrani n 0 = 40 sedežnih garnitur, mesečni strošek hrambe enega kosa pa je s 0 = 6e. Najprej preverimo, kakšna bi bila optimalna velikost skladišča pri takih stroških. s 0 6 β 0 = 1 + = 1 + = 1.12 p 50 s r 2 K α 30000 M 0 = = ≈ 66.815 s 0 β 0 6.72 Ker je M 0 > n 0, zapišimo formulo za enotske stroške za primer, ko imamo v skladišču največ n 0 kosov. µ ¶ 2 K α + ( s 0 + p) n 02 ατ 0 2990e S 0 = + p − n 0 = 500e · τ 0 − 2000e + 2 ατ 0 2 τ 0 123 Ker iščemo dolžino intervala, kjer dosežemo minimalne stroške, poiščimo, kje ima odvod zgornjega izraza po τ 0 ničlo za τ 0 > 0. 2990e 0e = 500e − τ 02 r2990 τ 0 = ≈ 2.445 500 Optimalna dolžina cikla ob uporabi drugega skladišča je torej 2.445 meseca. Vstavimo v zgornjo formulo, da dobimo mesečne stroške. 2990e S 0 = 500e · 2.445 − 2000e + ≈ 445.404e 2.445 Ker so stroški nižji kot pri prvem skladišču, se trgovini izplača sprejeti ponudbo. Naloga 7.4. Imamo sledeče podatke (pri časovni enoti 1 dan). ν = 300 K = 240e λ = 400 s = 0.1e Pri teh podatkih izračunajmo še ³ ν ´ 1 α = ν 1 − = 300 · = 75. λ 4 (a) Ker primanjkljaj ni dovoljen, vzamemo p = ∞ in torej β = 1. Izračunajmo optimalno dolžino cikla τ∗, največjo zalogo M∗, trajanje proizvodnje t∗ ter število izdelanih mask q∗ v posameznem ciklu. s r 2 K β 480 τ∗ = = = 8 sα 7.5 s r 2 K α 36000 M∗ = = = 600 sβ 0.1 M∗ 600 t∗ = = = 6 λ − ν 100 q∗ = τ∗ ν = t∗ λ = 8 · 300 = 2400 Optimalna dolžina cikla je torej 8 dni, od tega proizvodnja teče 6 dni. V tem času proizvedejo 2400 mask, v skladišču pa mora biti prostora za 600 mask. (b) Sedaj imamo p = 0.4e in torej β = 1 + s/ p = 1.25. Izračunajmo optimalno dolžino cikla τ∗, največjo zalogo M∗, največji primanjkljaj m∗, trajanje proizvodnje t∗ ter število izdelanih mask q∗ v posameznem ciklu. s r 2 K β 600 τ∗ = = ≈ 8.944 sα 7.5 124 s r 2 K α 36000 M∗ = = ≈ 536.656 sβ 0.125 m∗ = τ∗ α − M∗ ≈ 670.820 − 536.656 ≈ 134.164 M∗ + m∗ 670.820 t∗ = ≈ = 6.708 λ − ν 100 q∗ = τ∗ ν ≈ 8.944 · 300 = 2683.282 V tem primeru je torej optimalna dolžina cikla 8.944 dni, od tega proizvodnja teče 6.708 dni. V tem času proizvedejo približno 2683 mask, v skladišču pa mora biti prostora za 537 mask. Največji primanjkljaj ne preseže 135 mask. 125 Literatura [1] S. Dasgupta, C.H. Papadimitriou in U.V. Vazirani, Algorithms. McGraw-Hill Education, 2006. 126 Document Outline Kazalo Predgovor Naloge Zahtevnost algoritmov Celoštevilsko linearno programiranje Teorija odlocanja Dinamicno programiranje Algoritmi na grafih CPM/PERT Upravljanje zalog Rešitve Zahtevnost algoritmov Celoštevilsko linearno programiranje Teorija odlocanja Dinamicno programiranje Algoritmi na grafih CPM/PERT Upravljanje zalog Literatura