Tema_2_ProgramaciónDinámica_2018-II

Vista previa del material en texto

Tema 2 
Programación 
Dinámica
Investigación de Operaciones - 2
2
Tema 2 
Programación Dinámica
Investigación de Operaciones - 2
Índice
1. Introducción
2. Problemas de recorrido mínimo
3. Problemas de distribución de esfuerzo
4. Problemas de planificación
5. Problemas de producción bajo pedido
6. Problema de la mochila
3Investigación de Operaciones 2
▪ La Programación Dinámica (PD) se emplea para resolver problemas
muy variados de optimización que generalmente se expresan
mediante funciones no lineales.
▪ Estos problemas se suelen descomponer en etapas sucesivas o en 
opciones alternativas. e toman así decisiones multi-etapa .
▪ La PD resuelve el problema desde el final hacia el principio. 
1. Introducción
4
Tema 2 
Programación Dinámica
Investigación de Operaciones - 2
Índice
1. Introducción
2. Problemas de recorrido mínimo
3. Problemas de distribución de esfuerzo
4. Problemas de planificación
5. Problemas de fiabilidad de un sistema
6. Problemas de producción bajo pedido
7. Problema de la mochila
5Investigación de Operaciones 2
Ejemplo 1 Se quiere ir del punto A al punto J. Para ello hay varias rutas alternativas, que
pasan por los puntos B,C,D, etc. Cada trayecto entre dos puntos tiene un
coste que se indica en la figura. Denotaremos por 𝑐𝑖𝑗 al coste del trayecto
entre el punto 𝑖 y el 𝑗. Por ejemplo, cubrir el trayecto entre los puntos A y D
tiene un coste 𝑐𝐴𝐷 = 3. A la vista de la figura, harán falta 4 etapas para
cubrir el trayecto
¿Cuál es la ruta óptima?
2. Problemas de recorrido mínimo
6Investigación de Operaciones 2
Si elegimos la ruta con el
trayecto más barato en
cada etapa, tendríamos la
solución
𝐴 → 𝐵 → 𝐹 → 𝐼 → 𝐽
con un costo total de 13.
Esta estrategia no nos da, en
general, la solución óptima
Puede verse que incurriendo en un mayor coste en una etapa permite
acceder a trayectos más económicos en etapas siguientes, reduciendo el
coste total
Ejemplo: 𝐴 → 𝐷 → 𝐹 → 𝐼 → 𝐽 tiene un costo total de 11
𝐴 → 𝐶 → 𝐸 → 𝐻 → 𝐽 tiene un coste total de 11
2. Problemas de recorrido mínimo
7
¿Cómo encontrar la ruta óptima?
• Análisis exhaustivo de todas las rutas posibles: puede ser inviable si el problema tiene muchas 
alternativas.
• Programación dinámica: descompone un problema grande en una serie de etapas que se 
resuelven de forma secuencial.
El problema se resuelve de atrás hacia
adelante. De esta forma, la solución
óptima no depende de lo que se haga en
etapas posteriores.
Etapa 1
Etapa 2Etapa 3
Etapa 4
El orden de la numeración es por el
orden en que se va resolviendo. Primero
analizamos la Etapa 1, y finalizamos
analizando la Etapa 4. Sin embargo, el
viaje comenzará en a Etapa 4 y finalizará
en la 1.
Nota: Este criterio de numeración de las etapas se ha elegido para que coincida con el criterio seguido en el
libro de C. Angulo. No obstante, en la literatura es más habitual el criterio contrario: denotar como Etapa 1
aquella en la que se inicial el trayecto (la que se encuentra más a la izquierda), y como Etapa 4 la etapa final,
aunque sea la que se analice primero.
8Investigación de Operaciones 2
Un problema de optimización satisface el
principio de optimalidad de Bellman si dada
una sucesión óptima de decisiones o elecciones,
cada subsucesión es a su vez óptima.
Es decir, si una vez conocida la solución óptima
global, cualquier solución parcial que involucre
sólo una parte de las etapas, es también solución
óptima para ese problema parcial.
En ese caso, puede resolverse mediante
programación dinámica
Principio de optimalidad de Bellman
Los problemas de la ruta óptima (camino máximo, o camino mínimo) suelen cumplir 
este principio, y por eso se pueden resolver por programación dinámica, aunque 
también puede resolverse aplicando teoría de redes (O1)
Richard Ernest
Bellman (1920-1984)
fue un matemático 
aplicado, cuya mayor 
contribución fue la 
metodología denominada 
programación dinámica
2. Problemas de recorrido mínimo
9Investigación de Operaciones 2
Formulación
• Se denotará por 𝑠𝑛, 𝑛 = 1,2,3,4 al conjunto de variables de estado en la etapa
n-ésima. Es decir, variables que señalan el punto en el estamos antes de tomar
la decisión. Señalan el estado actual de la etapa n-ésima y contienen toda la
información necesaria para tomar la decisión. En nuestro ejemplo denota el
punto en el que nos encontramos al inicio de la etapa, antes de decidir dónde ir.
Se tiene entonces que:
• En la Etapa 4, 𝑠4 ∈ {𝐴}
• En la Etapa 3, 𝑠3 ∈ {𝐵, 𝐶, 𝐷}
• En la Etapa 2, 𝑠2 ∈ {𝐸, 𝐹, 𝐺}
• En la Etapa 1, 𝑠1 ∈ {𝐻, 𝐼} Etapa 1
Etapa 2Etapa 3
Etapa 4
2. Problemas de recorrido mínimo
10Investigación de Operaciones 2
Formulación
• Se denotará por 𝑥𝑛, 𝑛 = 1,2,3,4 al conjunto de variables de decisión (es decir,
variables sobre las que hay que decidir) en la etapa n-ésima. En nuestro
ejemplo, representa los destinos entre los que hay que decidir. En nuestro
ejemplo se tiene que:
• En la Etapa 4, 𝑥4 ∈ {𝐵, 𝐶, 𝐷}
• En la Etapa 3, 𝑥3 ∈ 𝐸, 𝐹, 𝐺
• En la Etapa 2, 𝑥2 ∈ {𝐻, 𝐼}
• En la Etapa 1, 𝑥1 ∈ {𝐽}
Una ruta entre A y J se puede escribir como 𝐴 → 𝑥4 → 𝑥3 → 𝑥2 → 𝑥1 con 𝑥1 = 𝐽
Etapa 1
Etapa 2Etapa 3
Etapa 4
𝐴 → 𝑥4
∗ → 𝑥3
∗ → 𝑥2
∗ → 𝑥1
∗ con 𝑥1
∗ = 𝐽
A los valores de 𝑥𝑛 que corresponden con 
la solución óptima se les denotará por 𝑥𝑛
∗
En nuestro ejemplo, la ruta óptima se 
escribirá como 
(No confundir 𝑥𝑛
∗ con el trayecto de menor coste en la etapa n-ésima. 𝑥𝑛
∗
corresponde con la ruta de menor coste total)
2. Problemas de recorrido mínimo
11Investigación de Operaciones 2
Formulación (continuación)
• En la Etapa 4, 𝑠4 ∈ {𝐴}
• En la Etapa 3, 𝑠3 ∈ {𝐵, 𝐶, 𝐷}
• En la Etapa 2, 𝑠2 ∈ {𝐸, 𝐹, 𝐺}
• En la Etapa 1, 𝑠1 ∈ {𝐻, 𝐼}
Etapa 1
Etapa 2Etapa 3
Etapa 4
En este ejemplo de las rutas, se
tiene que 𝑥𝑛 ≡ 𝑠𝑛−1 pero en otros
problemas no necesariamente son
lo mismo.
𝑠𝑛 𝑠𝑛−1
Etapa n Etapa n-1
𝑥𝑛
2. Problemas de recorrido mínimo
• En la Etapa 4, 𝑥4 ∈ {𝐵, 𝐶, 𝐷}
• En la Etapa 3, 𝑥3 ∈ 𝐸, 𝐹, 𝐺
• En la Etapa 2, 𝑥2 ∈ {𝐻, 𝐼}
• En la Etapa 1, 𝑥1 ∈ {𝐽}
12Investigación de Operaciones 2
Formulación (continuación)
• Se denota por 𝑓𝑛(𝑠𝑛, 𝑥𝑛) al valor ‘global’ de la función objetivo por elegir 𝑥𝑛
estando en el estado 𝑠𝑛 ,y haber elegido una solución óptima en las etapas
anteriores. No se trata del valor ‘local’ de ese trayecto, sino al valor global
desde esa etapa hasta la primera, asumiendo que en las anteriores se ha
tomado la decisión óptima, que se derive de la decisión tomada en esta
etapa. En nuestro ejemplo, es un coste que habrá que minimizar. Es decir:
Dados 𝑠𝑛 y 𝑥𝑛, sea 𝑥𝑛
∗ el valor de 𝑥𝑛
(no necesariamente único) que
minimiza 𝑓𝑛 𝑠𝑛, 𝑥𝑛 , y sea 𝑓𝑛
∗(𝑠𝑛)
dicho valor mínimo. Entonces
𝑓𝑛
∗ 𝑠𝑛 = min
𝑥𝑛
𝑓𝑛 𝑠𝑛, 𝑥𝑛 = 𝑓𝑛(𝑠𝑛, 𝑥𝑛
∗)
Nuestro ejemplo se inicia calculando
𝑓1
∗(𝑠1) y habrá terminado cuando
obtengamos 𝑓4
∗(𝐴).
Etapa 1
Etapa 2Etapa 3
Etapa 4
𝑓𝑛 𝑠𝑛, 𝑥𝑛 = costo inmediato (etapa n) + costo mínimo en etapas 𝑛 − 1, … , 1
2. Problemas de recorrido mínimo
13Investigación de Operaciones 2
Veamos cómo se aplica en nuestro ejemplo
Etapa 1 𝑓1 𝑠1, 𝑥1
= 𝑐𝑠1𝑥1
J 𝑓1
∗(𝑠1) 𝑥1
∗
H 3 3 J
I 4 4 J
𝑠1
𝑥1
Etapa 1
La interpretación de la solución óptima de esta etapa es obvia:
• Si estamos en el estado 𝑠1 = 𝐻, el destino óptimo siguiente es 𝑥1
∗ = 𝐽, lo que 
costará 𝑓1
∗ 𝐻 = 3
• Por contra, si estamos en el estado 𝑠1 = 𝐼, nuestro destino óptimo es 𝑥1
∗ = 𝐽, 
lo que costará 𝑓1
∗ 𝐼 = 4
Esta solución no depende de lo que se decida en etapas posteriores (principio de optimalidad)
2. Problemas de recorrido mínimo
14Investigación de Operaciones 2
Etapa 1 𝑓1 𝑠1, 𝑥1
= 𝑐𝑠1𝑥1
J 𝑓1
∗(𝑠1) 𝑥1
∗
H 3 3 J
I 4 4 J
𝑠1
𝑥1
Etapa 1
Etapa 2
𝑓2 𝑠2, 𝑥2
= 𝑐𝑠2𝑥2 + 𝑓1
∗(𝑠1)
H I 𝑓2
∗(𝑠2) 𝑥2
∗
E 1+3=4 4+4=8 4 H
F 6+3=9 3+4=7 7 I
G 3+3=6 3+4=7 6 H
𝑠2
𝑥2
Etapa 2
2. Problemas de recorridomínimo
15Investigación de Operaciones 2
Veamos como se aplica en nuestro ejemplo
Etapa 1 𝑓1 𝑠1, 𝑥1
= 𝑐𝑠1𝑥1
J 𝑓1
∗(𝑠1) 𝑥1
∗
H 3 3 J
I 4 4 J
𝑠1
𝑥1
Etapa 1
Etapa 2
𝑓2 𝑠2, 𝑥2
= 𝑐𝑠2𝑥2 + 𝑓1
∗(𝑠1)
H I 𝑓2
∗(𝑠2) 𝑥2
∗
E 1+3=4 4+4=8 4 H
F 6+3=9 3+4=7 7 I
G 3+3=6 3+4=7 6 H
𝑠2
𝑥2
Etapa 2
La función de 
costes es recursiva
2. Problemas de recorrido mínimo
16
Etapa 1
Etapa 2 𝑓2 𝑠2, 𝑥2
= 𝑐𝑠2𝑥2 + 𝑓1
∗(𝑠1)
H I 𝑓2
∗(𝑠2) 𝑥2
∗
E 1+3=4 4+4=8 4 H
F 6+3=9 3+4=7 7 I
G 3+3=6 3+4=7 6 H
𝑠2
𝑥2
Etapa 2
La interpretación de la solución de esta Etapa 2 hay que hacerla conjuntamente con la de 
la Etapa 1: 𝑠2 → 𝑥2
∗ → 𝑥1
∗ con un coste de 𝑓2
∗ 𝑠2 = 𝑐𝑠2𝑥2∗ + 𝑓1
∗
• Si comenzamos en el estado 𝑠2 = 𝐸, lo óptimo es dirigirnos a 𝑥2
∗ = 𝐻 (solución Etapa 2), y de ahí 
a 𝑥1
∗ = 𝐽 (solución Etapa 1). Esta opción tiene un coste de 𝑓2
∗ 𝐸 = 4.
𝐸 → 𝐻 → 𝐽
• Por contra, si partiésemos del estado 𝑠2 = 𝐹, el destino óptimo es 𝑥2
∗ = 𝐼, y de ahí a 𝑥1
∗ = 𝐽. Esta 
opción tiene un coste de 𝑓2
∗ 𝐹 = 7.
𝐹 → 𝐼 → 𝐽
• Alternativamente, si estuviésemos en el estado 𝑠2 = 𝐺, habría que dirigirse a 𝑥2
∗ = 𝐻, y de ahí a 
𝑥1
∗ = 𝐽. Esta opción tiene un coste de 𝑓2
∗ 𝐺 = 6 .
𝐺 → 𝐻 → 𝐽
Esta solución no depende de lo que se decida en etapas posteriores (principio de optimalidad)
17
Etapa 1
Etapa 2 𝑓2 𝑠2, 𝑥2
= 𝑐𝑠2𝑥2 + 𝑓1
∗(𝑠1)
H I 𝑓2
∗(𝑠2) 𝑥2
∗
E 1+3=4 4+4=8 4 H
F 6+3=9 3+4=7 7 I
G 3+3=6 3+4=7 6 H
𝑠2
𝑥2
Etapa 2
Etapa 3
𝑓3 𝑠3, 𝑥3 = 𝑐𝑠3𝑥3 + 𝑓2
∗(𝑠2)
E F G 𝑓3
∗(𝑠3) 𝑥3
∗
B 7+4=11 4+7=11 6+6=12 11 E o F
C 3+4=7 2+7=9 4+6=10 7 E
D 4+4=8 1+7=8 5+6=11 8 E o F
𝑠3
𝑥3
Etapa 3
18
Etapa 1
Etapa 2 𝑓2 𝑠2, 𝑥2
= 𝑐𝑠2𝑥2 + 𝑓1
∗(𝑠1)
H I 𝑓2
∗(𝑠2) 𝑥2
∗
E 1+3=4 4+4=8 4 H
F 6+3=9 3+4=7 7 I
G 3+3=6 3+4=7 6 H
𝑠2
𝑥2
Etapa 2
Etapa 3
𝑓3 𝑠3, 𝑥3 = 𝑐𝑠3𝑥3 + 𝑓2
∗(𝑠2)
E F G 𝑓3
∗(𝑠3) 𝑥3
∗
B 7+4=11 4+7=11 6+6=12 11 E o F
C 3+4=7 2+7=9 4+6=10 7 E
D 4+4=8 1+7=8 5+6=11 8 E o F
𝑠3
𝑥3
Etapa 3
La función de costes 
es recursiva
El óptimo de una etapa afecta a las siguientes, pero no a las anteriores (principio de optimalidad)
19
Etapa 1
Etapa 2Etapa 3 𝑓3 𝑠3, 𝑥3
= 𝑐𝑠3𝑥3 + 𝑓2
∗(𝑠2)
E F G 𝑓3
∗(𝑠3) 𝑥3
∗
B 11 11 12 11 E o F
C 7 9 10 7 E
D 8 8 11 8 E o F
𝑠3
𝑥3
Etapa 3
• Si estamos en B, el óptimo es E o F. 
o Si elegimos E, el óptimo es seguir por H y luego J: 
𝐵 → 𝐸 → 𝐻 → 𝐽 coste: 11
o Si elegimos F, el óptimo es seguir por I y luego J: 
𝐵 → 𝐹 → 𝐼 → 𝐽 coste: 11
• Si estamos en C, el óptimo es E: 𝐶 → 𝐸 → 𝐻 → 𝐽 coste:7
• Si estamos en D, el óptimo es E o F
𝐷 → 𝐸 → 𝐻 → 𝐽 coste: 8
𝐷 → 𝐹 → 𝐼 → 𝐽 coste: 8
20
Etapa 1
Etapa 2Etapa 3 𝑓3 𝑠3, 𝑥3
= 𝑐𝑠3𝑥3 + 𝑓2
∗(𝑠2)
E F G 𝑓3
∗(𝑠3) 𝑥3
∗
B 11 11 12 11 E o F
C 7 9 10 7 E
D 8 8 11 8 E o F
𝑠3
𝑥3
Etapa 3Etapa 4
𝑓4 𝑠4, 𝑥4 = 𝑐𝑠4𝑥4 + 𝑓3
∗(𝑠3)
B C D 𝑓4
∗(𝑠4) 𝑥4
∗
A 2+11=13 4+7=11 3+8=11 11 C o D
𝑠4
𝑥4
Etapa 4
Ya podemos identificar la solución óptima a partir de las cuatro tablas. Hay tres soluciones con el 
mismo coste mínimo
Solución 1: A → 𝐶 → 𝐸 → 𝐻 → 𝐽 costo: 11
Solución 2: A → 𝐷 → 𝐸 → 𝐻 → 𝐽 costo: 11
Solución 3: A → 𝐷 → 𝐹 → 𝐼 → 𝐽 costo: 11
21Investigación de Operaciones 2
Cada flecha representa una política de decisión óptima (mejor destino inmediato) desde ese estado. No
sólo se pueden visualizar las rutas óptimas (desde A hasta J) con su coste, sino la posibilidad de proponer
rutas alternativas si algún destino no fuese factible ante alguna contingencia.
Por ejemplo ¿Cuál sería la ruta óptima si, por alguna razón se comienza en el punto B? ¿Y si el destino F 
desaparece o es más caro? ¿Cómo proceder si cuando estamos es E somos desviados a F?
J
Descripción gráfica de la solución del problema de la ruta mínima
22Investigación de Operaciones 2
Resumen de las características de los problemas de programación dinámica
1. El problema se puede dividir en etapas, cada una de las cuales requiere de una
política (directrices) de decisión.
2. Cada etapa tiene un cierto número de estados de inicio. Puede ser finito o infinito.
3. El efecto de la política de decisión en cada etapa es transformar el estado actual en
un estado asociado con el inicio de la siguiente etapa.
4. Se verifica el principio de optimalidad de la programación dinámica.
5. El procedimiento se inicia cuando se determina la política óptima de la primera etapa
(el final de la ruta), que suele ser trivial.
6. Se dispone de una relación recursiva que identifica la política óptima para la etapa 𝑛,
dada la política óptima en la etapa 𝑛 − 1.
7. Para todos los problemas de programación dinámica se obtiene una tabla como la
siguiente para cada etapa 𝑛 = 1,2, …𝑁.
𝑓𝑛 𝑠𝑛, 𝑥𝑛
𝑓𝑛
∗(𝑠𝑛) 𝑥𝑛
∗
𝑠𝑛
𝑥𝑛
Etapa n
23Investigación de Operaciones 2
𝑠𝑛 𝑠𝑛−1
Etapa n Etapa n-1
𝑥𝑛
Programación dinámica determinista:
El estado de la etapa 𝑛 − 1 viene determinado por el estado de la 
etapa 𝑛 y la política de decisión 𝑥𝑛.
Se puede describir como el siguiente diagrama
Estado:
Valor: 𝑓𝑛 𝑠𝑛, 𝑥𝑛 𝑓𝑛−1
∗ 𝑠𝑛−1
Programación dinámica probabilística: El estado 𝑠𝑛 en la etapa n y 𝑥𝑛 no 
determinan 𝑠𝑛−1 sino que sólo influyen en la probabilidad de acabar en él.
variable de 
decisión
Contribución de 
𝑥𝑛
Transformamos el estado 𝑠𝑛 en el estado 𝑠𝑛−1
24Investigación de Operaciones 2
Una persona debe viajar desde A hasta Z, de tal manera que el 
recorrido sea mínimo.
1
10
8
9
7
5
4
2
3 6 11
A Z
3
6
7
2
5
2
4
3
3
4
3
6
4
7
4
7
5
5
3
4
Etapa 1Etapa 2Etapa 3Etapa 4
2. Problemas de recorrido mínimo
Problema
25Investigación de Operaciones 2
s1 \ x1
1
10
8
9
7
5
4
2
3 6 11
A Z
3
6
7
2
5
2
4
3
3
4
3
6
4
7
4
7
5
5
3
4
s2 \ x2
5
6
Etapa 1
8
9
10
11 f1* x1*
4 4 11
3 3 11
5 5 11 7
8
Etapa 2
Etapa 1
9 10
Etapa 2
f2* x2*
10 6 - 6 9
11 8 9 8 9
- 10 9 9 10
𝑓𝑛(𝑠𝑛, 𝑥𝑛) 𝑓𝑛(𝑠𝑛, 𝑥𝑛)
2. Problemas de recorrido mínimo
26Investigación de Operaciones 2
1
10
8
9
7
5
4
2
3 6 11
A Z
3
6
7
2
5
2
4
3
3
4
3
6
4
7
4
7
5
5
3
4
s3 / x3
2
3
Etapa 3
4
5
Etapa 4
Etapa 3
6 7
Etapa 4
f3* x3*
1314- 13 5
10
11
12 10 5
-
12
11 11 7
s4 / x4 2 3 4 f4* x4*
1 16 15 13 13 4
s2 / x2 f2* 
5 6 
6 8 
7 9 
 
