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:
-
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
-
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.
-
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.
-
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
-
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.
-
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.
-
Modifique las asignaciones de las variables del ciclo encontrado y vuelva
al paso 2.