Modelo em Programação Linear: Construção e Exemplos

Faculdade de Engenharia Eng Celso Daniel Engenharia de Produção Pesquisa Operacional I Profa Dra Lílian Kátia de Oliveira 3 Programação Linear 31 Modelo em Programação Linear Uma das técnicas mais utilizadas na abordagem de problemas de Pesquisa Operacional é a Programação Linear A simplicidade do modelo envolvido e a disponibilidade de uma técnica de solução programável facilitam sua aplicação As aplicações mais conhecidas são feitas em sistemas estruturados como os de produção finanças controle de estoques etc O modelo matemático de Programação Linear é composto de uma função objetivo linear e de restrições técnicas representadas por um grupo de inequações também lineares Exemplo Função objetivo a ser maximizada 1 2 Lucro 2 3 x x Restrições técnicas 1 2 1 2 4 3 10 6 20 x x x x de não negatividade 1 2 0 0 x x Variáveis de decisão 1 x e 2 x A construção do modelo matemático no caso um modelo linear é a parte mais complicada do nosso estudo Não há regra fixa para esse trabalho mas podemos sugerir o seguinte roteiro 1 Quais as variáveis de decisão Explicitar as decisões que devem ser tomadas e representar as possíveis decisões através de variáveis de decisão Exemplos Programação da produção quantidade a produzir no período Programação de investimentos decisões de investimento etc Pesquisa Operacional I Profa Dra Lilian Kátia de Oliveira 2 2 Qual o objetivo Identificar o objetivo na tomada de decisão Exemplos Maximizar lucros ou receitasetc Minimizar custos ou perdas etc 3 Quais as restrições Cada restrição imposta na descrição do sistema deve ser expressa como uma relação linear igualdade ou desigualdade montadas com as variáveis de decisão Exemplos 1 Certa empresa fabrica dois produtos P1 e P2 O lucro unitário de P1 é de 1000 unidades monetárias e o lucro unitário de P2 é de 1800 unidades monetárias A empresa precisa de 20 horas para fabricar uma unidade de P1 e de 30 horas para fabricar uma unidade de P2 O tempo anual de produção disponível para isso é de 1200 horas A demanda esperada para cada produto é de 40 unidades anuais para P1 e 30 unidades anuais para P2 Qual é o plano de produção para que a empresa maximize seu lucro Construa o modelo de PL para esse caso Solução a Quais as variáveis de decisão O que deve ser decidido é o plano de produção isto é quais as quantidades anuais que devem ser produzidas de P1 e P2 Portanto as variáveis de decisão serão 1x quantidade anual a produzir de P1 2x quantidade anual a produzir de P2 b Qual o objetivo O objetivo é maximizar o lucro que pode ser calculado Lucro devido a P1 1 1000x Lucro devido a P2 2 1800x Lucro total 1 2 1000 1800 L x x Objetivo 1 2 Maximizar 1000 1800 L x x Pesquisa Operacional I Profa Dra Lilian Kátia de Oliveira 3 c Quais as restrições As restrições impostas pelo sistema são Disponibilidade de horas para a produção Horas ocupadas com P1 1 20x Horas ocupadas com P2 2 30x Total de horas ocupadas na produção 1 2 20 30 x x Disponibilidade 1200 horas Restrição descritiva da situação 1 2 20 30 1200 x x Disponibilidade de mercado para os produtos demanda Disponibilidade para P1 40 unidades Quantidade a produzir de P1 1x Restrição descritiva da situação 1 x 40 Disponibilidade para P2 30 unidades Quantidade a produzir de P2 2x Restrição descritiva da situação 2 x 30 Resumo do modelo 1 2 1 2 1 2 1 2 Max 1000 1800 sujeito a 20 30 1200 40 30 0 0 L x x x x x x x x 2 Para uma boa alimentação o corpo necessita de vitaminas e proteínas A necessidade mínima de vitaminas é de 32 unidades por dia e a de proteínas é de 36 unidades por dia Uma pessoa tem disponível carne e ovos para se alimentar Cada unidade de carne contém 4 unidades de vitaminas e 6 unidades de proteínas Cada unidade de ovo contém 8 unidades de vitaminas e 6 unidades de proteínas Pesquisa Operacional I Profa Dra Lilian Kátia de Oliveira 4 Qual a quantidade diária de carne e ovos que deve ser consumida para suprir as necessidades de vitaminas e proteínas com o menor custo possível Cada unidade de carne custa 3 um e cada unidade de ovo custa 25 um Pesquisa Operacional I Profa Dra Lilian Kátia de Oliveira 5 32 Exemplos de Modelos de Otimização Linear 321 O Problema da Mistura Suponha que vários ingredientes devem ser misturados para a produção de um novo produto chamado mistura A composição dos ingredientes é conhecida bem como a composição da mistura a ser determinada Suponha que m componentes sejam relevantes para a mistura a ser determinada e que n ingredientes que contém os componentes estejam disponíveis Na tabela abaixo descrevese a fração de cada componente em cada ingrediente e a fração dos componentes na mistura A última linha fornece os custos unitários de cada ingrediente RKg Ingredientes Componentes 1 2 n Composição desejável na mistura 1 a11 a12 a1n b1 2 a21 a22 a2n b2 m am1 am2 amn bm Custos dos ingredientes c1 c2 cn sendo aij fração do componente i no ingrediente j isto é quantidade do componente i em uma unidade do ingrediente j por exemplo a24 03 em 1 kg do ingrediente 4 há 300 gramas do componente 2 bi fração do componente i na mistura cj custo de uma unidade do ingrediente j O problema consiste em determinar como misturar os ingredientes disponíveis de tal forma que a mistura final tenha os componentes conforme o desejado e o custo seja o menor possível Formulação Matemática xj quantidade do ingrediente j em uma unidade da mistura j 1 2 n Pesquisa Operacional I Profa Dra Lilian Kátia de Oliveira 6 1 2 0 1 1 2 a sujeito min 1 j 1 j 2 2 1 1 n j x x m i b x a c x c x c x f j n j n i j ij n n Exemplos de aplicações do problema da mistura Ração Ingredientes farinhas de ossos restos de peixe milho soja etc Componentes vitaminas sais minerais proteínas etc Liga metálica Ingredientes minérios de ferro restos de ligas grafite etc Componentes carbono manganês silício etc Adubo Ingredientes cloreto de potássio uréia nitrato etc Componentes nitrogênio potássio fósforo etc Suco de laranja Ingredientes sucos de laranja de diferentes pomares e diferentes tipos de laranja pêra lima etc Componentes acidez cor sólidos etc 322 O Problema de Corte Suponha que m tipos de peças sejam encomendadas por clientes e que b1 b2 bm sejam as quantidades solicitadas dos tipos 1 2 m respectivamente Além disso considere que as peças disponíveis em estoque sejam todas iguais e tenham comprimento L 11 Por exemplo considere m 3 tipos de peças com os seguintes comprimentos li e as seguintes quantidades demandadas bi l1 3 metros b1 1000 barras l2 35 metros b2 2000 barras l3 4 metros b3 1500 barras Pesquisa Operacional I Profa Dra Lilian Kátia de Oliveira 7 As diferentes maneiras que as peças menores podem ser cortadas a partir da peça maior são denominadas padrões de corte Para este exemplo os padrões de corte possíveis são o pedaço cinza é considerado perda Suponha que n padrões de corte sejam conhecidos e que o jésimo padrão de corte produz aij peças encomendadas do tipo i 1 2 m representado pelo vetor aj mj j a a 1 Para os padrões de corte acima temse os seguintes vetores a1 0 0 3 a2 0 2 1 a3 0 3 0 a4 2 0 1 Com isso o problema de corte se reduz a determinar o número de vezes que um padrão de corte deverá ser utilizado Objetivo cortar o menor número de peças em estoque de forma que a demanda dos itens seja atendida Formulação Matemática xj número de peças em estoque cortadas utilizando o padrão de corte j j 1 2 n 1 2 0 1 2 a sujeito min 1 j 2 1 n j x m i b x a x x x f j n i j ij n 3 3 1 2 2 1 2 2 2 1 1 1 Pesquisa Operacional I Profa Dra Lilian Kátia de Oliveira 8 Quando apenas uma dimensão é relevante para o corte dizse que o problema é unidimensional Se duas ou três dimensões são relevantes temse os problemas bidimensionais e tridimensionais respectivamente Exemplos de aplicações Problemas unidimensionais rolos de papel rolos de filme fotográfico barras de ferro etc Problemas bidimensionais placas de madeira placas de vidro chapas de aço etc Problemas tridimensionais carregamento de contêineres carregamento de caminhões etc 323 Problema de Transporte Unidades de um determinado produto deverão ser transportadas de localidades origens para localidades destinos Suponha que existam m origens e n destinos e o custo de transportar uma unidade do produto da origem i para o destino j seja cij Suponha também que o produto esta disponível na origem i na quantidade ai e a demanda do produto no destino j seja bj Considere que o produto pode ser transportado de qualquer origem para qualquer destino O problema consiste em determinar quais as quantidades que devem ser transportadas de cada origem para cada destino de forma que o custo total de transporte seja mínimo Formulação Matemática xij quantidade do produto a ser transportada da origem i para o destino j 1 2 1 2 0 1 2 1 2 a sujeito min 1 1 j 1 1 n m j i x n j b x m i a x c x f ij m i j ij n i ij m i n j ij ij REFERÊNCIAS BIBLIOGRÁFICAS SILVA E M SILVA E M GONÇALVES V MUROLO A C Pesquisa operacional 3ª Edição São Paulo Editora Atlas 1998 HILLIER F S Introdução à pesquisa operacional Rio de Janeiro Editora Campus 1988