Prévia do material em texto
<p>Aula 1 - Introducao a Programacao Linear - Modelagem</p><p>Matematica</p><p>Pesquisa Operacional I (Centro Federal de Educação Tecnológica Celso Suckow da</p><p>Fonseca)</p><p>Digitalizar para abrir em Studocu</p><p>A Studocu não é patrocinada ou endossada por nenhuma faculdade ou universidade</p><p>Aula 1 - Introducao a Programacao Linear - Modelagem</p><p>Matematica</p><p>Pesquisa Operacional I (Centro Federal de Educação Tecnológica Celso Suckow da</p><p>Fonseca)</p><p>Digitalizar para abrir em Studocu</p><p>A Studocu não é patrocinada ou endossada por nenhuma faculdade ou universidade</p><p>Baixado por Ellen S. (ellenzinhasds1@gmail.com)</p><p>lOMoARcPSD|44569012</p><p>https://www.studocu.com/pt-br?utm_campaign=shared-document&utm_source=studocu-document&utm_medium=social_sharing&utm_content=aula-1-introducao-a-programacao-linear-modelagem-matematica</p><p>https://www.studocu.com/pt-br/document/centro-federal-de-educacao-tecnologica-celso-suckow-da-fonseca/pesquisa-operacional-i/aula-1-introducao-a-programacao-linear-modelagem-matematica/17878744?utm_campaign=shared-document&utm_source=studocu-document&utm_medium=social_sharing&utm_content=aula-1-introducao-a-programacao-linear-modelagem-matematica</p><p>https://www.studocu.com/pt-br/course/centro-federal-de-educacao-tecnologica-celso-suckow-da-fonseca/pesquisa-operacional-i/4971286?utm_campaign=shared-document&utm_source=studocu-document&utm_medium=social_sharing&utm_content=aula-1-introducao-a-programacao-linear-modelagem-matematica</p><p>https://www.studocu.com/pt-br?utm_campaign=shared-document&utm_source=studocu-document&utm_medium=social_sharing&utm_content=aula-1-introducao-a-programacao-linear-modelagem-matematica</p><p>https://www.studocu.com/pt-br/document/centro-federal-de-educacao-tecnologica-celso-suckow-da-fonseca/pesquisa-operacional-i/aula-1-introducao-a-programacao-linear-modelagem-matematica/17878744?utm_campaign=shared-document&utm_source=studocu-document&utm_medium=social_sharing&utm_content=aula-1-introducao-a-programacao-linear-modelagem-matematica</p><p>https://www.studocu.com/pt-br/course/centro-federal-de-educacao-tecnologica-celso-suckow-da-fonseca/pesquisa-operacional-i/4971286?utm_campaign=shared-document&utm_source=studocu-document&utm_medium=social_sharing&utm_content=aula-1-introducao-a-programacao-linear-modelagem-matematica</p><p>Introdução à Programação Linear</p><p>Modelagem Matemática</p><p>Baixado por Ellen S. (ellenzinhasds1@gmail.com)</p><p>lOMoARcPSD|44569012</p><p>MODELAGEM MATEMÁTICA</p><p>Um modelo é uma representação simplificada de um sistema real, que preserva</p><p>alguma equivalência em determinados contextos. Modelos são usados nas mais</p><p>diversas situações, tendo papel ímpar no processo de compreensão de um sistema em</p><p>estudo. A partir de um modelo válido é possível tirar conclusões a serem usadas no</p><p>projeto e na operação destes sistemas. Experimentos podem ser realizados com o</p><p>modelo e hipóteses podem ser testadas para obter resultados aplicáveis ao sistema</p><p>real.</p><p>Inúmeros são exemplos de modelos usados nas mais diversas áreas do conhecimento.</p><p>Maquetes, plantas baixas, fotografias, mapas, simuladores de direção usados em</p><p>autoescolas, e jogos de vídeo game são modelos com os quais frequentemente nos</p><p>deparamos. Cada um deles, à sua maneira, procura representar uma dada realidade.</p><p>2</p><p>Baixado por Ellen S. (ellenzinhasds1@gmail.com)</p><p>lOMoARcPSD|44569012</p><p>MODELAGEM MATEMÁTICA</p><p>As vantagens no uso de um modelo residem na redução dos custos, dos riscos e do</p><p>tempo necessário para testar hipóteses diretamente no sistema real. Imagine se, para</p><p>testar as estruturas de um prédio, tivéssemos que construir e submetê-lo a ensaios</p><p>destrutivos até que o mesmo não mais suportasse. Por razões óbvias, esta não é uma</p><p>boa maneira de estudar o problema real.</p><p>O que se espera desta representação substitutiva é que ela incorpore todas as</p><p>características e propriedades relevantes para o tomador de decisão, uma vez que é</p><p>praticamente impossível (e até mesmo desnecessário) modelar todos os fatores</p><p>intervenientes no sistema e em seu comportamento. Devem ser considerados apenas</p><p>os elementos e características fundamentais, simplificando assim o posterior processo</p><p>de resolução e análise.</p><p>3</p><p>Baixado por Ellen S. (ellenzinhasds1@gmail.com)</p><p>lOMoARcPSD|44569012</p><p>MODELAGEM MATEMÁTICA</p><p>Antes de usar um modelo é preciso realizar um processo de verificação de sua</p><p>representatividade denominado validação do modelo. Nesta etapa do estudo as</p><p>equipes responsáveis verificam a compatibilidade dos resultados obtidos pelo o</p><p>modelo com observações do sistema real. Se no processo de validação foram</p><p>identificadas incorreções, o modelo é reformulado, e uma nova etapa de simulações e</p><p>validação é realizada.</p><p>A descrição e a análise de fenômenos naturais, sociais ou econômicos não raro recorre</p><p>à matemática. A partir da observação dos respectivos sistemas reais, buscam-se as</p><p>“leis” que os regem. Leis expressas na forma de relações matemáticas, caracterizando</p><p>então um modelo matemático do sistema em estudo.</p><p>4</p><p>Baixado por Ellen S. (ellenzinhasds1@gmail.com)</p><p>lOMoARcPSD|44569012</p><p>MODELAGEM MATEMÁTICA</p><p>Neste ponto da discussão é importante estabelecermos as diferenças entre dois</p><p>conceitos fundamentais: modelo e formulação. O modelo é resultado de um conjunto</p><p>de premissas e condições de contorno que refletem as características de interesse, ao</p><p>passo que a formulação é sua tradução através de um conjunto de equações,</p><p>inequações e outras estruturas matemáticas usadas na representação. Em muitos</p><p>trabalhos essa distinção entre formulação e modelo não está muito clara, mas neste</p><p>ela será sempre considerada.</p><p>Não raro dois modeladores produzem formulações diferentes para o mesmo modelo,</p><p>ambas válidas e capazes de oferecer as mesmas respostas. Entretanto, é natural que</p><p>alguns modelos sejam melhores que outros, segundo algum critério, como facilidade</p><p>de compreensão ou de resolução.</p><p>5</p><p>Baixado por Ellen S. (ellenzinhasds1@gmail.com)</p><p>lOMoARcPSD|44569012</p><p>MODELAGEM MATEMÁTICA</p><p>A modelagem de problemas quantitativos pode ser considerada uma arte, pois não há</p><p>regras objetivas sobre como representar um dado sistema real. Ela envolve intuição,</p><p>experiência, criatividade e poder de síntese. A multidisciplinaridade das equipes de</p><p>modeladores e tomadores de decisão também contribui para a qualidade do modelo e</p><p>das respostas por ele produzidas.</p><p>Como se trata de uma atividade tipicamente subjetiva é natural que algumas pessoas</p><p>tenham mais habilidade que outras. Mas, sempre é possível melhorar mediante treino</p><p>e leitura. Dicas gerais de modelagem podem ser encontradas em diversos livros de</p><p>Pesquisa Operacional e, mais especificamente, de Programação Linear.</p><p>6</p><p>Baixado por Ellen S. (ellenzinhasds1@gmail.com)</p><p>lOMoARcPSD|44569012</p><p>MODELAGEM MATEMÁTICA</p><p>7</p><p>Definição do problema</p><p>Construção do modelo inicial</p><p>Construção da formulação inicial</p><p>Validação</p><p>Aplicação</p><p>Redefinição das</p><p>características de</p><p>interesse, premissas e</p><p>condições de contorno.</p><p>Redefinição das variáveis</p><p>de decisão e/ou das</p><p>restrições.</p><p>Experimentação</p><p>A Figura 1 ilustra, em linhas gerais, o processo de construção de modelos matemáticos.</p><p>Baixado por Ellen S. (ellenzinhasds1@gmail.com)</p><p>lOMoARcPSD|44569012</p><p>EXEMPLO 1 – Planejamento do Mix de Produção</p><p>Uma companhia fabrica 2 produtos a partir de três matérias primas conforme</p><p>mostra a tabela abaixo :</p><p>Nas colunas “Produto 1” e “Produto 2” são dados, além das receitas unitárias de</p><p>venda, as quantidades de matéria prima necessárias para produzir uma tonelada</p><p>de cada um dos produtos.</p><p>Quanto se deve produzir de cada produto para maximizar a receita de vendas e</p><p>respeitar as restrições de disponibilidade das matérias primas?</p><p>Baixado por Ellen S. (ellenzinhasds1@gmail.com)</p><p>lOMoARcPSD|44569012</p><p>EXEMPLO 1 - Resolução</p><p>Variáveis de decisão</p><p>quantidade do produto a ser produzida,</p><p>Função objetivo: Maximizar a receita de vendas.</p><p>Restrições: Disponibilidade de matéria prima.</p><p>Declaração das variáveis: não-negativas.</p><p>Baixado por Ellen S. (ellenzinhasds1@gmail.com)</p><p>lOMoARcPSD|44569012</p><p>EXEMPLO 1 - Resolução</p><p>Formulação matemática</p><p>Baixado por</p><p>Ellen S. (ellenzinhasds1@gmail.com)</p><p>lOMoARcPSD|44569012</p><p>EXEMPLO 2 – Problema do Transporte</p><p>A P&T COMPANY produz ervilhas em lata em três fábricas (perto de Bellingham,</p><p>Washington; Eugene, Oregon; e Albert Lea, Minnesota), que depois são enviadas</p><p>de caminhão para quatro armazéns de distribuição no oeste dos Estados Unidos</p><p>(Sacramento, Califórnia; Salt Lake City, Utah; Rapid City, Dakota do Sul; e</p><p>Albuquerque, Novo México). Para a próxima temporada foi feita uma estimativa</p><p>da produção de cada fábrica de conservas, e a cada armazém foi alocada uma</p><p>parte do suprimento total de ervilhas. Essa informação, em número de caminhões</p><p>cheios, juntamente com os custos de expedição de um caminhão nas rotas entre</p><p>fábricas de conserva e armazéns é apresentada no grafo da figura seguinte.</p><p>Escreva um PPL para gerar um plano de distribuição entre fábricas e armazéns que</p><p>minimiza o custo total, atendendo integralmente às demandas e respeitando as</p><p>capacidades das fábricas.</p><p>Baixado por Ellen S. (ellenzinhasds1@gmail.com)</p><p>lOMoARcPSD|44569012</p><p>EXEMPLO 2 – Problema do Transporte</p><p>Baixado por Ellen S. (ellenzinhasds1@gmail.com)</p><p>lOMoARcPSD|44569012</p><p>EXEMPLO 2 - Resolução</p><p>Variáveis de decisão</p><p>quantidade de caminhões enviados da fábrica para o cliente tal que</p><p>e</p><p>Função objetivo: Minimizar o custo total de distribuição.</p><p>Restrições:</p><p>Baixado por Ellen S. (ellenzinhasds1@gmail.com)</p><p>lOMoARcPSD|44569012</p><p>EXEMPLO 2 - Resolução</p><p>R1) Atendimento das demandas dos armazéns</p><p>R2) Capacidade das fábricas</p><p>R3) Declaração das variáveis: não negativas.</p><p>Baixado por Ellen S. (ellenzinhasds1@gmail.com)</p><p>lOMoARcPSD|44569012</p><p>EXEMPLO 2 - Resolução</p><p>Formulação matemática: min 𝑧 = 464𝑥 + 513𝑥 + 654𝑥 + 867𝑥 + 352𝑥 + 416𝑥 + 690𝑥+ 791𝑥 + 995𝑥 + 682𝑥 + 288𝑥 + 685𝑥s.a.: 𝑥 + 𝑥 + 𝑥 = 80𝑥 + 𝑥 + 𝑥 = 65𝑥 + 𝑥 + 𝑥 = 70𝑥 + 𝑥 + 𝑥 = 85𝑥 + 𝑥 + 𝑥 + 𝑥 = 75𝑥 + 𝑥 + 𝑥 + 𝑥 = 125𝑥 + 𝑥 + 𝑥 + 𝑥 = 100𝑥 , 𝑥 , … , 𝑥 ≥ 0</p><p>Baixado por Ellen S. (ellenzinhasds1@gmail.com)</p><p>lOMoARcPSD|44569012</p><p>EXEMPLO 3 – O Problema da Dieta</p><p>Um atleta deseja planejar sua refeição matinal diária a partir de 4 ingredientes:</p><p>gérmen de trigo, granola, queijo branco e iogurte. Obviamente, ele deseja que</p><p>esta refeição tenha o menor custo possível, mas que atenda as necessidades</p><p>básicas de calorias, carboidratos, proteínas e gorduras. A tabela a seguir mostra a</p><p>composição e o preço de cada um desses ingredientes:</p><p>Requisitos nutricionais sugerem que, no café da manhã, é preciso ingerir, no</p><p>mínimo, 50g de carboidratos e 40g de proteína, e, no máximo, 600 kcal e 15g de</p><p>gordura. Nessas condições, escreva um PPL para obter a quantidade ótima de</p><p>cada ingrediente.</p><p>Ingrediente Valor Calórico (kcal) Carboidratos (g) Proteínas (g) Gorduras (g) Custo (R$)</p><p>Gérmen de Trigo (100g) 313 48 51 4 3,2</p><p>Granola (100g) 400 65 10 10 4,5</p><p>Queijo Branco (100g) 190 3 13 13 3,8</p><p>Iogurte (100g) 150 25 4 4 1,8</p><p>Baixado por Ellen S. (ellenzinhasds1@gmail.com)</p><p>lOMoARcPSD|44569012</p><p>EXEMPLO 3 - Resolução</p><p>Variáveis de decisão:𝑥 = quantidade do alimento 𝑖 na refeição, 𝑖 = 1(gérmen), 2(granola), 3(queijo),4(iogurte).</p><p>Função objetivo: Minimizar o custo da refeição.min 𝑧 = 3,2𝑥 + 4,5𝑥 + 3,8𝑥 + 1,8𝑥</p><p>Restrições: Requisitos nutricionais (mínimos e máximos).48𝑥 + 65𝑥 + 3𝑥 + 25𝑥 ≥ 50 (carboidratos)51𝑥 + 10𝑥 + 13𝑥 + 4𝑥 ≥ 40 (proteínas)313𝑥 + 400𝑥 + 190𝑥 + 150𝑥 ≤ 600 (calorias)4𝑥 + 10𝑥 +13𝑥 + 4𝑥 ≤ 50 (gordura)</p><p>Declaração das variáveis: não-negativas.𝑥 , 𝑥 , 𝑥 , 𝑥 ≥ 0</p><p>Baixado por Ellen S. (ellenzinhasds1@gmail.com)</p><p>lOMoARcPSD|44569012</p><p>EXEMPLO 3 - Resolução</p><p>Formulação matemática:min 𝑧 = 3,2𝑥 + 4,5𝑥 + 3,8𝑥 + 1,8𝑥s. a. :48𝑥 + 65𝑥 + 3𝑥 + 25𝑥 ≥ 50 (carboidratos)51𝑥 + 10𝑥 + 13𝑥 + 4𝑥 ≥ 40 (proteínas)313𝑥 + 400𝑥 + 190𝑥 + 150𝑥 ≤ 600 (calorias)4𝑥 + 10𝑥 +13𝑥 + 4𝑥 ≤ 50 (gorduras)𝑥 , 𝑥 , 𝑥 , 𝑥 ≥ 0</p><p>Baixado por Ellen S. (ellenzinhasds1@gmail.com)</p><p>lOMoARcPSD|44569012</p><p>EXEMPLO 4 – Problema do Transporte com</p><p>Transbordo</p><p>Um fabricante de eletroeletrônicos opera duas fábricas, uma em Memphis e outra</p><p>em Denver. A fábrica de Memphis produz 120 unidades por dia, e a fábrica de</p><p>Denver produz 140 unidades por dia. A produção é enviada por via aérea para</p><p>clientes em Los Angeles e Boston, que requerem 130 unidades por dia cada.</p><p>Devido a uma desregulamentação das tarifas aéreas, a empresa acredita que pode</p><p>ser mais barato enviar primeiro algumas unidades para Nova York ou Chicago e só</p><p>depois para seus destinos finais. Os custos unitários de são mostrados abaixo.</p><p>CUSTOS</p><p>[$/un.] Memphis Denver N.Y. Chicago Los Angeles Boston</p><p>Memphis 0 - 8 13 25 28</p><p>Denver - 0 15 12 26 25</p><p>N.Y. - - 0 6 16 17</p><p>Chicago - - 6 0 14 16</p><p>Los Angeles - - - - 0 -</p><p>Boston - - - - - 0</p><p>Baixado por Ellen S. (ellenzinhasds1@gmail.com)</p><p>lOMoARcPSD|44569012</p><p>EXEMPLO 4 – Problema do Transporte com</p><p>Transbordo</p><p>A estrutura da rede logística considerada neste estudo é ilustrada no grafo</p><p>abaixo.</p><p>Deseja-se minimizar o custo total de transporte da produção das fábricas até os</p><p>clientes.</p><p>Baixado por Ellen S. (ellenzinhasds1@gmail.com)</p><p>lOMoARcPSD|44569012</p><p>EXEMPLO 4 - Resolução</p><p>Sejam e .</p><p>Variáveis de decisão𝑥 = quantidade de produto enviada através do arco (𝑖, 𝑗) ∈ 𝐴.</p><p>Função objetivo: Minimizar o custo total de distribuição.min 𝑧 = 8𝑥 , + 13𝑥 , + 25𝑥 , + 28𝑥 ,+15𝑥 , + 12𝑥 , + 26𝑥 , + 25𝑥 ,+6𝑥 , + 16𝑥 , + 17𝑥 ,+6𝑥 , + 14𝑥 , + 16𝑥 ,</p><p>Restrições:</p><p>Baixado por Ellen S. (ellenzinhasds1@gmail.com)</p><p>lOMoARcPSD|44569012</p><p>EXEMPLO 4 - Resolução</p><p>R1) Atendimento das demandas𝑥 , + 𝑥 , + 𝑥 , + 𝑥 , = 130𝑥 , + 𝑥 , + 𝑥 , + 𝑥 , = 130</p><p>R2) Capacidade das fábricas𝑥 , + 𝑥 , + 𝑥 , + 𝑥 , = 120𝑥 , + 𝑥 , + 𝑥 , + 𝑥 , = 140</p><p>R3) Transbordo𝑥 , + 𝑥 , + 𝑥 , − 𝑥 , − 𝑥 , − 𝑥 , = 0𝑥 , + 𝑥 , + 𝑥 , − 𝑥 , − 𝑥 , − 𝑥 , = 0</p><p>R4) Declaração das variáveis𝑥 ≥ 0, ∀(𝑖, 𝑗) ∈ 𝐴</p><p>Baixado por Ellen S. (ellenzinhasds1@gmail.com)</p><p>lOMoARcPSD|44569012</p><p>EXEMPLO 5 – Problema da Mistura</p><p>A empresa Steel recebeu um pedido de 500 toneladas de aço para construção naval, que deve ter</p><p>seguintes características:</p><p>A empresa emprega sete diferentes matérias-primas para a produção desse aço. A tabela abaixo</p><p>lista as qualidades, quantidades disponíveis e preços para todas as matérias-primas.</p><p>O objetivo é determinar a composição do aço que minimize o custo de produção.</p><p>Elemento químico Concentração mínima (%) Concentração máxima (%)</p><p>Carbono (C) 2 3</p><p>Cobre (Cu) 0,4 0,6</p><p>Manganês (Mn) 1,2 1,65</p><p>Ligas Carbono (%) Cobre (%) Manganês (%) Disponibilidade (ton) Custo ($/ton.)</p><p>Ferro 1 2,5 0 1,3 400 200</p><p>Ferro 2 3,0 0 0,8 300 250</p><p>Ferro 3 0 0,3 0 600 150</p><p>Cobre 1 0 90 0 500 220</p><p>Cobre 2 0 96 4,0 200 240</p><p>Alumínio 0 0,4 1,2 300 200</p><p>Alumínio 0 0,6 0 250 165</p><p>Baixado por Ellen S. (ellenzinhasds1@gmail.com)</p><p>lOMoARcPSD|44569012</p><p>EXEMPLO 5 - Resolução</p><p>Variáveis de decisão𝑥 = quantidade da liga 𝑖 usada na composição do aço, tal que 𝑖 = 1 ferro 1 ,2 ferro 2 , 3 ferro 3 , 4 cobre 1 , 5 cobre 2 , 6 alumínio 1 , 7 alumínio 2 .</p><p>Função objetivo: Minimizar o custo de composição da liga.min 𝑧 = 200𝑥 + 250𝑥 + 150𝑥 + 220𝑥 + 240𝑥 + 200𝑥 + 165𝑥</p><p>Restrições:</p><p>R1) Atendimento da demanda𝑥 + 𝑥 + ⋯ + 𝑥 = 500</p><p>Baixado por Ellen S. (ellenzinhasds1@gmail.com)</p><p>lOMoARcPSD|44569012</p><p>EXEMPLO 5 - Resolução</p><p>R2) Especificações do aço</p><p>0,025𝑥 + 0,03𝑥 ≥ 10</p><p>0,025𝑥 + 0,03𝑥 ≤ 15</p><p>0,003𝑥 + 0,90𝑥 + 0,96𝑥 + 0,004𝑥 + 0,006𝑥 ≥ 2</p><p>0,003𝑥 + 0,90𝑥 + 0,96𝑥 + 0,004𝑥 + 0,006𝑥 ≤ 3</p><p>0,013𝑥 + 0,008𝑥 + 0,04𝑥 + 0,012𝑥 ≥ 6</p><p>0,013𝑥 + 0,008𝑥 + 0,04𝑥 + 0,012𝑥 ≤ 8,25</p><p>R3) Disponibilidade das ligas𝑥 ≤ 400, 𝑥 ≤ 300, 𝑥 ≤ 600, 𝑥 ≤ 500, 𝑥 ≤ 200, 𝑥 ≤ 300, 𝑥 ≤ 250</p><p>R4) Declaração das variáveis���� , 𝑥 , … , 𝑥 ≥ 0</p><p>Baixado por Ellen S. (ellenzinhasds1@gmail.com)</p><p>lOMoARcPSD|44569012</p><p>HIPÓTESE DE LINEARIDADE</p><p>Um Problema de Programação de Linear (PPL) deve atender às seguintes</p><p>hipóteses:</p><p>Proporcionalidade: A contribuição de cada variável de decisão à fo e às restrições</p><p>é diretamente proporcional ao valor da variável.</p><p>Aditividade: A contribuição total das variáveis à fo e às restrições é igual</p><p>à soma</p><p>das contribuições individuais.</p><p>Fracionamento: As variáveis de decisão podem assumir valores fracionários.</p><p>Certeza: Os coeficientes das variáveis na fo e nas restrições são grandezas</p><p>conhecidas a priori, isto é, constantes.</p><p>Baixado por Ellen S. (ellenzinhasds1@gmail.com)</p><p>lOMoARcPSD|44569012</p><p>BIBLIOGRAFIA</p><p>• ARENALES, M. et al., Pesquisa Operacional para Cursos de Engenharia. Rio de Janeiro: Elsevier, 2007.</p><p>• GOLDBARG, M.C. e LUNA, H.P., Otimização Combinatória e Programação Linear. Rio de Janeiro: Elsevier,</p><p>2005.</p><p>• GUÉRET, C., PRINS, C., SEVAUX, M. Applications of Optimization with Xpress-MP. Dash Optimization Ltd.,</p><p>2007.</p><p>• HILLIER, Frederick S.; LIEBERMAN, Gerald J. Introdução à Pesquisa Operacional. São Paulo: Campus,</p><p>1988.</p><p>• TAHA, H.A., Pesquisa Operacional, 8. ed.. São Paulo: Pearson Prentice Hall, 2008.</p><p>• VILLELA, P. Notas de Aula. DEMAT/DEPES – CEFET/RJ.</p><p>• WINSTON, W. L. Operations Research: Applications and Algorithms, 4 ed. Duxbury Press, 2003.</p><p>50</p><p>Baixado por Ellen S. (ellenzinhasds1@gmail.com)</p><p>lOMoARcPSD|44569012</p>