RL
Programa Académico CPEL
INVESTIGACION DE
OPERACIONES
SEMANA 4 SESION 1
PROBLEMA DE
TRANSPORTE
RL
CONTENIDO DE LA SESION
• Problema del transporte, donde se trata de determinar
la manera optima de transportar bienes.
• Problema de asignación, incluye aplicaciones tales
como asignar personas a tareas. Aunque sus
aplicaciones parecen diferir del problema de
transporte, este problema es un caso especial del
problema de transporte.
• METODOS: ESQUINA NOROESTE
• METODO DE TRANSPORTE
• METODO DE SALTO DE PIEDRA
Dr. (c ) Ricardo López Guevara
RL
OBJETIVO DEL CURSO
• Proporcionar una estructura básica para
la comprensión de los métodos
cuantitativos (Investigación Operativa)
que describa los conocimientos y las
prácticas de su uso en el campo de la
gestión empresarial.
Dr. (c ) Ricardo López Guevara
RL
El Problema de transporte
De una manera general, se define el problema del
transporte como la determinación de las cantidades de un
bien a enviar de un número "m" de orígenes a un número
"n" de destinos, de manera que los costos de envío sean
los menores.
Orígenes Destinos
1 1
2 2
m n
RL
El Problema de transporte
Cada origen tiene una cierta capacidad de "oferta",
Cada destino tiene una cierta capacidad de "demanda",
Y existen rutas desde los orígenes hasta los destinos.
Orígenes Destinos
a1 1 1 b1
a2 2 2 b2
Oferta Demanda
am m n bn
Rutas
RL
Se pueden enviar xij unidades del bien desde el origen "i" al
destino "j".
Cada unidad del bien que se envía del origen "i" al destino "j"
tiene un costo "cij" asociado.
x11 c11
1 1
2 2
m n
cmn xmn
De tal manera que el costo de enviar las unidades de "i" a "j" es: cijxij
RL
Sabiendo que se quiere minimizar el costo de transporte, y que la
cantidad a enviar no puede sobrepasar la capacidad de cada origen, y
que se desea surtir la demanda de los destinos, un modelo matemático
podría presentarse de la siguiente manera:
m n
MinZ cij xij (Costo total del transporte)
i 1 j 1
n
xij ai , i (Capacidad en los orígenes)
j 1
m
xij bj , j (Demanda en los destinos)
i 1
xij 0, i, j (No negatividad)
RL
Este nuevo modelo puede tratarse mediante el algoritmo Simplex, sin
embargo el número de variables y de restricciones crece rápidamente a
medida que aumenta el número de orígenes y de destinos. Así, se ha
ideado una forma más eficiente de resolver los problemas que pueden
plantearse como los de transporte.
Este método asume que el problema está "balanceado", es decir que la
cantidad ofrecida es igual a la cantidad demandada:
ai = bj
Dicha condición es fácilmente asegurada mediante la introducción de
las variables auxiliares adecuadas.
RL
El modelo lineal típico de transporte se convierte en:
m n
MinZ cij xij
i 1 j 1
n
xij ai , i
j 1
m
xij bj , j
i 1
xij 0, i, j
Donde las igualdades se aseguran por la adición de las
variables necesarias.
RL
El método tabular consiste en vaciar la información pertinente
en una tabla de formato especial.
Como en el caso del Simplex, se genera una solución inicial, y
se va mejorando a través de las iteraciones propias del
método.
La tabla de transporte tiene la siguiente forma:
Destino
Origen
1 2 3 4 Oferta
c11 c12 c13 c14
1 a1
x11 x12 x13 x14
c21 c22 c23 c24
2 a2
x21 x22 x23 x24
c31 c32 c33 c34
3 a3
x31 x32 x33 x34
a
Demanda b1 b2 b3 b4
b
RL
Ejemplo 1 de Render y Stair.
De acuerdo a la información presentada, la oferta es igual a la
demanda, está balanceado:
Destino
Origen
Albuquerque Boston Cleveland Oferta
5 4 3
Des Moines 100
8 4 3
Evansville 300
Fort 9 7 5
300
Lauderdale
700
Demanda 300 200 200
700
RL
Solución (distribución) inicial
Métodos:
Esquina Nor-Oeste
Costo menor
Por columna
Por fila
Mutua preferencia
Vogel
RL
Método de distribución inicial: Esquina N.-O.
Consiste en ir asignando la mayor cantidad posible a la casilla
de la esquina superior izquierda del cuadro formado por las
casillas vacías.
Primera casilla N.-O.: Des Moines-Albuquerque. Cantidad: 100
Destino
Origen
Albuquerque Boston Cleveland Oferta
5 4 3 El renglón 1
Des Moines 100 100
queda
8 4 3 saturado
Evansville 300
Fort 9 7 5
300
Lauderdale
700
Demanda 300 200 200
700
RL
Método de distribución inicial: Esquina N.-O.
La siguiente esquina N.-O. es: Evansville-Albuquerque.
Cantidad máxima: 200
Destino
Origen
Albuquerque Boston Cleveland Oferta
5 4 3
Des Moines 100 100
8 4 3
Evansville 200 300
Fort 9 7 5
300
Lauderdale
700
Demanda 300 200 200
700
Se satura la columna 1.
RL
Método de distribución inicial: Esquina N.-O.
La siguiente esquina N.-O. es: Evansville-Boston.
Cantidad máxima: 100
Destino
Origen
Albuquerque Boston Cleveland Oferta
Se satura el
5 4 3 renglón 2.
Des Moines 100 100
8 4 3
Evansville 200 100 300
Fort 9 7 5
300
Lauderdale
700
Demanda 300 200 200
700
RL
Método de distribución inicial: Esquina N.-O.
Como sólo quedan dos casillas por asignar, la elección resulta obvia, y se
completan las dos demandas y la oferta restantes.
Fort Lauderdale enviaría 100 unidades a Boston y 200 a Cleveland
Destino
Origen
Albuquerque Boston Cleveland Oferta
5 4 3
Des Moines 100 100
8 4 3
Evansville 200 100 300
Fort 9 7 5
100 200 300
Lauderdale
700
Demanda 300 200 200
700
El costo total de tranporte sería de $ 4,200
Nótese que la cantidad de casillas asignadas es "m+n-1", lo que indica que es una
solución no-degenerada.
RL
Optimización
Consiste en determinar si la distribución de una tabla es la óptima,
encontrando los costos de oportunidad de las casillas vacías (variables no-
básicas), es decir, el costo en el que se incurre al no enviar una unidad del
origen "i" al destino "j", y lograr una tabla óptima mediante las iteraciones
necesarias.
Métodos:
Stepping-stone (cruce del arroyo o Salto de piedra)
MODI (Distribución Modificada)
RL
Método Stepping-stone (Cruce del Arroyo o Salto de Piedra)
Consiste en encontrar los elementos índice (cij – zij) de las variables no-
básicas (casillas vacías) mediante el uso de recorridos o trayectorias
únicas de cada casilla vacía.
La variable con el índice negativo menor será la variable de entrada.
La variable de salida será aquélla con la menor cantidad asignada,
seleccionada entre las casillas con signo negativo dentro del reco- rrido.
RL
Reglas para encontrar el circuito (recorrido cerrado o trayectoria cerrada)
de las casillas vacías:
1. El recorrido de una casilla vacía es único y toca siempre un
número par de casillas (número de vértices).
2. Sólo se permiten movimientos en sentido horizontal y vertical.
Nunca en diagonal.
3. Al iniciar el trayecto en un sentido, el regreso es en el otro (Salida
vertical – regreso horizontal o viceversa).
4. El cambio de dirección (vértices) se efectúa sólo en casillas
asignadas.
5. Al pasar de un vértice a otro (de un cambio de dirección a otro) se
pueden saltar (ignorar) todas las casillas que se necesite, ya se trate
de asignadas o de vacías.
RL
Recorrido para la casilla 1,2 (variable no-básica x12):
Si se escogió partir en horizontal llegará a la 1,1.
Cambia en vertical a la 2,1.
Luego en horizontal a la 2,2.
Por último regresa verticalmente a la 1,2.
Destino
Origen
Albuquerque Boston Cleveland Oferta
5 4 3
Des Moines 100 100
8 4 3
Evansville 200 100 300
Fort 9 7 5
100 200 300
Lauderdale
700
Demanda 300 200 200
700
RL
Costo de oportunidad para la casilla 1,2 (c12 – z12):
Se asignan signos "+" y "-" alternativamente a las casillas del recorrido, iniciando por un
"+" en la de origen.
Y se suman y restan los costos de transporte, según su signo:
(c12 – z12) = 4 – 5 + 8 – 4 = 3.
Destino
Origen
Albuquerque Boston Cleveland Oferta
(-) 5 (+) 4 3
Des Moines 100 100
8 4 3
Evansville 200 100 300
(+) (-)
Fort 9 7 5
100 200 300
Lauderdale
700
Demanda 300 200 200
700
RL
Recorrido para la casilla 1,3 (variable no-básica x13):
Si se escogió partir en vertical llegará a la 3,3.
Cambia en horizontal a la 3,2.
Luego en vertical a la 2,2.
Después en horizontal a la 2,1.
En vertical a la 1,1. ... y por último regresa Horizontalmente a la 1,3.
Destino
Origen
Albuquerque Boston Cleveland Oferta
(-) 5 4 3
Des Moines 100 (+) 100
8 4 3
Evansville 200 (-) 100 300
(+)
Fort 9 7 (-) 5
(+) 100 200 300
Lauderdale
(c13 – z13) = 4
700
Demanda 300 200 200
700
RL
Recorrido para la casilla 2,3 (variable no-básica x23):
Si se escogió partir en horizontal llegará a la 2,2.
Cambia en vertical a la 3,2.
Luego en horizontal a la 3,3.
Por último regresa verticalmente a la 2,3.
Destino
Origen
Albuquerque Boston Cleveland Oferta
5 4 3
Des Moines 100 100
(c23 – z23) = 1
8 (-) 4 (+) 3
Evansville 200 100 300
Fort 9 (+) 7 (-) 5
100 200 300
Lauderdale
700
Demanda 300 200 200
700
RL
Recorrido para la casilla 3,1 (variable no-básica x31):
Si se escogió partir en horizontal llegará a la 3,2.
Cambia en vertical a la 2,2.
Luego en horizontal a la 2,1.
Por último regresa verticalmente a la 3,1.
Destino
Origen
Albuquerque Boston Cleveland Oferta
5 4 3
Des Moines 100 100
(c31 – z31) = - 2
8 4 3
Evansville 200 100 300
(-) (+)
Fort 9 7 5
100 200 300
Lauderdale (+) (-)
700
Demanda 300 200 200
700
RL
Se tienen ahora completos todos los costos de oportunidad:
(c12 – z12) = 3
(c13 – z13) = 4
(c23 – z23) = 1
(c31 – z31) = - 2
El criterio de optimalidad es que todos los elementos índice (costos de
oportunidad) sean no-negativos: (cij – zij) 0, por lo tanto x31 deberá
entrar a la base, puesto que su índice es "-2".
RL
La iteración consiste en seleccionar el recorrido de la variable
de entrada (x31) y reasignar las cantidades de las casillas Pertene-
cientes a dicho recorrido.
Esto se logra seleccionando la menor cantidad asignada entre
las casillas con signo negativo. Esta cantidad se suma y se resta
en las casillas del recorrido, según su signo: si tiene un "+" se
suma a la cantidad que tiene asignada, y si tiene un "-" se le resta.
Al hacerlo de esa manera, se asegura que la tabla siga siendo
factible y balanceada. Se puede presentar el caso de una solución
degenerada, pero éste se discutirá más adelante. El procedimiento
se repetirá hasta que no existan negativos en los costos de opor-
tunidad, en cuyo caso se ha encontrado la solución óptima.
RL
En este caso, las casillas con signo negativo son la 2,1 y la 3,2.
La menor cantidad asignada entre ellas es 100. Entonces se sumarán
100 unidades a las casillas 2,2 y 3,1, y se restarán 100 unidades a las
casillas 2,1 y 3,2 cuya variable (x32) sale de la base.
Destino
Origen
Albuquerque Boston Cleveland Oferta
5 4 3
Des Moines 100 100
8 4 3
Evansville 200 100 300
(-) (+)
Fort 9 7 5
100 200 300
Lauderdale (+) (-)
700
Demanda 300 200 200
700
RL
La nueva tabla quedaría de la manera siguiente:
Destino
Origen
Albuquerque Boston Cleveland Oferta
5 4 3
Des Moines 100 100
8 4 3
Evansville 100 200 300
Fort 9 7 5
100 200 300
Lauderdale
700
Demanda 300 200 200
700
(Nótese que la casilla de la variable de salida contiene ahora un punto.
Esto es porque es ahora no-básica)
Y el nuevo costo total será: Z = 4,000 (menor que el anterior)
Pregunta: ¿Esta solución es la óptima? ¿Por qué?
RL
Efectivamente: No es óptima porque queda aún la casilla 2,3 con un costo
de oportunidad negativo. Se deberá iterar de nuevo:
Destino
Origen
Albuquerque Boston Cleveland Oferta
5 4 3
Des Moines 100 100
8 4 (+)
3
Evansville 100 (-) 200 300
Fort 9 7 5
100 (+) 200 300
Lauderdale (-)
700
Demanda 300 200 200
700
(c23 – z23) = 3-8+9-5 = -1
Variable de entrada: x23. Variable de salida: x21. ¿Correcto?
RL
La nueva tabla queda como sigue:
Destino
Origen
Albuquerque Boston Cleveland Oferta
5 4 3
Des Moines 100 100
8 4 3
Evansville 200 100 300
Fort 9 7 5
200 100 300
Lauderdale
700
Demanda 300 200 200
700
Y el nuevo costo total de transporte es:
Z = 100*5 + 200*4 + 100*3 + 200*9 + 100*5 = 3,900
¿Esta solución es la óptima? ¿Por qué?
RL
Tienen razón. Es óptima porque ya no contiene índices negativos.
La solución óptima será entonces:
Enviar:
100 unidades de la fábrica de Des Moines al almacén de Albuquerque.
200 " " " " " Evansville " " " Boston.
100 " " " " " " " " " Cleveland.
200 " " " " " Fort Lauderdale " " Albuquerque.
100 " " " " " " " " " Cleveland.
Siendo el costo total de transporte: $3,900.00
RL
Método MODI (Distribución Modificada)
Consiste en determinar los costos de oportunidad mediante la relación:
(cij – zij) = cij – Ri - Kj
Donde Ri y Kj son valores asignados a renglones y columnas,
respectivamente, y se calculan por medio de las casillas asignadas,
tomando un valor inicial arbitrario de R o de K, y considerando su
respectivo (cij – zij) = 0 (por tratarse de variables básicas).
Una vez calculados todos los valores R y K, se procede a encontrar los
costos de oportunidad (c – z) correspondientes a las variables no-básicas
(casillas vacías) con relación mencionada; El resto es como en el método
"Stepping Stone“ o “Salto de Piedra”.
RL
Tomemos de nuevo el ejemplo con distribución inicial por esquina N-O, y asignemos
arbitrariamente un cero (0) a R1.
Kj 5
Destino
Ri Origen
Albuquerque Boston Cleveland Oferta
5 4 3
0 Des Moines 100 100
8 4 3
Evansville 200 100 300
Fort 9 7 5
100 200 300
Lauderdale
700
Demanda 300 200 200
700
Con ese cero en R1 se podrá encontrar el valor de K1, por medio de la casilla
asignada 1,1: K1 = c11 – R1 = 5 – 0 = 5
RL
Ahora, con K1, se podrán encontrar valores de R en la columna 1. En este caso
solamente la 2,1 está asignada.
Kj 5
Destino
Ri Origen
Albuquerque Boston Cleveland Oferta
5 4 3
0 Des Moines 100 100
8 4 3
3 Evansville 200 100 300
Fort 9 7 5
100 200 300
Lauderdale
700
Demanda 300 200 200
700
Entonces: R2 = c21 – K1 = 8 - 5 = 3
RL
¡Correcto! Dedujeron bien: Ahora encontramos el valor de K2 por medio de la casilla
asignada 2,2. ¿Cuál es el valor?
Kj 5 1
Destino
Ri Origen
Albuquerque Boston Cleveland Oferta
5 4 3
0 Des Moines 100 100
8 4 3
3 Evansville 200 100 300
Fort 9 7 5
100 200 300
Lauderdale
700
Demanda 300 200 200
700
En efecto, es 1: K2 = c22 – R2 = 4 - 3 = 1
Ahora ya pueden encontrar R3 y el de K3, mediante las otras casillas asignadas.
RL
El resultado es:
Kj 5 1 -1
Destino
Ri Origen
Albuquerque Boston Cleveland Oferta
5 4 3
0 Des Moines 100 100
8 4 3
3 Evansville 200 100 300
6 Fort 9 7 5
100 200 300
Lauderdale
700
Demanda 300 200 200
700
Obsérvese que los costos de oportunidad corresponden exactamente a los que se
Lo que siguecon
encontraron ahora es encontrar
el método los índices
de la esquina de las casillas vacías y determinar si la
N-O.:
solución es óptima con la relación: (cij – zij) = cij – Ri - Kj
(c12 – z12) = 3; (c13 – z13) = 4; (c23 – z23) = 1 y (c31 – z31) = - 2
RL
Lo anterior nos indica, al igual que con el método anterior, que la variable de entrada
es x31, y al igual que anteriormente, se busca su recorrido y se determina la variable de
salida, que corresponde a x32 , quedando como nueva solución:
Kj
Destino
Ri Origen
Albuquerque Boston Cleveland Oferta
5 4 3
Des Moines 100 100
8 4 3
Evansville 100 200 300
Fort 9 7 5
Lauderdale 100 200 300
700
Demanda 300 200 200
700
RL
Se vuelven a calcular los valores de R y K, y se encuentran los nuevos índices.
Kj 5 1 1
Destino
Ri Origen
Albuquerque Boston Cleveland Oferta
5 4 3
0 Des Moines 100 100
8 4 3
3 Evansville 100 200 300
4 Fort 9 7 5
Lauderdale 100 200 300
700
Demanda 300 200 200
700
Los costos de oportunidad para las casillas vacías son:
(c12 – z12) = 4 - 0 – 1 = 3; (c13 – z13) = 3 – 0 – 1 = 2;
(c23 – z23) = 3 – 3 – 1 = - 1 y (c32 – z32) = 7 – 4 – 1 = 2
RL
Igual que en el método Stepping stone, la variable de entrada es x23 y la de salida es x21.
La nueva solución es:
Kj
Destino
Ri Origen
Albuquerque Boston Cleveland Oferta
5 4 3
Des Moines 100 100
8 4 3
Evansville 200 100 300
Fort 9 7 5
Lauderdale 200 100 300
700
Demanda 300 200 200
700
RL
Se vuelven a calcular los valores de R y K, y se encuentran los nuevos índices.
(Favor de verificar que sean los valores correctos):
Kj 5 2 1
Destino
Ri Origen
Albuquerque Boston Cleveland Oferta
5 4 3
0 Des Moines 100 100
8 4 3
2 Evansville 200 100 300
4 Fort 9 7 5
Lauderdale 200 100 300
700
Demanda 300 200 200
700
(c12 – z12) = 4 - 0 – 2 = 2; (c13 – z13) = 3 – 0 – 1 = 2;
(c21 – z21) = 8 – 2 – 5 = 1 y (c32 – z32) = 7 – 4 – 2 = 1
RL
Puesto que no existen negativos en los índices, la solución es
óptima, y es exactamente la misma a la que se llegó por el método
Stepping Stone:
Enviar:
100 unidades de la fábrica de Des Moines al almacén de Albuquerque.
200 " " " " " Evansville " " " Boston.
100 " " " " " " " " " Cleveland.
200 " " " " " Fort Lauderdale " " Albuquerque.
100 " " " " " " " " " Cleveland.
Siendo el costo total de transporte: $3,900.00
RL
Método de Vogel o
Aproximación de Vogel
• Este modelo esta relacionado a la búsqueda
de una posible solución optima realizando
aproximaciones.
El resultado de este método es una solución
inicial factible, que servirá como entrada para
ser evaluada por otro modelo el cual vera si
esta es la mejor solución.
RL
Aproximación de Vogel
RL
Pasos del Método
1. Determinar para cada fila y columna una
medida de penalización restando los dos
costos menores en filas y columnas que es
la diferencia no negativa entre los 2 más
pequeños costos de embarque asociados
con las variables no asignadas en ese
renglón y en esa columna, le llamaremos
“Costo de Oportunidad”.
RL
Pasos de Método
2. Escoger la fila o columna con la mayor
penalización, es decir que de la resta en el paso
anterior se debe escoger el mayor (“Costo de
Oportunidad”).
3. De la fila o columna de mayor penalización
determinada en el paso anterior debemos
escoger la celda con menor costo y asignar la
mayor cantidad posible de unidades.
4. Reajustar la oferta y la demanda.
5. Eliminar la columna con demanda cero y la fila
con oferta cero.
6. Calcular los nuevo Costos de Oportunidad y
Volver a empezar del paso 1.
RL
Ejemplo Aproximación Vogel
RL
Ejemplo Aproximación Vogel
RL
Ejemplo Aproximación Vogel
RL
Ejemplo Aproximación Vogel
RL
Ejemplo Aproximación Vogel
RL
Ejemplo Aproximación Vogel
RL
Ejemplo Aproximación Vogel
RL
Ejemplo Aproximación Vogel
RL
Ejemplo Aproximación Vogel
RL
Ejemplo Aproximación Vogel
