SOLUCIÓN ÓPTIMA
FASE II. Iteración para llegar a la Solución Óptima
La fase II del método simplex de transporte es un procedimiento para iterar, partiendo de la
solución factible inicial que se identifica en la fase I, para llegar a la solución óptima. Recuerde que
cada celda de la tabla de transporte corresponde a un arco (ruta) del modelo de red para el
problema del transporte. El primer paso en cada una de las iteraciones de la fase II consiste en
identificar una celda (arco) de entrada. Un arco de entrada es la ruta que actualmente no se utiliza
(celda desocupada) en donde realizar una asignación de flujo ocasionaría la mayor reducción por
unidad en los costos totales. Después se asigna flujo a la celda de entrada, y se ajustan las
cantidades que se envían sobre todas las demás rutas a las que se ha asignado flujo para
conservar una solución factible. En el proceso de ajustar los flujos asignados a las celdas
ocupadas, se identifica una celda de salida y se elimina de la solución.
Se utiliza un método al que se denomina Método MODI, para analizar si la solución factible inicial
es óptima o no. Si no lo es este método indica la celda de entrada.
El método modi requiere que se defina un índice ui, para cada fila de la tabla (matriz) y un índice,
vj, para cada columna. Estos índices de columna y fila se obtienen utilizando los costos unitarios
de cada celda ocupada, mediante la siguiente fórmula: Cij = ui + vj
Para seguir el ejemplo se considera la solución factible inicial y se determinan los índices:
CELDAS OCUPADAS Cij = ui + vj
X11 3 = u1 + v1
X12 3 = u1 + v2
X21 3 = u2 + v1
X23 3 = u2 + v3
X42 3 = u4 + v2
X31 3 = u3 + v1
Se tiene un sistema con seis ecuaciones y siete variables. Como existe una variable más que el
número de ecuaciones, se puede elegir libremente un valor para una de las variables y luego
encontrar el valor de las otras. Generalmente se toma u1 = 0 y se halla el valor del resto.
C11 = ui + vj ui vi
3 = 0 + v1 u1 = 0 v1 = 3
2 = 0 + v2 u2 = 4 v2 = 2
7 = u2 + v1 u2 = 7 - 3 u3 = - 1 v3 = - 2
2 = u2 + v3 v3 = 2 - 4 v4 = - 1
3 = u2 + v4 v4 = 3 - 4
2 = u3 + v1 u3 = 2 - 3
Los científicos en la administración han demostrado que para cada celda no ocupada e ij = Ci j - ui
- vj muestra el cambio que daría en el costo total, por unidad, al asignar una unidad de flujo al
arco correspondiente.
Celdas desocupadas
e13 = 7 - 0 - (- 2) = 9
e14 = 6 - 0 - (- 1) = 7
e22 = 5 - 4 - 2 = -1
e32 = 5 - (-1) - 2 = 4
e33 = 4 - (-1) - (-2) = 7
e34 = 5 - (-1) - (-1) = 7
Replanteando la tabla que contiene la solución factible inicial y utilizando la información obtenida
se tiene:
Se puede observar que los ei j se han demarcado en negrilla en cada una de las celdas
desocupadas. Por cada unidad que se asigne a la celda X13 se obtendría un aumento en el costo
total de $9, por cada unidad que se asigne a la celda X33 se obtendría un aumento $7 en el costo
total y así sucesivamente. Como el objetivo es disminuir el costo total, se ve que la celda de
entrada en el ejemplo es X22 debido a que por cada unidad asignada a esta celda va ha existir una
disminución de $1 en el costo total.
Ahora la cuestión es: ¿Qué flujo se debe asignar a esta celda? Como el costo total disminuye en
$1 por unidad que se asigne, es deseable asignar el mayor flujo posible. Para encontrar este
máximo es necesario tener en cuenta que el equilibrio entre la oferta y la demanda debe
mantenerse. Puede utilizarse el método del cruce del arroyo para determinar los ajustes que son
necesarios, y para identificar el arco que sale.
Identificada la celda de entrada, se le asigna un (+) a esta y se busca en la misma fila una celda
ocupada y se le asigna (-), de igual forma con la columna.
Un ⊕ indica que la asignación a esa celda aumentará en la misma cantidad que se asigne a la
celda que entra. Un (-) indica que la asignación a esa celda disminuirá en la cantidad que se
asigne a la celda que entra por ello, para determinar la cantidad máxima que se puede asignar a la
celda que entra, simplemente se observan las celdas identificadas con (-) en el camino del cruce
del arroyo. Como no pueden existir asignaciones negativas de flujo, la celda que tenga (-) y que
tenga la menor cantidad asignada determina la cantidad máxima que se puede asignar a la celda
que entra. Después de asignar esa cantidad máxima a la celda que entra, se hacen todos los
ajustes necesarios sobre el camino del cruce del arroyo para conservar la factibilidad. La celda
entrante se convierte en una celda ocupada, y la celda que sale se elimina de la solución del
momento.
En el ejemplo se tienen las celdas X12 y X21 identificadas con (-) se escoge la de menor flujo o
sea la celda X21 que sería la celda de salida y el flujo a asignar a la celda de entrada sería 2.500 y
las que estén identificadas con ⊕ se les sumará esa cantidad y las (-) se les restará esa cantidad.
Hechos los respectivos ajustes se tendrá nueva una tabla, que representa una nueva solución
factible.
Se tiene ahora una nueva solución factible y mediante el método MODI se probará si es o no
óptima.
ASIGNACIÓN COSTOS COSTO
UNITARIO TOTAL
X11 ⇒ ruta Bogotá - Bucaramanga 3.500 $3 $10.500
X12⇒ ruta Bogotá - Cartagena 1.500 $2 3.000
X22 ⇒ ruta Medellín - Cartagena 2.500 $5 12.500
X23⇒ ruta Medellín - Tulua 2.000 $2 4.000
X24⇒ ruta Medellín - Arauca 1.500 $3 4.500
X31⇒ ruta Cali - Bucaramanga 2.500 $2 5.000
TOTAL 13.500 $39.500
C11 = ui + vj ui vi
3 = 0 + v1 u1 = 0 v1 = 3
2 = 0 + v2 u2 = 3 v2 = 2
7 = u2 + v2 u2 = 5-2 u3 = - 1 v3 = - 1
2 = u2 + v3 v3 = 3-4 v4 = 0
3 = u2 + v4 v4 = 3-3
2 = u3 + v1 u3 = 2 - 3
Se hallan los ei j en las celdas desocupadas
Celdas desocupadas
e13 = 7 - 0 - (- 1) = 8
e14 = 6 - 0 - 0 = 6
e21 = 7 - 3 - 3 = 1
e32 = 5 - (-1) - 2 = 4
e33 = 4 - (-1) - (-1) = 6
e34 = 5 - (-1) - 0 = 6
Todos los ei j son mayores que cero. Luego la solución obtenida es óptima.
Solución óptima para el problema del transporte es:
ASIGNACIÓN COSTOS COSTO
UNITARIO TOTAL
X11 ⇒ ruta Bogotá - Bucaramanga 3.500 $3 $10.500
X12 ⇒ ruta Bogotá - Cartagena 1.500 $2 3.000
X22 ⇒ ruta Medellín - Cartagena 2.500 $5 12.500
X23⇒ ruta Medellín - Tulua 2.000 $2 4.000
X24⇒ ruta Medellín - Arauca 1.500 $3 4.500
X31⇒ ruta Cali-Bucaramanga 2.500 $2 5.000
TOTAL 13.500 $39.500
Conservación de las m + n - 1 Celdas Ocupadas
Recuerde que m representa el número de orígenes y n representa el número de destinos. Se dice
que la solución a un problema de transporte que no tiene m+n-1 celdas con asignación es
degenerada. El problema con la degeneración es que debe haber m+n-1 celdas ocupadas para
que sea posible utilizar el método MODI para calcular todos los índices de columna y de fila.
Cuando se presenta la degeneración, puede crearse una celda ocupada para poder calcular los
índices de fila y de columna. En seguida se ilustra la forma en la que puede presentarse la
degeneración y como se soluciona.
En la tabla se muestra la solución factible inicial que se obtiene utilizando el método del costo
mínimo para un problema de transporte con m = 3 orígenes y n = 3 destinos. Para utilizar el
método Modi en este problema, es necesario tener m+ n -1 = 3 + 3 - 1 = 5 celdas ocupadas.
Como la solución factible inicial tiene 4 celdas, la solución es degenerada.
Para calcular todos los índices de fila y columna en los casos en que hay menos de m + n - 1
celdas ocupadas, se debe crear una o más celdas artificiales ocupadas con un flujo de 0, en el
ejemplo es necesario crear una celda artificial para tener 5 celdas ocupadas y de esta forma
utilizar el método MODI. Se puede convertir cualquier celda no ocupada en celda artificial ocupada,
si hacerlo permite que resulte posible calcular los índices restantes de fila y de columna. Por
ejemplo la celda X23 se toma como una celda artificial ocupada, en este momento se tienen 5
celdas ocupadas y se procede hallar los ui y los vj.
C11 = ui + vj ui vi
3 = 0 + v1 u1 = 0 v1 = 3
6 = 0 + v2 u2 =-1 v2 = 6
5 = u2 + v2 u2 = 5-6 u3 = 3 v3 = 8
7 = u2 + v3 v3 = 7-(-1)
11 = u3+ v3 u3 = 11-8
Se hallan los ei j en las celdas desocupadas
Celdas desocupadas
e13 = 7 - 0 - 8 = -1
e21 = 8 - (-1) - 3 = 6
e31 = 4 - 3 - 3 = -2
e32 = 9 - 3 - 6 = 0
Revisando los ei j se identifica que la celda entrante es la X31, porque presenta el e31 como el valor
más negativo lo cual indica que por cada unidad que se asigne a esta celda existirá una
disminución de $2 en el costo total. Se utiliza el método del cruce del arroyo y se hacen los
ajustes necesarios conservando la factibilidad.
tabla de transporte con una celda artificial X31
Ruta del Cruce del Arroyo para la Celda Entrante X31
Como la menor cantidad en las celdas que disminuye es 30, la asignación que se hace a la celda
que entra es 30 unidades. Sin embargo, cuando se asignan 30 unidades a la celda que entra y se
realizan los ajustes correspondientes en las celdas ocupadas en el camino del cruce del arroyo,
las asignaciones de dos celdas se convierten en cero. Se elige a cualquiera de las dos como
celda de salida pero no a las dos; la otra se convierte en una celda artificial ocupada y se le asigna
un flujo de cero. Mientras no se elimine más de una celda en cada iteración, el método MODI
funciona.
Calculados los nuevos índices de fila y columna se tiene la siguiente tabla:
Nuevos Indices de fila y Columna que se Obtienen después de asignar 30 unidades a la Celda X31 y
salir la Celda X33
Se observa que en la celda x13 hay -1 lo que quiere decir que la solución todavía no es óptima y
que se tiene como celda de entrada la x13. Cada unidad que se asigne a esta celda hará que
disminuya el valor del costo total en $1. En la siguiente tabla se muestra el camino del cruce del
arroyo correspondiente a la celda entrante x13.
Ruta del Cruce del Arroyo correspondiente a la Celda que entra X13
Realizando los ajustes necesarios, hallando los índices de filas y columnas y los ei j se tiene la
siguiente tabla.
Si se observa los ei j se da cuenta que son todos positivos, lo cual indica que se tiene la solución
óptima.
