Baixe Introdução à Pesquisa Operacional (9ª parte) e outras Notas de estudo em PDF para Cultura, somente na Docsity! Módulo 9 RedesTransporte – Programação Dinâmica Prof. Ms. Antonio dos Santos Problemas de Menor Caminho Se considerarmos uma rede na qual o arco signifique a distância entre dois pontos (nós) e desejarmos achar a rota que une estes pontos com distância mínima, teremos um problema do tipo do Menor Caminho. Este tipo de problema pode ser generalizado e aplicado a distribuição de produtos, entre outros. Disciplina: Pesquisa Operacional Prof. Ms. Antonio dos Santos Problemas de Menor Caminho Regra de Fluxo Balanceado Uma maneira de modelar um problema de rede é seguir a Regra Fluxo Balanceado para cada nó. No Caso de Oferta Total = Demanda Total ⎥ ⎦ ⎤ ⎢ ⎣ ⎡ =⎥ ⎦ ⎤ ⎢ ⎣ ⎡ −⎥ ⎦ ⎤ ⎢ ⎣ ⎡ nó do andaOferta/Dem nó no saídas de total nó no entradas de total Disciplina: Pesquisa Operacional Prof. Ms. Antonio dos Santos Problemas de Menor Caminho Regra de Fluxo Balanceado Caso a Oferta Total > Demanda Total Total de Entradas Total de Saídas Oferta / - > Demanda no nó do nó do nó Caso a Oferta Total < Demanda Total Total de entradas Total de Saídas Oferta / - < Demanda no nó do nó do nó Disciplina: Pesquisa Operacional Prof. Ms. Antonio dos Santos Problemas de Menor Caminho Exemplo B C D E F G H A B 4 3 2 1 40 30 30 30 20 20 20 Menor Caminho Rota Fluxo Oferta/ De Para Km Selecionada Nó Líquido Demanda A 1 40 0 A 0 -1 A 2 30 0 1 0 0 1 3 30 0 2 0 0 1 4 20 0 3 0 0 2 4 30 0 4 0 0 3 B 20 0 B 0 1 4 B 20 0 Distância Total 0 1 2 3 4 5 6 7 8 9 10 Disciplina: Pesquisa Operacional Prof. Ms. Antonio dos Santos Problemas de Menor Caminho Exemplo-Solução B C D E F G H A B 4 3 2 1 40 30 30 30 20 20 20 1 2 3 4 5 6 7 8 9 10 Menor Caminho Rota Fluxo Oferta/ De Para Km Selecionada Nó Líquido Demanda A 1 40 1 A -1 -1 A 2 30 0 1 0 0 1 3 30 0 2 0 0 1 4 20 1 3 0 0 2 4 30 0 4 0 0 3 B 20 0 B 1 1 4 B 20 1 Distância Total 80 Disciplina: Pesquisa Operacional Prof. Ms. Antonio dos Santos PROGRAMAÇÃO DINÂMICA 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. Disciplina: Pesquisa Operacional Prof. Ms. Antonio dos Santos PROGRAMAÇÃO DINÂMICA Definições: Etapas - São os diferentes níveis naturais em que se pode dividir um problema. Em cada uma delas estabelece-se um plano de decisões. Estados - Cada etapa terá associado um determinado número de estados (finito ou infinito, discreto ou contínuo dependendo da natureza do problema). Em geral os estados são as várias condições possíveis nos quais o sistema se pode apresentar numa dada etapa. Decisões - Segundo um determinado plano, o seu efeito em cada etapa é transformar o estado corrente num outro estado associado à etapa seguinte. Essa transformação pode eventualmente obedecer a uma distribuição de probabilidade, contudo os casos apresentados são de caráter determinístico e não probabilístico. Disciplina: Pesquisa Operacional Prof. Ms. Antonio dos Santos PROGRAMAÇÃO DINÂMICA Definições: Recursividade - É uma relação funcional que identifica o plano ótimo para cada estado na etapa genérica “n”, dado o plano ótimo da etapa seguinte, isto é, dado o plano ótimo para cada estado da etapa (n+1). Esta relação varia com o problema em estudo. Disciplina: Pesquisa Operacional Prof. Ms. Antonio dos Santos PROGRAMAÇÃO DINÂMICA Notação Usual: Disciplina: Pesquisa Operacional Prof. Ms. Antonio dos Santos PROGRAMAÇÃO DINÂMICA Exemplo: Disciplina: Pesquisa Operacional Prof. Ms. Antonio dos Santos PROGRAMAÇÃO DINÂMICA Solução: 5 8 8 10 (1+3) (4+4) (6+3) (3+4) (3+3) (3+4) Disciplina: Pesquisa Operacional Prof. Ms. Antonio dos Santos PROGRAMAÇÃO DINÂMICA Solução: 3 5 1 3 1 4 ou Disciplina: Pesquisa Operacional Prof. Ms. Antonio dos Santos PROGRAMAÇÃO DINÂMICA Solução:Solução Ótima: 4 + 3 + 1 + 3 = 11 Km, 3 + 4 + 1 + 3 = 11 Km, 3 + 1 + 3 + 4 = 11 Km Rotas Distâncias Disciplina: Pesquisa Operacional Prof. Ms. Antonio dos Santos
