Algoritmos

Algoritmo de transporte


Consideremos el siguiente ejemplo, para describir el algoritmo de transporte, este algoritmo se aplica a una solución básica-factible obtenida por el método de laesquina noroccidental o por el método de vogel, su objetivo es verificar si la solución es la óptima y si no es, el mismo algoritmo optimiza la solución.

Tres fabricas A,B y C disponen de ciertascantidades de un producto, esas cantidades respectivamente son: 100, 120 y 120 toneladas. El producto se entrega a cinco almacenes 1,2,3,4, y 5 que deben recibir respectivamente 40,50,70,90 y 90 toneladasdel producto. El costo por transporte de una cierta unidad de producto esta dado por la siguiente tabla. Obtener una primera solución básica-factible por el método de la esquina noroccidental.[pic]
Figura 6.39 MATRIZ DE COSTOS UNITARIOS
[pic]

Figura 6.40 SOLUCIÓN INICIAL BÁSICA FACTIBLE OBTENIDA POR EL METODO DE LA ESQUINA NOROCCIDENTAL

Para obtener la solución óptima esnecesario aplicar el algoritmo de transporte, siguiendo los siguientes pasos:

Paso 1:
Se colocan en un cuadro por separado los costos por unidad que corresponden a las casillas ocupadas por la matriz(Xij)1.
(Cij)1


Paso 2:
Ahora se trata de llenar las casillas vacías de (Cij)1 para ello:

a) Se selecciona el menor elemento que figure en la tabla (Cij)1 en este caso es el 1, se coloca enel margen derecho de la tabla, en cualquier fila, de preferencia en la primera fila.



Tabla de costos (Cij)1


| |4|
| |1|
| |2 |
| |...