Introdução Alocação de Tarefas Método Húngaro Introdução Alocação de Tarefas Método Húngaro Roteiro Método Húngaro 1. Introdução Prof. Dr. Leandro Balby Marinho 2. Problema de Alocação de Tarefas 2. Método Húngaro Análise e Técnicas de Algoritmos Prof. Dr. Leandro Balby Marinho Introdução 1 / 26 Alocação de Tarefas UFCG CEEI Método Húngaro Introdução Prof. Dr. Leandro Balby Marinho Introdução 2 / 26 Alocação de Tarefas UFCG CEEI Método Húngaro Roteiro 1. Introdução I Adequado a problemas de otimização Combinatória. I Resolve o problema da alocação em tempo polinomial (normalmente O(n3 )). I Origem: E. Egerváry e D. König (1931) I Criador: H. Kuhn (1955) 2. Problema de Alocação de Tarefas 2. Método Húngaro Prof. Dr. Leandro Balby Marinho 2 / 26 UFCG CEEI Prof. Dr. Leandro Balby Marinho 3 / 26 UFCG CEEI Introdução Alocação de Tarefas Método Húngaro Problema de Alocação de Tarefas Introdução Alocação de Tarefas Método Húngaro Roteiro I Alocar n agentes para n tarefas tal que o custo total de alocação seja o menor possı́vel. I Instâncias do problema podem ser especificadas por uma matriz de custo C ∈ Rn×n : c1,1 c1,2 · · · c1,n c2,1 c2,2 · · · c2,n C = . .. .. .. .. . . . cn,1 cn,2 · · · cn,n 1. Introdução 2. Problema de Alocação de Tarefas 2. Método Húngaro onde ci,j representa o custo de alocar o agente i para realizar a tarefa j. Prof. Dr. Leandro Balby Marinho Introdução 3 / 26 Alocação de Tarefas UFCG CEEI Método Húngaro Teorema da Alocação Ótima Prof. Dr. Leandro Balby Marinho Introdução 4 / 26 Alocação de Tarefas UFCG CEEI Método Húngaro Exemplo 1 Uma solução ótima para a matriz abaixo seria: c1,2 , c2,1 e c3,3 900 C = 350 1250 Teorema 1 Se um número real é somado ou subtraı́do de todas as entradas de uma linha ou coluna, então uma alocação ótima para a matriz resultante é também uma alocação ótima para a matriz original. Ao diminuir as linhas e colunas, estamos comparando-as com valores relativos. Subtraindo a menor entrada de cada 150 C = 0 350 750 750 850 550 950 900 linha temos: 0 0 500 200 50 0 Note que a solução ótima continua a mesma e é representada pelas entradas com custo 0. Prof. Dr. Leandro Balby Marinho 4 / 26 UFCG CEEI Prof. Dr. Leandro Balby Marinho 5 / 26 UFCG CEEI Introdução Alocação de Tarefas Método Húngaro Teorema de König Introdução Alocação de Tarefas Método Húngaro Algoritmo 1. Para cada linha, subtraia o mı́nimo da linha. Teorema 2 2. Para cada coluna, subtraia o mı́nimo da coluna. Se o número mı́nimo de traços que atravessam todos os zeros for n, temos uma alocação possı́vel para cada linha/coluna. 150 0 500 C = 0 350 50 Prof. Dr. Leandro Balby Marinho Introdução 3. Use o mı́nimo de traços possı́veis para cobrir todos os zeros da matriz. Não há receita de bolo para isso – basicamente tentativa e erro. Se você usou k traços: I 0 200 0 6 / 26 I UFCG CEEI Alocação de Tarefas Método Húngaro Exemplo 1 cont. Prof. Dr. Leandro Balby Marinho Introdução 7 / 26 Alocação de Tarefas UFCG CEEI Método Húngaro Exemplo 1 cont. Passo 1: Para cada linha, subtraia o 900 C = 350 1250 Passo 2: Para cada coluna, subtraia 150 C = 0 350 mı́nimo da linha. 750 750 850 550 950 900 150 0 500 C = 0 350 50 Prof. Dr. Leandro Balby Marinho Se j = n, temos uma solução ótima. Escolha um 0 por linha e coluna. Se j 6= n, determine a menor entrada que não tenha sido riscada. Subtraia essa entrada de todas as entradas não riscadas e a some a todas as entradas com 2 riscos (Volta ao passo 3). Como o mı́nimo de cada coluna é 0, a matriz permanece a mesma nesse passo. 0 200 0 8 / 26 o mı́nimo da coluna. 0 0 500 200 50 0 150 0 500 C = 0 350 50 UFCG CEEI Prof. Dr. Leandro Balby Marinho 0 200 0 9 / 26 UFCG CEEI Introdução Alocação de Tarefas Método Húngaro Exemplo 1 cont. Introdução Alocação de Tarefas Método Húngaro Exemplo 1 cont. Solução: Escolha um 0 por linha e coluna 150 0 0 500 200 C = 0 350 50 0 Passo 3: Cubra cada 0 com o mı́nimo de traços 150 0 500 C = 0 350 50 0 200 0 900 C = 350 1250 Como n = 3 traços, temos uma solução ótima. 150 0 500 C = 0 350 50 0 200 0 750 750 850 550 950 900 Total = 750 + 350 + 900 = 2000 Prof. Dr. Leandro Balby Marinho 10 / 26 Introdução UFCG CEEI Alocação de Tarefas Método Húngaro Exemplo 2 Prof. Dr. Leandro Balby Marinho Introdução Alocação de Tarefas UFCG CEEI Método Húngaro Exemplo 2 cont. Passo 1: Para cada linha, subtraia o 4 C = 2 3 Considere a matriz abaixo: Jogador 1 Jogador 2 Jogador 3 Pos 1 4 2 3 Pos 2 2 2 1 Pos 3 4 3 5 2 C = 0 2 Se você fosse um técnico de um time com salários atrasados e quisesse sabotar o time. Como escalar um time para que ele tenha a maior chance de perder? Prof. Dr. Leandro Balby Marinho 11 / 26 12 / 26 UFCG CEEI Prof. Dr. Leandro Balby Marinho mı́nimo da linha. 2 4 2 3 1 5 0 0 0 2 1 4 13 / 26 UFCG CEEI Introdução Alocação de Tarefas Método Húngaro Exemplo 2 cont. Alocação de Tarefas Método Húngaro Exemplo 2 cont. Passo 2: Para cada coluna, subtraia 2 C = 0 2 2 C = 0 2 Passo 3: Cubra cada 0 com o mı́nimo de traços. o mı́nimo da coluna. 0 2 0 1 0 4 0 0 0 Prof. Dr. Leandro Balby Marinho Introdução Introdução 2 C = 0 2 Alocação de Tarefas 2 1 4 Como n = 2 traços, subtraia a menor entrada não riscada de todas as outras. 1 0 0 C = 0 1 0 1 0 2 1 0 3 14 / 26 0 0 0 UFCG CEEI Método Húngaro Exemplo 2 cont. Prof. Dr. Leandro Balby Marinho Introdução 15 / 26 Alocação de Tarefas UFCG CEEI Método Húngaro Exemplo 2 cont. Solução: Escolha um 0 por linha e coluna. Repete Passo 3: Cubra cada 0 com o mı́nimo de traços. 1 C = 0 1 1 C = 0 1 0 1 0 0 0 2 0 1 0 0 0 2 1 C = 0 1 0 1 0 0 0 2 4 C = 2 3 2 2 1 4 3 5 Total = 4 + 2 + 1 = 7 Prof. Dr. Leandro Balby Marinho 16 / 26 UFCG CEEI Prof. Dr. Leandro Balby Marinho 17 / 26 UFCG CEEI Introdução Alocação de Tarefas Método Húngaro Problemas de Maximização Introdução Alocação de Tarefas Método Húngaro Exemplo 3 Considere a matriz abaixo: I I Da forma como foi apresentado, o método húngaro resolve apenas problemas de minimização. Jogador 1 Jogador 2 Jogador 3 Como resolver problemas de maximização sem alterar o algoritmo? Introdução 18 / 26 Alocação de Tarefas UFCG CEEI Método Húngaro Exemplo 3 cont. Pos 3 4 3 5 Prof. Dr. Leandro Balby Marinho Introdução 19 / 26 Alocação de Tarefas UFCG CEEI Método Húngaro Exemplo 3 cont. Passo 0: Multiplica a matriz por −1. 4 C = 2 3 2 2 1 −4 −2 C = −2 −2 −3 −1 Prof. Dr. Leandro Balby Marinho Pos 2 2 2 1 Se você fosse um técnico de um time e soubesse a qualidade de cada jogador em cada posição. Como escalar um time para que ele seja o mais forte possı́vel? Multiplicar por −1 a matriz de custo. Prof. Dr. Leandro Balby Marinho Pos 1 4 2 3 Passo 1: Para cada linha, subtraia o −4 C = −2 −3 4 3 5 0 C = 1 2 −4 −4 −5 20 / 26 UFCG CEEI Prof. Dr. Leandro Balby Marinho mı́nimo da linha. −2 −4 −2 −4 −1 −5 2 1 4 0 0 0 21 / 26 UFCG CEEI Introdução Alocação de Tarefas Método Húngaro Exemplo 3 cont. Alocação de Tarefas Método Húngaro Exemplo 3 cont. Passo 2: Para cada coluna, subtraia 0 C = 1 2 0 C = 1 2 Passo 3: Cubra cada 0 com o mı́nimo de traços. o mı́nimo da coluna. 2 0 1 0 4 0 1 0 3 Prof. Dr. Leandro Balby Marinho Introdução Introdução 0 C = 1 2 Alocação de Tarefas 0 0 0 Como n = 3 traços, temos uma solução ótima. 0 1 0 C = 1 0 0 2 3 0 0 0 0 22 / 26 1 0 3 UFCG CEEI Método Húngaro Exemplo 3 cont. Prof. Dr. Leandro Balby Marinho Introdução 23 / 26 Alocação de Tarefas UFCG CEEI Método Húngaro Matriz Não-Quadrada Solução: Escolha um 0 por linha e coluna. 0 1 0 C = 1 0 0 2 3 0 4 C = 2 3 2 2 1 4 3 5 I Quando houver mais agentes (ou vice-versa) que tarefas ainda podemos aplicar o método húngaro. I Nesse caso, adicione tarefas (ou agentes) fictÃcias de custo 0 de modo que a matriz de custo seja quadrada. Total = 4 + 2 + 5 = 11 Prof. Dr. Leandro Balby Marinho 24 / 26 UFCG CEEI Prof. Dr. Leandro Balby Marinho 25 / 26 UFCG CEEI Introdução Alocação de Tarefas Método Húngaro Referências Slides Prof. Tiago Massoni e Prof. Rohit Gheyi. Prof. Dr. Leandro Balby Marinho 26 / 26 UFCG CEEI
Download
