Slide - Seção 1 Modelagem 2020-2

Programa¸c˜ao Linear - ENP153 Prof. Dr. Alexandre Xavier Martins LASOS - DEENP - ICEA Modelagem Se¸c˜ao 1 Modelagem 2 / 24 Modelagem Modelagem Problema das ligas Met´alicas Uma metal´urgica deseja maximizar sua receita bruta. A Tabela 1 ilustra a propor¸c˜ao de cada material na mistura para a obten¸c˜ao das ligas poss´ıveis de fabrica¸c˜ao. O pre¸co est´a cotado em reais por tonelada da liga fabricada. Tamb´em em toneladas est˜ao expressas as restri¸c˜oes de disponibilidade de mat´erias-prima. Formular o modelo de programa¸c˜ao matem´atica que maximiza a receita da empresa 3 / 24 Modelagem Modelagem Problema das ligas Met´alicas Tabela: Parˆametros do Problema das ligas Met´alicas Liga Baixa Liga Alta Disponibilidade Resistˆencia Resistˆencia Cobre 0,50 0,20 16 ton Zinco 0,25 0,30 11 ton Chumbo 0,25 0,50 15 ton Lucro 3.000 5.000 4 / 24 Modelagem Modelagem Problema das ligas Met´alicas 1. Defini¸c˜ao da vari´avel (ou vari´aveis) de decis˜ao; 2. Formula¸c˜ao da fun¸c˜ao objetivo; 3. Formula¸c˜ao das restri¸c˜oes. 5 / 24 Modelagem Modelagem Problema das ligas Met´alicas ▶ Defini¸c˜ao da vari´avel de decis˜ao: para o problema em quest˜ao o tomador de decis˜oes deve decidir qual a quantidade de cada tipo de liga ele deve produzir. Seja xi a quantidade a ser produzida da liga i, onde i = 1 para a liga de baixa resistˆencia e i = 2 para a liga de alta resistˆencia. ▶ Formula¸c˜ao da fun¸c˜ao objetivo: o objetivo do tomador de decis˜oes no problema acima ´e definir valores para x1 e x2 de maneira que o lucro desta decis˜ao seja o maior poss´ıvel. Sabemos que para cada tonelada fabricada de x1 o retorno ´e de 3.000 enquanto para x2 o lucro ´e de 5.000. Dessa forma, podemos definir o nosso objetivo como maximizar Q(x) = 3.000x1 + 5.000x2. 6 / 24 Modelagem Modelagem Problema das ligas Met´alicas ▶ Defini¸c˜ao da vari´avel de decis˜ao: para o problema em quest˜ao o tomador de decis˜oes deve decidir qual a quantidade de cada tipo de liga ele deve produzir. Seja xi a quantidade a ser produzida da liga i, onde i = 1 para a liga de baixa resistˆencia e i = 2 para a liga de alta resistˆencia. ▶ Formula¸c˜ao da fun¸c˜ao objetivo: o objetivo do tomador de decis˜oes no problema acima ´e definir valores para x1 e x2 de maneira que o lucro desta decis˜ao seja o maior poss´ıvel. Sabemos que para cada tonelada fabricada de x1 o retorno ´e de 3.000 enquanto para x2 o lucro ´e de 5.000. Dessa forma, podemos definir o nosso objetivo como maximizar Q(x) = 3.000x1 + 5.000x2. 6 / 24 Modelagem Modelagem Problema das ligas Met´alicas ▶ Formula¸c˜ao das restri¸c˜oes: em nosso exemplo temos trˆes restri¸c˜oes associadas `a disponibilidade de mat´eria-prima. Pela Tabela 1 sabemos que para cada tonelada fabricada da liga de baixa resistˆencia (x1) s˜ao consumidas 0, 5 toneladas de cobre, enquanto para a outra liga (x2) s˜ao consumidas 0, 2 toneladas. Assim temos que 0, 5x1 + 0, 2x2 ≤ 16. As outras restri¸c˜oes que dizem respeito `as mat´erias-primas podem ser contru´ıdas de forma an´aloga, assim para o zinco temos que 0, 25x1 + 0, 3x2 ≤ 11 e para o chumbo temos 0, 25x1 + 0, 5x2 ≤ 15. Em todos os problemas de programa¸c˜ao linear, acrescentamos restri¸c˜oes triviais que chamamos de restri¸c˜oes de n˜ao-negatividade. Essas restri¸c˜oes indicam que as vari´aveis de decis˜ao n˜ao podem assumir valores negativos, assim temos que x1 ≥ 0 e x2 ≥ 0 7 / 24 Modelagem Modelagem Problema das ligas Met´alicas O modelo completo ´e dado a seguir: Maximize Q(x) = 3.000x1 + 5.000x2 Sujeito a: 0, 5x1 + 0, 2x2 ≤ 16 0, 25x1 + 0, 3x2 ≤ 11 0, 25x1 + 0, 5x2 ≤ 15 x1 ≥ 0, x2 ≥ 0 8 / 24 Modelagem Modelagem Problema do Planejamento de Produ¸c˜ao Uma determinada empresa est´a interessada em maximizar o lucro mensal proveniente de quatro de seus produtos, designados por I, II, III, IV. Para fabricar esses quatro produtos, ela utiliza dois tipos de m´aquinas (M1 e M2) e dois tipos de m˜ao-de-obra (MO1 e MO2). As disponibilidades destes recursos s˜ao apresentados na Figura 1. Os dados de utiliza¸c˜ao dos recursos para a produ¸cao de cada produto fornecidos pelo setor t´ecnico da empresa s˜ao dados pela Figura 2. O setor comercial da empresa forneceu as informa¸c˜oes referentes ao lucro de cada produto que ´e dado respectivamente por 10, 8, 9 e 7. Deseja-se saber a produ¸c˜ao mensal dos produtos I, II, III e IV para que o lucro mensal seja m´aximo. Formule um modelo de programa¸c˜ao linear que expresse o objetivo e as restri¸c˜oes desse empresa. 9 / 24 Modelagem Modelagem Problema do Planejamento de Produ¸c˜ao Lucro = 10, 8, 9 e 7 10 / 24 Modelagem Modelagem Problema do Planejamento de Produ¸c˜ao 11 / 24 Modelagem Modelagem Problema de importa¸c˜ao A OilCompany est´a construindo uma refinaria para fabricar 4 produtos: ´oleo diesel, gasolina, lubrificantes e combust´ıvel para jatos. A demanda m´ınima em barris/dia para cada um desses produtos ´e 14.000, 30.000, 10.000 e 8.000 respectivamente. A OilCompany tem contratos de fornecimento de ´oleo cru com o Ir˜a e Dubai. Ela deve receber no m´ınimo 40% do ´oleo cru do Ir˜a. Um barril de ´oleo cru do Ir˜a rende 0,2 barril de diesel, 0,25 barril de gasolina, 0,1 de lubrificante e 0,15 barril de combust´ıvel para jatos. Os rendimentos do ´oleo cru de Dubai s˜ao 0,1; 0,6; 0,15 e 0,1 respectivamente. Fa¸ca um modelo matem´atico para definir o m´ınimo que deve ser importado de cada fornecedor (em barris/dia). 12 / 24 Modelagem Modelagem Problema da dieta O objetivo do presente programa ´e determinar, em uma dieta para a redu¸c˜ao cal´orica, as quantidades de certos alimentos que dever˜ao ser ingeridos diariamente, de modo que determinados requisitos nutricionais sejam satisfeitos a custo m´ınimo. Suponha que uma certa dieta alimentar esteja restrita a leite desnatado, carne de boi, carne de peixe e uma salada de composi¸c˜ao conhecida. Sabendo-se ainda que os requisitos nutricionais ser˜ao expressos em termos de vitamina A, C e D e controlados por suas quantidades m´ınimas (em miligramas), uma vez que s˜ao indispens´aveis `a sa´ude da pessoa que estar´a se submetendo `a dieta. A Tabela 2 resume a quantidade de cada vitamina em disponibilidade nos alimentos e a sua necessidade di´aria para a boa sa´ude 13 / 24 Modelagem Modelagem Problema da dieta Tabela: Parˆametros do Problema da Dieta Vitamina Leite (litro) Carne (Kg) Peixe (Kg) Salada (100g) Req. M´ın. A 2 mg 2 mg 10 mg 20 mg 11 mg C 50 mg 20 mg 10 mg 30 mg 70 mg D 80 mg 70 mg 10 mg 80 mg 250 mg Custo 2 4 1,5 1 14 / 24 Modelagem Modelagem Problema do s´ıtio Um sitiante est´a planejando sua estrat´egia de plantio para o pr´oximo ano. Por informa¸c˜oes obtidas nos ´org˜aos governamentais, sabe que as culturas de trigo, arroz e milho ser˜ao as mais rent´aveis na pr´oxima safra. Por experiˆencia, sabe que a produtividade de sua terra para as culturas desejadas ´e constante na tabela a seguir. Por falta de um local de armazenamento pr´oprio, a produ¸c˜ao m´axima, em toneladas, est´a limitada a 60 toneladas. A ´area cultiv´avel do s´ıtio ´e de 200.000m2. Para atender `as demandas de seu pr´oprio s´ıtio, ´e imperativo que se plante no m´ınimo 400m2 de trigo, 800m2 de arroz e 10.000m2 de milho. O objetivo ´e construir um modelo que maximize o lucro 15 / 24 Modelagem Modelagem Problema do s´ıtio Tabela: Parˆametros do Problema do s´ıtio Cultura Produtividade Lucro por em Kg por m2 Kg de produ¸c˜ao Trigo 0,2 10,80 Arroz 0,3 4,20 Milho 0,4 2,03 16 / 24 Modelagem Modelagem Problema da Mochila ▶ Imagine que um viajante deseja arrumar sua mochila: ▶ S´o existe uma mochila, que s´o pode levar b quilos ▶ Cada objeto que pode ser levado na mochila tem um certo peso wi ▶ Cada objeto i proporciona um benef´ıcio ci se for levado ▶ O problema consiste em escolher os objetos que trar˜ao o maior benef´ıcio poss´ıvel sem ultrapassar a capacidade da mochila 17 / 24 Modelagem Modelagem Problema da Mochila 18 / 24 Modelagem Modelagem Instˆancia do Problema da Mochila Objeto 1 2 3 4 5 6 7 8 9 10 11 12 13 14 Benef´ıcio 3 3 2 4 2 3 5 3 6 1 3 5 4 2 Peso 5 4 7 9 4 7 6 6 5 2 3 2 3 2 Capacidade da mochila b = 30 Modele o problema de maneira a maximizar o benef´ıcio respeitando a capacidade da mochila 19 / 24 Modelagem Modelagem Problema dos dep´ositos Uma rede de dep´ositos de material de constru¸c˜ao tem lojas que devem ser abastecidas com 50m3 (L1), 80m3 (L2), 40m3 (L3) e 100m3 (L4) de areia. Essa areia pode ser carregada em 3 portos P1, P2 e P3, cujas distˆancias `as lojas est˜ao na Tabela a seguir (em Km). Tabela: Parˆametros do Problema dos dep´ositos L1 L2 L3 L4 P1 30 20 24 18 P2 12 36 30 24 P3 8 15 25 20 O caminh˜ao pode transportar 10m3 por viagem. Os portos tˆem areia para suprir qualquer demanda. Construir um modelo de programa¸c˜ao linear que minimize a distˆancia total percorrida e supra a necessidade das lojas 20 / 24 Modelagem Modelagem Problema do corte de lingotes 21 / 24 Modelagem Modelagem Problema do corte de lingotes Uma empresa produz lingotes de a¸co de 7 tamanhos. Cada tamanho consome uma quantidade de a¸co da panela que tem disponibilidade de 45000 kg. Os tamanhos dos lingostes e seus respectivos pesos s˜ao apresentados na Tabela abaixo. A empresa deseja programar a produ¸c˜ao de lingotes com o objetivo de minimizar a sobra de a¸co na panela. Construa o modelo. Lingote 1 2 3 4 5 6 7 Tamanho(m) 8 8,2 8,4 8,6 8,8 9 9,2 Peso(kg) 1488 1525 1562 1599 1636 1674 1711 22 / 24 Modelagem Modelagem Problema das Minas e Usinas Uma empresa sider´urgica possui 3 usinas e cada uma delas requer quantidade mensal m´ınima de min´erio para operar. A empresa adquire min´erio de 4 minas diferentes. Cada uma das minas tem uma capacidade m´axima de produ¸c˜ao mensal estabelecida. Por imposi¸c˜oes contratuais, o custo do min´erio para a empresa ´e composto por um custo fixo mensal para cada mina (este valor ´e pago em caso de haver produ¸c˜ao na mina), mais um custo de transporte ($/t) que varia de acordo com a distˆancia entre as minas e usinas (cada par mina/usina tem um custo diferente). Os dados s˜ao mostrados na tabela a seguir: 23 / 24 Modelagem Modelagem Parˆametros do problema Mina/Usina Usina 1 Usina 2 Usina 3 Capacidade Custo Fixo Mina 1 10 8 13 11500 50000 Mina 2 7 9 14 14500 40000 Mina 3 6 10 12 13000 30000 Mina 4 8 12 9 12300 25500 Demanda 10000 15400 13300 - - 24 / 24