POI Uchoa 3

Prévia do material em texto

1
Pesquisa Operacional I
Programação Linear
Prof. Eduardo Uchoa
http://www.logis.uff.br/~uchoa/POI/
2
Programação Linear
� Técnica que se propõe a otimizar (maximizar ou 
minimizar) o valor de uma função linear, respeitando um 
conjunto de restrições (equações ou inequações) 
lineares
� Criada por George B. Dantzig em 1947
� A criação da PL foi motivada por problemas de 
planejamento da Força Aérea dos EUA
Um modelo de Programação Linear (PL) reduz um sistema 
real a um conjunto de equações ou inequações lineares.
3
Problema de Programação Linear
Considere o seguinte problema
( )
( )
1 1 2 2
11 1 12 2 1 1
21 1 22 2 2 2
( / ) ...
 Sujeito a ... ,
 ... ,
 
n n
n n
n n
Maximizar Minimizar Z c x c x c x
a x a x a x b
a x a x a x b
= + + +
+ + + ≥ = ≤
+ + + ≥ = ≤
( )1 1 2 2
 
 ... ,
 
m m mn n ma x a x a x b+ + + ≥ = ≤
M M M M
1 2 , , .... , 0nx x x ≥
4
Problema de Programação Linear
Considere o seguinte problema
( )
( )
1
11 1 12 2 1 1
21 1 22 2 2
1 2
2
2
Sujeito a ... ,
 ... ,
 
( / ) ...
 
 
n n
n n
n n
a x a x a
Maximizar Minimizar Z c x c x c
x b
a x x a
x
a x b
= + + +
+ + + ≥ = ≤
+ + + ≥ = ≤
( )1 1 2 2
 
 ... ,
 
m m mn n ma x a x a x b+ + + ≥ = ≤
M M M M
1 2 , , .... , 0nx x x ≥Z: função objetivo
cj: coeficientes da função objetivo (custo / lucro), j = 1, …, n
xj: variáveis de decisão, j = 1, …, n
aij: coeficientes das variáveis nas restrições, i = 1,…,m e j = 1,…,n
bi: constantes do lado direito (right-hand-side), i = 1,…,m
5
Problema de Programação Linear
Considere o seguinte problema
( )
( )
1 2
11 1 12 2 1 1
21 1 22 2 2
1 2
2
( / )
Sujeito a ... ,
 ...
 ...
 
,
 
 
n n
n n
n n
Maximizar Minimizar Z x x x
a x a x a x b
a x a x a x b
c c c= + + +
+ + + ≥ = ≤
+ + + ≥ = ≤
( )1 1 2 2
 
 ... ,
 
m m mn n ma x a x a x b+ + + ≥ = ≤
M M M M
1 2 , , .... , 0nx x x ≥Z: função objetivo
cj: coeficientes da função objetivo (custo / lucro), j = 1, …, n
xj: variáveis de decisão, j = 1, …, n
aij: coeficientes das variáveis nas restrições, i = 1,…,m e j = 1,…,n
bi: constantes do lado direito (right-hand-side), i = 1,…,m
6
Problema de Programação Linear
Considere o seguinte problema
( )
( )
11 2
11 12 1 1
21 2
2
2 2
1
2
2
1 2
( / )
Sujeito a 
 ...
 ...
..
,
 ,
 
.
 
n
n
n
n
n
n
Maximizar Minimizar Z c c c
a a a
x x x
x x x
x xa a ax
b
b
= + + +
+ + + ≥ = ≤
+ + + ≥ = ≤
( )11 22
 
 ,
 
...
 
m m mn mnx x xa a a b+ + + ≥ = ≤
M M M M
1 2 , , , ... 0. nx x x ≥Z: função objetivo
cj: coeficientes da função objetivo (custo / lucro), j = 1, …, n
xj: variáveis de decisão, j = 1, …, n
aij: coeficientes das variáveis nas restrições, i = 1,…,m e j = 1,…,n
bi: constantes do lado direito (right-hand-side), i = 1,…,m
7
Problema de Programação Linear
Considere o seguinte problema
( )
( )
1 1 2 2
1 2 1
1
11 12 1
21 2 22 22
( / ) ...
 Sujeito 
 
...a ,
 ,
 
...
n
n n
n
n n
a a a
Maximizar Minimizar Z c x c x
a
c x
x x x b
x x xa ba
= + + +
+ + + ≥ = ≤
+ + + ≥ = ≤
( )11 22
 
 ,
 
...
 
n mm m mnx x xa a a b+ + + ≥ = ≤
M MM M
1 2 , , .... , 0nx x x ≥Z: função objetivo
cj: coeficientes da função objetivo (custo / lucro), j = 1, …, n
xj: variáveis de decisão, j = 1, …, n
aij: coeficientes das variáveis nas restrições, i = 1,…,m e j = 1,…,n
bi: constantes do lado direito (right-hand-side), i = 1,…,m
8
Problema de Programação Linear
Considere o seguinte problema
( )
( )
1 1 2 2
11 1 12 2 1
21 1 22 22
1
2
( / ) ...
 Sujeito a ... ,
 ... ,
 
 
 
 
n n
n n
n n
Maximizar Minimizar Z c x c x c x
a x a x a x
a
b
bx a x a x
= + + +
+ + + ≥ = ≤
+ + + ≥ = ≤
( )1 1 2 2
 
 ... ,
 
mm m mn na x a x a x b+ + + ≥ = ≤
M MM M
1 2 , , .... , 0nx x x ≥Z: função objetivo
cj: coeficientes da função objetivo (custo / lucro), j = 1, …, n
xj: variáveis de decisão, j = 1, …, n
aij: coeficientes das variáveis nas restrições, i = 1,…,m e j = 1,…,n
bi: constantes do lado direito (right-hand-side), i = 1,…,m
9
Programação Linear
Considere o seguinte problema
( )
( )
1 1 2 2
11 1 12 2 1 1
21 1 22 2 2 2
( / ) ...
 Sujeito a ... ,
 ... ,
 
n n
n n
n n
Maximizar Minimizar Z c x c x c x
a x a x a x b
a x a x a x b
= + + +
+ + + ≥ = ≤
+ + + ≥ = ≤
( )1 1 2 2
 
 ... ,
 
m m mn n ma x a x a x b+ + + ≥ = ≤
M M M M
1 2 , , .... , 0nx x x ≥Z: função objetivo
cj: coeficientes da função objetivo (custo / lucro), j = 1, …, n
xj: variáveis de decisão, j = 1, …, n
aij: coeficientes das variáveis nas restrições, i = 1,…,m e j = 1,…,n
bi: constantes do lado direito (right-hand-side), i = 1,…,m
10
Formas de representação de PLs
� Forma padrão: todas as restrições são igualdades e todas as 
variáveis são não-negativas
� Forma canônica: todas as restrições são do tipo ≥ (se for 
minimização) ou do tipo ≤ (se for maximização); todas as variáveis 
são não-negativas
11
Manipulação de PLs
� Transformar equações em inequações:
Uma equação equivale a duas inequações
 
1
⇒=∑
=
i
n
j
jij bxa i
n
j
jij bxa ≥∑
=1
i
n
j
jij bxa ≤∑
=1
12
Manipulação de PLs
� Transformar equações em inequações:
Uma equação equivale a duas inequações
0,,
123
10
 S.a
24Max 
321
321
321
321
≥
−=−+
=++
−+
xxx
xxx
xxx
xxx
 ⇒
0,,
123
123
10
10
 S.a
24Max 
321
321
321
321
321
321
≥
−≤−+
−≥−+
≤++
≥++
−+
xxx
xxx
xxx
xxx
xxx
xxx
13
Manipulação de PLs
� Transformar inequações em equações:
Adicionar uma novavariável não-negativa, conhecida como 
variável de folga.
 
1
⇒≤∑
=
i
n
j
jij bxa
01
1
1
≥
=+
+
+
=
∑
n
in
n
j
jij
x
bxxa
14
Manipulação de PLs
� Transformar inequações em equações:
Adicionar uma nova variável não-negativa, conhecida como 
variável de excesso.
 
1
⇒≥∑
=
i
n
j
jij bxa
01
1
1
≥
=−
+
+
=
∑
n
in
n
j
jij
x
bxxa
15
Manipulação de PLs
� Transformar inequações em equações:
Cada inequação transformada exige uma variável de folga ou 
de excesso diferente.
0,,
53
102
 S.a
3Min Z
321
21
321
31
≥
≥−
≤++
+=
xxx
xx
xxx
xx
 ⇒
0,,,,
53
102
 S.a
3Min Z
54321
521
4321
31
≥
=−−
=+++
+=
xxxxx
xxx
xxxx
xx
16
Manipulação de PLs
� Transformar inequações em equações:
0,,
53
102
 S.a
