TEMA 2 - Programação Linear (SLIDES)

Prévia do material em texto

Programação 
Linear
PROF. RICARDO MESQUITA
Como lidamos com um problema
1. Definimos o problema
2. Formulamos o objetivo
3. Avaliamos as alternativas
Prof. Ricardo Mesquita 2
Como lidamos com um problema
Problemas simples
Problemas complexos
Recurso à intuição e
à experiência
Métodos científicos
Programação Linear
Prof. Ricardo Mesquita 3
Programação Linear
• A Programação Linear consiste em buscar otimizar 
(maximizar ou minimizar) uma dada função linear, que se 
chama função objetivo, definida num dado conjunto 
convexo, tendo em conta que as variáveis estão sujeitas 
a restrições.
Prof. Ricardo Mesquita 4
Programação Linear
• Usa um modelo matemático para descrever o problema.
• A palavra “programação” não se refere a programação de 
computadores, mas sim como um sinônimo de planejamento.
• O termo “linear” significa que todas as funções matemáticas do 
modelo são, obrigatoriamente, funções lineares.
Prof. Ricardo Mesquita 5
Termos Importantes
• Modelo: um modelo é uma representação simplificada 
da realidade expressa por equações matemáticas que 
servem para simular tal realidade.
• A qualidade de um modelo está relacionada com a 
significância das respostas por ele fornecidas (e não com sua 
maior ou menor adesão com a realidade).
• A experiência mostra que um modelo mais simples 
(consequentemente mais facilmente implementável), com 95% 
de precisão é preferível a outro mais sofisticado com precisão
maior.
Prof. Ricardo Mesquita 6
Termos Importantes
• Variáveis de decisão: São as variáveis utilizadas no 
modelo que podem ser controladas pelo tomador de 
decisão. A solução do problema é encontrada testando-
se diversos valores das variáveis de decisão.
Prof. Ricardo Mesquita 7
Termos Importantes
• Parâmetros: São variáveis utilizadas no modelo que não 
podem ser controladas pelo tomador de decisão. A 
solução do problema é encontrada admitindo como 
fixos os valores dos parâmetros.
Prof. Ricardo Mesquita 8
Termos Importantes
• Função objetivo: É uma função matemática que 
representa o principal objetivo do tomador de decisão. 
Ela é de dois tipos: 
• minimização (de custos, erros, chance de perda, desvio do 
objetivo etc.) ou 
• maximização (de lucro, receita, utilidade, bem-estar, riqueza, 
chance de sobrevivência etc.).
Prof. Ricardo Mesquita 9
Termos Importantes
• Restrições: São regras que dizem o que podemos (ou 
não) fazer e/ou quais são as limitações dos recursos ou 
das atividades associadas ao modelo.
Prof. Ricardo Mesquita 10
Termos Importantes
• Função linear: Uma função ƒ( x1, x2, ..., xn ) das variáveis x1, 
x2, ..., xn é uma função linear se for do tipo ƒ( x1, x2, ..., xn ) 
= c1x1 + c2x2 + ... + cn xn, sendo c1, c2, ..., cn valores 
constantes.
Prof. Ricardo Mesquita 11
Termos Importantes
• Inequação linear: Para b e d, números quaisquer, e uma 
função linear ƒ( x1, x2, ..., xn ), define-se uma inequação 
linear como as inequações do tipo ƒ( x1, x2, ..., xn ) ≤ b e 
ƒ( x1, x2, ..., xn) ≥ d.
Prof. Ricardo Mesquita 12
Modelo Geral da PL
Contempla:
• As variáveis as quais temos poder para alterar, ou seja, variáveis 
de decisão;
• Os parâmetros, que são variáveis e os quais não temos poder 
para alterar;
• A função-objetivo, que define e mensura o principal objetivo;
• As restrições que combinam variáveis e parâmetros para 
estabelecer regras, relações e limites do modelo;
• Uma “montagem” ou modelo que contempla parâmetros, 
variáveis, função-objetivo e restrições e que representa o 
problema real em análise utilizando somente funções lineares.
Prof. Ricardo Mesquita 13
Características de um Problema de PL
Prof. Ricardo Mesquita 14
As variáveis podem ter 
valores fracionados.
Os relacionamentos entre 
variáveis são sempre adições 
e subtrações,
As contribuições de cada variável 
de decisão são proporcionais ao 
seu próprio valor.
Todos os parâmetros 
utilizados nos modelos são 
conhecidos com certeza.
Problema Exemplo
• Uma empresa produz 2 produtos em uma de suas fábricas. Na fabricação dos 
dois produtos, 3 insumos são críticos: as quantidades de matéria prima (tipos A e 
B) disponíveis e a mão de obra disponível para a produção dos 2 produtos.
• Para o próximo mês, a fábrica terá disponível 4900 kg da matéria prima A e 4500 
kg da matéria prima B.
• Cada unidade do produto tipo I, para ser produzida consome 70 kg da matéria 
prima A e 90 kg da matéria prima B. Por sua vez, cada unidade do produto tipo II 
para ser produzida, utiliza 70 kg da matéria prima tipo A e 50 kg da matéria prima 
tipo B.
• A mão-de-obra é especializada para cada produto.
Prof. Ricardo Mesquita 15
Problema Exemplo
• Para a produção do produto tipo I, a empresa terá disponível, no próximo mês, 
80 homens-hora. Já para o produto tipo II, terá 180 homens-hora. 
• Cada unidade do produto tipo I, para ser produzida, utiliza 2 homens-hora, 
enquanto que cada unidade do produto tipo II utiliza 3 homens-hora.
• Cada unidade do produto tipo I dá um lucro de $20 e cada unidade do produto 
tipo II dá um lucro de $60.
• Suponha que todas as unidades produzidas de ambos os produtos serão 
vendidas.
• Como obter o maior lucro possível com a produção e a venda das unidades dos 
produtos tipo I e II?
Prof. Ricardo Mesquita 16
Determinação do Modelo
Variáveis de decisão:
• x1 ⇒ n.º de unidades do produto tipo I a serem produzidas 
no próximo mês.
• x2 ⇒ n.º de unidades do produto tipo II a serem produzidas 
no próximo mês
Prof. Ricardo Mesquita 17
Determinação do Modelo
Função objetivo:
(MAX) z = 20x1 + 60x2
Prof. Ricardo Mesquita 18
Lucro obtido com o produto I
Lucro obtido com o produto II
Determinação do Modelo
Restrições do modelo:
70x1 + 70x2 ≤ 4900
90x1 + 50x2 ≤ 4500
2x1 ≤ 80
3x2 ≤ 180
x1, x2 ≥ 0
Prof. Ricardo Mesquita 19
Restrição de não negatividade
Determinação do Modelo
Modelo:
(MAX) z = 20x1 + 60x2
sujeito a:
70x1 + 70x2 ≤ 4900
90x1 + 50x2 ≤ 4500
2x1 ≤ 80
3x2 ≤ 180
x1, x2 ≥ 0
Prof. Ricardo Mesquita 20
Restrição de não negatividade
Restrições do modelo
Função objetivo
Solução Gráfica
Prof. Ricardo Mesquita 21
Solução Gráfica
R1: 
70x1 + 70x2 ≤ 4900
Prof. Ricardo Mesquita 22
Solução Gráfica
R2:
90x1 + 50x2 ≤ 4500
Prof. Ricardo Mesquita 23
Solução Gráfica
R3:
2x1 ≤ 80
Prof. Ricardo Mesquita 24
Solução Gráfica
R4:
3x2 ≤ 180
Prof. Ricardo Mesquita 25
Solução Gráfica
Espaço de solução
Prof. Ricardo Mesquita 26
Ponto Ótimo
• O ponto ótimo é um ponto do espaço solução, ou seja, pertencente ao polígono 
hachurado.
• Observe a função objetivo: z = 20x1 + 60x2.
• representa uma família de retas paralelas.
• Vamos escolher um valor arbitrário para z. Por exemplo, z = 1200. Teremos então uma 
reta passando por (60, 0) e (0, 20).
Prof. Ricardo Mesquita 27
Ponto Ótimo
z = 1200
Prof. Ricardo Mesquita 28
Ponto Ótimo
z = 2400
Prof. Ricardo Mesquita 29
Ponto Ótimo
z*
Prof. Ricardo Mesquita 30
Ponto Ótimo
Portanto, o ponto ótimo está na interseção entre as retas
• R1: 70x1 + 70x2 = 4900 e
• R4: 3x2 = 180 
• Temos:
3x2 = 180  x2 = 60 
Então: 70x1 + 70x2 = 4900 
70x1 + 70 60 = 4900
70x1 + 4200 = 4900
70x1 = 700
x1 = 10
Prof. Ricardo Mesquita 31
Para maximizar o lucro, deve-
se produzir (e vender) 
10 produtos do tipo I e 
60 produtos do tipo II
Dúvidas?
Prof. Ricardo Mesquita 32