Investigación
Operativa
Sesión N°20: Modelo de Transporte
Prof. Vania Quezada L.
Definición del modelo de transporte
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 1
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 son de 2300 y 1400 automóviles. La distancia en millas entre las plantas y los
centros de distribución aparece en la siguiente tabla:
El modelo de PL del problema sería:
Los costos de transporte por automóvil
en las diferentes rutas, redondeados al
dólar más cercano.
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).
Solución modelo
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:
La solución de esta programación lineal sería:
𝑋11 = 1.000 𝑢𝑛𝑖𝑑𝑎𝑑𝑒𝑠
𝑋22 = 200 𝑢𝑛𝑖𝑑𝑎𝑑𝑒𝑠
𝑋21 = 1.300 𝑢𝑛𝑖𝑑𝑎𝑑𝑒𝑠
𝑋32 = 1.200 𝑢𝑛𝑖𝑑𝑎𝑑𝑒𝑠
El costo de transporte mínimo es = $313.200
Solución modelo
Los pasos básicos del algoritmo de transporte son exactamente iguales a los del método simplex
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
La estructura especial del modelo de transporte permite asegurar que haya una solución básica no artificial de
inicio, obtenida con uno de los tres métodos siguientes:
1. Método de la esquina noroeste (superior, izquierda).
2. Método del costo mínimo.
3. Método de aproximación de Vogel.
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
Determinación de la solución de inicio
Método de la esquina noroeste. El método se inicia en la celda de la esquina noroeste (ruta) de la
tabla (variable x11).
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.
Determinación de la solución de inicio
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.
Determinación de la solución de inicio
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.
Ejemplo 2:
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 siguiente
tabla. 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.
Ejemplo 2:
Método de la esquina noroeste
Ejemplo 2:
Método del costo mínimo
Ejemplo 2:
Método de aproximación de VOGEL
Ejemplo 2: Método de aproximación de VOGEL
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.
Del ejemplo de MG Auto se tienen las mismas 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, 1300 y 1200 automóviles, y las
demandas de los dos centros de distribución durante el mismo periodo son de 2300 y 1400 automóviles.
La oferta total (= 3500) es menor
que la demanda total (=3700), lo
que significa que no se satisfará
una parte de la demanda en Denver La solución muestra que la
y Miami planta ficticia envía 200
automóviles a Miami, es decir
que a Miami le faltarán 200
automóviles para satisfacer
su demanda de 1400
automóviles
Ejemplo 3:
Tres plantas de energía eléctrica, con capacidades de 25, 40 y 50 millones de
kilovatios/hora, proporcionan electricidad a tres ciudades. La demanda máxima es de 30,
35 y 25 millones de kilovatios/hora. El costo de transporte por millón de kilovatio/hora
está dado en la siguiente tabla:
Tenemos un excedente de oferta de 25 millones de
kilovatios/hora, por lo tanto debemos agregar una ciudad
ficticia que consuma dicha cantidad. La tabla inicial la
construimos con 6 columnas y 5 filas.
Ejemplo 3:
Ejercicio Desafío
Una empresa está considerando satisfacer las necesidades de 4 clientes empleando
los artículos que tiene disponibles en 3 almacenes. La cantidad de artículos que tiene
en cada almacén son 10, 40 y 20 unidades respectivamente. Los clientes necesitan
12, 15, 30 y 20 unidades respectivamente. El costo unitario de embarque desde los
almacenes hasta el cliente se encuentran en la siguiente tabla:
