Aula 8 - Pesquisa Operacional I - Programação Linear Inteira

Programao Linear Inteira - PLI
Prof. Me. William de Sousa Dias

Mestre em Engenharia de Produo e Sistemas UNISINOS
[email protected]
Pesquisa Operacional
Nem sempre se pode dividir o valor de uma varivel: meia

mquina, produzir meio produto etc.
PL PLI
0 +
(c) William Dias 2

Utilizada quando h necessidade de expressar variveis

inteiras nos modelos de otimizao
Exemplos:
Variveis Dicotmicas (Binrias)

0: no acontece
1: acontece
Variveis Inteiras
0, 1, 2, 3, ...: nmero de pessoas alocadas numa tarefa
3
Um empresa produz dois tipos de produtos, A e B. A

capacidade total de trabalho por semana de 50 horas. O
produto A requer 3 horas de trabalho e propicia lucro de
R$ 300,00. O produto B precisa de 5 horas para ser terminado e
produz lucro de R$ 400,00.
Quantas unidades de A e B devem ser produzidas de modo a
maximizar o lucro?
Modelo de Programao Linear
a: nmero de unidades A
b: nmero de unidades B
maximizar z = 300 a + 400 b

sujeito a
3 a + 5 b <= 50
4
Modelo de Programao Linear no Lindo
max 300 a + 400 b

st
3 a + 5 b <= 50
end
Qual o significado desta
soluo?
Soluo
LP OPTIMUM FOUND AT STEP 1

OBJECTIVE FUNCTION VALUE
5000.000
VARIABLE VALUE REDUCED COST
A 16.666666 0.000000
B 0.000000 100.000000
ROW SLACK OR SURPLUS DUAL PRICES
2) 0.000000 100.000000
NO. ITERATIONS= 1
5
Tentativa 1:
a = 17
b=0
Lucro = 300 * a + 400 * b = 5.100,00
Mas: 3 * a + 5 * b = 51 > 50
A soluo no vlida!!!
Tentativa 2:
a = 16
b=0
Lucro = 300 * a + 400 * b = 4.800,00
a melhor soluo?
6
Reescrevendo o modelo:
max 300 a + 400 b Indicam que a e b

st devem ser inteiros
3 a + 5 b <= 50
end
gin a
gin b
Soluo
LP OPTIMUM FOUND AT STEP 1
OBJECTIVE VALUE = 5000.00000 Esta a melhor soluo
NEW INTEGER SOLUTION OF 4900.00 AT BRANCH 0 PIVOT 1
inteira!
RE-INSTALLING BEST SOLUTION...
OBJECTIVE FUNCTION VALUE
1) 4900.000
VARIABLE VALUE REDUCED COST
A 15.000000 -300.000000
B 1.000000 -400.000000
ROW SLACK OR SURPLUS DUAL PRICES
2) 0.000000 0.000000
NO. ITERATIONS= 1
BRANCHES= 0 DETERM.= 1.000E 0 7
Modelos Inteiros podem ser resolvidos por diversos algoritmos,

em geral complexos e que necessitam uso de computadores.
As estratgias dos Algoritmos de PLI envolvem 3 etapas:
Etapa 1. Relaxe a regio de solues da PLI eliminando a
restrio inteira imposta a todas as variveis inteiras e
substituindo qualquer varivel binria y pela faixa continua
0<=y<=1. O resultado uma PL normal.
Etapa 2. Resolva a PL e identifique a soluo tima continua.
Etapa 3. Comeando do ponto timo continuo, adicione
restries especiais que modifiquem iterativamente a regio de
solues da PL de maneira que, a certa altura, resultar em um
ponto extremo timo que satisfaz os requisitos inteiros.
(c) William Dias 8

Dois mtodos gerais foram desenvolvidos:

1. O mtodo Branch-and-Bound (B&B).
Mais antigo
Desenvolvido 1960 por A. Land e G. Doig
Resoluo de problemas misto e geral
Mais confivel
2. O mtodo de planos de corte.

Difcil
Incerto
Erros de arredondamento
(c) William Dias 9

max 300 a + 400 b

st a = 16,667
3 a + 5 b <= 50 b=0
end L = 5.000,00
gin a
gin b a = 16 a = 17
b = 0,400 b=?
L = 4.960,00 Invivel
a = 16 a = 15
b=0 b=1
L = 4.800,00 L = 4.900,00
Melhor
soluo inteira!
10
Exemplo PLI no Solver

Uma empresa deseja desenvolver e otimizar um modelo de
Programao Linear que estabelea o lucro timo: Sabe-se que a
produo do produto P1 deve ser de no mnimo 80 unidades, a
produo de P2 deve ser de no mnimo 100 unidades e por fim a
produo de P3 tambm deve ser de no mnimo 100 unidades.
Formule e otimize o problema abaixo:
P1 P2 P3 Disponvel
Lucro unitrio R$2.100,00 R$1.200,00 R$600,00
Horas homens 6 4 6 3.400

