Aula 04

Prévia do material em texto

1
Resolução de PLs
� O método gráfico resolve PLs com 2 variáveis
� 3 variáveis se você for um ninja da geometria 
descritiva!
� Precisamos de métodos para resolver PLs com 
qualquer número de variáveis
2
Pesquisa Operacional I
Sistemas de equações lineares
Prof.: Eduardo Uchoa
http://www.logis.uff.br/~uchoa/POI/
3
Representação algébrica
� Um sistema de n variáveis e m equações pode ser representado como:
11 1 12 2 1 1
21 1 22 2 2 2
1 1 2 2
:
n n
n n
m m mn n m
a x a x a x b
a x a x a x b
S
a x a x a x b
+ + + =
 + + + =


 + + + =
…
…
�
…
4
Representação matricial
� Definindo-se as seguintes matrizes,
o sistema S pode ser representado pelo produto:
Ax = b
11 12 1 1 1
21 22 2 2 2
1 2
n
n
m m mn n m
a a a x b
a a a x b
A x b
a a a x b
     
     
     
= = =
     
     
     
�
�
� � � � � �
�
5
Representação matricial
1 111 12 1
21 22 2 22
1 2 n
n
m n m
n
m m
x ba a a
a a a
A
a
b
x
x ba a
x
b
 
 
 
   
   
   
= =
   
   
=

  

 
  
�
�
� � � � �
�
�
Matriz dos coeficientes
11 12 1 1
21 22 2 2
1
2
n
n
m m mn n m
a a a b
a a a b
A b
x
x
a a b
x
x
   
   
   
= =
   
   
 
 
 
=
 
 
 
�
�
� � � � �
�
�
Vetor de
variáveis
11 12 1 1
21 22
1
22 2
1 2
n
n
m m mn mn
b
b
b
a a a x
a a a x
A x
a a a x b
   
   
   
= =
   
   
 
 
 
=
 

  

 
�
�
� � � �� �
�
Vetor dos termos 
independentes
ou constantes do lado 
direito
6
Sistemas de equações lineares
� Classificados quanto ao conjunto solução em:
1) Sistema determinado
� Uma única solução
2) Sistema indeterminado
� Infinitas soluções
3) Sistema inconsistente
� Nenhuma solução
7
Sistemas de equações lineares m x m
Caso 1: Sistema determinado
� D = det A ≠ 0
� Posto(A) = m
� A é uma matriz inversível, ou seja, A-1 existe
� A solução do sistema pode ser representada 
por:
x = A-1b
8
Sistemas de equações lineares m x m
Exemplo
x1
x2
2 x1 - x2 = 0
2 x1 + 3 x2 = 6
3
2
1 2
1
0
1 2
1 2
2 0
:
2 3 6
x x
S
x x
− =

+ =
9
Sistemas de equações lineares m x m
Caso 2: Sistema indeterminado
� Posto(A) < m
� Existem equações Linearmente Dependentes 
(LD) que podem ser eliminadas
10
Sistemas de equações lineares m x m
Exemplo
x1
x2
4 x1 + 6 x2 = 12
3
2
1 2
1
0
1 2
1 2
2 3 6
:
4 6 12
x x
S
x x
+ =

+ =
2 x1 + 3 x2 = 6
11
Sistemas de equações lineares m x m
Caso 3: Sistema inconsistente
12
Sistemas de equações lineares m x m
Exemplo
x1
x2
x1 + x2 = 1
3
2
1 2
1
0
1 2
1 2
2
:
1
x x
S
x x
+ =

+ =
x1 + x2 = 2
13
Resolução de sistemas lineares
Operações elementares
São transformações aplicadas a um sistema sem que 
seu conjunto-solução seja modificado. São estas:
1. Troca de ordem de equações
2. Multiplicação de uma equação por um escalar não-nulo
3. Soma da multiplicação de uma equação à outra
14
Resolução de sistemas lineares
Eliminação de Gauss-Jordan
� Método que busca a construção de uma matriz 
identidade por meio da aplicação de operações 
elementares
� Também serve para:
� Encontrar a inversa de uma matriz quadrada (se existir)
� Calcular o posto de uma matriz
� Detectar se o sistema é indeterminado
15
Resolução de sistemas lineares
Exemplo
( )
( )
( )
1 2 3
1 2 3
1 2 3
i i/2
ii i
2 3 2 i
2 7 ii
2 2
i i
ii1 iii i iii 2i
x x x
x x x
x x x
=
=
 + − =
