Topico 3e-OtimizacaoLinear

Prévia do material em texto

OTIMIZAÇÃO 
Tratamentos de Restrições de Otimização 
Linear 
Ref.: Notas de aula do Prof. R. H. Takahashi 
& Livro: Introdução à pesquisa Operacional 
(Hillier & Lieberman) 
Prof. Lenir Jr. - 2013 
Restrições de Desigualdades 
 
 Formulação de um problema 
 de Otimização 
Restrições de Desigualdades 
 
 O ponto de ótimo x* deve satisfazer às m desigualdades: 
 
 
 
 O que significa esta desigualdade? 
Restrições de Desigualdades 
 
ℝ𝑛 
𝒫1 𝒢1 𝒩1 
 
 
 
 
 
 
 
 
 Se exige-se 𝑔 𝑥∗ ≤ 0 é o mesmo dizer que a região factível 
, ou conjunto factível é a união dos conjuntos e 
Restrição de Desigualdades 
ℱ1 
𝒩1 𝒢1 
𝑥∗ ∈ ℱ1 e minimiza f(.) ℱ1 = 𝒢1 ∪ 𝒩1 
Restrições de Desigualdades 
 
 O que significa esta desigualdade? 
 
Otimização Linear 
 Função objetivo e funções de restrições são apresentadas na 
forma linear e dados por: 
 
 
 A função objetivo apresenta da seguinte forma: 
 
 
 O conjunto de restrições corresponde às m desigualdades: 
Otimização Linear 
 
Otimização Linear 
 
A região factível ℱ , 
correspondente a várias restrições 
lineares de desigualdade. Cada 
reta que contém um dos lados do 
poliedro factível corresponde à 
fronteira de uma restrição de 
desigualdade. 
O vetor gradiente da função objetivo ∇𝑓(𝑥), mostrado no 
ponto x, é constante em todo espaço, pois a função é linear. 
As linhas tracejadas correspondem às curvas de nível da 
função objetivo, sendo que elas correspondem a valores 
cada vez menores de função objetivo quando se caminha da 
direita para esquerda. Dessa forma o ponto x indicado na 
figura é o de menor valor da função objetivo dentro da 
região factível ℱ , correspondendo ao ponto em que a curva 
de nível de menor valor toca a região factível. 
Otimização Linear 
 Outra forma de entendimento das funções lineares: 
 
Otimização Linear 
 
Otimização Linear 
 Exemplo Protótipo 
 
 
A WYNDOR GLASS CO. fabrica produtos de vidro de alta qualidade, entre os quais janelas 
e portas de vidro. A empresa possui três fábricas industriais. As esquadrias de alumínio e 
ferragens são feitas na Fábrica 1, as esquadrias de madeira são produzidas na Fábrica 2 e, 
finalmente, a Fábrica 3 produz o vidro e monta os produtos. 
Em consequência da queda nos ganhos, a direção decidiu modernizar a linha de produtos da 
empresa. Produtos não rentáveis estão sendo descontinuados, liberando capacidade 
produtiva para o lançamento de dois novos produtos com grande potencial de vendas: 
 
Produto 1: Uma porta de vidro de 2,5 m com esquadria de alumínio 
Produto 2: Uma janela duplamente adornada com esquadrias de madeira de 1,20 X 1,80 m 
 
Otimização Linear 
 
 
 
O produto 1 requer parte da capacidade produtiva das Fábricas 1 e 3, mas nenhuma da 
Fábrica 2. O produto 2 precisa apenas das Fábricas 2 e 3. A divisão de marketing concluiu 
que a empresa poderia vender tanto quanto fosse possível produzir desses produtos por essas 
fábricas. Entretanto, pelo fato de ambos os produtos poderem estar competindo pela mesma 
capacidade produtiva na Fábrica 3, não está claro qual mix dos dois produtos seria o mais 
lucrativo e chegaram à seguinte definição do problema: 
 
Determinar quais devem ser as taxas de produção para ambos os produtos de modo 
a maximizar o lucro total, sujeito às restrições impostas pelas capacidades produtivas 
limitadas disponíveis nas três fábricas. (Cada produto será fabricado em lotes de 20, 
de forma que a taxa de produção é definida como o número de lotes produzidos por 
semana.) É permitida qualquer combinação de taxas de produção que satisfaça essas 
restrições, inclusive não produzir nada de um produto e o máximo possível do outro. 
Otimização Linear 
 
 
A equipe também identificou os dados que precisavam ser coletados: 
 
