Programação Dinâmica para Otimização

Prévia do material em texto

Fernando Nogueira Programação Dinâmica 1
Programação 
Dinâmica
Fernando Nogueira Programação Dinâmica 2
A Programação Dinâmica procura resolver o problema de otimização através da análise 
de uma seqüência de problemas mais simples do que o problema original.
A resolução do problema original de N variáveis é caracterizado pela determinação de 
uma variável e pela resolução de um problema que possua uma variável a menos (N-1). 
Este por sua vez é resolvido pela determinação de uma variável e pela resolução de um 
problema de N-2 variáveis e assim por diante. O problema a ser resolvido é do tipo:
-existem N atividades ou estágios numerados de 1 a N.
-Xi é a quantidade de recursos colocados nas atividades ou estágios i
-gi(Xi) é a função que representa o ganho ou o retorno devido a colocação de Xi
recursos na atividade i, Q = x1 + x2 + ... + xN é a quantidade total de recursos 
disponíveis.
-O objetivo é determinar a distribuição de recursos Xi que maximiza o ganho total.
R(X1, X2,...,XN) = g1(X1) + g2(X2) + ...gN(XN).
considerando que as atividades são independentes e os ganhos gi sejam aditivos.
( )0Xi ≥
Fernando Nogueira Programação Dinâmica 3
Formulação
Maximizar R depende de Q e N. Esta dependência é explicada da seguinte maneira:
fN(Q) representa o ganho máximo devido à distribuição de Q quantidades de recursos 
nas N atividades.
Condição Inicial
a)gi(0) = 0 ⇒ para cada atividade i (ganho nulo para zeros recursos distribuídos).
b)fN(0) = 0 ⇒ para N = 1,2,... (se o total Q de recursos é nulo, o ganho máximo também 
é nulo).
c)f1(Q) = g1(Q) ⇒ se existir N = 1 atividade, então R(X1) = g1(X1).
Relação de Recorrência entre fN(Q) e fN-1(Q)
Ao atribuir a quantidade de recursos à atividade N, restarão Q-XN
recursos a serem distribuídos nas N-1 atividades restantes e o ganho máximo 
proveniente dessas N-1 atividades pode ser expresso por fN-1(Q-XN). Sendo assim, o 
ganho total das N atividades pode ser expresso por:
( ) ( ){ }N21
i
N X,...,X,XRX
Max
Qf =
( )QX0X NN ≤≤
( ) ( )N1NNN XQfXg −+ −
Fernando Nogueira Programação Dinâmica 4
e se escolhermos XN, que maximize esse ganho, teremos o valor fN(Q) do ganho 
máximo devido à aplicação de Q recursos em N atividades. Temos então a relação 
fundamental da Programação Dinâmica, dada por:
Exemplo : Problema de Investimento de Capital
Q = $6,00 unidades de capital disponível
N = 3 atividades diferentes para investimento e as funções de ganho gi(Xi) dadas pelo 
quadro abaixo:
Qual a distribuição ótima do recurso Q = $6,00 nas 3 atividades ?
( ) ( ) ( ){ }
( ) ( )QgQf1Npara
,...3,2NparaXQfXgQ
X
Max
0Qf
11
N1NNN
N
N
=⇒=
=−+≤≤= −
Fernando Nogueira Programação Dinâmica 5
Obtenção da função f1(Q) da atividade 1
Condição inicial
Obtenção da função f2(Q) da atividade 2
fN(Q) para N=2
Para Q = 0, f2(0) = 0 pela condição inicial (b)
e como os valores possíveis de X2 são 0 e 1, temos: 
escolhemos, como solução ótima X2 = 0 (poderia ter sido X2 = 1).
( ) ( )
( ) ( )
( ) ( )
( ) ( )
( ) ( )
( ) ( )
( ) ( ) 1006g6f
955g5f
904g4f
803g3f
402g2f
151g1f
00g0f
11
11
11
11
11
11
11
==
==
==
==
==
==
==
( ) ( ) ( ){ }2122
2
2 X1fXg1X
Max
01f,1QPara −+≤≤==
( ) ( ) ( )( ) ( ) 1Xou0Xpara15150150f1g
151501f0g
Max1f 22
12
12
2 ===⎭⎬
⎫
⎩⎨
⎧
=+=+
=+=+=
( ) ( ) ( ){ }2122
2
2 X2fXg2X
Max
02f,2QPara −+≤≤==
Fernando Nogueira Programação Dinâmica 6
( )
( ) ( )
( ) ( )
( ) ( )
2Xou0Xpara40
400400f2g
3015151f1g
404002f0g
Max2f 22
12
12
12
2 ===⎪⎭
⎪⎬
⎫
⎪⎩
⎪⎨
⎧
=+=+
=+=+
=+=+
=
e como os valores possíveis de X2 são 0, 1 e 2 temos:
escolhemos, como solução ótima X2 = 0 (poderia ter sido X2 = 2).
e como os valores possíveis de X2 são 0, 1, 2 e 3 temos:
Prosseguindo, pode-se encontrar:
Para Q = 4, f2(4) = 95, para X2 = 1
Para Q = 5, f2(5) = 120, para X2 = 2
Para Q = 6, f2(6) = 140, para X2 = 3
( ) ( ) ( ){ }2122
2
2 X3fXg3X
Max
03f,3QPara −+≤≤==
( )
( ) ( )
( ) ( )
( ) ( )
( ) ( )
0Xpara80
600600f3g
5515401f2g
5540152f1g
808003f0g
Max3f 2
12
12
12
12
2 ==
⎪⎪⎭
⎪⎪⎬
⎫
⎪⎪⎩
⎪⎪⎨
⎧
=+=+
=+=+
=+=+
=+=+
=
Fernando Nogueira Programação Dinâmica 7
Obtenção da função f3(Q) da atividade 3
De maneira análoga, obtemos f3(Q):
Quadro dos Valores de fN(Q)
( ) ( ) ( ){ }3233
3
3 X2fXg2X
Max
02f,2QPara −+≤≤==
( )
( ) ( )
( ) ( )
( ) ( )
1Xpara41
400400f2g
4115261f1g
404002f0g
Max2f 3
23
23
23
3 ==⎪⎭
⎪⎬
⎫
⎪⎩
⎪⎨
⎧
=+=+
=+=+
=+=+
=
Fernando Nogueira Programação Dinâmica 8
Ganho Máximo do Investimento
Na coluna f3(Q) obtém-se como ganho máximo correspondente ao investimento nas 3 
atividades, o valor $146,00, para Q = 6.
A distribuição é:
a) para a atividade 3: X3 = $1,00 ⇒ f3(Q) = 146 e subtraindo o ganho g3(1) = 26 (do 
quadro de ganhos) restam ainda 146-26 = 120 unidades que correspondem ao 
ganho da aplicação de Q = 5 unidades nas outras 2 atividades.
b) para a atividade 2, o ganho de 120 unidades corresponde a aplicação de X2 = 2 
unidades na atividade e 
c) para a atividade 1, restam, portanto, Q-X3-X2 = 3 unidades a serem aplicadas. 
Portanto, X1 = 3.
Solução Ótima
X1 = 3 com g1(3) = 80, X2 = 2 com g2(2) = 40, X3 = 1 com g3(1) = 26 e 
R = g1 + g2 + g3 = $146,00
Fernando Nogueira Programação Dinâmica 9
Problema da Mochila (Knapsack problem) 
Objetivo: maximizar a somatória dos valores dos itens que serão colocados na mochila, 
respeitando a sua capacidade.
Existem n itens. Cada item i possui um valor ci e um peso wi associado. A capacidade 
da mochila é L. As variáveis de controle são xi tal que:
{ }⎪⎩
⎪⎨
⎧
∈
≤∑
∑
=
=
1,0x
Lxw
xcMax
i
n
1i
ii
n
1i
ii
Código MPL para o exemplo da figura
MAX 4X1 + 2X2 + 10X3 + 1X4 + 2X5
SUBJECT TO
12X1 + 1X2 + 4X3 + 1X4 + 2X5 <= 15;
BINARY X1 X2 X3 X4 X5
Fernando Nogueira Programação Dinâmica 10
Outra “versão” deste problema é quando as variáveis de controle não são binárias, mas 
sim inteiras (neste caso a solução irá determinar quantas unidades de cada produto serão 
colocados na mochila):
⎪⎩
⎪⎨
⎧
≤≤
≤∑
∑
=
=
ii
n
1i
ii
n
1i
ii
bx0
Lxw
xcMax
Outra “versão” deste problema é quando as variáveis de controle são reais, limitadas 
por valores máximos bi (neste caso a solução irá determinar a quantidade (grandeza 
contínua) de cada produto que será colocado na mochila):
⎪⎩
⎪⎨
⎧
Ζ∈≥
≤∑
∑
=
=
e0x
Lxw
xcMax
i
n
1i
ii
n
1i
ii
Fernando Nogueira Programação Dinâmica 11
Exemplo
Um navio pode carregar 4 toneladas. Existem 3 itens. A seguinte tabela fornece o peso 
unitário wi em toneladas e o retorno unitário ci em $ para cada item i. Como o navio 
deve ser carregado para maximizar o retorno total?
1413
4732
3121
ciwiItem i
Uma vez que os pesos wi e o peso máximo que o navio pode carregar W são inteiros, as 
variáveis xi devem ser somente inteiras também.
Fernando Nogueira Programação Dinâmica 12
Porque w3 = 1, o número máximo de itens 3 que o navio pode carregar é 4/1 = 4, que 
significa que os valores de m3 são 0,1,2,3,4. Uma alternativa m3 é viável somente se 
4565642281404
342---42281403
228------281402
114---------1401
00------------00
m3f3(x3)m3=4m3=3m3=2m3=1m3=0x3
Solução ótima14m3
( ) { } { } 4
1
4mmax,m14maxxf 33m33 3
=⎥⎦
⎤⎢⎣
⎡==
333 xmw ≤
Fernando Nogueira Programação Dinâmica 13
( ) ( ){ } { } 1
3
4mmax,m3xfm47maxxf 22232m22 2
=⎥⎦
⎤⎢⎣
⎡=−+=
16147+14=610+56=564
14747+0=470+42=423
028---0+28=282
014---0+14=141
00---0+0=00
m2f2(x2)m2=1m2=0x2
Solução ótima47m2+f3(x2-3m2)Fernando Nogueira Programação Dinâmica 14
( ) ( ){ } { } 2
2
4mmax,m2xfm31maxxf 11121m11 1
=⎥⎦
⎤⎢⎣
⎡=−+=
26262+0=6231+28=590+61=614
047---31+14=450+47=473
131---31+0=310+28=282
014------0+14=141
00------0+0=00
m1f1(x1)m1=2m1=1m1=0x1
Solução ótima31m1+f2(x1-2m1)
Fernando Nogueira Programação Dinâmica 15
Solução ótima
m1 = 2
x2 = x1 - 2m1
x2 = 4 – 2 x 2 = 0 => m2 = 0
x3 = x2 – 3m2
x3 = 0 – 3 x 0 = 0 => m3 = 0
m1 = 2, m2 = 0, m3 = 0
Z = $62,00