Programacao Dinamica

CAMILLA CANTUARIA BRAGA
RAPHAEL CANTUARIA BRAGA
PROGRAMAO DINMICA
MACAP
2010
CAMILLA CANTUARIA BRAGA

RAPHAEL CANTUARIA BRAGA
PROGRAMAO DINMICA
Trabalho apresentado disciplina Pesquisa

Operacional II do curso de Engenharia de Produo
da Universidade do Estado do Amap, sob orientao
do Professor Valdemar Vilena.
MACAP
2010
INTRODUO
A tomada de decises dentro do processo produtivo das empresas, nos mais

variados ramos de atividade, tem chamado cada vez mais a ateno dos
responsveis. No basta apenas achar para que atitudes sejam tomadas, as
decises tm que ser embasadas em nmeros que indiquem sua viabilidade e
qualidade.
Dentro deste contexto, a Pesquisa Operacional apresenta ferramentas
quantitativas para o auxlio destas decises.
O presente material de apoio tem como objetivo apresentar uma destas
ferramentas, a Programao Dinmica.
A Programao Dinmica, como uma tcnica matemtica utilizada na
resoluo de problemas que envolvem uma seqncia de decises interrelacionadas, busca a combinao de timas decises.
Esperamos que com o acesso a este material incentivemos as pessoas a
procurar conhecer melhor a Programao Dinmica e, principalmente, comear a
utiliz-la no processo decisrio das empresas.
1. PROGRAMAO DINMICA PD
Programao dinmica uma tcnica matemtica muito til para tomar uma
seqncia de decises inter-relacionadas.
Em contraste com a Programao Linear, no existe uma formulao

matemtica para o problema de Programao Dinmica PD. Ao contrrio, a PD
uma abordagem genrica para resoluo de problemas e as equaes utilizadas
devem ser desenvolvidas de acordo com cada situao particular.
Portanto, importante conhecer os elementos bsicos que caracterizam

problemas de PD.
2.
PRINCIPAIS
ELEMENTOS
DOS
PROBLEMAS
DE
PROGRAMAO
DINMICA
O objetivo da otimizao determinar a poltica tima que otimize a funo

objetivo global do sistema nas suas n etapas.
Em cada Estgio de Deciso possvel definir o Estado da soluo. O

Estado o ponto de situao em que se pode estar como consequncia da deciso
tomada no estgio anterior.
Em cada Estgio decide-se, para cada Estado, qual o Estado do Estgio
seguinte que oferece melhor retorno para a soluo do problema.
Para um dado estado do sistema, a poltica tima
para os restantes estados independente da poltica
de deciso adotada em estados anteriores.
(BELLMAN, Richard. Princpio da Otimidade, 1959)
3. CLASSIFICAO DOS PROBLEMAS DE PD:
Determinsticos: o estado do estgio seguinte est completamente

determinado pelos estados e decises do estgio atual.
Discreto
Contnuo
Probabilsticos: existe uma distribuio de probabilidade para determinar

qual ser o estado no prximo estgio.
Discreto
Contnuo
3.1 Metodologia
Estruturar a soluo tima para o ltimo estgio;
Procurar uma soluo descendente (recursiva), para calcular o valor timo

do resultado;
Calcular o valor timo de maneira ascendente;
Construir a soluo.
4. PROBLEMA DE PD DETERMINSTICO E DISCRETO
Quando o Estado do prximo estgio univocamente determinado (uma s

forma de expresso) pela deciso poltica sobre o estado atual est-se tratando de
um problema de Programao Dinmica Determinstica.
A estrutura bsica da PD Determinstica pode ser representada da seguinte

forma:
Sn: estado na etapa n

Xn: deciso poltica na etapa n
fn(s, xn): valor da funo no estado s etapa n relativo a deciso poltica xn
f*n (xn): valor mnimo ou mximo da funo na etapa n correspondente a uma
determinada deciso Xn.
Csxn: custo ou ganho para passar da etapa n estado no estado s para a etapa
n+1.
Problemas: Maximizao ou Minimizao

Valores: Discretos ou contnuos associados varivel de estado
O estado na etapa seguinte completamente determinado pelo estado de

deciso poltica na etapa atual.
Para melhor compreender o conceito e desenvolvimento deste problema,

usaremos o exemplo a seguir.
Suponhamos que um acadmico pretende minimizar o custo do transporte

entre a sua residncia e a faculdade utilizando vrios meios de transporte
disponveis na rede seguinte:
O custo associado s relaes existentes traduz-se nas seguintes matrizes de

transio:
Sendo a casa do acadmico o ponto inicial do percurso e a faculdade o ponto

final temos quatro estgios (n = 4) como mostra a figura a seguir:
A soluo ser da forma: A X1 X2 X3 X4 = J

