Método Húngaro para Otimização de Designações - Guia Passo a Passo

SISTEMA DE TRANSPORTE MÉTODO HÚNGARO 1 Redução de linhas subtraia o menor número em cada linha de cada um dos números da linha Inclua os resultados em uma nova tabela Cortar Pintar Lavar John 15 10 9 Kare n 9 15 10 Terri 10 12 8 Corta r Pintar Lavar John 6 1 0 Karen 0 6 1 Terri 2 4 0 MÉTODO HÚNGARO 2 Redução de colunas subtraia o menor número em cada coluna da nova tabela de cada um dos números da coluna Inclua os resultados em uma nova tabela Corta r Pintar Lavar John 6 1 0 Karen 0 6 1 Terri 2 4 0 Cortar Pintar Lavar John 6 0 0 Karen 0 5 1 Terri 2 3 0 MÉTODO HÚNGARO Essa tabela de custos tem todos os elementos zero necessários para um conjunto completo de designações Dessa maneira essas três designações constituem uma solução ótima Assim John pintará a porta da garagem Karen cortará a grama e Terri lavará os carros O custo total é 9 10 8 27 Infelizmente uma solução ótima nem sempre é obtida tão facilmente podendo ser necessárias mais etapas para achar a designação ótima Cortar Pintar Lavar John 6 0 0 Karen 0 5 1 Terri 2 3 0 MÉTODO HÚNGARO Suponha que a situação do problemaprotótipo seja estendida para 4 empregados e 4 tarefas com os seguintes custos 1 2 3 4 1 1 4 6 3 2 9 7 10 9 3 4 5 11 7 4 8 7 8 5 MÉTODO HÚNGARO 1 2 3 4 1 1 4 6 3 2 9 7 10 9 3 4 5 11 7 4 8 7 8 5 1 2 3 4 1 0 3 5 2 2 2 0 3 2 3 0 1 7 3 4 3 2 3 0 MÉTODO HÚNGARO 1 2 3 4 1 0 3 2 2 2 2 0 0 2 3 0 1 4 3 4 3 2 0 0 MÉTODO HÚNGARO A aplicação das etapas 1 e 2 redução de linhas e colunas à nova tabela de custos problemaprotótipo estendido dá como resultado a tabela abaixo 1 2 3 4 1 0 3 5 2 2 2 0 3 2 3 0 1 7 3 4 3 2 3 0 MÉTODO HÚNGARO 3 Teste se é possível fazer um conjunto de designações ótimas Isso é feito determinandose o número mínimo de traços necessários para cruzar todos os zeros Se o número mínimo de de traços for igual ao número de linhas é possível termos um conjunto de designações ótimo Nesse caso vá para a etapa 6 caso contrário prossiga na etapa 4 1 2 3 4 1 0 3 2 2 2 2 0 0 2 3 0 1 4 3 4 3 2 0 0 MÉTODO HÚNGARO 4 Se o número de traços for menor que o de linhas modifique a tabela da seguinte maneira a Subtraia o menor número descoberto de cada um dos números descobertos da tabela neste ex 1 b Adicione o menor número descoberto aos números que se encontram nas interseções dos traços c Números que foram eliminados mas não se encontram nas interseções de traços eliminados são transferidos sem alteração para a próxima tabela 1 2 3 4 1 0 2 1 1 2 3 0 0 2 3 0 0 3 2 4 4 2 0 0 MÉTODO HÚNGARO 5 Repita as etapas 3 e 4 até se tornar possível um conjunto ótimo de designações 1 2 3 4 1 0 2 1 1 2 3 0 0 2 3 0 0 3 2 4 4 2 0 0 MÉTODO HÚNGARO 6 Faça as designações uma de cada vez nas posições contendo elementos zero Comece com linhas e colunas que tenham apenas um zero Já que cada linha e coluna precisam receber exatamente uma designação risque tanto a linha quanto a coluna envolvidas após cada designação ter sido feita A seguir prossiga nas linhas e colunas que ainda não foram riscadas para selecionar a próxima designação Continue até todas as linhas e colunas terem exatamente uma designação e portanto terem sido cruzadas O conjunto completo de designações feito dessa forma é uma solução ótima para o problema 1 2 3 4 1 0 2 1 1 2 3 0 0 2 3 0 0 3 2 4 4 2 0 0 Custo total Z 15105 21 Origem D1 D2 D3 O1 1 3 0 O2 0 5 4 O3 0 6 4 1 REGRA 2 REGRA Origem D1 D2 D3 O1 1 0 0 O2 0 2 4 O3 0 3 4 REGRA DOS TRAÇOS Origem D1 D2 D3 O1 1 0 0 O2 0 2 4 O3 0 3 4 Origem D1 D2 D3 O1 1 0 0 O2 0 0 2 O3 0 1 2 Z 9 9 6 24