RLG
Programa CPEL
INVESTIGACION DE
OPERACIONES
SESION 2
RLG
BIBLIOGRAFA
Taha, Hamdy A.; Investigacin de Operaciones
Gould, Eppen y Schmidt; Investigacin de Operaciones en
la Ciencia Administrativa.
Richard Levin y Charles Kirkpatrick; Enfoques
cuantitativos a la Administracin.
K. Roscoe, Patrick G. McKeown; Modelos Cuantitativos
para la Administracin
Anderson, Sweeney, Willimas; Mtodos Cuantitativos para
los Negocios Editorial International Thomson.
Winston; Introduccin a la Investigacin de Operaciones.
Editorial, Fondo de Cultura Interamericano, Mxico.
Hillier y Lieberman; Introduccin a la Investigacin de
Operaciones
M Sasieni A Yaspan L Friedman; Investigacin de
operaciones, Ed. Limusa
Dr. (c) Ricardo Lpez Guevara 2 de 65
RLG
OBJETIVO DEL CURSO
Proporcionar una estructura bsica para la
comprensin de los mtodos cuantitativos
(Investigacin Operativa) que describa los
conocimientos y las prcticas de su uso en el campo
de la gestin empresarial.
Dr. (c ) Ricardo Lpez Guevara
RLG
El Problema de transporte
De una manera general, se define el problema del transporte
como la determinacin de las cantidades de un bien a enviar de
un nmero "m" de orgenes a un nmero "n" de destinos, de
manera que los costos de envo sean los menores.
Orgenes Destinos
1 1
2 2
m n
RLG
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 orgenes hasta los destinos.
Orgenes Destinos
a1 1 1 b1
a2 2 2 b2
Oferta Demanda
am m n bn
Rutas
RLG
Se pueden enviar xij unidades del bien desde el origen "i" al
destino "j".
Cada unidad del bien que se enva 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
RLG
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 matemtico
podra presentarse de la siguiente manera:
m n
MinZ c
i 1 j 1
ij xij (Costo total del transporte)
x
j 1
ij ai , i (Capacidad en los orgenes)
x
i 1
ij b j , j (Demanda en los destinos)
xij 0 , i, j (No negatividad)
RLG
Este nuevo modelo puede tratarse mediante el algoritmo Simplex, sin
embargo el nmero de variables y de restricciones crece rpidamente a
medida que aumenta el nmero de orgenes y de destinos. As, se ha
ideado una forma ms eficiente de resolver los problemas que pueden
plantearse como los de transporte.
Este mtodo asume que el problema est "balanceado", es decir que la
cantidad ofrecida es igual a la cantidad demandada:
ai = bj
Dicha condicin es fcilmente asegurada mediante la introduccin de
las variables auxiliares adecuadas.
RLG
El modelo lineal tpico de transporte se convierte en:
m n
MinZ c
i 1 j 1
ij xij
n
x
j 1
ij ai , i
x
i 1
ij b j , j
xij 0 , i, j
Donde las igualdades se aseguran por la adicin de las variables
necesarias.
RLG
El mtodo tabular consiste en vaciar la informacin pertinente en
una tabla de formato especial.
Como en el caso del Simplex, se genera una solucin inicial, y se va
mejorando a travs de las iteraciones propias del mtodo.
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
RLG
Ejemplo 1 de Render y Stair.
De acuerdo a la informacin 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
RLG
Solucin (distribucin) inicial
Mtodos:
Esquina Nor-Oeste
Vogel
RLG
Mtodo de distribucin 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 vacas.
Primera casilla N.-O.: Des Moines-Albuquerque. Cantidad: 100
Destino
Origen
Albuquerque Boston Cleveland Oferta
5 4 3 El rengln 1
Des Moines 100 100
queda saturado
8 4 3
Evansville 300
Fort 9 7 5
300
Lauderdale
700
Demanda 300 200 200
700
RLG
Mtodo de distribucin inicial: Esquina N.-O.
La siguiente esquina N.-O. es: Evansville-Albuquerque.
Cantidad mxima: 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.
RLG
Mtodo de distribucin inicial: Esquina N.-O.
La siguiente esquina N.-O. es: Evansville-Boston.
Cantidad mxima: 100
Destino
Origen
Albuquerque Boston Cleveland Oferta
Se satura el
5 4 3 rengln 2.
Des Moines 100 100
8 4 3
Evansville 200 100 300
Fort 9 7 5
300
Lauderdale
700
Demanda 300 200 200
700
RLG
Mtodo de distribucin inicial: Esquina N.-O.
Como slo quedan dos casillas por asignar, la eleccin resulta obvia, y se
completan las dos demandas y la oferta restantes.
Fort Lauderdale enviara 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 sera de $ 4,200
RLG
Mtodo Stepping-stone (Cruce del Arroyo o Salto de Piedra)
Consiste en encontrar los elementos ndice (cij zij) de las casillas
vacas (PL= variables no-bsicas ) mediante el uso de recorridos o
trayectorias nicas de cada casilla vaca.
La variable con el ndice negativo menor ser la Casilla a asignar
(PL= variable de entrada).
La casilla a desasignar (PL= variable de salida) ser aqulla con la menor
cantidad asignada, seleccionada entre las casillas con signo negativo
dentro del recorrido.
RLG
Reglas para encontrar el circuito (recorrido cerrado o trayectoria
cerrada) de las casillas vacas:
1. El recorrido de una casilla vaca es nico y toca siempre un nmero par
(4, 6, 8 ) de casillas (PL= nmero de vrtices).
2. Slo 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 direccin se efecta slo en casillas asignadas.
5. Al pasar de una casilla a otra (de un cambio de direccin a otro) se
pueden saltar (ignorar) todas las casillas que se necesite, ya se trate de
asignadas o de vacas.
RLG
Recorrido para la casilla 1,2 (variable no-bsica 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
RLG
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, segn 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
RLG
Recorrido para la casilla 1,3 (variable no-bsica 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.
Despus 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 (-) 100
4 3
Evansville 200 300
(+)
Fort 9 7 (-) 5
(+) 100 200 300
Lauderdale
(c13 z13) = 4
700
Demanda 300 200 200
700
RLG
Recorrido para la casilla 2,3 (variable no-bsica 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
RLG
Recorrido para la casilla 3,1 (variable no-bsica 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
RLG
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".
RLG
La iteracin 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, segn 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 solucin
degenerada, pero ste se discutir ms adelante. El procedimiento
se repetir hasta que no existan negativos en los costos de opor-
tunidad, en cuyo caso se ha encontrado la solucin ptima.
RLG
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 sumarn
100 unidades a las casillas 2,2 y 3,1, y se restarn 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
RLG
La nueva tabla quedara 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
(Ntese que la casilla de la variable de salida contiene ahora un punto.
Esto es porque es ahora no-bsica)
Y el nuevo costo total ser: Z = 4,000 (menor que el anterior)
Pregunta: Esta solucin es la ptima? Por qu?
RLG
Efectivamente: No es ptima porque queda an 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?
RLG
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 solucin es la ptima? Por qu?
RLG
Tienen razn. Es ptima porque ya no contiene ndices negativos.
La solucin ptima ser entonces:
Enviar:
100 unidades de la fbrica de Des Moines al almacn de Albuquerque.
200 " " " " " Evansville " " " Boston.
100 " " " " " " " " " Cleveland.
200 " " " " " Fort Lauderdale " " Albuquerque.
100 " " " " " " " " " Cleveland.
Siendo el costo total de transporte: $3,900.00
RLG
EJERCICIO CLASE -PROBLEMA DE TRANSPORTE
La compaa Transportes de Granos SAC, enva camiones cargados de grano desde tres silos a
cuatro molinos. La oferta y la demanda, junto con los costos del transporte por carga de camin en
las diferentes rutas, se resumen en la siguiente tabla, en donde la oferta y la demanda vienen dadas
en trminos de camiones cargados y los costos en cientos de $.
MOLINO 1 MOLINO 2 MOLINO 3 MOLINO 4 OFERTA
SILO 1 10 2 20 11 15
SILO 2 12 7 9 20 25
SILO 3 4 14 16 18 10
DEMANDA 5 15 15 15
Determine qu cantidad de camiones, xij , hay que enviar desde cada silo i a cada molino j para
conseguir que el costo total del transporte sea lo menor posible.
Graficar la RED de transporte, Formular el problema como un problema de Programacin Lineal y
resolver con el mtodo de la esquina Nor Oeste y luego optimice con Lingo.
RLG
EJERCICIO CLASE -PROBLEMA DE TRANSPORTE
MODEL: RLG
!Problema de transporte con 6 almacenes y 8
tiendas: MODELO COMPACTO DE LINGO;
Sets:
almacenes: capacidad;
tiendas: demanda;
Links (almacenes, tiendas): costo, volumen;
end sets
!DATOS;
almacenes = A1 A2 A3 A4 A5 A6;
tiendas = T1 T2 T3 T4 T5 T6 T7 T8;
!valores de atributos;
capacidad = 60 55 51 43 41 52;
demanda = 35 37 22 32 41 32 43 38;
costo = 6 2 6 7 4 2 5 9
4 9 5 3 8 5 8 2
5 2 1 9 7 4 3 3
7 6 7 3 9 2 7 1
2 3 9 5 7 2 6 5
5 5 2 2 8 1 4 3;
enddata
RLG
!funcion objetivo;
Min @sum(Link(i,j):
costo(i,j)*volumen(i,j));
!Restricciones de demanda;
@for tiendas(j):
@sum
(almacenes(i):volumen(i,j)=demanda(j));
!Restricciones de capacidad oferta;
@for (almacenes(i):
@sum(tiendas(j):volumen(i,j)<=
capacidad(i));
end
RLG
Mtodo MODI (Distribucin Modificada)
Consiste en determinar los costos de oportunidad mediante la relacin:
(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 bsicas).
Una vez calculados todos los valores R y K, se procede a encontrar los
costos de oportunidad (c z) correspondientes a las variables no-bsicas
(casillas vacas) con relacin mencionada; El resto es como en el mtodo
"Stepping Stone o Salto de Piedra.
RLG
Tomemos de nuevo el ejemplo con distribucin 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
Lauderdale 100 200 300
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
RLG
Ahora, con K1, se podrn 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
Lauderdale 100 200 300
700
Demanda 300 200 200
700
Entonces: R2 = c21 K1 = 8 - 5 = 3
RLG
Correcto! Dedujeron bien: Ahora encontramos el valor de K2 por medio de la casilla
asignada 2,2. Cul 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
Lauderdale 100 200 300
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.
RLG
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
Lauderdale 100 200 300
700
Demanda 300 200 200
700
Obsrvese que los costos de oportunidad corresponden exactamente a los que se
Lo que siguecon
encontraron ahora es encontrar
el mtodo los ndices
de la esquina de las casillas vacas y determinar si la
N-O.:
solucin es ptima con la relacin: (cij zij) = cij Ri - Kj
(c12 z12) = 3; (c13 z13) = 4; (c23 z23) = 1 y (c31 z31) = - 2
RLG
Lo anterior nos indica, al igual que con el mtodo 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 solucin:
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
RLG
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 vacas 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
RLG
Igual que en el mtodo Stepping stone, la variable de entrada es x23 y la de salida es x21.
La nueva solucin 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
RLG
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
RLG
Puesto que no existen negativos en los ndices, la solucin es
ptima, y es exactamente la misma a la que se lleg por el mtodo
Stepping Stone:
Enviar:
100 unidades de la fbrica de Des Moines al almacn de Albuquerque.
200 " " " " " Evansville " " " Boston.
100 " " " " " " " " " Cleveland.
200 " " " " " Fort Lauderdale " " Albuquerque.
100 " " " " " " " " " Cleveland.
Siendo el costo total de transporte: $3,900.00
RLG
Mtodo de Vogel o Aproximacin de
Vogel
Este modelo esta relacionado a la bsqueda de una posible solucin
optima realizando aproximaciones.
El resultado de este mtodo es una solucin inicial factible, que
servir como entrada para ser evaluada por otro modelo el cual vera
si esta es la mejor solucin.
RLG
Aproximacin de Vogel
RLG
Pasos del Mtodo
1. Determinar para cada fila y columna una medida de penalizacin
restando los dos costos menores en filas y columnas que es la
diferencia no negativa entre los 2 ms pequeos costos de
embarque asociados con las variables no asignadas en ese rengln
y en esa columna, le llamaremos Costo de Oportunidad.
RLG
Pasos de Mtodo
2. Escoger la fila o columna con la mayor penalizacin,
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 penalizacin
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.
RLG
Ejemplo Aproximacin Vogel
RLG
Ejemplo Aproximacin Vogel
RLG
Ejemplo Aproximacin Vogel
RLG
Ejemplo Aproximacin Vogel
RLG
Ejemplo Aproximacin Vogel
RLG
Ejemplo Aproximacin Vogel
RLG
Ejemplo Aproximacin Vogel
RLG
Ejemplo Aproximacin Vogel
RLG
Ejemplo Aproximacin Vogel
RLG
Ejemplo Aproximacin Vogel
RLG
GRACIAS
Lo ms importante no siempre es el
cmo empiezas, sino el cmo terminas.
Ricardo Lpez Guevara
