PO-II-15-Programacao-Dinamica-INCOMPLETO

Prévia do material em texto

Departamento de Engenharia de Produção – UFPR 108 
Professor Volmir Eugênio Wilhelm – Professora Mariana Kleina 
Programação Dinâmica (incompleto!!!!!) 
A programação dinâmica-PD (incluindo o nome) foi introduzida por Richard Bellman 
na década de 1950. A PD é uma abordagem de otimização que transforma um 
problema complexo em uma sequência de problemas mais simples; sua principal 
característica é a natureza multiestágio do procedimento de otimização. Mais do que 
as técnicas de otimização vistas em aulas anteriores (em TP052, TP065 e TP066), a 
programação dinâmica fornece uma estrutura geral para analisar muitos tipos de 
problemas. Dentro deste quadro, uma variedade de técnicas de otimização pode ser 
empregada para resolver aspectos particulares de uma formulação mais geral. 
Geralmente, a criatividade é necessária antes que possamos reconhecer que um 
problema em particular pode ser efetivamente definido como um programa 
dinâmico; e, muitas vezes, insights sutis são necessários para reestruturar a 
formulação para que ela possa ser resolvida de maneira eficaz. 
(web.mit.edu/15.053/www/AMP-Chapter-11.pdf) 
Portanto, a programação dinâmica pode ser vista como uma técnica para determinar 
uma sequência de decisões inter-relacionadas. Busca particionar o problema 
principal em subproblemas utilizando uma equação recursiva. Ou seja, este 
particionamento é feita iterativamente. Os subproblemas são resolvidos uma única 
vez e seus resultados são armazenados, consultando-o cada vez que o subproblema 
for requerido. Em cada subproblema (estágio), consideram-se somente as soluções 
ótimas. 
A ideia básica da programação dinâmica é construir por etapas uma resposta ótima 
combinando respostas já obtidas para partes menores. Inicialmente, a entrada é 
decomposta em partes mínimas, para as quais são obtidas respostas. Em cada passo, 
sub-resultados são combinados obtendo-se respostas para partes maiores, até que se 
obtenha uma resposta para o problema original. A decomposição é feita uma única 
vez e os casos menores são tratados antes dos maiores. Suas soluções são 
armazenadas para serem usadas quantas vezes for necessário. 
A PD é baseada no princípio da otimalidade de Bellman: em uma sequência ótima de 
escolhas ou de decisões, cada subsequência também deve ser ótima. Ela reduz 
drasticamente o número total de verificações, pois evita aquelas que sabidamente 
não podem ser ótimas: a cada passo são eliminadas subsoluções que certamente não 
farão parte da solução ótima do problema. 
Princípio de Otimalidade de Bellman 
 “Uma trajetória ótima tem a seguinte propriedade: quaisquer que tenham sido 
os passos anteriores, a trajetória remanescente deverá ser uma trajetória 
ótima com respeito ao estado resultante dos passos anteriores, ou seja, uma 
política ótima é formada de subpolíticas ótimas.” 
web.mit.edu/15.053/www/AMP-Chapter-11.pdf
Departamento de Engenharia de Produção – UFPR 109 
Professor Volmir Eugênio Wilhelm – Professora Mariana Kleina 
 Dado um estado atual, a decisão ótima para cada estágio seguinte depende 
somente do estado atual, não importando o que aconteceu anteriormente. 
 Exemplo: suponha que o caminho mais curto entre Curitiba e Ponta Grossa 
seja conhecido e esse caminho passa necessariamente por Campo Largo. 
Consequentemente, o caminho mais curto entre Curitiba e Ponta Grossa deve 
incluir o caminho mais curto entre Campo Largo e Ponta Grossa. 
 Uma política ótima tem a propriedade de que, qualquer que seja o estado 
