Modelo de transporte

El modelo de transporte es una clase especial de programación lineal que tiene que
ver con transportar un artículo desde sus fuentes (es decir, fábricas) hasta sus
destinos (es decir, bodegas). El objetivo es determinar el programa de transporte
que minimice el costo total del transporte y que al mismo tiempo satisfaga los límites
de la oferta y la demanda. En el modelo se supone que el costo de transporte es
proporcional a la cantidad de unidades transportadas en determinada ruta.
Definición del modelo de transporte
La siguiente imagen representa el problema. Hay m orígenes y n destinos, cada uno
representado por un nodo. Los arcos representan las rutas que unen los orígenes
con los destinos. El arco (i, j) que une el origen i con el destino j transporta dos
piezas de información: el costo de transporte por unidad, cij y la cantidad
transportada, xij. La cantidad de la oferta en el origen i es ai y la cantidad de la
demanda en el destino j es bj. El objetivo del modelo es minimizar el costo de
transporte total al mismo tiempo que se satisfacen las restricciones de la oferta y la
demanda.

Ejemplo: MG Auto cuenta con tres plantas en Los Ángeles, Detroit y Nueva Orleáns,
y dos importantes centros de distribución en Denver y Miami. Las capacidades
trimestrales de las tres plantas son 1000, 1500 y 1200 automóviles, y las demandas
de los dos centros de distribución durante el mismo periodo es de 2300 y 1400
automóviles. La distancia en millas entre las plantas y los centros de distribución
aparece en la siguiente tabla:
La compañía transportista cobra 8 centavos por milla por automóvil. En la siguiente
tabla se dan los costos de transporte por automóvil en las diferentes rutas,
redondeados al dólar más cercano.

El modelo de PL del problema es:

Todas estas restricciones son ecuaciones porque la oferta total desde los tres
orígenes (= 1000 + 1500 + 1200 = 3700 automóviles) es igual a la demanda total en
los dos destinos (= 2300 + 1400 = 3700 automóviles).
La estructura especial del problema de transporte permite una representación
compacta del problema utilizando el formato tabla de transporte que aparece en la
siguiente tabla:

Este formato permite modelar muchas situaciones que no tienen que ver con bienes
de transporte
Balanceo del modelo de transporte. La representación de la tabla de transporte
asume que el modelo está balanceado, es decir, que la demanda total es igual a la
oferta total. Si el modelo está desbalanceado, podemos agregar un origen o un
destino ficticios para restaurar el balance.
Algoritmo de transporte
Los pasos básicos del algoritmo de transporte son exactamente iguales a los del
método Simplex. Sin embargo, en lugar de utilizar la tabla simplex regular,
aprovechamos la estructura especial del modelo de transporte para organizar los
cálculos en una forma más conveniente.
Paso 1. Determine una solución factible básica inicial y vaya al paso 2.
Paso 2. Use la condición de optimalidad del método simplex para determinar la
variable de entrada de entre todas las variables no básicas. Si se satisfacen las
condiciones de optimalidad, deténgase. De lo contrario, avance al paso 3.
Paso 3. Use la condición de factibilidad del método simplex para determinar la
variable de entrada de entre todas las variables básicas actuales, y halle la nueva
solución básica. Regrese al paso 2.
Ejemplo:
SunRay Transport Company transporta granos de tres silos a cuatro molinos. La
oferta (en camiones cargados) y la demanda (también en camiones cargados) junto
con los costos de transporte por unidad por camión cargado en las diferentes rutas,
se resumen en la tabla siguiente. Los costos de transporte por unidad, cij (que se
muestran en la esquina de cada casilla) están en cientos de dólares. El modelo
busca el programa de envíos a un costo mínimo entre los silos y los molinos.

Determinación de la solución de inicio

