Universidade Federal Rural do Semi-Árido
Departamento de Ciências Ambientais e Tecnológicas
Bacharelado em Engenharia de Produção
Professor: MSc. Luiz Carlos
Pesquisa Operacional
Programação Linear
Daniel de Oliveira
Isadora Mendes
José Alípio
Modelagem Matemática
1. Problemas de Modelagem Matemática têm por objetivo
encontrar os valores para as variáveis de decisão que
otimizam (maximizam ou minimizam) uma função
objetivo respeitando um conjunto de restrições.
2. Alguns tipos de modelos de programação matemática
são:
 Programação linear;
 Programação inteira;
 Programação não-linear;
 Programação dinâmica;
Programação Linear
1. A Programação Linear trata-se, então, de uma técnica
de otimização com aplicações amplas e diversificadas
ao nível de problemas reais.
2. Características
1. Proporcionalidade
2. Não Negatividade
3. Aditividade
4. Separabilidade
Características da Programação Linear
1. Proporcionalidade: a quantidade de recurso
consumido por uma dada atividade deve ser
proporcional ao nível dessa atividade na solução final
do problema;
2. Não negatividade: deve ser sempre possível
desenvolver dada atividade em qualquer nível não
negativo e qualquer proporção de um dado recurso
deve sempre ser utilizado;
Características da Programação Linear
3. Aditividade: o custo total é a soma das parcelas
associadas a cada atividade;
4. Separabilidade: pode-se identificar de forma separada
o custo (ou consumo de recursos) específicos das
operações de cada atividade.
Componentes da Programação Linear
1. Todo modelo de programação linear tem duas
características importantes:
1. Função Objetivo a ser maximizada ou minimizada;
2. Restrições que devem ser respeitadas;
2. Função objetivo: medida de desempenho a ser
otimizada
3. Restrições: Atividades que consomem recursos em
determinadas proporções, apresentadas em forma de
equações ou inequações lineares, uma para cada
recurso, considerando os insumos disponíveis dentro
de cada atividade.
Componentes da Programação Linear
Forma Genérica:
Máx. ou Mín.:
Z = C1X1 + C2X2 + ... + CnXn
(função matemática que codifica o objetivo do problema - funçãoobjetivo)
Sujeito a:
a11x1 + a22x2 + ... + a1nxn < b1
a21x1 + a22x2 + ... + a2nxn < b2
...
am1x1 + am2x2 + ... + amnxn < bm
(funções matemáticas que codificam as principais
identificadas)
restrições
Componentes da Programação Linear
Forma Genérica:
•
•
•
•
•
xi ≥ 0 e bj ≥ 0, para i = 1, 2, ... , n e j = 1,2, ... , m
xi: variáveis decisórias que representam as quantidades ou
recursos que se quer determinar para otimizar o resultado global;
ci: coeficientes de ganho ou custo que cada variável é capaz de
gerar;
bj: quantidade disponível de cada recurso;
aij: quantidade de recurso que cada variável decisória consome.
Exemplo 01
Função Objetivo
•
Maximizar o lucro na produção de
cadeiras do tipo Mate e Captain, sendo
que os recursos são limitados.
Lucro Máximo:
A margem de contribuição unitária (preço
menos custo variável unitário) é de R$ 56 sobre
cada cadeira Captain que é vendida e de R$ 40
sobre cada cadeira Mate.
Max Z = 56C + 40M
Restrições
1. Montar uma cadeira exige pinos longos, pinos curtos,
pernas e dois tipos de assentos, que estão disponíveis
em estoques limitados que não podem ser
aumentados;
2. O estoque de pernas é de 760 e cada cadeira
produzida utiliza quatro pernas;
Restrições
3. Para a produção, o estoque de pinos longos e curtos é
de 1280 e 1600, respectivamente. Cada cadeira
Captain produzida usa oito pinos longos e quatro pinos
curtos, enquanto que cada Mate produzida usa quatro
pinos longos e doze pinos curtos;
4. O estoque de assentos pesados e de assentos leves é
de 140 e 120, respectivamente;
5. O número total de cadeiras produzidas tem de ser
superior a 100 unidades.
Dados do Problema
Dados do Problema
Mate
320
310
300
290
280
270
260
250
240
230
220
210
200
190
180
170
160
150
140
130
M < 120
120
110
100
90
80
70
60
50
40
30
20
10
0 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160 170 180 190 200 210 220 230 240 250 260 270 280 290 300 310 320 330 340 350 360 370 380 390 400
Captain
Restrições
• Número de assentos leves
Dados do Problema
Mate
320
C < 140
310
300
290
280
270
260
250
240
230
220
210
200
190
180
170
160
150
140
130
M < 120
120
110
100
90
80
70
60
50
40
30
20
10
0 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160 170 180 190 200 210 220 230 240 250 260 270 280 290 300 310 320 330 340 350 360 370 380 390 400
Captain
Restrições
• Número de assentos leves
• Número de assentos pesados
Dados do Problema
Mate
320
C < 140
310
300
290
280
270
260
250
240
230
220
210
200
190
180
170
160
150
140
130
M < 120
120
110
100
90
80
70
60
50
40
30
20
C + M > 100
10
0 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160 170 180 190 200 210 220 230 240 250 260 270 280 290 300 310 320 330 340 350 360 370 380 390 400
Captain
Restrições
• Número de assentos leves
• Número de assentos pesados
• Produção mínima
Dados do Problema
Mate
320
C < 140
310
300
290
280
270
260
250
240
230
220
210
200
190
180
170
160
150
140
130
M < 120
120
110
100
90
80
70
60
50
40
30
20
C + M > 100
4C + 4M < 760
10
0 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160 170 180 190 200 210 220 230 240 250 260 270 280 290 300 310 320 330 340 350 360 370 380 390 400
Captain
Restrições
• Número de assentos leves
• Número de assentos pesados
• Produção mínima
• Número de pernas
Dados do Problema
Mate
320
C < 140
8C + 4M < 1280
310
300
290
280
270
260
250
240
230
220
210
200
190
180
170
160
150
140
130
M < 120
120
110
100
90
80
70
60
50
40
30
20
C + M > 100
4C + 4M < 760
10
0 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160 170 180 190 200 210 220 230 240 250 260 270 280 290 300 310 320 330 340 350 360 370 380 390 400
Captain
Restrições
• Número de assentos leves
• Número de assentos pesados
• Produção mínima
• Número de pernas
• Pinos longos
Dados do Problema
Mate
320
C < 140
8C + 4M < 1280
310
300
290
280
270
260
250
240
230
220
210
200
190
180
170
160
150
140
130
M < 120
120
110
100
90
80
70
60
50
40
4C + 12M < 1600
30
20
C + M > 100
4C + 4M < 760
10
0 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160 170 180 190 200 210 220 230 240 250 260 270 280 290 300 310 320 330 340 350 360 370 380 390 400
Captain
Restrições
• Número de assentos leves
• Número de assentos pesados
• Produção mínima
• Número de pernas
• Pinos longos
• Pinos curtos
Dados do Problema
Mate
320
C < 140
8C + 4M < 1280
310
300
290
280
270
260
250
240
230
220
210
200
190
180
170
160
150
140
130
M < 120
120
110
100
90
80
70
60
50
40
4C + 12M < 1600
30
20
C + M > 100
4C + 4M < 760
10
0 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160 170 180 190 200 210 220 230 240 250 260 270 280 290 300 310 320 330 340 350 360 370 380 390 400
Captain
Restrições
• Número de assentos leves
• Número de assentos pesados
• Produção mínima
• Número de pernas
• Pinos longos
• Pinos curtos
Solução Ótima
Softwares
↑ Variáveis e restrições = ↑ Robusticidade do programa;
1. Caso Delta Airlines:
• Especificação de tipos de frotas;
• 40 mil restrições e 60 mil variáveis.
2. Problemas de médio e pequeno portes;
3. Ferramenta Solver.
Exemplo 02
Função Objetivo
• Maximizar o lucro semanal da produção de dois tipos de brinquedos
de madeira (soldados e trens), considerando os custos de mão-deobra e matéria-prima.
– Soldado (S):
• Preço de venda: R$ 27;
• MP: R$ 10;
• MO: R$ 14.
– Trem (T):
• Preço de venda: R$ 21;
• MP: R$ 9;
• MO: R$ 10.
• Receita por semana = 27*S + 21*T
• Custos de MP = 10*S + 9*T
• Custos de MO = 14*S + 10*T
• LUCRO = (27*S + 21*T) - (10*S + 9*T) - (14*S + 10*T) = 3S + 2T
Restrições
•
•
•
•
•
•
Tipos de mão-de-obra:
– Acabamento;
– Carpintaria;
Soldado:
– 2 horas de A e 1 hora de C;
Trem:
– 1 hora de A e 1 hora de C;
Não mais que 100 horas semanais de acabamento;
– Total de h de A/semana = 2S + 1T ≤ 100
Não mais que 80 horas semanais de carpintaria;
– Total de h de C/semana = 1S + 1T ≤ 80
Não mais que 40 soldados por semana.
– S ≤ 40
Descrição das equações
• Max L = 3S + 2T
• Sujeita a:
– 2S + T ≤ 100
– S + T ≤ 80
– S ≤ 40
• Organizando:
Exemplo 03
Exemplo
1. Uma empresa fabrica dois produtos A e B. Cada um deste
produtos requer uma certa quantidade de tempo na linha de
montagem e ainda mais algum para a sua finalização. Cada
produto do tipo A necessita de 5 horas na linha de
montagem e de 2 horas para a finalização. Cada produto de
tipo B necessita de 3 horas na linha de montagem e de 4
horas para a finalização. Numa semana, a empresa dispõe
de 108 horas para a linha de montagem e 60 horas para a
finalização. Toda a produção é vendida. O lucro de cada
produto é de R$ 120,00 para o produto A e de R$ 210,00
para o B.
Quantas unidades, por semana, dos produtos A e B se
devem produzir, de modo a que o lucro seja máximo?
Exemplo
MONTAGEM
FINALIZAÇÃO
LUCRO
A
5
2
120
B
3
4
210
DISPONIBILIDADE
108
60
-
Exemplo
Exemplo
1. Teorema
Dado um problema de programação linear, se S for a região
admissível e for limitada então existe um máximo e mínimo em
S e cada um destes ocorre pelo menos num dos vértices da
região.
Se S não for limitada, então pode não existir nem máximo nem
mínimo. Mas se existir ele encontra-se num vértice de S.
Exemplo
X
Y
L = 120x + 210y
O
0
0
0
A
21,6
0
2592
B
18
6
3420
C
0
15
3150
Curiosidade
Bibliografia
1. CAIXETA-FILHO, José Vicente. Pesquisa Operacional:
técnicas de otimização aplicadas a sistema
agroindustriais. 2 ed. São Paulo: Atlas, 2004.
2. GOLDBARG, Marco Cesar; LUNA, Henrique Pacca L.
Otimização combinatória e programação linear:
modelos e algortimos. Rio de Janeiro: Campus, 2000.
5ª tiragem.
3. MOORE, Jeffrey H.; WEATHERFORD, Larry R.
Tomada de decisão em administração com planilhas
eletrônicas. 6 ed. Porto Alegre: Bookman, 2005.