Lineaarisen kokonaislukuoptimoinnin käyttö lukujärjestys- ja työvuorolistaongelmien ratkaisemiseen
Pakarinen, Matti Samuli (2018)
2018
Teknis-luonnontieteellinen
Teknis-luonnontieteellinen tiedekunta - Faculty of Natural Sciences
This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited.
Hyväksymispäivämäärä
2018-04-04
Julkaisun pysyvä osoite on
https://urn.fi/URN:NBN:fi:tty-201803231422
https://urn.fi/URN:NBN:fi:tty-201803231422
Tiivistelmä
Tässä diplomityössä tutkitaan lineaarisen kokonaislukuoptimoinnin käyttöä aikataulutusongelmien ratkaisemisessa. Tavoitteena on vertailla erilaisia ratkaisumetodeja keskenään. Ongelmat ratkaistaan käyttämällä numeerisia kokonaislukuratkaisijoita, kuten Matlabin intlinprog. Lineaarisen optimoinnin perusteiden lisäksi teoriaosiossa tehdään kirjallisuuskatsaus numeeristen ratkaisijoiden matemaattisen pohjaan.
Lineaarista kokonaislukuoptimointia käytetään sellaisten optimointiongelmien ratkaisemiseen, joissa muuttujien arvot ovat diskreettejä tai kokonaislukuja. Muuttujia, joiden arvot on rajoitettu kokonaislukuihin antavat vastauksen esimerkiksi kysymyksiin siitä, kuinka monta kappaletta tilataan tuotetta x, kuinka monta työntekijää kohdennetaan projektin osa-alueeseen x, ja niin edelleen.
Erityistapauksena lineaarisesta kokonaislukuoptimoinnista on lineaarinen binäärilukuoptimointi (BIP). Optimointiongelmassa, joka on tyypistään BIP, muuttujat saavat vain arvoja 0 tai 1. Nämä arvot kuvaavat kyllä-ei luonteisia päätöksiä, kuten ostetaanko, palkataanko tai sijoitetaanko. Binäärilukuoptimointi on tämän diplomityön kannalta oleellinen, sillä työssä esiintyvät ongelmat formuloidaan ja ratkaistaan BIP-ongelmina.
Aikataulutusongelmien ratkaiseminen käyttäen lineaarista kokonaislukuoptimointia edellyttää, että voimme formuloida nämä ongelmat kokonaislukuoptimointi ongelmiksi ja ratkaista ne kohtuullisessa ajassa. Keskitymme kahteen eri aikataulutusongelmaan. Ensimmäinen ongelma on luoda optimaalisia työvuorolistoja yhtiön työntekijöille ja toinen ongelma on luoda optimaalisia lukujärjestyksiä yliopiston opiskelijoille. Nämä ongelmat voidaan formuloida IP-ongelmiksi ja simulaatiosta saatujen tulosten perusteella huomataan, että instanssit saadaan ratkaistua nopeasti tai kohtuullisessa ajassa. Eri ratkaisijoiden välillä löydetään myös eroja niiden kyvyssä ja tehokkuudessa ratkaista testattuja instansseja.
Lineaarista kokonaislukuoptimointia käytetään sellaisten optimointiongelmien ratkaisemiseen, joissa muuttujien arvot ovat diskreettejä tai kokonaislukuja. Muuttujia, joiden arvot on rajoitettu kokonaislukuihin antavat vastauksen esimerkiksi kysymyksiin siitä, kuinka monta kappaletta tilataan tuotetta x, kuinka monta työntekijää kohdennetaan projektin osa-alueeseen x, ja niin edelleen.
Erityistapauksena lineaarisesta kokonaislukuoptimoinnista on lineaarinen binäärilukuoptimointi (BIP). Optimointiongelmassa, joka on tyypistään BIP, muuttujat saavat vain arvoja 0 tai 1. Nämä arvot kuvaavat kyllä-ei luonteisia päätöksiä, kuten ostetaanko, palkataanko tai sijoitetaanko. Binäärilukuoptimointi on tämän diplomityön kannalta oleellinen, sillä työssä esiintyvät ongelmat formuloidaan ja ratkaistaan BIP-ongelmina.
Aikataulutusongelmien ratkaiseminen käyttäen lineaarista kokonaislukuoptimointia edellyttää, että voimme formuloida nämä ongelmat kokonaislukuoptimointi ongelmiksi ja ratkaista ne kohtuullisessa ajassa. Keskitymme kahteen eri aikataulutusongelmaan. Ensimmäinen ongelma on luoda optimaalisia työvuorolistoja yhtiön työntekijöille ja toinen ongelma on luoda optimaalisia lukujärjestyksiä yliopiston opiskelijoille. Nämä ongelmat voidaan formuloida IP-ongelmiksi ja simulaatiosta saatujen tulosten perusteella huomataan, että instanssit saadaan ratkaistua nopeasti tai kohtuullisessa ajassa. Eri ratkaisijoiden välillä löydetään myös eroja niiden kyvyssä ja tehokkuudessa ratkaista testattuja instansseja.