Problemas Lineares Especiais Problema de Atribuição-2020-1

12 Problemas Lineares Especiais – Problema de Atribuição © 2020 Prof. Sérgio F. Mayerle 12 Problemas Lineares Especiais – Problema de Atribuição EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 2 of 14  Descrição do problema de atribuição  Algoritmo Húngaro  Exemplo numérico  Exemplo prático 12 Problemas Lineares Especiais – Problema de Atribuição EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 3 of 14 ijc Descrição do Problema de Atribuição O Problema de Atribuição consiste em designar n tarefas a n máquinas, de modo que toda tarefa seja designada a uma e somente uma máquina, e que além disto o custo total desta atribuição seja mínimo. Seja ijc o custo de atribuir a tarefa j à máquina i. Então, este problema poderá ser definido como:   1 1 1 1 . : 1 1,..., 1 1,..., 0,1 , 1,..., (1.a) (1.b) (1.c) (1.d) n n ij ij i j n ij i n ij j ij Min z c x s a x j n x i n x i j n                  Para obter a solução deste problema, é utilizado um algoritmo específico, conhecido como algoritmo húngaro, cuja aplicação requer que o número de máquinas seja igual ao número de tarefas. Sempre é possível satisfazer essa condição, fazendo com que sejam criadas máquinas ou tarefas fictícias, com custos de atribuição nulos. Como resultado desta operação é obtida uma matriz quadrada de custos de atribuição, denotada por [ ij ] n n C c   . 12 Problemas Lineares Especiais – Problema de Atribuição EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 4 of 14 Algoritmo Húngaro P1 Subtraia de cada linha da matriz C o menor elemento da linha, obtendo a matriz C. Subtraia de cada coluna da matriz C o menor elemento da coluna, obtendo a matriz 0 C . Faça k  0 . P2 Assinale o máximo número de zeros na matriz k C , de modo que não exista mais do que um zero assinalado por linha e coluna. Se n zeros foram assinalados em k C , então PARE. Os zeros assinalados correspondem à atribuição ótima. P3 Cubra os zeros da matriz k C com o menor número de retas horizontais e verticais, efetuando, para tanto, as seguintes operações: a) marque com  cada uma das linhas que não tiveram zeros assinalados; b) marque com  cada uma das colunas que possui um zero não assinalado em linha marcada; c) marque com  as linhas que possuírem zeros assinalados em colunas marcadas; d) repita as operações (b) e (c) até que nenhuma marca adicional possa ser realizada; e) cubra com retas horizontais as linhas da matriz não marcadas com ; f) cubra com retas verticais as colunas da matriz marcadas com . P4 Encontre o menor elemento da matriz k C não coberto por reta (vertical ou horizontal). Subtraia este valor de todos os elementos não cobertos por reta, e adicione este mesmo valor aos elementos cobertos por duas retas (uma vertical e outra horizontal). Denomine a matriz resultante de k 1 C  , faça 1 k  k  , e retorne a P2. 12 Problemas Lineares Especiais – Problema de Atribuição EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 5 of 14 Exemplo Resolver o problema de atribuição, considerando a seguinte matriz de custos de alocação: Tarefas T1 T2 T3 T4 T5 M1 5 7 6 8 10 M2 7 9 12 11 16 M3 6 9 11 9 13 M4 8 10 11 10 12 M5 7 10 15 12 15 M6 6 8 14 12 17 Máquinas M7 8 9 10 13 15 Inclua colunas fictícias, de modo a igualar o número de linhas e colunas. T1 T2 T3 T4 T5 Fic Fic M1 5 7 6 8 10 0 0 M2 7 9 12 11 16 0 0 M3 6 9 11 9 13 0 0 M4 8 10 11 10 12 0 0 M5 7 10 15 12 15 0 0 M6 6 8 14 12 17 0 0 M7 8 9 10 13 15 0 0 Da matriz acima subtraia o menor elemento de cada linha de todos elementos da respectiva linha, e da matriz resultante, subtraia o menor elemento de cada coluna de todos elementos da respectiva coluna. 12 Problemas Lineares Especiais – Problema de Atribuição EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 6 of 14 Assinale o maior número de zeros, sem que existam mais do que um zero assinalado em cada linha e cada coluna. T1 T2 T3 T4 T5 Fic Fic M1 0 0 0 0 0 0 0 M2 2 2 6 3 6 0 0 M3 1 2 5 1 3 0 0 M4 3 3 5 2 2 0 0 M5 2 3 9 4 5 0 0 M6 1 1 8 4 7 0 0 M7 3 2 4 5 5 0 0 (a) Marque as linhas que não contém zeros assinalados. (b) Marque as colunas que possue um zero não assinalado em linha marcada. (c) Marque linhas com zeros assinalados em colunas marcadas. (d) Repita (b) e (c) até que não seja mais possível marcar linhas e colunas. Cubra com retas verticais as colunas marcadas, e com retas horizontais as linhas não marcadas. T1 T2 T3 T4 T5 Fic Fic M1 0 0 0 0 0 0 0 M2 2 2 6 3 6 0 0 P M3 1 2 5 1 3 0 0 P M4 3 3 5 2 2 0 0 P M5 2 3 9 4 5 0 0 P M6 1 1 8 4 7 0 0 P M7 3 2 4 5 5 0 0 P P P Encontre o menor elemento não coberto por reta. Subtraia este valor de todos os elementos não cobertos por retas, e adicione-o nos elementos cobertos por duas retas. 12 Problemas Lineares Especiais – Problema de Atribuição EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 7 of 14 Na matriz resultante assinale o maior número de zeros, sem que existam mais do que um zero assinalado em cada linha e cada coluna. T1 T2 T3 T4 T5 Fic Fic M1 0 0 0 0 0 1 1 M2 1 1 5 2 5 0 0 M3 0 1 4 0 2 0 0 M4 2 2 4 1 1 0 0 M5 2 2 8 3 4 0 0 M6 0 0 7 3 6 0 0 M7 2 1 3 4 4 0 0 (a) Marque as linhas que não contém zeros assinalados. (b) Marque as colunas que possue um zero não assinalado em linha marcada. (c) Marque linhas com zeros assinalados em colunas marcadas. Repita (b) e (c) até que não seja mais possível marcar linhas e colunas. Cubra com retas verticais as colunas marcadas, e com retas horizontais as linhas não marcadas. T1 T2 T3 T4 T5 Fic Fic M1 0 0 0 0 0 1 1 M2 1 1 5 2 5 0 0 P M3 0 1 4 0 2 0 0 M4 2 2 4 1 1 0 0 P M5 2 2 8 3 4 0 0 P M6 0 0 7 3 6 0 0 M7 2 1 3 4 4 0 0 P P P Encontre o menor elemento não coberto por reta. Subtraia este valor de todos os elementos não cobertos por retas, e adicione-o nos elementos cobertos por duas retas. 12 Problemas Lineares Especiais – Problema de Atribuição EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 8 of 14 Na matriz resultante assinale o maior número de zeros, sem que existam mais do que um zero assinalado em cada linha e cada coluna. T1 T2 T3 T4 T5 Fic Fic M1 0 0 0 0 0 2 2 M2 0 0 4 1 4 0 0 M3 0 1 4 0 2 1 1 M4 1 1 3 0 0 0 0 M5 1 1 7 2 3 0 0 M6 0 0 7 3 6 1 1 M7 1 0 2 3 3 0 0 Como todas linhas e colunas possuem um zero assinalado, a solução corrente é ótima! Note-se que as máquinas M5 e M7 não são alocadas. Entretanto, observando os dados originais, não se tem evidência de que estas máquinas fossem dominadas pelas demais, de modo a eliminá-las previamente. Assim, a inclusão de tarefas fictícias para que a matriz de custos fosse quadrada, é a única alternativa segura para obteção da solução ótima do problema. Máquina Tarefa Custo M1 T3 6 M2 T1 7 M3 T4 9 M4 T5 12 M5 Fic 0 M6 T2 8 M7 Fic 0 Custo Total 42 A solução apresentada no quadro acima, não é a única. Observe que na última matriz existem outras escolha possíveis de alocação de “zeros”, como por exemplo alocando a máquina M2 à tarefa T2, e a máquina M6 à tarefa T1. 12 Problemas Lineares Especiais – Problema de Atribuição EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 9 of 14 Exemplo Prático O Sr. Taylor é responsável pelo planejamento operacional de uma empresa de transporte aéreo que mantem os seguintes vôos diários: Saída Chegada Num. Vôo Local Hora Local Hora 01 125 POA 09:00 SAO 12:00 02 127 SAO 09:30 FLN 10:40 03 130 FLN 10:00 POA 10:45 04 132 CWB 10:15 FOZ 10:45 05 135 RIO 12:00 POA 17:30 06 140 FOZ 12:30 SAO 15:30 07 142 SAO 14:00 FOZ 17:00 08 148 POA 16:30 CWB 18:00 09 157 FOZ 16:30 RIO 19:15 10 162 RIO 18:00 CWB 19:30 11 170 SAO 17:20 POA 20:30 12 172 FLN 15:10 SAO 18:25 13 176 CWB 10:15 FOZ 12:10 14 180 RIO 13:20 CWB 17:20 15 182 FOZ 16:00 RIO 19:00 Ajude o Sr. Taylor a formular um plano de operação que minimize os custos. Considere os seguintes dados adicionais: Custo de uma decolagem US $ 8.000,00 Custo de um pouso US $ 4.000,00 Custo por km de vôo US $ 50,00 Custo por hora parada US$ 8.000,00 Tempo de um pouso/decolagem 15 min Velocidade de cruzeiro 850 km/h Tempo embarque/desembarque 30 min Considere as seguintes coordenadas dos aeroportos, expressos em km: Aeroporto Coord X Coord Y POA 2570 670 FLN 2750 930 CWB 2700 1170 FOZ 2170 1180 SAO 2650 1370 RIO 3120 1420 12 Problemas Lineares Especiais – Problema de Atribuição EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 10 of 14 Dados: É necessário calcular os custos improdutivos (custos de decolagem, deslocamento e pouso das transferências de aeronaves entre aeroportos, acrescido dos custos de espera da próxima viagem). Considere conhecidos os seguintes parâmetros: i HS , i HC horário de saída e chegada da i-ésima viagem; i O , i D local de origem e destino da i-ésima viagem; ( , ) i d D Oj distância entre o destino da i-ésima viagem e a origem da j-ésima viagem, em km; , disp ti j tempo disponível entre a chegada da i-ésima viagem e a saída de j-ésima viagem; , nesc ti j necessário para sequenciar a j-ésima viagem após o termino da i-ésima viagem; V velocidade de cruzeiro do avião, em km/h; ,i j C custo de sequenciar a j-ésima viagem após o termino da i-ésima viagem; Cálculo da matriz de custos: Cálculo do tempo necessário , ( , )/850 1 30/ 60 i j j i nesc i j d D O O D t       se em caso contrário Cálculo do tempo disponível entre a i-ésima e a j- ésima viagem: , , 24 nesc j i j i i j disp i j j i HS HC HS HC t t HS HC           se em caso contrário Cálculo do custo , , , 0,05 ( , ) 8 12 8 disp i j i j j i i j disp i j j i d D O t O D C t O D           se se 12 Problemas Lineares Especiais – Problema de Atribuição EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 11 of 14 Matriz de custos: 15 215.2 172.0 210.6 200.3 227.6 233.8 16.0 83.2 73.8 83.6 42.7 59.9 200.3 238.3 69.8 206.5 217.2 186.7 212.9 245.4 58.2 61.2 74.5 90.2 101.4 87.9 36.0 212.9 64.0 86.2 178.0 229.2 213.8 225.8 260.5 250.4 73.2 46.0 90.4 116.5 99.9 63.1 225.8 79.2 86.4 222.4 219.8 229.6 226.5 263.0 14.0 63.8 90.4 46.0 119.0 90.5 78.9 226.5 81.7 42.0 124.0 175.2 159.8 171.8 206.5 196.4 211.2 184.0 228.4 254.5 237.9 201.1 171.8 217.2 224.4 187.2 144.0 182.6 172.3 199.6 205.8 180.0 247.2 237.8 55.6 14.7 223.9 172.3 210.3 233.8 172.4 169.8 179.6 176.5 213.0 156.0 205.8 232.4 188.0 261.0 232.5 220.9 176.5 223.7 184.0 157.8 146.3 152.3 130.0 180.4 186.5 182.3 217.8 218.5 228.4 209.0 193.6 130.0 191.1 214.5 168.5 149.6 160.7 156.4 134.0 199.0 185.6 228.5 231.0 182.0 212.3 202.0 156.4 144.7 227.0 145.8 134.3 140.3 118.0 168.4 174.5 170.3 205.8 206.5 216.4 197.0 181.6 118.0 179.1 202.5 100.0 151.2 135.8 147.8 182.5 172.4 187.2 160.0 204.4 230.5 213.9 177.1 147.8 193.2 200.4 163.9 120.7 159.2 149.0 176.3 182.5 156.7 223.9 214.5 224.3 183.3 200.6 149.0 187.0 210.5 211.1 208.5 218.2 215.2 251.7 194.7 52.5 79.1 34.7 107.7 79.1 67.6 215.2 262.3 30.7 163.2 151.6 157.6 135.3 185.8 191.8 187.6 223.2 223.8 233.8 214.3 198.9 135.3 196.4 219.8 170.5 151.6 162.7 158.4 136.0 201.0 187.6 230.5 233.0 184.0 214.3 204.0 158.4 146.7 229.0 12 Problemas Lineares Especiais – Problema de Atribuição EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 12 of 14 Aplicando o algoritmo de atribuição sobre esta matriz de custos, obtém-se a seguinte solução para o problema: ------------------------------- ASSIGNMENT PROBLEM ------------------------------- Row Column Cost ------------------------------- 1 7 16,000 2 12 36,000 3 8 46,000 4 6 14,000 5 1 124,000 6 11 14,700 7 9 188,000 8 13 130,000 9 10 182,000 10 4 118,000 11 3 135,800 12 2 120,700 13 15 30,700 14 14 196,400 15 5 136,000 ------------------------------- Total Cost: ... 1.488,300 Iterations: ... 9 CPU Time: ..... 0,007 ------------------------------- Esta solução corresponde às seguintes sequências de viagens: Seqüência ------------------------------------------------------ #01 01-07-09-10-04-06-11-03-08-13-15-05 #02 02-12 #03 14 12 Problemas Lineares Especiais – Problema de Atribuição EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 13 of 14 Considerando a programação dos vôos das seqüências, será necessário alocar 09 aviões, conforme mostram as tabelas abaixo: Saída Chegada Num. Dia Avião Vôo Local Hora Local Hora 01 1 A1 125 POA 09:00 SAO 12:00 07 1 A1 142 SAO 14:00 FOZ 17:00 09 2 A2 157 FOZ 16:30 RIO 19:15 10 3 A3 162 RIO 18:00 CWB 19:30 04 4 A4 132 CWB 10:15 FOZ 10:45 06 4 A4 140 FOZ 12:30 SAO 15:30 11 4 A4 170 SAO 17:20 POA 20:30 03 5 A5 130 FLN 10:00 POA 10:45 08 5 A5 148 POA 16:30 CWB 18:00 13 6 A6 176 CWB 10:15 FOZ 12:10 15 6 A6 182 FOZ 16:00 RIO 19:00 05 7 A7 135 RIO 12:00 POA 17:30 Saída Chegada Num. Dia Avião Vôo Local Hora Local Hora 02 1 A8 127 SAO 09:30 FLN 10:40 12 1 A8 172 FLN 15:10 SAO 18:25 Saída Chegada Num. Dia Avião Vôo Local Hora Local Hora 14 1 A9 180 RIO 13:20 CWB 17:20 12 Problemas Lineares Especiais – Problema de Atribuição EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 14 of 14 F I M (© 2020 Prof. Sérgio Mayerle)