Aula04_PL1

Prévia do material em texto

OTIMIZAÇÃO DE 
SISTEMAS
Aula-04
Profa. Stephanie Alvarez
Departamento de Engenharia Elétrica
salvarez@unb.com
OBJETIVOS
NA AULA PASADA
 Definir o que são modelos
 Conhecer as fases de um modelo
 Introduzir programação linear
 Revisão de inequações
NESTA AULA
 Apresentar exemplos de programação 
linear
 Praticar como formular modelos de 
problemas usando a forma padrão-
programação linear
 Praticar solução gráfica de problemas
 Referências: 
 Andrade, Eduardo Leopoldino de, 
Introdução à pesquisa operacional, 5ª 
Edição, 2015
 Hillier, Frederick S. e Lieberman, 
Gerald J., Introdução à pesquisa 
operacional, 9ª Edição, McGraw Hill, 
2013
TIPOS DE 
MODELOS DE 
PROGRAMAÇÃO 
MATEMÁTICA
PROGRAMAÇÃO LINEAR
• Um número razoável de 
sistemas reais podem ser bem 
modelados como PLs
• Métodos de solução 
extremamente eficazes, 
problemas com milhões de 
variáveis e restrições podem 
ser resolvidos num laptop
PROBLEMA DE MISTURA
PROBLEMA DE MISTURA
Uma refinaria produz três tipos de gasolina: verde, azul e comum. Cada tipo 
requer gasolina pura, octana e aditivo, que são disponíveis na quantidade de 
9.600.000, 4.800.000 e 2.200.000 litros por semana, respectivamente. As 
especificações de cada tipo são:
 Um litro de gasolina verde requer 0.22 litro de gasolina pura, 0.50 litro de 
octana e 0.28 de aditivo;
 Um litro de gasolina azul requer 0.52 litro de gasolina pura, 0.34 litro de 
octana e 0.14 litro de aditivo;
 Um litro de gasolina comum requer 0.74 litro de gasolina pura, 0,20 litro de 
octana e 0.06 litro de aditivo.
PROBLEMA DE MISTURA
Com base na demanda de mercado, o planejamento da refinaria estipulou que a 
quantidade de gasolina comum deve ser no mínimo igual a 16 vezes a quantidade 
de gasolina verde e que a quantidade de gasolina azul seja no máximo igual a 
600.000 litros por semana.
A empresa sabe que cada litro de gasolina verde, azul e comum dá uma margem 
de contribuição para o lucro de $0,30, $0,25 e $0,20, respectivamente, e seu 
objetivo é determinar o programa de produção que maximiza a margem total de 
contribuição para o lucro.
PROBLEMA DE MISTURA
Uma refinaria produz três tipos de gasolina: verde, azul e comum. Cada tipo 
requer gasolina pura, octana e aditivo, que são disponíveis na quantidade de 
9.600.000, 4.800.000 e 2.200.000 litros por semana, respectivamente. As 
especificações de cada tipo são:
𝑥1 quantidade de gasolina verde a produzir
𝑥2 quantidade de gasolina azul a produzir
𝑥3 quantidade de gasolina comum a produzir
PROBLEMA DE MISTURA
Uma refinaria produz três tipos de gasolina: verde, azul e comum. Cada tipo requer 
gasolina pura, octana e aditivo, que são disponíveis na quantidade de 9.600.000, 
4.800.000 e 2.200.000 litros por semana, respectivamente. As especificações de cada 
tipo são:
𝑥1 quantidade de gasolina verde a produzir
𝑥2 quantidade de gasolina azul a produzir
𝑥3 quantidade de gasolina comum a produzir
 Um litro de gasolina verde requer 0.22 litro de gasolina pura, 0.50 litro de octana 
e 0.28 de aditivo;
 Um litro de gasolina azul requer 0.52 litro de gasolina pura, 0.34 litro de octana e 
0.14 litro de aditivo;
 Um litro de gasolina comum requer 0.74 litro de gasolina pura, 0,20 litro de 
octana e 0.06 litro de aditivo.
Sujeito a 0,22𝑥1 + 0,52𝑥2 + 0,74𝑥3 ≤ 9.600.000
0,50𝑥1 + 0,34𝑥2 + 0,20𝑥3 ≤ 4.800.000
0,28𝑥1 + 0,14𝑥2 + 0,06𝑥3 ≤ 2.200.000
pura
PROBLEMA DE MISTURA
Uma refinaria produz três tipos de gasolina: verde, azul e comum. Cada tipo requer 
gasolina pura, octana e aditivo, que são disponíveis na quantidade de 9.600.000, 
4.800.000 e 2.200.000 litros por semana, respectivamente. As especificações de cada 
tipo são:
𝑥1 quantidade de gasolina verde a produzir
𝑥2 quantidade de gasolina azul a produzir
𝑥3 quantidade de gasolina comum a produzir
 Um litro de gasolina verde requer 0.22 litro de gasolina pura, 0.50 litro de octana 
e 0.28 de aditivo;
 Um litro de gasolina azul requer 0.52 litro de gasolina pura, 0.34 litro de octana e 
0.14 litro de aditivo;
 Um litro de gasolina comum requer 0.74 litro de gasolina pura, 0,20 litro de 
octana e 0.06 litro de aditivo.
Sujeito a 0,22𝑥1 + 0,52𝑥2 + 0,74𝑥3 ≤ 9.600.000
0,50𝑥1 + 0,34𝑥2 + 0,20𝑥3 ≤ 4.800.000
0,28𝑥1 + 0,14𝑥2 + 0,06𝑥3 ≤ 2.200.000
octana
PROBLEMA DE MISTURA
Uma refinaria produz três tipos de gasolina: verde, azul e comum. Cada tipo requer 
gasolina pura, octana e aditivo, que são disponíveis na quantidade de 9.600.000, 
4.800.000 e 2.200.000 litros por semana, respectivamente. As especificações de cada 
tipo são:
𝑥1 quantidade de gasolina verde a produzir
𝑥2 quantidade de gasolina azul a produzir
𝑥3 quantidade de gasolina comum a produzir
 Um litro de gasolina verde requer 0.22 litro de gasolina pura, 0.50 litro de octana 
e 0.28 de aditivo;
 Um litro de gasolina azul requer 0.52 litro de gasolina pura, 0.34 litro de octana e 
0.14 litro de aditivo;
 Um litro de gasolina comum requer 0.74 litro de gasolina pura, 0,20 litro de 
octana e 0.06 litro de aditivo.
Sujeito a 0,22𝑥1 + 0,52𝑥2 + 0,74𝑥3 ≤ 9.600.000
0,50𝑥1 + 0,34𝑥2 + 0,20𝑥3 ≤ 4.800.000
0,28𝑥1 + 0,14𝑥2 + 0,06𝑥3 ≤ 2.200.000 aditivo
PROBLEMA DE MISTURA
Uma refinaria produz três tipos de gasolina: verde, azul e comum. Cada tipo requer 
gasolina pura, octana e aditivo, que são disponíveis na quantidade de 9.600.000, 
4.800.000 e 2.200.000 litros por semana, respectivamente. As especificações de cada 
tipo são:
𝑥1 quantidade de gasolina verde a produzir
𝑥2 quantidade de gasolina azul a produzir
𝑥3 quantidade de gasolina comum a produzir
 Um litro de gasolina verde requer 0.22 litro de gasolina pura, 0.50 litro de octana 
e 0.28 de aditivo;
 Um litro de gasolina azul requer 0.52 litro de gasolina pura, 0.34 litro de octana e 
0.14 litro de aditivo;
 Um litro de gasolina comum requer 0.74 litro de gasolina pura, 0,20 litro de 
octana e 0.06 litro de aditivo.
Sujeito a 0,22𝑥1 + 0,52𝑥2 + 0,74𝑥3 ≤ 9.600.000
0,50𝑥1 + 0,34𝑥2 + 0,20𝑥3 ≤ 4.800.000
0,28𝑥1 + 0,14𝑥2 + 0,06𝑥3 ≤ 2.200.000
pura
octana
aditivo
PROBLEMA DE MISTURA
Com base na demanda de mercado, o planejamento da refinaria estipulou que a 
quantidade de gasolina comum deve ser no mínimo igual a 16 vezes a quantidade de 
gasolina verde e que a quantidade de gasolina azul seja no máximo igual a 600.000 
litros por semana.
Sujeito a 𝑥3 ≥ 16𝑥1 ou 16𝑥1 − 𝑥3 ≤ 0
𝑥2 ≤ 600.000
A empresa sabe que cada litro de gasolina verde, azul e comum dá uma margem de 
contribuição para o lucro de $0,30, $0,25 e $0,20, respectivamente, e seu objetivo é 
determinar o programa de produção que maximiza a margem total de 
contribuição para o lucro.
Maximizar 𝑍 = 𝑓 𝑥1, 𝑥2, 𝑥3 = 0,30𝑥1 + 0,25𝑥2 + 0,20𝑥3
𝑥1 ≥ 0, 𝑥2 ≥ 0, 𝑥3 ≥ 0
Restrições de produção
Restrição de não negatividade
PROBLEMA DE MISTURA
𝑥1 quantidade de gasolina verde a produzir
𝑥2 quantidade de gasolina azul a produzir
𝑥3 quantidade de gasolina comum a produzir
Maximizar 𝑍 = 𝑓 𝑥1, 𝑥2, 𝑥3 = 0,30𝑥1 + 0,25𝑥2 + 0,20𝑥3
Sujeito a 0,22𝑥1 + 0,52𝑥2 + 0,74𝑥3 ≤ 9.600.000
0,50𝑥1 + 0,34𝑥2 + 0,20𝑥3 ≤ 4.800.000
0,28𝑥1 + 0,14𝑥2 + 0,06𝑥3 ≤ 2.200.000
𝑥3 ≥ 16𝑥1 ou 16𝑥1 − 𝑥3 ≤ 0
𝑥2 ≤ 600.000
e
𝑥1 ≥ 0, 𝑥2 ≥ 0, 𝑥3 ≥ 0
pura
octana
aditivo
Restrições de produção
Restrição de não negatividade
EXEMPLOS
EXEMPLO 1
 Suponha que para construir uma casa popular por mês uma construtora 
necessite de 2 pedreiros e 4 serventes. Para construir um apartamento no 
mesmo intervalo de tempo, a mesma construtora necessita de 3 pedreiros e 8 
serventes. A construtora possui um efetivo total de 30 pedreiros e 70 
serventes contratados. A construtora obtém um lucro de R$3.000,00 na venda 
de cada casa popular e R$5.000,00 na venda de cada apartamento e toda 
“produção” da construtora é vendida.
 Qual é a quantidade ótima de casas populares e apartamentos que a 
construtora deve construir para que esta obtenha lucro máximo.EXEMPLO 2
 Uma empresa que produz camiões, automóveis e motocicletas tem a sua fábrica 
dividida em duas secções: a secção A onde se efetua o trabalho de montagem e a 
seção B onde se realizam as operações de acabamento. O quadro seguinte mostra 
o número de horas gasta em cada secção na produção de um camião, um 
automóvel e uma motocicleta, os recursos diários da empresa (um número de 
horas de trabalho) e o lucro obtido com a produção de cada veículo (em centenas 
de euros).
 Supondo que por razões de mercado a produção de motocicletas não deve 
ultrapassar as 75 unidades diárias, pretende-se determinar quantos veículos de 
cada tipo devem ser produzidos por dia de forma a maximizar o lucro da empresa
Unidades
Bens a produzir Recursos 
disponíveisCamiões Automóveis Motocicletas
Secção A Hora 6 4 2 240
Secção B Hora 3 3 1 135
Lucro Centenas de euros 10 8 5
EXEMPLO 3
Uma empresa fabrica dois produtos em três processos sequenciais. A empresa 
funciona 10 horas por dia. A tabela resume os dados do problema
Determine o Mix ótimo dos dois produtos em um dia
Produto
Minutos por unidade
Lucro por 
unidade
Processo
1 2 3
1 10 6 8 2
2 5 20 10 3
EXEMPLO 4
 Uma agroindústria deve produzir um tipo de ração para um determinado 
animal. A ração é produzida pela mistura de farinhas de 3 ingredientes 
básicos: farinhas de osso, de soja e de peixe
 Cada um dos ingredientes contém diferentes quantidades de dois nutrientes 
necessários para uma dieta nutricional balanceada: proteína e cálcio.
 O nutricionista específica as necessidades mínimas desses nutrientes em 1 kg 
de ração.
 Cada ingrediente é adquirido no mercado com certo custo unitário
 OBJETIVO: Determinar em que quantidades os ingredientes devem ser 
