USO DE REDES PARA REPRESENTAÇÃO DO PROBLEMA

A rede da Figura 1 é conveniente para representação do problema. Pode-se, entretanto, fazer uso de redes para representação de outros problemas que não dizem respeito ao problema do viajante. Em outras palavras, esta estrutura pode ser usada para representação de problemas menos óbvios que o apresentado.

 

Em geral, o sistema pode ser representado por nós da rede, cujos arcos representam as possíveis transições, e os números associados a cada arco representam os retornos.

 

Para generalização desta representação, podem-se denotar os nós pelas variáveis de estado e estágio. Assim, ao invés de representar uma cidade pelo símbolo      , esta mesma cidade será representada por        ,  indicando estar faltando uma viagem (estágio) para a chegada na cidade       e se trata da segunda alternativa (cidade) possível do viajante ao se encontrar neste estágio. Generalizando, o i-ésimo estado no estágio n é denotado por (n,i).

 

 

 

 

 

 

 

 

 

 

 

 

 

                                  

 

 

                                                                   Figura 2: problema da viagem entre a cidade       e

 

                                                                     a cidade      , denotado pelas variáveis de estágio e estado.

 

 

 

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)

 

No Problema do Viajante, por exemplo, a identificação da k-ésima ação com a cidade a ser escolhida (viagem a ser realizada), pode ser feita com base sequencialmente do NORTE para o SUL.

Assim, 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 de cada estado.

 

A especificação do problema do viajante, considerando a nomenclatura que acabou de ser apresentada é a seguinte: