Kohdistustehtävän ratkaiseminen unkarilaisella algoritmilla

Abstract

Tämän kandidaatintyön luettuaan lukija tietää, mikä on unkarilainen algoritmi, miten se toimii ja miten sitä voidaan hyödyntää kohdistustehtävien ratkaisemiseen. Työn luettuaan lukija tietää, mikä on kohdistustehtävä, osaa soveltaa unkarilaista algoritmia kohdistustehtävän ratkaisemiseen ja ymmärtää algoritmin matemaattisen taustan.

Operaatiotutkimus on matematiikan osa-alue, jossa mallinnetaan ja ratkaistaan erilaisia käytännön optimointiongelmia. Tässä työssä tutustutaan kohdistustehtävään (engl. assignment problem), joka on yksi operaatiotutkimuksen osa-alueista. Perinteisessä kohdistustehtävässä työtehtäviä jaetaan työntekijöiden kesken niin, että tehtävistä syntyvät kokonaiskustannukset olisivat mahdollisimman pienet tai tulot olisivat mahdollisimman suuret. Työssä käydään läpi kohdistustehtävään liittyvää terminologiaa ja esitetään kohdistustehtävän matemaattinen malli ja rajoitteet. Työssä näytetään myös, miten kohdistustehtävissä esiintyviä erilaisia rajoitteita voidaan mallintaa matemaattisesti.

Kohdistustehtävän lisäksi työssä tutustutaan unkarilaiseen algoritmiin, jonka avulla voidaan ratkaista kohdistustehtäviä. Algoritmi esitellään työssä vuokaavion avulla. Vuokaavion jokainen vaihe on numeroitu, ja jokaisen vaiheen matemaattinen tausta selitetään lukijalle. Vuokaavion ymmärtämisen helpottamiseksi työssä käydään läpi esimerkkejä, joiden avulla vuokaavion eri vaiheet konkretisoituvat. Työn lopuksi esitellään algoritmille muunnelmia, jotta unkarilaista algoritmia voisi käyttää hiukan sovellettuihin kohdistustehtäviin.

Aiheen käsittely alkaa luvussa 2, jossa esitellään kohdistustehtävä ja käydään läpi, miten kohdistustehtävä voidaan mallintaa matemaattisesti. Tämän jälkeen luvussa 3 esitellään unkarilainen algoritmi vuokaavion avulla, sekä havainnollistetaan sitä esimerkeillä luvussa 4. Lopuksi käydään läpi algoritmin matemaattinen tausta luvussa 5, sekä luvussa 6 esitetään pari kohdistusteh