05/10/2014
Investigacin de
Operaciones I
Ing. Enrique M. Avendao Delgado
eavendano@[Link]
Unidad 1
PROGRAMACION LINEAL
Ing. Enrique M. Avendao Delgado
eavendano@[Link]
05/10/2014
Definicin:
El Problema de Transporte corresponde a un tipo particular de un problema
de programacin lineal. Si bien este tipo de problema puede ser resuelto por
el mtodo Simplex, existe un algoritmo simplificado especial para resolverlo.
El modelo de transporte se define como una tcnica que determina un
programa de transporte de productos o mercancas desde unas fuentes hasta
los diferentes destinos al menor costo posible.
Fuentes:
i
a1
Destinos j
xij : c ij
b1
Unidades
de
Demanda
Unidades
de Oferta
a2
b2
am
bn
xmn : c mn
Ing. Enrique Avendao Delgado
Procter & Gamble (P & G)
Procter & Gamble (P & G) produce y comercializa ms de 300 marcas de productos a nivel
mundial. Esta compaa ha crecido continuamente a travs de su larga historia que data
desde 1830. Para mantener y acelerar ese crecimiento, un importante estudio de IO se
realiz para fortalecer la efectividad global de P & G. Antes del estudio, la cadena de
suministro de la compaa consista en cientos de proveedores para las 50 categoras de
productos en 60 plantas, 15 centros de distribucin y ms de 1 000 zonas de consumo. Sin
embargo, en la medida en que la compaa consider marcas globales, la administracin se
percat de que se requera consolidar las plantas a fi n de reducir los gastos de manufactura,
mejorar la velocidad de entrega al mercado y reducir la inversin de capital. Por lo cual, el
estudio se enfoc al rediseo del sistema de produccin y distribucin de la compaa para
sus operaciones en Norteamrica. El resultado fue una reduccin del nmero de plantas en
Norteamrica de casi 20 por ciento, ahorrando ms de 200 millones de dlares en costos
antes de impuestos por ao.
Gran parte del estudio consisti en la formulacin y solucin de problemas de transporte de
categoras individuales de producto. Para cada opcin referente a mantener abiertas ciertas
plantas, la solucin del correspondiente problema de transporte para cierta categora de
producto mostr cul sera el costo de distribucin para enviar dicha categora de producto
desde esas plantas hacia los centros de distribucin y zonas de consumo.
Ing. Enrique Avendao Delgado
05/10/2014
Ejemplo
Uno de los productos ms importantes de la P & T COMPANY es el chcharo enlatado. Los chcharos se
preparan en tres enlatadoras cercanas a Bellingham, Washington; Eugene, Oregon, y Albert Lea,
Minnesota y despus se envan por camin a cuatro almacenes de distribucin Sacramento,
California; Salt Lake City, Utah; Rapid City, South Dakota, y Albuquerque, Nuevo Mxico en el oeste de
Estados Unidos, como se muestra en la figura 1. Debido a que los costos de embarque constituyen un
gasto importante, la administracin ha iniciado un estudio para reducirlos a su mnima expresin. Se ha
estimado la produccin de cada enlatadora durante la prxima temporada y se ha asignado a cada
almacn cierta cantidad de la produccin total de chcharos. En la tabla 2 se proporciona esta
informacin en unidades de carga de camin, junto con el costo de transporte por camin cargado
de cada combinacin de enlatadora-almacn. Como se ve, hay un total de 300 cargas de camin que se
deben transportar. El problema es determinar el plan de asignacin de estos embarques a las distintas
combinaciones de enlatadora-almacn que minimice el costo total de transporte.
Costo de embarque ($) por carga
Almacn
1
464
513
654
867
75
Enlatadora 2
352
416
690
791
125
995
682
388
685
100
80
65
70
85
Asignacin
Produccin
Ing. Enrique Avendao Delgado
Ejemplo
Ing. Enrique Avendao Delgado
05/10/2014
Ejemplo
Ing. Enrique Avendao Delgado
Formulacin con Programacin Lineal
En realidad, el problema descrito en la fi gura 8.2 es de programacin lineal del tipo
de los problemas de transporte. Para formularlo, sea Z el costo total de transporte y
sea xij (i 5 1, 2, 3; j 5 1, 2, 3, 4) el nmero de cargas de camin enviadas de la
enlatadora i al almacn j. El objetivo es seleccionar valores de estas 12 variables
de decisin (las xij)
F.O: Min Z= 464x11 + 513x12 + 654x13 + 867x14 + 352x21 + 416x22 +
690x23 + 791x24 + 995x31 + 682x32 + 388x33 + 685x34
s.a.
x11 + x12 + x13 + x14 = 75
x21 + x22 + x23 + x24 = 125
x31 + x32 + x33 + x34 = 100
x11 + x21 + x31 = 80
x12 + x22 + x32 = 65
x13 + x23 + x33 = 70
x14 + x24 + x34 = 85
xij 0 (i 1, 2, 3; j 1, 2, 3, 4).
Ing. Enrique Avendao Delgado
05/10/2014
Modelo del Problema de Transporte
Para describir el modelo general del problema de transporte es necesario emplear
trminos mucho menos especficos que los que se usaron para designar los
componentes del ejemplo prototpico. En particular, el problema general de
transporte se refiere en sentido literal o figurado a la distribucin de cualquier
mercanca desde cualquier grupo de centros de suministro, llamados orgenes, a
cualquier grupo de centros de recepcin, llamados destinos, de tal manera que se
minimicen los costos totales de distribucin.
Ing. Enrique Avendao Delgado
Uso de Excel para formular y resolver
problemas de transporte
El proceso de usar una hoja de clculo para formular un modelo de
programacin lineal para un problema comienza por definir las respuestas
a tres preguntas. Cul es la decisin que se tomar? Cules son las
restricciones sobre estas decisiones? Cul es la medida global de
desempeo de estas decisiones?
Ing. Enrique Avendao Delgado
05/10/2014
Ejercicio 2
La Compaa Childfair tiene tres plantas de produccin de carros para bebs que deben
distribuirse a cuatro centros de distribucin. Las plantas 1, 2 y 3 producen 34, 25 y 11
cargamentos por mes, respectivamente. Cada centro de distribucin necesita recibir :
Centro1, 15 cargamentos por mes, Centro2, 20 cargamentos por mes; Centro3, 15
cargamentos por mes y la diferencia para el centro4. En la siguiente tabla se da la distancia
de cada planta a su respectivo centro de distribucin:
El costo del flete de cada
embarque es de $100
ms 0.50 centavos
por milla.
Cunto se debera
embarcar a cada centro
de distribucin para
minimizar el costo total
del envo?
Distancia (millas)
Centro de distribucin
Planta
800
1300
400
700
1100
1400
600
1000
600
1200
800
900
a) Formule el problema como uno de transporte mediante la elaboracin
de una tabla de parmetros apropiada.
b) Trace la representacin de red de este problema.
c) Obtenga una solucin ptima. (Usando Solver de excel)
Ing. Enrique Avendao Delgado
Ejercicio 3
Una empresa de camiones enva camiones cargados de grano desde tres
silos a cuatro molinos. La oferta (en camiones cargados) y la demanda
(tambin en camiones cargados), junto con los costes de transporte por carga
de camin en las diferentes rutas se resumen en el modelo de transporte
siguiente. Los costos de transporte por unidad, cij, son en cientos de euros.
Determinar el costo mnimo del programa de envo entre los silos y los
molinos. Utilice Solver de Excel para encontrar la solucin.
Molinos
Oferta
10
20
11
15
Silos 2
12
20
25
14
16
18
10
Demanda
15
15
15
Ing. Enrique Avendao Delgado
05/10/2014
Mtodos de solucin:
Los mtodos ms empleados para obtener soluciones iniciales son:
El mtodo de la Esquina Noroeste.
El mtodo del Costo Mnimo.
El Mtodo Vogel.
Ing. Enrique Avendao Delgado
METODO ESQUINA NOROESTE
Ing. Enrique Avendao Delgado
05/10/2014
Mtodo Noroeste
Para encontrar una solucin inicial se comienza por la esquina superior izquierda
(noroeste) del tablea de transporte intentando asignar la mxima cantidad
posible a x11. Evidentemente, el valor mximo de x11 debe ser el menor entre
s1 y d1. Si x11 = s1, se puede descartar la primera fila, pues ya no podra
asignarse ms desde el primer punto de oferta, se avanza a la siguiente fila. Al
mismo tiempo, se debe cambiar d1 por d1-s1, de forma de indicar la cantidad
de demanda no satisfecha en el primer punto de demanda. En caso que x11 =
d1, se debe descartar la primera columna y cambiar s1 por s1-d1, avanzando
una columna. Si x11 = d1 = s1, se debe avanzar en una columna o en una fila
(pero no en ambas). Se asigna un cero en la direccin escogida y se descarta
la otra alternativa.
El mtodo continua aplicando el mismo criterio desde la esquina noroeste del
tablero restante. Una vez que estn asignadas toda de demanda y oferta
disponible, se terminan las asignaciones y est completa la asignacin inicial.
Ing. Enrique Avendao Delgado
Mtodo Noroeste
Costo Total: 75*464 + 5*352 + 65*416 + 55*690 + 15*388 + 85*685
Costo Total: 165595
Ing. Enrique Avendao Delgado
05/10/2014
Ejercicio 2
Hacer una distribucin utilizando el mtodo de la esquina noroeste:
Brasil
EEUU
Italia
22
Per
30
Mxico
24
10
8500
Alemania
30
10
32
25
Espaa
24
12
22
15
11700
14000
Japn
24
25
18
20
10000
12700
15000
5000
11500
Ing. Enrique Avendao Delgado
Brasil
EEUU
Italia
Per
Mxico
22
30
24
10
30
10
32
25
8500
Alemania
8500
4200
Espaa
7500
24
12
7500
Japn
24
22
5000
25
11700
750
0
14000
650
0
15
1500
18
150
0
20
10000
1270
0
15000
5000
11500
4200
7500
10000
10000
Costo: 810500
Ing. Enrique Avendao Delgado
05/10/2014
METODO DEL COSTO MINIMO
Ing. Enrique Avendao Delgado
Costo mnimo:
Caractersticas:
Es ms elaborado que el mtodo de la esquina
noroeste
Tiene en cuenta los costos para hacer las
asignaciones
Generalmente nos deja alejados del ptimo
Ing. Enrique Avendao Delgado
10
05/10/2014
Costo mnimo:
Pasos:
1. Construya una tabla de disponibilidades, requerimientos y costos
2. Empiece en la casilla que tenga el menor costo de toda la tabla, si hay
empate, escoja arbitrariamente (Cualquiera de los empatados).
3. Asigne lo mximo posible entre la disponibilidad y el requerimiento (El menor
de los dos).
4. Rellene con ceros (0) la fila o columna satisfecha y actualice la
disponibilidad y el requerimiento, restndoles lo asignado.
Nota: Recuerde que no debe eliminar satisfacer fila y columna al mismo
tiempo, caso en que la oferta sea igual a la demanda, en tal caso recuerde
usar la (Epsilon).
5. Muvase a la casilla con el costo mnimo de la tabla resultante (Sin tener en
cuenta la fila o columna satisfecha).
6. Regrese a los puntos 3,4,5 sucesivamente, hasta que todas las casillas
queden asignadas.
Ing. Enrique Avendao Delgado
Costo mnimo:
Costo Total: 80*352 + 20*513 + 45*682 + 70*388 + 55*867 + 30*685
Costo Total: 152535
Ing. Enrique Avendao Delgado
11
05/10/2014
Costo mnimo:
100
45
77
45
7000
90
35
90
70
2500
78
50
60
110
1500
45
65
56
130
3000
4500
2500
3800
3200
Ing. Enrique Avendao Delgado
METODO VOGEL
Ing. Enrique Avendao Delgado
12
05/10/2014
Mtodo Vogel:
El mtodo comienza calculando por cada columna y por cada fila el
castigo o penalidad. El castigo se calcula como la diferencia entre los
dos costos menores en la columna o en la fila segn corresponda. A
continuacin, se determina la fila o columna con un mayor valor de
castigo. Luego, se selecciona como variable basal la celda con menor
costo de la fila o columna, segn corresponda, y se le asigna la
mxima cantidad posible. Una vez realizada la asignacin, se descarta
la fila o columna cuya oferta o demanda haya sido completa. Se
recalcula la demanda u oferta disponible en la fila o columna. La
primera asignacin se ha completado.
Se vuelven a calcular los castigos por fila y por columna y se repite el
procedimiento descrito hasta completar las asignaciones posibles en el
tablero. La ventaja del mtodo de Vogel por sobre el de la Esquina
Noroeste es que va adelante algunas iteraciones y por lo tanto se
obtiene una solucin inicial mejor. Eventualmente puede ocurrir que
aplicando el mtodo se llegue directamente a la solucin ptima.
Ing. Enrique Avendao Delgado
Mtodo Vogel
Ing. Enrique Avendao Delgado
13
05/10/2014
Mtodo Vogel
Ing. Enrique Avendao Delgado
Mtodo Vogel
Ing. Enrique Avendao Delgado
14
05/10/2014
Mtodo Vogel
Ing. Enrique Avendao Delgado
Mtodo Vogel
Ing. Enrique Avendao Delgado
15
05/10/2014
Mtodo Vogel:
Chiclayo
100
Trujillo
65
Chimbote
50
Puno
125
Lima
7000
130
100
90
70
Arequipa
2500
20
80
100
150
70
70
100
160
Piura
1500
Cajamarca
3000
4500
2500
3800
3200
Ing. Enrique Avendao Delgado
PROBLEMAS
Material:
Papel
Lapicero
Calculadora
Ing. Enrique Avendao Delgado
16
05/10/2014
Ejercicio 1:
La compaa Deltron produce su producto lder en tres fbricas
diferentes, los cuales se envan por camin a cuatro bodegas de
distribucin las cuales se encargan de su venta.
La produccin por fbrica es la siguiente (se utiliza como unidad de
medida camiones de producto) La capacidad de cada bodega es la siguiente
Fbrica
Produccin
(camiones)
75
125
100
Total
300
(se utiliza como unidad de medida camiones
de producto):
Bodega
Capacidad
(camiones)
80
65
70
85
Total
300
Ing. Enrique Avendao Delgado
Ejercicio 1:
Los costos asociados a enviar productos desde las diferentes
fabricas a las bodegas, es el siguiente:
Fbrica
Bodega 1
Bodega 2
Bodega 3
Bodega 4
$ 464
$ 513
$ 654
$ 867
$ 352
$ 416
$ 690
$ 791
$ 995
$ 682
$ 388
$ 685
Resolverlo utilizando los tres mtodos:
1. El mtodo de la Esquina Noroeste.
2. El mtodo del Costo Mnimo.
3. El Mtodo Vogel
Ing. Enrique Avendao Delgado
17
05/10/2014
Ejercicio 2:
Una aerolnea regional puede comprar su combustible para jet a cualquiera de tres
proveedores. Las necesidades de la aerolnea para el prximo mes, en cada uno de
los tres aeropuertos a los que da servicio, son 200 galones en el aeropuerto 1. 230 en
el aeropuerto 2, y 350 galones en el aeropuerto 3. Cada proveedor puede suministrar
combustible a cada aeropuerto a los precios que se dan en el siguiente cuadro:
Cada proveedor, sin embargo,
tiene limitaciones en cuanto al
nmero total de galones que
puede proporcionar durante un
mes dado.
Estas capacidades son 320 para
el proveedor 1. 270 galones
para el proveedor 2 y 190 para
el proveedor 3.
Determine una poltica de
compra que cubra los
requerimientos de la aerolnea
en cada
Aeropuerto 1
Aeropuerto 2
Aeropuerto 3
Proveedor 1
92
89
90
Proveedor 2
91
91
95
Proveedor 3
87
90
92
aeropuerto, a un costo mnimo. Cual es el costo de esa poltica
de compra.
Resolverlo utilizando el mtodo de Vogel
Ing. Enrique Avendao Delgado
Ejercicio 3:
El gobierno de Estados Unidos est subastando contratos de arrendamientos
de petrleo en dos sitios 1 y 2. En cada sitio, se subastan 100 000 acres de
tierra. Cliff Erwing, Blake Barnes y Alexis Pickens llevan a cabo licitaciones para
el petrleo. Las reglas del gobierno establecen que ningn licitador puede
recibir ms de 40% de la tierra que esta siendo subastada. Cliff oferto $ 1
000/acre para el suelo del sitio 1 y $ 2 000/acre para el suelo del sitio 2. Blake
ofreci $ 900/acre para el suelo del sitio 1 y $2 200/acre para el suelo del sitio
2. Alexis ofert $1 100/acre para el sitio 1 y $ 1 900/acre para el sitio 2. Formule
un modelo de transporte equilibrado para maximizar el ingreso del gobierno.
Ing. Enrique Avendao Delgado
18
05/10/2014
19