Tilordningsproblemet er et klassisk problem indenfor lineær optimering. Hvis du f.eks. Har n jobs som på m-maskiner så vil du tildele jobs til maskiner på en optimal måde. Restriktionen i dette eksempel er, at hver maskine kun kan udføre ét job. Alle jobs skal planlægges, dvs. tildeles en maskine.

Problemet kan angives i en matematisk model. Nedenfor er problemet angivet for et tilfælde, hvor der er 3 jobs og 3 maskiner. Omkostningerne ved at producere job 1 på maskine 1 er 1 USD, men 2 USD når job 1 produceres på maskine 2. Job 2 koster 2 USD på maskine 1 og 3 USD på maskine 2. Job 3 koster 5 USD på maskine 1 og 1 USD på maskine 2. Maskine 3 kan udføre job 1 for henholdsvis 2 USD og job 2 for 3 USD.

Den matematiske model for tilordningsproblemet ser således ud som følger:

Vi kan modellere og løse dette problem med lpSolve-pakken i R, en pakke til lineær programmering og lineær optimering (til kontinuerlige problemer og helttalsproblemer). Funktionen lp.assign kan udføre jobbet:

library(lpSolve)

# forbered omkostningsmatrixen
cost.mat <- rbind(c(1,2,3),
                     c(2,3,3),
                     c(5,1,3))

# modeller og løs tilordningsproblemet med lp.assign
solution <- lp.assign(cost.mat=cost.mat,
                      direction="min")

lp.assign er en funktion som specifikt er beregnet til at løse tilordningsproblemet. Opgaveproblemet, per definition, er et problem hvor alle beslutningsvariabler er heltalsvariabler. Vi behøver derfor ikke specifikt at fortælle lp.assign at beslutningsvariablerne skal betragtes som heltalsvariabler.

Lad os se de minimale omkostninger ved at udgive resultatet:

solution

## Success: the objective function is 5

Lad os se den minimale produktionsplan ved at udgive løsningen:

solution$solution

##      [,1] [,2] [,3]
## [1,]    1    0    0
## [2,]    0    0    1
## [3,]    0    1    0

Linnart Felkl

Industriingeniør som gerne beskæftiger sig med optimering, simulation og matematisk modellering i R, SQL, VBA og Python