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 personas

Tarea A 0 3 8
Tarea B 0 4 5
Tarea 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:

X2 X3
X1
n=1 n=2 n=3

e1 e2 e3

ETAPA 3:

X1 X2 X3

n=1 n=2 n=3

e1 e2 e3
 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.

Valores posibles
de la variable de
decisión en la
etapa 3

i 0 1 2 Personas Rendimie
personas persona personas optimo nto
Estados optimo f*
posibles 0 0 - - 0 0
personas
en la
1 0 5 - 1 5
etapa 3 personas
2 0 5 7 2 7
personas
3 0 5 7 2 7
personas

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
ETAPA 2:

X1 X2 X3

n=1 n=2 n=3

e1 e2 e3

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 1 2 Personas Rendimie
personas persona personas optimo nto
optimo f*
0 0+0 - - 0 0
personas
1 0+5 4+0 - 0 5
personas
2 0+7 4+5 5+0 1 9
personas
3 0 4+7 5+5 1 11
personas

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
 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 1 2 Personas Rendimie
personas persona personas optimo nto
optimo f*
3 0+11 3+9 8+5 2 13
personas

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 Costo de Valor de

Ingreso, r(t)
,t Operación, c(t) recuperación, s(t)
($)
(años) ($) ($)

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:

Solución
K R
Óptima
t
r(0)+s(t)+s(1)-c(0)- Decisió
r(t)+s(t+1)-c(t) f4(t)
100 n

1 19.0+60-0.6=78.4 20+80+80-0.2- 79.8 R

 100=79.8

20+60+80-0.2-
2 18.5+50-1.2=67.3 67.3 K
100=59.8

20+50+80-0.2-
3 17.2+30-1.5=45.7 49.8 R
100=49.8

(Se debe 20+ 5+80-0.2-100=

6 4.8 R
reemplazar) 4.8

ETAPA III:

Solución
K R
Óptima
t
r(0)+s(t) - c(0)-100+ Decisió
r(t)-c(t)+ f4(t+1) f3(t)
f4(1) n

19.0- 20+80-0.2-
1 85.7 R
0.6+67.3=85.7 100+79.8=79.6

18.5- 20+60-0.2-
2 67.1 K
1.2+49.8=67.1 100+79.8=59.6

14.0-1.8+ 20+50-0.2-
5 19.8 R
4.8=17.0 100+79.8=19.6

ETAPA II:

Solución
K R
Óptima
t
r(0)+s(t)-c(0)-100+ Decisió
r(t)-c(t)+ f3(t+1) f2(t)
f3(1) n

20+80-0.2-
1 19.0-0.6+67.1=85.5 85.5 KoR
100+85.7=85.5

20+60-0.2-
4 18.5-1.7+19.6=67.3 35.5 K
100+85.7=35.5

ETAPA I:

Solución
K R
Óptima
t
r(0)+s(t)-c(0)-100+ Decisió
r(t)-c(t)+ f2(t+1) f1(t)
f2(1) 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 [Link] 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 3
1 7 4 6
 2 10 8 9
3 14 11 13
4 17 14 15

DISPONE DE: 6 MILLONES

MIN 1 MILLON EN C/PRODUCTO

1 MILLON/PRODUCTO

Max / Max
1º Determinar la Función min Ventas

2º Determinar el número de etapas 3

3º Determinar el estado gastos disponibles i

Determinar la variable de
4º decisión gastos asignados j

Etapa 3

Max Mejor
gastos asignados venta decisión
gastos
disponibles 1 2 3 4 f * (i) j*
1 6 6 1
2 9 9 2
3 13 13 3
4 15 15 4
Etapa 2

Max Mejor
gastos asignados venta decisión
gastos
disponibles 1 2 3 4 f * (i) j*
2 10 10 1
3 13 14 14 2
4 17 17 17 17 1,2,3
5 19 21 20 20 21 2

Etapa 1

Max Mejor
gastos asignados venta decisión
gastos
disponibles 1 2 3 4 f * (i) j*
6 28 27 28 27 28 1,3

Producto
s opción 1 opción3
p1 1 3
p2 2 2
p3 3 1
venta
Max 28 28
fn (i) = Max { Vij + f n+1 *
(j) }
j pertenece al dominio de i