Problemas de transporte y asignación

Existen dos tipos de problemas sumamente relevantes en la investigación de operaciones (relacionados de manera directa con la programación lineal), para los cuales se han desarrollado algoritmos específicos de resolución, dado que suelen aparecer en muchas aplicaciones prácticas. Se trata de los problemas de “transporte” y “asignación”.

Problemas de transporte con R

Para resolver los problemas de transporte, usualmente se emplea la función lp.transport del paquete lpSolve. Los argumentos de esta función son, en este orden:

• cost.mat: Matriz de costos en la que el elemento \(ij\) representa el costo de transportar una unidad del origen \(i\) al destino \(j\).
• direction: “min” (por defecto) o “max”, según se trate de minimizar un coste o maximizar un beneficio.
• row.signs: Vector de desigualdades de las restricciones de filas.
• row.rhs: Vector de coeficientes de los lados derechos de las restricciones de filas.
• col. signs: Vector de desigualdades de las restricciones de columnas.
• col.rhs: Vector de coeficientes de los lados derechos de las restricciones de columnas.
• integers: vector que representa qué variables deben ser enteras. Si no hay ninguna se debe escribir NULL.

Ejemplo I

Considérense tres centros de producción \(A\), \(B\) y \(C\) con una capacidad de producción diaria de \(50\), \(20\) y \(40\) toneladas de carbón, respectivamente. Se quiere programar el transporte diario a cuatro centros de consumo \(D_{1}\), \(D_{2}\), \(D_{3}\) y \(D_{4}\) cuyas necesidades diarias son \(35\), \(35\), \(22\) y \(18\) toneladas respectivamente. Se conoce la matriz de costes unitarios desde cada origen a cada punto de destino:

En este contexto, el objetivo es organizar el transporte que haga mínimo el coste diario; es decir, determinar las cantidades diarias que hay que trasladar de cada centro de producción a cada centro de consumo.

# install.packages('lpSolve')
library(lpSolve)

# Matriz de costos (transportar una unidad del origen al destino):
# - Matriz de 3 filas.
# - Matriz ordenada por filas.
matriz.costos <- matrix(c(10, 30, 15, 8,
                          12, 25, 5, 35,
                          20, 7, 14, 22), nrow = 3, byrow = T)
matriz.costos

     [,1] [,2] [,3] [,4]
[1,]   10   30   15    8
[2,]   12   25    5   35
[3,]   20    7   14   22

# Vector de desigualdades de las restricciones de fila:
# - Restricciones de los centros de producción A, B y C.
# - Repetir el signo `=` tres veces ().
vector.desigualdades.fila <- c(rep("=", 3))
vector.desigualdades.fila

[1] "=" "=" "="

# Vector de coeficientes de las restricciones de fila (lado derecho).
# - Restricciones de los centros de producción A, B y C.
# - Capacidad de producción diaria.
Vector.coeficientes.fila <- c(50, 20, 40)
Vector.coeficientes.fila

[1] 50 20 40

# Vector de desigualdades  de las restricciones de columna.
# - Restricciones de los centros de consumo D1, D2, D3 y D4.
# - Repetir el signo `=` cuatro veces ().
Vector.desigualdades.columna <- c(rep("=", 4))
Vector.desigualdades.columna

[1] "=" "=" "=" "="

# Vector de coeficientes  de las restricciones de columna (lado derecho).
# - Restricciones de los centros de consumo D1, D2, D3 y D4.
# - Necesidad de consumo diaria.
Vector.coeficientes.columna <- c(35, 35, 22, 18)
Vector.coeficientes.columna

[1] 35 35 22 18

# Se ejecuta la función para maximizar la función objetivo:
# - Se establece `direction` en `min` para minimizar los costos.
# - Se establece `integers` en `NULL` al no tener variables enteras.
lp.transport(cost.mat = matriz.costos, 
             direction = "min",
             row.signs = vector.desigualdades.fila,
             row.rhs = Vector.coeficientes.fila,
             col.signs = Vector.desigualdades.columna,
             col.rhs = Vector.coeficientes.columna,
             integers = NULL) 

Success: the objective function is 897 

