Download - Trabajo Invope 2 Dd
UNIVERSIDAD NACIONAL DE
TRUJILLO
“PROBLEMAS DE DINAMICA”
CURSO:
INVOPE II
DOCENTE:
Marcos Baca
INTEGRANTES:
BURGOS DIONICIO, ALEX JOHEL
IDROGO ZAVALETA, SANTIAGO
OJEDA NAMOC, FERNANDO
CICLO:
VII
TRUJILLO - PERÚ
2013
Facultad de Ingeniería Escuela Profesional deEscuela Profesional de Ingeniería de SistemasIngeniería de Sistemas
PROGRAMACIÓN DINÁMICA DETERMINISTICA
PROBLEMA01
Soy un excursionista.- El último verano fui con mi amiga a un viaje de acampar y caminar en las bellas montañas blancas de Nueva Hampshire. Decidimos limitar nuestras caminatas en un área formada por 3 cumbres bien conocidas: los montes Washington, Jefferson y Adams. El monte Washington tiene una vereda de 6 millas de la base a la cumbre. Las veredas correspondientes para los montes Jefferson y Adams tiene 4 y 5 millas respectivamente.- Los caminos que unen las bases de las 3 montañas tiene 3 millas entre los montes Washington y Jefferson, 2 millas entre los montes Jefferson y Adams, y 5 millas entre los montes Washington y Adams. Iniciamos el primer día en la base del monte Washington y regresamos al mismo lugar al final de los 5 días.- Nuestra meta era caminar todas las millas que pudiéramos. También decidimos subir exactamente a una montaña cada día y acampar en la base en la que subiremos al día siguiente, además decidimos no visitar la misma montaña 2 días consecutivos. ¿Cómo programamos nuestro recorrido?
SOLUCION
a) Función Objetivo: Maximizar Distancia (Hallar el camino más largo)b) Número de Etapas: 5c) Estado: Origen Sn (i)d) Variable Decisión: Destino Xn (j)
DESARROLLO
FASE 5
ORIGEN(i)
DESTINO (j) W Solución Optima
2*vereda + camino F5(i) DecisiónAJ
2*5 + 5 = 152*4 + 3 = 11
1511
WW
FASE 4
ORIGEN(i)
DESTINO (j)W A J Solución Optima
2*vereda + camino + F5(i)
2*vereda + camino + F5(i)
2*vereda + camino + F5(i)
F4(i) Decisión
WAJ
–2*5 +5 + 0 = 152*4 +3 + 0 = 11
2*6 + 5 + 15 = 32–
2*4 + 2 + 15 = 25
2*6 + 3 + 11 = 222*5 + 2 + 11 = 23
–
322325
AJA
FASE 3
ORIGEN(i)
DESTINO (j)W A J Solución Optima
2*vereda + camino + F4(i)
2*vereda + camino + F4(i)
2*vereda + camino + F4(i)
F3(i) Decisión
WAJ
–2*5 +5 +32 = 472*4 +3 +32 = 43
2*6 + 5 + 23 = 40–
2*4 + 2 + 23 = 33
2*6 + 3 + 25 = 402*5 + 2 + 25 = 37
–
404743
A , JWA
FASE 2
ORIGEN(i)
DESTINO (j)W A J Solución Optima
2*vereda + camino + F3(i)
2*vereda + camino + F3(i)
2*vereda + camino + F3(i)
F2(i) Decisión
AJ
2*5 +5 +40 = 552*4 +3 +40 = 51
–2*4 + 2 + 47 = 57
2*5 + 2 + 43 = 55–
5557
W , JA
FASE 1
ORIGEN(i)
DESTINO (j)
W A JSolución Optima
2*vereda + camino + F2(i)
2*vereda + camino + F2(i)
F1(i) Decisión
W – 2*6 + 5 + 55 = 72 2*6 + 3 + 57 = 72 72 A , J
La cantidad máxima de millas que puede caminar es de 72 millas entre las 3 montañas
RUTA:
DÍA 1 DÍA 2 DÍA 3 DÍA 4 DÍA 5
FUNCION RECURSIVA:
f (i )=Max(2¿ V i+di→ j +f n +1¿ ( j))
PROBLEMA 02
Fin base W
W
J
W
A
J
A
J
W
A
J
A
W
Cierto estudiante desea destinar los siete días de la semana próxima a estudiar 4 cursos. Necesita al menos un día para cada curso y el puntaje que puede lograrse se da en la siguiente tabla:
CURSO – etapa n
decisiòn I II III IV1 13 15 12 W14 = 162 15 15 14 173 16 16 17 184 17 19 18 19
Solución:
1. Función Objetivo : Maximizar Puntaje2. Número de Etapas: 4 (Cursos)3. Estado : Días Disponibles (Sn) (0,1,2,3,4,5,6,7)4. Variable Decisión: Días Asignados (Xn) (1,2,3,4)
FORMULA GENERAL DE PROGRAMACIÓN DINÁMICA:
f n ( Sn , X n )=( Max ó Min) {f (n+1)¿ (Sn+1)}
Objetivos del problema: Determinar cuántos días se debe asignar a cada curso Determinar la función recursiva del modelo
ETAPA 4
Asignados
Variable de Decisión : X4
Max. Punt. F4*
Mejor Dec. X4*
ESTADO: S4 1 2 3 4
Disponible1 16 16 12 17 - - 17 23 18 - 18 34 19 19 4
Como ya se empleó un día en la etapa anterior ,restamos 1 a los días disponibles
ETAPA 3
Asignados
Variable de Decisión : X3 Max.
Punt.f*
Mejor Dec. X*
ESTADO: S3 1 2 3 4
2(1)
W13+f*4(2-1)
12+16=28 - - - 28 1
3(2) 12+17=29W23+f*4(3-2)
14+16=30 - - 30 2
4(3) 12+18=30 14+17=3117
+16=33 - 33 3
5(4) 12+19=31 14+18=3217
+17=34 18+16=34 34 3,4
Como ya se emplearon 2 días en las etapas anteriores, restamos 2 a los días disponibles.
ETAPA 2 AsignadosVariable de Decisión: X2
Max. Punt. f*
Mejor Dec.X*
ESTADO S2 1 2 3 4
Disponibles 3(1) 15+28=43 - - - 43 1
4(2) 15+30=45 15+28=43 - - 45 15(3) 15+33=48 15+30=45 16+28=44 - 48 16(4) 15+34=49 15+33=48 16+30=46 19+28=47 49 1
En esta última etapa se puede ofrecer todo días disponibles
ETAPA 1 Asignado Variable de Decisión: X1
Max. Punt. f*
Mejor Dec.X*
ESTADO S1 1 2 3 4
Disponible 7 13+49=62 15+48=63 16+45=61 17+43=60 63 2
4 dispon. 3 dispon. 2 dispon. 1 dispon.
ETAPA DISPONIBLE
ASIGNADO
1 7 22 7-2=5 13 5-1=4 34 4-3=1 1
Formula Generalf n ( Sn , X n )=( Max ó Min) {f (n+1)
¿ (Sn , Xn)}Si Sn−Xn∈ f (n+ 1)
¿ (Sn , Xn)
Entonces:f n ( Sn , X n )=( Max) {P(xn)
+ f (n+1)¿ (Sn−Xn) }
En caso contrario: No factiblef n(S) = Max { Wxn + f*n+1 (S-x)}
PROBLEMA 03:
Un vendedor vive en Bloomington y debe estar en Indianápolis el siguiente jueves. El lunes, martes y miércoles puede vender su mercadería en Indianápolis, Bloomington o Chicago, según su experiencia cree que puede ganar 12 dólares si se queda un día en Indianápolis 16 dólares si se queda un día en Bloomington y 17 dólares si se queda en Chicago. Para elevar al máximo sus ventas menos impuestos menos gastos de viaje ¿Dónde debe pasar los primeros tres días y noches de la semana? En la siguiente tabla se muestra los costos de viaje.
De AIndianápoli
sBloomington Chicago
Indianápolis - 5 2Bloomington 5 - 7
Chicago 2 7 -I=12
B=16
C=17
Solución:
a) Función Objetivo: Maximizar (Ganancia – Costo)b) Número de Etapas: 4c) Estado: Origen Sn
d) Variable Decisión: Destino Xn
Establecemos las Etapas:
Fase 1 : Domingo Fase 2 : Lunes Fase 3 : Martes Fase 4 : Miércoles
Fase 4:Miércoles
FUNCIÓN: F3 (S3) = Max [Ganancia - Costo (S3, X3)]
S3\X3 Indianápolis F3(S3) X3
Indianápolis 12 – 0 = 12 12 IndianápolisBloomingto
n12 – 5 = 7 7 Indianápolis
Chicago 12 – 2 = 10 10 Indianápolis
Fase 3:Martes
FUNCIÓN: F2 (S2) = Max [Ganancia - Costo (S2, X2) + F3 (X3)]
S2\X2 Indianápolis Bloomington Chicago F2(S2) X2
Indianápolis 12-0+12=24 16-5+7=18 17-2+10=25 25 ChicagoBloomingto
n12-5+12=19
16-0+7=23 17-7+10=2023 Bloomington
Chicago 12-2+12=22 16-7+7=16 17-0+10=27 27 Chicago
Fase 2: Lunes
FUNCIÓN: F1 (S1) = Max [Ganancia - Costo (S1, X1) + F2 (X1)]
S1\X1 Indianápolis Bloomington Chicago F1(S1) X1
Indianápolis 12-0+25=37 16-5+23=34 17-2+27=42 42 Chicago
Bloomington
12-5+25=3216-0+23=39 17-7+27=37
39 Bloomington
Chicago 12-2+25=35 16-7+23=32 17-0+27=44 44 Chicago
Fase 1: Domingo
FUNCIÓN: F0 (S0) = Max [Ganancia - Costo (S0, X0) + F1 (X0)]
S1\X1 Indianápolis Bloomington Chicago F1(S1) X1
Bloomington
12-5+42=4916-0+39=56 17-7+44=54
56 Bloomington
- Por tanto para poder obtener máximas ganancias el vendedor deberá de tener la siguiente agenda:
Lunes : Bloomington
Martes : Bloomington
Miércoles : Bloomington
Jueves : Indianápolis Ganancia Máxima = 56 dólares
EJERCICIO 4: Una empresa tiene los siguientes datos de demanda de su producto:
¿Cuántas unidades debe fabricar en el mes? Sabiendo que:
Durante el mes que se producen algunas unidades se incurre en un costo fijo de $30.
El costo variable es de $10 por cada unidad fabricada. Al final de cada mes se genera un costo de almacenamiento de $5 por cada
unidad. Las limitaciones de capacidad permiten una producción máxima de 5 unidades. El tamaño del almacén restringe un inventario final máximo de 4 unidades cada
mes. Se dispone de 0 unidades al principio del primer mes.
Características:
Se conoce la demanda de cada mes al principio del mes 1. Se debe determinar cuántas unidades deben producirse teniendo en cuenta
que la capacidad de fabricación es limitada. La demanda de cada período debe satisfacerse a tiempo con el inventario o la
producción actual. Durante cada período donde la producción tiene lugar se genera un costo fijo, así como un costo variable por unidad.
Mes Demanda
1 1
2 3
3 2
4 4
Se tiene capacidad limitada de almacenamiento. Se genera un costo de almacenamiento por unidad al inventario final de cada período.
El objetivo es minimizar el costo total por cumplir con la demanda de cada período.
Modelo de revisión periódica: El inventario se conoce al final de cada período, y se toma la decisión sobre la producción.
SOLUCIÓN
Sean:
xn : Nivel de producción en el mes n
yn : Inventario inicial en el mes n
dn : Demanda en el mes n
Costo de producción de xn unidades CP(xn) 30+10xn
Inventario en el siguiente mes yi+1 yi + xi - di
Costo de inventario de siguiente mes CI(yi+1) 5(yi + xi - di)
Función recursiva:
Costo mínimo de cumplir las demandas fn(sn ,xn) = min {CI(yn+1) + CP(xn) + fn+1(sn+1)}
Sn: disponibilidad de almacén
Etapa 4 (demanda=4)
s4
f4(s4,x4)=30+10x4 Solución óptima
x4 = x4 = 1 x4 = 2 x4 = 3 x4 = 4 f4*(s4) x4
*
0
0 - - - - 30+40
70 4
1 - - - 30+30
- 60 3
2 - - 30+20
- - 50 2
3 - 30+10
- - - 40 1
4 0+0 - - - - 0 0
Etapa 3 (demanda=2)
s3
f3(s3,x3)= 5(y3+x3-d3)+30+10x3+f4*(y3+x3-d3)
Solución
óptima
x3 = 0 x3 = 1 x3 = 2 x3 = 3 x3 = 4 x3 = 5 f3
*(s3)
x3
*
0 - - 0+50+70=1
20
5+60+60=1
25
10+70+50=
130
15+80+40=
135
120 2
1 - 0+40+70=1
10
5+50+60=1
15
10+60+50=
120
15+70+40=
125
20+80+0=1
00
100 5
2 0+0+70=
70
5+40+60=1
05
10+50+50=
110
15+60+40=
115
20+70+0=9
0
- 70 0
3 5+0+60=
65
10+40+50=
100
15+50+40=
105
20+60+0=8
0
- - 65 0
4 10+0+50
15+40+40=
20+50+0=7
- - - 60 0
=60 95 0
Etapa 2 (demanda=3)
s2
f2(s2,x2)= 5(y2+x2-d2)+30+10x2+f3*(y2+x2-d2)
Solución
óptima
x2 = 0 x2 = 1 x2 = 2 x2 = 3 x2 = 4 x2 = 5 f2
*(s2)
x2
*
0 - - - 0+60+120
=180
5+70+100
=175
10+80+70
=160
160 5
1 - - 0+50+120
=170
5+60+100
=165
10+70+70
=150
15+80+65
=160
150 4
2 - 0+40+120
=160
5+50+100
=155
10+60+70
=140
15+70+65
=150
20+80+60
=160
140 3
3 0+0+120=
120
5+40+100
=145
10+50+70
=130
15+60+65
=140
20+70+60
=150
- 120 0
4 5+0+100=
105
10+40+70
=120
15+50+65
=130
20+60+60
=140
- - 105 0
Etapa 1 (demanda=1)
s1 f1(s1,x1)= 5(y1+x1-d1)+30+10x1+f2
*(y1+x1-d1)
Solución
óptima
x1
x1 = 1 x1 = 2 x1 = 3 x1 = 4 x1 = 5 f1
*(s1
x
= 0
) 1*
0 - 0+40+160=
200
5+50+150=
205
10+60+140=
210
15+70+120=
205
20+80+105=
205
200 1
Respuesta:
Mes
Deben
producirse
(unids)
1 1
2 5
3 0
4 4
EJERCICIO 5: Un barco de 4 toneladas es cargado con uno o más de tres artículos, la tabla siguiente muestra el peso unitario pn, en toneladas y el ingreso por unidad in , en miles de $, para el artículo n. ¿Cómo se debe cargar el barco para maximizar los ingresos totales?
Como el peso unitario y el peso permisible son enteros, las variables sólo deben tener valores enteros.
Solución: Considerar a los estados como la capacidad aún disponible en el barco.
Etapa 3
s3
f3(s3,x3)=14x3 Solución óptima
x3 =0 x3 =1 x3 =2 x3 =3 x3 =4 f3*(s3) x3
*
0 14(0)=0
- - - - 0 0
1 - 14(1)=14 - - - 14 1
2 - - 14(2)=28 - - 28 2
3 - - - 14(3)=42
- 42 3
4 - - - - 14(4)=56 56 4
Etapa 2
s2
f2(s2,x2)=47x2+f3*(s2-3x2) Solución
óptima
x2 =0 x2 =1 f2*(s2) x2
*
0 47(0)+0=0 - 0 0
1 47(0)+14=14 - 14 0
2 47(0)+28=28 - 28 0
3 47(0)+42=42 47(1)+0=47 47 1
4 47(0)+56=56 47(1)+14=61 61 1
Etapa 1
s1
f1(s1,x1)=31x1+ f2*(s1-2x1) Solución
óptima
x1 =0 x1 =1 x1 =2 f1*(s1) x1
*
0 31(0)+0=0 - - 0 0
1 31(0)+14=14 - - 14 0
2 31(0)+28=28 31(1)+0=31 - 31 1
3 31(0)+47=47 31(1)+14=45 - 47 0
4 31(0)+61=61 31(1)+28=59 31(2)+0=62
62 2
Ingreso total= $ 62 000; llevar 2 unidades del artículo 1; peso acumulado = 4 toneladas
EJERCICIO 6: Un contratista constructor estima que la fuerza de trabajo necesaria durante las próximas 5 semanas será de 5, 7, 8, 4 y 6 trabajadores, respectivamente. La mano de obra en exceso que se conserve le costará $300 por trabajador semanalmente, y la nueva contratación en cualquier semana tendrá un costo fijo de $400 más $200 por trabajador y por semana. Sugiera un plan de contratación para minimizar los costos en los que se incurren.
Solución:
Sea xn la mano de obra asignada a cada semana.
Sea rn la mano de obra requerida para cada semana, entonces: r1 =5, r2 =7, r3 =8, r4 =4 y r5 =6
Costo de exceso de mano de obra: 300(xn – rn) cuando: xn > rn
Costo de contratación: 400 + 200(xn – sn) cuando: xn > sn
Etapa 5 (r5 = 6)
s5
f5(s5,x5)=300(x5 - 6)+[400+200(x5-s5)] Solución óptima
x5 =6 f5*(s5) x5
*
4 300(0)+[400+200(2)]=800 800 6
5 300(0)+[400+200(1)]=600 600 6
6 300(0)+[0]=0 0 6
Etapa 4 (r4 = 4)
s4
f4(s4,x4)=300(x4 - 4)+[400+200(x4-s4)]+f5*(x4) Solución
óptima
x4 =4 x4 =5 x4 =6 f4*(s4) x4
*
8 300(4)+[0]+800=2000
300(3)+[0]+600=1500
300(2)+[0]+0=600
600 6
Etapa 3 (r3 = 8)
s3
f3(s3,x3)=300(x3 - 8)+[400+200(x3-s3)]+f4*(x3) Solución
óptima
x3 =8 f3*(s3) x3
*
7 300(0)+[400+200(1)]+600=1200 1200 8
8 300(0)+[0]+600=600 600 8
Etapa 2 (r2 = 7)
s2
f2(s2,x2)=300(x2 - 7)+[400+200(x2-s2)]+f3*(x2) Solución
óptima
x2 =7 x2 =8 f2*(s2) x2
*
5 300(0)+[400+200(2)]+1200=2000
300(0)+[400+200(3)]+600=1600
1600 8
6 300(0)+[400+200(1)]+1200=1800
300(0)+[400+200(2)]+600=1400
1400 8
7 300(0)+[0]+1200=1200 300(0)+[400+200(1)]+600=1200
1200 7,8
8 300(1)+[0]+1200=1500 300(0)+[0]+600=600 600 8
Etapa 1 (r1 = 5)
s1
f1(s1,x1)=300(x1 - 5)+[400+200(x1-s1)]+f2*(x1) Solución
óptima
x1 =5 x1 =6 x1 =7 x1 =8f
1*(s1
)
x1
*
0
300(0)+[400+200(5)]
+1600=3000
300(0)+[400+200(6)]
+1400=3000
300(0)+[400+200(7)]
+1200=3000
300(0)+[400+200(8)]
+600=2600
2600
8
Plan de contratación: x1=8, x2=8, x3=8, x4=6, x5=6