SISTEMAS DE
PRODUCCION E
INVENTARIOS
Desarrollo
Richard Bellman
Nació en la ciudad de Nueva
York en 1920. Sus estudios se
desarrollaron en la universidad
de Brooklyn el después hizo una
maestría en la universidad de
Wisconsin. Durante la segunda
guerra mundial trabajo en el
Laboratorio nacional de los
Alamos en física teórica.
Bellman murió en 1984.
Un ratoncito desea comer queso
¿Podrías ayudarlo?
Ecuación
Recursiva
Programación Dinámica
• La programación dinámica es un método para
reducir el tiempo de ejecución de un algoritmo
mediante la utilización de subproblemas
superpuestos y subestructuras óptimas, se
utiliza para optimizar problemas complejos
que pueden ser discretizados y
secuencializados.
PROBLEMA DE RUTA CORTA
¿Cómo debe ser la ruta que le genera la
distancia mas corta?
Una compañía de aparatos electrónicos tiene un contrato para
entregar las cantidades siguientes de radios durante los tres meses
próximos: mes 1, 20; mes 2, 25; mes 3, 15 radios. Por cada radio
producido durante los meses 1 y 2 se genera un costo variable de 10
dólares; por cada radio fabricado durante el mes 3 se incurre en un
costo variable de 10 dólares. El costo de inventario es de 1.50 dólares
por cada radio en existencia al final del mes. El costo fijo durante un
mes es de 50 dólares así se produzca o no. Los radios fabricados en
el mes se pueden usar para cumplir con la demanda para ese mes o
para cualquier mes futuro. Suponga que la producción de cada mes
se realizan en lotes de 5. Dado que el nivel de inventario inicial es
unidades y la capacidad de almacen es de 5 unidades, utilice la
programación dinámica para determinar un plan de producción
óptimo.
Datos:
Mes 1 y 2: CV=10 $/radio
Mes 3: CV=12 $/radio
C. Inventario: 1.5 $/radio
C. Fijo: 250 $/mes
Producción: 0, 100, 200, 300, 400…..
800.
I. inicial = 0 radios
MES DEMANDA INVENTARIO FINAL
1 200 800-200=600
2 300 600-300=300
3 300 300-300=0
TOTAL 800
MES 2
0 600
MES 1 MES 3
200 800 0 300
* FUNCION: MAX INGRESOS
* ETAPAS: 3
* ESTADO i: Inventario
PRODUCCIÓN(X3) F3* x3
0 100 200 300
0 250 3850 300
+(300*12)=
3850
100 250+(200*12)+ 2650 200
(1,5*(200+100-
INVENTARIO(i) 300))=2650
200 250+(100*12)
+(1,5*(100+200-
300))=1450 1450 100
300 250+(0*12)+ 250 0
(1,5*(0+300-
300)=250
PRODUCCIÓN(X2)
0 100 200 300 400 50 60 F2* x2
0 0
0 250+300*1 4250 52 62 300
0 0=3250 50 50 3250
1 250+(200*10) 3400 4550 57
0 +(1,5*(200+1 00
I
0 00-
N
300))=2250 2250 200
V
E 2 1250 2400 250+300*1 4700
N 0 0+1,5*(30
T 0 0+200-
A 300)=3550 1250 100
R 3 250 1400 250+(200*10) 3700
I 0 +(1,5*(200+3
O 0 00-
300))=2550 250 0
4 250+(0*10)+ 1550 2700,0
0 (1,5*(0+400
0 -300))=400 400 0
5 550,0 250+(100*10
0 )+(1,5*(100+
0 500-
300))=1700 550 0
6 700
0
0 700 0
PRODUCCIÓN(X1)
200 300 400 500 600 700 800 F1* x1
0 250+(200* 250+(300*1 4550 5700 6850 8000 9150
INVENTARIO 10)+(1,5* 0)+(1,5*(30
(i) (200-0- 0-0-
200)=2250 200))=3400 2250 200
Fn(i)=CF + (CV*X)+(CI*(Xn+i-D)
Una compañía de construcción de semiremolques tiene un contrato
para entregar las cantidades siguientes cantidades durante los tres
meses próximos: mes 1, 4; mes 2, 3; mes 3, 4 unidades. Por cada
semiremolque producido durante los meses se genera un costo variable
de 500 dólares y se vende a 900 dólares. El costo de inventario es de
300 dólares por cada unidad en existencia al final del mes, pero si no se
cubre la demanda hay un costo de escasez de 200 dólares por unidad.
El costo fijo durante un mes es de 600 dólares así se produzca o no. La
capacidad de almacén es de cuatro unidades. Dado que el nivel de
inventario inicial es 1 unidades y la capacidad de producción es 3
unidades, utilice la programación dinámica para
determinar un plan de producción óptimo.
Un representante de ventas que vive en Bloomington y tiene q ir el próximo
jueves a Indianápolis.
Los Lunes, Martes y miércoles puede vender su mercancía en Indianápolis,
Bloomington o en Chicago.
De acuerdo con sus experiencias pasadas cree que puede ganar $12 si pasa
un día en Indianápolis
$16 si pasa un día en Bloomington y $17 si pasa un día en Chicago.
¿Dónde debe pasar el primero de los tres días y noches de la semana para
maximizar su ingreso por las ventas menos costos del viaje?
Costos del Viaje $
Indiana
De polis Bloomington Chicago
Indiana
polis - 5 2
Bloomi
ngton 5 - 7
Chicag
o 2 7 -
Chica
go 17 $/DIA
Bloomi
ngton 16 $/DIA
Indian
apolis 12 $/DIA
LUNES: LUNES MARTES MIERCOLES JUEVES
Partida
Indianápolis 2 Indianápolis
2 Indianápolis
5 5
Bloomingt 2
7 2 2 Indianap
on Chicago Chicago Chicago
olis
7 7
5
7
7
Bloomington Bloomington 5 Bloomington
5
MIERCOLES
ORIGEN DESTINO F(UTILIDAD - COSTO) J
Indianápolis Indianápolis 12-0+12=24 Indianápolis 12
Chicago Indianápolis 12-2+17=27 Indianápolis 7
Bloomington Indianápolis 12-5+16=23 Indianápolis 10
MARTES
ORIGEN DESTINO F(UTILIDAD - COSTO) J
Indianápolis Indianápolis 17-0+24=41 Chicago 24
Chicago 12-2+27=37 25
Bloomington 16-5+23=34 18
Chicago Indianápolis 12-2+24=34 22
Chicago 17-0+27=44 Chicago 27
Bloomington 16-7+23=32 16
Bloomington Indianápolis 12-5+24=31 19
Chicago 17-7+27=37 20
Bloomington 16-0+23=39 Bloomington 23
LUNES ESTADIA
ORIGEN DESTINO F(UTILIDAD - COSTO) J
Indianápolis Indianápolis 12-0+42=54 37
Chicago 17-2+44=59 Chicago 42
Bloomington 16-5+39=50 34
Chicago Indianápolis 12-2+42=52 35
Chicago 17-0+44=61 Chicago 44
Bloomington 16-7+39=50 32
Bloomington Indianápolis 12-5+42=49 32
Chicago 17-7+44=54 37
Bloomington 16-0+39=55 Bloomington 39
LUNES
PARTIDA
F(UTILIDAD -
ORIGEN DESTINO COSTO) J
Indianápolis 59-5=54 49
Bloomington Chicago 61-7=54 54
Bloomington 55-0=55 Bloomington 55
RECORRIDO:
Bloomington Bloomington Bloomington INDIANAPOLIS
LUNES MARTES MIERCOLES JUEVES
UTILIDAD NETA: 55 SOLES
La cantidad de delitos en cada una de las demarcaciones
policiacas de la ciudad depende del número de patrullas
asignadas a cada demarcación.
Se dispone de 5 patrullas. Determine con programación dinámica,
cuantas patrullas se deben asignar a cada demarcación.
Patrullas asignadas a la demarcación
Demarcación 0 1 2 3 4 5
1 14 10 7 4 1 0
2 25 19 16 14 12 11
3 20 14 11 8 6 5
Patrullas X1* f1*
0 0 14
1 1 10
2 2 7
3 3 4
4 4 1
5 5 0
(Solo Demarcación
X2* 2) i -X2*
Patrullas 0 1 2 3 4 5 f2*(i) X2* X1*
25+14=3
0 9 39 0 0
25+10=3
1 5 19+14=33 33 1 0
2 25+7=32 19+10=29 16+14=30 29 1 1
3 25+4=29 19+7=26 16+10=26 14+14=28 26 2 1
4 25+1=26 19+4=23 16+7=23 14+10=24 12+14=26 23 2 2
11+14=
5 25+0=25 19+1=20 16+4=20 14+7=21 12+10=22 25 20 2 3
X3* (Solo Demarcación 3) i -X2*
Patrullas 0 1 2 3 4 5 f3*(i) X3* X2* X1*
5 20+20=40 14+23=37 11+26=37 8+29=37 6+33=39 5+39=44 37 1 2 2
2 2 1
3 1 1
PROBLEMA 4 PAG.969
Debo viajar en mi automóvil desde Blomington hasta Cleveland.
Hay varios caminos (ver figura). El número en cada arco es el
tiempo que toma viajar de una ciudad a otra. Por ejemplo, se
requieren 3 horas para ir en automóvil desde Blomington hasta
Cincinnati. Determinar el camino más corto (en términos de
tiempo) de Blomington a Cleveland mediante el procedimiento
de ir hacia atrás.
4 7
3h 3h
1 Gary Toled Cleveland
o
2h 1h 5 3h
8
3h 2h
2 Indianapoli Dayton Columbu
s s
1h 2h 2.5h
6
3h
3 Blomington Cincinna
ti
Etapa 4
destino
inicio 7 F(4) j
4 3 3 4-8
8 3 3
Etapa 3
destino
inicio 4 8 F(3) j
1 6 6 4
el camino a seguir será el
5 4 5 4 4 siguiente para ahorrar horas
6 5,5 5,5 8
de viaje
Etapa 2
destino
inicio 4 8 F(3) j j
1 8 8 4 5
5 6 7,5 6 4 5
3-2-5-4-7
6 8 8 8 6
Etapa 1
destino
inicio 2 6 F(1) j
3 5 8 8 2