# Método para conocer los valores de las variables en el óptimo igual a 897:
lp.transport(cost.mat = matriz.costos, 
             direction = "min",
             row.signs = vector.desigualdades.fila,
             row.rhs = Vector.coeficientes.fila,
             col.signs = Vector.desigualdades.columna,
             col.rhs = Vector.coeficientes.columna,
             integers = NULL)$solution

     [,1] [,2] [,3] [,4]
[1,]   32    0    0   18
[2,]    0    0   20    0
[3,]    3   35    2    0

La salida se interpreta del siguiente modo: hay que llevar \(32\) toneladas de carbón del centro de producción \(A\) a \(D_{1}\), \(18\) toneladas de \(A\) a \(D_{4}\), \(20\) toneladas de \(B\) a \(D_{3}\), \(3\) toneladas de \(C\) a \(D_{1}\), \(35\) toneladas de \(C\) a \(D_{2}\) y \(2\) toneladas de \(C\) a \(D_{3}\). Finalmente, el óptimo de la función objetivo es \(897\).

Problemas de asignación con R

Para resolver los problemas de asignación, usualmente se emplea la función lp.assign del paquete lpSolve. Los argumentos de esta función son, en este orden:

• cost.mat: Matriz de costos en la que el elemento \(ij\) representa el costo o beneficio de asignar el origen \(i\) al destino \(j\).
• direction: “min” (por defecto) o “max”, según se trate de minimizar un coste o maximizar un beneficio.

Ejemplo I

Supongamos que la tabla que se presenta a continuación representa lo siguiente: \(A\), \(B\), \(C\) y \(D\) son cuatro abogados de un cierto bufete, mientras que \(M_{1}\), \(M_{2}\), \(M_{3}\) y \(M_{4}\) son \(4\) casos a resolver.

Los valores de la siguiente tabla son los tiempos estimados en horas que emplearían los distintos abogados con cada uno de los casos:

En este contexto, el objetivo es determinar la forma óptima de asignar los casos a los abogados de manera que cada uno aborde un caso diferente y que el tiempo total empleado sea mínimo.

# install.packages('lpSolve')
library(lpSolve)

# Matriz de costos (tiempos estimados en horas de cada uno de los casos):
# - Matriz de 4 filas.
# - Matriz ordenada por filas.
matriz.costos <- matrix(c(34, 10, 15, 28,
                          16, 15, 22, 12,
                          10, 25, 13, 20, 
                          30, 19, 27, 31), nrow = 4, byrow = T)
matriz.costos

     [,1] [,2] [,3] [,4]
[1,]   34   10   15   28
[2,]   16   15   22   12
[3,]   10   25   13   20
[4,]   30   19   27   31

# Se ejecuta la función para maximizar la función objetivo:
# - Se establece `direction` en `min` para minimizar los costos.
lp.assign(cost.mat = matriz.costos, 
          direction = "min")

Success: the objective function is 56 

# Método para conocer los valores de las variables en el óptimo igual a 56:
lp.assign(cost.mat = matriz.costos, 
          direction = "min")$solution

     [,1] [,2] [,3] [,4]
[1,]    0    0    1    0
[2,]    0    0    0    1
[3,]    1    0    0    0
[4,]    0    1    0    0

Por lo tanto, el abogado \(A\) será asignado al caso \(M_{3}\), el abogado \(B\) al caso \(M_{4}\), el abogado \(C\) al caso \(M_{1}\) y el abogado \(D\) al caso \(M_{2}\).

Conclusión

Al ser R un software de programación estadística sumamente versatil, existe una gran variedad de opciones alternativas, entre las que destacan:

• Utilizar la función solveLP del paquete linprog.
• Cargar el paquete glpk que proporciona una interface para el programa GLPK (GNU Linear Programming Package), que es un software libre para resolver problemas de programación lineal y de programación lineal entera mixta de gran escala, así como problemas relacionados.
• Utilizar el paquete rcdd para resolver problemas PL con aritmética exacta mediante la función lpcdd.

Referencias

• Sallan, J. M., Lordan, O., & Fernandez, V. (2015). Modeling and solving linear programming with R. OmniaScience.
• Murthy, G. S. R. (2015). Applications of operations research and management science: Case Studies. International Series in Operations Research and Management Science. Springer New York.
• Murthy, G. S. R. (2015). Case Studies in Operations Research: Applications of Optimal Decision Making. International Series in Operations Research and Management Science. Springer New York.