misturados de modo a produzir 1 kg de ração que satisfaça às restrições 
nutricionais com o mínimo custo.
EXEMPLO 4
Ingredientes
Nutrientes Osso Soja Peixe Ração
Proteína 0.2 0.5 0.4 0.3
Cálcio 0.6 0.4 0.4 0.5
Custos ($/kg) 0.56 0.81 0.46
Variáveis de decisão (1 kg de mistura) ?
Custo da mistura ?
Restrições ?
EXEMPLO 4
 Uma agroindústria deve produzir um tipo de 
ração para um determinado animal. A ração é 
produzida pela mistura de farinhas de 3 
ingredientes básicos: farinhas de osso, de 
soja e de peixe
 Cada um dos ingredientes contém diferentes 
quantidades de dois nutrientes necessários 
para uma dieta nutricional balanceada: 
proteína e cálcio.
 O nutricionista específica as necessidades 
mínimas desses nutrientes em 1 kg de ração.
 Cada ingrediente é adquirido no mercado 
com certo custo unitário
 OBJETIVO: Determinar em que quantidades 
os ingredientes devem ser misturados de 
modo a produzir 1 kg de ração que satisfaça 
às restrições nutricionais com o mínimo 
custo.
Ingredientes
Nutrientes Osso Soja Peixe Ração
Proteína 0.2 0.5 0.4 0.3
Cálcio 0.6 0.4 0.4 0.5
Custos 
($/kg)
0.56 0.81 0.46
Variáveis de decisão (1 kg de mistura) ?
Custo da mistura ?
Restrições ?
EXEMPLO 5
 Ana deseja balancear os alimentos que consume de forma a obter uma dieta 
alimentar que forneça diariamente toda a energia, proteína e cálcio que 
necessita. Seu médico recomendou que ela se alimente de forma a obter 
diariamente no mínimo 2000 kcal de energia, 65g de proteína e 800 mg de 
cálcio.
 Quanto de cada alimento Ana deve consumir para obter uma dieta que atenda 
a recomendação médica e que tenha o menor custo possível?
 O valor nutritivo e o preço (por porção) de cada alimento a ser considerado 
na dieta é dado na tabela
EXEMPLO 5
Tipo de 
alimento
Tamanho 
da porção
Energia 
(Kcal)
Proteína (g) Cálcio Preço por 
porção 
(centavos)
Arroz 100 g 170 3 12 14
Ovos 2 Uni 160 13 54 13
Leite 273 ml 160 8 285 9
Feijão 260 g 337 22 86 19
Variáveis de decisão ?
Custo da mistura ?
Restrições ?
EXEMPLO 5
 Ana deseja balancear os alimentos 
que consume de forma a obter uma 
dieta alimentar que forneça 
diariamente toda a energia, proteína 
e cálcio que necessita. Seu médico 
recomendou que ela se alimente de 
forma a obter diariamente no mínimo 
2000 kcal de energia, 65g de proteína 
e 800 mg de cálcio.
 Quanto de cada alimento Ana deve 
consumir para obter uma dieta que 
atenda a recomendação médica e 
que tenha o menor custo possível?
 O valor nutritivo e o preço (por 
porção) de cada alimento a ser 
considerado na dieta é dado na 
tabela
Tipo de 
alimento
Tamanho 
da porção
Energia 
(Kcal)
Proteína (g) Cálcio Preço por 
porção 
(centavos)
Arroz 100 g 170 3 12 14
Ovos 2 Uni 160 13 54 13
Leite 273 ml 160 8 285 9
Feijão 260 g 337 22 86 19
Variáveis de decisão ?
Custo da mistura ?
Restrições ?
EXEMPLO 6
 Uma empresa fabrica dois produtos, A e B. O volume de vendas de A é no 
mínimo 80% do total de venda de ambos (A e B). Contudo, a empresa não 
pode vender mais do que 100 unidades de A por dia. Ambos os produtos usam 
matéria prima cuja disponibilidade máxima diária é de 240 lb. As taxas de 
utilização de matéria prima são 2 lb por unidade de A e 4 lb por unidade de B. 
Os lucros unitários para A e B, são respectivamente $20 e $50. Determine o 
Mix ótimo para empresa.
EXEMPLO 7
 Um individuo quer investir $5000 no próximo ano em dois tipos de 
investimento: o investimento em A rende 5% e o investimento em B rende 
8%. Pesquisas de mercado recomendam uma alocação de no mínimo 25% em 
A e no máximo 50% em B. Além do mais, o investimento em A deve ser no 
mínimo a metade do investimento em B. Como o fundo deve ser alocado aos 
dois investimentos. 
EXEMPLO 8
 Resolva graficamente o modelo abaixo:
Maximizar 𝑍 = 2𝑥1 + 5𝑥2
S.a. 𝑥1 ≤ 4
2𝑥2 ≤ 12
3𝑥1 + 2𝑥2 ≤ 18
e 𝑥1, 𝑥2, ≥ 0
EXEMPLO 9
 Resolva graficamente o modelo abaixo:
Maximizar 𝑍 = 2𝑥1 + 𝑥2
S.a. 𝑥2 ≤ 10
2𝑥1 + 5𝑥2 ≤ 60
𝑥1 + 𝑥2 ≤ 18
3𝑥1 + 𝑥2 ≤ 44
e 𝑥1, 𝑥2, ≥ 0
SOLUÇÕES
EXEMPLO 1
 Suponha que para construir uma casa popular por mês uma construtora 
necessite de 2 pedreiros e 4 serventes. Para construir um apartamento no 
mesmo intervalo de tempo, a mesma construtora necessita de 3 pedreiros e 8 
serventes. A construtora possui um efetivo total de 30 pedreiros e 70 
serventes contratados. A construtora obtém um lucro de R$3.000,00 na venda 
de cada casa popular e R$5.000,00 na venda de cada apartamento e toda 
“produção” da construtora é vendida.
 Qual é a quantidade ótima de casas populares e apartamentos que a 
construtora deve construir para que esta obtenha lucro máximo.
EXEMPLO 1
 Suponha que para construir uma casa popular por mês uma construtora 
necessite de 2 pedreiros e 4 serventes. Para construir um apartamento no 
mesmo intervalo de tempo, a mesma construtora necessita de 3 pedreiros e 8 
serventes. A construtora possui um efetivo total de 30 pedreiros e 70 
serventes contratados. A construtora obtém um lucro de R$3.000,00 na venda 
de cada casa popular e R$5.000,00 na venda de cada apartamento e toda 
“produção” da construtora é vendida.
 Qual é a quantidade ótima de casas populares e apartamentos que a 
construtora deve construir para que esta obtenha lucro máximo.
EXEMPLO 1
 Suponha que para construir uma casa popular por mês uma construtora 
necessite de 2 pedreiros e 4 serventes. Para construir um apartamento no 
mesmo intervalo de tempo, a mesma construtora necessita de 3 pedreiros e 8 
serventes. A construtora possui um efetivo total de 30 pedreiros e 70 
serventes contratados. A construtora obtém um lucro de R$3.000,00 na venda 
de cada casa popular e R$5.000,00 na venda de cada apartamento e toda 
“produção” da construtora é vendida.
 Qual é a quantidade ótima de casas populares e apartamentos que a 
construtora deve construir para que esta obtenha lucro máximo.
EXEMPLO 1
 Suponha que para construir uma casa popular por mês uma construtora 
necessite de 2 pedreiros e 4 serventes. Para construir um apartamento no 
mesmo intervalo de tempo, a mesma construtora necessita de 3 pedreiros e 8 
serventes. A construtora possui um efetivototal de 30 pedreiros e 70 
serventes contratados. A construtora obtém um lucro de R$3.000,00 na venda 
de cada casa popular e R$5.000,00 na venda de cada apartamento e toda 
“produção” da construtora é vendida.
 Qual é a quantidade ótima de casas populares e apartamentos que a 