inicial e a decisão inicial, a decisão restante deve constituir uma política ótima 
em relação ao estado resultante da primeira decisão. 
É necessário trabalhar com muitos exemplos para entender PD! 
Não existe uma formulação matemática padrão do problema. Em vez disso, a 
programação dinâmica é um tipo geral de abordagem para a resolução de problemas, 
e suas equações podem ser adotadas para atender a muitos problemas. 
Ao contrário da programação linear, não existe um padrão matemático para 
formulação do "problema de programação dinâmica". Em vez disso, a programação 
dinâmica é um tipo geral de abordagem à solução de problemas, e as equações 
específicas usadas devem ser desenvolvidas para se adequarem a cada situação. 
Principais conceitos em Programação Dinâmica (web.mit.edu/15.053/www/AMP-Chapter-11.pdf) 
As três características mais importantes dos problemas de programação dinâmica 
são: 
a) estágios; 
b) estados; e 
c) fórmula recursiva. 
Cada uma destas 3 características será exemplificada. 
Exemplo http://mat.gsia.cmu.edu/classes/dynamic/node2.html 
Uma corporação tem US $ 5 milhões para alocar em suas três fábricas para possível 
expansão. Cada fábrica apresentou uma série de propostas sobre como pretende 
gastar o dinheiro. Cada proposta fornece o custo da expansão (C) e a receita total 
esperada (R). A tabela a seguir (Tabela 1) fornece as propostas geradas: 
 Planta 1 Planta 2 Planta 3 