¿Cuál es la trayectoria óptima?
𝑓𝑛(𝑠𝑛, 𝑥𝑛)𝑓𝑛(𝑠𝑛, 𝑥𝑛)
2. Problemas de recorrido mínimo
27Investigación de Operaciones 2
s1 / x1
1
10
8
9
7
5
4
2
3 6 11
A Z
3
6
7
2
5
2
4
3
3
4
3
6
4
7
4
7
5
5
3
4
s2 / x2
5
6
Etapa 1
8
9
10
11 f1* x1*
4 4 11
3 3 11
5 5 11 7
8
Etapa 2
9 10 f2* x2*
10 6 - 6 9
11 8 9 8 9
- 10 9 9 10
2. Problemas de recorrido mínimo
28Investigación de Operaciones 2
Juan Quispe, que estudia en Boston, decide hacer turismo por EEUU en sus
vacaciones de verano, visitando a los amigos que tiene en varias ciudades,
con quienes se comunica por e-mail. Él ha decidido visitar en primer lugar a un
amigo que viva en una ciudad del sur este (Richmond, Atlanta o Charlotte),
luego a uno del medio oeste (Detroit, Chicago o Milwaukee) y finalmente a uno
de la costa oeste (Los Ángeles, San Francisco o Portland).
Aunque Juan dispone de suficiente dinero para sus vacaciones, se ha
propuesto gastar lo menos posible en sus desplazamientos (por vía aérea). Él
ha visto en Internet que el viaje de retorno, desde cualquiera de las tres
ciudades de la costa oeste, a Boston, le cuesta $400. Además, ha anotado los
costos de los pasajes entre los distintos viajes que puede hacer y se ha
construido el siguiente diagrama:
Problema
2. Problemas de recorrido mínimo
29Investigación de Operaciones 2
Char
LA
Port
Bost
15
0
135
-95
140
12
5 
-
 1
