Problema de asignación

Este es un problema particular de programación lineal y consiste en asignar \(m\) trabajadores para realizar \(n\) tareas. La asignación de cada trabajador a una de las tareas tiene un costo \(c_{ij}\). El objetivo es determinar cúal trabajador asignar a qué tarea (\(x_{i,j}=1\)) de tal manera que se minimice el costo total (\(Z\)).

Las variables del problema son las siguientes:

El problema en forma simbólica se puede representar así:

Ejemplo

Se tienen tres trabajadores 1, 2 y 3 para realizar las tareas 1, 2 y 3. Cada asignación de un trabajador a una tarea tiene un costo y corresponde al mostrado en la siguiente matriz.

¿Qué trabajador se debe asignar a qué tarea para minimizar el costo? ¿Cuál es el costo de la asignación?

Solución

El paquete lpSolve de R nos permite solucionar este tipo de problemas de una forma sencilla. Abajo las instrucciones para hacerlo.

# To load the lpSolve package
library(lpSolve)

# Defining costs
costs <- matrix(c(15, 10,  9,
                   9, 15, 10,
                  10, 12,  8), nrow=3, byrow=TRUE)

# Print assignment costs matrix
costs
##      [,1] [,2] [,3]
## [1,]   15   10    9
## [2,]    9   15   10
## [3,]   10   12    8
# Final value (z)
lp.assign(costs)
## Success: the objective function is 27
# Variables final values
lp.assign(costs)$solution
##      [,1] [,2] [,3]
## [1,]    0    1    0
## [2,]    1    0    0
## [3,]    0    0    1

De las salidas anteriores vemos que la asignación debería ser:

El costo de esta asignación sería de 27 unidades monetarias.