TRABALHO PARA AP2: O PROBLEMA DO CAIXEIRO VIAJANTE

UNIABEU CENTRO UNIVERSITÁRIO

MAGDA CRISTYAN

RAFAEL LIMA

GESTÃO DE SISTEMA DE INFORMAÇÕES

Angra dos Reis

2016

TRABALHO PARA AP2: O PROBLEMA DO CAIXEIRO VIAJANTE

Trabalho apresentado em

cumprimento   às    exigências    da

atividade para AP2, da disciplina

de Gestão de Sistema de Informações.

Orientador: Prof. Jefferson Borges

Angra dos Reis

2016

Sumário

1.INTRODUÇÃO        4

2.O PROBLEMA DO CAIXEIRO VIAJANTE        4

3.SOFTWARE UTILIZADO NA RESOLUÇÃO DO PROBLEMA        4

    3.1. APLICAÇÃO DO SOLVER NO PROBLEMA DO CAIXEIRO VIAJANTE        5

    3.2 VANTAGENS DO SOLVEL        5

    3.3 DESVANTAGENS DO SOLVER        5

4. CONCLUSÃO        5

5. BIBLIOGRAFIA        6

1. INTRODUÇÃO

Antigamente muitos vendedores, chamados de caixeiros viajantes, ganhavam a vida oferecendo seus produtos em diferentes cidades. Imagine que um caixeiro viajante escolhesse algumas cidades e precisasse encontrar o caminho mais curto para suas andanças. Em que ordem ele deveria percorrer as cidades escolhidas? Se fossem poucas cidades, seria fácil descobrir. E se o caixeiro quisesse percorrer todas as capitais brasileiras? Mas são tantas, que se levássemos apenas 1 segundo para calcular a distância total de cada possível percurso, levaríamos cerca de um bilhão de vezes a idade do universo para encontrar a resposta.

Isso acontece porque o número de percursos alternativos cresce quando aumentamos o número de cidades. Esse é o chamado Problema do Caixeiro Viajante, uma questão matemática muito importante para a indústria. Embora se trate de um problema simples, sua resolução pode ser tão complexa quanto forem os elementos envolvidos.

Historicamente, não se sabe exatamente quem foi o criador do problema. Embora atribuído a certos acadêmicos norte-americanos, é provável que  ele já fosse utilizado por mercadores e senescais ao longo da idade média e possivelmente além.  As rotas comerciais pelo interior da Eurásia adotadas pelos povos da Antiguidade Clássica possivelmente faziam uso do problema do caixeiro viajante.

1. O PROBLEMA DO CAIXEIRO VIAJANTE

O problema consiste na procura por um trajeto de menor distância para que um caixeiro possa sair da cidade A e percorrer outras como B e C sem a necessidade de ter de passar por elas mais de uma vez, regressando sempre a cidade inicial. Nos dias de hoje, o PCV é muito usado em empresas e setores governamentais ligados a transporte, assim como pelas áreas de segurança, saúde e educação.

1. SOFTWARE UTILIZADO NA RESOLUÇÃO DO PROBLEMA

Dentre os muitos suplementos e funções disponibilizados pelo software Excel da Microsoft Office, temos o Solver, ao qual possibilita realizar espécies de simulações na planilha, com base em limites e restrições. Esta ferramenta é utilizada, principalmente, para análises de sensibilidade contendo mais de uma variável e com restrições de parâmetros.

Com o suplemento ativo no Excel, o usuário pode localizar um resultado ideal para determinada fórmula. Este resultado, por sua vez, será direcionado para uma célula pré-determinada, chamada de célula de destino, onde temos as possibilidades de maximizar/minimizar valores ou atingir uma meta de valor específico. Para isso, o Solver trabalha com um grupo de células que se relacionam direta ou indiretamente com a fórmula posta na célula de destino.

APLICAÇÃO DO SOLVER NO PROBLEMA DO CAIXEIRO VIAJANTE

Um problema típico de programação linear contém:

• Variáveis de decisão: cidades de entrega de mercadoria;
• Função objetivo: menor rota a ser percorrida no atendimento a todas as cidades;
• Restrições do sistema: distância, custo, tempo.

1. VANTAGENS DO SOLVER

• Facilidade de utilização
• Disponível a todos os usuários do Excel.
• Determina soluções de problemas envolvendo múltiplas variáveis e restrições, determinando a melhor solução.
• Auxilia na economia de capital, recursos e tempo.

1. DESVANTAGEM DO SOLVER

• Alto custo na aquisição do aplicativo Excel
• É necessário alto conhecimento na execução deste aplicativo

1. CONCLUSÃO

Esse problema do caixeiro viajante é resolvido com a ajuda de computadores, mais precisamente, com a utilização de softwares e o Solver é uma opção para a empresa, pois possibilita a realização de simulações em um modelo criado pelo usuário, para depois de testado e aprovado, ser usado no ambiente real, ou seja, a empresa tem a possibilidade de simular diferentes cenários e optar por aquele que melhor atender suas necessidades.

Após informar quais pontos a serem atendidos, quais restrições ou limites a serem obedecidas e quais objetivos a serem atingidos, a ferramenta Solver pode determinar as soluções ideais para problema.

...