Programacion dinamica

Tema 1
Introducci´n a la Programaci´n
o
o
Din´mica. El Problema de la
a
Mochila
“La programaci´n din´mica no es un algoritmo. Es m´s bien un principio genero
a
a
al aplicable a diversos problemas de optimizaci´n que verifican una cierta propiedad
o
denominada descomponibilidad”.

1.1.

El problema de la Mochila

Un excursionista debe decidir, entre n objetos, cuales de ellos va allevarse en su
mochila. Cada objeto supone para el excursionista un beneficio cj y ocupa una capacidad de aj . La mochila tiene una capacidad m´xima b. La formulaci´n del problema
a
o
ser´ la siguiente:
ıa

1

2

Tema 1. Introducci´n a la Programaci´n Din´mica. El Problema de la Mochila
o
o
a
n

(KP )

Maximizar

cj x j
j=1

s.a
n

aj x j ≤ b
j=1

xj ∈ {0, 1}

j =1, ..., n

donde aj ∈ N ∀j = 1, ..., n ; b ∈ N y cj ∈ R ∀j = 1, ..., n .
La idea principal de la programaci´n din´mica consiste en intentar reducir el problema
o
a
(KP) de n variables en una secuencia de problemas en una sola variable. Para ello es
necesario llevar a cabo dos operaciones:

Encajar el problema dado en una familia de problemas de la misma naturaleza.
En el caso delproblema (KP) se considera la siguiente familia de n(b+1) problemas:
n

[KPi (E)]

Maximizar

cj x j
j=i

s.a
n

aj xj + E ≤ b
j=i

xj ∈ {0, 1}

j = i, ..., n

con i variando entre 1 y n, y E entero variando entre 0 y b.
La cantidad E se denomina variable de estado (o vector de estado cuando la catidad sea vectorial). El conjunto de los posibles valores de E se denomina espacio deestados y se representa por ξ. En este caso ξ = {0, 1, ..., b}.

1.1. El problema de la Mochila

3

Se puede observar que el problema original [KP] es un miembro de la familia (es de
o
hecho [KP1 (0)]). Se denotar´ por Fi∗ (E) al valor ´ptimo de [KPi (E)]. Cuando E < 0
a
o E > b el problema es infactible y se acuerda que Fi∗ (E) = −∞. El valor ´ptimo del
o
∗
problema original es F ∗ =F1 (0).

Buscar una relaci´n recurrente que conecte los valores ´ptimos de los difero
o
entes problemas de la familia
Para ello vamos a analizar la familia de problemas [KPi (E)]. Supongamos que en la
mochila, al decidir sobre los objetos j=1,...,i-1, se ha ocupado una capacidad E. Por
tanto queda una capacidad b-E para decidir sobre los objetos j=i,...,n. El excursionista
desea sabercu´l es la mejor decisi´n que puede tomar.
a
o

Etapa n. En [KPn (E)] el excursionista debe decidir si introduce o no el objeto n. Si ha
∗
ocupado ya una capacidad E > b − an , no puede hacerlo, y por lo tanto Fn (E) = 0. En

caso de que E ≤ b − an , a´n existe la posibilidad de introducir el objeto. Lo har´ si su
u
a
∗
a
beneficio es positivo (cn ≥ 0) con lo cual Fn (E) = cn , o lodesechar´ en caso contrario
∗
(cn < 0), con lo cual Fn (E) = 0

Etapa n-1. En [KPn−1 (E)] debe decidir si se introducen los objetos n−1 y n, pero con
lo indicado en el apartado anterior se puede simplificar el problema a decidir solamente
sobre el objeto n − 1. Si se introduce dicho objeto, en la etapa n el problema a resolver
∗
ser´ [KPn (E + an−1 )], por tanto se obtendr´ un beneficio de cn−1 +Fn (E + an−1 ),
a
ıa

y si no lo introducimos, en la etapa n el problema a resolver ser´ [KPn (E)] y obtena
∗
dremos un beneficio de Fn (E). Por tanto la decisi´n se basa simplemente en la siguiente
o

comparaci´n.
o
∗
∗
∗
Fn−1 (E) = M ax{cn−1 + Fn (E + an−1 ), Fn (E)}

4

Tema 1. Introducci´n a la Programaci´n Din´mica. El Problema de la Mochila
o
o
a

Etapa i. Con unrazonamiento an´logo al de la etapa n − 1, en una etapa intermedia
a
i, 1 ≤ i ≤ n, tendremos la siguiente relaci´n:
o
∗
∗
Fi∗ (E) = M ax{ci + Fi+1 (E + ai ), Fi+1 (E)}

Algoritmo para la resoluci´n del problema de la mochila por
o
programaci´n din´mica
o
a
Etapa n
∗
∗
Para todo E (0 ≤ E ≤ b) calcular Fn (E) - Fn (E) = 0 si E > b − an
∗
- Fn (E) = cn si E ≤ b − an y cn ≥ 0
∗
- Fn...