Exercícios Resolvidos de Pesquisa Operacional - Heurística do Vizinho Mais Próximo e Ford-Fulkerson

Questão 1 Adaptação da Heurística do Vizinho mais próximo para o Problema de Roteamento de Veículos com frota homogênea Ideia básica Passo 1 Partir do depósito com um novo veículo e ir até a cidade mais próxima ainda não visitada Passo 2 Determinar a cidade mais próxima da última cidade inserida na rota e verificar se é possível atender sua demanda Passo 3 Se for possível atender a demanda dessa cidade adicionála à rota Caso contrário retornar ao depósito e voltar ao Passo 1 Use essa adaptação para calcular rotas para o problema de roteamento de veículosVRP 20 pts cij 0 1 2 3 4 5 6 7 8 9 0 120 102 95 63 73 78 54 100 81 1 120 28 42 63 157 187 171 220 194 2 102 28 51 57 130 163 150 201 180 3 95 42 51 32 149 170 149 192 160 4 63 63 57 32 120 139 117 161 132 5 73 157 130 149 120 45 58 106 121 6 78 187 163 170 139 45 32 64 91 7 54 171 150 149 117 58 32 54 63 8 100 220 201 192 161 106 64 54 50 9 81 194 180 160 132 121 91 63 50 Capacidade de carga dos veículos 12t Resposta da Questão 1 Nº Rotas Finais Carga Final 1 0765890 11t 2 04320 11t 3 010 6t Questão 2 Considere a rede capacitada abaixo Os números próximos aos arcos arestas são as capacidades nas arestas Resposta da Questão 2 Caminho Fluxo no caminho SceT 2 SabdT 2 SbeT 1 SaeT 1 ScdT 2 TOTAL 8 Execute o algoritmo FordFulkerson Selecione sempre o caminho aumentante mais promissor ou seja aquele que admite o maior fluxo entre S e T 30 pts Rede de Fluxo a d a d 04 02 02 05 02 02 T S b b S 4 2 2 2 02 01 02 1 1 01 04 c c e e 06 Rede de Fluxo a d a d 04 02 02 05 02 02 T S b b S 4 2 2 2 02 01 02 1 1 01 04 c c e e 06 Rede Residual 4 2 5 T S 2 b 2 2 1 4 1 c 6 e Rede Residual 4 2 5 T S 2 b 2 2 1 4 1 c 6 e Rede de Fluxo a d a d 04 02 02 05 02 02 T S b b S 4 2 2 2 02 01 02 1 1 01 04 c c e e 06 Rede de Fluxo a d a d 04 02 02 05 02 02 T S b b S 4 2 2 2 02 01 02 1 1 01 04 c c e e 06 Rede Residual 4 2 5 T S 2 b 2 2 1 4 1 c 6 e Rede Residual 4 2 5 T S 2 b 2 2 1 4 1 c 6 e Rede de Fluxo a d a d 24 22 22 25 02 02 T S b b S 4 2 2 2 02 01 02 1 1 01 04 c c e e 06 Rede Residual 4 2 5 T S 2 b 2 2 1 4 1 c 6 e Rede Residual 4 2 5 T S 2 b 2 2 1 4 1 c 6 e Rede de Fluxo a d a d 24 22 22 25 02 02 T S b b S 4 2 2 2 02 01 02 1 1 01 04 c c e e 06 Rede Residual 4 2 5 T S 2 b 2 2 1 4 1 c 6 e Rede Residual 4 2 5 T S 2 b 2 2 1 4 1 c 6 e Rede de Fluxo a d a d 24 22 22 45 12 01 T S b b 12 11 1 4 1 36 c c e e 1 4 Rede Residual 4 2 5 T S 2 b 2 2 1 4 1 c 6 e Rede Residual 4 2 5 T S 2 b 2 2 1 4 1 c 6 e Rede de Fluxo a d a d 34 22 22 45 12 01 T S b b 12 11 1 4 1 36 c c e e 1 4 Rede Residual 4 2 5 T S 2 b 2 2 1 4 1 c 6 e Rede Residual 4 2 5 T S 2 b 2 2 1 4 1 c 6 e Questão 3 Quais os caminhos mínimos entre o nó 0 e os demais Se a solução for múltipla mostreas 30 pts cij 0 1 2 3 4 0 5 7 inf inf 1 6 6 inf 2 4 5 3 3 4 No enunciado original desta questão elaborado corretamente o grafo era direcionado Porém quando um aluno perguntou se o grafo seria direcionado ou não eu falei erroneamente que era não direcionado e isso levou a um ciclo negativo entre os nós 3 e 4 Portanto na correção desta questão vou apenas conferir detalhadamente se o algoritmo de Floyd foi executado corretamente até o fim da iteração 3 C0 0 1 2 3 4 d0 0 1 2 3 4 0 5 7 inf inf 0 0 0 0 0 1 5 6 6 inf 1 1 1 1 1 2 7 6 4 5 2 2 2 2 2 3 inf 6 4 3 3 3 3 3 3 4 inf inf 5 3 4 4 4 4 4 Iteração 1 C1 0 1 2 3 4 d1 0 1 2 3 4 0 5 7 inf inf 0 0 0 1 0 1 5 6 6 inf 1 1 1 1 1 2 7 6 4 5 2 2 2 2 2 3 inf 6 4 3 3 1 3 3 3 4 inf inf 5 3 4 4 4 4 4 Iteração 2 C2 0 1 2 3 4 d2 0 1 2 3 4 0 5 7 11 inf 0 0 0 1 2 1 5 6 6 inf 1 1 1 1 2 2 7 6 4 5 2 2 2 2 2 3 11 6 4 3 3 1 3 3 3 4 inf inf 5 3 4 2 2 4 4 Iteração 3 C3 0 1 2 3 4 d3 0 1 2 3 4 0 5 7 11 12 0 0 0 1 3 1 5 6 6 11 1 1 1 1 3 2 7 6 4 5 2 2 2 2 3 3 11 6 4 3 3 1 3 3 3 4 12 11 5 3 4 1 3 3 4 Até aqui C4 0 1 2 3 4 d4 0 1 2 3 4 0 5 7 11 8 0 0 0 4 3 1 5 6 6 3 1 1 3 4 3 2 7 6 4 1 2 2 3 4 3 3 11 6 4 3 3 1 3 3 3 4 8 3 1 3 4 1 3 3 4 b Qual arco não pode ser aumentado em comprimento sem alterar P Porque não tem outro arco com esta propriedade 05 tps Resposta Seja P a rota ACDHI O comprimento de P é 24 Considerando apenas os arcos de P apenas AC não pode aumentar em mais de 2 unidades por exsistirem diferentes caminhos e o único arco que pertence a todos os caminhos é AC Todos os arcos que não fazem parte de alguma das 4 rotas podem aumentar indefinidamente c Existe algum arco que não pode diminuir em comprimento sem alterar P Justifique sua resposta 05 pts Resposta Seja a rota ACDHI O comprimento de P é 24 Considerando somente os arcos de P se diminuir o comprimento de qualquer um deles o caminho não muda Se diminuir o comprimento de vários arcos fora de P pex diminuir o arco AB em 9 unidades o caminho mínimo entre A e I será diferente de P