00
-
 -
1
7
0
120
170
100
130
Atla
-1
6
5
Rich 210
-165
220
16
0 
-
 2
35
-
 -
2
3
0
205
180
-2
2
0
Detr
Milw
Chic SF
Determine cómo debe planear su viaje para 
gastar lo menos posible. 
2. Problemasde recorrido mínimo
30Investigación de Operaciones 2
Etapa 1
s1 / d1 LA SF Port f1* d1*
Detr 610 605 620 605 SF
Chic 560 565 580 560 LA
Milw 630 635 620 620 Port
Char
LA
Port
Bost
15
0
135
-95
140
12
5 
-
 1
00
-
 -
1
7
0
120
170
100
130
Atla
-1
6
5
Rich 210
-165
220
16
0 
-
 2
35
-
 -
2
3
0
205
180
-2
2
0
Detr
Milw
Chic SF
-
31Investigación de Operaciones 2
Etapa 2
s2 / d2 Detr Chic Milw f2* d2*
Rich 740 660 785 660 Chic
Char 730 655 750 655 Chic
Atla 775 660 760 660 Chic
Char
LA
Port
Bost
15
0
135
-95
140
12
5 
-
 1
00
-
 -
1
7
0
120
170
100
130
Atla
-1
6
5
Rich 210
-165
220
16
0 
-
 2
35
-
 -
2
3
0
205
180
-2
2
0
Detr
Milw
Chic SF
-
32Investigación de Operaciones 2
Etapa 3. Solución
s3 \ d3 Rich Char Atla f3* d3*
Bost 810 775 830 775 Char
Char
LA
Port
Bost
15
0
135
-95
140
12
5 
-
 1
00
-
 -
1
7
0
120
170
100
130
Atla
-1
6
5
Rich 210
-165
220
16
0 
-
 2
35
-
 -
2
3
0
205
180
-2
2
0
Detr
Milw
Chic SF
Solución: Boston – Charlotte 
33Investigación de Operaciones 2
Solución
s2 / d2 Detr Chic Milw f2* d2*
Rich 740 660 785 660 Chic
Char 730 655 750 655 Chic
Atla 775 660 760 660 Chic
Char
LA
Port
Bost
15
0
135
-95
140
12
5 
-
 1
00
-
 -
1
7
0
120
170
100
130
Atla
-1
6
5
Rich 210
-165
220
16
0 
-
 2
35
-
 -
2
3
0
205
180
-2
2
0
Detr
Milw
Chic SF
34Investigación de Operaciones 2
Solución
s3 \ d3 Rich Char Atla f3* d3*
Bost 810 775 830 775 Char
Char
LA
Port
Bost
15
0
135
-95
140
12
5 
-
 1
00
-
 -
1
7
0
120
170
100
130
Atla
-1
6
5
Rich 210
-165
220
16
0 
-
 2
35
-
 -
2
3
0
205
180
-2
2
0
Detr
Milw
Chic SF
Solución: Boston – Charlotte – Chicago 
35Investigación de Operaciones 2
Solución
s1 / d1 LA SF Port f1* d1*
Detr 610 605 620 605 SF
Chic 560 565 580 560 LA
Milw 630 635 620 620 Port
Char
LA
Port
Bost
15
0
135
-95
140
12
5 
-
 1
00
-
 -
1
7
0
120
170
100
130
Atla
-1
6
5
Rich 210
-165
220
16
0 
-
 2
35
-
 -
2
3
0
205
180
-2
2
0
Detr
Milw
Chic SF
36Investigación de Operaciones 2
Solución
s3 \ d3 Rich Char Atla f3* d3*
Bost 810 775 830 775 Char
Char
LA
Port
Bost
15
0
135
-95
140
12
5 
-
 1
00
-
 -
1
7
0
120
170
100
130
Atla
-1
6
5
Rich 210
-165
220
16
0 
-
 2
35
-
 -
2
3
0
205
180
-2
2
0
Detr
Milw
Chic SF
Solución: Boston – Charlotte – Chicago – Los Ángeles 
Gasto total: $775
37Investigación de Operaciones 2
▪ Suponga que Juan decide pasar de todas maneras por Milwaukee, 
donde vive su amiga Ana. ¿Cómo afecta esto sus planes? Determine 
su nuevo plan. 
Char
LA
Port
Bost
15
0
135
-95
140
12
5 
-
 1
00
-
 -
1
7
0
120
170
100
130
Atla
-1
6
5
Rich 210
-165
220
16
0 
-
 2
35
-
 -
2
3
0
205
180
-2
2
0
Detr
Milw
Chic SF
38Investigación de Operaciones 2
Solución
s1 / d1 LA SF Port f1* d1*
Milw 630 635 620 620 Port
s2 / d2 Milw f2* d2*
Rich 785 785 Milw
Char 750 750 Milw
Atla 760 760 Milw
s3 / d3 Rich Chic Atla f3* d3*
Bost 935 870 930 870 Char
Char
LA
Port
Bost
15
0
135
-95
140
12
5 
-
 1
00
-
 -
