problemas de transporte y asignación

Cátedra: Producción I
Capítulo 7. Programación lineal. Problemas de transporte y asignación

PROBLEMAS DE TRANSPORTE Y ASIGNACION.
Dos tipos particularmente importantes (y relacionados) de problemas de
programación lineal, son el problema de transporte y el problema de asignación.
El problema de transporte recibe este nombre debido a que muchas de sus
aplicaciones involucran determinar lamanera óptima de transportar bienes. Sin embargo,
algunas de aplicaciones importantes (como la programación de la producción), de hecho no
tienen nada que ver con el transporte.
El segundo tipo, llamado problema de asignación, incluye aplicaciones tales como
asignar personas a tareas. Aunque sus aplicaciones parecen diferir del problema de
transporte, se vera que este problema es un acasoespecial del problema de transporte.
1. Modelo del problema de transporte.
El problema general de transporte se refiere a la distribución de cualquier bien desde
cualquier grupo de centros de suministro, llamados orígenes, a cualquier grupo de centros
de recepción, llamados destinos, de tal manera que se minimicen los costos totales de
distribución. La terminología utilizada en estos problemasse resume en la siguiente tabla:
Problema general
Ejemplo
Unidades de un bien
Cargas de latas de tomate
m orígenes
Cuatro enlatadoras
n destinos
Cuatro almacenes
si recursos en el origen i
Producción de la enlatadora i
Demanda dj en el destino j
Asignación al almacén j
Costo cij por unidad distribuida desde el Costo de envío por carga desde la enlatadora
origen i al destino j
i alalmacén j
Como se indico en la tabla anterior, cada origen tiene cierto suministro de unidades
que distribuir a los destinos, y cada destino tiene cierta demanda de unidades que deben
recibirse de los orígenes. Las suposiciones sobre suministros y demandas son las siguientes:
• Suposición de requerimientos: Cada origen tiene un suministro fijo de unidades y el
suministro completo debedistribuirse a los destinos. (si es el número de unidades que
suministra el origen i). De igual manera, el destino tiene una demanda fija de unidades,
y debe satisfacerse desde los orígenes, (dj es el numero de unidades recibidas por el
destino j). Un problema de transporte tiene soluciones factibles si y solo si:
m
n
∑ si = ∑ d j
i =1
j =1
Esta suposición significa que es necesario un balanceentre el suministro total de
todos los orígenes y la demanda total de todos los destinos. Algunos problemas reales no se
ajustan por completo al problema de transporte porque violan la suposición de
requerimientos. Sin embargo, es posible reformular el problema de manera que se ajuste al
modelo con la introducción de un destino ficticio o un origen ficticio para que se haga cargo
de la holguraentre las cantidades reales distribuidas.
• Suposición de costo: el costo de distribuir unidades de un origen a un destino dado es
directamente proporcional al número de unidades distribuidas. Por lo tanto este costo es
justo el costo unitario de distribución multiplicado por el número de unidades

27

Cátedra: Producción I
Capítulo 7. Programación lineal. Problemas de transporte yasignación

distribuidas. (el costo unitario del origen i al destino j se denota por cij). En resumen la
suposición de costo nos dice que: la función del costo de transporte debe ser una
función lineal del número de unidades transportadas y que el costo de transporte por
unidad no varía con la cantidad transportada.
Los únicos datos necesarios para un problema de transporte son suministros,demandas y costos unitarios. Estos son los parámetros del modelo. Todos estos parámetros
se pueden resumir en la siguiente tabla de parámetros.
Costo por unidad distribuida
Destino
Recursos
1
2
...
n
c11
c12
...
c1n
s1
1
Origen
...
c21
c22
s2
c2n
2
....
...
...
....
....
...
...
cm1
cm2
sm
cmn
m
Demanda
d2
...
dn
d1
Entonces cualquier problema (ya sea que...