INTRODUÇÃO À PESQUISA
OPERACIONAL
** Programação Linear – Parte 2b **
Profa. Vitória Pureza
2º Semestre
Última Aula
• Construção de modelos de programação linear
Hoje verificaremos a modelagem dos exercícios
pendentes da lista e utilizaremos uma linguagem de
programação matemática para resolvê-los.
Nas aulas seguintes veremos a fundo o método de
resolução que esta linguagem utiliza
Roteiro
• Construção passo a passo de modelos de
Programação Linear
• Uso da linguagem de programação LINDO
para resolução dos modelos
Passos para Modelagem de
Programação Matemática
 Defina o objetivo do problema. Colete os dados
associados
 Defina os fatores que afetam o alcance do
objetivo do problema. Colete os dados
associados
 Elabore uma representação informal do problema
 Elabore um modelo de programação matemática
do problema
Um Problema de Transporte
Powerco tem 3 usinas de energia elétrica que suprem a necessidade de 4
cidades. Cada usina pode suprir a seguinte quantidade de milhões de
kilowatts-hora de eletricidade: U1 = 35; U2 = 50; U3 = 40. As demandas de
pico nas 4 cidades ocorrem na mesma hora e são (em milhões de KWh): C1
= 45; C2 = 20; C3 = 30; C4 = 30.
Os custos de se enviar 1 milhão de kwh de eletricidade de uma usina para
uma cidade depende da distância que a eletricidade deve percorrer (tabela
a seguir). Formule um PL para minimizar o custo de atender pelo menos a
demanda de pico das cidades.
CUSTO (x106 KWh)
CIDADE
USINA
C1
C2
C3
C4
U1
8
6
10
9
U2
9
12
13
7
U3
14
9
16
5
 Objetivo do Problema
Minimizar custo total de suprimento da demanda de pico das
cidades
CUSTO (x106 KWh)
CIDADE
USINA
C1
C2
C3
C4
U1
8
6
10
9
U2
9
12
13
7
U3
14
9
16
5
 Fatores que Afetam o Alcance do Objetivo
• Limitações de capacidade produtiva das usinas
USINA
PRODUÇÃO MÁXIMA
(x106 KWh )
U1
35
U2
50
U3
40
• Demanda mínima das cidades
CIDADE
DEMANDA MÁXIMA MENSAL
C1
45
C2
20
C3
30
C4
30
 Representação Informal do
Problema
Deseja-se
Minimizar custo total de suprimento da demanda de pico das
cidades, sujeito às seguintes restrições:
1.
2.
a quantidade de energia elétrica enviada pelas usinas não
pode exceder a produção horária das usinas
a quantidade de energia elétrica recebida pelas cidades não
pode ser inferior às suas demandas de pico
 Formulação do Modelo de Programação
Matemática
a) Variáveis de Decisão
•
O custo total de transporte é determinado pela quantidade de
eletricidade enviada de cada usina p/ cada cidade
xi j = 106 KWh produzidos na usina i e enviados à cidade j
b) Função Objetivo (FO)
Min 8x11 + 6x12 + 10x13 + 9x14 (custo de transporte da usina 1)
+ 9x21 + 12x22 + 13x23 + 7x24 (custo de transporte da usina 2)
+ 14x31 + 9x32 + 16x33 + 5x34 (custo de transporte da usina 3)
 Formulação do Modelo de Programação
Matemática
c) Restrições
1. A quantidade de energia elétrica enviada das usinas não pode exceder
suas produções horárias
Restrições de suprimento
x11 + x12 + x13 + x14 ≤ 35
x21 + x22 + x23 + x24 ≤ 50
x31 + x32 + x33 + x34 ≤ 40
2.
(suprimento de U1)
(suprimento de U2)
(suprimento de U3)
A quantidade de energia elétrica recebida pelas cidades não pode ser
inferior a suas demandas de pico
Restrições de demanda
x11 + x21 + x31 ≥ 45
x12 + x22 + x32 ≥ 20
x13 + x23 + x33 ≥ 30
x14 + x24 + x34 ≥ 30
(demanda de C1)
(demanda de C2)
(demanda de C3)
(demanda de C4)
 Formulação do Modelo de Programação
