Notas de Aula Metodos Quantitativos Tomada de Decisao Otimizacao e Heuristicas

Notas de Aula da Disciplina de Métodos Quantitativos para Tomada de Decisão Prof Edgard Pedroso Arquivo de aulas n o 01a Apresentação do plano de ensino Introdução aos Métodos Quantitativos para Tomada de Decisão Problemas de Otimização Combinatória Métodos Quantitativos para Tomada de Decisão Mapa Mental 3 Métodos exatos Garantem a obtenção da solução ótima máximo ou mínimo em um no finito de passos Para problemas que apresentam um espaço de busca de grande dimensão com várias soluções possíveis entre as quais devese encontrar a solução ótima o tempo de processamento para tal tarefa pode tornarse inviável Neste caso uma opção para reduzir do custo computacional para níveis aceitáveis é utilizar os métodos heurísticos ou meta heurísticos Exemplos de métodos exatos Otimização de ProcessosOtimização Avançada de Processos Programação linear Método Simplex Big M Duas Fases e Alg DualSimplex Designação Algoritmo Húngaro Transporte Algoritmo Próprio Caminho mais curto Algoritmo de Dijkstra Fluxo de custo mínimo Método das Variáveis Duais Outros Programação Inteira Algoritmo de Blanch Bound Limitar e Ramificar Programação Dinâmica Princípio de Bellman Uma política de decisões ótimas só pode ser formada por subpolíticas ótimas Programação Não Linear O modelo matemático apresenta relações nãolineares na função objetivo eou restrições Método Gradiente Método de Newton outros MÉTODOS HEURÍSTICOS Introdução Etimologia da palavra heurística Do grego heuriskein significa encontrar ou descobrir Heurísticas Técnicas de busca de boas soluções próximas ao ótimo em tempo computacional aceitável sem garantir otimalidade ou o quão próximo ao ótimo tal solução está São métodos desenvolvidos para serem aplicados na solução de problemas específicos Metaheurísticas São consideradas heurísticas de uso geral ou uma heurística das heurísticas São métodos desenvolvidos para serem aplicados na solução de um amplo conjunto de problemas diferentes Métodos Heurísticos e Metaheurísticos São utilizados para resolver Problemas de Otimização Combinatória Otimização Combinatória Problemas de Otimização Combinatória São problemas para os quais existe uma gama enorme de soluções possíveis domínio finito restrições dentre as quais procurase determinar a ótima que maximiza ou minimiza o valor da função objetivo Exemplos Clássicos de Otimização Combinatória Área de Pesquisa Operacional Problema do Caixeiro Viajante PCV Problemas de Localização de FacilidadesInstalações PLF Problema da Mochila Problemas de grande dimensão de Roteamento de Veículos Transporte etc 5 De forma simplificada os problemas de Otimização Combinatória podem ser classificados em P Polinomial NP Não Polinomial NPhard Não Polinomial Difícil I Um problema de Otimização Combinatória é P Polinomial quando o número de operações necessárias para a obtenção da solução ótima é limitado no pior caso por uma função polinomial Deterministic Polynomialtime Exemplos de problemas P Problemas de Transportes PT Problemas de Designação PD Problema de Programação de Horários de Trabalho etc II Um problema de Otimização Combinatória é NP Não Polinomial quando o número de operações necessárias para a obtenção da solução ótima é dado por uma função não polinomial Nondeterministic Polynomialtime Exemplos de problemas NP Problema do Caixeiro Viajante PCV Problemas de Localização de FacilidadesInstalações PLF Problemas de Roteamento de grande dimensão etc III Problema de Otimização Combinatória NPhard são os mais difíceis de serem resolvidos dentre os problemas NP Não serão abordados em nossos estudos Exemplos de problemas NPhard Problema de decisão da soma de subconjuntos Dado um conjunto de números inteiros pode algum subconjunto não vazio deste somar zero Classificação simplificada dos Problemas de Otimização Combinatória MédiaM ENADE 14Q19EP Ex Programação de Produção mix de produção Refrig A x1 litros Refrig B x2 litros Valores limitantes por semana Extrato Delta pacotes litro de refrig 1 3 000 pacotes Extrato Gama pacotes litro de refrig 1 4 000 pacotes Água litros litro de refrig 1 112 9 000 litros Lucro Reais litro de refrig 5 2 Refrig A x1 litros Refrig B x2 litros Valores limitantes por semana Extrato Delta pacotes litro de refrig 1 3 000 pacotes Extrato Gama pacotes litro de refrig 1 4 000 pacotes Água litros litro de refrig 1 112 9 000 litros Lucro Reais litro de refrig 5 2 inteiros x e 0 x 0 x x 9 000 III 2x x 4 000 II x 3 000 I x sa 2x 5x f x x max 2 1 2 1 2 1 2 1 2 1 2 1 fobj Satisfaz todas as restrições mas não maximiniza a f 1 000 4 000 13 000 4 000 1000 x x e fobj e satisfaz todas restrições Maximiniza a f 3 000 3 000 2 1000 3000 3000 x x d Não satisfaz a restrição III f 3 000 4 000 23 000 4 000 3000 x x c fobj Satisfaz todas as restrições mas não maximiniza a 8 000 f 0 4 000 4 000 0 x x b Satisfaz todas as restrições mas não maximiniza a função objetivo 0 f 0 0 0 0 x x a 2 1 2 1 2 1 2 1 2 1 Acerto em D 598 Atração por C 268 OBS Modelo Matemático 9 Atividade Prática Formativa em Grupo No 1 1º TDE Metodologia Sala de Aula Invertida Exemplo Programação de Produção Uma fábrica de polpa para papel fabrica polpa mecânica PM e polpa química PQ Como ela pertence a uma cooperativa ela quer garantir um mínimo de 300 trabalhadoresdia em empregos e um faturamento mínimo diário de R 4000000 Os dois tipos de polpa exigem 1 trabalhadordia por tonelada produzida A PM é vendida por R 10000 ton e a PQ é vendida por R 20000ton A poluição é medida pela demanda bioquímica de oxigênio DBO Uma tonelada de PM gera 1 DBO e 1 ton de PQ gera 15 DBO A capacidade máxima de produção diária é 250 toneladas de PM e de 300 toneladas de PQ e os processos de produção são independentes Denominando de XPM a quantidade em toneladasdia de polpa mecânica e de XPQ a quantidade em toneladasdia de polpa química a serem produzidos qual deverá ser o plano de produção diário viável para gerar o mínimo de poluição em DBOs possível ao meio ambiente atendendo as restrições apresentadas A XPM 250 e XPQ 0 B XPM 0 e XPQ 300 C XPM 150 e XPQ 50 D XPM 100 e XPQ 100 E XPM 200 e XPQ 100 Exemplo Programação de Produção Uma fábrica de polpa para papel fabrica polpa mecânica PM e polpa química PQ Como ela pertence a uma cooperativa ela quer garantir um mínimo de 300 trabalhadoresdia em empregos e um faturamento mínimo diário de R 4000000 Os dois tipos de polpa exigem 1 trabalhadordia por tonelada produzida A PM é vendida por R 10000 ton e a PQ é vendida por R 20000ton A poluição é medida pela demanda bioquímica de oxigênio DBO Uma tonelada de PM gera 1 DBO e 1 ton de PQ gera 15 DBO A capacidade máxima de produção diária é 250 toneladas de PM e de 300 toneladas de PQ e os processos de produção são independentes Quanto se deve fabricar diariamente de cada tipo de polpa poluindo o mínimo possível Variáveis de decisão xPM x1 Quantidade em toneladasdia de PM a ser produzida xPQ x2 Quantidade em toneladasdia de PQ a ser produzida Modelo matemático Função Objetivo min Poluição min Z fxPM xPQ 1 xPM 15 xPQ I capacidade de produção de PM xPM 250 Sujeita as seguintes restrições II capacidade de produção de PQ xPQ 300 IV Renda bruta mínima 100 xPM 200 xPQ 40 000 III nº min de empregos 1 xPM 1 xPQ 300 xPM 0 e xPQ 0 sa Determinação do mix de produção Feedback Resolução pelo software LINGO 120 200 tondia 100 tondia X x x x x X 2 1 PQ PM 350 DBOdia x x f Z PQ PM min min Conclusão Portanto a programação de produção a ser adotada pela fábrica afim de minimizar a demanda bioquímica de oxigênio poluição será produzir 200 tondia de Poupa Mecânica e 100 tondia de Poupa Química alcançandose a demanda mínima de 350 DBOdia método exato Resposta Item A 12 Problema de programação de horários de trabalho Considere uma praça de pedágio cujo funcionamento tem a seguinte demanda por funcionários Horário Nº min de funcionários 0000 h 0600 h 2 0600 h 1000 h 6 1000 h 1200 h 4 1200 h 1400 h 5 1400 h 1600 h 4 1600 h 1800 h 6 1800 h 2200 h 4 2200 h 2400 h 3 Considere xj o nº de funcionários que iniciam seu trabalho na hora j e que todos eles trabalham 8h de forma ininterrupta O início de turno de trabalho deve ocorrer sempre em horários a partir de 0000 h com intervalos de 2 horas ou seja às 0000 h 0200 h 0400 h 2200h Determine quantos funcionários no mínimo a empresa deverá contratar e de que forma estes deverão trabalhar Ex Programação Linear Inteira Programação de pessoal 13 Horário Nº min de funcs 00 06 2 06 10 6 10 12 4 12 14 5 14 16 4 16 18 6 18 22 4 22 24 3 Solução através de método exato de um modelo de programação linear inteira 22 20 18 16 14 12 10 8 6 4 2 0 x x x x x x x x x x x x Função Objetivo min Z Restrições Horário de início dos turnos de 8h Nº min de funcs 00 h 02 h 2 02 h 04 h 2 04 h 06 h 2 06 h 08 h 6 08 h 10 h 6 10 h 12 h 4 12 h 14 h 5 14 h 16 h 4 16 h 18 h 6 18 h 20 h 4 20 h 22 h 4 22 h 24 h 3 inteiros não negativos x 3 x x x x 4 x x x x 4 x x x x 6 x x x x x 4 x x x x x 5 x x x x x 4 x x x x x 6 6 x x x x 2 x x x x 2 x x x x 2 x x x x j 16 18 20 22 14 16 18 20 12 14 16 18 10 12 14 16 8 10 12 14 6 8 10 12 4 6 8 10 2 4 6 8 0 24 2 4 6 22 0 24 2 4 20 22 0 24 2 18 20 22 24 0 Z xj nº de funcionáriosque iniciam a jornada de trabalho na hora j 22 20 18 16 14 12 10 8 6 4 2 0 x x x x x x x x x x x x Função Objetivo min Z Restrições inteiros não negativos x 3 x x x x 4 x x x x 4 x x x x 6 x x x x x 4 x x x x x 5 x x x x x 4 x x x x x 6 6 x x x x 2 x x x x 2 x x x x 2 x x x x j 16 18 20 22 14 16 18 20 12 14 16 18 10 12 14 16 8 10 12 14 6 8 10 12 4 6 8 10 2 4 6 8 0 24 2 4 6 22 0 24 2 4 20 22 0 24 2 18 20 22 24 0 Z 12 Nº de variáveis de decisão n 12 Nº de restrições n polinomial P é trabalho de problema de programaçã o de horários O início de turno de n de horários n o OBS Mais adiante veremos que no Problema do Caixeiro Viajante PCV que é não polinomial NP temos Nº de variáveis n2 n Nº de restrições 2n 2 onde n nº de nós Solução Método de Branch and Bound Limitar e Ramificar método exato Não Polinomial Resolução pelo LINDO RESPOSTA Entre outras soluções existentes serão apresentadas algumas obtidas por softwares Linear Interactive and Discrete Optimizer método exato 02 24 46 68 810 1012 1214 1416 1618 1820 2022 2224 X0 0 X2 2 2 2 2 2 X4 0 X6 4 4 4 4 4 X8 0 X10 0 X12 1 1 1 1 1 X14 4 4 4 4 4 X16 1 1 1 1 1 X18 0 X20 0 X22 2 2 2 2 2 Total 14 Restrição 2 2 2 6 6 4 5 4 6 4 4 3 Nº de funcs por int 2h 2 4 4 6 6 4 5 5 6 6 5 3 Solução pelo LINDO método exato 17 Resolução pelo LINGO RESPOSTA Language for Interactive General Optimizer método exato 02 24 46 68 810 1012 1214 1416 1618 1820 2022 2224 X0 2 2 2 2 2 X2 3 3 3 3 3 X4 0 X6 1 1 1 1 1 X8 2 2 2 2 2 X10 2 2 2 2 2 X12 0 X14 1 1 1 1 1 X16 3 3 3 3 3 X18 0 X20 0 X22 0 Total 14 Restrição 2 2 2 6 6 4 5 4 6 4 4 3 Nº de funcs por int 2h 2 5 5 6 6 5 5 5 6 4 4 3 Solução pelo LINGO 19 Resolução pelo TORA Temporary Ordered Routing Algorithm método exato 02 24 46 68 810 1012 1214 1416 1618 1820 2022 2224 X0 1 1 1 1 1 X2 4 4 4 4 4 X4 0 X6 2 2 2 2 2 X8 0 X10 2 2 2 2 2 X12 1 1 1 1 1 X14 1 1 1 1 1 X16 2 2 2 2 2 X18 0 X20 1 1 1 1 1 X22 0 Total 14 Restrição 2 2 2 6 6 4 5 4 6 4 4 3 Nº de funcs por int 2h 2 6 5 7 6 4 5 4 6 4 4 3 Solução pelo TORA 20 Total 14 02 24 46 68 810 1012 1214 1416 1618 1820 2022 2224 X2 2 2 2 2 2 X6 4 4 4 4 4 X12 1 1 1 1 1 X14 4 4 4 4 4 X16 1 1 1 1 1 X22 2 2 2 2 2 Nº de funcs por int 2h 2 4 4 6 6 4 5 5 6 6 5 3 Total 14 02 24 46 68 810 1012 1214 1416 1618 1820 2022 2224 X0 1 1 1 1 1 X2 4 4 4 4 4 X6 2 2 2 2 2 X10 2 2 2 2 2 X12 1 1 1 1 1 X14 1 1 1 1 1 X16 2 2 2 2 2 X20 1 1 1 1 1 Nº de funcs por int 2h 2 6 5 7 6 4 5 4 6 4 4 3 SolLINDO SolTORA Total 14 02 24 46 68 810 1012 1214 1416 1618 1820 2022 2224 X0 2 2 2 2 2 X2 3 3 3 3 3 X6 1 1 1 1 1 X8 2 2 2 2 2 X10 2 2 2 2 2 X14 1 1 1 1 1 X16 3 3 3 3 3 Nº de funcs por int 2h 2 5 5 6 6 5 5 5 6 4 4 3 SolLINGO OBS Softwares diferentes podem resultar em soluções ótimas diferentes 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