3Min Z
321
21
321
31
≥
≥−
≤++
+=
xxx
xx
xxx
xx
 ⇒
0,,,,
53
102
 S.a
3Min Z
54321
521
4321
31
≥
=−−
=+++
+=
xxxxx
xxx
xxxx
xx
5
0
0
67,1
:ótima Solução
3
2
1
=
=
=
=
Z
x
x
x
5
0
33,8
0
0
67,1
:ótima Solução
5
4
3
2
1
=
=
=
=
=
=
Z
x
x
x
x
x
17
Manipulação de PLs
� Transformar Minimização em Maximização :
Não esquecer que o valor da função objetivo do novo problema de 
maximização deve ser multiplicada por -1 para obter o valor da 
função objetivo do problema de minimização original.
∑∑
==
−=−⇒=
n
j
jj
n
j
jj xcZxcZ
11
)(Maximizar Minimizar 
18
Manipulação de PLs
� Transformar Maximização em Minimização:
Não esquecer que o valor da função objetivo do novo problema de 
minimização deve ser multiplicada por -1 para obter o valor da 
função objetivo do problema de maximização original.
∑∑
==
−=−⇒=
n
j
jj
n
j
jj xcZxcZ
11
)(Minimizar Maximizar 
19
Manipulação de PLs
0,,
53
102
 S.a
3Min Z
321
21
321
31
≥
≥−
≤++
+=
xxx
xx
xxx
xx
 ⇒
0,,
53
102
 S.a
-3ZMax 
321
21
321
31
≥
≥−
≤++
−=′
xxx
xx
xxx
xx
5
0
0
67,1
:ótima Solução
3
2
1
=
=
=
=
Z
x
x
x
5
0
0
67,1
:ótima Solução
3
2
1
−=′
=
=
=
Z
x
x
x
20
Manipulação de PLs
� Transformar “variáveis livres” em variáveis não-negativas
Em alguns casos é possível existir variáveis que podem assumir 
valores positivos ou negativos.
livre 
0,
4
52
 S.a
Min Z
3
21
31
321
321
x
xx
xx
xxx
xxx
≥
≤−
=++−
++=
21
Manipulação de PLs
 ⇒
5,0
4
5,4
0
:ótima Solução
3
2
1
=
−=
=
=
Z
x
x
x
livre 
0,
4
52
 S.a
Min Z
3
21
31
321
321
x
xx
xx
xxx
xxx
≥
≤−
=++−
++=
0,,,
4
52
 S.a
Min Z
4321
431
4321
4321
≥
≤+−
=−++−
−++=
xxxx
xxx
xxxx
xxxx
5,0
4
0
5,4
0
:ótima Solução
4
3
2
1
=
=
=
=
=
Z
x
x
x
x
22
Pesquisa Operacional I
Método gráfico de solução
Prof.: Eduardo Uchoa
uchoa@producao.uff.br
23
Objetivo
� Descrever o procedimento gráfico / geométrico para 
resolver problemas de programação linear com 2 
variáveis
� Obter a solução ótima enumerando os pontos extremos
� Obter a solução ótima pelo gradiente da função objetivo
� Ilustrar os casos da PL: 
� Solução ótima única
� Múltiplas soluções ótimas
� Soluções ilimitadas
� Problema inviável (não tem solução)
24
Exemplo de PL – Mix de produção
Uma empresa fabrica 2 tipos de porta: de madeira e 
de alumínio. Cada porta passa por 3 operações: 
corte, montagem e acabamento. O tempo gasto em
cada uma dessas operações, por cada tipo de porta
é conhecido. 
Determine a produção diária de cada tipo de porta
para maximizar o lucro da empresa, respeitando as 
disponibilidades diárias de tempo da máquina que
executa cada operação.
R$ 6,00
R$ 4,00
Lucro Unitário
8 h21 h24 hDisponibilidade
1,0 h/porta1,5 h/porta4,0 h/portaAlumínio
1,0 h/porta3,0 h/porta1,5 h/portaMadeira
AcabamentoMontagemCorte
25
Variáveis:
xi: qtde a ser produzida, i = porta de madeira, porta de alumínio
Função objetivo:
Maximizar Lucro →Maximizar Z = 4,0 xmad + 6,0 xal
Restrições de capacidade produtiva:
1,5 xmad + 4,0 xal ≤ 24 (corte)
3,0 xmad + 1,5 xal ≤ 21 (montagem)
1,0 xmad + 1,0 xal ≤ 8 (acabamento)
Restrições de não-negatividade:
xmad, xal ≥ 0
Exemplo de PL – Mix de produção
26
Exemplo de PL – Mix de produção
xmad
5 10 15
x
a
l
5
1
0
27
Exemplo de PL – Mix de produção
xmad
5 10 15
x
a
l
5
1
0
corte→→→→ 1,5 xmad + 4,0 xal ≤ 24
28
Exemplo de PL – Mix de produção
xmad
5 10 15
x
a
l
5
1
0
montagem→→→→ 3,0 xmad + 1,5 xal ≤ 21
29
Exemplo de PL – Mix de produção
xmad
5 10 15
x
a
l
5
1
0
acabamento→→→→ 1,0 xmad + 1,0 xal ≤ 8
30
Exemplo de PL – Mix de produção
xmad
5 10 15
x
a
l
5
1
0
Não-negatividade→→→→ xmad, xal ≥ 0
31
Exemplo de PL – Mix de produção
xmad
5 10 15
x
a
l
5
1
0
5 10 15
5
1
0
REGIÃO (CONJUNTO) DE 
SOLUÇÕES VIÁVEIS →→→→ POLÍGONO CONVEXO
32
Solução por enumeração dos pontos 
extremos
xmad
5
x
a
l
5
PONTOS EXTREMOS
xmad xal Lucro (Z)
0 0 0
0 6 36
7 0 28
3,2 4,8 41,6
6 2 36
33
Os pontos extremos correspondem a pares 
de restrições
x
a
l
xmad
53,2
4,8
RESTRIÇÕES ATIVAS: 
CORTE e ACABAMENTO
xmad xal
Restrições ativas
0 0 xmad, xal ≥ 0
0 6 xmad ≥ 0, corte: 1,5 xmad + 4,0 xal ≤ 24
7 0 xal ≥ 0, montagem: 3,0 xmad + 1,5 xal ≤ 21
3,2 4,8 corte: 1,5 xmad + 4,0 xal ≤ 24,
acabamento: 1,0 xmad + 1,0 xal ≤ 8
6 2 acabamento: 1,0 xmad + 1,0 xal ≤ 8,
montagem: 3,0 xmad + 1,5 xal ≤ 21
Obs:Montagem - tempo ocioso: 4,2 h/dia
34
Solução gráfica pelo gradiente da função 
objetivo
xmad
5 10 15
x
a
l
5
1
0
Lucro = Z = 4,0 xmad + 6,0 xal
35
xmad
5 10 15
x
a
l
5
1
0
Solução gráfica pelo gradiente da função 
objetivo
36
Nesse caso existe uma única solução ótima
xmad
5
x
a
l
3,2
4,8
Z = 41,6 
37
Isso nem sempre acontece
� Múltiplas soluções ótimas
Maximizar Lucro = Z = 6,0 xmad + 6,0 xal
x
a
l
6
6
xmad
38
Soluções ilimitadas
Max x1 + x2
S.a x1 + x2 ≥ 4
- x1 + 2 x2 ≤ 4
x1, x2 ≥ 0
x2
5
1
0
5 10 x1
39
Soluções ilimitadas
Geralmente indica erro 
na modelagem, não 
existe sistema real 
“ilimitado”
Max x1 + x2
S.a x1 + x2 ≥ 4
- x1 + 2 x2 ≤ 4
x1, x2 ≥ 0
x2
5
1
0
5 10 x1
40
Problema inviável (não existe solução)
Max x1 + x2
S.a x1 + x2 ≥ 8
x1 + x2 ≤ 4
x1, x2 ≥ 0
x2
5
1
0
5 10 x1
41
Problema inviável (não existe solução)
Nem sempre é erro de 
modelagem. Pode ser uma 
indicação real que se está
tentando fazer algo 
impossível!
x2
5
1
0
5 10 x1
42
OBSERVAÇÃO
Este material refere-se às notas de aula do curso 
TEP117 (Pesquisa Operacional I) da Universidade 
Federal Fluminense (UFF) e foi criado a partir das 
notas do Prof. Rodrigo A. Scarpel do ITA 
(www.mec.ita.br/~rodrigo) e não pode ser 
reproduzido sem autorização prévia de ambos os 
autores. Quando autorizado, seu uso é exclusivo 
para atividades de ensino e pesquisa em 
instituições sem finslucrativos.