Notas de Aula - Problema do Caixeiro Viajante PCV e Algoritmos de Resolução

Notas de Aula da Disciplina de Métodos Quantitativos para Tomada de Decisão Prof Edgard Pedroso Arquivo de aulas n o 03 Problema do Caixeiro Viajante PCV algoritmo de designação em conjunto com uma variante do método Branch and Bound B B Problema do Caixeiro Viajante PCV O PCV é um problema que envolve uma pessoa veículo que deve sair de uma localidade sede visitar n1 dentre n localidades uma única vez e em seguida retornar à sede O custo cij da viagem entre as localidades i e j pode ser igual ou não a cji caracterizando um PCV simétrico ou não simétrico respectivamente O objetivo do PCV é determinar um itinerário circuito hamiltoniano de custo mínimo Ilustração PCV 3 4 5 2 1 6 3 O jogo de nome Around the World proposto por Willian Rowan Hamilton 1857 baseavase em encontrar uma rota através dos vértices cidades de um dodecaedro que iniciasse e terminasse em um mesmo vértice cidade sem repetir a visita Uma solução do jogo passou a ser chamada de Circuito Hamiltoniano As figuras a seguir apresentam uma solução rota possível Um Circuito Hamiltoniano Dodecaedro 20 vértices 30 arestas12 faces pentagonais Circuito Hamiltoniano Animações de 2 exemplos de circuitos Hamiltonianos V A F 2 Problema do Caixeiro Viajante PCV Quando não é dada a matriz de distâncias mínimas entre todos pares de nós o PCV tem como prérequisito o uso do Algoritmo de Floyd Existem várias formas de se resolver o PCV 1 Métodos Exatos Método que utiliza uma variante do Método Branch and Bound Modelo Matemático outros 2 Métodos Heurísticos Algoritmo de Clarke Wright savings Algoritmo da Inserção do nó mais próximo outros 3 Métodos MetaHeurísticos Algoritmos Genéticos Simulated Annealing outros 1 Métodos Exatos para resolver o PCV A Método que utiliza uma Variante do método Branch and Bound Ramifica e Limita É possível associar um Problema de Designação PD a todo PCV É evidente que a toda solução viável do PCV corresponde uma solução do PD associado Contudo o PD poderá possuir soluções viáveis que não representam soluções viáveis para o PCV pois vários circuitos ao invés de apenas um podem ser formados pela solução do PD De qualquer forma a solução ótima do PD associado serve como uma 1ª aproximação da solução do PCV Assim sendo aplicase o Método Húngaro à matriz de custos do PD e se o resultado corresponder a um itinerário viável para o PCV este será o itinerário ótimo Caso contrário podese usar uma variante do Método Branch and Bound para criar novos PDs até encontrar a solução ótima do PCV 1 1 1 1 1 1 1 1 1 1 Nós de Oferta Nós de Demanda 3 2 1 1 4 5 2 3 4 5 1 1 1 1 1 1 1 1 1 1 1 3 2 1 4 5 2 3 4 5 4 1 2 3 5 EX 1 Viável p PCV 1 1 1 1 1 1 1 1 1 1 1 3 2 1 4 5 2 3 4 5 EX 2 Viável p PD 4 1 2 3 5 EX 2 Inviável p PCV Designações Possíveis p o PD EX 1 Viável p PD Toda solução do PCV é viável para o PD mas nem toda solução de PD é viável para o PCV No PD os nós da esquerda e direita são considerados distintos mas no PVC não Método que utiliza uma variante do Método Branch Bound método exato 1 5 4 2 3 j i 1 2 3 4 5 1 0 10 3 6 9 2 5 0 5 4 2 3 4 9 0 7 8 4 7 1 3 0 4 5 3 2 6 5 0 C Suponha o Problema do Caixeiro Viajante PCV não simétrico de cinco cidades representado pelo grafo a seguir A matriz inicial de custos Mínimos entre todos os pares de nós Cij associado ao grafo foi obtida como na aplicação do algoritmo de Floyd e é dada ao lado do grafo Exemplo de Referência Determine um itinerário ótimo para o Caixeiro Viajante dada a matriz C de custos ou seja de distâncias mínimas entre os diversos pares de pontos através dos quais ele deve passar Grafo Matriz inicial de custos mínimos entre todos os pares 7 Método que utiliza uma variante do Método Branch Bound método exato j i 1 2 3 4 5 1 0 10 3 6 9 2 5 0 5 4 2 3 4 9 0 7 8 4 7 1 3 0 4 5 3 2 6 5 0 C Inicialmente devemos obter a solução ótima do Problema de Designação PD associado ao PCV aplicando o Algoritmo Húngaro e para tanto devese substituir os zeros da diagonal principal da matriz de custos por infinito j i 1 2 3 4 5 1 10 3 6 9 2 5 5 4 2 3 4 9 7 8 4 7 1 3 4 5 3 2 6 5 8 Método que utiliza uma variante do Método Branch Bound método exato j i 1 2 3 4 5 1 10 3 6 9 2 5 5 4 2 3 4 9 7 8 4 7 1 3 4 5 3 2 6 5 Aplicando o Algoritmo Húngaro temse j i 1 2 3 4 5 1 7 0 3 6 2 3 3 2 0 3 0 5 3 4 4 6 0 2 3 5 1 0 4 3 1 Coloque os custos por unidade de recurso na forma de matriz matriz de eficiência 2 Subtraiaomenorcustodecadalinhaeoucolunatalqueexistanomínimo umzeroemcadalinha emcadacoluna j i 1 2 3 4 5 1 7 0 1 6 2 3 3 0 0 3 0 5 1 4 4 6 0 2 3 5 1 0 4 1 Subtrações das linhas Subtrações das colunas 9 Método que utiliza uma variante do Método Branch Bound método exato j i 1 2 3 4 5 1 7 0 1 6 2 3 3 0 0 3 0 5 1 4 4 6 0 2 3 5 1 0 4 1 j i 1 2 3 4 5 1 7 0 1 6 2 3 3 0 0 3 0 5 1 4 4 6 0 2 3 5 1 0 4 1 3 Marque o máximo número de designações às células zero como segue 31 Em cada linha com somente um 0 designe o 0 e elimine todos os 0s daquela coluna 32 Em cada coluna com somente um 0 designe o 0 e elimine todos os 0s daquela linha 33 Repita 31 e 32 até que todos os 0s tenham sido designados ou eliminados 34 Esteja certo de que não existe mais do que um 0 designado em cada linha e coluna 10 j i 1 2 3 4 5 1 7 0 1 6 2 3 3 0 0 3 0 5 1 4 4 6 0 2 3 5 1 0 4 1 4 Se existe um 0 designado em cada linha e coluna estas serão as designações ótimas Marque as correspondentes células da matriz original e obtenha o custo total Estas são as designações de custo total mínimo 4 Não existe um 0 designado em cada linha e coluna Segue para o passo 5 j i 1 2 3 4 5 1 7 0 1 6 2 3 3 0 0 3 0 5 1 4 4 6 0 2 3 5 1 0 4 1 j i 1 2 3 4 5 1 7 0 1 6 2 3 3 0 0 3 0 5 1 4 4 6 0 2 3 5 1 0 4 1 5 Se não existe um 0 designado em cada linha e em cada coluna obtenha mais 0s como segue 51 Marque todas as linhas que não tenham designação 52 Marque todas as colunas com 0s eliminados nas linhas marcadas 53 Marque todas as linhas com 0s designados nas colunas marcadas 54 Repita 52 e 53 até a exaustão 6 Risque com um traço todas as linhas não marcadas e colunas marcadas Verifique 1 Se o no de traços no de 0s designados 2 Se todos os 0s designados ou eliminados estão riscados com um traço 1 Se o no de traços no de 0s designados 2 Se todos os 0s designados ou eliminados estão riscados com um traço SIM SIM 12 j i 1 2 3 4 5 1 7 0 1 6 2 3 3 0 0 3 0 5 1 4 4 6 0 2 3 5 1 0 4 1 j i 1 2 3 4 5 1 8 0 1 6 2 3 3 0 0 3 0 6 1 4 4 5 0 1 2 5 0 0 3 0 72 e 73 Subtraia o menor dos não riscados e some nas intersecções 13 j i 1 2 3 4 5 1 8 0 1 6 2 3 3 0 0 3 0 6 1 4 4 5 0 1 2 5 0 0 3 0 Existe um 0 designado em cada linha e coluna FIM 3 Marque o máximo número de designações às células zero como segue 31 Em cada linha com somente um 0 designe o 0 e elimine todos os 0s daquela coluna 32 Em cada coluna com somente um 0 designe o 0 e elimine todos os 0s daquela linha 33 Repita 31 e 32 até que todos os 0s tenham sido designados ou eliminados 34 Esteja certo de que não existe mais do que um 0 designado em cada linha e coluna 8 Faça o máximo no de designações como no passo 3 e repita 5 6 e 7 até que exista uma designação 0 em cada linha e cada coluna como descrito no passo 4 4 Se existe um 0 designado em cada linha e coluna estas serão as designações ótimas Marque as correspondentes células da matriz original e obtenha o custo total Estas são as designações de custo total mínimo 14 Método que utiliza uma variante do Método Branch Bound Ramifica e Limita método exato j i 1 2 3 4 5 1 8 0 1 6 2 3 3 0 0 3 0 6 1 4 4 5 0 1 2 5 0 0 3 0 j i 1 2 3 4 5 1 10 3 6 9 2 5 5 4 2 3 4 9 7 8 4 7 1 3 4 5 3 2 6 5 1 5 4 2 3 Temse a solução do PD dada por dois circuitos 131 e 2542 A partir daí aplicase a variante do método B B Z 34251 15 matriz inicial Atenção Se tivesse sido obtido um circuito único já seria a solução ótima para o PCV 2 subcircuitos P1 P2 P3 131 e 2542 c13 31 c 15 Z Variante do BB Se vários circuitos são formados então tomase por facilidade o circuito que tiver o menor número de nós S 1 2 k e acrescentase os custos c12 c13 c14 c1k c21 c23 c24 c2k c31 c32 c34 c3k até ck1 ck2 ck3 ckk1 ao problema original um conjunto de cada vez resultando em k novos problemas de designação Rompimento do subcircuito 131 com menor nº de nós 1 5 4 2 3 Solução inicial do PD 131 Todas combinações começando com 1 Todas combinações começando com 3 Todas combinações começando com 1 Todas combinações começando com 2 Todas combinações começando com 3 Todas combinações começando com k P1 P2 131 e 2542 13 c 15 Z Resolução do problema P2 Impomos a restrição c13 ꚙ no Problema de Designação logo a matriz inicial do PD passa ser j i 1 2 3 4 5 1 10 6 9 2 5 5 4 2 3 4 9 7 8 4 7 1 3 4 5 3 2 6 5 j i 1 2 3 4 5 1 4 0 3 2 3 3 2 0 3 0 5 3 4 4 6 0 2 3 5 1 0 4 3 j i 1 2 3 4 5 1 4 0 3 2 3 1 2 0 3 0 5 3 4 4 6 0 0 3 5 1 0 2 3 j i 1 2 3 4 5 1 4 0 3 2 3 1 2 0 3 0 5 3 4 4 6 0 0 3 5 1 0 2 3 252 e 1431 P5 P4 3 c25 52 c Z 22634 17 j i 1 2 3 4 5 1 10 6 9 2 5 5 4 2 3 4 9 7 8 4 7 1 3 4 5 3 2 6 5 3 1 5 4 2 3 Começando com k 2 Começando com k 5 P1 P2 P3 c13 c31 P1 P2 131 e 2542 31 c 15 Z Resolução do problema P3 Impomos a restrição c31 ꚙ no Problema de Designação logo a matriz inicial do PD passa ser j i 1 2 3 4 5 1 10 3 6 9 2 5 5 4 2 3 9 7 8 4 7 1 3 4 5 3 2 6 5 j i 1 2 3 4 5 1 7 0 3 6 2 3 3 2 0 3 2 0 1 4 6 0 2 3 5 1 0 4 3 j i 1 2 3 4 5 1 7 0 3 6 2 2 3 2 0 3 2 0 1 4 5 0 2 3 5 0 0 4 3 252 e 1431 P5 P4 4 P3 17 Z j i 1 2 3 4 5 1 7 0 3 6 2 2 3 2 0 3 2 0 1 4 5 0 2 3 5 0 0 4 3 134251 Z 37123 16 j i 1 2 3 4 5 1 10 3 6 9 2 5 5 4 2 3 9 7 8 4 7 1 3 4 5 3 2 6 5 4 1 5 4 2 3 P1 P2 P3 c13 c31 j i 1 2 3 4 5 1 4 0 0 2 1 0 0 3 0 5 3 1 4 6 0 1 0 5 1 0 3 3 j i 1 2 3 4 5 1 4 0 0 2 1 0 0 3 0 5 3 1 4 6 0 1 0 5 1 0 3 3 P1 P2 131 e 2542 25 c 15 Z Resolução do problema P4 Impomos a restrição c25 ꚙ no Problema de Designação P2 logo a matriz inicial do PD passa ser 252 e 1431 16 Z P5 P4 P3 Z 17 134251 145231 j i 1 2 3 4 5 1 10 6 9 2 5 5 4 3 4 9 7 8 4 7 1 3 4 5 3 2 6 5 j i 1 2 3 4 5 1 4 0 3 2 1 1 0 3 0 5 3 4 4 6 0 2 3 5 1 0 4 3 3 2 j i 1 2 3 4 5 1 10 6 9 2 5 5 4 3 4 9 7 8 4 7 1 3 4 5 3 2 6 5 3 2 Z 64254 21 1 5 4 2 3 c13 e c25 13 c Começando com k 2 j i 1 2 3 4 5 1 4 0 3 2 3 1 2 0 3 0 5 3 4 4 6 0 0 3 5 0 1 2 P1 P2 131 e 2542 52 c 15 Z Resolução do problema P5 Impomos a restrição c52 ꚙ no Problema de Designação P2 logo a matriz inicial do PD passa ser 252 e 1431 16 Z P5 P4 P3 Z 17 134251 145231 j i 1 2 3 4 5 1 10 6 9 2 5 5 4 2 3 4 9 7 8 4 7 1 3 4 5 3 6 5 j i 1 2 3 4 5 1 4 0 3 2 3 3 2 0 3 0 5 3 4 4 6 0 2 3 5 0 3 2 3 2 21 Z 142531 j i 1 2 3 4 5 1 4 0 3 2 4 1 2 0 3 0 4 2 3 4 7 0 0 3 5 0 0 1 j i 1 2 3 4 5 1 4 0 3 2 4 1 2 0 3 0 4 2 3 4 7 0 0 3 5 0 0 1 j i 1 2 3 4 5 1 10 6 9 2 5 5 4 2 3 4 9 7 8 4 7 1 3 4 5 3 6 5 3 2 Z 61264 19 1 5 4 2 3 c13 e c52 13 c Começando com k 5 20 P1 P2 131 e 2542 15 Z 252 e 1431 16 Z P5 P4 P3 Z 17 134251 145231 Z 21 19 Z 142531 1 5 4 2 3 Desta linha em diante não seria necessário continuar pois o problema P2 resultou Z17 que já é maior que o resultado de P3 Z 16 então os resultados de Z para P4 e P5 só poderiam resultar maior que 17 e não interessariam ATENÇÃO Neste sentido aumenta o valor de Z nos problemas de minimizar c13 31 c c25 c52 Usando a variante do Método Branch and Bound determine um itinerário ótimo para o Caixeiro Viajante dada a matriz de distâncias mínimas entre os diversos pontos através dos quais ele deve passar 1 2 3 4 5 6 7 8 1 0 76 43 38 51 42 19 80 2 42 0 49 26 78 52 39 87 3 48 28 0 36 53 44 68 61 4 72 31 29 0 42 49 50 38 5 30 52 38 47 0 64 75 82 6 66 51 83 51 22 0 37 71 7 77 62 93 54 69 38 0 26 8 42 58 66 76 41 52 83 0 A resposta para o PD é a seguinte 1 7 8 6 5 1 e 2 4 3 2 Ache a resposta para o PCV Atividade Formativa 7 1º TDE Metodologia Sala de Aula Invertida OBS A realização desta atividade faz parte do processo de ensino e aprendizagem contribuindo em muito com a consolidação deste conhecimento Não é necessária sua entrega e se qualquer dúvida permanecer após o feedback dado nos próximos slides esta deverá ser sanada com o professor nos horários das aulas P1 P2 P6 P5 P3 178243651 254 Z Z 232 178651 2432 P4 P7 P8 P9 23 c 32 c 43 c 17 c 78 c 81 c 24 c 143278651 264 Z 42 c 1781 242 3653 248 Z 1781236542 ou 1427813653 280 Z 1781 246532 165324781 176532481 Z 274 251 Z 178324651 266 Z 1 3 6 5 7 2 4 8 min 251 Z 250 Z OBS Não adianta ramificar pois o valor de Z seria maior que 280 1º Bound candidata a S O 2º Bound candidata a S O 3º Bound candidata a S O 24 c 34 c 42 c 18 c 71 c 87 c Todas combinações começando com k 2 Começando com k 3 Começando com k 4 Começando com k 2 Começando com k 4 Começando com k 1 Começando com k 7 Começando com k 8 Z aumenta 23 Problema 1 P1 178651 2432 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 Software OBS M 25 Problema 2 P2continuação OBS M 26 Problema 2 P2 continuação 143278651 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 OBS M Problema 3 P3 Pesquisa Operacional Atribuição 260315 1304 MATRIZ ORIGINAL MINIMIZAR M 999 M 76 43 38 51 42 19 80 42 M 49 78 52 39 87 48 M M M 53 44 68 61 72 31 29 M 42 49 50 38 30 52 38 47 M 64 75 82 66 51 83 51 22 M 37 71 77 62 93 54 69 38 M 26 42 58 66 76 41 52 83 M SUBTRAINDO MENOR CUSTO DE CADA LINHA M19 57 24 19 32 23 0 61 16 M26 23 0 52 26 13 61 4 M44 M44 M44 9 0 24 17 43 2 0 M29 13 20 21 9 0 22 8 17 M30 34 45 52 44 29 61 29 0 M22 15 49 51 36 67 28 43 12 M26 0 1 17 25 35 0 11 42 M41 SUBTRAINDO O MENOR CUSTO DE CADA COLUNA M19 55 24 19 32 23 0 61 16 M28 23 0 52 26 13 61 4 M46 M44 M44 9 0 24 17 43 0 0 M29 13 20 21 9 0 20 8 17 M30 34 45 52 44 27 61 29 0 M22 15 49 51 34 67 28 43 12 M26 0 1 15 25 35 0 11 42 M41 TRAÇANDO RETAS PARA COBRIR TODOS OS ZEROS M19 55 24 19 32 23 0 61 16 M28 23 0 52 26 13 61 4 M46 M44 M44 9 0 24 17 43 0 0 M29 13 20 21 9 0 20 8 17 M30 34 45 52 44 27 61 29 0 M22 15 49 51 34 67 28 43 12 M26 0 1 15 25 35 0 11 42 M41 OBS M 28 Problema 4 P4 Pesquisa Operacional Atribuição 230815 1821 MATRIZ ORIGINAL MINIMIZAR M 999 M 76 43 38 51 42 19 80 42 M 49 26 78 52 39 87 48 28 M 36 53 44 68 61 72 M M M 42 49 50 38 30 52 38 47 M 64 75 82 66 51 83 51 22 M 37 71 77 62 93 54 69 38 M 26 42 58 66 76 41 52 83 M SUBTRAINDO MENOR CUSTO DE CADA LINHA M19 57 24 19 32 23 0 61 16 0 52 26 13 61 20 0 M36 8 25 16 40 33 34 29 61 29 0 M22 15 49 51 36 67 28 43 12 M26 0 1 17 25 35 0 11 42 M41 SUBTRAINDO O MENOR CUSTO DE CADA COLUNA M19 57 16 19 32 12 0 61 16 M26 15 0 52 15 13 61 20 0 M36 8 25 5 40 33 34 29 0 M38 M46 M38 4 0 12 0 44 29 53 29 0 M33 15 49 51 36 59 28 43 1 M26 0 1 17 35 0 0 42 M41 TRAÇANDO RETAS PARA COBRIR TODOS OS ZEROS M19 57 16 19 32 12 0 61 16 M26 15 0 52 15 13 61 20 0 M36 8 25 5 40 33 34 29 0 M38 M46 M38 4 0 12 0 44 29 53 29 0 M33 15 49 51 36 59 28 43 1 M26 0 1 17 35 0 0 42 M41 OBS M 23 Problema 2 P2 Pesquisa Operacional Atribuição 260315 1257 MATRIZ ORIGINAL MINIMIZAR M 999 M 76 43 38 51 42 19 80 42 M M M 78 52 39 87 48 28 36 53 44 68 61 72 31 29 M 42 49 50 38 30 52 38 47 M 64 75 82 66 51 83 51 22 M 37 71 77 62 93 54 69 38 M 26 42 58 66 76 41 52 83 M SUBTRAINDO MENOR CUSTO DE CADA LINHA M19 57 24 19 32 23 0 61 3 M39 M39 M39 39 13 0 48 20 0 M28 25 16 40 33 43 2 0 M29 13 20 21 9 0 22 8 17 M30 34 45 52 44 29 61 21 0 M33 15 49 51 36 67 20 43 1 M26 0 1 17 25 27 0 42 M41 SUBTRAINDO O MENOR CUSTO DE CADA COLUNA M19 57 24 11 32 12 0 61 3 M39 M39 M39 39 2 0 48 20 0 M28 0 25 5 40 33 43 2 0 M37 13 9 21 9 0 22 8 17 M30 23 45 52 44 29 61 0 M33 15 49 51 36 67 20 43 1 M26 0 1 25 27 0 0 42 M41 TRAÇANDO RETAS PARA COBRIR TODOS OS ZEROS M19 57 24 11 32 12 0 61 3 M39 M39 M39 39 2 0 48 20 0 M28 0 25 5 40 33 43 2 0 M37 13 9 21 9 0 22 8 17 M30 23 45 52 44 29 61 0 M33 15 49 51 36 67 20 43 1 M26 0 1 25 27 0 0 42 M41 OBS M 28 Problema 3 P3 continuação 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1781 242 3653 OBS M 30 Problema 4 P4 continuação 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1781 246532 OBS M Problema 5 P5 Pesquisa Operacional Atribuição 260315 1313 MATRIZ ORIGINAL MINIMIZAR M 999 M 76 43 38 51 42 19 80 42 M 49 M 78 52 39 87 48 M M M 53 44 68 61 72 31 29 M 42 49 50 38 30 52 38 47 M 64 75 82 66 51 83 51 22 M 37 71 77 62 93 54 69 38 M 26 42 58 66 76 41 52 83 M SUBTRAINDO MENOR CUSTO DE CADA LINHA M19 57 24 19 32 23 0 61 3 M39 10 M39 39 13 0 48 4 M44 M44 M44 9 0 24 17 43 2 0 M29 13 20 21 9 0 22 8 17 M30 34 45 52 44 29 61 29 0 M22 15 49 51 36 67 28 43 12 M26 0 1 17 25 35 0 11 42 M41 SUBTRAINDO O MENOR CUSTO DE CADA COLUNA M19 55 24 2 32 23 0 61 3 M41 10 M56 39 13 0 48 4 M46 M44 M61 9 0 24 17 43 0 0 M46 13 20 21 9 0 20 8 0 M30 34 45 52 44 27 61 12 0 M22 15 49 51 34 67 11 43 12 M26 0 1 15 25 18 0 11 42 M41 TRAÇANDO RETAS PARA COBRIR TODOS OS ZEROS OBS M 32 Problema 5 P5 continuação OBS M 33 Problema 5 P5 continuação OBS Duas soluções ótimas possíveis 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1781236542 ou 1427813653 OBS M 34 Problema 6 P6 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 178243651 OBS M Problema 7 P7 Pesquisa Operacional Atribuição 260315 1318 MATRIZ ORIGINAL MINIMIZAR M 999 M 76 43 38 51 42 M M 42 M 49 26 78 52 39 87 48 28 M 36 53 44 68 61 72 M M M 42 49 50 38 30 52 38 47 M 64 75 82 66 51 83 51 22 M 37 71 77 62 93 54 69 38 M 26 42 58 66 76 41 52 83 M SUBTRAINDO MENOR CUSTO DE CADA LINHA M38 38 5 0 13 4 M38 16 M26 23 0 52 26 13 61 20 0 M28 8 25 16 40 33 34 M38 M38 M38 4 11 12 0 0 22 8 17 M30 34 45 52 44 29 61 29 0 M22 15 49 51 36 67 28 43 12 M26 0 1 17 25 35 0 11 42 M41 SUBTRAINDO O MENOR CUSTO DE CADA COLUNA M38 38 0 0 13 0 M50 M38 16 M26 18 0 52 22 1 61 20 0 M33 8 25 12 28 33 34 M38 M43 M38 4 7 0 0 0 22 3 17 M30 30 33 52 44 29 56 29 0 M26 3 49 51 36 62 28 43 8 M38 0 1 17 20 35 0 7 30 M41 TRAÇANDO RETAS PARA COBRIR TODOS OS ZEROS OBS M 36 Problema 7 P7 continuação OBS M 37 Problema 7 P7 continuação 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 165324781 OBS M Problema 8 P8 Pesquisa Operacional Atribuição 260315 1321 MATRIZ ORIGINAL MINIMIZAR M 999 M 76 43 38 51 42 19 80 42 M 49 26 78 52 39 87 48 28 M 36 53 44 68 61 72 M M M 42 49 50 38 30 52 38 47 M 64 75 82 66 51 83 51 22 M 37 71 M 62 93 54 69 38 M M 42 58 66 76 41 52 83 M SUBTRAINDO MENOR CUSTO DE CADA LINHA M19 57 24 19 32 23 0 61 16 M26 23 0 52 26 13 61 20 0 M28 8 25 16 40 33 34 M38 M38 M38 4 11 12 0 0 22 8 17 M30 34 45 52 44 29 61 29 0 M22 15 49 M38 24 55 16 31 0 M38 M38 1 17 25 35 0 11 42 M41 SUBTRAINDO O MENOR CUSTO DE CADA COLUNA M19 57 16 19 32 23 0 61 16 M26 15 0 52 26 13 61 20 0 M36 8 25 16 40 33 34 M38 M46 M38 4 11 12 0 0 22 0 17 M30 34 45 52 44 29 53 29 0 M22 15 49 M38 24 47 16 31 0 M38 M38 1 17 17 35 0 11 42 M41 TRAÇANDO RETAS PARA COBRIR TODOS OS ZEROS OBS M 39 Problema 8 P8 continuação 176532481 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 OBS M Problema 9 P9 Pesquisa Operacional Atribuição 260315 1323 MATRIZ ORIGINAL MINIMIZAR M 999 M 76 43 38 51 42 19 80 42 M 49 26 78 52 39 87 48 28 M 36 53 44 68 61 72 M M M 42 49 50 38 30 52 38 47 M 64 75 82 66 51 83 51 22 M 37 71 77 62 93 54 69 38 M 26 M 58 66 76 41 52 M M SUBTRAINDO MENOR CUSTO DE CADA LINHA M19 57 24 19 32 23 0 61 16 M26 23 0 52 26 13 61 20 0 M28 8 25 16 40 33 34 M38 M38 M38 4 11 12 0 0 22 8 17 M30 34 45 52 44 29 61 29 0 M22 15 49 51 36 67 28 43 12 M26 0 M41 17 25 35 0 11 M41 M41 SUBTRAINDO O MENOR CUSTO DE CADA COLUNA M19 57 16 19 32 12 0 61 16 M26 15 0 52 15 13 61 20 0 M36 8 25 5 40 33 34 M38 M46 M38 4 0 12 0 0 22 0 17 M30 23 45 52 44 29 53 29 0 M33 15 49 51 36 59 28 43 1 M26 0 M41 17 17 35 0 0 M41 M41 TRAÇANDO RETAS PARA COBRIR TODOS OS ZEROS M19 57 16 19 32 12 0 61 16 M26 15 0 52 15 13 61 20 0 M36 8 25 5 40 33 34 M38 M46 M38 4 0 12 0 0 22 0 17 M30 23 45 52 44 29 53 29 0 M33 15 49 51 36 59 28 43 1 M26 0 M41 17 17 35 0 0 M41 M41 OBS M 41 Problema 9 P9 continuação 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 178324651 OBS M Notas de Aula Prof Edgard 1 Arenales M Armentano V Morabito R E Yanasse H Pesquisa Operacional para cursos de Engenharia Editora Campus Rio de Janeiro 2007 2 Bodin L Golden B Assad A and Ball M Routing and Scheduling of veicles and crews Special edition of Computer and Operations Research col 10 n2 1983 3 Bronson R Pesquisa Operacional São Paulo Schaum McGrawHill do Brasil Ltda 1985 4 Goldbarg M C e Luna H P Otimização Combinatória e Programação Linear Modelos e Algoritmos Editora Campus Rio de Janeiro 2000 5 Hillier F S e Lieberman G J Introdução à Pesquisa Operacional traduzido McGrawHill São Paulo 2006 6 Murty K Linear and Combinatorial Programming Robert E Krieger Publishing Company Malabar Florida 1985 7 Puccini A de L e Pizzolato N D Programação Linear Livros Técnicos e Científicos Ed Ltda Rio de Janeiro 1990 Importante Este material tem finalidade única e exclusivamente didática e serve apenas como notas de apoio às aulas da disciplina de Métodos Quantitativos para Tomada de Decisão do curso de Graduação de Engenharia de Produção Este material não pode ser utilizado como referência bibliográfica e muito menos comercialmente Recomendase consultar as seguintes obras