−
= −
−

− + =
 + + = −
16
Resolução de sistemas lineares
Exemplo
( )
( )
( )
1 2 3
1 2 3
1 2 3
ii ii i
iii iii
2 3 2 i i i/2 
2 7 ii
2 2 1 iii 2i
x x x
x x x
x x x
=
 + − = −
−
= −
←

− + =
 + + = −
17
Resolução de sistemas lineares
Exemplo
( )
( )
( )
1 2 3
1 2 3
1 2 3
ii ii i
i
2 3 2 i i i/2
2 7 ii
2 2 1 ii ii ii ii 2i
x x x
x x x
x x x
 + − = − ←

− + =
 + + =
−
=− −
=
( )
( )
( )
1 2 3
1 2 3
1 2 3
1 3 1 i
2 2
2 7 ii ii i
i i/2
iii iii 2
i i
2 2 1 iii i
x x x
x x x
x x x

+ − = −

− + = ← −
 + + = −= −

=

18
Resolução de sistemas lineares
Exemplo
( )
( )
( )
1 2 3
2 3
1 2 3
i i/2
ii i
1 3 1 i
2 2
3 7 8 ii
2 2
2 2 1 iii
i
iii ii i
i
i 2
x x x
x x
x x x

+ − = −


− + =

+ + = − ← −
=
−

=


19
Resolução de sistemas lineares
Exemplo
( )
( )
( )
1 2 3
2 3
1 2 3
i i/2
ii i
1 3 1 i
2 2
3 7 8 ii
2 2
2 2 1 iii
i
iii ii i
i
i 2
x x x
x x
x x x

+ − = −


− + =

+ + = − ← −
=
−

=


( )
( )
( )
1 2 3
2 3
2 3
1 3 1 i
2 2
3 7 8 ii ii ii/(-3
i
/
i ii/2
ii
2)
2 2
i ii i4 i i ii i1
x x x
x x
x x

+ − = −


− + = ←
= −
=

+ −

=


20
Resolução de sistemas lineares
Exemplo
( )
( )
( )
1 2 3
2 3
2 3
1 3 1 i i i ii/2
2 2
7 16 ii
3
ii ii/
3
4 1
(-3/2)
iii iii iii ii
x x x
x x
x x
=

+ − = − ← −


− = −
=

= −

+


21
Resolução de sistemas lineares
Exemplo
( )
( )
( )
1 2 3
2 3
2 3
1 3 1 i i i ii/2
2 2
7 16 ii
3
ii ii/
3
4 1
(-3/2)
iii iii iii ii
x x x
x x
x x
=

+ − = − ← −


− = −
=

= −

+


( )
( )
( )
1 3
2 3
2 3
i i ii/2
ii ii
1 5 i
3 3
7 16 ii
3 3
4 1 iii iii iii
/(-3/2)
ii
x x
x x
x x

− =


−
= −
== −

+ = ← −


22
Resolução de sistemas lineares
Exemplo
( )
( )
( )
1 3
2 3
3
i i (iii/3)
ii ii [(7
1 5 i
3 3
7 16 ii
3 3
19 19 iii iii iii / (19 / 3)
3 3
/3)(iii)]
x x
x x
x
=

− =


− =
+
−


= ←

= +

23
Resolução de sistemas lineares
Exemplo
( )
( )
( )
1 3
2 3
3
i i (iii/3)
ii ii [(7
1 5 i
3 3
7 16 ii
3 3
19 19 iii iii iii / (19 / 3)
3 3
/3)(iii)]
x x
x x
x
=

− =


− =
+
−


= ←

= +

