SIJOITUSONGELMA
(KOHDISTUSONGELMA)
Sijoitusongelmassa on kaksi yhtä suurta joukkoa ja kummankin joukon jokaiselle alkiolle on haettava vastinalkio toisesta joukosta. On esimerkiksi jaettava k kpl tehtäviä k:n henkilön kesken s.e. kullekin tulee täsmälleen yksi (sopivin) tehtävä. Sijoitusongelma on
kuljetusongelman erikoistapaus. Siis sellainen kuljetusongelma, jossa tuottajia ja hankkijoita on yhtä paljon ja jossa kukin tuottaja vie optimiratkaisussa tavaraa ainoastaan täsmälleen yhdelle hankkijalle, joten optimiratkaisussa on alkioita n kpl (kuljetusongelmassahan määrä oli 2n-1 kun m=n). Mikäli tuottajien ja hankkijoiden määrä ei ole sama niin lisätään varjomuuttujia (dummy person), joille kustannuskerroin (cij) on nolla. Sijoitusongelma voidaan esittää LP-ongelmana allaolevassa muodossa (vertaa vastaavaan kuljetusongelman esitykseen):
Sijoitusongelma voitaisiin kuljetusongelman erikoistapauksena myös ratkaista sellaisena, mikä kuitenkin on turhan työlästä. On syytä muistaa, että tuolloin saadaan 2n-1 ratkaisua, joista n valitaan (loput n-1 alkiota ovat aina nollia). Sijoitusongelman ratkaisemiseksi on kehitetty ns. unkarilainen menetelmä, joka sisältää seuraavat vaiheet: 1° ongelmasta muodostetun nxn-matriisin kultakin riviltä vähennetään sen riviminimi, 2° sen jälkeen kultakin sarakkeelta vähennetään sarakeminimi, 3° yliviivataan kaikki 0-alkiot siten että viivoja on mahdollisimman vähän (aluksi eniten nollia sisältävät rivit/sarakkeet) 4° jos viivojen lukumäärä on suurempi tai yhtäsuuri kuin n niin mennään viimeiseen askeleeseen (6°), 5° etsitään pienin alkio (merk. L), jota ei ole peitetty viivalla javähennetään se kaikista
peittämättömien rivien alkioista ja lisätään kaikkien peitettyjen sarakkeiden alkioihin ja palataan askeleeseen 3°, 6° valitaan ratkaisuun tulevat nolla-alkiot siten että kultakin riviltä ja sarakkeelta tulee täsmälleen yksi alkio (huom! ratkaisu ei ole aina yksiselitteinen).
Esimerkki:
Kolme pientä porsasta A, B ja C joutuvat palaamaan turvallisuussyistä kotiin eri teitä. Vaihtoehtoisia reittejä on neljä ja optimaalinen tulos on sellainen, että possujen yhteenlaskettu kotimatka on mahdollisimman pieni. Ratkaisun kehityskulku on alla. Koska teitä on enemmän kuin porsaita niin on lisättävä yksi varjopotsi, X. Eri vaiheiden jälkeen päädytään sivun alalaidassa olevaan matriisiin, joka sisältää 9 nolla-alkiota (tummatut ruudut), joista valitaan 4 (mustat ruudut). Ratkaisu – A ≈ 2, B ≈ 4 ja C ≈ 1 (X ≈ 3) – on yksikäsitteinen.
Ratkaisu:
