MÉTODO DE TRANSPORTE

Método de Asignación 

El modelo de asignación es un caso especial del modelo de transporte, en el que los recursos se asignan a las actividades en términos de uno a uno, haciendo notar que la matriz correspondiente debe ser cuadrada. Así entonces cada recurso debe asignarse, de modo único a una actividad particular o asignación.

Se tiene un costo Cij asociado con el recurso que es asignado, de modo que el objetivo es determinar en que forma deben realizarse todas las asignaciones para minimizar los costos totales.

Metodología:

Método Húngaro
Caso A: Minimización.

Revisar que todas las casillas tengan su costo ( beneficio) unitario correspondiente. Si alguna no lo tiene asignarlo en términos del tipo de matriz y problema considerado.

1. Balancear el modelo, es decir obtener m=n (obtener una matriz cuadrada)

En donde m= número de renglones.

En donde n= número de columnas.

Todo renglón o columna tendrá un costo (beneficio ) unitario de cero.

2. Para cada renglón escoger el MENOR VALOR y restarlo de todos los demás en el MISMO RENGLÓN.

3. Para cada columna escoger el MENOR VALOR y restarlo de todos los demás en la MISMA COLUMNA.

4.  Trazar el NO pasar al siguiente punto.

6. Seleccionar el menor valor no tachado de toda la matriz. El valor restarlo de todo elemento no tachado sumarlo a los elementos en la interacción de dos líneas.

7. Regresar al paso 4.

Caso B: Maximización.

l MÍNIMO número de líneas verticales y horizontales de forma tal que todos los ceros queden tachados.

5. Criterio de optimidad:

Metodología:

Seleccionar el MAYOR ELEMENTO de toda la matriz de beneficio. Este valor restarlo de todos los demás, los valores negativos que se obtengan representan los costos de oportunidad, lo que se deja de ganar o producir.

Para el caso de la solución del modelo considerar solo valores absolutos.

Con esta transformación se ha obtenido un modelo de minimización y por tanto resolverlo como tal.

Ejemplos:

Se necesita procesar 4 diferentes tareas para lo cual se cuenta con 4 máquinas. Por diferencias tecnológicas el desperdicio que se produce depende del tipo de tarea y la máquina en la cual se ejecuta, dada la matriz de Desperdicios expresada en pesos definir la asignación óptima.

MAQUINAS
TAREAS		1	2	3	4
	A	49	86	54	70
	B	45	79	66	81
	C	46	58	78	88
	D	44	38	66	69

¿El número de líneas es igual al orden de la matriz?

SI, el modelo es óptimo y por tanto hacer la asignación y traducir la solución.

La asignación se debe hacer en las casillas donde haya ceros cuidando que cada renglón y cada columna tenga una sola asignación.

Como se trata de Desperdicios, buscaremos MINIMIZARLOS.

Checamos que todas las casillas tengan su costo unitario, en este caso se cumple sin ningún problema.

Balanceamos la tabla M= renglones = 4 N= columnas= 4

Por lo que M=N, quedando balanceada.

MAQUINAS
TAREAS		1	2	3	4
	A	49	86	54	70
	B	45	79	66	81
	C	46	58	78	88
	D	44	38	66	69

Por renglón

Elegir el menor valor de renglón y restarlo a los demás. En este caso es son : 49,45,46,38.

Restamos ese valor a cada uno de los demás del renglón.

MAQUINAS
TAREAS		1	2	3	4
	A	49-49=0	86-49=37	54-49=5	70-49=21
	B	45-45=0	79-45=34	66-45=21	81-45=36
	C	46-46=0	58-46=12	78-46=32	88-46=42
	D	44-38=6	38-38=0	66-38=28	69-38=31

Formamos la nueva tabla

MAQUINAS
TAREAS		1	2	3	4
	A	0	37	5	21
	B	0	34	21	36
	C	0	12	32	42
	D	6	0	28	31

Por columna

Elegimos los menores valores de cada columna en este caso son : 0,0,5,21

Restamos esos valores a los demás números de las columnas

MAQUINAS
TAREAS		1	2	3	4
	A	0-0=0	37-0=37	5-5=0	21-21=0
	B	0-0=0	34-0=34	21-5=16	36-21=15
	C	0-0=0	12-0=12	32-5=27	42-21=21
	D	6-0=6	0-0=0	28-5=23	31-21=10

Obtenemos la nueva tabla:

MAQUINAS
TAREAS		1	2	3	4
	A	0	37	0	0
	B	0	34	16	15
	C	0	12	27	21
	D	6	0	23	10

Trazamos las líneas.

MAQUINAS
TAREAS		1	2	3	4
	A	0	37	0	0
	B	0	34	16	15
	C	0	12	27	21
	D	6	0	23	10

Contamos el número de líneas y observamos que son 3 líneas y el número de la matriz es de 4 por lo que NO ES ÓPTIMO.

Buscamos dentro de la tabla el menor valor no tachado en este caso es 12

Lo restamos a todos los demás, respetando los valores de los ya tachados y adicionándolos a los que están intersectados.

MAQUINAS
TAREAS		1	2	3	4
	A	0+12=12	37	0	0
	B	0	34-12=22	16-12=4	15-12=3
	C	0	12-12=0	27-12=15	21-12=9
	D	6+12=18	0	23	10

Nos queda:

MAQUINAS
TAREAS		1	2	3	4
	A	12	37	0	0
	B	0	22	4	3
	C	0	0	15	9
	D	18	0	23	10

Trazamos las líneas.

3 ≠ 4 NO ES ÓPTIMO

Volvemos a buscar el menor número de los no tachados.

MAQUINAS
TAREAS		1	2	3	4
	A	12+3=15	37+3=40	0	0
	B	0	22	4-3=1	3-3=0
	C	0	0	15-3=12	9-3=6
	D	18	0	23-3=20	10-3=7

En este caso es 3 y se lo restamos a los demás no tachados y respetamos a los tachados y se los sumamos a los intersectados. Y volvemos a trazar líneas.

MAQUINAS
TAREAS		1	2	3	4
	A	15	40	0	0
	B	0	22	1	0
	C	0	0	12	6
	D	18	0	20	7

4=4 ES ÓPTIMO

Ahora checamos las asignaciones, sean 1 a 1.

MAQUINAS
TAREAS		1	2	3	4
	A	15	40	0	0
	B	0	22	1	0
	C	0	0	12	6
	D	18	0	20	7

0 = se escogen

0= se deshabilitan

Se traduce la solución:

Realizar la tarea A en la máquina 3 con un costo de $54

Realizar la tarea B con la máquina 4 con un costo $81.

Realizar la tarea C en la máquina 1 con un costo $46.

Realizar la tarea D en la máquina 2 con un costo $38.

Costo total mínimo= $219

METODO DE TRANSPORTE

Método Voguel (MAV- Método de Aproximación de Voguel)

El Método de Aproximación de Vogel es una versión mejorada del Método del Costo Mínimo y el Método de la Esquina Noroeste que en general produce mejores soluciones básicas factibles de inicio, entendiendo por ello a soluciones básicas factibles que reportan un menor valor en la función objetivo (de minimización) de un Problema de Transporte balanceado (suma de la oferta = suma de la demanda).

• Los pasos que requiere la aplicación del Método de Aproximación de Vogel son los siguientes:

Paso 1: Determinar para cada fila (columna) una medida de penalización restando el elemento de costo unitario mínimo en la fila (columna) del elemento con costo unitario siguiente al mínimo de la misma fila (columna).

Paso 2: Identificar la fila o columna con la mayor penalización. Romper los empates (de existir) de forma arbitraria. Asignar todo lo posible a la variable que tenga el mínimo costo unitario de la fila o columna seleccionada. Ajusta la oferta y la demanda y tachar la fila o la columna ya satisfecha. Si se satisfacen una fila y una columna en forma simultánea, sólo se tacha uno de los dos y al que queda se le asigna oferta o demanda cero.

• Paso 3:
• 
  
• Si queda sin tachar exactamente una fila o columna con cero oferta o demanda, detenerse.
• 
  
• Si queda sin tachar una fila (columna) con oferta (demanda) positiva, determinar las variables básicas en la fila (columna) con el Método del Costo Mínimo. Detenerse.
• 
  

• Si todas las filas y columnas que no se tacharon tienen cero oferta y demanda (restante), determinar las variables básicas cero por el Método del Costo Mínimo. Detenerse.

• En cualquier otro caso, seguir en el Paso 1.

• Ejemplo:

• Consideremos nuevamente un problema de transporte balanceado que tiene 3 fuentes de oferta (silos) y 4 fuentes de demanda (molinos). Los valores numéricos en la esquina superior derecha de cada cuadro, en adelante  representan el costo unitario de transporte desde el silo i al molino j. Por ejemplo  es el costo unitario de transporte desde el silo 1 al molino 1.

• 

  
  

• Según lo descrito anteriormente el primer paso consiste en calcular el factor de penalización para cada fila y columna de la tabla que representa el problema de transporte anterior. Por ejemplo, en la fila 1 el mínimo costo es $2 y y el costo unitario siguiente al mínimo es $10. En consecuencia la penalización de dicha fila es $8 ($10-$2). Se replica el mismo cálculo para cada fila y columna de la tabla lo cual es trivial y reporta los siguientes resultados (se han marcado las penalizaciones de las respectivas filas y columnas con color naranjo para mayor claridad):

• 
  
  

• Como la fila 3 tiene la máxima penalización ($10) y la celda correspondiente a  tiene el costo unitario mínimo de esa fila, se asigna 5 unidades a  (más no es necesario aún cuando la capacidad del silo 3 lo permite dado que la demanda del molino 1 es de sólo 5 unidades). Con esto la columna 1 se debe tachar (lo hemos marcado con color amarillo) y se procede a calcular las nuevas penalizaciones como se aprecia a continuación:

• 
  
  
  

Ahora la penalización máxima es $9 ($11-$2) lo cual se alcanza en la fila 1. En consecuencia se asigna la máxima cantidad posible a la variable , con lo que se obtiene , y al mismo tiempo se satisfacen tanto la fila 1 como la columna 2. En forma arbitraria se tacha la columna 2 y se ajusta a cero la oferta en la fila 1.

Al continuar de la misma forma, ahora la fila 2 es la que produce la máxima penalización correspondiente a $11 ($20-$9), por tanto se asigna , con lo que se tacha la columna 3 y quedan 10 unidades en la fila 2. Sólo queda la columna 4 y tiene 15 unidades de oferta positiva. Al aplicar el Método del Costo Mínimo a esa columna, se asigna de forma sucesiva  (se recomienda verificar dichos resultados). Notar adicionalmente que hay otras soluciones posibles que dependen de cómo se rompen los empates.

El valor de la función objetivo asociado a esta solución factible inicial es Z=15(2)+0(11)+15(9)+10(20)+5(4)+5(18)=$475 que es similar a lo alcanzado por el Método del Costo Mínimo, no obstante, en general el Método de Aproximación de Vogel reporta mejor solución de inicio.

 

METODO DE TRANSPORTE

Costo Mínimo

Es un procedimiento mucho más eficaz porque permite obtener un costo menor asociado al transporte. Se asigna el valor más grande posible a la variable con menor costo unitario de la tabla. Se tacha el renglón o columna satisfecho, repitiéndose este último procedimiento hasta tachar todas las columnas y/o renglones.

Ejemplo:

La empresa generador de energía eléctrica RENACE dispone de cuatro plantas de generación para satisfacer la demanda diaria eléctrica en cuatro departamentos, Alta Verapaz, Baja Verapaz, Izabal y Petén. Las plantas 1,2,3 y 4 pueden satisfacer 80, 30, 60 y 45 millones de KW al día respectivamente. Las necesidades de los departamentos de Alta Verapaz, Baja Verapaz, Izabal y Petén son de 70, 40, 70 y 35 millones de Kw al día respectivamente. Los costos asociados al envío de suministro energético por cada millón de KW entre cada planta y cada departamento son los registrados en la siguiente tabla.

Paso No.1: Verificar la existencia de una matriz de costos.

Paso No.2: Confirmar que la suma de las disponibilidades sea igual a la suma de los requerimientos.

Si no fueran iguales la suma de los requerimientos y las disponibilidades debemos agregar una fila o columna con costos de transporte cero (agregando una fila /columna con el nombre de ficticia)

Paso No.3: Buscar el valor del costo mínimo renglón por renglón y anotarlo al finalizar la fila.

Paso No.4: Buscar el valor del costo mínimo columna por columna y anotarlo al finalizar la columna.

Paso No.5:

• Seleccionar el menor de todos los valores anotados al final de cada fila y columna (si hubiera dos o más iguales, seleccionamos aquella fila o columna en donde la disponibilidad y/o el requerimiento sean muy semejantes a fin de asignar la mayor cantidad posible a dicha casilla). 
• Asignar la oferta (disponibilidad / origen), la cantidad máxima posible al costo mínimo, de acuerdo con la demanda (requerimiento o destino) atendido.
• Anular las casillas del renglón o columna, que hubiesen sido satisfechas; lo que primero suceda. O todas las casillas del renglón y todas las columnas, si la oferta y la demanda hubiesen sido agotadas totalmente.

Paso No.6: Repetir los pasos 3, 4 y 5 hasta completar de satisfacer toda la matriz (disponibilidad y requerimiento).

Paso No.7: Seleccionar las casillas que tengan una asignación y vamos a multiplicarlas por el costo de transporte correspondiente, para con la sumatoria total encontrar el Costo Total de Transporte.

Costo Total de Transporte= (25x5) + (50x7) +(5x3) + (30x1) + (40x1) + (20x2) + (45x4)= Q750