construtora deve construir para que esta obtenha lucro máximo.
EXEMPLO 1
Casa popular Apartamento
Disponibilidade 
de mano de obra
Pedreiro 2 3 30
Servente 4 8 70
Lucro (em mil R$) 3 5
EXEMPLO 1
Casa popular Apartamento
Disponibilidade 
de mano de obra
Pedreiro 2 3 30
Servente 4 8 70
Lucro (em mil R$) 3 5
𝑥1 é a quantidade de casas populares construídas
𝑥2 é a quantidade de apartamentos construídos
Maximizar 𝑍 = 𝑓 𝑥1, 𝑥2 = 3𝑥1 + 5𝑥2
Sujeito a 
2𝑥1 + 3𝑥2 ≤ 30
4𝑥1 + 8𝑥2 ≤ 70
e 𝑥1 ≥ 0, 𝑥2 ≥ 0
EXEMPLO 2
𝑥1 número de camiões a produzir
𝑥2 número de automóveis a produzir
𝑥3 número de motocicletas a produzir
Maximizar 𝑍 = 𝑓 𝑥1, 𝑥2, 𝑥3 = 10𝑥1 + 8𝑥2 + 5𝑥3
Sujeito a
6𝑥1 + 4𝑥2 + 2𝑥3 ≤ 240
3𝑥1 + 3𝑥2 + 𝑥3 ≤ 135
𝑥3 ≤ 75
e 𝑥1, 𝑥2, 𝑥3 ≥ 0
Unidades
Bens a produzir Recursos 
disponíveisCamiões Automóveis Motocicletas
Secção A Hora 6 4 2 240
Secção B Hora 3 3 1 135
Lucro Centenas de euros 10 8 5
EXEMPLO 3
Maximizar 𝑍 = 𝑓 𝑥1, 𝑥2 = 2𝑥1 + 3𝑥2
S.a. 10𝑥1 + 5𝑥2 ≤ 600
6𝑥1 + 20𝑥2 ≤ 600
8𝑥1 + 10𝑥2 ≤ 600
e 𝑥1, 𝑥2, ≥ 0
EXEMPLO 4
 Variáveis de decisão (1 kg de mistura)
𝑥𝑜𝑠𝑠𝑜 quantidade de farinha de osso
𝑥𝑠𝑜𝑗𝑎 quantidade de farinha de soja
𝑥𝑝𝑒𝑖𝑥𝑒 quantidade de farinha de peixe
 Custo da mistura
Minimizar 𝑓 𝑥𝑜𝑠𝑠𝑜, 𝑥𝑠𝑜𝑗𝑎, 𝑥𝑝𝑒𝑖𝑥𝑒 = 0,56𝑥𝑜𝑠𝑠𝑜 + 0,81𝑥𝑠𝑜𝑗𝑎 + 0,46𝑥𝑝𝑒𝑖𝑥𝑒
 Sujeito a
0,2𝑥𝑜𝑠𝑠𝑜 + 0,5𝑥𝑠𝑜𝑗𝑎 + 0,4𝑥𝑝𝑒𝑖𝑥𝑒 ≥ 0,3
0,6𝑥𝑜𝑠𝑠𝑜 + 0,4𝑥𝑠𝑜𝑗𝑎 + 0,4𝑥𝑝𝑒𝑖𝑥𝑒 ≥ 0,5
𝑥𝑜𝑠𝑠𝑜 + 𝑥𝑠𝑜𝑗𝑎 + 𝑥𝑝𝑒𝑖𝑥𝑒 = 1
e 𝑥𝑜𝑠𝑠𝑜, 𝑥𝑠𝑜𝑗𝑎, 𝑥𝑝𝑒𝑖𝑥𝑒 ≥ 0
EXEMPLO 5
 Variáveis de decisão
𝑥𝑎 porção de arroz
𝑥𝑜 porção de ovos
𝑥𝑙 porção de leite
𝑥𝑓 porção de feijão 
Minimizar 𝑓 𝑥𝑎 , 𝑥𝑜, 𝑥𝑙 , 𝑥𝑓 = 14𝑥𝑎 + 13𝑥𝑜 + 9𝑥𝑙 + 19𝑥𝑓
 Sujeito a