Sendo o custo de transporte associado deciso, quando o acadmico se
encontra no Estado esta relao recursiva da forma:
f*n(s) = min {CSXn + f*n+1 (xn}

xn
f*n(4), f*n(3), f*n(2), f*n(1)
O quadro seguinte ilustra as decises associadas ao Estgio 4:
Podemos ento concluir que a poltica tima tem um custo total mnimo de = 8
u.m.
Problema com mltiplas solues. Existem trs caminhos distintos com o

mesmo valor timo (com custo = 8 $.)
5. O PROBLEMA DA DILIGNCIA
Esse problema foi especialmente elaborado (Prof. Harvey M. Vagner) para

introduzir os conceitos e ilustrar os elementos da PD.
Um caador de tesouros do Missouri (regio central dos EUA) decidiu

participar da corrida do ouro na Califrnia (na metade do sculo 19). A viagem at a
Califrnia seria realizada por diligncia atravs de territrio inseguro, correndo-se
riscos de ataque de assaltantes. Apesar de seu ponto de sada e destino serem
fixos, o caador de tesouros tinha uma liberdade considervel para escolher por
quais estados ele deveria passar at chegar ao seu destino. O caador era um
homem prudente e estava preocupado com sua segurana ao longo da viagem.
Depois de pensar um pouco, ele teve uma brilhante idia para determinar a rota
mais segura. Empresas de seguros ofereciam aplices de seguro de vida para
passageiros de diligncias. O custo das aplices para cada trecho percorrido era
calculado de acordo com as condies de segurana daquele trecho. Quanto mais
arriscada uma rota, mais caro o seguro. Assim, a rota mais segura deveria ser
aquela que tivesse a mais barata aplice de segura de vida associada.
Os custos das aplices de seguros associados a cada possvel trecho da

viagem (do estado i para o estado j), denotados por cij so:
O ponto de partida e o ponto de chegada so fixos, mas o viajante tem a

liberdade de escolher os estados que quer passar. preciso passar por 4 etapas
para concluir a viagem.
As rotas possveis so mostradas na Figura abaixo.
O objetivo decidir qual a rota que minimiza o custo total.
Inicia-se a soluo a partir do problema menor onde o caador quase

completou uma viagem e tem apenas mais um estgio a percorrer (n=4). A soluo
bvia para este problema ir do seu estado atual (seja qual for H ou I) para seu
destino final (estado J). A cada iterao subseqente, o problema ampliado
aumentando-se em 1 o nmero de estgios restantes para completar a viagem. Para
esse ltimo problema ampliado, a soluo tima para onde se deve ir em seguida a
partir de cada estado possvel pode ser encontrado relativamente fcil a partir dos
resultado obtidos na iterao anterior.
Seja fn(s,xn) o custo total da melhor poltica a ser adotada para o restante dos
estgios, dado que o caador de tesouros est no estado s, pronto para seguir para
o estgio n e seleciona xn como seu destino imediato.
Dados s e n, seja xn qualquer valor de xn que minimiza fn(s,xn) e seja fn*(s) o
valor mnimo correspondente de fn(s,xn). Logo,
fn*(s) = min fn(s,xn) = fn(s,xn*)
onde:
fn(s,xn) = custo imediato (estgio n) + mnimo custo futuro (estgios n+1 em

diante)
De outra forma:
fn(s,xn) = cSXn + f*n+1(xn)

CSXn dado nas tabelas para cij, com i = s (estado atual) e j = xn (o destino
imediato)
Como ltimo destino (estado J) alcanado ao final do estgio 4, fS*(J) = 0

O objetivo encontrar f1*(A) e a rota correspondente. A PD faz isso
encontrando sucessivamente f4*(s), f3*(s), f2*(s), para cada um dos possveis estados
s e utilizando f2*(s) para encontrar f1*(A).
Quando o caador tem apenas mais um estgio para percorrer (n=4), sua rota
determinada inteiramente por seu estado atual s (H ou I) e seu destino final x4 = J.
Assim, a rota final da diligncia s J. Tem-se que:
f4*(s) = f4(s,x4*) = f4 (s,J) = cs,J + f4+1*(J) = cs,J

Logo, a soluo imediata para n=4 :
Para n=3 tem-se:
Para n=2 tem-se:
Para n=1 tem-se:
Assim, existem 3 possveis rotas que apresentam a mesma segurana

(menores custos de seguro):
ACEHJ
ADEHJ
ADFIJ
Todas as rotas apresentam o mesmo custo total de f1*(A)=11.
6. PROGRAMAO DINMICA PROBABILSTICA
A programao dinmica probabilstica diferencia-se da determinstica no

sentido que o estado no prximo estgio no completamente determinado pelo
estado e pela deciso poltica no estgio atual.
Existe uma distribuio de probabilidade que determinar qual ser o prximo

estado.
Contudo, essa distribuio de probabilidade completamente determinada

pelo estado e pela deciso poltica no estgio atual.
Estgio n
Estgio n+1
Contribuio
do estgio n
Probabilidade
1
f*n+1(1)
Deciso
Estado:
sn
fn(sn,xn)
xn
2
f*n+1(2)
S
f*n+1(s)
CONCLUSO
A Programao Dinmica uma tcnica bastante til para tomar decises

seqencialmente inter-relacionadas.
Para tanto, faz-se necessrio formular relaes recorrentes apropriadas para

cada problema individual.
Em suma, uma ferramenta de Pesquisa Operacional de extrema

importncia quando se refere a tomada de decises dentro de uma empresa e pode
ser aplicada de diversas formas, abrangendo os mais diversos tipos de situaes.

Programacao Dinamica

Enviado por

Direitos autorais:

Formatos disponíveis

Programacao Dinamica

Enviado por

Dados do documento

Descrição original:

Direitos autorais

Formatos disponíveis

Compartilhar este documento

Compartilhar ou incorporar documento

Opções de compartilhamento

Você considera este documento útil?

Este conteúdo é inapropriado?

Direitos autorais:

Formatos disponíveis

Programacao Dinamica

Enviado por

Direitos autorais:

Formatos disponíveis

CAMILLA CANTUARIA BRAGA

RAPHAEL CANTUARIA BRAGA

CAMILLA CANTUARIA BRAGA

Trabalho apresentado disciplina Pesquisa

A tomada de decises dentro do processo produtivo das empresas, nos mais

Em contraste com a Programao Linear, no existe uma formulao

Portanto, importante conhecer os elementos bsicos que caracterizam

O objetivo da otimizao determinar a poltica tima que otimize a funo

Em cada Estgio de Deciso possvel definir o Estado da soluo. O

3. CLASSIFICAO DOS PROBLEMAS DE PD:

Determinsticos: o estado do estgio seguinte est completamente

Probabilsticos: existe uma distribuio de probabilidade para determinar

Estruturar a soluo tima para o ltimo estgio;

Procurar uma soluo descendente (recursiva), para calcular o valor timo

Calcular o valor timo de maneira ascendente;

4. PROBLEMA DE PD DETERMINSTICO E DISCRETO

Quando o Estado do prximo estgio univocamente determinado (uma s

A estrutura bsica da PD Determinstica pode ser representada da seguinte

Sn: estado na etapa n

Problemas: Maximizao ou Minimizao

O estado na etapa seguinte completamente determinado pelo estado de

Para melhor compreender o conceito e desenvolvimento deste problema,

Suponhamos que um acadmico pretende minimizar o custo do transporte

O custo associado s relaes existentes traduz-se nas seguintes matrizes de

Sendo a casa do acadmico o ponto inicial do percurso e a faculdade o ponto

A soluo ser da forma: A X1 X2 X3 X4 = J

f*n(s) = min {CSXn + f*n+1 (xn}

O quadro seguinte ilustra as decises associadas ao Estgio 3:

O quadro seguinte ilustra as decises associadas ao Estgio 2:

O quadro seguinte ilustra as decises associadas ao Estgio 1:

Problema com mltiplas solues. Existem trs caminhos distintos com o

Esse problema foi especialmente elaborado (Prof. Harvey M. Vagner) para

Um caador de tesouros do Missouri (regio central dos EUA) decidiu

Os custos das aplices de seguros associados a cada possvel trecho da

O ponto de partida e o ponto de chegada so fixos, mas o viajante tem a

As rotas possveis so mostradas na Figura abaixo.

O objetivo decidir qual a rota que minimiza o custo total.

Inicia-se a soluo a partir do problema menor onde o caador quase

fn(s,xn) = custo imediato (estgio n) + mnimo custo futuro (estgios n+1 em

fn(s,xn) = cSXn + f*n+1(xn)

Como ltimo destino (estado J) alcanado ao final do estgio 4, fS*(J) = 0

Assim, a rota final da diligncia s J. Tem-se que:

f4*(s) = f4(s,x4*) = f4 (s,J) = cs,J + f4+1*(J) = cs,J

Para n=3 tem-se:

Para n=2 tem-se:

Para n=1 tem-se:

Assim, existem 3 possveis rotas que apresentam a mesma segurana

Todas as rotas apresentam o mesmo custo total de f1*(A)=11.

6. PROGRAMAO DINMICA PROBABILSTICA

A programao dinmica probabilstica diferencia-se da determinstica no

Existe uma distribuio de probabilidade que determinar qual ser o prximo

Contudo, essa distribuio de probabilidade completamente determinada

A Programao Dinmica uma tcnica bastante til para tomar decises

Para tanto, faz-se necessrio formular relaes recorrentes apropriadas para

Em suma, uma ferramenta de Pesquisa Operacional de extrema

Você também pode gostar

fn(s) = min {CSXn + fn+1 (xn}

f4(s) = f4(s,x4) = f4 (s,J) = cs,J + f4+1*(J) = cs,J