Introdução à Programação Inteira e Problemas Relacionados

Facens Programação Inteira PI Um problema de Programação Inteira é um problema de Programação Linear com a restrição adicional de que o valor todas as variáveis sejam números inteiros A primeira aproximação da solução de qualquer problema de Programação Inteira pode ser obtida ignorandose a restrição de valores inteiros e resolvendose o problema de programação linear pelas técnicas já apresentadas Programação Inteira Se a solução encontrada no problema de Programação Linear for inteira então esta solução é ótima senão podese arredondar a solução para os valores inteiros mais próximos e obter uma segunda aproximação Este procedimento é útil para soluções com valores grandes entretanto para números pequenos pode ser muito impreciso Programação Inteira Modelo de Programação Inteira 𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑎𝑟 𝑍 𝑐𝑥 𝑠𝑢𝑗𝑒𝑖𝑡𝑜 𝑎 𝐴𝑥 𝑏 𝑥 𝑍 𝑛 Programação Inteira Mista Um problema de PIM é um problema de PL que possui variáveis inteiras e reais e tem a seguinte forma 𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑎𝑟 𝑍 𝑐𝑥 𝑑𝑦 𝑠𝑢𝑗𝑒𝑖𝑡𝑜 𝑎 𝐴𝑥 𝐷𝑦 𝑏 𝑥 𝑅 𝑛 𝑦 𝑍 𝑛 Exemplo Modelo de Programação Inteira Resolva o seguinte problema de PI 𝑀𝑎𝑥 𝑍 10𝑥1 6𝑥2 𝑆𝑢𝑗𝑒𝑖𝑡𝑜 𝑎 9𝑥1 5𝑥2 45 4𝑥1 5𝑥2 5 𝑥 𝑍2 Somente variáveis inteiras Método Gráfico O último inteiro da função objetivo é o ponto 50 Z 50 Exercício PI Resolva o seguinte modelo 𝑀𝑎𝑥 𝑍 8𝑥1 6𝑥2 𝑆𝑢𝑗𝑒𝑖𝑡𝑜 𝑎 𝑥1 𝑥2 7 5𝑥1 3𝑥2 30 𝑥 𝑍2 Solução Gráfica X 4 3 Z 84 63 32 18 50 Exemplo Modelo de Programação Inteira Mista Resolva o seguinte problema de PL 𝑀𝑎𝑥 𝑍 10𝑥1 6𝑥2 𝑆𝑢𝑗𝑒𝑖𝑡𝑜 𝑎 9𝑥1 5𝑥2 45 4𝑥1 5𝑥2 5 𝑥1 𝑅1 𝑥2 𝑍1 Variável Real Variável Inteira Método Gráfico Solução ótima no ponto Q X 333 3 Z 5133 Exercício PI Resolva o seguinte modelo 𝑀𝑎𝑥 𝑍 4𝑥1 7𝑥2 𝑆𝑢𝑗𝑒𝑖𝑡𝑜 𝑎 𝑥1 𝑥2 9 𝑥1 3𝑥2 16 𝑥1 𝑅1 𝑥2 𝑍1 Solução Gráfica X 63 Z 46 73 24 21 45 Exercício 1 Programação Inteira Um fabricante de óleo está programando a produção para o próximo mês em uma de suas fábricas Atualmente a fábrica produz os óleos 5W30 e 15W30 A produção é vendida somente para lojas no atacado em caixas Cada caixa gera um lucro de R 1200 para o óleo 5W30 e R 1000 para o óleo 15W30 Cada caixa de óleo consome respectivamente 10 horas e 8 horas de trabalho em que a planta possui instalada a capacidade de trabalhar até 40000 horas Os produtos são sintéticos e utilizam respectivamente 14 e 16 litros de matéria prima com compra mensal de matéria prima programada para 70000 litros As demandas máximas mensais são 3500 caixas para cada um dos óleos Considerando as caixas como unidades inteiras formule um modelo de programação linear inteira para maximizar o lucro e resolva graficamente Exercício 2 Programação Inteira Mista O mesmo fabricante de óleo do exercício anterior está programando a produção para o próximo mês em uma outra fábrica Nesta planta é feito o óleo 15W50 para motores à Diesel O produto é trabalhado em duas configurações envasado em caixas de 20 litros para ser vendido a comerciantes em geral e à granel que é vendido diretamente a transportadoras em grande quantidade Cada litro vendido em caixa gera um lucro de R 170 e cada litro vendido à granel gera um lucro R 150 Cada litro de óleo consome respectivamente 04 horas mais tempo pelo envase e 03 horas de trabalho a planta possui instalada a capacidade de trabalhar até 50000 horas As demandas máximas mensais são 100000 litros para óleo envasado 5000 caixas e de 80000 litros para óleo à granel Formule um modelo de programação linear inteira mista para maximizar o lucro e resolva graficamente Exercícios 3 Um carpinteiro possui 6 peças de madeira e dispõe de 28 horas de trabalho para confeccionar biombos ornamentais Dois modelos venderam muito bem no passado de maneira que ele se limitou a esses dois tipos Ele estima que o modelo I requer 2 peças de madeira e 7 horas de trabalho enquanto o modelo II necessita de 1 peça de madeira e 8 horas de trabalho Os preços dos modelos são respectivamente 120 e 80 reais Quantos biombos de cada modelo o carpinteiro deve montar se desejar maximizar o rendimento obtido com as vendas Modelo como um problema de Programação Inteira Exercícios 4 Um artesão produz dois tipos de jogos para crianças e vende para lojas em todo o país A demanda excede a capacidade produtiva entretanto o artesão continua a trabalhar sozinho durante 50 horas por semana O jogo I requer 35horas para ser confeccionado e propicia um lucro de R 2800 enquanto o jogo II precisa de 4 horas para ser produzido e gera um lucro de R 3100 O jogo I consome 3 partes de madeira e o jogo II consome 45 partes de madeira o artesão compra semanalmente 50 partes de madeira Qual quantidade de cada modelo deve ser produzido durante a semana se o objetivo é maximizar o lucro Modele como um problema de Programação Inteira Facens