Matemática
d) Restrições de sinal
xij ≥ 0 (i=1..3, j=1..4) (106 KWh )
Modelo de Programação Linear
Min 8x11+6x12+10x13+9x14+9x21+12x22+13x23+7x24+ 14x31 +9x32 +16x33 +5x34
sujeito a:
x11 + x12 + x13 + x14 ≤ 35
(restrições de suprimento)
x21 + x22 + x23 + x24 ≤ 50
x31 + x32 + x33 + x34 ≤ 40
x11 + x21 + x31 ≥ 45
(restrições de demanda)
x12 + x22 + x32 ≥ 20
x13 + x23 + x33 ≥ 30
x14 + x24 + x34 ≥ 30
xij ≥ 0 (i=1,2,3; j=1,2,3,4)
(restrições de sinal)
Representação Gráfica
U1
C1
C2
U2
C3
U3
C4
Um Problema de Planejamento da
Produção
Uma companhia possui 2 fábricas, A e B. Cada fábrica faz 2 produtos,
padrão e deluxe. Uma unidade de padrão resulta em lucro de $10 e uma
unidade de deluxe em um lucro de $15.
Cada fábrica utiliza 2 processos (lixamento e polimento) para produzir esses
produtos. A fábrica A tem uma capacidade semanal de lixamento de 80
horas e de polimento de 60 horas. Para a fábrica B, essas capacidades são
60 e 75 horas semanais. Os tempos de lixamento e polimento em horas
para uma unidade de cada produto em cada fábrica são dados na Tabela 2.
Cada unidade de produto usa 4 kgs de matéria-prima e dos 120 kgs
disponíveis, 75 kgs foram alocados à fábrica A e 45 kgs à fábrica B. Formule
um PL para cada fábrica que maximize o lucro.
 Objetivo do Problema
Maximizar o lucro com a venda dos produtos padrão
e deluxe
PRODUTO
LUCRO
($)
Padrão
15
Deluxe
20
 Fatores que Afetam o Alcance do Objetivo
• Limitações de capacidade produtiva das fábricas
FÁBRICA A
FÁBRICA B
PROCESSO
Padrão
Deluxe
Padrão
Deluxe
LIXAMENTO
4
2
5
3
POLIMENTO
2
5
5
6
MATÉRIA PRIMA
4
4
4
4
QUANTIDADE
MÁXIMA DO
RECURSO
LIXAMENTO
POLIMENTO
MATÉRIA
PRIMA
FÁBRICA A
80
60
75
FÁBRICA B
60
75
45
 Representação Informal do Problema
Deseja-se (para cada uma das fábricas!)
Maximizar o lucro com a venda dos produtos padrão e deluxe,
sujeito às seguintes restrições:
1.
2.
3.
as horas semanais de lixamento para fabricação dos
produtos não podem exceder a disponibilidade semanal
as horas semanais de polimento para a fabricação dos
produtos não podem exceder a disponibilidade semanal
a quantidade de matéria-prima para fabricação dos
produtos não podem exceder a disponibilidade semanal
 Formulação do Modelo de Programação
Matemática (para a Fábrica A)
a) Variáveis de Decisão
•
O lucro é determinado pela quantidade de produto padrão e
deluxe produzidos na fábrica
x1 = quantidade de produtos padrão produzidos na fábrica A /semana
x2 = quantidade de produtos deluxe produzidos na fábrica A /semana
b) Função Objetivo (FO)
Max { 10x1 + 15x2 } ($/semana)
(para a fábrica A)
 Formulação do Modelo de Programação
