Algoritmo De Transporte

Algoritmo de Transporte

Objetivo: Resolver el problema de transporte

Algoritmo:P 1. Determinar una soluci´on inicial b´asica factible (esquina noroeste o costo m´ınimo)

P 2. (Prueba de optimalidad)

Obtener una soluci´on dual resolviendo el sistema

ui + vj = cij 8xij b´asica

P 2.1 Si ui + vj − cij  0 8xij no b´asica, FIN. La soluci´on actual es ´optima

P 2.2 Si ui + vj − cij > 0 para alguna xij no b´asica, ir al Paso 3

P 3. Determinar la variable entrante (Cualquiera no b´asica tal que ui + vj − cij  0)

P 4. Determinar la variable saliente. Para ello encuentra el ciclo formado por la variable entrante

y variables b´asicas. Marcar alternadamente + y − las variables del ciclo empezando con la

variable entrante. Para determinar la cantidad de flujo que pasar´a por la variable entrante toma

el m´ın{fij} para las casillas (o arcos en la gr´afica) marcados con −, ´estos son los arcos por los

cuales es posible regresar flujo. Sea
el valor m´ınimo.

P 5 Sumar
a las variable marcadas con +, restar
a las marcadas con − e ir al Paso 2.

Aplica el algoritmo de transporte considerando que tenemos 3 origenes con oferta (300, 300, 100)

tres destino con demanda (200, 200, 300) con una matriz de costos

5 3 9

2 4 8

7 1 6

...