170𝑥𝑎 + 160𝑥𝑜 + 160𝑥𝑙 + 337𝑥𝑓 ≥ 2000
3𝑥𝑎 + 13𝑥𝑜 + 8𝑥𝑙 + 22𝑥𝑓 ≥ 65
12𝑥𝑎 + 54𝑥𝑜 + 285𝑥𝑙 + 86𝑥𝑓 ≥ 800
e 𝑥𝑎, 𝑥𝑜, 𝑥𝑙 , 𝑥𝑓 ≥ 0
EXEMPLO 6
𝑥1 número de unidades de A
𝑥2 número de unidades de B
Maximiza 𝑍 = 𝑓 𝑥1, 𝑥2 = 20𝑥1 + 50𝑥2
Sujeito a 
𝑥1
𝑥1+𝑥2
≥ 0,8 ou −0,2𝑥1 + 0,8𝑥2 = 0
𝑥1 ≤ 100
2𝑥1 + 4𝑥2 ≤ 240
e 𝑥1, 𝑥2 ≥ 0
EXEMPLO 7
𝑥1 Capital investido em A
𝑥2 Capital investido em B
Maximiza 𝑍 = 𝑓 𝑥1, 𝑥2 = 0,05𝑥1 + 0,08𝑥2
Sujeito a 
𝑥1 ≥ 0,25(𝑥1 + 𝑥2)
𝑥2 ≤ 0,5(𝑥1 + 𝑥2)
𝑥1 ≥ 0,5𝑥2
𝑥1 + 𝑥2 ≤ 5000
e 𝑥1, 𝑥2 ≥ 0
EXEMPLO 8
EXEMPLO 9
PROGRAMAÇÃO LINEAR –
MODELO MATEMÁTICO
PROGRAMAÇÃO LINEAR
Consumo unitário de recurso por atividade
Recursos
Atividades Quantidade de Recurso 
disponível1 2 3 ⋯ 𝑛
1 𝑎11 𝑎12 𝑎13 ⋯ 𝑎11 𝑏1
2 𝑎21 𝑎22 𝑎23 ⋯ 𝑎11 𝑏2
⋮ ⋮ ⋮ ⋮ ⋯ ⋮ ⋮
𝑚 𝑎𝑚1 𝑎𝑚2 𝑎𝑚3 ⋱ 𝑎𝑚𝑛 𝑏𝑚
Lucro 𝑐1 𝑐2 𝑐3 ⋯ 𝑐𝑛
Variáveis 
Decisão
𝑥1 𝑥2 𝑥3 ⋯ 𝑥𝑛
PROGRAMAÇÃO LINEAR
Otimizar 𝑓 𝑥1, 𝑥2, ⋯ , 𝑥3 = 𝑐1𝑥1 + 𝑐2𝑥2 +⋯+ 𝑐𝑛𝑥𝑛
Sujeito a 𝑎11𝑥1 + 𝑎12𝑥2 +⋯+ 𝑎1𝑛𝑥𝑛 ≤ 𝑏1
𝑎21𝑥1 + 𝑎22𝑥2 +⋯+ 𝑎2𝑛𝑥𝑛 ≤ 𝑏2
⋮
𝑎𝑚1𝑥1 + 𝑎𝑚2𝑥2 +⋯+ 𝑎𝑚𝑛𝑥𝑛 ≤ 𝑏𝑚
e
𝑥1 ≥ 0, 𝑥2 ≥ 0,⋯ , 𝑥𝑛 ≥ 0
RESOLUÇÃO DE PPLs
A partir da modelagem matemática de um Problema de Programação Linear 
(PPL), pode-se encontrar a sua solução através da interpretação gráfica da 
função objetivo e das restrições operacionais, desde que o problema possua no 
máximo duas variáveis de decisão.
 Por que somente duas variáveis?
 No espaço de duas dimensões uma igualdade representa uma reta
 É importante perceber que cada desigualdade representa um semi-espaço
Este tipo de solução não tem aplicação prática pois os problemas do mundo real 
tem na maioria das vezes muito mais variáveis.
No entanto, a solução gráfica nos ajudará a 
entender os princípios básicos do método 
analítico, chamado de método simplex, usado 
para resolver os modelos de PL.
RESOLUÇÃO DE PPLs
MÉTODO SIMPLEX
 Algoritmo para resolver PPLs
 George Dantzig, 1947
 Muito utilizado
 Facilmente implementado como programa de computador
 Consegue resolver problemas com muitas variáveis
 Produz variáveis auxiliares para análise de sensibilidade
 Convém saber resolver “à mão”, para se compreender o seu funcionamento.
PRÓXIMA AULA
 Solucionando problemas usando programação linear
 Desenvolvimento do método simplex
 28/08/2019 das 14:00 às 15:50
 Sala FT – 34/15
❑ Slides no site stephaniealvarez.com/teaching
❑ Atendimento extraclasse: SG-11, sala AT-65/11, terças e quintas das 13:00 às 
14:30 
❑ Marcar o atendimento pelo salvarez@unb.com
OBSERVAÇÃO
Este material refere-se às notas de aula do curso 
169617 – TÓPICOS EM ENGENHARIA (OPTIMIZAÇÃO 
DE SISTEMAS) da Universidade de Brasília (UnB) e 
não pode ser reproduzido sem autorização prévia 
da Profa. Stephanie Alvarez. Quando autorizado, 
seu uso é exclusivo para atividades de ensino e 
pesquisa em instituições sem fins lucrativos.