1
7
0
120
170
100
130
Atla
-1
6
5
Rich 210
-165
220
16
0 
-
 2
35
-
 -
2
3
0
205
180
-2
2
0
Detr
Milw
Chic SF
Gasto total: $870
39Investigación de Operaciones 2
s1 / x1
1
10
8
9
7
5
4
2
3 6 11
A Z
3
6
7
2
5
2
4
3
3
4
3
6
4
7
4
7
5
5
3
4
s2 / x2
5
6
Etapa 1
8
9
10
11 f1* x1*
4 4 11
3 3 11
5 5 11 7
8
Etapa 2
9 10 f2* x2*
10 6 - 6 9
11 8 9 8 9
- 10 9 9 10
2. Problemas de recorrido mínimo
40Investigación de Operaciones 2
Cuatro vehículos participan en una competición en un rally por el que deben atravesar cierta región del
centro de Europa con autos del siglo XIX. Los competidores salen de un mismo punto, pero pueden
llegar al punto de meta por la ruta que deseen. La región cuenta con una extensa red de caminos, por
los que en poco tiempo los corredores se encuentran siguiendo rutas diferentes, con la esperanza de
que su ruta sea la más rápida. En un instante dado, la competición se encuentra tal y como muestra la
figura siguiente. En ella, los nodos de la red representan localizaciones geográficas y los números de las
flechas representan la distancia, en tiempo, entre los puntos que unen, siempre en la dirección de la
flecha. Al inicio de la red se encuentran los competidores. Analizando la carrera con la técnica de
programación dinámica, ¿qué auto crees que debe ganar la carrera, qué ruta debería seguir, y cuánto
tiempo tardará?
Problema
Problemas de recorrido mínimo
41Investigación de Operaciones 2
Vemos que no todas las trayectorias posibles pasan por el mismo número de nodos. Por ejemplo, la ruta 1-A-G-I se
hace en tres etapas, pero 1-A-D-E-H-I lo hace en cinco. Por tanto, si asociamos cada nodo a una etapa, va a ser
complicado resolverlo con programación dinámica. Una forma de resolverlo es modificando el gráfico, añadiendo
nodos virtuales, basados en duplicar un nodo con un coste/distancia cero, de tal forma que todas las trayectorias
tengan el mismo número de etapas. Añadiendo nodo duplicados en los trayectos más cortos conseguiremos que todos
los trayectos tengan el mismo número de nodos.
La siguiente figura muestra el gráfico modificado. Los nodos que se han añadido aparecen en amarillo. En este nuevo
gráfico, es fácil ver que todas las trayectorias posibles tienen 5 etapas, y es así inmediato aplicar programación
dinámica. (puede haber varias representaciones alternativas)
42Investigación de Operaciones 2
43Investigación de Operaciones 2
ETAPA 1 𝑥1
𝑓1(𝑠1, 𝑥1)
= 𝑑11
𝑠1 I 𝑓1
∗ 𝑥1
∗
D'' 11 11 I
F' 15 15 I
G' 8 8 I
H 2 2 I
ETAPA 2 𝑥2
𝑓2(𝑠2, 𝑥2) = 𝑑22 + 𝑓1
∗(𝑠1);𝑠1 = 𝑥2
𝑠2 D'' F' G' H 𝑓2
∗ 𝑥2
∗
D' 0+11=11 11 D''
E 5+2=7 7 H
F
0+15=15 9+2=11 11
H
G
0+8=8 8
G'
44Investigación de Operaciones 2
ETAPA 3 𝑥3
𝑓3(𝑠3, 𝑥3) = 𝑑33 + 𝑓2
∗(𝑠2); 𝑠2 = 𝑥3
𝑠3 D' E F G 𝑓3
∗ 𝑥3
∗
A'
9+8=17 17
G
C'
13+7=20 12+11=23 20
E
D
0+11=11 2+7=9 5+8=13 9
E
45Investigación de Operaciones 2
ETAPA 5 𝑥5 𝑓5 𝑠5, 𝑥5 = 𝑑55 + 𝑓4
∗ 𝑠4 ; 𝑠4 = 𝑥5
𝑠5 A B C 𝑓5
∗ 𝑥5
∗
1 6+17=23 23 A
2 7+17=24 8+13=21 21 B
3 6+13=19 8+20=28 19 B
4 10+23=23 4+20=24 23 B
ETAPA 4 𝑥4 𝑓4 𝑠4, 𝑥4 = 𝑑44 + 𝑓3
∗ 𝑠3 ; 𝑠3 = 𝑥4
𝑠4 A' C' D 𝑓4
∗ 𝑥4
∗
A 0+17=17 11+9=20 17 A'
B 4+9=13 13 D
C 0+20=20 20 C'
46Investigación de Operaciones 2
El menor tiempo lo tiene el auto en la posición 3. Llegaría a la meta en 19 
unidades de tiempo, y la ruta sería:
3-B-D-E-H-I
47Investigación de Operaciones 2
Problemas complementarios
A continuación se muestran un conjunto de redes
que representan trayectos alternativos entre un
origen y un destino. Los números de las líneas que
unen cada nodo representan la distancia (coste)
entre los puntos que unen. Utiliza PD para
encontrar la ruta más conveniente.
48Investigación de Operaciones 2
49Investigación de Operaciones 2
50Investigación de Operaciones 2
51Investigación de Operaciones 2
¿Cuál es la ruta más económica para ir desde A hasta G o H, según convenga más?
B
C
D
E
F
G
H
2
5
3
6
4
6
1
2
7
4
3
6
5
52Investigación de Operaciones 2
53Investigación de Operaciones 2
Considere la siguiente red, donde los números junto a cada trayectoria
representa la distancia entre el par de nodos que conecta. El objetivo es
encontrar la ruta más corta del origen al destino. Haga la descripción
gráfica de la solución.
Problema
2. Problemas de recorrido mínimo
54Investigación de Operaciones 2
Considere la siguiente red, donde los números junto a cada trayectoria
representa la distancia entre el par de nodos que conecta. El objetivo es
encontrar la ruta más corta del origen al destino. Haga la descripción
gráfica de la solución.
Problema
14
2. Problemas de recorrido mínimo
55Investigación de Operaciones 2
Problema
Considere la siguiente red de un proyecto, donde el númerosobre el
nodo es el tiempo que se requiere para la actividad correspondiente.
Considere el problema de encontrar la trayectoria más larga (el
mayor tiempo total) a través de esta red desde el inicio hasta su
término, puesto que la trayectoria más larga es la ruta crítica.
2. Problemas de recorrido mínimo
56
Tema 2 
Programación Dinámica
Investigación de Operaciones - 2
Índice
1. Introducción
2. Problemas de recorrido mínimo
3. Problemas de distribución de recursos
4. Problemas de planificación
5. Problemas de producción bajo pedido
6. Problema de la mochila
57Investigación de Operaciones 2
3. PROBLEMAS DE DISTRIBUCIÓN DE RECURSOS
Un problema-tipo de programación dinámica es el de distribución, o asignación, de
recursos, o esfuerzos, entre un conjunto de actividades alternativas. Cada actividad lleva
asociada una medida relacionada con coste o beneficio, que es la magnitud que hay que
optimizar en el reparto del recurso.
Algunos ejemplos:
• Distribución de capital entre inversiones alternativas.
• Distribución de fuerza de trabajo entre varias tareas o áreas.
• Distribución de un presupuesto entre varias partidas de gasto.
• Distribución de tiempo entre varias actividades.
Por simplicidad, el recurso se tratará de forma discreta, aunque también admite ser tratado como variable continua.
Formulación:
• Etapa 𝑛: actividad 𝑛 𝑛 = 1,2, … , 𝑁 .
• Variable de decisión 𝑥𝑛: cantidad de recursos asignados a la 
actividad 𝑛.
• Estado 𝑠𝑛: cantidad de recursos todavía disponibles para asignarse 
a las actividades restantes (𝑛, 𝑛 − 1,… , 1)
58Investigación de Operaciones 2
Ejemplo
Un inversionista tiene $6000 para invertir en tres productos financieros.
Se puede invertir en unidades de $1000. El retorno potencial (miles de
$) a partir de la inversión depende de la cantidad invertida, de acuerdo a
la siguiente tabla:
Cantidad invertida Retorno a partir del riesgo 
 A B C 
0 0 0 0 
1 0,5 1,5 1,2 
2 1,0 2,0 2,4 
3 3,0 2,2 2,5 
4 3,1 2,3 2,6 
5 3,2 2,4 2,7 
6 3,3 2,5 2,8 
 
3. PROBLEMAS DE DISTRIBUCIÓN DE RECURSOS
Retorno por cada producto
59Investigación de Operaciones 2
Etapa n: Producto donde invertir 𝑛 = 1,2,3 (𝐴 = 3, 𝐵 = 2, 𝐶 = 1)
Estado 𝑠𝑛: Cantidad disponible para invertir en los productos 𝑛, 𝑛 − 1,… , 1
Variable de decisión 𝑥𝑛 : Cantidad a invertir en el producto 𝑛. 𝑥𝑛 = 0,1,2,3,4,5,6.
En el libro de C. Angulo, la variable de decisión 𝑥𝑛 se denota por 𝑑𝑛
En este caso no existe
una secuencia en el
tiempo. Se elige
comenzar con C.
3. PROBLEMAS DE DISTRIBUCIÓN DE RECURSOS
Cantidad invertida Retorno a partir del riesgo 
 A B C 
0 0 0 0 
1 0,5 1,5 1,2 
2 1,0 2,0 2,4 
3 3,0 2,2 2,5 
4 3,1 2,3 2,6 
5 3,2 2,4 2,7 
6 3,3 2,5 2,8 
 