Horas Mquinas 12 6 2 3.200
(c) William Dias 11

Maximizar Z = 5x1 +4x2

x1 + x2 <= 5
10x1 + 6x2 <= 45
x1, x2 inteiras, no negativas
(c) William Dias 12

Solver: Cinco projetos esto sob avaliao dentro de uma

projeo de planejamento de trs anos. A tabela a seguir d os
retornos esperados para cada projeto e os desembolsos anuais
associados.
Desembolso em milhes/ ano
Projeto 1 2 3 Retorno milhes
1 5 1 8 20
2 4 7 10 40
3 3 9 2 20
4 7 4 1 15
5 8 6 10 30
Fundos disponveis em milhes 25 25 25
Quais projetos devem ser selecionados na projeo de trs

anos? Responda sim-ou-no para cada projeto
(c) William Dias 13
Trs empresas de telefonia me consultaram para que eu

assinasse seus servios de longa distncia (Claro, Vivo e Oi). A
Claro cobrar uma taxa fixa de R$16 por ms, mais R$0,25 por
min. A Vivo cobrar R$25 por ms, mas reduzir o custo por
minuto para R$0,21. Quanto Oi, a taxa fixa mensal R$18 e o
custo por minuto R$0,22. De modo geral, gasto uma mdia
mensal de 200 minutos em chamadas de longa distncia.
Considerando que eu no pague a taxa fixa a menos que eu faa
chamadas e as distribua entre todas as trs empresas vontade,
como eu poderia usar as trs empresas para minimizar minha
conta telefnica mensal?
x1 = minutos de chamadas de longa
distncia por ms pela Claro
y1 = 1 se x1>0 e 0 se x1 = 0
y2 = 1 se x2>0 e 0 se x2 = 0
distncia por ms pela Vivo
y3 = 1 se x3>0 e 0 se x3 = 0
distncia por ms pela Oi
(c) William Dias 14
Minimizar Z = 0,25x1 + 0,21x2 + 0,22x3 + 16y1 + 25y2 + 18y3

Sujeito a
x1 + x2 + x3 = 200
x1<= 200y1
x2<= 200y2 Isso garante que yj ser igual a 1 se xj for positiva
x3<= 200y3
Xj <= Myj; j =1,2,3
O valor de M deve ser suficientemente grande de
modo a no restringir a varivel xj artificialmente, por
isso 200, que aproximadamente o nmero de
chamadas por ms. Se xj = 0 na soluo forar yj
tambm ter valor 0 na soluo.
(c) William Dias 15

TAHA, H. A. Pesquisa Operacional. 8. ed. So Paulo: Pearson,

2008.
(c) William Dias 31

POR HOJE S
32

Aula 8 - Pesquisa Operacional I - Programação Linear Inteira

Enviado por

Direitos autorais:

Formatos disponíveis

Aula 8 - Pesquisa Operacional I - Programação Linear Inteira

Enviado por

Dados do documento

Descrição original:

Direitos autorais

Formatos disponíveis

Compartilhar este documento

Compartilhar ou incorporar documento

Opções de compartilhamento

Você considera este documento útil?

Este conteúdo é inapropriado?

Direitos autorais:

Formatos disponíveis

Aula 8 - Pesquisa Operacional I - Programação Linear Inteira

Enviado por

Direitos autorais:

Formatos disponíveis

Programao Linear Inteira - PLI

Prof. Me. William de Sousa Dias

Nem sempre se pode dividir o valor de uma varivel: meia

(c) William Dias 2

Utilizada quando h necessidade de expressar variveis

Variveis Dicotmicas (Binrias)

Um empresa produz dois tipos de produtos, A e B. A

Modelo de Programao Linear

maximizar z = 300 a + 400 b

Modelo de Programao Linear no Lindo

max 300 a + 400 b

LP OPTIMUM FOUND AT STEP 1

max 300 a + 400 b Indicam que a e b

Modelos Inteiros podem ser resolvidos por diversos algoritmos,

(c) William Dias 8

Dois mtodos gerais foram desenvolvidos:

2. O mtodo de planos de corte.

(c) William Dias 9

max 300 a + 400 b

Exemplo PLI no Solver

Horas homens 6 4 6 3.400

(c) William Dias 11

Maximizar Z = 5x1 +4x2

(c) William Dias 12

Solver: Cinco projetos esto sob avaliao dentro de uma

Quais projetos devem ser selecionados na projeo de trs

Trs empresas de telefonia me consultaram para que eu

Minimizar Z = 0,25x1 + 0,21x2 + 0,22x3 + 16y1 + 25y2 + 18y3

(c) William Dias 15

TAHA, H. A. Pesquisa Operacional. 8. ed. So Paulo: Pearson,

(c) William Dias 31

Você também pode gostar