Notas de Aula - Algoritmo Húngaro e Problema de Designacao

Notas de Aula da Disciplina de Métodos Quantitativos para Tomada de Decisão Prof Edgard Pedroso Arquivo de aulas n o 01b Matriz de designação algoritmo Húngaro BREVE REVISÃO Capacidade de Demanda Problema de Designação The Assignment Problem Breve Revisão Possíveis designações pares de projetistas p clientes Ex de uma designação ótima correspondência 1 a 1 Zmin 26 dias OBS O motivo para esta revisão é o de que este conteúdo é prérequisito para o etendimento de assuntos que serão abordados mais adiante nesta disciplina Tempo de conclusão em dias João Pedro Paula João Pedro Paula Cliente 1 Cliente 2 Cliente 3 Cliente 1 Cliente 2 Cliente 3 Clientes Projetistas Clientes Projetistas 1 2 3 1 1 1 1 1 1 1 1 1 1 1 1 Capacidade de Oferta Exemplo de Referência Programação Inteira Binária Dados um conjunto de 4 máquinas e 4 tarefas e os custos de designações de cada máquina para cada tarefa determinar uma designação que minimize o custo total de alocação das máquinas Observe que cada máquina só poderá realizar uma única tarefa e viceversa cada tarefa só poderá ser realizada por uma única máquina i j Tarefa 1 Tarefa 2 Tarefa 3 Tarefa 4 Ofertas Máq 1 94 1 54 68 1 Máq 2 74 10 88 82 1 Máq 3 62 88 8 76 1 Máq 4 11 74 81 21 1 Demandas 1 1 1 1 4 Capacidade ai de oferta em cada nó Capacidade bj de demanda em cada nó Origens Oi Máquinas Destinos Dj Tarefas c12 c11 c13 c14 c22 c21 c23 c24 c32 c31 c33 c34 c42 c41 c43 c44 1 X 0 X X ij ij ij designação usada Esta é usada designação Esta 10 é não Modelo Matemático 01 X 1 x x x x 1 x x x x 1 x x x x 1 x x x x 1 x x x x 1 x x x x 1 x x x x 1 x x x x sa 21x 81x 74x 11x 76x 8x 88x 62x 82x 88x 10x 74x 68x 54x 1x 94x Z min ij 44 34 24 14 43 33 23 13 42 32 22 12 41 31 21 11 44 43 42 41 34 33 32 31 24 23 22 21 14 13 12 11 44 43 42 41 34 33 32 31 24 23 22 21 14 13 12 11 i j Tarefa 1 Tarefa 2 Tarefa 3 Tarefa 4 Ofertas Máq 1 94 1 54 68 1 Máq 2 74 10 88 82 1 Máq 3 62 88 8 76 1 Máq 4 11 74 81 21 1 Demandas 1 1 1 1 4 variável binária CLINDOSAMPLESDESIG2LTX MIN 94x11 1x12 54x13 68x14 74x21 10x22 88x23 82x24 62x31 88x32 8x33 76x34 11x41 74x42 81x43 21x44 SUBJECT TO x11 x12 x13 x14 1 x21 x22 x23 x24 1 x31 x32 x33 x34 1 x41 x42 x43 x44 1 x11 x21 x31 x41 1 x12 x22 x32 x42 1 x13 x23 x33 x43 1 x14 x24 x34 x44 1 END Reports Window LP OPTIMUM FOUND AT STEP 7 OBJECTIVE FUNCTION VALUE 1 9700000 VARIABLE VALUE REDUCED COST X11 0000000 36000000 X12 0000000 0000000 X13 0000000 50000000 X14 1000000 0000000 X21 0000000 7000000 X22 1000000 0000000 X23 0000000 75000000 X24 0000000 5000000 X31 0000000 0000000 X32 0000000 83000000 X33 1000000 0000000 X34 0000000 4000000 X41 1000000 0000000 X42 0000000 120000000 X43 0000000 124000000 X44 0000000 0000000 Diagrama da solução ótima a11 O1 68 D1 b11 a21 O2 10 D2 b21 a31 O3 8 D3 b31 a41 O4 11 D4 b41 Nós de Oferta Nós de Demanda Software LINDO Algoritmo do Problema de Designação O problema de designação é resolvido determinandose como as designações devem ser feitas de forma a minimizar o custo total As características particulares do sistema AX b do modelo de designação permitem o uso de um algoritmo específico para sua solução Matriz de custos ou de eficiência O problema consiste em determinar um único elemento em cada linha e em cada coluna da matriz de custos de forma que a soma desses custos seja a menor possível caso de minimização mais comum n n j i 1 2 n 1 c11 c12 c1n 2 c21 c22 c2n n cn1 cn2 cnn Destinos Origens Algoritmo de Designação ou Método Húngaro MatemáticosHúngarosDénesKönigeJenõEgerváry Problema de designação CasodeMinimização 1Coloqueoscustosporunidadederecursonaformadematrizmatrizdeeficiência 2Subtraiaomenorcustodecadalinhaeoucolunatalqueexistanomínimoumzeroemcadalinhaeemcadacoluna 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 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 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 7 Obtenha na matriz reduzida encontrada no mínimo mais um 0 como segue 71 Ache o menor valor não riscado por um traço 72 Subtraia este valor de todas as linhas marcadas 73 Adicione este valor a todas as colunas marcadas 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 72 e 73 Subtraia o menor dos não riscados e ou some nas intersecções Exemplo de Referência Dado uma conjunto de 4 máquinas e 4 tarefas e os custos de designações de cada tarefa para cada máquina determinar uma designação que minimize o custo total de alocação das tarefas Observe que cada máquina só poderá realizar uma única tarefa e viceversa cada tarefa só poderá ser realizada por uma única máquina j i 1 2 3 4 1 94 1 54 68 2 74 10 88 82 3 62 88 8 76 4 11 74 81 21 i j Tarefa 1 Tarefa 2 Tarefa 3 Tarefa 4 Ofertas Máq 1 94 1 54 68 1 Máq 2 74 10 88 82 1 Máq 3 62 88 8 76 1 Máq 4 11 74 81 21 1 Demandas 1 1 1 1 4 Matriz de custos j i 1 2 3 4 1 94 1 54 68 2 74 10 88 82 3 62 88 8 76 4 11 74 81 21 j i 1 2 3 4 1 94 1 54 68 2 74 10 88 82 3 62 88 8 76 4 11 74 81 21 j i 1 2 3 4 1 93 0 53 67 2 64 0 78 72 3 54 80 0 68 4 0 63 70 10 j i 1 2 3 4 1 93 0 53 67 2 64 0 78 72 3 54 80 0 68 4 0 63 70 10 j i 1 2 3 4 1 93 0 53 57 2 64 0 78 62 3 54 80 0 58 4 0 63 70 0 linha coluna 2 Subtraia o menor custo de cada linha eou coluna tal que exista no mínimo um zero em cada linha e em cada coluna j i 1 2 3 4 1 93 0 53 57 2 64 0 78 62 3 54 80 0 58 4 0 63 70 0 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 4 Não existe um 0 designado em cada linha e coluna Segue para o passo 5 j i 1 2 3 4 1 93 0 53 57 2 64 0 78 62 3 54 80 0 58 4 0 63 70 0 j i 1 2 3 4 1 93 0 53 57 2 64 0 78 62 3 54 80 0 58 4 0 63 70 0 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 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 1 O no de traços no de 0s designados 2 Todos os 0s designados ou eliminados estão riscados com um traço SIM SIM j i 1 2 3 4 1 93 0 53 57 2 64 0 78 62 3 54 80 0 58 4 0 63 70 0 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 j i 1 2 3 4 1 93 0 53 57 2 64 0 78 62 3 54 80 0 58 4 0 63 70 0 j i 1 2 3 4 1 40 53 0 4 2 11 53 25 9 3 54 80 0 58 4 0 63 70 0 j i 1 2 3 4 1 40 0 0 4 2 11 0 25 9 3 54 133 0 58 4 0 116 70 0 7 Obtenha na matriz reduzida encontrada no mínimo mais um 0 como segue 71 Ache o menor valor não riscado por um traço 72 Subtraia este valor de todas as linhas marcadas 73 Adicione este valor a todas as colunas marcadas ou 72 e 73 Subtraia o menor dos não riscados e some nas intersecções dos riscos j i 1 2 3 4 1 40 0 0 4 2 11 0 25 9 3 54 133 0 58 4 0 116 70 0 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 Não existe um 0 designado em cada linha e coluna Segue para o passo 5 j i 1 2 3 4 1 40 0 0 4 2 11 0 25 9 3 54 133 0 58 4 0 116 70 0 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 j i 1 2 3 4 1 40 0 0 4 2 11 0 25 9 3 54 133 0 58 4 0 116 70 0 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 j i 1 2 3 4 1 40 0 0 4 2 11 0 25 9 3 54 133 0 58 4 0 116 70 0 j i 1 2 3 4 1 36 4 4 0 2 7 4 21 5 3 50 129 4 54 4 0 116 70 0 j i 1 2 3 4 1 36 0 0 0 2 7 0 25 5 3 50 133 0 54 4 0 120 74 0 7 Obtenha na matriz reduzida encontrada no mínimo mais um 0 como segue 71 Ache o menor valor não riscado por um traço 72 Subtraia este valor de todas as linhas marcadas 73 Adicione este valor a todas as colunas marcadas ou 72 e 73 Subtraia o menor dos não riscados e some nas intersecções dos riscos 4Existe um único 0 designado em cada linha e coluna FIM j i 1 2 3 4 1 36 0 0 0 2 7 0 25 5 3 50 133 0 54 4 0 120 74 0 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 Tarefa 1 Tarefa 2 Tarefa 3 Tarefa 4 Ofertas Máq 1 94 1 54 68 1 Máq 2 74 10 88 82 1 Máq 3 62 88 8 76 1 Máq 4 11 74 81 21 1 Demandas 1 1 1 1 4 97 11 8 10 68 min 41 33 22 14 min Z c c c c Z 1 2 3 4 2 3 4 1 Nós de Oferta Nós de Demanda 0 0 0 1 0 1 0 0 0 0 1 0 1 0 0 0 44 43 42 41 34 33 32 31 24 23 22 21 14 13 12 11 x x x x x x x x x x x x x x x x X j i 1 2 3 4 1 36 0 0 0 2 7 0 25 5 3 50 133 0 54 4 0 120 74 0 Tarefas Técnicos 1 2 3 4 5 6 7 8 1 76 43 38 51 42 19 80 2 42 49 78 52 39 87 3 48 53 44 68 61 4 72 31 29 42 49 50 38 5 30 52 38 47 64 75 82 6 66 51 83 51 22 37 71 7 77 62 93 54 69 38 26 8 42 58 66 76 41 52 83 Outro Exemplo de Referência Oito trabalhadores devem ser designados para executar oito diferentes tipos de tarefas Na tabela abaixo são apresentados os tempos médios em minutos de execução de cada tarefa por cada trabalhador considere que se um determinado trabalhador não sabe executar uma determinada tarefa então o tempo considerado foi infinito O objetivo é designar os trabalhadores para as tarefas de tal forma que o tempo total de realização de todas as tarefas seja minimizado 1 2 3 4 5 6 7 8 1 76 43 38 51 42 19 80 2 42 49 78 52 39 87 3 48 53 44 68 61 4 72 31 29 42 49 50 38 5 30 52 38 47 64 75 82 6 66 51 83 51 22 37 71 7 77 62 93 54 69 38 26 8 42 58 66 76 41 52 83 1 2 3 4 5 6 7 8 1 57 26 19 32 23 0 61 2 3 10 39 13 0 48 3 4 9 0 24 17 4 43 2 0 13 20 21 9 5 0 22 8 17 34 45 52 6 44 29 61 29 0 15 49 7 51 36 67 28 43 12 0 8 1 17 25 35 0 11 42 1Coloqueoscustosporunidadederecursonaformadematrizmatrizdeeficiência 2Subtraiaomenorcustodecadalinhaeoucolunatalqueexistanomínimoumzeroemcadalinhae emcadacoluna 1 2 3 4 5 6 7 8 1 57 26 19 32 23 0 61 2 3 10 39 13 0 48 3 4 9 0 24 17 4 43 2 0 13 20 21 9 5 0 22 8 17 34 45 52 6 44 29 61 29 0 15 49 7 51 36 67 28 43 12 0 8 1 17 25 35 0 11 42 1 2 3 4 5 6 7 8 1 55 26 2 32 23 0 61 2 3 10 39 13 0 48 3 4 9 0 24 17 4 43 0 0 13 20 21 9 5 0 20 8 0 34 45 52 6 44 27 61 12 0 15 49 7 51 34 67 11 43 12 0 8 1 15 25 18 0 11 42 Cópia da última tabela 2Subtraiaomenorcustodecadalinhaeoucolunatalqueexistanomínimoumzeroemcadalinhae emcadacoluna 1 2 3 4 5 6 7 8 1 55 26 2 32 23 0 61 2 3 10 39 13 0 48 3 4 9 0 24 17 4 43 0 0 13 20 21 9 5 0 20 8 0 34 45 52 6 44 27 61 12 0 15 49 7 51 34 67 11 43 12 0 8 1 15 25 18 0 11 42 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 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 1 2 3 4 5 6 7 8 1 55 26 2 32 23 0 61 2 3 10 39 13 0 48 3 4 9 0 24 17 4 43 0 0 13 20 21 9 5 0 20 8 0 34 45 52 6 44 27 61 12 0 15 49 7 51 34 67 11 43 12 0 8 1 15 25 18 0 11 42 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 1 se o número de traços número de 0s designados 2 se todos 0s designados ou eliminados têm um traço SIM SIM 1 2 3 4 5 6 7 8 1 55 26 2 32 23 0 61 2 3 10 39 13 0 48 3 4 9 0 24 17 4 43 0 0 13 20 21 9 5 0 20 8 0 34 45 52 6 44 27 61 12 0 15 49 7 51 34 67 11 43 12 0 8 1 15 25 18 0 11 42 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 2 3 4 5 6 7 8 1 55 26 2 32 23 0 61 2 3 10 39 13 0 48 3 4 9 0 24 17 4 43 0 0 13 20 21 9 5 0 20 8 0 34 45 52 6 44 27 61 12 0 15 49 7 51 34 67 11 43 12 0 8 1 15 25 18 0 11 42 1 2 3 4 5 6 7 8 1 54 25 1 32 22 0 60 2 2 9 39 12 0 47 3 4 10 0 25 17 4 43 0 0 14 20 22 9 5 0 20 8 0 34 46 52 6 43 26 60 11 0 15 48 7 51 34 67 11 44 12 0 8 0 14 24 17 0 10 42 Cópia da última tabela 7 Obtenha na matriz reduzida encontrada no mínimo mais um 0 como segue 71 Ache o menor valor não riscado por um traço 72 Subtraia este valor de todas as linhas marcadas 73 Adicione este valor a todas as colunas marcadas ou 72 e 73 Subtraia o menor dos não riscados e some nas intersecções dos riscos 1 2 3 4 5 6 7 8 1 54 25 1 32 22 0 60 2 2 9 39 12 0 47 3 4 10 0 25 17 4 43 0 0 14 20 22 9 5 0 20 8 0 34 46 52 6 43 26 60 11 0 15 48 7 51 34 67 11 44 12 0 8 0 14 24 17 0 10 42 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 Não existe um 0 designado em cada linha e coluna Segue para o passo 5 1 2 3 4 5 6 7 8 1 54 25 1 32 22 0 60 2 2 9 39 12 0 47 3 4 10 0 25 17 4 43 0 0 14 20 22 9 5 0 20 8 0 34 46 52 6 43 26 60 11 0 15 48 7 51 34 67 11 44 12 0 8 0 14 24 17 0 10 42 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 1 2 3 4 5 6 7 8 1 54 25 1 32 22 0 60 2 2 9 39 12 0 47 3 4 10 0 25 17 4 43 0 0 14 20 22 9 5 0 20 8 0 34 46 52 6 43 26 60 11 0 15 48 7 51 34 67 11 44 12 0 8 0 14 24 17 0 10 42 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 número de traços número de 0s designados 2 se todos 0s designados ou eliminados têm um traço SIM SIM 1 2 3 4 5 6 7 8 1 54 25 1 32 22 0 60 2 2 9 39 12 0 47 3 4 10 0 25 17 4 43 0 0 14 20 22 9 5 0 20 8 0 34 46 52 6 43 26 60 11 0 15 48 7 51 34 67 11 44 12 0 8 0 14 24 17 0 10 42 1 2 3 4 5 6 7 8 1 53 24 0 31 21 0 59 2 1 8 38 11 0 46 3 4 10 0 26 17 4 43 0 0 14 20 23 9 5 0 20 8 0 34 47 52 6 43 26 60 11 0 16 48 7 51 34 67 11 44 12 0 8 0 14 24 17 0 10 43 Cópia da última tabela 7 Obtenha na matriz reduzida encontrada no mínimo mais um 0 como segue 71 Ache o menor valor não riscado por um traço 72 Subtraia este valor de todas as linhas marcadas 73 Adicione este valor a todas as colunas marcadas ou 72 e 73 Subtraia o menor dos não riscados e some nas intersecções dos riscos 1 2 3 4 5 6 7 8 1 53 24 0 31 21 0 59 2 1 8 38 11 0 46 3 4 10 0 26 17 4 43 0 0 14 20 23 9 5 0 20 8 0 34 47 52 6 43 26 60 11 0 16 48 7 51 34 67 11 44 12 0 8 0 14 24 17 0 10 43 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 Não existe um 0 designado em cada linha e coluna Segue para o passo 5 1 2 3 4 5 6 7 8 1 53 24 0 31 21 0 59 2 1 8 38 11 0 46 3 4 10 0 26 17 4 43 0 0 14 20 23 9 5 0 20 8 0 34 47 52 6 43 26 60 11 0 16 48 7 51 34 67 11 44 12 0 8 0 14 24 17 0 10 43 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 1 2 3 4 5 6 7 8 1 53 24 0 31 21 0 59 2 1 8 38 11 0 46 3 4 10 0 26 17 4 43 0 0 14 20 23 9 5 0 20 8 0 34 47 52 6 43 26 60 11 0 16 48 7 51 34 67 11 44 12 0 8 0 14 24 17 0 10 43 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 número de traços número de 0s designados 2 se todos 0s designados ou eliminados têm um traço SIM SIM 1 2 3 4 5 6 7 8 1 53 24 0 31 21 0 59 2 1 8 38 11 0 46 3 4 10 0 26 17 4 43 0 0 14 20 23 9 5 0 20 8 0 34 47 52 6 43 26 60 11 0 16 48 7 51 34 67 11 44 12 0 8 0 14 24 17 0 10 43 1 2 3 4 5 6 7 8 1 45 16 0 31 13 0 51 2 1 0 38 3 0 38 3 12 18 0 34 17 4 51 0 0 22 20 31 9 5 0 12 0 0 26 47 44 6 43 18 52 11 0 16 40 7 59 34 67 19 52 12 0 8 0 6 16 17 0 2 43 Cópia da última tabela 7 Obtenha na matriz reduzida encontrada no mínimo mais um 0 como segue 71 Ache o menor valor não riscado por um traço 72 Subtraia este valor de todas as linhas marcadas 73 Adicione este valor a todas as colunas marcadas ou 72 e 73 Subtraia o menor dos não riscados e some nas intersecções dos riscos Existe um 0 designado em cada linha e coluna FIM Obs No passo 3 se todas as linhas e colunas com um único 0 acabaram e somente linhas e colunas com dois ou mais 0s permanecem significa que existe mais de uma designação mínima para estas linhas e colunas Qualquer um desses 0s pode ser designado para produzir o mesmo custo mínimo total Neste caso as soluções alternativas devem ser registradas 1 2 3 4 5 6 7 8 1 45 16 0 31 13 0 51 2 1 0 38 3 0 38 3 12 18 0 34 17 4 51 0 0 22 20 31 9 5 0 12 0 0 26 47 44 6 43 18 52 11 0 16 40 7 59 34 67 19 52 12 0 8 0 6 16 17 0 2 43 1 2 3 4 5 6 7 8 1 45 16 0 31 13 0 51 2 1 0 38 3 0 38 3 12 18 0 34 17 4 51 0 0 22 20 31 9 5 0 12 0 0 26 47 44 6 43 18 52 11 0 16 40 7 59 34 67 19 52 12 0 8 0 6 16 17 0 2 43 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 1 2 3 4 5 6 7 8 1 76 43 38 51 42 19 80 2 42 49 78 52 39 87 3 48 53 44 68 61 4 72 31 29 42 49 50 38 5 30 52 38 47 64 75 82 6 66 51 83 51 22 37 71 7 77 62 93 54 69 38 26 8 42 58 66 76 41 52 83 280 42 26 22 38 31 44 39 38 min 81 78 65 53 42 36 27 14 min Z c c c c c c c c Z 280 42 26 22 47 31 44 49 19 min 81 78 65 54 42 36 23 17 min Z c c c c c c c c Z 1 2 3 4 5 6 7 8 1 45 16 0 31 13 0 51 2 1 0 38 3 0 38 3 12 18 0 34 17 4 51 0 0 22 20 31 9 5 0 12 0 0 26 47 44 6 43 18 52 11 0 16 40 7 59 34 67 19 52 12 0 8 0 6 16 17 0 2 43 1 2 3 4 5 6 7 8 1 45 16 0 31 13 0 51 2 1 0 38 3 0 38 3 12 18 0 34 17 4 51 0 0 22 20 31 9 5 0 12 0 0 26 47 44 6 43 18 52 11 0 16 40 7 59 34 67 19 52 12 0 8 0 6 16 17 0 2 43 1 2 3 4 5 6 7 8 1 76 43 38 51 42 19 80 2 42 49 78 52 39 87 3 48 53 44 68 61 4 72 31 29 42 49 50 38 5 30 52 38 47 64 75 82 6 66 51 83 51 22 37 71 7 77 62 93 54 69 38 26 8 42 58 66 76 41 52 83 X11 0 X12 0 X13 0 X14 1 X15 0 X16 0 X17 0 X18 0 X21 0 X22 0 X23 0 X24 0 X25 0 X26 0 X27 1 X28 0 X31 0 X32 0 X33 0 X34 0 X35 0 X36 1 X37 0 X38 0 X41 0 X42 1 X43 0 X44 0 X45 0 X46 0 X47 0 X48 0 X51 0 X52 0 X53 1 X54 0 X55 0 X56 0 X57 0 X58 0 X61 0 X62 0 X63 0 X64 0 X65 1 X66 0 X67 0 X68 0 X71 0 X72 0 X73 0 X74 0 X75 0 X76 0 X77 0 X78 1 X81 1 X82 0 X83 0 X84 0 X85 0 X86 0 X87 0 X88 0 X11 0 X12 0 X13 0 X14 0 X15 0 X16 0 X17 1 X18 0 X21 0 X22 0 X23 1 X24 0 X25 0 X26 0 X27 0 X28 0 X31 0 X32 0 X33 0 X34 0 X35 0 X36 1 X37 0 X38 0 X41 0 X42 1 X43 0 X44 0 X45 0 X46 0 X47 0 X48 0 X51 0 X52 0 X53 0 X54 1 X55 0 X56 0 X57 0 X58 0 X61 0 X62 0 X63 0 X64 0 X65 1 X66 0 X67 0 X68 0 X71 0 X72 0 X73 0 X74 0 X75 0 X76 0 X77 0 X78 1 X81 1 X82 0 X83 0 X84 0 X85 0 X86 0 X87 0 X88 0 1 2 3 4 5 6 7 8 1 76 43 38 51 42 19 80 2 42 49 78 52 39 87 3 48 53 44 68 61 4 72 31 29 42 49 50 38 5 30 52 38 47 64 75 82 6 66 51 83 51 22 37 71 7 77 62 93 54 69 38 26 8 42 58 66 76 41 52 83 280 42 26 22 38 31 44 39 38 min 81 78 65 53 42 36 27 14 min Z c c c c c c c c Z 280 42 26 22 47 31 44 49 19 min 81 78 65 54 42 36 23 17 min Z c c c c c c c c Z 1 2 3 4 5 6 7 8 1 76 43 38 51 42 19 80 2 42 49 78 52 39 87 3 48 53 44 68 61 4 72 31 29 42 49 50 38 5 30 52 38 47 64 75 82 6 66 51 83 51 22 37 71 7 77 62 93 54 69 38 26 8 42 58 66 76 41 52 83 OBS Obtivemos pelo Lingo apenas uma das soluções ótimas LINGO Solver Status LINGO1 Solver Status Model Class LP State Unknown Objective 0 Infeasibility 0 Iterations 0 Extended Solver Status Solver Type Best Obj Obj Bound Steps Active Update Interval 2 Variables Total 64 Nonlinear 0 Integers 0 Constraints Total 17 Nonlinear 0 Nonzeros Total 192 Nonlinear 0 Generator Memory Used K 31 Elapsed Runtime hhmmss 000000 Demo LINGO Release 100 9 May 07 Copyright 2006 LINDO Systems Inc 1415 North Dayton Street Chicago IL 60622 3129887422 httpwwwlindocom Limits for this Installation Constraints 150 Variables 300 Integer Variables 30 Nonlinear Variables 30 Global Variables 5 Generator Memory Mb 32 Uma companhia de aluguel de carros tem um único carro em cada uma de cinco lojasi de locação em locais distantes entre si quais sejam 1234 e 5 Cinco clientes em cidadesj diferentes 1234 e 5 demandam um carro cada um As distâncias entre as lojas e as cidades onde os clientes estão são dadas na tabela a seguir Como os carros serão designados para os clientes a fim de minimizar a distância viajada Clientes j Lojas i 1 2 3 4 5 Ofertas 1 160 130 175 190 200 1 2 135 120 130 160 175 1 3 140 110 155 170 185 1 4 50 50 80 80 110 1 5 55 35 70 80 105 1 Demandas 1 1 1 1 1 5 Atividade Prática Formativa em Grupo No 2 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 no próximo slide esta deverá ser sanada com o professor nos horários das aulas VERIFICANDO SE A SOLUÇÃO É ÓTIMA MARCANDO LINHAS E COLUNAS RISCANDO AS LIN Ñ MARC E COL MARC LOCALIZANDO O MENOR Ñ RISCADO SUBTRAI O MENOR DOS Ñ RISCADOS E SOMA NAS INTERSECÇÕES VERIFICANDO SE A SOLUÇÃO É ÓTIMA 1 2 3 4 2 3 4 1 Nós de Oferta Nós de Demanda 5 5 570 80 50 130 110 200 min min Z Z LP OPTIMUM FOUND AT STEP 18 OBJECTIVE FUNCTION VALUE 1 5700000 VARIABLE VALUE REDUCED COST X11 0000000 5000000 X12 0000000 5000000 X13 0000000 5000000 X14 0000000 5000000 X15 1000000 0000000 X21 0000000 20000000 X22 0000000 35000000 X23 1000000 0000000 X24 0000000 15000000 X25 0000000 15000000 X31 0000000 0000000 X32 1000000 0000000 X33 0000000 0000000 X34 0000000 0000000 X35 0000000 0000000 X41 1000000 0000000 X42 0000000 30000000 X43 0000000 15000000 X44 0000000 0000000 X45 0000000 15000000 X51 0000000 5000000 X52 0000000 15000000 X53 0000000 5000000 X54 1000000 0000000 X55 0000000 10000000 Feedback da Atividade Formativa 2 1º TDE Software LINDO 1 2 3 4 2 3 4 1 Nós de Oferta Nós de Demanda 5 5 570 80 50 130 110 200 min min Z Z 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