Baixe o app para aproveitar ainda mais
Prévia do material em texto
Pesquisa Operacional – Aula 4 Profª. M.Sc. Júlia S. Humberto Plano de aula • Objetivo ─ Entendimento do aluno acerca de Modelagem de Problemas Gerenciais. • Conteúdos Programação linear: solução gráfica • Metodologia de Ensino – Aula expositiva • Atividades – Resolução de exercícios • Leitura Obrigatória – Nenhuma • Leitura Recomendada Revisão PROGRAMAÇÃO LINEAR A programação linear usa um modelo matemático para descrever o problema em questão. O adjetivo linear significa que todas as funções matemáticas nesse modelo são necessariamente funções lineares. A palavra programação, nesse caso, não se refere à programação e computador; ela é, essencialmente, um sinônimo para planejamento. Portanto, a programação linear envolve o planejamento de atividades para obter um resultado ótimo, isto é, um resultado que atinja o melhor objetivo especificado (de acordo como modelo matemático) entre todas as alternativas viáveis. Modelo de PL com duas variáveis Obter os dados básicos do problema • Estruturar o problema: – Variáveis de decisão – Função objetivo – Restrições técnicas – Resolução gráfica Passo a passo 1. Interpretar o problema de programação linear; 2. Identificar as variáveis de decisão 3. Estruturar a função objetivo para a geração do máximo lucro 4. Estipular as restrições técnicas do sistema em inequações 5. Resolver analiticamente as equações 6. Criar e plotar pares ordenados no plano cartesiano 7. Construir graficamente o problema 8. Localizar a área de solução no plano cartesiano 9. Determinar o máximo lucro de forma gráfica Exemplo: Companhia Reddy Mikks A Reddy Mikks produz tintas para interiores e exteriores com base em duas matérias-primas, M1 e M2. A tabela abaixo apresenta os dados básicos do problema: Produção de tintas da Reddy Mikks Toneladas de matéria-prima por tonelada de Disponibilidade máxima diária (ton) Tinta para exteriores Tinta para interiores Matéria prima, M1 6 4 24 Matéria prima, M2 1 2 6 Lucro por tonelada (R$ 1000) 5 4 Uma pesquisa de mercado indica que a demanda diária de tinta para interiores não pode ultrapassar a de tintas para exteriores por mais de 1 tonelada. Além disso, a demanda máxima diária de tinta para interiores é 2t. A Reddy Mikks quer determinar o mix ótimo (o melhor) de produtos de tintas para interiores e exteriores que maximize o lucro total diário. Exemplo 1ª etapa: Dados do problema 2ª etapa: Estruturar o problema a) Identificar as variáveis de decisão: X1 = toneladas de tinta para exteriores produzidas diariamente X2 = toneladas de tinta para interiores produzidas diariamente b) Definir a função objetivo: Maximizar Z = 5 𝑋1+ 4 𝑋2 c) Estipular as restrições técnicas: Restrição de disponibilidade diárias: – Matéria-prima M1: 6𝑋1 + 4𝑋2 ≤ 24 – Matéria-prima M2: 𝑋1 + 2𝑋2 ≤ 6 Restrição de demanda: - Limite de mercado: 𝑋2 − 𝑋1≤ 1 - Limite de demanda: 𝑋2 ≤ 2 Restrição de não negatividade: 𝑋1≥ 0 e 𝑋2 ≥ 0 Exemplo Modelo completo da Reddy Mikks: Maximizar Z = 5 𝑋1+ 4 𝑋2 Sujeito a: 6𝑋1 + 4𝑋2 ≤ 24 𝑋1 + 2𝑋2 ≤ 6 −𝑋1 − 𝑋2 ≤ 1 𝑋2 ≤ 2 𝑋1, 𝑋2 ≥ 0 (1) (2) (3) (4) (5) Exemplo 3ª etapa: Transformar inequações em equações: (1): 6𝑋1 + 4𝑋2 ≤ 24 6𝑋1 + 4𝑋2 = 24 (2): 𝑋1 + 2𝑋2 ≤ 6 𝑋1 + 2𝑋2 = 6 (3): −𝑋1 + 𝑋2 ≤ 1 −𝑋1 + 𝑋2 = 1 (4): 𝑋2 ≤ 2 𝑋2 = 2 Como 𝑋1 = 0 : 6 . (0) + 4𝑋2 = 24 Então: 𝑋2 = 24/4 = 6 Como 𝑋2 = 0 : 𝑋1 + 2 . (0) = 6 Então: 𝑋1 = 6 Mesmo raciocínio para os demais pontos. A (0, 6) B (4, 0) C (0, 3) D (6, 0) E (0, 1) F (2,5, 3,5) G (0,2) H (4,2) 𝑋_1 Exemplo 4ª etapa: Construir de forma gráfica 1 2 3 4 5 1 2 3 4 5 A (0, 6) B (4, 0) 𝑋1 𝑋2 C (0, 3) E (0, 1) 𝟏 𝟐 𝟑 D (6, 0) F (2,5 , 3,5) G (0, 2) H (4 , 2) 𝟒 6 7 6 W (0,0 ) 𝑋_1 Exemplo 5ª etapa: Testando o ponto “W” e determinando a região de solução 6𝑋1 + 4𝑋2 ≤ 24 6 . (0) + 4 . (0) ≤ 24 0 ≤ 24 VERDADEIRO A região que contém o Ponto “W” pertence a região de solução no gráfico W (0, 0) 𝑋1 + 2𝑋2 ≤ 6 0 ≤ 6 VERDADEIRO A região que contém o Ponto “W” pertence a região de solução no gráfico W (0, 0) 𝑋2 - 𝑋1 ≤ 1 0 ≤ 1 VERDADEIRO A região que contém o Ponto “W” pertence a região de solução no gráfico W (0, 0) 𝑋2 ≤ 2 0 ≤ 2 VERDADEIRO A região que contém o Ponto “W” pertence a região de solução no gráfico W (0, 0) 𝑋_1 Exemplo 6ª etapa: Determinar a região solução 1 2 3 4 5 1 2 3 4 5 A (0, 6) B (4, 0) 𝑋1 𝑋2 C (0, 3) E (0, 1) 𝟏 𝟐 𝟑 D (6, 0) F (2,5 , 3,5) G (0, 2) H (4 , 2) 𝟒 6 7 6 W (0,0 ) 𝑋_1 Exemplo 7ª etapa: Identificar os pontos máximos da região solução K (?, ?) 1 2 3 4 5 1 2 3 4 5 𝑋1 𝑋2 6 7 6 E (0, 1) 𝟒 𝟐 B (4, 0)W (0,0 ) 𝟏 Y (?, ?) V (?, ?) 𝟑 Exemplo 8ª etapa: Achar os pontos “K, Y e V” do gráfico 𝑋2 − 𝑋1 = 1 𝑋2 = 2 𝑋1 + 2𝑋2 = 6 𝑋2 = 2 6𝑋1 + 4𝑋2 = 24 𝑋1 + 2𝑋2 = 6 K 2 − 𝑋1 = 1 𝑋1 = 1 K (1,2) Y 𝑋1 + 2.2 = 6 𝑋1 = 2 Y (2,2) V 6𝑋1 + 4𝑋2 = 24 𝑋1 = 6 − 2𝑋2 6(6 − 2𝑋2) + 4𝑋2 = 24 36 − 12𝑋2 + 4𝑋2 = 24 -8𝑋2 = 24 − 36 𝑋2 = 12/8 = 1,5 V (3, 1,5) 𝑋1 + 2 . 1,5 = 6 𝑋1 =3 Exemplo 9ª etapa: Substituir os pontos extremos da região de solução na função objetivo e encontrar o ponto de máximo lucro. PONTO FUNÇÃO OBJETIVO LUCRO (Z) (R$ 1000) W (0, 0) Max Z = 5(0)+4(0)= 0 E (0, 1) Max Z = 5(0)+4(1)= 4 K (1,2) Max Z = 5(1)+4(2)= 13 Y (2, 2) Max Z = 5(2)+4(2)= 18 V (3, 1,5) Max Z = 5(3)+4(1,5)= 21 B (4, 0) Max Z = 5(4)+4(0)= 20 Conclusão: Isso representa um mix de produto diário de 3 t de tina para exteriores e 1,5 t de tinta para interiores. O lucro unitário é $21.000. Exemplo O modelo completo da Reddy Mikkes é: Maximizar Z = 5𝑋1 + 4𝑋2 Sujeito a: 6𝑋1 + 4𝑋2≤ 24 𝑋1 + 2𝑋2≤ 6 −𝑋1 + 𝑋2≤ 1 𝑋2≤ 2 𝑋1, 𝑋2≥ 0 Por exemplo: a solução 𝑋1= 3t/d e 𝑋2 = 1 t/d é viável? Sim! Não viola nenhum das restrições. E a solução 𝑋1= 4t/d e 𝑋2 = 1 t/d é viável? Não! Não satisfaz a restrição 1. (1) (2) (3) (4) (5) Atividade 1. Construa para o modelo Reddy Mikks, cada uma das seguintes restrições e as expresse com o lado esquerdo linear e o lado direto constante. Atividade 2. Determine a melhor solução viável entre as seguintes soluções (viáveis e inviáveis) do modelo da Reddy Mikks: 3. Para a solução viável X1 = 2, X2 = 2 do modelo da Reddy Mikks determine as quantidades não utilizadas das matérias–primas M1 e M2. ATIVIDADE Uma empresa que funciona 10 horas por dia fabrica dois produtos em três processos sequenciais. A tabela resume os dados do problema. Determine o mix ótimo dos dois produtos. Resolva o problema graficamente. Minutos por unidade Lucro por unidade ($)Produto Processo 1 Processo 2 Processo 3 1 10 6 8 2 2 5 20 10 3 ATIVIDADE A Burroughs Garment Company fabrica camisas masculinas e blusas femininas para a Walmark Discount Stores. A Walmark aceitará toda a produção fornecidas pela Burroughs. O processo de produção inclui cortar, costurar e embalar. A Burroughs emprega 25 trabalhadores no departamento de corte, 35 no departamento de costura e 5 no departamento de embalagem. A empresa trabalha em turno de 8 horas por dia, 5 dias por semana. A tabela dá os requisitos de tempo e os lucros por unidade para as duas peças de vestuário. Determine a programação semanal ótima de produção para a Burroughs. Minutos por unidade Lucro por unidade ($)Peça Corte Costura Embalagem Camisas 20 70 12 8 Blusas 60 60 4 12
Compartilhar