PESQUISA OPERACIONAL Fabiano F. T. dos Santos Instituto de Matemática e Estatística Origens da Pesquisa Operacional O termo pesquisa operacional é atribuído a A. P. Rowe, que, em 1938 na Grã-Bretanha, coordenava equipes para examinar a eciência de técnicas de operações advindas de experimentos com interceptação de radar. Seção de Pesquisa Operacional do Comando da Força Aérea de Combate, com equipes envolvidas em problemas de Em 1941, foi inaugurada a operações de guerra (alocação eciente dos escassos recursos). Após o nal da guerra a PO evoluiu rapidamente na Inglaterra e nos EUA. Em 1947, foi implantado o projeto SCOOP (Scientic Computation of Optimal Programs) no Pentágono, com o objetivo de apoiar decisões de operações na força aérea americana. Nesse período, o matemático George Danting criou o método simplex e implementou o nome programação linear. Em 1952 foi fundada a sociedade americana de PO: ORSA; em 1953 foram fundadas a sociedade inglesa de PO: ORS e a sociedade americana de ciências e administração: TIMS. Em 1957 foi realizada a primeira conferência internacional de PO, na Inglaterra. Em 1968 foi fundada a sociedade brasileira de PO: SOBRAPO. Os trabalhos apresentados focavam diversas situações. Teoria de estoques Substituição de equipamentos Teoria de las Teoria de jogos Programação de tarefas em máquinas Fluxo em redes etc Desde 1960 a PO vem sendo aplicada em diversas áreas. Mineração, metalurgia exploração de petróleo e construção civil. Setores têxtil, famacêutico, bancário, de telecomunicações e de transportes. Denição de Pesquisa Operacional A PO consiste na abordagem cientíca para tomada de decisões. A PO consiste na abordagem cientíca para solução de problemas no gerenciamento de sistemas complexos. Modelagem Matemática A matemática tem uma importância fundamental na descrição de fenômenos naturais, sociais, econômicos etc. O objetivo é encontrar leis que regem estes fenômenos. Essas leis dão origem aos modelos matemáticos. Um modelo é um objeto abstrato que procura imitar as principais características de um objeto real. Em geral, um modelo matemático é uma representação simplicada do problema real que está sendo estudado. Um modelo deve ser sucientemente detalhado para captar os elementos essenciais do problema, mas sucientemente tratável por métodos de resolução. Processo de modelagem O que estudaremos em Pesquisa Operacional? Ementa ♠ Problemas Clássicos de Programação Linear ♣ Solução Gráca de Problemas de Programação Linear ♥ Método Simplex ♦ Dualidade X Problema do transporte z Análise de sensibilidade Referências Bibliográcas X DE ANDRADE, E. L. Introdução à pesquisa operacional: métodos e modelos para análise de decisão FREITAS, G. L. A. Pesquisa operacional na tomada de decisão: modelagem em Excel X YANASSE, H. H. Pesquisa operacional-Modelagem e algoritmos PRADO, D. Programação linear MOREIRA, D. A. Pesquisa operacional-Curso introdutório X LIEBERMAN, G. J., HILLIER, F. S. Introdução à pesquisa operacional Atendimento Quartas e sextas - 17:00 às 18:40 Avaliações P1 em 16/04/2014 P2 em 28/05/2014 P3 em 11/07/2014 E (no decorrer do curso) MF = 0, 3 · P1 + 0, 3 · P2 + 0, 3 · P3 + 0, 1 · E Problemas de Mistura Problemas de mistura consistem em combinar materiais obtidos na natureza (ou restos de outros já combinados anteriormente) para gerar novos materiais ou produtos com características convenientes. Exemplo 1 Uma empresa deve produzir um tipo de ração para determinado animal. Essa ração é produzida pela mistura de farinhas de três ingredientes básicos: osso, soja e resto de peixe. Cada um desse três ingredientes contém diferentes quantidades de dois nutrientes necessários a uma dieta nutricional balanceada: proteína e cálcio. O nutricionista especica as necessidades mínimas desses nutrientes em 1 kg de ração: a ração deve ser composta de pelo menos 30% de proteína e 50% de cálcio. Cada ingrediente é adquirido no mercado com um certo custo unitário ($/kg). Na tabela a seguir, os dados do problema são apresentados. Dados do problema Nutrientes Proteína Cálcio Custos ($/kg) Osso 0,2 0,6 0,56 Ingredientes Soja 0,5 0,4 0,81 Peixe 0,4 0,4 0,46 Ração 0,3 0,5 O objetivo é: determinar em que quantidades os ingredientes devem ser misturados de modo a produzir uma ração que satisfaça às restrições nutricionais com o mínimo custo. X Sejam x1 , x2 e x3 as quantidades, em kg, de osso, soja e peixe, respectivamente. X O custo da mistura é dado por Z = 0, 56x1 + 0, 81x2 + 0, 46x3 . X As restrições da composição são dadas por 0, 2x1 + 0, 5x2 + 0, 4x3 ≥ 0, 3 e 0, 6x1 + 0, 4x2 + 0, 4x3 ≥ 0, 5. X Sabemos também, que x1 + x2 + x3 = 1, x1 ≥ 0, x2 ≥ 0 e x3 ≥ 0. O modelo matemático completo ca assim Minimizar: Z = 0, 56x1 + 0, 81x2 + 0, 46x3 . O modelo matemático completo ca assim Minimizar: Sujeito a: Z = 0, 56x1 + 0, 81x2 + 0, 46x3 . 0, 2x1 + 0, 5x2 + 0, 4x3 ≥ 0, 3 0, 6x1 + 0, 4x2 + 0, 4x3 ≥ 0, 5 x1 + x2 + x3 = 1 x1 ≥ 0, x2 ≥ 0 x3 ≥ 0. Neste modelo, os objetos envolvidos têm nome: X x1 , x2 e x3 são as variáveis de decisão. X Z é a função objetivo. X As três inequações e a equação após a função objetivo são as restrições de especicação e disponibilidade. Problemas de Transporte Esses problemas referem-se, por exemplo, ao transporte ou distribuição de produtos dos centros de produção aos mercados consumidores de modo que o custo total de transporte seja o menor possível. Os produtos podem ser: petróleo, máquinas, produção agrícola, energia elétrica etc. Exemplo 2 Um companhia distribuidora de bebidas tem dois centros de produção (Araraquara e São José dos Campos) e três mercados consumidores principais (São Paulo, Belo Horizonte e Rio de Janeiro). O custo unitário (em R$) de se transportar uma unidade de um dado produto de cada centro de produção a cada mercado consumidor é dado na tabela a seguir. Nessa tabela também são apresentadas as demandas de cada mercado e quantidade máxima disponível do produto em cada centro de produção. Dados do problema Centro de produção SP (1) Araraquara (1) S. J. Campos (2) Demanda dos mercados 4 11 500 Mercado BH (2) 2 7 400 RJ (3) 5 4 900 Suprimento disponível 800 1000 O objetivo é: determinar em que quantidades o produto deve ser enviado para cada destino com o mínimo custo. X Seja xij a quantidade do produto a ser enviada do centro de X X X X produção i (i=1,2) ao mercado j (j=1,2,3). O custo em transportar o produto dos centros de produção aos mercados é dado por Z = 4x11 + 2x12 + 5x13 + 11x21 + 7x22 + 4x23 . A quantidade que pode ser transportada não pode ultrapassar a disponibilidade do produto no centro de produção: x11 + x12 + x13 ≤ 800 e x21 + x22 + x23 ≤ 1000. As demandas dos mercados devem ser atendidas: x11 + x21 = 500, x12 + x22 = 400 e x13 + x23 = 900. Além disso, x11 ≥ 0, x12 ≥ 0 x13 ≥ 0, x21 ≥ 0, x22 ≥ 0 e x23 ≥ 0. O modelo matemático completo ca assim Minimizar: Z = 4x11 + 2x12 + 5x13 + 11x21 + 7x22 + 4x23 . O modelo matemático completo ca assim Minimizar: Sujeito a: Z = 4x11 + 2x12 + 5x13 + 11x21 + 7x22 + 4x23 . x11 + x12 + x13 ≤ 800 x21 + x22 + x23 ≤ 1000 x11 + x21 = 500 x12 + x22 = 400 x13 + x23 = 900 x11 ≥ 0, x12 ≥ 0, x13 ≥ 0, x21 ≥ 0, x22 ≥ 0, x23 ≥ 0, onde X xij , i = 1, 2; j = 1, 2, 3 são as variáveis de decisão. X Z é a função objetivo. X As oito inequações e as três equações após a função objetivo são as restrições de especicação e disponibilidade. Nós somos aquilo que fazemos repetidamente. Excelência, então, não é um modo de agir, mas um hábito. Aristóteles