Proposta C1 R1 C2 R2 C3 R3 
1 0 0 0 0 0 0 
2 1 5 2 8 1 4 
3 2 6 3 9 --- --- 
4 --- --- 4 12 --- --- 
web.mit.edu/15.053/www/AMP-Chapter-11.pdf
http://mat.gsia.cmu.edu/classes/dynamic/node2.html
Departamento de Engenharia de Produção – UFPR 110 
Professor Volmir Eugênio Wilhelm – Professora Mariana Kleina 
Cada planta só terá permissão para aprovar uma de suas propostas. O objetivo é 
maximizar as receitas da empresa resultantes da alocação dos US $ 5 milhões. Vamos 
supor que qualquer parte dos US $ 5 milhões não gastos está perdido. 
Uma maneira simples de resolver isso é elencar todas as possibilidades e escolher a 
melhor. Neste caso, existem apenas maneiras de alocar o dinheiro. 
Muitas delas são inviáveis (por exemplo, as propostas 3, 4 e 1 para as três fábricas 
custam US $ 6 milhões). Outras propostas são viáveis, mas muito inferiores/fracas 
(como as propostas 1, 1 e 2, que são viáveis, mas retornam apenas US $ 4 milhões). 
Algumas desvantagens da enumeração total são: 
1. Para problemas maiores, a enumeração de todas as soluções possíveis pode 
não ser computacionalmente viável. 
2. Combinações inviáveis não podem ser detectadas a priori, levando à 
ineficiência. 
3. Informações sobre combinações investigadas anteriormente não são usadas 
para eliminar combinações “inferiores/fracas” ou inviáveis. 
Note também que este problema não pode ser formulado como um programa linear, 
pois as receitas retornadas não são funções lineares. 
Vamos tentar descobrir as receitas associadas a cada estado. A única possibilidade 
fácil é no estágio 1, os estados x1. A tabela 2 fornece a receita associada a x1. 
Se o capital Então a proposta E a receita para 
disponível x1 é ótima é o estágio 1 é 
0 1 0 
1 2 5 
2 3 6 
3 3 6 
4 3 6 
5 3 6 
a) Estágios 
A característica essencial da abordagem de programação dinâmica é a estruturação 
de problemas de otimização em múltiplos estágios, os quais são resolvidos 
sequencialmente um estágio por vez. Embora cada problema de um estágio seja 
resolvido como um problema comum de otimização, sua solução ajuda a definir as 
características do próximo problema de um estágio na sequência. 
No problema do caminho mais curto, cada estágio constitui um novo problema a ser 
resolvido para encontrar o próximo nó mais próximo da origem. Em algumas 
aplicações de programação dinâmica, os estágios estão relacionados ao tempo, daí o 
nome programação dinâmica. Estes são frequentemente problemas de controle 
dinâmico e, por razões de eficiência, os estágios são frequentemente resolvidos no 
Departamento de Engenharia de Produção – UFPR 111 
Professor Volmir Eugênio Wilhelm – Professora Mariana Kleina 
sentido inverso do tempo, isto é, de um ponto no futuro em relação ao presente. Isso 
ocorre porque os caminhos que levam do estado presente para o estado do objetivo 
futuro são sempre apenas um subconjunto de todos os caminhos que levam adiante 
do estado atual. Por isso, é mais eficiente trabalhar para trás ao longo deste 
subconjunto de caminhos. Nós estaremos lidando com exemplos estáticosem que a 
direção é irrelevante, mas também trabalharemos de trás para frente para que não 
seja uma surpresa quando você precisar fazer isso para um problema de controle 
dinâmico relacionado ao tempo. Isso é conhecido como recursão reversa-backward. 
Exemplo (acima) 
No exemlo acima, vamos particionar/dividir o problema em três estágios: cada 
estágio representa o dinheiro alocado a uma única fábrica. Assim, o estágio 1 
representa o dinheiro alocado para a Planta 1, o estágio 2 o dinheiro para a Planta 2 e 
o estágio 3 para a Planta 3. Vamos fazer um ordenamento artificial nos estágios, 
dizendo que primeiro vamos alocar para a Planta 1, depois para a Planta 2 e depois 
Planta 3. 
b) Estados 
Associados a cada estágio do problema de otimização estão os estados do processo. 
Os estados refletem as informações necessárias para avaliar plenamente as 
consequências que a decisão atual tem sobre as ações futuras. Num problema de 
inventário, cada estágio tem apenas uma variável descrevendo o estado: o nível de 
estoque disponível da mercadoria, p.ex. 
A especificação dos estados do sistema é talvez o parâmetro mais crítico do modelo 
de programação dinâmica. Não há regras definidas para isso. Na verdade, na maior 
parte do tempo, essa é uma arte que muitas vezes requer criatividade e percepção 
sutil sobre o problema que está sendo estudado. As propriedades essenciais que 
devem motivar a seleção de estados são: 
i) Os estados devem transmitir informações suficientes para tomar decisões 
futuras sem considerar como o processo atingiu o estado atual; e 
ii) O número de variáveis de estado deve ser pequeno, uma vez que o esforço 
computacional associado à abordagem de programação dinâmica é 
proibitivamente caro quando há mais de duas ou possivelmente três variáveis 
de estado envolvidas na formulação do modelo. 
Esta última característica limita consideravelmente a aplicabilidade da programação 
dinâmica na prática. 
Então, cada estágio tem vários estados. Geralmente, esta é a informação que você 
precisará para resolver um problema menor em um estágio. Para o problema do 
caminho mínimo, o estado é: i) o conjunto de nós já incluídos no caminho; ii) os arcos 
no conjunto de arcos; e iii) os nós não analisados e arcos conectados diretamente aos 
nós resolvidos. 
Departamento de Engenharia de Produção – UFPR 112 
Professor Volmir Eugênio Wilhelm – Professora Mariana Kleina 
Exemplo (acima) 
No exemplo acima, vamos dividido/particionar cada estágio em estados. Um estado 
abrange as informações necessárias para ir de um estágio para o próximo. Neste caso, 
os estados para os estágios 1, 2 e 3 são: 
 {0,1,2,3,4,5}: a quantidade de dinheiro gasto na planta 1, representada por x1; 
 {0,1,2,3,4,5}: a quantidade de dinheiro gasto nas plantas 1 e 2 (x2); e 
 {5}: a quantidade de dinheiro gasto nas plantas 1, 2 e 3 (x3). 
Ao contrário da programação linear, os xi não representam variáveis de decisão: são 
simplesmente representações de um estado genérico no estágio. 
Associado a cada estado temos uma receita. Note que para tomar uma decisão no 
estágio 3, é necessário apenas saber quanto foi gasto nas plantas 1 e 2, e não como foi 
gasto. Note também que queremos que x3 seja 5. 
Função Recursiva 
Existe uma relação recursiva entre o valor da decisão em um estágio e o valor das 
decisões ótimas nos estágios anteriores. Em outras palavras, a decisão ótima neste 
estágio usa o ótimo encontrado anteriormente. Em um relacionamento recursivo, 
uma função aparece em ambos os lados da equação. Em palavras, o relacionamento 
recursivo do camininho mínimo se parece com isto: 
 
