ORM (TJT Y 30) kl. 99 5. DEMOT (viikko 8)

Operaatiotutkimuksen ja matematiikan perusteet

1. Neljä firmaa, A, B, C ja D ovat keskittäneet toimintansa Hauhoon, josta on keskimäärin yhtä pitkä matka jokaisen suomalaisen luo. Eräänä päivänä kukin firma saa neljä tilausta eri puolilta Suomea, pohjoisesta, etelästä, lännestä ja idästä. Koska mikään firmoista ei voi hoitaa useita kuljetuksia saman päivän aikana niin tilaukset päätetään jakaa. Optimoi kuljetuskustannusten yhteissummaa kun kunkin firman kuljetuskustannukset eri ilmansuuntiin on ilmoitettu kustannusmatriisissa alla.

2. Jyväskylän kaupungin upouudella poliisilaitoksella on eräänä aamuna vapaana 7 rikostutkimusryhmää. Samoin aamulla on 7 rikosta selvitettävänä. Alla olevassa taulukossa on annettu keskimääräinen aika (työtunteina), mikä kultakin ryhmältä kuluu vastaavan tyyppisen rikoksen selvittämiseen. Ratkaise kuinka poliisipäällikön tulisi määrätä rikokset eri tutkimusryhmille, jotta selvitysaikojen summa olisi mahdollisimman pieni.

 

3. Suositussa TV-ohjelmassa Napanolla on jokaisessa ohjelmassa neljä naista ja miestä. Nämä vastaavat viiteen monivalintakysymykseen, joiden vastaukset pisteytetään. Sitten jokaisen vastaajan kunkin kysymyksen pisteet vähennetään jokaisen vastakkaisen sukupuolen edustajan vastaavasta pistemäärästä ja erotuksien itseisarvot summataan henkilöittäin. Kun kaikki ovat vastanneet lähetetään aineisto savolaiselle älykone Uatamille, joka tulostaa alla olevan matriisin. Mitä suurempi luku, sitä paremmin yhteen soppii. Hae unkarilaista menetelmää käyttäen jokaiselle daamille soveliain kavaljeeri tai halutessasi päinvastoin.

4. Agentti Cooper on saanut ratkaistavakseen L.P. -ongelman, murhan, joka on tehty Twin Peaksin kaupungissa. Vietettyään paikallisessa kuppilassa munkilla ja kahvilla höystetyn iltapäivän hän näkee seuraavana yönä kofeiininhuuruisen unen, josta saa idean kuinka seuloa viiden epäillyn miehen joukosta murhaaja. Syyllinen olisi mitä ilmeisemmin murhatun neiti L.P.:n viidestä poikaystävästä. Ongelma oli siinä, että L.P.:llä oli suhde jokaiseen näistä viidestä. Ja lisäksi jokaisella miehellä on suhde neljään muuhun neitoseen! Tehtävänä on näin ollen selvittää kuka on kenenkin todellinen poika/tyttöystävä. Kriteerinä käytetään keskinäisten riitojen määrää. Siis mitä vähemmän keskinäisiä riitoja on niin sitä todennäköisempää on suhteen vakavuus. Tarkastelun lopussa tulee jokaisella epäillyistä murhaajakandidaateista olla ainoastaan yksi tyttöystävä ja riitojen yhteismäärä mahdollisimman pieni. Varmuudella todennettujen riitojen määrät näkyvät alla. Kuka herroista on mahdollisesti syyllinen?

………..……Donna………..Jennifer…….…Audrey………….Maddy

Ben…………….6………………5………………2………………1

Bob…………….9………………8………………7………………3

Leo……….……8………………5………………9………………4

Mr. Longhair…...7………………8………………8………………3

James…………..5………………5………………6………………4

Huom: tehtävät 1.-4. hyvitetään 1. välikokeessa, tehtävät 5.-7. seuraavassa välikokeessa!

5. a) Eurolähettiläs Erkki Tarpeellinen tekee Brysselistä kiertomatkan tärkeisiin europääkau-punkeihin: Amsterdamiin, Bonniin, Lontooseen, Luxembourgiin ja Pariisiin. Kun kartaston taulukossa ei ole Bonnia, hän käyttää sen tilalla Kölniä. Kaupunkien väliset etäisyydet ovat seuraavat:

……………………..A………B………K………Lo………Lu………P

Amsterdam……….…-…..…210…….260…..…550…..…390…….510

Brysseli……….……210……..-…...…220……..390…..…220….…300

Köln………….……260……220………-…...…610…..…200….…490

Lontoo…………..…550……390…….610………-……….600……450

Luxembourg……..…390……220….…200…..…600………-…..…340

Pariisi………………510……300….…490…..…450….….340……..-

Etsi branch-and bound -algoritmilla minimireitti.

b) Erkillä on äkilinen rahapula ja hän ajattelee, että kilometrikorvauksia olisi mukava saada mahdollisimman paljon ts. että ajettu matka olisi mahdollisimman pitkä, Mieti (ei tarvitse laskea), kuinka tämä tehtävä voitaisiin ratkaista. Oletetaan kuitenkin, että Erkki ei ajele mutkille vaan kahden kaupungin väli taittuu taulukon ilmoittamassa kilometrimäärässä.

6. Muotoile oheinen "Mikki Hiiren valinta" (kuva vain paperiversiossa) sijoitusongelmaksi itse valitsemillasi parametereilla ja ratkaise tehtävä sitten unkarilaisella menetelmällä.

7. Ratkaise tehtävä 1 kuljetusongelmana.

Demot viikolla 8 ovat Ti 12-14 (MaD 355) ja To 10-12 & 12-14 (L 209)