Matemática
c) Restrições
1.
As horas semanais de lixamento para fabricação dos produtos não
podem exceder a disponibilidade semanal
4x1
+ 2x2
≤ 80
(hrs/semana)
2.
As horas semanais de polimento para a fabricação dos produtos não
podem exceder a disponibilidade semanal
2x1
+ 5x2
≤ 60
(hrs/semana)
3.
A quantidade de matéria-prima para fabricação dos produtos não
podem exceder a disponibilidade semanal
4x1
+ 4x2
≤ 75
(kgs/semana)
d) Restrições de sinal
xi ≥ 0 (i=1..2) (unidades de produto/semana)
Modelo da Fábrica A
Max 15x1 + 20x2
sujeito a:
4x1
2x1
4x1
x1
x2
(lucro da fábrica)
+ 2x2
+ 5x2
+ 4x2
≤ 80
≤ 60
≤ 75
≥ 0
(lixamento)
(polimento)
(matéria-prima)
(sinal)
≥0
Modelo da Fábrica B
Max 15x3 + 20x4
sujeito a:
5x3
5x3
4x3
x3
x4
(lucro da fábrica)
+ 3x4
+ 6x4
+ 4x4
≥0
≤ 60
≤ 75
≤ 45
≥0
(lixamento)
(polimento)
(matéria-prima)
(sinal)
Um Problema da Dieta
Minha dieta requer que toda a comida que eu coma venha dos 4 grupos
alimentares básicos (chocolate, sorvete, refrigerante e torta). No momento,
os 4 alimentos seguintes estão disponíveis para consumo: brownies, sorvete
de chocolate, coca-cola e torta de abacaxi. Cada brownie custa 0,50, cada
bola de sorvete de chocolate custa 0,20, cada garrafa de coca-cola custa
0,30 e cada pedaço de torta de abacaxi custa 0,80.
A cada dia, preciso ingerir pelo menos 500 calorias, 6 onças de chocolate,
10 onças de açúcar e 8 onças de gordura. O conteúdo nutricional por
unidade de cada alimento é mostrado abaixo. Formule um PL que possa ser
usado para satisfazer meus requerimentos nutricionais diários a um custo
mínimo.
ALIMENTO
CALORIAS
CHOCOLATE (on)
AÇÚCAR (on)
GORDURA (on)
BROWNIE
400
3
2
2
BOLA DE SORVETE DE CHOCOLATE
200
2
2
4
GARRAFA DE COCA COLA
150
0
4
1
PEDAÇO DE TORTA DE ABACAXI
500
0
4
5
 Objetivo do Problema
Minimizar o custo com a compra dos alimentos
BROWNIE
CUSTO
($/UNIDADE)
0,50
BOLA DE SORVETE DE CHOCOLATE
0,20
GARRAFA DE COCA COLA
0,30
PEDAÇO DE TORTA DE ABACAXI
0,80
ALIMENTO
 Fatores que Afetam o Alcance do Objetivo
• Requerimentos nutricionais diários
NUTRIENTE
REQUERIMENTO
DIÁRIO
CALORIAS
500
CHOCOLATE (on)
6
AÇÚCAR (on)
10
GORDURA (on)
8
 Representação Informal do Problema
Deseja-se
Minimizar o custo com a compra dos alimentos de minha dieta,
sujeito às seguintes restrições:
1.
2.
3.
4.
a quantidade de calorias ingeridas diariamente não podem
ser inferiores ao requerimento diário
a quantidade de chocolate ingerido diariamente não pode
ser inferior ao requerimento diário
a quantidade de açúcar ingerido diariamente não pode ser
inferior ao requerimento diário
a quantidade de gordura ingerida diariamente não pode ser
inferior ao requerimento diário
 Formulação do Modelo de Programação
Matemática
a) Variáveis de Decisão
•
O custo total de minha dieta é determinado pela quantidade de
alimentos de cada tipo comprados.
x1 = quantidade de brownies comprados /dia
x2 = bolas de sorvete de chocolate compradas /dia
x3 = garrafas de coca-cola compradas /dia
x4 = pedaços de torta de abacaxi compradas /dia
b) Função Objetivo (FO)
Min 0,50x1+ 0,20x2+ 0,30x3+ 0,80x4 ($/dia)
 Formulação do Modelo de Programação
Matemática
c) Restrições
1.
A quantidade de calorias ingeridas diariamente não podem ser inferiores
ao requerimento diário
400x1+200x2+150x3+500x4 ≥ 500 (cal/dia)
2.
A quantidade de chocolate ingerida diariamente não pode ser inferior ao
requerimento diário
3x1 + 2x2 ≥ 6
(on/dia)
3.
A quantidade de açúcar ingerida diariamente não pode ser inferior ao
requerimento diário
2x1 + 2x2 + 4x3 + 4x4 ≥ 10 (on/dia)
4.
A quantidade de gordura ingerida diariamente não pode ser inferior ao
seu requerimento diário
2x1 + 4x2 + x3 + 5x4 ≥ 8
(on/dia)
 Formulação do Modelo de Programação
Matemática
d) Restrições de sinal
xi ≥ 0 (i=1..4) (unidades de alimento/dia)
Modelo de Programação Linear
Min 0,50x1+ 0,20x2+ 0,30x3+ 0,80x4
sujeito a:
400x1+200x2+150x3+500x4 ≥ 500
3x1 + 2x2
≥6
(requerimento de calorias)
(requerimento de chocolate)
2x1 + 2x2 +
4x3 + 4x4 ≥ 10
(requerimento de açúcar)
2x1 + 4x2 +
x3 + 5x4 ≥ 8
(requerimento de gordura)
xi ≥ 0 (i=1..4)
(restrições de sinal)