https://www.sce.carleton.ca/faculty/chinneck/po/Chapter15.pdf 
Observa-se que o “comprimento do caminho mínimo” aparece nos dois lados da 
equação: ela é recursiva. Todas as relações recursivas em programação dinâmica 
mostram a função ótima em ambos os lados da equação: o novo ótimo é sempre 
derivado do ótimo antigo/anterior junto com algum valor local. A relação não precisa 
ser de adição; pode ser qualquer coisa: multiplicação ou algum outro relacionamento 
abstrato. 
Exemplo (acima) 
Considerando o exemplo acima, agora estamos prontos para lidar com os cálculos 
para o estágio 2. Nesse caso, queremos encontrar a melhor solução para ambas as 
Plantas 1 e 2. Se quisermos calcular a melhor receita para um dado x2, simplesmente 
passamos por todas as propostas da Planta 2, alocamos o montante de $ para a Planta 
2 e usamos a tabela acima para ver como a Planta 1 gastará o restante. 
Por exemplo, suponha que queremos determinar a melhor alocação para o estado x2 
= 4. No estágio 2, podemos fazer/propor uma das seguintes propostas: 
https://www.sce.carleton.ca/faculty/chinneck/po/Chapter15.pdf
Departamento de Engenharia de Produção – UFPR 113 
Professor Volmir Eugênio Wilhelm – Professora Mariana Kleina 
- A proposta 1 gera receita 0, sobra 4 para o estágio 1, que retorna 6. Total: 6. 
- A proposta 2 gera receitas 8, sobra 2 para o estágio 1, que retorna 6. Total: 14. 
- A proposta 3 gera receita 9, sobra 1 para o estágio 1, que retorna 5. Total: 14. 
- A proposta 4 gera receita 12, sobra 0 para o estágio 1, que retorna 0. Total: 12. 
A melhor coisa a fazer com quatro unidades (US $ 4) é a proposta 1 para o Planta 2 e 
a proposta 2 para a Planta 1, rendendo 14, ou a proposta 2 para a Planta 2 e a 
proposta 1 para a Planta 1, também rendendo 14. Em ambos os casos, a receita de 
estar em estado x2 = 4 é 14. O resto da tabela 3 pode ser preenchido de forma 
semelhante. 
Se o capital Então a proposta E a receita para 
disponível x2 é ótima é o estágio 1 é 
0 1 0 
1 1 5 
2 2 8 
3 23 13 
4 2 ou 3 14 
5 4 17 
Podemos agora passar para o estágio 3. O único valor em que estamos interessados é 
 . Mais uma vez, passamos por todas as propostas para este estágio, 
determinamos a quantidade de dinheiro restante e usamos a Tabela 3 para decidir o 
valor para os estágios anteriores. Então aqui podemos fazer o seguinte na Planta 3. 
- A proposta 1 gera receita 0, sobra 5. Os estágios anteriores retornam 17. Total: 
17. 
- A proposta 2 gera receita 4, sobra 4. Os estágios anteriores retornam 14. Total: 
18. 
Portanto, a solução ótima é implementar a proposta 2 na Planta 3, a proposta 2 ou 3 
na Planta 2 e a proposta 3 ou 2 (respectivamente) na Planta 1. Isso gera uma receita 
de 18. 
Se você estudar este procedimento, verá que os cálculos são feitos recursivamente. 
Os cálculos do estágio 2 são baseados no estágio 1, no estágio 3 apenas no estágio 2. 
De fato, considerando que você está em um estado, todas as decisões futuras são 
tomadas independentemente de como você chegou ao estado. Este é o princípio da 
otimização e toda a programação dinâmica baseia-se nessa suposição. 
Podemos resumir esses cálculos nas seguintes fórmulas: 
Denotemos por R(kj) a receita da proposta kj no estágio j e por C(kj) o custo 
correspondente. Seja fj(xj) a receita do estado xj no estágio j. Então temos os 
seguintes cálculos 
Departamento de Engenharia de Produção – UFPR 114 
Professor Volmir Eugênio Wilhelm – Professora Mariana Kleina 
f ma 
 : 
 
