Programación Dinámica
1.- Un alumno debe seleccionar en total 10 cursos opcionales d cuatro departamentos distintos, y
al menos un curso de cada departamento. Los 10 cursos se asignan a los cuatro departamentos en
una forma que maximiza el “conocimiento”. El alumno mide el conocimiento en una escala de 100
puntos y llega a la tabla siguiente.
Número de Cursos
Depart
1 2 3 4 5 6 ≥7
I 25 50 60 80 100 100 100
II 20 70 90 100 100 100 100
III 40 60 80 100 100 100 100
IV 10 20 30 40 50 60 70
¿Cómo debe seleccionar los cursos el alumno?
Solución:
Número de Cursos
Depart
1 2 3 4 5 6 7 8 9 10
I 25 50 60 80 100 100 100 100 100 100
II 20 70 90 100 100 100 100 100 100 100
III 40 60 80 100 100 100 100 100 100 100
IV 10 20 30 40 50 60 70 70 70 70
Sea: 𝑿𝒊𝒋 = El número de cursos por departamento
i = 1,2,3,4 (del departamento i)
j = 1,2,3,…..,9, 10 (# de cursos j)
Función objetivo:
𝑍𝑚á𝑥 = 𝑋𝑖𝑗
Sujeto a:
25𝑋11 +50𝑋12 +60𝑋13 +80𝑋14 +100𝑋15 +……………..+100𝑋110 ≤ 100
20𝑋21 +70𝑋22 +90𝑋23 +100𝑋24 +…………….+100𝑋210 ≤ 100
40𝑋31 +60𝑋32 +80𝑋33 +100𝑋34 +…………….+100𝑋310 ≤ 100
10𝑋41 +20𝑋42 +30𝑋43 +40𝑋44 +……………….+70𝑋410 ≤ 100
𝑿𝒊𝒋 = 10
𝑿𝒊𝒋 > 0
Utilizamos el algoritmo de viajero y incluyendo (TORA); tenemos
1° Paso:
Si : 𝑋11 = 4 𝐶1 = 100 𝑋12 = …. = 𝑋110 = 0
N0
𝑋12 = 2 𝐶1 = 100 𝑋11 = 0 y 𝑋13 = 𝑋14 = ……. = 0
2° Paso :
Si: 𝑋21 = 𝑋22 = 0 y 𝑋23 = 3 𝐶2 = 270
𝑋24 = …… 𝑋210 = 0
3° Paso:
Si: 𝑋31 = 𝑋32 = 𝑋33 = 0 y 𝑋34 = 4 𝐶3 = 400
𝑋35 = …… 𝑋310 = 0
4° Paso: por ser el último paso 𝑋41 = 1
𝐶4 = 1 x 10 = 10
Solución Óptima:
2 cursos de I
3 cursos de III
4 cursos de III
1 cursos de IV
Por ende: Total de cursos = 10; con una capacidad de conocimiento revelada.
2. Una compañía de aparatos eléctricos tiene un contrato para entregar las cantidades siguientes
de radios durante los tres meses próximos: mes 1, 200 radios; mes 2, 300 radios; mes 3, 300 radios.
Por cada radio producido durante los meses 1 y 2 se genera un costo variable de 10 dólares; por
cada radio producido en el mes 3 se incurre en un costo variable de 12 dólares. El costo de inventario
es de 1.5 dólares por cada radio en existencia al final del mes. El costo por preparar la producción
durante un mes es de 250 dólares. Los radios fabricados se pueden usar para cumplir con la
demanda para ese mes o para cualquier mes futuro. Suponga que la producción de cada mes debe
ser un múltiplo de 100. Dado que el nivel de inventario inicial es 0 unidades, utilice la programación
dinámica para determinar un plan de producción óptimo.
Definimos :
Xi : numero de radios producidos para este mes ( una restricción del problema es que este debe ser
múltiplo de 100)
Yi: inventario de radio al inicio del periodo i
Di : demanda de radios en el mes i
Mi : variable auxiliar , solo para formular , si es 0 se decidió no producir en el mes i y si vale 1 se
decidió producir
min. sumatoria{ CP( xi ) + CI( yi ) + 250 Mi }
> Sumatoria { 10(x1) + 10(x2) + 12(x3) + 150( Y1 + Y2 + Y3 ) }
S.a.
Sumatoria ( Xi ) = 9
Yi,Xi >=0 , para todo i de 1 a 3
Mi ={ 0 , 1 }
Condiciones de borde : y1=0 , y4=0
K=3
** 3 etapas , es por mes
Función de transformación
Yi+1 = Yi + Xi - Di
** Lo que tenga en almacén el siguiente mes , será lo que produje mas lo que tenia en inventario
menos la demanda de dicho mes
Función de recursión
Fi (Yi) = min. { CP( xi ) + CI( yi+1 ) + 250 Mi + F i+1 ( Yi+1 ) }
Ahora a iterar :P , bien la repuesta es .
En el mes 1 se produciría : 200
En el mes 2 se produciría : 600
En el mes 3 se produciría : 0
El costo total seria : 8950
3.Una compañía esta planeando una estrategia de publicidad durante el año próximo para sus 3
productos mas importantes. Como los 3 son bastante diferentes, cada esfuerzo de publicidad estará
dedicado a un solo producto. Se dispone de un total de 6 millones de dólares para esta campaña de
publicidad y se supone que el gasto para cada producto deberá ser un número entero mayor o igual
a uno. El vicepresidente de mercadotecnia ha establecido el objetivo como sigue: determinar cuanto
gastar en cada producto con el fin demaximizar las ventas totales. La siguiente tabla da un
incremento estimado en ventas (en las unidades apropiadas) para los diferentes gastos en
publicidad:
