Disciplina: Programação Dinâmica

PESQUISA OPERACIONAL

TERMINOLOGIA

    

TERMINOLOGIA:

O objetivo desta seção é formalizar o sistema e a terminologia a ser adotada. Para exemplificar, será usado o Problema de obtenção do Caminho de Mínima Distância em uma Rede Simples.

Na Figura 1 abaixo é apresentado uma rede viária, onde uma cidade X é representada pelo símbolo       . Os comprimentos das vias (custos) estão indicados (não está em escala). Um homem deseja viajar da cidade A para a cidade H. Qual o caminho que ele deverá seguir?

Figura 1: Problema de obtenção do Caminho de Mínima

              Distância entre as cidades A e H.

O interesse neste problema não reside apenas em sua solução, mas, também, em desenvolver um método que possa resolver outros problemas similares. Para tanto, será apresentada, a seguir, uma terminologia que será usada nestes problemas.

 

Estado: Um estado é uma configuração do sistema, e é identificado por um rótulo que indica suas propriedades. No problema apresentado na Figura 1, 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 1, o movimento do viajante, de uma cidade para a próxima, corresponde ao estágio. Cada caminho cidade A para a cidade H tem três 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 1, no estado (cidade 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 sequência de ações.

 

Plano: Um plano é um conjunto de ações, no qual para cada estado é especificado uma ação. Um plano ótimo é o melhor conjunto de ações considerando o objetivo fixado.

 

Retorno: O retorno é algo que o sistema gera, sobre um estágio ou processo. No problema da Figura 1, é a distância percorrida entre uma cidade e a próxima. O retorno é, usualmente, algo do tipo: lucro; custo; distância; consumo de recursos; e etc.

 

Valor do Estado: O 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.

 

OBSERVAÇÃO: Diferentes problemas serão estudados, sendo, entretanto, comuns a todos a estrutura da Programação Dinâmica, que pode, para o exemplo apresentado ser assim descrita:

OBSERVAÇÃO: Veja outro Exemplo de Aplicação - O Problema da Diligência (Formato ".PDF").     Veja uma Vídeo Aula

Carlos Monardes - Clase 01, Capítulo 1, Programación Dinámica

 

Publicado em 19 de mar de 2013

Problema de la Diligencia. Características y Elementos de la Programación Dinámica. Programación Dinámica Determinística.

Diapositivas: https://docs.google.com/file/d/0B2E6295qzJL6dDdaWFRKYkgzX3M/edit?usp=sharing

  A partir de 23 Jul de 2018

Você é o Visitante de Número

(48) 8410.6510 /  faleconosco@ensinoeinformacao.com  /  Florianópolis - SC - Brasil

  • w-facebook
  • Twitter Clean
  • w-googleplus

® 2003 - 2018 Todos os direitos Reservados, ensinoeinformacao.com

Temos Uma versão desta Revista Especificamente para SmartPhones: Versão mais Enxuta somente com Vídeo Aulas e Eventos