( )
( )
( )
1 3
2 3
3
ii ii [(7/3)(iii
1 5 i i i (iii
)]
/3
iii iii / (19 / 3)
)
3 3
7 16 ii
3 3
1 iii
x x
x x
x

− = ← +


− = −

=
+
=

=


24
Resolução de sistemas lineares
Exemplo
( )
( )
( )
1
2 3
3
2 i
7 16 ii ii ii [(7/3)(iii)]
3 3
1 iii
i i (iii/3)
iii iii / (19 / 3)
x
x x
x
 =


− = − ←
= +

= =
+


25
Resolução de sistemas lineares
Exemplo
( )
( )
( )
1
2 3
3
2 i
7 16 ii ii ii [(7/3)(iii)]
3 3
1 iii
i i (iii/3)
iii iii / (19 / 3)
x
x x
x
 =


− = − =
= +

= =
+


( )
( )
( )
1
2
3
i i (iii/3)
ii ii [(7/3
2 i
3 ii
1 iii
)(iii)]
iii iii / (19 / 3)
x
x
x
 =

= −

=
=
= +
=
+
26
Resolução de PLs por 
enumeração de bases
Prof.: Eduardo Uchoa
27
Programação linear
� As restrições de um PL na formapadrão 
definem um sistema linear Ax = b, com Am×n e 
n ≥ m
� O complicador é a existência das restrições 
de não-negatividade x ≥ 0
28
Definindo bases
� Assuma que posto(A) = m (as equações LD podem ser 
detectadas e eliminadas pelo método de Gauss-Jordan)
� Pode-se achar soluções para Ax = b da seguinte forma:
1. Selecione m colunas LI de A (não necessariamente 
contíguas)
2. A matriz m×m formada será chamada de B. Dizemos 
que B é uma base. As variáveis associadas a B são 
ditas básicas e definem o vetor m×1 xB .
3. As demais colunas formam uma matriz m×(n-m)
chamada de N, as variáveis associadas são ditas não-
básicas e definem o vetor (n-m)×1 xN .
29
Exemplo: Problema de Mix de Produçã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
30
Exemplo: Problema de Mix de Produçã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
maximizar z = 4,0 xmad + 6,0 xal
Sujeito a
1,5 xmad + 4,0 xal ≤ 24
3,0 xmad + 1,5 xal ≤ 21
1,0 xmad + 1,0 xal ≤ 8
xmad , xal ≥ 0
Converter para a forma padrão
introduzindo variáveis de
folga
31
Exemplo: Problema de Mix de Produçã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
maximizar z = 4,0 xmad + 6,0 xal
Sujeito a
1,5 xmad + 4,0 xal + x3 = 24
3,0 xmad + 1,5 xal + x4 = 21
1,0 xmad + 1,0 xal + x5 = 8
xmad , xal , x3 , x4 , x5 ≥ 0
32
Representação matricial do sistema
3
4
5
3
4
5
1,5 4,0 1 0 0 24
3,0 1,5 0 1 0 21
1,0 1,0 0 0 1 8
1,5 4,0 1 0 0 24
3,0 1,5 0 1 0 21
1,0 1,0 0 0 1 8
mad
al
mad
al
x
x
A x x b
x
x
x
x
x
x
x
Ax b
 
 
    
    = = =       
    
 
 
 
 
    
    → =       
    
 
 
=
33
Montando uma base
3
4
5
1,5 4,0 1 0 0 24
3,0 1,5 0 1 0 21
1,0 1,0 0 0 1 8
mad
al
x
x
A x x b
x
x
 
 
    
    = = =       
    
 
 
Selecionar 3 variáveis.
34
Montando uma base
3
5
4
4,0 0
1,5 1
1,
1,5 1 0 24
3,0 0 0 21
1 0 0 10 0, 8
mad
al
x
A
x
x
x
x
x b
 
 
    
    = = =       
    
 
 
