3 de examem
TRANSCRIPT
Programación dinámica determinista
Ejercicio 1
Una empresa ha contratado a 3 personas para 3 tareas. El máximo número de personas asignadas a una tarea son 2
La utilidad de los trabajadores en cada tarea es:
0 personas 1 persona 2 personasTarea A 0 3 8Tarea B 0 4 5Tarea C 0 5 7
¿Cuántas personas debo asignar a cada tarea para maximizar la utilidad?
Solución:
a) analisis
Etapa: la asignación de trabajadores a cada tarea
1º etapa(n=1) Asignación de trabajadores a la tarea A
2º etapa(n=2) Asignación de trabajadores a la tarea B
3º etapa(n=3) Asignación de trabajadores a la tarea C
Tenemos 3 tareas => definiremos 3 etapas.
Estados: nro. de trabajadores que aun puedo asignar a una etapa.
El estado siempre nos informa de algo que debemos conocer antes de tomar una decisión.
Estado en=0 No hay trabajadores disponibles en Tarea n
Estado en=1 Hay 1 trabajadores disponibles en Tarea n
Estado en=2 Hay 2 trabajadores disponibles en Tarea n
Estado en=3 Hay 3 trabajadores disponibles en Tarea n
Esto es debido a que hay 3 trabajadores para asignar desde el principio
Variable de decisión:
Como hay 3 etapas tendremos 3 variables de decisión que puede tomar el valor de 0, el valor de 1 y el valor de 2.
Xn=0 Asignar cero trabajadores en la tarea n
Xn=1 Asignar1 trabajadores en la tarea n
Xn=2 Asignar 2 trabajadores en la tarea n
Los valores posibles de una etapa dependen del valor del estado en esa etapa. Si estamos en la etapa 2 y el estado es me queda una persona por asignar no podre tomar la decisión de asignar 2 personas.
Fase de análisis:
ETAPA 3:
n=1
e1
X1X2
n=2
e2
n=3
e3
X3
n=1
e1
X1 X2 n=2
e2
n=3
e3
X3
Rendimiento n=3
F3 (e3, x3)
La función recurrente en la tercera etapa solo hará referencia a la tercera etapa ya que no hay nada después de ella.
j
i 0 personas
1 persona
2 personas
Personas optimo
Rendimiento optimo f*
0 personas
0 - - 0 0
1 personas
0 5 - 1 5
2 personas
0 5 7 2 7
3 personas
0 5 7 2 7
Si tenemos 0 personas por asignar y asignamos cero personas entonces la utilidad será cero.
Si tenemos 0 personas por asignar es imposible asignar 1 o 2 personas
Si tenemos 1 persona por asignar y asignamos 0 personas
Si tenemos 1 persona por asignar y asignamos 1 persona la utilidad será 5
Estados posibles en la etapa 3
Valores posibles de la variable de decisión en la etapa 3
ETAPA 2:
F2 (e2,x2)=rendimiento(x2)+f3*(e2-x2)
La función recurrente de la etapa 2 es igual a la utilidad de la etapa 2 más la utilidad de las etapas posteriores
El estado de una etapa= estado de la etapa anterior menos la variable de decisión de la etapa anterior.
Ejemplo: si tengo 3 personas por asignar e=3 y asigno a dos personas x=2 el nro de personas que podre asignar será su diferencia en este caso igual a 1
0 personas
1 persona
2 personas
Personas optimo
Rendimiento optimo f*
0 personas
0+0 - - 0 0
1 personas
0+5 4+0 - 0 5
2 personas
0+7 4+5 5+0 1 9
3 personas
0 4+7 5+5 1 11
En el ejemplo:
Si tenemos 1 persona por asignar y asignamos cero personas obtendremos un beneficio de 0 utilidades. Nos quedaría una persona por asignar en la siguiente etapa. Vayamos a la tercera etapa. Si nos
n=1
e1
X1 X2 X3 n=2
e2
n=3
e3
queda una persona por asignar lo mejor es asignar una persona y obtendremos un beneficio de 5 utilidades.
Etapa 1:
F1(e1,x1)=rendimiento(x1)+f2*(e1-x1)
0 personas
1 persona
2 personas
Personas optimo
Rendimiento optimo f*
3 personas
0+11 3+9 8+5 2 13
Solo tenemos 1 estado posible:
E1=3 ya que al inicio tenemos 3 personas por asignar.
b) Decisión:
La utilidad obtenida en la etapa 1 es el rendimiento optimo acumulado es 13.
En la primera etapa debemos asignar es 2 personas.
Como hemos asignado 2 personas en la primera etapa nos quedara una persona para asignar en la segunda etapa. En la etapa dos el nro de personas a asignar es cero personas. Ahora nos quedara para asignar 1 persona en la tercera etapa., entonces debemos de asignar una persona en la etapa 3.
Solución:
Rendimiento máximo=13
Tarea A=2 personas
Tarea B=0 personas
Tarea C=1 persona
Funcion:
Fn(ei,xi)=Max{U(xi) + f(n+1)*(ei-xi)} , ei=e1,e2,e3; xi=x0,x1,x2
Ejercicio 2
CASO:
La empresa Acme Manufacturing debe determinar la política óptima, durante los próximos 4 años, de reemplazo de una máquina, que en la actualidad tiene 3 años. La siguiente tabla muestra los datos del problema. La empresa ha establecido que toda máquina que tenga 6 años de edad debe reemplazarse. El costo de una nueva máquina es de $100’000.
Tiempo, t
(años)
Ingreso, r(t) ($)
Costo de Operación, c(t)
($)
Valor de recuperación, s(t)
($)
0 20’000 200 ----
1 19’000 600 80’000
2 18’500 1200 60’000
3 17’200 1500 50’000
4 15’500 1700 30’000
5 14’000 1800 10’000
6 12’200 2200 5’000
La determinación de los valores factibles de la edad de la máquina en cada etapa requiere de algo de ingenio. En la figura se asume la red que presenta el problema. Al iniciar el año 1 se tiene una máquina de 3 años de antigüedad. Se puede reemplazarla (R) o conservarla (K) durante otro año. Al iniciar el año 2, si hay reemplazo, la máquina nueva tendrá 1 año de edad; en caso contrario, la máquina actual tendrá 4 años de antigüedad. Los mismos razonamientos se aplican al iniciar los años 2 a 4. Si se reemplaza una máquina con un año de antigüedad, al iniciar el año 2 y 3, su reposición tendrá un año de antigüedad al inicio del siguiente año. También, al iniciar el año 4, se debe reemplazar una máquina con 6 años de servicio, y al final del año 4 se desechan todas las máquinas, con recuperación S.
SOLUCION:
Podemos ver en la red que al comenzar el año 2, las edades posibles de la máquina son 1 y 4 años. Para el comienzo del año 3, las antigüedades posibles son 1, 2 y 5años, y para el comienzo del año 4, las antigüedades posibles son 1, 2, 3 y 6.
OBJETIVO: Maximizar las ganancias obtenidas por el uso y cambio de máquinas de la empresa.
FASES: Serán 4 fases, una para cada año de decisión.
ESTADOS:
K = conservar
R = reemplazar
S = vender
DESARROLLO
ETAPA IV:
t
K RSolución Óptima
r(t)+s(t+1)-c(t)r(0)+s(t)+s(1)-c(0)-
100f4(t)
Decisión
1 19.0+60-0.6=78.4 20+80+80-0.2- 79.8 R
100=79.8
2 18.5+50-1.2=67.320+60+80-0.2-
100=59.867.3 K
3 17.2+30-1.5=45.720+50+80-0.2-
100=49.849.8 R
6(Se debe
reemplazar)20+ 5+80-0.2-100=
4.84.8 R
ETAPA III:
t
K RSolución Óptima
r(t)-c(t)+ f4(t+1)r(0)+s(t) - c(0)-100+
f4(1)f3(t)
Decisión
119.0-
0.6+67.3=85.720+80-0.2-
100+79.8=79.685.7 R
218.5-
1.2+49.8=67.120+60-0.2-
100+79.8=59.667.1 K
514.0-1.8+ 4.8=17.0
20+50-0.2-100+79.8=19.6
19.8 R
ETAPA II:
t
K RSolución Óptima
r(t)-c(t)+ f3(t+1)r(0)+s(t)-c(0)-100+
f3(1)f2(t)
Decisión
1 19.0-0.6+67.1=85.520+80-0.2-
100+85.7=85.585.5 K o R
4 18.5-1.7+19.6=67.320+60-0.2-
100+85.7=35.535.5 K
ETAPA I:
t
K RSolución Óptima
r(t)-c(t)+ f2(t+1)r(0)+s(t)-c(0)-100+
f2(1)f1(t)
Decisión
3 17.2- 20+50-0.2- 79.8 R
1.5+35.5=51.2 100+85.5=55.3
FORMA ANALITICA:
fn(t) = MAX{ Kn(t), Rn(t) }
Kn(t) = [ r(t) - c(t) ] + fn+1(t+1)
Rn(t) = [ r(0) – c(0) ] + [ s(t) – 100'000 ] + fn+1(1)
RESPUESTA: Al iniciar el año 1, la decisión óptima para t=3 es reemplazar la máquina. Así, la máquina nueva tendrá un año al iniciar el año 2, y t=1 al iniciar el año 2 determina conservarla o reemplazarla. Si se reemplaza, la nueva máquina tendrá un año al iniciar el año 3, año en el cual; en caso contrario, la máquina conservada tendrá 2 años. De esta manera obtendremos 2 maneras de optimizar la ganancia (a un nivel de $55’300), cuales se pueden ver en la figura:
Ejercicio 3
Una compañía está planeando una estrategia de publicidad durante el año próximo para sus tres productos más importantes .Como los son bastantes diferentes, cada esfuerzo de publicidad estará dedicado a un solo producto .En unidades de millón de dólares se dispone de un total de 6 para esta campaña de publicidad y se supone que el gasto en cada producto debe ser un numero entero mayor igual a 1.El vicepresidente de mercadotecnia ha establecido el objetivo como sigue :determinar cuánto gastar en cada producto a fin de maximizar las ventas. La siguiente tabla da el incremento estimado en ventas para los diferentes gastos en publicidad.
PRODUCTOS GASTO
PUBLICIDAD 1 2 31 7 4 6
2 10 8 93 14 11 134 17 14 15
DISPONE DE: 6 MILLONES
MIN 1 MILLON EN C/PRODUCTO
1 MILLON/PRODUCTO
1º Determinar la FunciónMax / min
Max Ventas
2º Determinar el número de etapas 3
3º Determinar el estado gastos disponibles i
4º Determinar la variable de decisión gastos asignados j
Etapa 3
gastos asignados Max venta
Mejor decisión
gastos disponibles 1 2 3 4 f * (i) j *
1 6 6 12 9 9 23 13 13 34 15 15 4
Etapa 2
gastos asignados Max venta
Mejor decisión
gastos disponibles 1 2 3 4 f * (i) j *
2 10 10 13 13 14 14 24 17 17 17 17 1,2,35 19 21 20 20 21 2
Etapa 1
gastos asignados Max venta
Mejor decisión
gastos disponibles 1 2 3 4 f * (i) j *
6 28 27 28 27 28 1,3
Productos opción 1 opción3p1 1 3p2 2 2p3 3 1venta Max 28 28
fn (i) = Max { Vij + f n+1 * (j) } j pertenece al dominio de i