Oficina 2: Programação Linear e Maximização de Lucros

Pesquisa Operacional Oficina 2 Programação Linear Prof Victor Diogho Heuer de Carvalho Campus do Sertão Universidade Federal de Alagoas Conteúdo da Oficina 2 Programação Linear Relembrando os pressupostos do modelo Exemplos de Problemas de Minimização e Maximização Exemplo de Resolução Gráfica Esta Foto de Autor Desconhecido está licenciado em CC BYND Relembrando os Pressupostos da Programação Linear Aditividade Proporcionalidade Divisibilidade Certeza Programação Linear Retomemos o exemplo de Regsdale 2009 A Blue Ridge Hot Tubs fabrica e vende dois modelos de banheiras a AquaSpa e a HydroLux Howie Jones proprietário e gerente da empresa precisa decidir quanto de cada tipo de banheira produzir em seu ciclo de produção Howie compra cubas de fibra de vidro préfabricadas de um fornecedor local e adiciona a elas a bomba e a tubulação para criar suas banheiras Esse fornecedor pode abastecer Howie com quantas cubas ele precisar Howie instala o mesmo tipo de bomba em ambos os modelos de banheira Ele terá apenas 200 bombas disponíveis durante seu próximo ciclo de produção Do ponto de vista da fabricação a principal diferença entre os dois modelos de banheira é a quantidade de tubulação e de trabalho necessários Cada AquaSpa requer nove horas de trabalho e 12 pés de tubulação Cada HydroLux requer seis horas de trabalho e 16 pés de tubulação Howie espera ter 1566 horas de trabalho de produção e 2880 pés de tubulação disponíveis durante o próximo ciclo de produção Howie tem lucro de 35000 em cada AquaSpa que vende e 30000 em cada HydroLux comercializada Perguntase quantas AquaSpas e HydroLuxes devem ser produzidas se quisermos maximizar os lucros durante o próximo ciclo de produção Etapas da Formulação do Modelo Matemático 1ª Etapa Entenda o problema Qual o seu objetivo Entender quantas banheiras de cada tipo deverão ser produzidas para maximizar o lucro dadas as restrições de horas de trabalho e de materiais de produção 2ª Etapa Quais as Variáveis de Decisão As variáveis de decisão estão relacionadas ao que se quer produzir para que se obtenha lucro as banheiras AquaSpas que chamaremos na modelagem de X1 e HydroLuxes que chamaremos de X2 3ª Etapa Determine a Função objetivo como uma combinação linear das variáveis definidas No exemplo trabalhado em cada AquaSpa é obtido um lucro de 350 e em cada Hydro Lux o lucro é de 300 Como o objetivo é maximizar o lucro total a função objetivo será Max Z 350X1 300X2 Etapas da Formulação do Modelo Matemático 4ª Etapa As restrições serão combinações lineares das variáveis de decisão São enfrentadas 3 restrições destacadas no exemplo Com apenas 200 bombas disponíveis e cada banheira requer uma bomba não podem ser produzidas mais que 200 banheiras X1 X2 200 o que indica que cada unidade de X1 e de X2 usará uma das 200 bombas disponíveis de forma que o numero total de bombas usadas deve ser menor ou igual a 200 Há 1566 horas de trabalho disponíveis durante o próximo ciclo de produção de forma que cada unidade de X 1 requer 9 horas de trabalho e cada unidade de X2 requer 6 horas e trabalho 9X1 6X2 1566 onde o numero total de horas usado por cada unidade de X1 e X2 deverá ser menor ou igual a quantidade máxima de 1566 horas de trabalho Apenas 2880 pés de tubulação está disponíveis cada unidade de X1 requer 12 pés e cada unidade de X2 requer 16 pés 12X1 16X2 2880 onde o numero total de pés utilizados por cada unidade de X1 e X2 deve ser menor ou igual a 2880 Etapas da Formulação do Modelo Matemático 5ª Etapa Identifique quaisquer vínculos nas variáveis de decisão Neste para X1 e X2 é impossível produzir um número negativo e banheiras logo X1 0 e X2 0 Modelo Matemático em Função dos dois produtos da Blue Ridge Hot Tubs Max Z 350X1 300X2 Sujeito a X1 X2 200 9X1 6X2 1566 12X1 16X2 2880 X1 0 X2 0 Resolução Gráfica Tenhamos em mente que o modelo matemático é um conjunto de funções lineares logo cada função incluindo a Função Objetivo descreve uma reta Será a partir dos cruzamentos entre as retas das restrições de acordo com suas desigualdades que conseguiremos determinar a Região Factível que conterá a solução para o problema Resolução Gráfica Nomeando as restrições como R1 X1 X2 200 R2 9X1 6X2 1566 R3 12X1 16X2 2880 Podemos encontrar seus cruzamentos resolvendo os sistemas R1 x R2 R1 x R3 R2 x R3 R1 X R2 𝑋 1 𝑋 2200 9 𝑋 16 𝑋 21566 Soluções X1 122 X2 78 R1 X R3 𝑋1 𝑋 2200 12 𝑋 116 𝑋 22880 Soluções X1 80 X2 120 R2 X R3 9 𝑋16 𝑋 21566 12 𝑋 116 𝑋 22880 Soluções X1 108 X2 99 Todo o Sistema O gráfico ao lado considera não só as retas que podem ser descritas substituindo as desigualdades por igualdades assim como a região factível que se obtém usando as desigualdades A reta em vermelho é a reta da Função Objetivo Demais pontos Ainda há outras possibilidades de pontos como as interseções de cada restrição com os eixos de X1 e X2 x e y por exemplo R1 e Eixo X1 fazendo X2 0 X1 0 200 X1 200 Logo o ponto seria 200 0 R3 e Eixo X2 fazendo X1 0 0 16X2 2880 X2 288016 X2 180 Logo o ponto seria 0 180 Solução do Problema da Blue Ridge Hot Tubs Considerando todos os pontos encontrados nos cruzamentos entre retas no contorno da região factível basta agora que encontremos o que produz o máximo valor usando a Função Objetivo Ponto no Gráfico X1 X2 Z 350X1 300X2 O 0 0 0 C 122 78 66100 D 120 80 64000 F 174 0 60900 H 0 180 54000 Exemplo de Problema de Minimização Uma granja quer misturar dois tipos de alimentos para criar um tipo especial de ração para suas galinhas poedeiras A primeira característica a ser atingida com a nova ração é o menor preço possível por unidade de peso Cada um dos alimentos contém os nutrientes necessários à ração final vamos chamalos de X Y e Z porém em proporções variáveis Cada 100g do Alimento 1 por exemplo possuem 10g do nutriente X 50g do nutriente Y e 40g do nutriente Z O Alimento 2 por sua vez para cada 100g possui 20g do nutriente X 60g do nutriente Y e 20g do nutriente Z Cada 100g do Alimento 1 custam para a granja R 060 enquanto que cada 100g do Alimento 2 custam R 080 A ração final deve ter no mínimo 2g de X 64g de Y e 34g de Z É preciso obedecer a essa composição minimizando ao mesmo tempo o custo por peso da nova ração Dados do problema de Minimização Composição por 100g Composição de nutrientes mínima em gramas Alimento 1 Alimento 2 X 10 20 2 Y 40 60 64 Z 50 20 34 Custo100g R 060 R 080 Outra característica importante definida no enunciado do problema o custo mínimo deve ser definido por peso logo por grama Isso nos leva a determinar para os Alimentos 1 e 2 os valores dos coeficientes das funções objetivo e restrições divididos por 100g Modelo Matemático Da tabela anterior podemos extrair de forma praticamente direta o nosso modelo matemático Min Z 060100X1 080100X2 Sujeito à 10100X1 20100X2 2 40100X1 60100X2 64 50100X1 20100X2 34 Resolução Gráfica O mesmo procedimento adotado antes pode ser aplicado no caso de minimização R1 01X1 02X2 2 R2 04X1 06X2 64 R3 05X1 02X2 34 R1 x R2 01 𝑋 102 𝑋 22 0 4 𝑋 106 𝑋 26 4 Soluções X1 X2 Resolver como exercício R1 x R3 01 𝑋 102 𝑋 22 05 𝑋 102 𝑋 234 Soluções X1 X2 Resolver como exercício R2 x R3 Soluções X1 X2 0 4 𝑋 106 𝑋 264 05 𝑋 102 𝑋 234 Resolver como exercício Gráfico do Problema de Minimização Solução do Problema da Granja Como exercício para a próxima aula Resolver os sistemas lineares para encontrar as interseções entre as retas Descobrir demais pontos por exemplo cruzamento de retas de restrições com os as retas dos eixos do gráfico Obter solução aplicando os valores de X1 e X2 em Z e determinando o mínimo custog Referências MOREIRA Daniel Augusto Pesquisa Operacional curso introdutório 2 ed São Paulo Cengage Learning 2010 REGSDALE Cliff T Modelagem e Análise da Decisão São Paulo Cengage Learning 2011 Autoria e Uso da Apresentação Esta apresentação foi desenvolvida pelo Prof Victor Diogho Heuer de Carvalho para uso na disciplina de Pesquisa Operacional e é propriedade do Group of Engineering in Decision Making and Artificial Intelligence GEDAI Todo uso deste material deverá fazer referência também ao seu autor e ao referido grupo Campus do Sertão Delmiro Gouveia