1. Número de horas de tempo de produção disponível por semana em cada fábrica para 
esses novos produtos. (A maior parte do tempo nessas fábricas já está comprometida com os 
produtos atuais, de modo que a capacidade disponível para os novos produtos 
é bastante limitada.) 
2. Número de horas de tempo de produção usado em cada fábrica para cada lote produzido 
de cada novo produto. 
3. Lucro por lote produzido de cada novo produto. Foi escolhido o lucro por lote produzido 
como uma medida apropriada após a equipe de PO ter concluído que o incremento de lucro 
de cada lote adicional produzido ser aproximadamente constante independentemente do 
número total de lotes produzidos. Pelo fato de nenhum custo adicional incorrer para o início 
da produção e a comercialização de tais produtos, o lucro total de cada um deles é 
aproximadamente esse lucro por lote vezes o número de lotes produzidos. 
Otimização Linear 
 
 
Formulação como Problema de Programação Linear: (Tabela 3.1) 
Para formular o modelo matemático (programação linear) para esse problema, façamos 
x1 = número de lotes do produto 1 produzido semanalmente 
x2 = número de lotes do produto 2 produzido semanalmente 
Z = lucro total por semana (em milhares de dólares) obtido pela produção desses Produtos. 
Portanto, x1 e x2 são as variáveis de decisão para o modelo. 
Otimização Linear 
 
 
Usando-se a linha inferior da Tabela 3.1, obtemos Z = 3x1 + 5x2 • 
O objetivo é escolher os valores de x1 e x2 de forma a maximizar Z = 3x1 + 5x2, sujeito às 
restrições impostas em seus valores por limitações de capacidade de produção disponível nas 
três fábricas. A Tabela 3.1 indica que cada lote de produto 1 fabricado por semana usa uma 
hora de tempo de produção por semana na Fábrica 1, ao passo que estão disponíveis 
somente quatro horas semanais. Essa restrição é expressa matematicamente pela 
desigualdade x1 ≤ 4. 
Otimização Linear 
 
 
Similarmente, a Fábrica 2 impõe a restrição 2x2 ≤ 12. O número de horas de produção usado 
semanalmente na Fábrica 3 escolhendo-se x1 e x2 como as taxas de produção dos novos 
produtos seria 3x1 + 2x2. Portanto, a declaração matemática da restrição da Fábrica 3 é 3x1 
+ 2x2 ≤ 18. Finalmente, já que as taxas de produção não podem ser negativas, é necessário 
restringir as variáveis de decisão para serem não-negativas: x1 ≥ 0 e x2 ≥ 0. 
Otimização Linear 
 
 
Em suma, na linguagem matemática da programação linear, o problema é escolher os 
valores de x1 e x2 de forma a: 
Otimização Linear 
 Solução Gráfica 
Otimização Linear 
 Solução Gráfica 
Otimização Linear 
 Essas observações fazem que nosso procedimento de tentativa e erro para construção de retas na 
Figura 3.3 envolva mais do que desenhar uma família de retas paralelas contendo pelo menos um 
ponto na região de soluções viáveis e selecionar a reta que corresponde ao maior valor de Z. A 
Figura 3.3 mostra que essa reta passa pelo ponto (2, 6) indicando que a solução ótima é x1 = 2 e 
x2 = 6. A equação dessa reta é 3x1 + 5x2 = 3(2) + 5(6) = 36 = Z, indicando que o valor ótimo de 
Z é Z = 36. O ponto (2, 6) se encontra na interseção das retas 2x2 = 12 e 3x1 + 2x2 = 18, 
conforme mostrado na Figura 3.2, de forma que esse ponto pode ser calculado algebricamente 
como a solução simultânea dessas duas equações. 
Otimização Linear 
 Conclusão do problema: 
A equipe que usou esse método para descobrir que a solução ótima é x1 = 2, x2 = 6 com 
Z = 36. Essa solução indica que a Wyndor Glass Co. deveria fabricar os produtos 1 e 2 a 
uma taxa de, respectivamente, dois lotes por semana e seis lotes por semana, com um 
lucro total resultante de US$ 36 mil por semana. Nenhum outro mix de produtos seriatão lucrativo - de acordo com o modelo. 
Otimização Linear 
 Faça você mesmo. 
Planejamento de Fábrica de processamento de alimentos 
Bolos e Pães é uma fábrica de processamento de alimentos que produz salsichas e pães para 
cachorro-quente. A empresa moe sua própria farinha para fazer os pães em uma taxa máxima de 
200kg (peso) por semana. Cada pãozinho para cachorro-quente requer 0,l kg de farinha. 
Atualmente, possui um contrato com a Pigland, Inc. que especifica que uma entrega de 800 kg de 
carne suína é entregue toda segunda-feira. Cada salsicha precisa de 1/4 de kg de carne suína. 
Todos os demais ingredientes para fabricação de salsicha e pães se encontram em estoque pleno. 
Finalmente, a força de trabalho da empresa é formada por cinco empregados em período integral 
( 40 h/semana cada). Cada salsicha requer 3 minutos de trabalho e cada pãozinho, 2 minutos. 
Cada salsicha gera um lucro de R$ 0,20 e cada paõzinho R$ 0,10. 
A empresa gostaria de saber quantas salsichas e quantos pães deve produzir para obter o maior 
lucro possível. 
(a) Formule um modelo de programação linear para esse problema. 
(b) Use o método gráfico para solucionar esse modelo.