Modelo De Transporte

UNIDAD IV: TRANSPORTE Y ASIGNACIÓN.

Esta unidad trata dos aplicaciones especialmente importantes de la PL: los problemas de transporte y de asignación. En su formulación inicial, el problema de transporte estudia la distribución de un producto homogéneo desde un conjunto de fábricas a un conjunto de almacenes, de modo que se satisfagan las demandas de los almacenes y no se superen las disponibilidades de las fábricas, con costo mínimo. El modelo de transporte tiene notable interés por sus importantes aplicaciones que, como se verá en algún ejercicio, no se restringe únicamente a la distribución de mercancías; puede aplicarse, por ejemplo, a problemas de planificación de la producción e inventarios. Su procedimiento específico de solución, llamado algoritmo de transporte, consta de dos fases y es rápido y eficiente. La segunda parte de la unidad se dedica al problema de asignación. Este modelo permite determinar la asignación óptima de individuos o máquinas a tareas, con costo mínimo, y es un caso particular del de transporte; pero, aunque puede resolverse con el algoritmo de transporte, resulta más eficiente su resolución mediante un algoritmo específico conocido como método húngaro.

4.1 Definición del problema de transporte.

El problema de transporte puede describirse de modo genérico en los términos siguientes. Se tienen “m” orígenes (fábricas, almacenes) con mercancía disponible para su traslado a “n” destinos (centros de distribución) los cuales están requiriendo dicha mercancía. La cantidad disponible (oferta) en el origen “i” es ai y la cantidad requerida (demanda) en el destino “j” es bj. El costo unitario de transporte del origen “i” al destino “j” es Cij. El propósito es decidir la cantidad Xij que cada origen “i” habrá de enviar a cada destino “j” a fin de minimizar el costo total de transporte, Z.

Suponiendo que el modelo esté balanceado (o en equilibrio), lo cual significa que la oferta total sea igual a la demanda total, esto es: i = i , entonces el modelo se expresa matemáticamente del modo siguiente:

Minimizar Z = C11 X11 + C12 X12 + … + Cmn Xmn ,

Sujeto a: ij = ai , para i = 1, 2, …, m

ij = bj , para j = 1, 2, …, n

Xij ≥ 0 , para i = 1, 2, …, m

j = 1, 2, …, n.

Para ejemplificar, supongamos que tenemos 3 orígenes y 4 destinos cuyos costos de transporte (unitarios), así como sus respectivas ofertas y demandas se muestran en la tabla siguiente:

O D E S T I N O

R 1 2 3 4 OFERTA:

I 1 5 8 4 7 240

G 2 10 6 9 11 160

E 3 8 3 10 6

200

N DEMANDA: 100 150 250 100

Cij ($/unidad)

¿Qué cantidad (unidades de producto) habrá de enviar cada origen a cada destino, a fin de satisfacer la demanda y a costo mínimo?

El modelo matemático correspondiente es:

Minimizar Z = 5X11 + 8 X12 + 4 X13 + 7 X14 + 10 X21 + 6 X22 + 9 X23 + 11 X24 + 8 X31

+3 X32 + + 10 X33 + 6 X34 ,

Sujeto a: X11 + X12 + X13 + X14 = 240 Restricciones

X21 + X22 + X23 + X24 = 160 de

X31 + X32 + X33 + X34 = 200 oferta

X11 + X21 + X31 = 100

X12 + X22 + X32 = 150 Restricciones

X13 + X23 + X33 = 250 de

X14 + X24 + X34 = 100 demanda

X11, X12, X13, …, X34 ≥ 0 Condición de no negatividad

Observamos en este problema específico, así como en cualquier otro problema de transporte, los siguientes 2 elementos que le confieren un carácter especial:

1) Todas las restricciones técnicas, tanto de oferta como de demanda, son igualdades.

2) Todos los coeficientes de las variables de decisión que aparecen en cada restricción técnica, son iguales a 1.

Son estas 2 características las que permiten resolver este tipo de problemas mediante un algoritmo más eficiente que el método simplex. Intentar aplicar el método simplex a éstos modelos de transporte tiene sus inconvenientes y complicaciones. Veamos: el problema específico que hemos presentado contiene 3 orígenes y 4 destinos, que dan lugar a –relativamente- poca información; diríamos que se trata de un problema sencillo. Sin embargo, al observar el modelo matemático vemos que contiene 7 restricciones técnicas (3 de oferta y 4 de demanda) y 12 variables de decisión más las 7 variables artificiales que tendríamos que agregar para formar la matriz identidad I7 . En general, vemos que para un problema de transporte de “m” orígenes y “n” destinos, el modelo matemático correspondiente constará de ( m + n ) restricciones técnicas (“m” de oferta y “n” de demanda) y de “m n” variables de decisión, además de (m + n ) variables artificiales. Este sencillo análisis pone en evidencia lo inconveniente que resulta el método simplex para tratar los problemas de transporte.

El algoritmo de transporte resulta ser más sencillo y más eficiente que el simplex y consta esencialmente de dos etapas:

1) Obtención de la solución inicial básica factible.

2) Análisis de la solución, para investigar si es óptima; en caso de no ser óptima habrá que mejorarla hasta optimizarla.

MÉTODOS PARA OBTENER LA SOLUCIÓN INICIAL.

Consideraremos dos métodos:

1) Método de la esquina noroeste.

2) Método de Vogel.

4.2 El método de la esquina noroeste.

Como su nombre lo sugiere, se trata de asignar (colocar un envío) en la esquina NW tanto como sea posible según lo permita la combinación de oferta y demanda correspondiente a dicha esquina, eliminando el vector (renglón columna) que corresponda al origen que haya quedado sin mercancía, o bien al destino que haya sido satisfecho. Enseguida se asigna en la celda que ocupe la posición NW después de la cancelación del vector aludido. Se continúa de este modo hasta que todos los destinos queden satisfechos ( y consecuentemente los orígenes quedarán vacíos).

A continuación se muestra la solución inicial obtenida por el método de la esquina NW, aplicado al problema que hemos considerado como ejemplo.

O D E S T I N O

R

I 100 140

G 10 150

E 100 100

N

Siendo su costo total:

CT = 100(5) + 140 (8) + 10 (6) + 150 (9) + 100 (10) + 100 (6) = $4630

4.3 El método MODI.

El método MODI (distribución modificada, también denominado u-v) es un procedimiento

...