Programación dinamica

Problema 1

Un contador, ha recibido ofertas de tres diferentes clientes que desean sus servicios. A cada uno le gustaría que el contralor trabajara para el tiempo completo; sin embargo, cada cliente está deseoso de emplear al contador tantos días a la semana como él pueda hacerlo por los honorarios que se muestran en la tabla siguiente.

Numero de días Cliente 1 Cliente 2 Cliente 3

0 0 0 0

1 100 125 150

2 250 250 300

3 400 375 400

4 525 500 550

5 600 625 650

¿Cuántos días deberá dedicar el contador a cada cliente para maximizar su ingreso semanal?

Z=700

X1=3

X2=0

X3=2

En el siguiente problema consideramos a F3(s) como la cantidad que obtendrá el contador por trabajar un determinado número de días para el cliente tres, y a x3 tomara valores de 0 a 3 de acuerdo a el número de días que se asignaran para el cliente 3.

S F3(s) X3

0 0 0

1 150 1

2 300 2

3 400 3

4 550 4

5 650 5

La tabla anterior corresponde a la etapa uno y el valor que maximiza a f3(s) es asignar tres días para el cliente tres.

La siguiente tabla corresponde a la etapa 2, para la función de f2(s), sumamos el costo obtenido de asignar un determinado número de días al cliente 2 más el costo de asignar días al cliente 3.

F2(s,x2)=C2+f3(s-x2) F2(s) X2

S x2 0 1 2 3 4 5

0

1

2

3

4 0

150 125

300 275 250

400 425 400 375

500 525 550 525 500 0

150

300

400

550 0

0

1

1

2

5 650 675 800 575 650 625 650 3

Para la etapa 2 al obtener los valores para la función f2 observamos que los valores que maximizan el ingreso se encuentran en la fila del valor de 0 para x2 por lo tanto asignamos 0 días para el cliente 2, cuando x=2.

La siguiente tabla muestra los resultados para la última etapa (1) y se obtienen sumando el costo obtenido por asignar un determinado número de días para el cliente 1, más el costo obtenido en la etapa 2.

X1

S F1(s1,x1)=c1+f2(s-x1) F1(s) X1

0 1 2 3 4 5

S 650 650 650 700 675 600 700 3

Para la última etapa sustituyendo los valores en la función f1 encontramos que el valor máximo que podríamos asignar a la función es 700, pero implicaría asignar 3 días al cliente 1 y solo tenemos disponibles 2 días para asignar, por lo tanto escogemos el valor de 650 asignando 2 días al

...