e 
f ma 
 : 
 f para j . 
Tudo o que estávamos fazendo com os cálculos acima foi determinar essas funções. 
Os cálculos foram realizados em um procedimento forward. Também é possível 
calcular do último estágio até o primeiro estágio. Nós poderíamos definir 
- y1 = quantidade alocada para os estágios 1, 2 e 3, 
- y2 = valor alocado para os estágios 2 e 3, e 
- y3 = valor alocado para o estágio 3. 
Isso define uma recursão backward. Graficamente, isso é ilustrado na Figura 1. 
 
As fórmulas correspondentes são: 
- Seja f3(y3) a receita ótima para o estágio 3, dado y3; 
- f2(y2) ser a receita ótima para os estágios 2 e 3, y3; e 
- f1(y1) é a receita ótima para os estágios 1, 2 e 3, dado y1. 
As fórmulas recursivas são: 
f ma 
 : 
 
e 
f ma 
 : 
 f 
Departamentode Engenharia de Produção – UFPR 115 
Professor Volmir Eugênio Wilhelm – Professora Mariana Kleina 
Se você realizar os cálculos, terá a mesma resposta. 
A recursividade forward parece mais natural. Neste caso particular, a ordenação dos 
estágios não fez diferença. Em outros casos, no entanto, pode haver vantagens 
computacionais de escolher uma sobre a outra. Em geral, a recursão backward é 
considerada mais eficaz na maioria das aplicações.1 
Dado o estado atual, a decisão ótima para as etapas restantes é independente das 
decisões tomadas nos estados anteriores. Este é o princípio fundamental de 
otimalidade em programação dinâmica. Isso significa que não há problema em 
particionar o problema em partes menores e resolvê-las de forma independente. Por 
exemplo, no problema do caminho mínimo, nos preocupamos apenas com a distância 
total da origem até um nó já analisado; não nos importamos com a rota atual da 
origem até o nó resolvido. As decisões tomadas depois usam apenas as informações 
de distância, sem levar em conta a rota real (ou seja, as decisões anteriores). 
A ideia da programação dinâmica - Resumo 
Para formular uma solução via programação dinâmica, você deve responder às 
seguintes perguntas: 
 Quais são os estágios na solução? 
 Como os estados são definidos em um estágio? 
 Que tipo de decisão você deve tomar em um estágio? 
 Como a decisão atualiza o estado para o próximo estágio? 
 Qual é a relação de valor recursivo entre a decisão ótima em um estágio e uma 
decisão ótima anterior? 
Uma relação recursiva que identifica a solução para o estágio n, dada a solução ótima 
para o estágio n + 1, deve estar disponível: 
 min
 
 
 O primeiro termo é o custo atual associado ao estágio atual 
 O segundo termo são os custos associados aos estágios futuros 
Tanto o custo mínimo quanto a política ótima 
 são definidos. 
 O procedimento de solução é projetado para encontrar uma política ótima para 
o problema geral, ou seja, uma receita da decisão de política ótima em cada 
etapa para cada um dos estados possíveis. 
 A sequência ótima das decisões é encontrada pesquisando os resultados da 
iteração na direção à direta/esquerda. 
 
