Problemas de Transporte
 
 
D1
D2
D3
D4
Oferta
S1
50
75
30
45
12
S2
65
80
40
60
17
S3
40
70
50
55
11
Demanda
10
10
10
10
 
Problema de Transporte: Matriz de costos unitarios
 

Algoritmo Simplex de Transporte.

1. Determinar una solución inicial factible (Método de la esquina Noroeste, Método deVogel)
2. Encontrar los valores actuales de Cij-Zij para cada variable que no está en la base (no-básica) y seleccione aquella con el valor más negativo de Cij-Zij como la variable entrante a la base; Si todos los Cij-Zij son valores positivo, esta es la solución óptima.
3. Determinar que variable alcanza el 0 primero cuando la variable entrante aumenta de valor
4. Determine una nueva solución básica y volver a 2.

Algoritmo MODI (Modified distribution approach).

Este algoritmo se basa en los métodos usados en dualidad. Este método supone que, si necesariamente, un destino artificial o un origen artificial se han agregado tal que la demanda total iguala a la oferta total. Si este es el caso, m restricciones de oferta y las n restricciones de demanda se pueden escribir como igualdades, entonces el algoritmo procede como sigue:
 

  1. Si Ui es la variable dual asociada con la i-ésima restricción de oferta, y Vj es la variable dual asociada con la j-ésima restricción de demanda, entonces para el traslado desde el nodo i al nodo j se puede encontrar el correspondiente valor de Zij como Ui-Vj. Asi el valor de Cij-Zij para la variable Xij se encuentra usando la siguiente relación:  Cij-Zij = Cij-(Ui-Vj) = Cij -Ui + Vj
  2. Dado que hay una ecuación redundante entre las m+n restricciones (y cualquiera de las m+n puede ser considerada como la "restricción redundante"), se puede mostrar que Ui ó Vj asociado con la ecuación redundante vale 0. Asi, se puede seleccionar arbitrariamente un Ui ó Vj y asignarle el valor 0. Por ejemplo U1.
  3. Ya que los Cij-Zij de las variables básicas valen 0, se puede resolver fácilmente los valores restantes de los Uis y Vjs de las m+n-1 ecuaciones de las variables básicas.
  4. Una vez que se han determinado los valores de los Ui´s y Vj´s, se pueden determinar los valores para las variables no básicas, calculando: Cij-Zij = Cij - Ui + Vj
  5. Seleccionar la variable no-básica con el valor más negativo de Cij-Zij como la variable que entra a la base. Si todos los Cij-Zij son no-negativos, entonces está en el óptimo. La solución actual es la óptima.
  6. Encontrar el ciclo que incluye la variable entrante y algunas de las variables BASICAS. Alternando cambios negativos y positivos en el ciclo, determine la "cantidad de cambio" como la cantidad más pequeña dentro del ciclo.
  7. Modifique las asignaciones de las variables del ciclo encontrado y vuelva al paso 2.