PROGRAMACION DINAMICA
Es un tipo de programación de la IO que se utiliza para problemas para los cuales la programación
lineal no puede ser aplicable
Un caso muy común es el problema de la mochila
Por ejemplo, yo tengo una maleta que tiene una capacidad de 40 kilogramos de capacidad y me
dan la posibilidad de cargar uno o más de tres artículos, y me dan ingreso por cargar unos o
varios artículos de estos
Articulo 1 pesa 20 kg articulo 2 pesa 30 kg y el 3 me pesa 10 kg
¿Cuál sería la mejor opción para maximizar los ingresos totales?
Programación dinámica busca dividir el problema en subproblemas y los va solucionando hasta
encontrar una solución óptima.
De atrás hacia adelante
METODOLOGIA
1. Cada problema debe dividirse en etapas
2. Cada etapa se divide en estados, los cuales representan una posibilidad de realizar una
etapa
3. En cada etapa habrá una política de decisión
4. El método de programación dinámica debe hallar una solución optima
5. El problema inicia por la última etapa y se mueve recursivamente
TERMINOLOGIA
N= número total de etapas
n= estado particular donde n =1,2……N
en = estado particular de la etapa n
Xn = Variable de decisión de la etapa n
Xn* = Valor óptimo de Xn para cada en
Fn(en,Xn) = CONTRIBUCIÓN ACUMULADA DE LA FO de la etapa n hasta la N
Problema de la diligencia
En el siguiente esquema se muestran 10 ciudades en las cuales se indican las rutas para abastecer
un producto A hasta j y sobre las flechas se dan los costos de fletes en miles de pesos , ¿ cual será
la mejor ruta que hay que seguir para minimizar el costo total?
ETAPA 1 ETAPA 2 ETAPA 3 ETAPA 4 ETAPA 5
B 16 D 12 F 7 H 15
10 6 4
A 13 J
13 15 9 6 12
C E G 8 I
14 11
F(en, Xn) = CenXn+ Fn+1(Xn+1) función recursiva
ETAPA 5
F(e5,X5) = Ce5X5+F6(X6) F(I,J) = 12+0 =12
F(H,J) = 15+0 = 15
, e5 , f5(e5) X5
H 15 J
I 12 J
ETAPA 4
F(e4,X4) = Ce4X4+F5(X5)
F(F,H) = 7+15 =22 , F(F,I)= 4+12 =16 F(G,H) = 6+15 =21 F(G,I) = 8+12 = 20
,e4 H I F4*(e4) X4
F 22 16 16 I
G 21 20 20 I
ETAPA 3
F(e3,X3) = Ce3X3+F4(X4)
F(D,F) = 12+16 = 28 , F(D,G)= 6+20 =26 , F(E,F) = 9+16 =25 , F(E,G)=11+20 =31
,e3 F G F3*(e3) X3
D 28 26 26 G
E 25 31 25 F
ETAPA 2
F(e2,X2) = Ce2X2+F3(X3)
F(B,D) =16+26 = 42 , F(B,E)= 13 +25 = 38 F(C,D) = 15+26 =41 , F ( C, E)= 14+25 =39
,e2 D E F2*(e2) X2
B 42 38 38 E
C 41 39 39 E
ETAPA 1
F(e1,X1) = Ce1X1+F2(X2)
F(A,B) = 10+ 38 =48 F (A,C) = 13+39 = 52
,e1 B C F1*(e1) X2
A 48 52 48 B
A – B- E-F-I-J = 48
B 2 D 3 F
3 9 2
2
A 4 M 8 L 4 N 5H
1 7 2
4
C 6E 3G
ETAPA N 4
, f4 ( e4, X4) = Ce4X4+f5*(x5)
, e4 F4(e4) X4
F 2 H
N 5 H
G 4 H
ETAPA N 3 , f3 ( e3, X3) = Ce3X3+f4*(x4)
, e3 F N G F3(e3) X3
D 5 - - 5 F
L 4 9 6 4 F
E - - 7 7 G
ETAPA N 2 , f2 ( e2, X2) = Ce2X2+f3*(x3)
, e2 D L E F2(e2) X2
B 7 - - 7 D
M 14 12 14 12 L
C - - 13 13 E
ETAPA N 1 , f1 ( e1, X1) = Ce1X1+f2*(x2)
, e1 B M C F1(e1) X1
A 10 16 14 10 B
A-B-D-F-H =10
PROBLEMA DE LA MOCHILA
Ejemplo
Un barco de 4 toneladas se carga con uno o más artículos. La tabla siguiente muestra el peso
unitario Wi en toneladas y el ingreso por unidad rj en miles de dólares para el articulo i ¿Cómo se
debe cargar el barco para maximizar los ingresos totales?
Articulo i Wi peso Toneladas Ri Ingreso
1 2 31
2 3 47
3 1 14
Capacidad : 4 toneladas
, i = la etapa 1,2,3
Xi = estado de la etapa i quiere decir cuántas unidades voy a colocar de cada articulo
, mi = cantidad del articulo i
, fi = ingreso esperado ri*mi
, mi = Wt / Wi
Fn(Xn) = MAX ri*mi+ Fn+1(Xn-Wi*mi)
ETAPA 3 ARITCULO 3
, m3 = 4 toneladas/ 1 tonelada = 4 articulos de 3
F3(X3) = MAX 14m3 +F4( (X3-1*m3) = max 14 m3
Xn / mi ,m3 =0 ,m3=1 ,m3=2 ,m3=3 ,m3=4 F3(X3) ,m3
0 0 - - - - 0 0
1 0 14 - - - 14 1
2 0 14 28 - - 28 2
3 0 14 28 42 - 42 3
4 0 14 28 42 56 56 4
ETAPA 2 ARTICULO 2
, m2 = 4 toneladas /3 toneladas = 1,25 se aproxima 1 tonelada
F2(X2) = MAX 47m2 +F3( (X2-3*m2)
Xn/mi ,m2=0 ,m2=1 F2(X2) .m2
0 0 - 0 0
1 14 - 14 0
2 28 - 28 0
3 42 47 47 1
4 56 61 61 1
X2=0 ,m2 =0 F2(0) = max47(0)+F3(0-(3*0)) = 0+F3(0) =0
X2= 1 , m2 =0 F2(1) = max47(0)+F3(1-(3*0)) = 0+F3(1)
X2=2 , m2 =0 F2(2) =max47(0)+F3(2- (3*0))= F3(2) =28
X2=0 ,m2 = 1 F2(0) = max 47 (1)+F3(0-3*1)= 47+ F3(-3) = NO ES FACTIBLE
X2 = 1, m2 = 1 F2(1) = max47(1)+F3(1-(3*1)) = 47+F3(-2) = no factible
X2= 3 ,m2 =1 F2(3) = max 47( 1)+F3( 3-(3*1) = 47+F3(0) = 47+0 = 47
X2=4, m2 =1 F2(4) = max 47 +F3(4-(3*1) = 47+F3(1) =47+14 =61
ETAPA 1 ARTICULO 1
Fn(Xn) = MAX ri*mi+ Fn+1(Xn-Wi*mi)
F1(X1) = MAX 31*m1+F2(X2-2m1) m1= 4 / 2 = 2 artículos 1
Xn/ mi ,m1=0 ,m1=1 ,m1=2 F1(X1) ,m1
0 0 - - 0 0
1 14 - - 14 0
2 28 31+0 =31 - 31 1
3 47 31+14 =45 - 47 0
4 61 31+28 =59 62 62 2
X1=0 , m1=0 Max 31*0 +F2(0-(2*0)) = 0+ F2(0) = 0
X1=1, m1 =0 Max 31*0+F2(1-(2*0)) = 0+F2(1) = 14
X1=0 , m1=1 = MAX 31 *1+F2(0-(2*1)) = 31+F2(-2)) = no es factible
X1=2 , m1 =1 = MAX 31*1 +F2(2-(2*1)) = 31+F2(0) =31 , x1=
X1 =3 ,m1 =1= Max 31*1+F2(3-(2*1) =31+F2(1) = 31+14 =45
X1= 4 , m1= 2 = max 31*2)+F2(4-(2*2)) = 62 +F2(0) = 62
LLEVO DOS ARTICULOS DE 1 EL INGRESO SERIA DE 62 UNIDADES MONETARIAS
PESO BENEFICIO
ARTICULO 1 4 lb 11
ARTICULO 2 3 lb 7
ARTICULO 3 5 lb 12
La mochila 10 libras
, i = la etapa 1,2,3
Xi = estado de la etapa i quiere decir cuántas unidades voy a colocar de cada articulo
, mi = cantidad del articulo i
, fi = ingreso esperado ri*mi
, mi = Wt / Wi
F3(X3) = Max 12 m3
X3 ,m3 =0 ,m3 =1 , m3 =2 F3(X3) ,m3
0 0 - - 0 0
1 0 - - 0 0
2 0 - - 0 0
3 0 - - 0 0
4 0 - - 0 0
5 0 12 - 12 1
6 0 12 - 12 1
7 0 12 - 12 1
8 0 12 - 12 1
9 0 12 - 12 1
10 0 12 24 24 2
, m2 = 3
F2(X2) = MAX( 7m2+ F3( X2- 3m2))
Xn /mi ,m2=0 ,m2=1 ,m2=2 ,m2=3 F2(X2) ,m2
0 0 - - - 0 0
1 0 - - - 0 0
2 0 - - - 0 0
3 0 7 - - 7 1
4 0 7 - - 7 1
5 12 7 - - 12 0
6 12 7 14 - 14 2
7 12 7 14 - 14 2
8 12 19 14 - 19 1
9 12 19 14 21 21 3
10 24 19 14 21 24 0
, m1 = 10/ 4 = 2,5 = 2 articulos de 1
Xn /mi ,m1=0 ,m1=1 ,m1=2 F1(X1) ,m1
0 0 - - 0 0
1 0 - - 0 0
2 0 - - 0 0
3 7 - - 7 0
4 7 11 11 1
5 12 11 - 12 2
6 14 11 - 14 0
7 14 18 - 14 1
8 19 18 22 19 2
9 21 23 22 23 1
10 24 25 22 25 1
F1(X1) = MAX( 11m1+ F2( X1- 4m1)) =22+ F2(10-2*2) =22+F2(6)
38 m1= 1 ,m2 =2 m3 =0