1 Backward – inicia pelo último estado até encontrar a solução ótima do estado inicial 
Forward – inicia pelo primeiro estado até encontrar a solução ótima do estado final 
Departamento de Engenharia de Produção – UFPR 116 
Professor Volmir Eugênio Wilhelm – Professora Mariana Kleina 
Exemplo A (http://mayerle.deps.prof.ufsc.br/private/eps7005/ProgDinamica.PDF) 
 
Estado: Um estado é uma configuração do sistema, e é identificado por um rótulo que 
indica suas propriedades. No problema apresentado na figura, um estado é uma 
cidade. 
Estágio: Programação dinâmica diz respeito a sistemas que evoluem de um estado 
para outro. Um estágio é um passo singular, e corresponde à transição do sistema de 
um estado para o próximo adjacente. Na figura, o movimento do viajante, de uma 
cidade para a próxima, corresponde ao estágio. Cada caminho de A para J tem quatro 
estágios. 
Ação: Em cada estado existe um conjunto de ações viáveis, das quais uma deverá ser 
escolhida e executada. No exemplo da figura, no estado C existem três ações viáveis: 
ir para a cidade E, ir para a cidade F ou ir para a cidade G. Resolver o problema de 
programação dinâmica significa, dado um objetivo, achar a melhor sequencia de 
ações. 
Plano: É um conjunto de ações, no qual para cada estado é especificada uma ação. Um 
plano ótimo é o melhor conjunto de ações considerando o objetivo fixado. 
Retorno: É algo que o sistema gera, sobre um estágio ou processo. No problema da 
figura acima, o retorno é a distância percorrida entre uma cidade e a próxima. O 
retorno é usualmente, algo do tipo: lucro, custo, distância, consumo de recursos, etc. 
Valor do Estado: É uma função dos retornos gerados, quando o sistema evolui de um 
estado inicial para um estado final, através de um plano dado. No caso do problema 
da viagem, o valor do estado, para um determinado plano, corresponde à distância 
desta cidade até a cidade terminal. O valor de um estado sob um plano ótimo é o 
valor ótimo. 
 
Exemplo B - Mochila 
Também conhecido como problema da mochila booleana. Dado um valor inteiro W e 
os conjuntos: 
o S = {1, 2, 3, ..., n} 
o W = {w1, w2, w3, ..., wn} 
o V = {v1, v2, v3, ..., vn} 
http://mayerle.deps.prof.ufsc.br/private/eps7005/ProgDinamica.PDF
Departamento de Engenharia de Produção – UFPR 117 
Professor Volmir Eugênio Wilhelm – Professora Mariana Kleina 
Onde W é a capacidade da mochila, S é um conjunto de objetos, W é o conjunto dos 
pesos de tais objetos e V é o conjunto de seus valores. Devemos encontrar quais itens 
de S devem ser colocados na mochila visando maximizar o valor carregado, sem 
exceder a capacidade da mochila. 
Podemos considerar um subproblema definido como: 
Sk = conjunto de itens numerados de 1 a k, onde n. 
Devemos considerar o peso de cada subconjunto de subitens como parâmetro. O 
subproblema consiste em computar f(r,c) (fórmula recursiva) 
f r c 
f r c se 
f r c ma f r c f r c v 
 
A melhor solução Sr com peso c é: 
 A melhor solução Sr-1 com peso c, ou 
 A melhor solução Sr-1 com peso c – wr mais o valor do item r 
Seja f(r,c) a solução ótima considerando o conjunto de objetos [1, r] e o peso c, com 
1rn e 0cW. A solução ótima para o problema será f(n, W). A relação de 
recorrência para a solução é 
 r c ma f r c f r c v 
Algoritmo 
FOR c=0:W, 
 F[0,w] = 0 
ENDFOR 
FOR r=1:n 
 F[i,0] = 0 
ENDFOR 
FOR r=1:n 
 FOR c=0:W 
 IF (wi <= W0, THEN %o item i pode fazer parte da solução 
 IF (F[r-1,c-wi] + vr > F[r-1,c], 
 F[r,c] = F[r-1,c-wi] + vr 
 ELSE 
 F[r,c] = F[r-1,c] 
 ENDIF 
 ELSE 
 F[r,c] = F[r-1,c] % wi > W – não cabe na mochila 
 ENDIF 
 ENDFOR 
ENDFOR 
Seja uma mochila de capacidade 10 e 5 objetos com seus pesos e valores 
Objeto 1 2 3 4 5 
Peso – w 8 3 6 4 2 
Valor – v 100 60 70 15 15 
 
Item\peso 0 1 2 3 4 5 6 7 8 9 10 
0 0 0 0 0 0 0 0 0 0 0 0 
1 0 0 0 0 0 0 0 0 100 100 100 
2 0 0 0 60 60 60 60 60 100 100 100 
Departamento de Engenharia de Produção – UFPR 118 
Professor Volmir Eugênio Wilhelm – Professora Mariana Kleina 
3 0 0 0 60 60 60 70 70 100 130 130 
4 0 0 0 60 60 60 70 75 100 130 130 
5 0 0 15 60 60 75 75 75 100 130 130 
 
Exemplo C (Prof. Mayerle) – Caminho de menor custo entre os nós 3.1 e 0.1 
 
Usando esta representação, têm-se os seguintes estados, de acordo com cada estágio: 
Estágio 0 u(0)={(0,1)} Estágio 1 u(1)={(1,1) , (1,2) , (1,3)} 
Estágio 2 u(2)={(2,1) , (2,2) , (2,3)} Estágio 3 u(3)={(3,1)} 
Associado a cada estado (n,i), existe um conjunto Kn,i de ações viáveis. Deste 
conjunto, caberá ao tomador de decisões escolher a ação mais adequada, segundo um 
critério estabelecido. No caso do problema em questão, o critério a ser usado é a 
minimização da distância. O conjunto Kn,i pode ser denotado genericamente por: 
Kn,i = {1, 2, ..., k, ..., Kn,i} (1) 
Os conjuntos de ações viáveis em cada estado serão os seguintes: 
K01 = Ø K11 = {1} K12 = {1} K13 = {1} 
K21 = {1, 2} K22 = {1, 2, 3} K23 = {2, 3} K31 = {1, 2, 3} 
No problema do viajante, em um estado (n,i), o estado sucessor será (n-1,j), onde j 
será determinado a partir de uma ação k, pela equação: 
J=k k ϵ Kn,i (2) 
Em geral, o sucessor de um estado é determinado a partir do estágio corrente, das 
variáveis de estado e da ação, por uma função chamada de transição t, representada 
por: 
J=t(n,i,k) (3) 
A equação (2) é um exemplo simples de função de transição. 
Quando uma ação k é escolhida em um estado (n,i), o retorno no corrente estágio é 
determinado, por uma função r(n,i,k). 
O valor do estado (n,i), sob um plano ótimo é denotado por f(n,i), que é a função do 
valor ótimo decada estado. 
Departamento de Engenharia de Produção – UFPR 119 
Professor Volmir Eugênio Wilhelm – Professora Mariana Kleina 
A especificação do problema do viajante, considerando a nomenclatura que acabou 
de ser apresentada é a seguinte: 
 
 
Exemplo C: problema do caixeiro viajante 
Em linhas gerais, a solução do problema pode ser obtida atribuindo o valor zero ao 
estado terminal, e voltando para estágios anteriores (1, 2, etc.), a fim de determinar 
em cada estado, a melhor ação a ser executada. 
 
Em detalhes, o método pode ser delineado pelo seguinte algoritmo: 
Passo 0: Inicializar o problema (ler e preparar dados do problema); 
Passo 1: Atribuir aos estados terminais o valor zero; 
Passo 2: Repetir os Passos 3, 4, 5 e 6 para cada estágio; 
Passo 3: Repetir os Passos 4, 5, e 6 para cada estado; 
Passo 4: Repetir os Passos 5 e 6 para cada ação; 
Passo 5: Comparar o valor da ação para o estado corrente; 
Passo 6: Comparar o valor calculado com a melhor ação obtida anteriormente, 
mantendo a decisão sobre a melhor delas; 
Passo 7: Parar (apresentar a solução ótima). 
 
Exemplificando a utilização do algoritmo apresentado, considere o problema do 
viajante. 
 
Inicialmente, é zerado o valor do estado (0,1), isto é, faz-se f(0,1)=0. 
 
Considerando, então, que o viajante se encontra no estágio 1, embora não se saiba se 
o mesmo irá passar por (1,1), caso isto ocorra, então só restará uma ação a ser 
tomada: ir para (0,1), e este caminho tem um custo 3. Portanto, o valor do estado 
(1,1) é 3. Outra hipótese a ser considerada é que, dado que o viajante se encontra no 
estado (0,2), a única ação viável é deslocar-se para o estado (0,1) percorrendo uma 
distância 6, e este será o valor do estado (1,2). Do mesmo modo, caso o viajante esteja 
no estado (1,3), ele poderá se deslocar para o estado (0,1) percorrendo uma distância 
2, que, também, será o valor do estado (1,3). Resumidamente: 
Departamento de Engenharia de Produção – UFPR 120 
Professor Volmir Eugênio Wilhelm – Professora Mariana Kleina 
 
f(1,1)=r(1,1,1) + f(0,1)=3 + 0=3 
f(1,2)=r(1,2,1) + f(0,1)=6 + 0=6 
f(1,3)=r(1,3,1) + f(0,1)=2 + 0=2 
 
 
Considerando, agora, o estágio 2, tem-se que o viajante poderá se encontrar em três 
estados diferentes. No estado (2,1), duas decisões poderão ser tomadas: ir para o 
estado (1,1), com um custo 4 até alcançar este estado, e a partir daí ter um custo 
adicional 3 até o estado final (Total: 4 + 3=7), ou ir para o estado (1,2), com um custo 
6, e a partir deste estado alcançar o estado final com um custo adicional 6 (Total: 6 
+6=12). 
Resumindo: 
f(2,1) = r(2,1,1) + f(1,1) = 4 + 3 = 7 , se k=1 
f(2,1) = r(2,1,2) + f(1,2) = 6 + 6 = 12 , se k=2 
Obviamente, entre as duas alternativas apresentadas, o melhor é optar pela primeira 
cujo custo total, até alcançar o estado final, é o menor e, portanto f(2,1)=7, que 
corresponde à ação ótima K*21=1. Em outras palavras, no caso genérico tem-se: 
 (1) 
 (2) 
No caso específico do Problema do Viajante, a equação acima será: 
 (3) 
Aplicando-se a equação (3) para o estado (2,1), tem-se: 
 
Ou simplesmente: 
f(2,1) = min[4 + 3, 6+6]=7 
Departamento de Engenharia de Produção – UFPR 121 
Professor Volmir Eugênio Wilhelm – Professora Mariana Kleina 
onde o valor de estado obtido corresponde à ação ótima K*21=1, como já havia sido 
concluído anteriormente. 
Procedimento idêntico realizado para o estado (2,2), termina f(2,2): 
 
=min[4 + 3, 5 + 6, 6+6]=7 
com K*22=1. 
Para o estado (2,3), com o uso da equação (3), obtem-se: 
 
=min[4 + 6, 5 + 2]=7 
com K*23=3. 
Realizando estes cálculos, também, para o estado (3,1), tem-se: 
 
com K*31=3. 
Estando, portanto, no estado inicial (3,1) o viajante deverá ir para o estado (3-1, K*31), 
isto é, para o estado (2,3) e nesta cidade, o viajante deverá decidir em ir para o estado 
(2-1, K*23), isto é, para o estado (1,3), e a partir deste estado só restará uma ação 
possível para ser executada: ir para o estado (0,1). Esta sequência de decisões 
corresponde á seguinte trajetória: 
 
cujo custo total é (1 + 5 + 2)=8, que é o valor encontrado para f(2,1). 
Este procedimento pode ser sistematizado através de tabelas, como a apresentada a 
seguir: 
Este procedimento pode ser sistematizado através de tabelas, como a apresentada a 
seguir: 
Departamento de Engenharia de Produção – UFPR 122 
Professor Volmir Eugênio Wilhelm – Professora Mariana Kleina 
 
 
 
Exemplo D https://www.ime.unicamp.br/~andreani/MS515/capitulo7.pdf 
 
Programação dinâmica probabilística 
 O estado na próxima etapa não é determinado pelo estado e a decisão no 
estágio atual. 
 Em vez disso, existe uma distribuição probabilística para o próximo estado. 
Essa distribuição é completamente determinada pelo estado e a decisão no 
estado atual. 
 O objetivo esperado é otimizado 
https://www.ime.unicamp.br/~andreani/MS515/capitulo7.pdf
Departamento de Engenharia de Produção – UFPR 123 
Professor Volmir Eugênio Wilhelm – Professora Mariana Kleina 
 
 
Aplicações 
http://www.nptel.ac.in/downloads/105108127/ 
 
Exemplo http://mat.gsia.cmu.edu/classes/dynamic/node3.html 
http://www.nptel.ac.in/downloads/105108127/
http://mat.gsia.cmu.edu/classes/dynamic/node3.html