Tema 1

Introducci on a la Programacion
Dinamica. El Problema de la
Mochila
La programacion din amica no es un algoritmo. Es mas bien un principio gener-
al aplicable a diversos problemas de optimizacion que verican una cierta propiedad
denominada descomponibilidad.
1.1. El problema de la Mochila
Un excursionista debe decidir, entre n objetos, cuales de ellos va a llevarse en su
mochila. Cada objeto supone para el excursionista un benecio c
j
y ocupa una capaci-
dad de a
j
. La mochila tiene una capacidad maxima b. La formulacion del problema
sera la siguiente:
1
2 Tema 1. Introduccion a la Programacion Dinamica. El Problema de la Mochila
(KP) Maximizar
n

j=1
c
j
x
j
s.a
n

j=1
a
j
x
j
b
x
j
{0, 1} j = 1, ..., n
donde a
j
N j = 1, ..., n ; b N y c
j
R j = 1, ..., n .
La idea principal de la programacion dinamica consiste en intentar reducir el problema
(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 natu-
raleza.
En el caso del problema (KP) se considera la siguiente familia de n(b+1) problemas:
[KP
i
(E)] Maximizar
n

j=i
c
j
x
j
s.a
n

j=i
a
j
x
j
+E b
x
j
{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 cati-
dad sea vectorial). El conjunto de los posibles valores de E se denomina espacio de
estados 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
hecho [KP
1
(0)]). Se denotar a por F

i
(E) al valor optimo de [KP
i
(E)]. Cuando E < 0
o E > b el problema es infactible y se acuerda que F

i
(E) = . El valor optimo del
problema original es F

= F

1
(0).
Buscar una relaci on recurrente que conecte los valores optimos de los difer-
entes problemas de la familia
Para ello vamos a analizar la familia de problemas [KP
i
(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 saber cu al es la mejor decision que puede tomar.
Etapa n. En [KP
n
(E)] el excursionista debe decidir si introduce o no el objeto n. Si ha
ocupado ya una capacidad E > b a
n
, no puede hacerlo, y por lo tanto F

n
(E) = 0. En
caso de que E b a
n
, a un existe la posibilidad de introducir el objeto. Lo har a si su
benecio es positivo (c
n
0) con lo cual F

n
(E) = c
n
, o lo desechar a en caso contrario
(c
n
< 0), con lo cual F

n
(E) = 0
Etapa n-1. En [KP
n1
(E)] debe decidir si se introducen los objetos n1 y n, pero con
lo indicado en el apartado anterior se puede simplicar el problema a decidir solamente
sobre el objeto n1. Si se introduce dicho objeto, en la etapa n el problema a resolver
ser a [KP
n
(E + a
n1
)], por tanto se obtendra un benecio de c
n1
+ F

n
(E + a
n1
),
y si no lo introducimos, en la etapa n el problema a resolver ser a [KP
n
(E)] y obten-
dremos un benecio de F

n
(E). Por tanto la decisi on se basa simplemente en la siguiente
comparaci on.
F

n1
(E) = Max{c
n1
+F

n
(E +a
n1
), F

n
(E)}
4 Tema 1. Introduccion a la Programacion Dinamica. El Problema de la Mochila
Etapa i. Con un razonamiento an alogo al de la etapa n 1, en una etapa intermedia
i, 1 i n, tendremos la siguiente relaci on:
F

i
(E) = Max{c
i
+F

i+1
(E +a
i
), F

i+1
(E)}
Algoritmo para la resoluci on del problema de la mochila por
programaci on dinamica
Etapa n
Para todo E (0 E b) calcular F

n
(E) - F

n
(E) = 0 si E > b a
n
- F

n
(E) = c
n
si E b a
n
y c
n
0
- F

n
(E) = 0 si E b a
n
y c
n
< 0
Etapa i
Para cada i = n 1, ...., 2 calcular:
F

i
(E) = Max{c
i
+F

i+1
(E +a
i
), F

i+1
(E)}
para todo 0 E b.
Etapa 1
Calcular F

= Max{F

2
(0), c
1
+F

2
(a
1
)}
Comentario. La etapa 1 se puede extender calculando, para cada 0 E b
F

1
(E) = Max{F

2
(E), c
1
+F

2
(E +a
1
)}
De este modo, F

= F

1
(0) y ademas, para cada 0 E b, F

1
(E) representara la
utilidad maxima posible en una mochila de carga m axima b E.
1.2. Ejercicios 5
Obtenci on de la solucion optima
Mediante el algoritmo anterior se obtiene el valor optimo de (KP) pero no la solucion
optima x

explcitamente. Para ello se procede del siguiente modo.

0 si F

i
(E) = F

i+1
(E)
1 si F

i
(E) = c
i
+F

i+1
(E +a
i
)
Siendo inicialmente E=0 y actualizando en cada paso el valor de E a E +a
i
x

i
. Final-
mente,
x
n
=

0 si F

n
(E) = 0
1 si F

n
(E) = c
n
1.2. Ejercicios
1. Un navegante solitario dispone en su barco de 5 metros c ubicos para almacenar
cuatro objetos. El objeto A tiene un volumen de 2 m
3
y reporta al navegante 3
unidades de benecio (ub). Los objetos B,C, y D ocupan respectivamente 4,3 y
2 m
3
y el benecio respectivo es de 5,1 y 1 ub.
a) Determinar mediante un algoritmo de programacion dinamica cuales son los
objetos que debe llevar el navegante.
b) Que ocurrira si la capacidad del barco fuese respectivamente de 4, 3, 2 o 1
metros c ubicos?
2. Adaptacion del algoritmo de programaci on din amica para la resolucion del proble-
6 Tema 1. Introduccion a la Programacion Dinamica. El Problema de la Mochila
ma de la mochila 0-1 unidimensional al caso en que la restriccion sea de igualdad:
Max 3x
1
+ 5x
2
+x
3
+x
4
x
5
s.a
2x
1
+ 4x
2
+ 3x
3
+ 2x
4
+x
5
= 5
x
i
{0, 1} i = 1, 2, 3, 4, 5
3. Adaptacion del algoritmo de programaci on din amica para la resolucion del prob-
lema de la mochila unidimensional al caso en que las variables son enteras y
acotadas de la forma 0 x
j
M
j
:
Max 5x
1
+ 3x
2
+x
3
+x
4
s.a
4x
1
+ 2x
2
+ 3x
3
+ 2x
4
5
x
i
{0, 1, 2} i = 1, 2, 3, 4
4. Adaptacion del algoritmo de programaci on din amica para la resolucion del prob-
lema de la mochila unidimensional al caso en que las variables son enteras y no
acotadas:
Maximizar 5x
1
+ 4x
2
+ 2x
3
s.a
4x
1
+ 3x
2
+ 2x
3
8
x
j
Z
+
j = 1, 2, 3
1.2. Ejercicios 7
5. Adaptacion del algoritmo de programaci on din amica para la resolucion del prob-
lema de la mochila 0-1 bidimensional:
Max 4x
1
+x
2
+ 5x
3
s.a
2x
1
+x
2
+ 3x
3
4
x
1
+ 2x
2
+ 2x
3
3
x
i
{0, 1} i = 1, 2, 3
6. Un cami on puede transportar un total de 10 toneladas de productos. Hay tres
clases de productos para transportar, cuyo peso y valor se muestran en la siguiente
tabla. Suponiendo que por lo menos se debe transportar un artculo de cada clase,
determinar el cargamento que maximiza el valor total.
Clase Valor (miles de euros) Peso (tn)
A 2 1
B 5 2
C 6 2