Por exemplo, xmad, x3 e x5
35
Reescrevendo o sistema separando as 
variáveis básicas e não-básicas
3
4
5
3
4
5
1,5 1 0 4,0 0 24
3,0 0 0 1,5 1 21
1,0 0 1 1,0 0 8
1,5 1 0 4,0 0 24
3,0 0 0 1,5 1 21
1,0 0 1 1,0 0
mad
al
B N
mad
al
B N
x
x
B N x x x b
x
x
x
x
Ax b Bx Nx b x
x
x
       
        
= = = = =        
        
       
    
     
= ↔ + = → + =     
     
     8
 
 
 
 
 
36
Encontrando a solução básica
Fazendo xN = 0, o único valor possível para é xB = 
B-1.b
A solução x= (xB=B-1.b, xN= 0) é chamada de 
solução básica do sistema Ax = b associada a 
base B.
1
1
3
5
1,5 1 0 24 7
3,0 0 0 21 13,5
1,0 0 1 8 1
mad
B B
x
Bx b x B b x
x
−
−
       
       
= → = → = ⋅ =       
       
       
37
Encontrando a solução básica
Fazendo xN = 0, o único valor possível para é xB = 
B-1.b
Para encontrar xB não é preciso calcular B-1. 
Basta resolver o sistema BxB = b.
1
1
3
5
1,5 1 0 24 7
3,0 0 0 21 13,5
1,0 0 1 8 1
mad
B B
x
Bx b x B b x
x
−
−
       
       
= → = → = ⋅ =       
       
       
38
Soluções básicas viáveis
�Uma solução básica em que x = (xB, xN) ≥ 0 é chamada 
de solução básica viável, ou seja, é uma solução legítima 
do PL
�Uma solução x = (xB, xN) com alguma variável < 0 é uma 
solução básica não-viável do PL
Propriedade: Se um PL possui uma única solução ótima, 
essa solução é básica viável.
Propriedade: Se um PL possui múltiplas soluções ótimas, 
existem pelo menos 2 soluções básicas viáveis ótimas.
39
Um PL pode ser resolvido por 
enumeração de soluções básicas
Para resolvermos um PL, podemos nos limitar a olhar 
apenas as soluções básicas, ou seja, testar todas as 
soluções básicas e pegar a melhor (de acordo com a 
função objetivo) que seja viável.
Porém o número de soluções básicas é:
Este número pode ser muito grande e, portanto, o método 
é ineficiente e só serve para problemas pequenos.
( )
!
! !
n n
m m n m
 
= 
− 
40xmadeira
5 10 15
x
a
l
u
m
í
n
i
o
5
1
0
VARIÁVEIS BÁSICAS VARIÁVEIS NÃO BÁSICAS
FOLGACORTE, FOLGAMONTAGEM, FOLGAACABAMENTO XMADEIRA, XALUMÍNIO
XMADEIRA, FOLGAMONTAGEM, FOLGAACABAMENTO FOLGACORTE, XALUMÍNIO
XALUMÍNIO, FOLGAMONTAGEM, FOLGAACABAMENTO FOLGACORTE, XMADEIRA
FOLGACORTE, XMADEIRA, FOLGAACABAMENTO FOLGAMONTAGEM, XALUMÍNIO
FOLGACORTE, XALUMÍNIO, FOLGAACABAMENTO FOLGAMONTAGEM, XMADEIRA
FOLGACORTE, FOLGAMONTAGEM, XMADEIRA FOLGAACABAMENTO, XALUMÍNIO
FOLGACORTE, FOLGAMONTAGEM, XALUMÍNIO FOLGAACABAMENTO, XMADEIRA
XMADEIRA, XALUMÍNIO, FOLGACORTE FOLGAMONTAGEM, FOLGAACABAMENTO
XMADEIRA, XALUMÍNIO, FOLGAMONTAGEM FOLGACORTE, FOLGAACABAMENTO
XMADEIRA, XALUMÍNIO, FOLGAACABAMENTO FOLGACORTE, FOLGAMONTAGEM
Geometria das soluções básicas
41
As soluções básicas viáveis correspondem aos 
pontos extremos do espaço de soluções.
Geometria das soluções básicas viáveis
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 fins lucrativos.