top of page

PESQUISA OPERACIONAL

PESQUISA OPERACIONAL

Disciplina: Programação Dinâmica

SOLUÇÃO DO PROBLEMA DO VIAJANTE PELO PROCESSO ITERATIVO

    

SOLUÇÃO DO PROBLEMA DO VIAJANTE PELO PROCESSO ITERATIVO

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:

 

P0 → Inicializar o problema (ler e preparar dados do problema);

P1 → Atribuir aos estados terminais o valor zero1;

P2 → Repetir os passos 3, 4, 5 e 6 para cada estágio;

P3 → Repetir os passos 4, 5, e 6 para cada estado;

P4 → Repetir os passos  5 e 6 para cada ação;

P5 → Comparar o valor da ação para o estado corrente;

P6 → Comparar o valor calculado com a melhor ação obtida anteriormente, mantendo a decisão sobre a melhor delas;

P7 → 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)2, 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:

        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

___________________

¹ O valor zero, atribuído aos estados terminais, pode ser adequadamente substituído pelos valores residuais do sistema, considerando cada

  estado no final de sua vida útil. Em alguns casos é conveniente atribuir um valor que penabilize o plano que contenha um determinado estado

  terminal, caso este estado não seja desejável.

 

² É evidente que ao estar neste estado, correspondente a cidade       , nada mais resta a fazer, e portanto nenhuma distância restará para

  ser percorrida.

_____________________

 

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 a 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

 

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:

 

 

                                      

                                             

                                                                           =Min [7 + 7 , 4 + 7 , 1 + 7]=8

 

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 sistatizado atravésde tabelas, como a apresentada a seguir:

 

Com base na Tabela acima, pode-se obter a sequência de decisões ótimas, dadas pelos apontadores ou (←) – ou PONTEIROS termo utilizado em Linguagem de Programação: ele trabalha com o REGISTRO na MEMÓRIA - associado à ação ótima de cada estado, resultando com isto a Tabela abaixo que contém apenas o plano ótimo.

Voltar para PROGRAMAÇÃO DINÂMICA: Tópicos

  A partir de 23 Jul de 2018

Você é o Visitante de Número

bottom of page