60
6 6
5
4
3
2
1
0 0
6
5
4
3
2
1
0
Etapa 3: 
Asignación a A
Etapa 2: 
Asignación a B
Etapa 1: 
Asignación a C
círculos=estados
=cantidades 
disponibles
61
6 6
5
4
3
2
1
0 0
6
5
4
3
2
1
0
Al inicio los 𝑠3 =
6 mil dólares 
están 
disponibles…
… y hay que 
decidir si 
quedarnos con 
𝑠2 =
0,1,2,… , 6 y el 
resto, 𝑥3 ,
invertirlo en A 
Etapa 3: 
Asignación a A
Etapa 2: 
Asignación a B
Etapa 1: 
Asignación a C
𝑠𝑛−1 = 𝑠𝑛 − 𝑥𝑛
Ecuación de 
transformación 
de estado
𝑠𝑛−1
= 𝑠𝑛, 𝑠𝑛 − 1,… , 0
62
6 6
5
4
3
2
1
0 0
6
5
4
3
2
1
0
Una posible solución 
(no necesariamente 
la óptima)
Empezamos teniendo 6 y 
terminamos teniendo 4, 
pues invertimos 2 en A:
𝑠3 = 6; 𝑥3 = 2; 𝑠2 = 4
Empezamos teniendo 4 y 
terminamos teniendo 3, 
pues invertimos 1 en B:
𝑠2 = 4; 𝑥2 = 1; 𝑠1 = 3
Empezamos teniendo 3 y 
terminamos teniendo 0, 
pues invertimos 3 en C:
𝑠1 = 3; 𝑥1 = 3; 𝑠0 = 0
Etapa 3: 
Asignación a A
Etapa 2: 
Asignación a B
Etapa 1: 
Asignación a C
𝑠𝑛−1 = 𝑠𝑛 − 𝑥𝑛
Ecuación de 
transformación 
de estado
63
6 6
5
4
3
2
1
0 0
6
5
4
3
2
1
0
Una posible solución 
(no necesariamente 
la óptima)
Invertimos:
2 en A, 1 en B y 4 en C
El retorno de esta solución 
es 1+1.5+2.5=5
Etapa 3: 
Asignación a A
Etapa 2: 
Asignación a B
Etapa 1: 
Asignación a C
65Investigación de Operaciones 2
𝑠1
𝑓1 𝑠1, 𝑥1 = 𝑟11
0 1 2 3 4 5 6 f1* x1*
0 0 - - - - - - 0 0
1 0 1,2 - - - - - 1,2 1
2 0 2,4 - - - - 2,4 2
3 0 2,5 - - - 2,5 3
4 0 2,6 - - 2,6 4
5 0 2,7 - 2,7 5
6 0 2,8 2,8 6
C
0 0
1 1,2
2 2,4
3 2,5
4 2,6
5 2,7
6 2,8
6 6
5
4
3
2
1
0 0
6
5
4
3
2
1
0
Etapa 3: A Etapa 2: B Etapa 1: C
s1=dinero que queda
para invertir en C
x1 = decisión sobre 
cuánto invertir en C
𝑥1
𝑟11=retorno obtenido por 
haber invertido x1 en C
3. PROBLEMAS DE DISTRIBUCIÓN DE RECURSOS
66
s1 f1*
0 0
1 1,2
2 2,4
3 2,5
4 2,6
5 2,7
6 2,8
𝑓2 𝑠2, 𝑥2 = 𝑟22 + 𝑓1
∗(𝑠1)
𝑠1 = 𝑠2 − 𝑥2
0 1 2 3 4 5 6 f2* x2*
0
1
2
3
4
5
6
s2
0 - - - - -- 0 0
1,2 1,5 - - - -- 1,5 1
2,4 2,7 2,0 - - -- 2,7 1
2,5 3,9 3,2 2,2 - - - 3,9 1
2,6
B
0 0
1 1,5
2 2
3 2,2
4 2,3
5 2,4
6 2,5
4,0 4,4 3,4 2,3 - - 4,4 2
2,7 4,1 4,5 4,6 3,5 2,4 - 4,6 3
2,8 4,2 4,6 4,7 4,7 3,6 2,5 4,7 3; 4
PROBLEMAS DE DISTRIBUCIÓN DE ESFUERZO O RECURSOS
s2 = dinero que queda 
para invertir en B y C
x2 = decisión sobre 
cuánto invertir en B
𝑟22=retorno obtenido por 
haber invertido x2 en B
x2
6 6
5
4
3
2
1
0 0
6
5
4
3
2
1
0
Etapa 3: A Etapa 2: B Etapa 1: C
67
s1 f1*
0 0
1 1,2
2 2,4
3 2,5
4 2,6
5 2,7
6 2,8
𝑓2 𝑠2, 𝑥2 = 𝑟22 + 𝑓1
∗(𝑠1)
𝑠1 = 𝑠2 − 𝑥2
0 1 2 3 4 5 6 f2* x2*
0
1
2
3
4
5
6
s2
0 - - - - -- 0 0
1,2 1,5 - - - -- 1,5 1
2,4 2,7 2,0 - - -- 2,7 1
2,5 3,9 3,2 2,2 - - - 3,9 1
2,6
B
0 0
1 1,5
2 2
3 2,2
4 2,3
5 2,4
6 2,5
4,0 4,4 3,4 2,3 - - 4,4 2
2,7 4,1 4,5 4,6 3,5 2,4 - 4,6 3
2,8 4,2 4,6 4,7 4,7 3,6 2,5 4,7 3; 4
PROBLEMAS DE DISTRIBUCIÓN DE ESFUERZO O RECURSOS
s2 = dinero que queda 
para invertir en B y C
x2 = decisión sobre 
cuánto invertir en B
𝑟22=retorno obtenido por 
haber invertido x2 en B
x2
6 6
5
4
3
2
1
0 0
6
5
4
3
2
1
0
Etapa 3: A Etapa 2: B Etapa 1: C
68
s1 f1*
0 0
1 1,2
2 2,4
3 2,5
4 2,6
5 2,7
6 2,8
𝑓2 𝑠2, 𝑥2 = 𝑟22 + 𝑓1
∗(𝑠1)
𝑠1 = 𝑠2 − 𝑥2
0 1 2 3 4 5 6 f2* x2*
0
1
2
3
4
5
6
s2
0 - - - - -- 0 0
1,2 1,5 - - - -- 1,5 1
2,4 2,7 2,0 - - -- 2,7 1
2,5 3,9 3,2 2,2 - - - 3,9 1
2,6
B
0 0
1 1,5
2 2
3 2,2
4 2,3
5 2,4
6 2,5
4,0 4,4 3,4 2,3 - - 4,4 2
2,7 4,1 4,5 4,6 3,5 2,4 - 4,6 3
2,8 4,2 4,6 4,7 4,7 3,6 2,5 4,7 3; 4
PROBLEMAS DE DISTRIBUCIÓN DE ESFUERZO O RECURSOS
s2 = dinero que queda 
para invertir en B y C
x2 = decisión sobre 
cuánto invertir en B
𝑟22=retorno obtenido por 
haber invertido x2 en B
x2
6 6
5
4
3
2
1
0 0
6
5
4
3
2
1
0
Etapa 3: A Etapa 2: B Etapa 1: C
Si tengo 𝑠2 = 5 e invierto
𝑥2 = 3 en B obtengo 2.2, y
las otras 2 unidades, 𝑥1 =
5 − 3 = 2, las invierto en C
y obtengo 2.4 . Total =4.6
69
𝑓3 𝑠3, 𝑥3 = 𝑟33 + 𝑓2
∗(𝑠2)
𝑠2 = 𝑠3 − 𝑥3
0 1 2 3 4 5 6 f3* x3*
6 4,7 5,1 5,4 6,9 5,8 4,7 3,3 6,9 3
Conviene invertir:
• $3000 en A.
• $1000 en B.
• $2000 en C.
A
0 0
1 0,5
2 1
3 3
4 3,1
5 3,2
6 3,3
f1* d1* f2* d2*
0 0 0 0 0 0
1 1,2 1 1 1,5 1
2 2,4 2 2 2,7 1
3 2,5 3 3 3,9 1
4 2,6 4 4 4,4 2
5 2,7 5 5 4,6 3
6 2,8 6 6 4,7 3;4
PROBLEMAS DE DISTRIBUCIÓN DE ESFUERZO O RECURSOS
6 6
5
4
3
2
1
0 0
6
5
4
3
2
1
0
Etapa 3: A Etapa 2: B Etapa 1: C
s3=dinero que queda
para invertir en A, B y C
𝑥3 = decisión de 
inversión en A
𝑠3
𝑥3
𝑥2
∗𝑥1
∗
Rendimiento: 6.9
70Investigación de Operaciones 2
3. PROBLEMAS DE DISTRIBUCIÓN DE RECURSOS
• ¿Cómo cambia este problema si no se pueden invertir
más de 3000 dólares en cada producto?
• ¿Cómo cambia el problema si no se puede invertir más
de 3000 dólares en el producto B no más de 2000 en C
71Investigación de Operaciones 2
Problema
El propietario de una cadena de tres supermercados tiene la oportunidad de adquirir hasta
un máximo de cinco cargas de fresas frescas. Las ganancias por vender las fresas difiere
entre los tres supermercados. El propietario quieresaber cómo debe asignar las cinco
cargas a las tiendas para maximizar la ganancia esperada. Por cuestiones logísticas, no
quiere dividir una misma cargas entre las tiendas. Sin embargo, está de acuerdo en asignar
cero cargas a cualquiera de ellas.
En la siguiente tabla se proporciona la ganancia esperada de cada tienda al asignar
distintas cantidades de cargas:
• Utilice programación dinámica para determinar cuántas cargas debe asignarse a 
cada tienda para maximizar la ganancia total esperada.
• ¿Cómo cambia el problema si la tienda 3 no admite más de 3 cargas?
72Investigación de Operaciones 2
73
Tema 2 
Programación Dinámica
Investigación de Operaciones - 2
Índice
1. Introducción
2. Problemas de recorrido mínimo
3. Problemas de distribución de recursos
4. Problemas de planificación
5. Problemas de producción bajo pedido
6. Problema de la mochila
74Investigación de Operaciones 2
▪ Una empresa sabe que la demanda de su producto durante cada uno de
los 4 siguientes meses será: 1, 3, 2 y 4 unidades. Al principio de cada
mes, la empresa debe determinar cuánto se debe producir con el fin de
cubrir la demanda de ese mes.
▪ Cada mes que hay producción se incurre en un costo de preparación de
$3. El costo por cada unidad producida es de $1. Al final de cada mes se
incurre en un costo de $0,50 por cada unidad en inventario.
▪ Las limitaciones de capacidad permiten la producción de un máximo de
5 unidades cada mes. El tamaño de los almacenes de la empresa
restringe el inventario final de cada mes a 4 unidades como máximo.
▪ La empresa desea determinar cuánto producir cada mes, de tal manera
que se cumpla a tiempo con las demandas y se reduzca al mínimo los
costos totales durante los 4 meses.
▪ Se asume que el inventario inicial es cero.
Ejemplo
4. PROBLEMAS DE PLANIFICACIÓN
75Investigación de Operaciones 2
¿Qué hay que decidir?
Cuánto producir cada mes
Entonces, cada etapa es un mes
Variable de decisión: 𝑥𝑖= producción del mes 𝑖
Dado un mes (etapa) , con demanda 𝐷𝑖, ¿de qué variable 
depende que se quiera producir más o menos ?
Del nivel de inventario inicial: variable de estado 𝑠𝑖
Dentro del rango de valores de 𝑥𝑖 ¿Cómo se decide el óptimo?
Por el coste total. 𝑓𝑖 𝑠𝑖 , 𝑥𝑖 =costes totales
76Investigación de Operaciones 2
4. PROBLEMAS DE PLANIFICACIÓN
• Variable de estado: 𝑠𝑖 = nivel de inventario en el mes de la etapa i
• Variable de decisión: 𝑥𝑖 =producción en mes de la etapa i
• Coste de producción 𝑐𝑝𝑖𝑖 = 𝑐𝑝 𝑠𝑖 , 𝑥𝑖 ≡ 𝑐𝑝 𝑥𝑗 = 3 × 𝐼𝑥𝑖>0 + 𝑥𝑖
• Coste inventario 𝑐𝑖𝑖𝑖 = 𝑐𝑖 𝑠𝑖 , 𝑥𝑖 = 0.5 × (𝑠𝑖 + 𝑥𝑖 − 𝐷𝑖) = 0.5 × 𝑠𝑖−1
• Coste total 𝑐𝑡𝑖𝑖 = 𝑐𝑝𝑖𝑖 + 𝑐𝑖𝑖𝑖
• Objetivo: min
𝑥𝑖
σ𝑖=1
4 3 × 𝐼𝑥𝑖>0 + 𝑥𝑖 − 0.5 𝑠𝑖 + 𝑥𝑖 − 𝐷𝑖
s.a
• Demanda mes etapa i: mes 1:𝐷4 = 1 mes 2: 𝐷3 = 3, mes 3: 𝐷2 = 2, mes 4: 
𝐷1 = 4
• Ecuación de transformación de estado: 𝑠𝑛 + 𝑥𝑛 − 𝐷𝑛 = 𝑠𝑛−1
0 ≤ 𝑥𝑖 ≤ 5; 0 ≤ 𝑠𝑖 ≤ 4; 𝑠𝑖−1 = 𝑠𝑖 + 𝑥𝑖 − 𝐷𝑖
77Investigación de Operaciones 2
4. PROBLEMAS DE PLANIFICACIÓN
0
4
3
2
1
0 0
4
3
2
1
0
Etapa 2: MES 3 Etapa 1: MES 4
4
3
2
1
0
Etapa 3: MES 2Etapa 4: MES 1
𝑥1 = 4
𝐷1 = 4𝐷2 = 2𝐷3 = 3𝐷4 = 1
inventario 
mes 1
inventario 
mes 2
inventario 
mes 3
inventario 
mes 4
inventario 
final
𝑥4 = 1 𝑥3 = 3
𝑥3 = 3
𝑥2 = 2
𝑥2 = 2
78Investigación de Operaciones 2
𝑠1
𝑓1 𝑠1, 𝑥1 = 𝑐𝑝11 + 𝑐11
0 1 2 3 4 5 f1* x1*
0 - - - - 7 - 7 4
1 - - - 6 - - 6 3
2 - - 5 - - - 5 2
3 - 4 - - - - 4 1
4 0 - - - - - 0 0
𝑥1
Etapa 1: Demanda=4, inventario inicial= 𝑠1, inventario final=0, producción = 𝑥1
• Si 𝑠1 = 0 no hay más opción que producir toda la demanda 
⇒ 𝑥1 = 4
Coste 𝑐11 = 𝑐𝑝11 + 𝑐𝑖11 = 3 + 4 + 0 = 7
• Si 𝑠1 = 1, no hay más opción que producir 3 unidades más 
para cubrir la demanda ⇒ 𝑥1 = 3
Coste 𝑐11 = 𝑐𝑝11 + 𝑐𝑖11 = 3 + 3 + 0 = 6
• Si 𝑠1 = 4, no hay que producir nada para cubrir la demanda ⇒
𝑥1 = 0
Coste 𝑐11 = 𝑐𝑝11 + 𝑐𝑖11 = 0 + 0 + 0 = 0
0
Etapa 1: MES 4
4
3
2
1
0
𝑥1 = 4
79Investigación de Operaciones 2
𝑠1
𝑓1 𝑠1, 𝑥1 = 𝑐𝑝11 + 𝑐11
0 1 2 3 4 5 f1* x1*
0 - - - - 7 - 7 4
1 - - - 6 - - 6 3
2 - - 5 - - - 5 2
3 - 4 - - - - 4 1
4 0 - - - - - 0 0
𝑥1
Etapa 1: Demanda=4, inventario inicial= 𝑠1, inventario final=0, producción = 𝑥1
• Si 𝑠1 = 0 no hay más opción que producir toda la demanda 
⇒ 𝑥1 = 4
Coste 𝑐11 = 𝑐𝑝11 + 𝑐𝑖11 = 3 + 4 + 0 = 7
• Si 𝑠1 = 1, no hay más opción que producir 3 unidades más 
para cubrir la demanda ⇒ 𝑥1 = 3
Coste 𝑐11 = 𝑐𝑝11 + 𝑐𝑖11 = 3 + 3 + 0 = 6
• Si 𝑠1 = 4, no hay que producir nada para cubrir la demanda ⇒
𝑥1 = 0
Coste 𝑐11 = 𝑐𝑝11 + 𝑐𝑖11 = 0 + 0 + 0 = 0
0
Etapa 1: MES 4
4
3
2
1
0
𝑥1 = 4
no cubriríamos 
la demanda
tendríamos 
excedentes que 
no venderíamos
80Investigación de Operaciones 2
𝑠2
𝑓2 𝑠2, 𝑥2 = 𝑐𝑝22 + 𝑐𝑖22 + 𝑓1
∗ 𝑠1
𝑠1 = 𝑠2 + 𝑥2 − 𝐷2
0 1 2 3 4 5 f2* x2*
0 - - 12 12.5 13 13.5 12 2
1 - 11 11.5 12 12.5 10 10 5
2 7 10.5 11 11.5 9 - 7 0
3 6.5 10 10.5 8 - - 6.5 0
4 6 9.5 7 - - - 6 0
𝑥2
Etapa 2: Demanda=2, inventario inicial= 𝑠2, inventario final=𝑠1 , producción = 𝑥2
Si 𝑠2 = 0 y 𝑥2 > 2, tendremos al final un inventario 𝑠1 que tendrá un coste. 
No podemos producir 𝑥3 < 2 pues hay que cubrir demanda. 
o Si 𝑥2 = 2 ⇒ 𝑠1 = 0 ⇒ 𝑐𝑡22 = 3 + 2 + 0 = 5
⇒ 𝑓2 𝑠2, 𝑥2 = 𝑐𝑡22 + 𝑓1
∗ 𝑠1 = 0 = 5 + 7 = 12
o Si 𝑥2 = 3 ⇒ 𝑠1 = 1 ⇒ 𝑐𝑡22 = 3 + 3 + 0.5 = 6.5
⇒ 𝑓2 𝑠2, 𝑥2 = 𝑐𝑡22 + 𝑓1
∗ 𝑠1 = 1 = 6.5 + 6 = 12.5
o Si 𝑥2 = 4 ⇒ 𝑠1 = 2 ⇒ 𝑐𝑡22 = 3 + 4 + 1 = 8
⇒ 𝑓2 𝑠2, 𝑥2 = 𝑐𝑡22 + 𝑓1
∗ 𝑠1 = 2 = 8 + 5 = 13… y así sucesivamente
4
3
2
1
0 0
Etapa 2: MES 3 Etapa 1: MES 4
4
3
2
1
0
𝐷4 = 4𝐷3 = 2
no hay 
capacidad de 
almacén
no cubre 
demanda
81Investigación de Operaciones 2
𝑠2
𝑓2 𝑠2, 𝑥2 = 𝑐𝑝22 + 𝑐𝑖22 + 𝑓1
∗ 𝑠1
𝑠1 = 𝑠2 + 𝑥2 − 𝐷2
0 1 2 3 4 5 f2* x2*
0 - - 12 12.5 13 13.5 12 2
1 - 11 11.5 12 12.5 10 10 5
2 7 10.5 11 11.5 9 - 7 0
3 6.5 10 10.5 8 - - 6.5 0
4 6 9.5 7 - - - 6 0
𝑥2
Etapa 2: Demanda=2, inventario inicial= 𝑠2, inventario final=𝑠1 , producción = 𝑥2
Si 𝑠2 = 0 y 𝑥2 > 2, tendremos al final un inventario 𝑠1 que tendrá un coste. 
No podemos producir 𝑥3 < 2 pues hay que cubrir demanda. 
o Si 𝑥2 = 2 ⇒ 𝑠1 = 0 ⇒ 𝑐𝑡22 = 3 + 2 + 0 = 5
⇒ 𝑓2 𝑠2, 𝑥2 = 𝑐𝑡22 + 𝑓1
∗ 𝑠1 = 0 = 5 + 7 = 12
o Si 𝑥2 = 3 ⇒ 𝑠1 = 1 ⇒ 𝑐𝑡22 = 3 + 3 + 0.5 = 6.5
⇒ 𝑓2 𝑠2, 𝑥2 = 𝑐𝑡22 + 𝑓1
∗ 𝑠1 = 1 = 6.5 + 6 = 12.5
o Si 𝑥2 = 4 ⇒ 𝑠1 = 2 ⇒ 𝑐𝑡22 = 3 + 4 + 1 = 8
⇒ 𝑓2 𝑠2, 𝑥2 = 𝑐𝑡22 + 𝑓1
∗ 𝑠1 = 2 = 8 + 5 = 13… y así sucesivamente
4
3
2
1
0 0
Etapa 2: MES 3 Etapa 1: MES 4
4
3
2
1
0
𝐷4 = 4𝐷3 = 2
82Investigación de Operaciones 2
▪ ¿Qué valores puede tomar s3?
▪ ¿Qué valores puede tomar x3?
▪ ¿Qué valores puede tomar 𝑠2?
s3 = inventario 
al inicio
del mes 2
x3 = producción del mes 2
0
1
2
3
4
0 1 2 3 4 f3* x3*5
- - - 18 17,5 16 16 5
- - 17 16,5 15 16 15 4
- 16 15,5 14 15 16 14 3
12 14,5 13 14 15 - 12 0
10,5 12 13 14 - - 10,5 0
Etapa 3: Demanda=3, inventario inicial= 𝑠3, inventario final=𝑠2 , producción = 𝑥3
4
3
2
1
0 0
4
3
2
1
0
Etapa 2: MES 3 Etapa 1: MES 4
4
3
2
1
0
Etapa 3: MES 2
𝐷4 = 4𝐷3 = 2𝐷2 = 3
𝑓3 𝑠3, 𝑥3 = 𝑐𝑝33 + 𝑐𝑖33 + 𝑓2
∗ 𝑠2
𝑠2 = 𝑠3 + 𝑥3 − 𝐷3
83Investigación de Operaciones 2
▪ ¿Qué valores puede tomar s4?
▪ ¿Qué valores puede tomar x4?
x4 = producción del mes 1
0 1 2 3 4 5 f4* x4*
0
s4 = inventario 
al inicio
del mes 1
20 20,5 21 21,5 20,5- 20 1
Solución:
Mes 1: 1 unidad
Mes 2: 5 unidades
Mes 3: 0 
Mes 4: 4 unidades
Costo total: $20
Demanda: 4Demanda: 2
f1* x1*
7 4
6 3
5 2
4 1
0 0
f2* x2*
12 2
10 5
7 0
6.5 0
6 0
mes 3 mes 4
Demanda: 3
mes 2
Etapa 4: Demanda=1, inventario inicial= 𝑠4, inventario final=𝑠3 , producción = 𝑥4
84Investigación de Operaciones 2
4. PROBLEMAS DE PLANIFICACIÓN
0
4
3
2
1
0 0
4
3
2
1
0
Etapa 2: MES 3 Etapa 1: MES 4
4
3
2
1
0
Etapa 3: MES 2Etapa 4: MES 1
𝑥1 = 4
𝐷4 = 4𝐷3 = 2𝐷2= 3𝐷1 = 1
𝑥4 = 1
“Ruta óptima”
¿Cuál sería la solución óptima si cuando estamos en el mes 3 una de 
las unidades del inventario resulta ser inservible? ¿Fabricar una?
85Investigación de Operaciones 2
4. PROBLEMAS DE PLANIFICACIÓN
0
4
3
2
1
0 0
4
3
2
1
0
Etapa 2: MES 3 Etapa 1: MES 4
4
3
2
1
0
Etapa 3: MES 2Etapa 4: MES 1
𝑥1 = 4
𝐷4 = 4𝐷3 = 2𝐷2 = 3𝐷1 = 1
inventario 
mes 1
inventario 
mes 2
inventario 
mes 3
inventario 
mes 4
inventario 
final
𝑥4 = 1 𝑥2 = 2
Diagrama de la solución (completa)
4
3
0
0
5
0
1
2
3
2
1
0
86
Tema 2 
Programación Dinámica
Investigación de Operaciones - 2
Índice
1. Introducción
2. Problemas de recorrido mínimo
3. Problemas de distribución de recursos
4. Problemas de planificación
5. Problemas de producción bajo pedido
6. Problema de la mochila
87Investigación de Operaciones 2
▪ Un pequeño taller de calzado ubicado en Piura ha recibido un pedido
de 12 docenas de pares de zapatos escolares de una zapatería.
Debido a la urgencia de la zapatería y a las limitaciones del taller, que
debe también continuar con su producción diaria, el día domingo se
conviene en entregar la mitad del pedido al final del día miércoles, y el
resto al final del día viernes.
▪ Las limitaciones del taller le impiden producir más de 4 docenas
diarias, aparte de la producción normal diaria. Los costos de
producción de los pedidos adicionales están en función del número de
docenas adicionales que se tenga que producir, y esto depende del
día de la semana, como se muestra en la siguiente tabla de utilidades.
Determine cuánto le conviene producir cada día de la semana.
5. PROBLEMAS DE PRODUCCIÓN BAJO PEDIDO
88Investigación de Operaciones 2
Número de
docenas
producidas
Lun Mar Mié Jue Vie
0 -30 -30 -30 -40 -40
1 30 60 50 20 30
2 110 100 120 110 120
3 180 200 180 180 170
4 160 150 200 160 180
5. PROBLEMAS DE PRODUCCIÓN BAJO PEDIDO
Tabla de utilidades por día de semana y docenas producidas
89Investigación de Operaciones 2
¿Qué hay que decidir?
Entonces, cada etapa es el día: L,M,X,J,V.
Dentro del rango de valores de 𝑥𝑖 en cada 𝑠𝑖 ¿Cómo se decide el óptimo?
Maximizando las Utilidades 𝑓𝑖 𝑠𝑖 , 𝑥𝑖 =utilidades
Cuántos pares (docenas) fabricar cada día
Variable de decisión: 𝑥𝑛= número de pares a fabricar el día de la etapa 𝑛 −ésima
Dado un día (etapa) , con utilidad 𝑈𝑛 ¿qué otra información se necesita para 
decidir producir más o menos?
El número de pares que falta por fabricar al inicio de cada etapa: variable de estado 𝑠𝑛
con ecuación de transformación de estado 𝑠𝑖−1 = 𝑠𝑖 − 𝑥𝑖
90
12 12 12 12
0
11
10
9
8
11
10
8
5
4
9
6
7
11
10
8
5
4
9
6
7
1
0
2
3
12
11
10
8
5
4
9
6
7
1
0
2
3
Diagrama de los estados con las siguientes restricciones: entrega de 6 pares el miércoles, 
y máxima producción diaria de 4. 
L M X J V
Los círculos representan los 
pares que quedan pendientes de 
fabricar al inicio de cada día, y 
las líneas, los trayectos factibles.
12
𝑥5 = 0
𝑥5 = 4
𝑥4 = 0
𝑥4 = 4 x3 = 0
𝑥3 = 4
Si produzco 4 
cada día el 
miércoles 
acabaría
91
12 12 12 12
0
11
10
9
8
11
10
8
5
4
9
6
7
11
10
8
5
4
9
6
7
1
0
2
3
12
11
10
8
5
4
9
6
7
1
0
2
3
Diagrama de los estados con las siguientes restricciones: entrega de 6 pares el miércoles, 
y máxima producción diaria de 4. 
L M X J V
Los círculos representan los pares 
que quedan pendientes de fabricar 
al inicio de cada día, y las líneas, los 
trayectos factibles.
12
𝑥5 = 0
𝑥5 = 4
𝑥4 = 0
𝑥4 = 4 x3 = 0
𝑥3 = 4
x3 = 4
x4 = 2
Para entregar 6 el 
miércoles, deben 
quedar por 
entregar otros 6. 
Habrá un mínimo 
de producción 
diaria que hay que 
cumplir
92
12 12 12 12
0
11
10
9
8
11
10
8
5
4
9
6
7
11
10
8
5
4
9
6
7
1
0
2
3
12
11
10
8
5
4
9
6
7
1
0
2
3
Diagrama de los estados con las siguientes restricciones: entrega de 6 pares el miércoles, 
y máxima producción diaria de 4. 
L M X J V
Los círculos representan los pares 
que quedan pendientes de fabricar 
al inicio de cada día, y las líneas, los 
trayectos factibles.
𝑥5 = 0
𝑥5 = 4
93Investigación de Operaciones 2
⚫ ¿Qué valores puede tomar s1?
⚫ ¿Qué valores puede tomar x1?
Número de 
docenas 
producidas
Viernes
0 -40
1 30
2 120
3 170
4 180
0
4
1
0
2
3
Etapa 1 (viernes)
𝑥1
𝑓1(𝑠1, 𝑥1) = 𝑈11
𝑠1
0 1 2 3 4 𝑓1
∗ 𝑥1
∗
0 −40 −40 0
1 30 30 1
2 120 120 2
3 170 170 3
4 180 180 4
𝑈11
94Investigación de Operaciones 2
⚫ ¿Qué valores puede tomar s2?
⚫ ¿Qué valores puede tomar x2?
Etapa 2 (jueves) 𝑈22
5
4
6
1
0
2
3
4
1
0
2
3
𝑥2
𝑓2(𝑠2, 𝑥2) = 𝑈22 + 𝑓1
∗(𝑠1)
𝑠1 = 𝑠2 − 𝑥2
𝑠2
0 1 2 3 4 𝑓2
∗ 𝑥2
∗ 𝑠1(𝑥2
∗)
0 −80 −80 0 0
1 −10 −20 −10 0 1
2 80 50 70 80 0 2
3 130 140 140 140 140 1,2,3 2,1,0
4 140 190 230 210 120 230 2 2
5 200 280 300 190 300 3 2
6 290 350 280 350 3 3
Número de
docenas
producidas
Jue
0 -40
1 20
2 110
3 180
4 160
𝑓2 𝑠2 = 4, 𝑥2 = 3 = 180 + 𝑓1
∗ 1 = 180 + 30 = 210
95Investigación de Operaciones 2
⚫ ¿Qué valores puede tomar 𝑠3?
⚫ ¿Qué valores puede tomar 𝑥3?
Etapa 3 (miércoles)
𝑈33
𝑓3 𝑠3 = 6, 𝑥3 = 2 = 120 + 𝑓2
∗ 4 = 120 + 230 = 350
Número de 
docenas 
producidas
Miércoles
0 -30
1 50
2 120
3 180
4 200
𝑥3
𝑓3(𝑠3, 𝑥3) = 𝑈33 + 𝑓2
∗(𝑠2)
𝑠2 = 𝑠3 − 𝑥3
𝑠3
0 1 2 3 4 𝑓3
∗ 𝑥3
∗ 𝑠2(𝑥3
∗)
4 200 190 200 170 120 200 0 𝑦 2 4 𝑦 2
5 270 280 260 260 190 280 1 4
6 320 350 350 320 280 350 1 y 2 5 y 4
7 400 420 410 340 420 2 5
8 470 480 430 480 3 5
9 530 500 530 3 6
10 550 550 4 6
10
8
5
4
9
6
7
5
4
6
1
0
2
3
96Investigación de Operaciones 2
⚫ ¿Qué valores puede tomar 𝑠4?
⚫ ¿Qué valores puede tomar 𝑥4?
Etapa 4 (martes)
𝑈44
𝑓4 𝑠4 = 10, 𝑥4 = 2 = 100 + 𝑓3
∗ 8 = 100 + 480 = 580
Número de 
docenas 
producidas
Martes
0 -30
1 60
2 100
3 200
4 150
12
11
10
9
8
10
8
5
4
9
6
7
𝑥4
𝑓4(𝑠4, 𝑥4) = 𝑈44 + 𝑓3
∗(𝑠3)
𝑠3 = 𝑠4 − 𝑥4
𝑠4
0 1 2 3 4 𝑓4
∗ 𝑥4
∗ 𝑠3(𝑥4
∗)
8 450 480 450 480 350 480 1 𝑦 3 7 𝑦 5
9 500 540 520 550 430 550 3 6
10 520 590 580 620 500 620 3 7
11 610 630 680 570 680 3 8
12 650 730 630 730 3 9
97Investigación de Operaciones 2
⚫ ¿Qué valores puede tomar 𝑠5?
⚫ ¿Qué valores puede tomar 𝑥5?
Etapa 5 (lunes) 𝑈55
𝑓5 𝑠5 = 12, 𝑥5 = 4 = 160 + 𝑓4
∗ 8 = 160 + 480 = 640
Número de 
docenas 
producidas
Lunes
0 -30
1 30
2 110
3 180
4 160
12 12
11
10
9
8
𝑥5
𝑓5(𝑠5, 𝑥5) = 𝑈55 + 𝑓4
∗(𝑠4)
𝑠4 = 𝑠5 − 𝑥5
𝑠5 0 1 2 3 4 𝑓3
∗ 𝑥3
∗ 𝑠2(𝑥3
∗)
12 700 710 730 730 640 730 2 𝑦 3 10 𝑦 9
lunes martes miércoles jueves viernes
A
B
C
Plan de 
acción
Soluciones:
2 3 2 3 2
3 3 1 3 2
3 3 2 2 2
99
Tema 2 
Programación Dinámica
Investigación de Operaciones - 2
Índice
1. Introducción
2. Problemas de recorrido mínimo
3. Problemas de distribución de recursos
4. Problemas de planificación
5. Problemas de producción bajo pedido
6. Problema de la mochila
100Investigación de Operaciones 2
6. PROBLEMA DE LA MOCHILA
El problema de la mochila es un problema-tipo muy popular en programación
dinámica, así como e programación no entera (O1).
Resuelve una situación similar al llenado de una mochila que, lógicamente, sólo
admite hasta un peso determinado. Hay que seleccionar el subconjunto de objetos,
cada uno con un peso y una utilidad o valor específicos. La selección de objetos
debe maximizar la utilidad o valor total sin exceder el peso máximo.
???
max 10 kg
4 kg/$8 2 kg/$2
2 kg/$9
5 kg/$3
2 kg/7$
1 kg/$6
101Investigación de Operaciones 2
6. PROBLEMA DE LA MOCHILA
???
Es un caso particular de problema de reparto de esfuerzo o recursos. Ahora hay que
repartir la capacidad de la mochila entre los diferentes objetos.
¿Qué hay que decidir?
Entonces, cada etapa es un objeto
Dentro del rango de valores de 𝑥𝑖 = 0,1 en cada 𝑠𝑖 ¿Cómo se decide el óptimo?
Maximizando las Utilidades 𝑓𝑖 𝑠𝑖 , 𝑥𝑖 =utilidades
Qué objetos introduciren la mochila
Variable de decisión: 𝑥𝑛= seleccionar o no (1/0) el objeto 𝑛 −ésimo
Dado un objeto (etapa) , con utilidad 𝑈𝑛 ¿qué otra información se necesita?
La capacidad que falta por asignar: variable de estado 𝑠𝑛
con ecuación de transformación de estado 𝑠𝑖−1 = 𝑠𝑖 − 𝑥𝑖
103Investigación de Operaciones 2
Un ingeniero está a punto de regresar de una excursión de trabajo en
el desierto. Su vehículo se descompone a una distancia considerable
de la carretera y decide cargar sólo hasta 11 Kg. El equipo científico
contiene varias piezas importantes, por lo que elabora un inventario,
donde asigna un factor de importancia de cada artículo, y construye un
bolso especial de 1 kg, que podrá contener cualquier volumen que
decida cargar. ¿Qué artículos debe cargar si quiere maximizar la
importancia?
6. PROBLEMA DE LA MOCHILA
Artículo 4 3 2 1
Peso 4 6 3 2
Importancia 5 7 3 6
Sean:
si = disponibilidad en la etapa i.
xi = si carga (1) o no carga (0) el artículo i.
104
10 10
8
5
4
9
6
7
1
0
2
3
Artículo 4
peso 4
Los círculos representan kilos que aún pueden introducirse en la mochila
Artículo 2
peso 3
Artículo 1
peso 2
Artículo 3
peso 6
10
8
5
4
9
6
7
1
0
2
3
10
8
5
4
9
6
7
1
0
2
3
𝑥4 = 0
10
8
5
4
9
6
7
1
0
2
3
𝑠4
𝑠3 𝑠2 𝑠1
105
10
8
5
4
9
7
1
0
2
3
Artículo 4
peso 4
Los círculos representan kilos que aún pueden introducirse en la mochila
Artículo 2
peso 3
Artículo 1
peso 2
Artículo 3
peso 6
8
5
9
7
1
0
2
3
10
8
5
4
9
6
7
0
2
𝑥4 = 0
5
4
9
6
7
1
0
2
3
𝑠4
𝑠3 𝑠2 𝑠1
4
6
10 10
6
10
8
3
1
106Investigación de Operaciones 2
Etapa 1: artículo 1. Peso=2, utilidad=6 
𝑥1
𝑠1
0 1 𝑓1
∗ 𝑥1
∗
0 − 1 0 0 0
2 − 10 0 6 6 1
Etapa 2: artículo 2. Peso=3, utilidad=3 
𝑥2
𝑠2 0 1
𝑓2
∗ 𝑥2
∗ 𝑠1(𝑥1
∗)
0 0 0 0 0
4 6 3 6 0 4
6 6 9 9 1 3
10 6 9 9 1 7
(fijándonos en el 
diagrama de los 
estados, éstos 
son los únicos 
posibles)
(fijándonos en el 
diagrama de los 
estados, salen 
muchos estados 
diferentes. Es más 
sencillo usar esta 
agregación)
107Investigación de Operaciones 2
Etapa 3: artículo 3. Peso=6, utilidad=7 
Etapa 4: artículo 4. Peso=4, utilidad=5 
𝑥3
𝑠3 0 1
𝑓3
∗ 𝑥3
∗ s2(𝑥3
∗)
6 9 7 9 0 6
10 9 13 13 1 4
𝑥4
𝑠4 0 1 𝑓4
∗ 𝑥4
∗ 𝑠3(𝑥4
∗)
10 13 14 14 1 6
Solución: hay que cargar los artículos 4, 2 y 1. El peso total 
será de 9 y el beneficio de 14.
(fijándonos en el 
diagrama de los 
estados, éstos 
son los únicos 
posibles)