Un modelo de transporte general con m orígenes y n destinos tiene m + n
ecuaciones de restricción, una por cada origen y cada destino. Sin embargo, como
el modelo de transporte siempre está balanceado (suma de la oferta = suma de la
demanda) una de las ecuaciones es redundante, por lo que el modelo se reduce a
m + n - 1 ecuaciones independientes y m + n - 1 variables básicas. En el ejemplo,
la solución inicial tiene 3+4-1=6 variables básicas.
La estructura especial del problema de transporte permite asegurar una solución
básica inicial no artificial siguiendo uno de los tres métodos:
1. Método de la esquina noroeste
2. Método del costo mínimo
3. Método de aproximación de Vogel
Método de la esquina noroeste. El método se inicia en la celda de la esquina
noroeste
Paso 1. Asigne lo más posible a la celda seleccionada, y ajuste las cantidades
asociadas de oferta y demanda restando la cantidad asignada.
Paso 2. Tache la columna o fila con oferta o demanda cero para indicar que no se
hagan más asignaciones en esa fila o columna. Si una fila y una columna dan cero
al mismo tiempo, tache sólo una, y deje una oferta (demanda) cero en la fila
(columna) no tachada.
Paso 3. Si se deja sin tachar exactamente una fila o columna, deténgase. De lo
contrario, muévase a la celda a la derecha si acaba de tachar una columna, o abajo
si acaba de tachar una fila. Vaya al paso 1.

Método del costo mínimo. El método del costo mínimo determina una mejor solución
inicial al concentrarse en las rutas más económicas. Asigna lo más posible a la celda
con el costo unitario mínimo (los empates se rompen arbitrariamente). Luego se
tacha la fila o columna satisfecha y se ajustan las cantidades de oferta y demanda
como corresponda. Si una fila o una columna se satisfacen al mismo tiempo, sólo
se tacha una, igual que en el método de la esquina noroeste. A continuación,
seleccione la celda no tachada con el costo unitario mínimo y repita el proceso hasta
que se deje sin tachar exactamente una fila o columna.
Método de aproximación de Vogel (MAV). Este método es una versión mejorada del
método del costo mínimo que por lo general, pero no siempre, produce mejores
soluciones iniciales.
Paso 1. Para cada fila (columna) determine una medida de penalización restando el
elemento de costo unitario mínimo en la fila (columna) del siguiente elemento de
costo mínimo en la misma fila (columna).
Paso 2. Identifique la fila o columna con la penalización máxima, que rompa los
empates arbitrariamente. Asigne lo más posible a la variable con el costo unitario
mínimo en la fila o columna seleccionada. Ajuste la oferta y la demanda, y tache la
fila o columna satisfecha. Si una fila y una columna se satisfacen al mismo tiempo,
sólo se tacha una de las dos, y a la fila restante (columna) se le asigna una oferta
(demanda) cero.
Paso 3. (a) Si exactamente una fila o columna con oferta o demanda cero
permanece sin tachar, deténgase.
(b) Si una fila (columna) con oferta (demanda) positiva permanece sin tachar,
determine las variables básicas en la fila (columna) mediante el método del costo
mínimo. Deténgase.
(c) Si todas las filas y columnas no tachadas tienen oferta y demanda cero
(restantes), determine las variables básicas cero por el método del costo mínimo.
Deténgase.
(d) De lo contrario, vaya al paso 1.
Cálculos iterativos del algoritmo de transporte
Después de determinar la solución inicial, utilizamos el siguiente algoritmo para
determinar la solución óptima:
Paso 1. Utilice la condición de optimalidad inicial para determinar la variable de
entrada. Si la condición de optimalidad se satisface, deténgase. De lo contrario,
continúe con el paso 2.
Paso 2. Determine la variable de salida utilizando la condición de factibilidad
simplex. Cambie la base, y regrese al paso 1.
Las condiciones de optimalidad y factibilidad no implican las conocidas operaciones
de filas utilizadas en el método simplex. En su lugar, la estructura especial del
modelo de transporte permite cálculos (manuales) más simples.

Bibliografía:
TAHA, HAMDY A. Investigación de operaciones Novena edición PEARSON
EDUCACIÓN, México, 2012