Modelos Lineares de Otimização - Aplicações em Planejamento Urbano, Investimento e Produção

3º Aula Modelos lineares de otimização Objetivos de aprendizagem Ao término desta aula vocês serão capazes de conhecer como aplicar a Pesquisa Operacional em problemas de planejamento urbano conhecer como aplicar a Pesquisa Operacional em problemas de investimento conhecer como aplicar a Pesquisa Operacional em problemas de planejamento de produção conhecer como aplicar a Pesquisa Operacional em problemas de indústria química de alimentos ou de base que tenham problemas de mistura de matériasprimas Prezadosas alunosas Nesta terceira aula estudaremos os principais modelos lineares de otimização Esses modelos representam a maior parte das aplicações de PL e consequentemente de PO que os profissionais encontram no dia a dia Bons estudos 26 Pesquisa Operacional Seções de estudo 1 Modelagem em planejamento urbano 2 Modelagem em investimento 3 Programação linar e planejamento de produção 4 Probelma da mistura e refi nação 1 Modelagem em planejamento urbano Planejamento urbano trata de três áreas gerais 1 construção de novos projetos habitacionais 2 recuperação de áreas habitacionais e recreacionais urbanas deterioradas e 3 planejamento de instalações públicas como escolas e aeroportos As restrições associadas com esses projetos são tanto econômicas terreno construção fi nanciamento quanto sociais escolas parques nível de renda Os objetivos do planejamento urbano variam No desenvolvimento de projetos habitacionais de modo geral o lucro é o motivo para a consecução do projeto Nas duas categorias restantes os objetivos envolvem considerações sociais políticas econômicas e culturais A seguir veremos um exemplo de como modelar um problema de planejamento urbano adicionando as restrições e objetivos nas equações de PL 11 Exemplo de Modelo de renovação urbana A seguir veremos um exemplo resolvido baseado em Taha 2008 A cidade de Dourados enfrenta uma séria carência orçamentária Em busca de uma solução de longo prazo a câmara de vereadores da cidade aprova uma melhoria da base de cobrança de impostos que prevê a condenação de uma área habitacional do centro da cidade e sua substituição por um conjunto habitacional moderno O projeto envolve duas fases 1 demolição das casas que estão aquém do padrão para liberar terreno para o novo projeto e 2 construção do novo conjunto urbano A seguir daremos um resumo da situação 1 Um total de 300 casas aquém do padrão podem ser demolidas Cada casa ocupa um lote de 025 acres O custo da demolição de uma casa condenada é de 2000 2 Os tamanhos de lotes para domicílios unidades simples duplos triplos e quádruplos são de 018 028 04 e 05 acres respectivamente Ruas espaços abertos e instalações públicas ocupam 15 da área disponível 3 No novo conjunto habitacional as unidades triplas e quádruplas representam no mínimo 25 do total Unidades simples devem representar no mínimo 20 de todas as unidades e unidades duplas no mínimo 10 4 O imposto cobrado por unidade para unidades simples duplas triplas e quádruplas é de 1000 1900 2700 e 3400 respectivamente 5 O custo da construção por unidade domiciliar simples dupla tripla e quádrupla é de 50000 70000 130000 6 160000 respectivamente O fi nanciamento acordado com um banco local será de no máximo 15 milhões Quantas unidades de cada tipo devem ser construídas para maximizar a arrecadação de impostos Modelo matemático Além de determinar o número de unidades de cada tipo a ser construído precisamos também decidir quantas casas devem ser demolidas para liberar espaço para o novo projeto habitacional Assim as variáveis do problema podem ser defi nidas da seguinte maneira x1 número de unidades simples x2 número de unidades duplas x3 número de unidades triplas x4 número de unidades quádruplas x5 número de casas antigas a demolir O objetivo é maximizar a arrecadação de impostos de todos os quatro tipos de residências isto é Maximizar z 1000x1 1900x2 2700x3 3400x4 A primeira restrição do problema trata da disponibilidade de terreno Área usada para construção de novas casa Área líquida disponível Pelos dados do problema temos Área necessária para novas casas 018x1 028x2 04x3 05x4 Para determinar a área disponível cada casa demolida ocupa um lote de 025 acres o que resulta em um total de 025x5 acres Deixando 15 para espaços abertos ruas e instalações públicas a área líquida disponível é 085025x5 02125x5 A restrição resultante é 018x1 028x2 04x3 05x4 02125x5 Ou 018x1 028x2 04x3 05x4 02125x5 0 O número de casas demolidas não pode exceder 300 o que é expresso como x5 300 Em seguida adicionamos as restrições que limitam o número de unidades de cada tipo de casa Número de unidades simples 20 do total de unidades Número de unidades duplas 10 do total de unidades Número de unidades triplas e quádruplas 25 do total de unidades Essas restrições são expressas matematicamente como x1 02x1 x2 x3 x4 x2 01x1 x2 x3 x4 x3 x4 025x1 x2 x3 x4 A única restrição restante trata de manter o custo de demoliçãoconstrução dentro do orçamento permitido isto é Custo de demolição e construção Orçamento disponível Exprimindo todos os custos em milhares de dólares obtemos 50x1 70x2 130x3 160x4 2x5 15000 Assim o modelo completo se torna 27 Maximizar z l000x1 1900x2 2700x3 3400x4 sujeito a 018x1 028x2 04x3 05x4 02125x5 0 x5 300 08x1 02x2 02x3 02x4 0 01x1 09x2 01x1 01x4 0 025x1 025x2 075x3 075x4 0 50x1 70x2 130x3 160x4 2x5 15000 x1 x2 x3 x4 x5 0 Solução A solução ótima usando o solver tendo Arrecadação total de impostos z 343965 Número de unidades residenciais simples x1 3583 36 unidades Número de unidades residenciais duplas x2 9853 99 unidades Número de unidades residenciais triplas x3 4479 45 unidades Número de unidades residenciais quádruplas x4 0 unidades Número de casas demolidas x5 24449 245 unidades 2 Modelagem em investimento Hoje há inúmeras oportunidades de investimento disponíveis para os investidores Exemplos de problemas de investimento são orçamentos de capital para projetos estratégia de investimentos em títulos seleção de carteira de ações e determinação da política de empréstimos bancários Em muitas dessas situações a programação linear pode ser usada para selecionar o mix ótimo de oportunidades que maximizará o retorno atendendo às condições estabelecidas pelo investidor 21 Modelo de política de empréstimo Nesse exemplo adaptado de Taha 2008 temos o Banco do Brasileiro que está em processo de elaboração de uma política de empréstimo que envolve um máximo de 12 milhões A Tabela 1 apresenta os dados pertinentes aos tipos de empréstimos disponíveis Tabela 1 Empréstimos disponíveis no Banco do Brasileiro Tipo de empréstimo Taxa de juros Taxa de inadimplência Pessoal 0140 010 Automóvel 0130 007 Habitacional 0120 003 Agrícola 0125 005 Comercial 0100 002 Fonte adaptado de Taha 2008 A concorrência com outras instituições fi nanceiras requer que o banco destine no mínimo 40 dos fundos a créditos agrícola e comercial Para auxiliar o setor de construção de residências da região a quantia destinada ao crédito habitacional deve ser igual a no mínimo 50 dos empréstimos pessoais para aquisição de automóveis e aquisição habitacional O banco também estabeleceu uma política de não permitir que a taxa global de inadimplência sobre todos os empréstimos exceda 4 TAHA 2008 Modelo matemático A situação procura determinar a quantidade de empréstimos em cada categoria o que resulta nas seguintes defi nições das variáveis x1 empréstimos pessoais em milhões de dólares x2 empréstimos para compra de automóveis x3 empréstimos habitacionais x4 empréstimos agrícolas x5 empréstimos comerciais O objetivo do Banco do Brasileiro é maximizar seu retorno líquido que é a diferença entre receita de juros e créditos inadimplentes A receita de juros é obtida somente com base em empréstimos em boa posição Portanto como 10 dos empréstimos pessoais são créditos inadimplentes o banco receberá juros sobre apenas 90 do valor emprestado isto é receberá 14 de juros sobre 09x1 do empréstimo original x1 O mesmo raciocínio é aplicado aos outros quatro tipos de empréstimos Assim Total de juros 01409x1 013093x2 012097x3 0125095x4 01 098x5 0126x1 01209x2 01164x3 011875x4 0098x5 Também temos Créditos inadimplentes 01x1 007x2 003x3 005x4 002x5 Ainda seguindo a linha de Taha 2008 a função objetivo é expressa como Maximizar z Total de juros Créditos inadimplentes 0126x1 01209x2 01164x3 011875x4 0098x5 01x1 007x2 003x3 005x4 002x5 0026x1 00509x2 00864x3 006875x4 0078x5 O problema tem cinco restrições 1 O total de fundos não deve exceder 12 milhões x1 x2 x3 x4 x5 12 2 Os empréstimos agrícolas e comerciais são iguais a no mínimo 40 de todos os empréstimos x4 x5 04x1 x2 x3 x4 x5 ou 043x1 04x2 04x3 06x4 06x5 0 3 O crédito habitacional deve ser igual a no mínimo 50 dos empréstimos pessoais para compra de automóveis e habitacional x3 05x1 x2 x3 ou 05x1 05x2 05x3 0 4 Créditos inadimplentes não devem exceder 4 de todos os empréstimos 28 Pesquisa Operacional 01x1 007x2 003x3 005x4 002x5 004x1 x2 x3 x4 x5 ou 006x1 003x2 001x3 001x4 002x5 0 5 Nãonegatividade x1 x2 x3 x4 x5 0 Uma premissa sutil adotada na formulação precedente é que todos os empréstimos são concedidos aproximadamente ao mesmo tempo Essa premissa nos permite ignorar diferenças no valor tempo dos fundos alocados aos diferentes empréstimos TAHA 2008 Solução A solução ótima é z 099648 x1 0 x2 0 x3 72 x4 0 x5 48 3 Programação linar e planejamento de produção Há inúmeras aplicações de PL em controle da produção e de estoque Indo desde a simples alocação de capacidade de máquina para atender à demanda até o caso mais complexo da utilização de estoque para atenuar o efeito da mudança imprevisível na demanda para determinada projeção de planejamento e da utilização de contratação e demissão para enfrentar as mudanças nas necessidades de mão de obra Esta aula apresenta dois exemplos O primeiro trata da programação de produtos usando as instalações normais de produção para atender à demanda durante um único período o segundo trata da utilização do estoque em um sistema de produção que abrange vários períodos para atender à demanda futura TAHA 2008 31 Modelo de produção para um único período Como precaução para o inverno uma empresa de confecção está fabricando parcas e casacos com enchimento de penas de ganso calças com isolamento térmico e luvas Todos os produtos são fabricados em quatro departamentos diferentes corte isolamento térmico costura e embalagem A empresa recebeu pedidos fechados para seus produtos O contrato estipula uma multa para itens não entregues A Tabela 2 mostra os dados pertinentes à situação Tabela 2 Dados para a produção da confecção Tempo por unidade h Departamento Parca Penas de ganso Calças Luvas Capacidade h Corte 030 030 025 015 1000 Isolamento 025 035 030 010 1000 Costura 045 050 040 022 1000 Embalagem 015 015 010 005 1000 Demanda 800 750 600 500 Lucro por unidade 30 40 20 10 Multa por unidade 15 20 10 8 Fonte Taha 2008 Elabore um plano ótimo de produção para a empresa Modelo matemático A defi nição das variáveis é direta Seja x1 número de parcas x2 número de jaquetas com enchimento de penas de ganso x3 número de calças x4 número de pares de luvas Ainda seguindo a linha de raciocínio de Taha 2008 a empresa é multada se não atender à demanda O que signifi ca que o objetivo do problema e maximizar as receitas líquidas defi nidas como Receitas líquidas Lucro total Multa total O lucro total é expresso como 30x1 40x2 20x3 10x4 A multa total é uma função das quantidades não fornecidas Demanda Unidades fornecidas de cada produto TAHA 2008 Essas quantidades podem ser determinadas pelos seguintes limites de demanda x1 800 x2 750 x3 600 x4 500 Uma demanda não é atendida se sua restrição for satisfeita como uma desigualdade Por exemplo se forem produzidas 650 parcas então x1 650 o que resulta em 800 650 150 parcas a menos Podemos expressar a falta de qualquer produto algebricamente com a defi nição de uma nova variável não negativa ou seja sj Número de unidades faltantes do produto jj 1 2 3 4 Nesse caso as restrições da demanda podem ser expressas como x1 s1 800 x2 s2 750 x3 s3 600 x4 s4 500 xj 0 sj 0 j 1234 Agora podemos calcular a multa por produto não entregue como 15s1 20s2 10s3 8s4 Assim a função objetivo pode ser escrita como Maximizar z 30x1 40x2 20x3 10x4 15s1 20s2 10s3 8s4 Para completar o modelo as restrições restantes tratam das capacidades de produção ou seja 030x1 030x2 025x3 015x4 1000 Corte 025x1 035x2 030x3 010x4 1000 Isolamento 045x1 050x2 040x3 022x4 1000 Costura 015x1 05x2 010x3 005x4 1000 Embalagem Portanto o modelo completo se torna Maximizar z 30x1 40x2 20x3 10x4 15s1 20s2 10s3 8s4 Sujeito a 29 030x1 030x2 025x3 015x4 1000 025x1 035x2 030x3 010x4 1000 045x1 050x2 040x3 022x4 1000 015x1 05x2 010x3 005x4 1000 x1 s1 800 x2 s2 750 x3 s3 600 x4 s4 500 xj 0 sj 0 j 1234 Solução A solução ótima é z 64625 x1 850 x2 750 x3 3875 x4 500 s1 s2 s4 0 s3 2125 A solução satisfaz toda a demanda por ambos os tipos de jaquetas parcas e de penas de ganso e por luvas A ausência de 213 arredondada de 2125 calças resultará em um custo de multa de 213 x 10 2130 TAHA 2008 32 Modelo de produção e estoque para vários períodos Novamente usaremos os estudos de Taha 2008 para exemplificar mais esse cenário de planejamento de produção A Esquadril CO firmou um contrato para entrega de janelas de casa para os próximos seis meses As demandas para cada mês são de 100 250 190 140 220 e 110 unidades respectivamente O custo de produção por janela varia de mês para mês dependendo do custo da mão de obra do material e de utilidades A empresa estima que o custo de produção por janela nos próximos seis meses seja 50 45 55 48 52 e 50 respectivamente Para aproveitar a vantagem das variações no custo de fabricação a Acme pode optar por produzir mais do que o necessário em determinado mês e reter as unidades excedentes para entregar em meses posteriores Entretanto isso incorrerá em custos de armazenagem de 8 por janela por mês considerando o estoque no final do mês Desenvolva um modelo de programação linear para determinar a programação ótima de produção Modelo matemático As variáveis do problema incluem a quantidade de produção mensal e o estoque no final do mês Para i 1 2 6 Seja xi número de unidades produzidas no mês í Ii número de unidades deixadas no estoque no final do mês i A relação entre essas variáveis e a demanda mensal para a projeção de seis meses é representada pelo gráfico esquemático da Figura 1 O sistema começa vazio o que significa que I0 0 Figura 1 Representação esquemática do sistema de produção e estoque Fonte Taha 2008 A função objetivo procura minimizar a soma dos custos de produção e de estoque Aqui temos Custo total de produção 50x1 45x2 55x3 48x4 52x5 50x6 Custo total de estoque 8I1 I2 I3 I4 I5 I6 Dessa maneira a função objetivo é Minimizar z 50x1 45x2 55x3 48x4 52x5 50x6 8I1 I2 I3 I4 I5 I6 As restrições do problema podem ser determinadas diretamente de acordo com a representação na Figura 25 Para cada período temos a seguinte equação de equilíbrio Estoque inicial Quantia produzida Estoque final Demanda Essa relação é expressa matematicamente para cada um dos meses como I0 x1 I1 100 Mês 1 I1 x2 I2 250 Mês 2 I2 x3 I3 190 Mês 3 I3 x4 I4 140 Mês 4 I4 x5 I5 220 Mês 5 I5 x6 I6 110 Mês 6 xi li 0 para todo i 126 I0 0 Para o problema I0 0 porque a situação parte de zero de estoque inicial Ademais em qualquer solução ótima o estoque final 16 será zero uma vez que não é lógico terminar a projeção com estoque positivo cujo único efeito seria incorrer em custo adicional de estoque sem atender a nenhuma finalidade Agora o modelo completo é dado por Minimizar z 50x1 45x2 55x3 48x4 52x5 50x6 8I1 I2 I3 I4 I5 I6 Sujeito a x1 I1 100 Mês 1 I1 x2 I2 250 Mês 2 I2 x3 I3 190 Mês 3 I3 x4 I4 140 Mês 4 I4 x5 I5 220 Mês 5 I5 x6 I6 110 Mês 6 xi li 0 para todo i 126 Solução A solução ótima está resumida na Figura 2 Ela mostra que a demanda de cada mês é satisfeita diretamente pela produção do mês exceto no mês 2 cuja quantidade produzida de 440 unidades abrange a demanda para ambos os meses 2 e 3 O custo total associado e Z 49980 TAHA 2008 Figura 2 Solução ótima para o problema de produção e estoque Fonte Taha 2008 30 Pesquisa Operacional 4 Probelma da mistura e refi nação Várias aplicações de PL tratam da mistura de diferentes materiais de entrada para produzir produtos que obedeçam a certas especifi cações e ao mesmo tempo minimizar o custo ou maximizar o lucro Os materiais de entrada podem ser minérios sucatas de metal produtos químicos ou óleos crus e os produtos de saída podem ser lingotes de metal tintas ou gasolina de vários graus Uma meta do modelo é determinar o mix ótimo de produtos fi nais que maximizará uma função lucro adequada Em alguns casos a meta pode ser minimizar uma função custo 41 Refi nação de óleo cru e mistura de gasolinas Para exemplifi car usaremos um exercício resolvido de Taha 2008 A Petrobrazuca tem uma capacidade de 1500000 barris de óleo cru por dia Entre os produtos fi nais da refi naria estão três tipos de gasolina sem chumbo com diferentes octanagens ON normal com ON 87 premium com ON 89 e super com ON 92 O processo de refi nação abrange três estágios 1 uma torre de destilação que produz fração ON 82 à razão de 02 barris por barris de óleo cru 2 uma unidade de craqueamento que produz frações de gasolina ON 98 usando uma porção da fração produzida na torre de destilação à taxa de 05 barris por barris de fração e 3 uma unidade misturadora que mistura a fração de gasolina da unidade de craqueamento com a fração da torre de destilação A empresa estima o lucro líquido por barril dos três tipos de gasolina em 670 720 e 810 respectivamente A capacidade de entrada da unidade de craqueamento e 200000 barris de fração por dia Os limites da demanda para gasolina comum premium e super são 50000 30000 e 40000 barris por dia Desenvolva um modelo para determinar a programação ótima de produção para a refi naria A Figura 3 resume os elementos do modelo Figura 3 Representação matemática da fábrica da Petrobrazuca Fonte Taha 2008 As variáveis podem ser defi nidas em termos das duas correntes de entrada para a unidade de mistura fração e gasolina craqueada e dos três produtos fi nais Seja xij barrisdia da corrente de entrada i usada para misturar o produto fi nal j i 1 2 j 1 2 3 Usando essa defi nição temos Produção diária de gasolina comum x11 x21 barris dia Produção diária de gasolina premium x12 x22 barris dia Produção diária de gasolina super x13 x23 barrisdia Tabela 3 equações auxiliares Produção diária da unidade misturadora produção diária da gasolina comum produção diária da gasolina pre mium produção diária da gasolina super x11 x21 x12 x22 x13 x23 barrisdia Alimenta ção diária de fração para a unidade misturadora x11 x12 x13 barrisdia Alimenta ção diária da unida de de craqueamen to para a unidade misturadora x21 x22 x23 barrisdia Alimenta ção diária da fração para a unidade de craqueamento 2x21 x22 x23 barrisdia Quan tidade diária de óleo cru usado na refi naria 5x11 x12 x13 10x21 x22 x23 barrisdia Fonte adaptado de Taha 2008 O objetivo do modelo é maximizar o lucro total resultante da venda de todos os três tipos de gasolina Pelas defi nições dadas obtemos Maximizar z 670x11 x21 720x12 x22 810x13 x23 As restrições do problema são desenvolvidas da seguinte maneira 1 Fornecimento diário de óleo em não deve exceder 1500000 barrisdia 5x11 x12 x13 10x21 x22 x23 1500000 2 Capacidade de entrada da unidade de craqueamento não deve exceder 200 000 barrisdia 2x21 x22 x23 200000 3 Demanda diária para gasolina comum não deve exceder 50000 barrisdia 31 x11 x21 50000 4 Demanda diária para gasolina premium não deve exceder 30000 barrisdia x12 x22 30000 5 Demanda diária para gasolina super não deve exceder 40000 barrisdia x13 x23 40000 6 Octanagem para gasolina comum é no mínimo 87 A octanagem de uma gasolina ON é a média ponderada das octanagens das correntes de entrada usadas no processo de mistura e pode ser calculada como TAHA 2008 ON da fração x barrisdia de fração ON da unidade de craqueamento x barrisdia da unidade de craqueamento Total de barrisdia de gasolina comum 82x11 98x21 x11 x21 87 A restrição é linearizada como 82x11 98x21 87x11 x21 7 Octanagem para premium é no mínimo 89 82x12 98x22 x12 x22 89 A restrição é linearizada como 82x12 98x22 89x12 x22 8 Octanagem para super é no mínimo 92 82x13 98x23 x13 x23 92 A restrição é linearizada como 82x13 98x23 92x13 x23 Assim o modelo completo é resumido como Maximizar z 670x11 x21 720x12 x22 810x13 x23 Sujeito a 5x11 x12 x13 10x21 x22 x23 1500000 2x21 x22 x23 200000 x11 x21 50000 x12 x22 30000 x13 x23 40000 82x11 98x21 87x11 x21 82x12 98x22 89x12 x22 82x13 98x23 92x13 x23 x11 x12 x13 x21 x22 x23 0 Solução Lucro diário 87500000 Quantidade diária de gasolina comum 50000 barris dia Quantidade diária de gasolina premium 30000 barris dia Quantidade diária de gasolina super 40000 barrisdia Ao chegar ao fi nal da terceira aula vamos recordar o que aprendemos Retomando a aula 01 Modelagem em planejamento urbano Nesta seção vimos quais são os desafi os da área de planejamento urbano e na sequência um exemplo resolvido de uma aplicação de planejamento urbano Esse exemplo resolvido serve de base para podermos aplicar a pesquisa operacional em situações similares usando a programação linear para encontro das soluções ótimas 02 Modelagem em investimento Similar à seção 01 aqui estudamos um modelo de programação linear em um problema de investimento Através desse exemplo temos uma base de como identifi car as restrições e a funçãoobjetivo mais adequada na hora de montar nosso modelo de programação linear 03 Programação linar e planejamento de produção Nesta seção abordamos dois exemplos de aplicação de programação linear em planejamento de produção Em um dos casos temos um planejamento da produção em um único período e n o outro temos o planejamento da produção em vários períodos 04 Probelma da mistura e refi nação Por fi m nesta última seção vimos um exemplo de problema da mistura Ainda vimos como montar as restrições e função objetivo nesse tipo de problema tão comum nas indústrias químicas e de alimentos Hillier FS e Lieberman GJ Introdução à Pesquisa Operacional 8ª edição São Paulo McGrawHill 2006 Lachtermacher G Pesquisa operacional na tomada de decisões 5ª edição São Paulo Prentice Hall 2016 Taha H A Pesquisa Operacional 8ª edição São Paulo Pearson 2008 Vale a pena ler Vale a pena