Modulo 2 - Curso de Otimizacao Linear

Prévia do material em texto

Pontifícia Universidade Católica do Rio de Janeiro (PUC-Rio)
Departamento de Engenharia Elétrica (DEE)Departamento de Engenharia Elétrica (DEE)
www.ele.puc-rio.br
Curso de Otimização Linear
aplicado ao Setor Elétricoaplicado ao Setor Elétrico
Módulo 2Módulo 2
Prof. Alexandre Street
1
Setembro de 2010
AgendaAgenda
Módulo 1 – Modelagem de problemas de PL:
historia da Programação Linear;historia da Programação Linear;
modelagem de problemas (foco no setor elétrico: exemplo de contratação de 
energia);
interpretação geométricainterpretação geométrica;
Exercícios com Excel.
Módulo 2 – Propriedades das soluções e o Método Simplex:
soluções básicas viáveis e suas interpretações;
método simplex;método simplex;
exercícios (hands on).
Módulo 3 – Teoria de dualidade e análise de sensibilidade
Módulo 4 – Decomposição de Benders e PDDE 
2
Soluções básicas (SB) e Soluções Básicas Viáveis (SBV)Soluções básicas (SB) e Soluções Básicas Viáveis (SBV)
Utilizando o exemplo da Produção
Forma padrão do problema de PL
Apenas restrições de Igualdade: A⋅x=b
Para transformarmos uma desigualdade em igualdade adicionamos uma variável de
folga.folga.
As folgas não devem alterar a região viável do problema original.
xB(1.1) Maximizar, ≥ 4 ⋅ + 3 ⋅ (1). : 2 ⋅ + 1 ⋅ + 1 = 4 (1.1)4(1 2) 1 ( )1 ⋅ + 2 ⋅ + 2 = 4 (1.2)2(1.2)
2 4
3
xA2 4
Soluções Básicas Viáveis (SBV)Soluções Básicas Viáveis (SBV)
Soluções básicasMaximizar 4 ⋅ + 3 ⋅ (1)Maximizar, ≥ 4 + 3 (1). : 2 ⋅ + 1 ⋅ + 1 = 4 (1.1)1 ⋅ + 2 ⋅ + 2 = 4 (1.2)m
xB(1.1)
l õ X X(f)
n m+
4
2
(1.2)
soluções XA XB s1 s2
a (SBV) 0 0 4 4
b (SBV) 2 0 0 2(e)
( )
2 b (SBV) 2 0 0 2
c (SB) 4 0 -4 0
d (SBV) 4/3 4/3 0 0
( )
(d)
xA2 4
e (SBV) 0 2 2 0
f (SB) 0 4 0 -4(a) (b)
(c)
4
Soluções Básicas Viáveis (SBV)Soluções Básicas Viáveis (SBV)
Interpretação das variáveis na forma padrão:
Todas as variáveis podem ser vistas como “folgas”. As variáveis originais podem ser
consideradas folgas das restrições de positividade x ≥ 0
Solução básica (SB) é aquela na qual n (número de variáveis originais)
componentes do vetor solução (incluindo as folgas) estão zeradas , ou seja, ép ç ( g ) , j ,
uma solução apoiada na interseção de n restrições.
xB(1.1)
l õ X XE ( ) t d
4
(1 2)
soluções XA XB s1 s2
a (SBV) 0 0 4 4
b (SBV) 2 0 0 2
(f)
Ex: em (c), temos duas 
restrições ativas:
xB ≥ 0 e a (1.2).
2
(1.2) b (SBV) 2 0 0 2
c (SB) 4 0 -4 0
d (SBV) 4/3 4/3 0 0
(d)
(e)
x2 4
e (SBV) 0 2 2 0
f (SB) 0 4 0 -4
(a) (b)
(c)
5
xA2 4(a) (b)
Soluções Básicas Viáveis (SBV)Soluções Básicas Viáveis (SBV)
Interpretação das variáveis na forma padrão:
Todas as variáveis podem ser vistas como “folgas”. As variáveis originais podem ser
consideradas folgas das restrições de positividade x ≥ 0
Solução básica viável (SBV) é uma solução básica em que as m componentes
remanescentes são todas não negativas.g
SBV são os vértices do poliedro de soluções viáveis (℘), pois não há violação.
xB(1.1)
l õ X XE (d) t d
4
(1 2)
soluções XA XB s1 s2
a (SBV) 0 0 4 4
b (SBV) 2 0 0 2
(f)
Ex: em (d), temos duas 
restrições ativas:
a (1.1) e (1.2).
2
(1.2) b (SBV) 2 0 0 2
c (SB) 4 0 -4 0
d (SBV) 4/3 4/3 0 0
(d)
(e)
℘
x2 4
e (SBV) 0 2 2 0
f (SB) 0 4 0 -4
(a) (b)
(c)
6
xA2 4(a) (b)
Soluções Básicas Viáveis (SBV)Soluções Básicas Viáveis (SBV)
Caracterização das SBV:
Número de variáveis na forma padrão: n+m
Número de restrições: m
Uma SBV tem: n zeros e m valores não negativos x = [---xN---|--xB--]T ,
• Onde xN = [0,...,0]T e xB ≥ 0.Onde xN [0,...,0] e xB ≥ 0.
• xN é denominado de vetor de variáveis não básicas e xB de variáveis básicas.
xB(1.1)
l õ X X
4
(1 2)
soluções XA XB s1 s2
a (SBV) 0 0 4 4
b (SBV) 2 0 0 2
(f)
2
(1.2) b (SBV) 2 0 0 2
c (SB) 4 0 -4 0
d (SBV) 4/3 4/3 0 0
(d)
(e)
x2 4
e (SBV) 0 2 2 0
f (SB) 0 4 0 -4
(a) (b)
(c)
7
xA2 4(a) (b)
Soluções Básicas Viáveis (SBV)Soluções Básicas Viáveis (SBV)
Caracterização das SBV:
Número de variáveis na forma padrão: n+m
Número de restrições: m
Com n componentes zeradas, o vetor x possui apenas m componentes que podem
ser diferentes de zero. Como existem m restrições, uma vez escolhidas as nç ,
componentes não básicas, o vetor xB será único.
xB(1 1) l õ X XB
4
(1.1) soluções XA XB s1 s2
a (SBV) 0 0 4 4
b (SBV) 2 0 0 2
(f)
2
(1.2)
b (SBV) 2 0 0 2
c (SB) 4 0 -4 0
d (SBV) 4/3 4/3 0 0(d)
(e)
e (SBV) 0 2 2 0
f (SB) 0 4 0 -4(c)
8
xA2 4(a) (b)
Soluções Básicas Viáveis (SBV)Soluções Básicas Viáveis (SBV)
Caracterização das SBV:
B é uma matriz mxm contendo as colunas da matriz A (da forma padrão)
correspondentes às variáveis básicas.
N é uma matriz mxn contendo as colunas da matriz A (da forma padrão)
correspondentes às não variáveis básicas.
xB(1 1) l õ X X
⋅ = | ⋅ = ⋅ + ⋅ = 
B
4
(1.1) soluções XA XB s1 s2
a (SBV) 0 0 4 4
b (SBV) 2 0 0 2
(f)
2
(1.2)
b (SBV) 2 0 0 2
c (SB) 4 0 -4 0
d (SBV) 4/3 4/3 0 0(d)
(e)
e (SBV) 0 2 2 0
f (SB) 0 4 0 -4(c)
9
xA2 4(a) (b)
Soluções Básicas Viáveis (SBV)Soluções Básicas Viáveis (SBV)
Caracterização das SBV:
B é uma matriz mxm contendo as colunas da matriz A (da forma padrão)
correspondentes às variáveis básicas.
N é uma matriz mxn contendo as colunas da matriz A (da forma padrão)
correspondentes às não variáveis básicas.
xB(1 1) l õ X X
= − ⋅ − − ⋅ ⋅ 
B
4
(1.1) soluções XA XB s1 s2
a (SBV) 0 0 4 4
b (SBV) 2 0 0 2
(f)
2
(1.2)
b (SBV) 2 0 0 2
c (SB) 4 0 -4 0
d (SBV) 4/3 4/3 0 0(d)
(e)
e (SBV) 0 2 2 0
f (SB) 0 4 0 -4(c)
10
xA2 4(a) (b)
Soluções Básicas Viáveis (SBV)Soluções Básicas Viáveis (SBV)
Caracterização das SBV:
Exemplo:Maximizar, ≥ 4 ⋅ + 3 ⋅. : 2 ⋅ + 1 ⋅ + 1 = 4 = 2 1 1 01 2 0 1 = 1 
xB(1 1) l õ X X
1 ⋅ + 2 ⋅ + 2 = 4 2
B
4
(1.1) soluções XA XB s1 s2
a (SBV) 0 0 4 4
b (SBV) 2 0 0 2
(f)
2
(1.2)
b (SBV) 2 0 0 2
c (SB) 4 0 -4 0
d (SBV) 4/3 4/3 0 0(d)
(e)
e (SBV) 0 2 2 0
f (SB) 0 4 0 -4(c)
11
xA2 4(a) (b)
Soluções Básicas Viáveis (SBV)Soluções Básicas Viáveis (SBV)
Caracterização das SBV:
Exemplo:Maximizar, ≥ 4 ⋅ + 3 ⋅. : 2 ⋅ + 1 ⋅ + 1 = 4 = 2 1 1 01 2 0 1 = 1 
xB(1 1) l õ X X
1 ⋅ + 2 ⋅ + 2 = 4 2
B
4
(1.1) soluções XA XB s1 s2
a (SBV) 0 0 4 4
b (SBV) 2 0 0 2
(f) = 12 = 44 
2
(1.2)
b (SBV) 2 0 0 2
c (SB) 4 0 -4 0
d (SBV) 4/3 4/3 0 0(d)
(e)
( 0,0,4,4 ) = 0
e (SBV) 0 2 2 0
f (SB) 0 4 0 -4(c)
12
xA2 4(a) (b)
Soluções Básicas Viáveis (SBV)Soluções Básicas Viáveis (SBV)
Caracterização das SBV:
Exemplo:Maximizar, ≥ 4 ⋅ + 3 ⋅. : 2 ⋅ + 1 ⋅ + 1 = 4 = 2 1 1 01 2 0 1 = 1 
xB(1 1) l õ X X
1 ⋅ + 2 ⋅ + 2 = 4 2
B
4
(1.1) soluções XA XB s1 s2
a (SBV) 0 0 4 4
b (SBV) 2 0 0 2
(f) = 2 = 22 
2
(1.2)
b (SBV) 2 0 0 2
c (SB) 4 0 -4 0
d (SBV) 4/3 4/3 0 0(d)
(e)
( 2,0,0,2 ) = 8
e (SBV) 0 2 2 0
f (SB) 0 4 0 -4(c)
13
xA2 4(a) (b)
Soluções Básicas Viáveis (SBV)Soluções Básicas Viáveis (SBV)
Caracterização das SBV:
Exemplo:Maximizar, ≥ 4 ⋅ + 3 ⋅. : 2 ⋅ + 1 ⋅ + 1 = 4 = 2 1 1 01 2 0 1 = 1 
xB(1 1) l õ X X
1 ⋅ + 2 ⋅ + 2 = 4 2
B
4
(1.1) soluções XA XB s1 s2
a (SBV) 0 0 4 4
b (SBV) 2 0 0 2
(f) = = 4/34/3
2
(1.2)
b (SBV) 2 0 0 2
c (SB) 4 0 -4 0
d (SBV) 4/3 4/3 0 0(d)
(e)
43 , 43 , 0,0 = 283= 9.3 …
e (SBV) 0 2 2 0
f (SB) 0 4 0 -4(c)
9.3 …
14
xA2 4(a) (b)
AgendaAgenda
Módulo 1 (4 horas) – Modelagem de problemas de PL
historia da Programação Linear;historia da Programação Linear;
modelagem de problemas (foco no setor elétrico: exemplo de contratação de 
energia);
interpretação geométricainterpretação geométrica;
exercícios com Excel;
Módulo 2 (4 horas) – Propriedades das soluções e o Método Simplex
soluções básicas viáveis e suas interpretações;
método simplex;método simplex;
exercícios (hands on).
Módulo 3 (4 horas) – Teoria de dualidade e análise de sensibilidade
Módulo 4 (4 horas) – Decomposição de Benders e PDDE 
15
Método Simplex (simplificado)Método Simplex (simplificado)
Curiosidade: O que é um simplex?
16
Método Simplex (simplificado)Método Simplex (simplificado)
Curiosidade: O que é um simplex?
Um simplex é um poliedro que tem a seguinte propriedade:
• Os seus vérticesformam um conjunto de pontos independentes afins.
Por exemplo: 3 pontos no ℜ2 {v1, v2, v3}.
Os vetores {v2-v1, v3-v1} são linearmente independentes.Os eto es { 2 1, 3 1} são ea e te depe de tes.
Um simplex com N+1 pontos (3 no exemplo) é um simplex N-dimensional.
Obviamente, a maior dimensão de um simplex no ℜN é N.
v2
Simplex
17
v1 v3
Método Simplex (simplificado)Método Simplex (simplificado)
Curiosidade: Por que o método simplex tem esse nome?
v2
Simplex
18
v1 v3
Método Simplex (simplificado)Método Simplex (simplificado)
Curiosidade: Por que o método simplex tem esse nome?
Porque na busca da solução ótima, o método “pula” de vértice em vértice do
poliedro definido pelas restrições do problema, de maneira que cada “pulo” seja
entre vértices “vizinhos” de um mesmo simplex.
O simplex que define a vizinhança de pontos entre os quais o método pode buscar
uma próxima solução é tal que: apenas uma única troca de variável básica (≥0) por
uma não básica (=0) seja verificada.
xBB
4
2 (d)
(e)
[0,2,2,0]
(b)
Simplex
[0,0,4,4]
[2,0,0,2]
19
xA2 4(a)
(b)
[ , , , ]
Método Simplex (simplificado)Método Simplex (simplificado)
Curiosidade: Por que o método simplex tem esse nome?
Porque na busca da solução ótima, o método “pula” de vértice em vértice do
poliedro definido pelas restrições do problema, de maneira que cada “pulo” seja
entre vértices “vizinhos” de um mesmo simplex.
O simplex que define a vizinhança de pontos entre os quais o método pode buscar
uma próxima solução é tal que ocorra apenas uma única troca de variável básica
(≥0) por uma não básica (=0).
xBB
4 Não podemos ir para a solução (d), estando em (a), pois implica 
2 (d)
(e)
[0,2,2,0]
[4/3,4/3,0,0]
( ), ( ), p p
em uma troca de duas variáveis 
básicas por não básicas.
(b)
Simplex 1[0,0,4,4]
[2,0,0,2]
[ , , , ]
20
xA2 4(a)
(b)
[ , , , ]
Método Simplex (simplificado)Método Simplex (simplificado)
Curiosidade: Por que o método simplex tem esse nome?
Optando pelo passo ruma à SBV (b), temos um novo simplex de vizinhanças que
contemple a volta para (a) ou a ida para (d), ambos com apenas uma troca!
xBB
4
2 (d)
(e)
[4/3 4/3 0 0]
(b)
[0,0,4,4]
[2,0,0,2]Simplex 2
[4/3,4/3,0,0]
21
xA2 4(a)
(b)
[ , , , ]
Método Simplex (simplificado)Método Simplex (simplificado)
Qual o significado algébrico de um pulo entre vértices?
“Uma troca” de status entre duas variáveis (uma básica e outra não básica).
Maximizar, ≥ 4 ⋅ + 3 ⋅2 + 1 + 4
Podemos escrever o problema original na forma padrão,
no formato de um “dicionário”, em que m variáveisxB
. : 2 ⋅ + 1 ⋅ + 1 = 41 ⋅ + 2 ⋅ + 2 = 4
estão parametrizadas pelas n remanescentes. A
escolha das n variáveis que parametrizarão o valor
das demais m deve ser de acordo com a SBV
B
4
corrente.
Como as variáveis básicas estão em função só das
não básicas, a solução pode ser lida diretamente do2 (d)
(e)
[0,2,2,0]
dicionário
(b)
Simplex
[0,0,4,4]
[2,0,0,2]
= 0 + 4 ⋅ + 3 ⋅1 = 4 − 2 ⋅ − 1 ⋅
22
xA2 4(a)
(b)
[ , , , ] 2 = 4 − 1 ⋅ − 2 ⋅
Método Simplex (simplificado)Método Simplex (simplificado)
Uma troca de uma variável não básica por uma básica implica em:
Dado que estamos em uma SBV, devemos aumentar o valor de uma variável nãoq ,
básica de maneira que
1. a função objetivo aumente de valor
2 e que nenhuma variável básica se torne negativa (manter viável)
xB
2. e que nenhuma variável básica se torne negativa (manter viável).
até que alguma variável básica se torne zero.
= 0 + 4 ⋅ + 3 ⋅1 = 4 − 2 ⋅ − 1 ⋅
B
4
Variável básica mais 
limitante, que se tornará 12 = 4 − 1 ⋅ − 2 ⋅
2 (d)
(e)
não básica (=0)
(b)
Simplex
[0,0,4,4]
[2,0,0,2] Variável não básicaSelecionada para se 
23
xA2 4(a)
(b)
[ , , , ]
Tornar básica (≥ 0)
Método Simplex (simplificado)Método Simplex (simplificado)
Uma troca de uma variável não básica por uma básica implica em:
Ao aumentar o valor de uma variável não básica de maneira que até que variávelq q
básica mais restritiva se torne zero, implica em trocar ambas de posição no
dicionário.
xB
= 0 + 4 ⋅ + 3 ⋅1 = 4 − 2 ⋅ − 1 ⋅2 = 4 − 1 ⋅ − 2 ⋅B
4
2 = 4 1 2
= 0 + 4 ⋅ + 3 ⋅= 2 − 12 ⋅ 1 − 12 ⋅2 (d)(e) 2 22 = 4 − 1 ⋅ − 2 ⋅
(b)
Simplex
[0,0,4,4]
[2,0,0,2]
24
xA2 4(a)
(b)
[ , , , ]
Método Simplex (simplificado)Método Simplex (simplificado)
Uma troca de uma variável não básica por uma básica implica em:
Ao realizarmos a troca, não temos mais um dicionário em que as variáveis básica, q
estão parametrizadas pelas não básicas
xA ainda permanece tanto na expressão de z (f.obj.) quanto na de s2
xB
= 0 + 4 ⋅ + 3 ⋅1 = 4 − 2 ⋅ − 1 ⋅2 = 4 − 1 ⋅ − 2 ⋅B
4
2 = 4 1 2
= 0 + 4 ⋅ + 3 ⋅= 2 − 12 ⋅ 1 − 12 ⋅2 (d)(e) 2 22 = 4 − 1 ⋅ − 2 ⋅
(b)
Simplex
[0,0,4,4]
[2,0,0,2]
25
xA2 4(a)
(b)
[ , , , ]
Método Simplex (simplificado)Método Simplex (simplificado)
Uma troca de uma variável não básica por uma básica implica em:
Devemos então substituir a expressão de xA nas demais equações para obtermos= 0 + 4 ⋅ 2 − 12 ⋅ 1 − 12 ⋅ + 3 ⋅ 
p A q ç p
um novo dicionário= 0 + 4 ⋅ + 3 ⋅ 
= 2 − 12 ⋅ 1 − 12 ⋅4 1 2 1 1 2 = 2 −
12 ⋅ 1 − 12 ⋅2 = 4 − 1 ⋅ − 2 ⋅ (1 1) 2 = 4 − 1 ⋅ 2 − 2 ⋅ 1 − 2 ⋅ − 2 ⋅xB
4
2(1.1)
2 (d)
(e) = 8 − 2 ⋅ 1 + 1 ⋅(1.2)
(b)
[2,0,0,2]
= 2 − 12 ⋅ 1 − 12 ⋅1 3 Simplex 2
26
xA2 4(a)
(b) 2 = 2 + 2 ⋅ 1 − 2 ⋅
Método Simplex (simplificado)Método Simplex (simplificado)
Qual deve ser a nova troca de variáveis que devemos fazer para melhorar a
função objetivo?= 8 − 2 ⋅ 1 + 1 ⋅1 1= 2 − 12 ⋅ 1 − 12 ⋅= 43 + 13 ⋅ 1 − 23 ⋅ 2
xB
4
(1.1) 3 3 1 3 2
2 (d)
(e)(1.2)
( )
[2,0,0,2]Simplex 2
27
xA2 4(a)
(b)
Método Simplex (simplificado)Método Simplex (simplificado)
Qual deve ser a nova troca de variáveis que devemos fazer para melhorar a
função objetivo?= 8 − 2 ⋅ 1 + 1 ⋅
2 1 1
Variável básica mais 
limitante, que se tornará 
não básica (=0)
= 2 − 2 ⋅ 1 − 2 ⋅= 43 + 13 ⋅ 1 − 23 ⋅ 2
xB
4
(1.1)
não básica ( 0)3 3 3
2 (d)
(e)(1.2)
Variável não básica
Selecionada para se 
Tornar básica (≥ 0)( )
[2,0,0,2]Simplex 2
Tornar básica (≥ 0)
28
xA2 4(a)
(b)
Método Simplex (simplificado)Método Simplex (simplificado)
Qual deve ser a nova troca de variáveis que devemos fazer para melhorar a
função objetivo? 4 1 2= 8 − 2 ⋅ 1 + 1 ⋅1 1 = 8 − 2 ⋅ 1 + 1 ⋅
43 + 13 ⋅ 1 − 23 ⋅ 2 1 1 4 1 2= 2 − 12 ⋅ 1 − 12 ⋅= 43 + 13 ⋅ 1 − 23 ⋅ 2
= 2 − 12 ⋅ 1 − 12 ⋅ 43 + 13 ⋅ 1 − 23 ⋅ 2= 4 + 1 ⋅ 1 − 2 ⋅ 2 
xB
4
(1.1) 3 3 1 3 2 3 + 3 1 3 2
Pare!
2 (d)
(e)
[4/3 4/3 0 0]
(1.2) = 283 − 53 ⋅ 1 − 23 ⋅ 2 Não podemos mais melhoramos a f.obj
[4/3,4/3,0,0]
Simplex 2
= 43 − 23 ⋅ 1 + 13 ⋅ 24 1 2 [2,0,0,2]
29
xA2 4(a)
(b) = 43 + 13 ⋅ 1 − 23 ⋅ 2
Método Simplex (Resumo)Método Simplex (Resumo)
O método simplex, na busca pelo ponto ótimo, inspeciona apenas os vértices
do poliedro (SBV). Um dos vértices sempre será o ótimo, caso este exista.
Recebe esse nome em função da maneira em que os pontos são visitados: em
uma vizinhança denominada simplex (um sub poliedro com propriedades
específicas)específicas).
Realizar uma troca entre uma variável básica por uma não básica é
equivalente a “pular” de um vértice para outro, com a propriedade de que o
segundo será vizinho, dentro de um simplex, do primeiro.
Um dicionário é constituído pela parametrização de m variáveis nas demais n
remanescentes:= ⋅ + ⋅ = ⋅ − ⋅ + − ⋅ − ⋅ ⋅ Custo reduzido
O método não para enquanto houver custos reduzidos positivos
= − ⋅ − − ⋅ ⋅ = − ⋅ − − ⋅ ⋅ 
30
O método não para enquanto houver custos reduzidos positivos
(maximização) e nenhuma direção extrema identificada.
Método Simplex (Condições de parada)Método Simplex (Condições de parada)
O método para quando:
Custos reduzidos forem negativos (no problema de maximização)
• Não melhoramos mais a função objetivo ao trocarmos nenhuma variável não básica por
básica.
C sto red ido ̂ ̂ ≤ 0
= ⋅ − ⋅ + − ⋅ − ⋅ ⋅xB(1.1)
Custo reduzido: = 1, … , ≤ 0 
= += − ⋅ − − ⋅ ⋅ 4
(1 2) cT
2
(1.2)
4/3
cT ̂ = ( ) − ⋅ −1 ⋅ ≤ 0 ∀ = 1, … ,
xA2 44/3
31
xA2 44/3
Método Simplex (Condições de parada)Método Simplex (Condições de parada)
O método para quando:
Custosreduzidos forem negativos (no problema de maximização): ponto ótimo!
• Não melhoramos mais a função objetivo ao trocarmos nenhuma variável não básica por
básica.
Existir uma variável não básica que melhore a função objetivo e que não seja
= ⋅ − ⋅ + − − ⋅ ⋅limitada por nenhuma variável básica (raio estremo): problema ilimitado!xB(1.1) = − ⋅ − − ⋅ ⋅ 4
(1 2)(1.2)
1
Direção extrema: ( ) = 1⋮ ≤ 0 
xA1
cT
32
xA1
Método Simplex (fase 1)Método Simplex (fase 1)
A escolha da primeira iteração deve ser, sempre que possível, a seguinte:
Variáveis básicas: folgas.
Variáveis não básicas: originais do problema.
Por que? Porque B = Identidade
Mas isso requer que o ponto 0 (origem) seja SBV.
xB
Maximizar, ≥ 4 ⋅ + 3 ⋅2 + 1 + 4
q q p ( g ) j
B
4
. : 2 ⋅ + 1 ⋅ + 1 = 41 ⋅ + 2 ⋅ + 2 = 4
2 (d)
(e)
[0,2,2,0] = 0 + 4 ⋅ + 3 ⋅1 = 4 − 2 ⋅ − 1 ⋅2 = 4 − 1 ⋅ − 2 ⋅
(b)
Simplex
[0,0,4,4]
[2,0,0,2]
2 4 1 2
33
xA2 4(a)
(b)
[ , , , ]
Método Simplex (fase 1)Método Simplex (fase 1)
E se a origem não for uma SBV?
Por exemplo, se tivéssemos a restrição + ≥ 1
Maximizar≥ 4 ⋅ + 3 ⋅
xB
, ≥. : 2 ⋅ + 1 ⋅ + 1 = 41 ⋅ + 2 ⋅ + 2 = 41 + 1 = 1O ponto [0 0] não éB
4 = 0 + 4 ⋅ + 3 ⋅
1 ⋅ + 1 ⋅ − 3 = 1O ponto [0,0] não é 
mais viável!
2 (d)
(e) 1 = 4 − 2 ⋅ − 1 ⋅2 = 4 − 1 ⋅ − 2 ⋅ (f)
(b)
[0,0,4,4]
23 = −1 + 1 ⋅ + 1 ⋅1 (f)
(g)
34
xA2 4(a)
(b)
[ , , , ]
1
Método Simplex (fase 1)Método Simplex (fase 1)
E se a origem não for uma SBV?
Não temos uma SBV inicial!!!
Maximizar 4 ⋅ + 3 ⋅O que é pré-requisito para o método, que só é capaz de encontrar uma novaSBV se estiver em uma.O que fazer?
xB
Maximizar, ≥ 4 + 3. : 2 ⋅ + 1 ⋅ + 1 = 41 ⋅ + 2 ⋅ + 2 = 4
O que fazer?
B
4
1 ⋅ + 1 ⋅ − 3 = 1= 0 + 4 ⋅ + 3 ⋅
2 (d)
(e)
(f)
 = 0 + 4 + 3
1 = 4 − 2 ⋅ − 1 ⋅= 4 1 2 
(b)
[0,0,4,4]
1
(f)
(g)
2 = 4 − 1 ⋅ − 2 ⋅3 = −1 + 1 ⋅ + 1 ⋅
35
xA2 4(a)
(b)
[ , , , ]
1
Método Simplex (fase 1)Método Simplex (fase 1)
E se a origem não for uma SBV?
Devemos inserir uma variável “artificial” (auxiliar) que garanta que o problema
á lseja sempre viável.
O novo objetivo passa a ser minimizá-la até zero.
Se isso for possível significa que temos uma SBV inicial para a fase 2
xB
Se isso for possível, significa que temos uma SBV inicial para a fase 2.Minimizar≥w≥0B
4 Minimizar. : ⋅ − ⋅ ≤
2 (d)
(e)
, ≥w≥0. : 2 ⋅ + 1 ⋅ + 1 − = 41 ⋅ + 2 ⋅ + 2 − = 4(f)
(b)
1 ⋅ + 2 ⋅ + 2 − = 4−1 ⋅ − 1 ⋅ + 3 − = −11 (f)
(g)
36
xA2 4(a)
(b)1
Método Simplex (fase 1)Método Simplex (fase 1)
E se a origem não for uma SBV?
Como iniciar?
D f t lh d f l iá i bá iDa mesma forma que antes, escolhendo as folgas como variáveis básicas,
porém na primeira iteração, contra o princípio de melhorar a f.obj. (minimização),
deveremos selecionar (obrigatoriamente) a variável w para entrar na base, e
l é á l bá
xB
aumentar o seu valor até que a variável básica mais negativa se torne zero.= 0 +
V iá l bá iB
4
1 = 4 − 2 ⋅ − 1 ⋅ +2 = 4 − 1 ⋅ − 2 ⋅ +1 + 1 + 1 + 
Variável básica 
mais negativa, 
que se tornará 
não básica (=0)
2 (d)
(e)
(f)
3 = −1 + 1 ⋅ + 1 ⋅ +não básica (=0)
(b)
1
(f)
(g)
Variável não básica
Selecionada para se 
Tornar básica (≥ 0)
37
xA2 4(a)
(b)1 Tornar básica (≥ 0)
Método Simplex (fase 1)Método Simplex (fase 1)
E se a origem não for uma SBV?
Ao realizarmos esta troca, teremos um dicionário viável.
Equivalente a expandir o poliedro até que ele contenha a origem.
Neste novo dicionário, o método simplex pode ser empregado de maneira
análoga a que vimos antes
xB
análoga a que vimos antes. = 0 +
1 = 4 − 2 ⋅ − 1 ⋅ + B
4
2 = 4 − 1 ⋅ − 2 ⋅ +3 = −1 + 1 ⋅ + 1 ⋅ +
2 (d)
(e)
(f)
 = 1 − 1 ⋅ − 1 ⋅ + 3
(b)
1
(f)
(g)
1 = 5 − 3 ⋅ − 2 ⋅ + 32 = 5 − 2 ⋅ − 3 ⋅ + 31 1 1 
38
xA2 4(a)
(b)1 = 1 − 1 ⋅ − 1 ⋅ + 3
Método Simplex (fase 1)Método Simplex (fase 1)
E se a origem não for uma SBV?
Ao realizarmos esta troca, teremos um dicionário viável.
Equivalente a expandir o poliedro até que ele contenha a origem.
Neste novo dicionário, o método simplex pode ser empregado de maneira
análoga a que vimos antes
xB
análoga a que vimos antes. = 1 − 1 ⋅ − 1 ⋅ + 3
1 = 5 − 3 ⋅ − 2 ⋅ + 3 B
4
2 = 5 − 2 ⋅ − 3 ⋅ + 3= 1 − 1 ⋅ − 1 ⋅ + 3
2 (d)
(e)
(f)
 = + 1 ⋅ + 0 ⋅ + 0 ⋅ 3
(b)
1
(f)
(g)
3
1 = 2 + 3 ⋅ + 1 ⋅ − 2 ⋅ 32 = 3 + 2 ⋅ − 1 ⋅ − 1 ⋅ 3 
39
xA2 4(a)
(b)1
2 3= 1 − 1 ⋅ − 1 ⋅ + 1 ⋅ 3
Método Simplex (fase 1)Método Simplex (fase 1)
Caso w* > 0, então o problema é inviável!
Por fim, chegamos a condição de otimalidade (custos reduzidos positivos).
Encontramos uma SBV em que w é não básica (= 0).
Logo podemos iniciar a fase 2, que consistem em retirar w do dicionário, e
voltar com a f obj original (substituindo as variáveis básicas nesta) e seguir
xB
voltar com a f.obj. original (substituindo as variáveis básicas nesta) e seguir
os passos do simplex. = + 1 ⋅ + 0 ⋅ + 0 ⋅ 3
B
4
1 = 2 + 3 ⋅ + 1 ⋅ − 2 ⋅ 32 = 3 + 2 ⋅ − 1 ⋅ − 1 ⋅ 3= 1 − 1 ⋅ − 1 ⋅ + 1 ⋅ 
2 (d)
(e)
(f)
= 1 − 1 ⋅ − 1 ⋅ + 1 ⋅ 3= 4 ⋅ (1 − 1 ⋅ + 1 ⋅ 3) + 3
(b)
1
(f)
(g)
1 = 2 + 1 ⋅ − 2 ⋅ 32 = 3 − 1 ⋅ − 1 ⋅ 31 1 + 1 
40
xA2 4(a)
(b)1 = 1 − 1 ⋅ + 1 ⋅ 3
Método Simplex (fase 2)Método Simplex (fase 2)
Este dicionário corresponde à primeira SBV do problema original (já com o
poliedro original).
é d d é ó l áO método deve seguir até encontrar a SBV ótima, que neste exemplo será a
mesma do exercício anterior.
xB = 4 ⋅ −1 ⋅ + 4 ⋅ 3B
4
 4 1 + 4 3
1 = 2 + 1 ⋅ − 2 ⋅ 32 = 3 − 1 ⋅ − 1 ⋅ 3 
2 (d)
(e)
(f)
2 = 3 − 1 ⋅ − 1 ⋅ 3= 1 − 1 ⋅ + 1 ⋅ 3
(b)
1
(f)
(g)
41
xA2 4(a)
(b)1
Método Simplex (Resumo do algoritmo)Método Simplex (Resumo do algoritmo)
Inicialização: Verifique se a origem é SBV. 
Se origem é SBV, então: vá para a fase 2 com o dicionário composto por variáveis básicas (as 
folgas) e não básicas (as originais)folgas) e não básicas (as originais).
Caso contrário, vá para a fase 1.
Fase 1: Adicionar uma variável artificial ao problema e minimizá-la.
Introduzir uma variável auxiliar subtraindo o lado esquerdo de todas as restrições e resolver o 
problema w* = Min(w,x){w |s.a: A⋅x – 1⋅w ≤ b}
Se w* = 0, então: vá para a fase 2 com o dicionário final obtido na fase 1, retirando a coluna 
relativa a w (que deve ser var não básica)relativa a w (que deve ser var. não básica). 
• A função objetivo será a função original com as variáveis básicas do dicionário substituídas.
Caso contrário (w* > 0), então: PARE! Problema Inviável.
Fase 2: Dado um dicionário viável realize trocas sucessivas de variáveis básicas por nãoFase 2: Dado um dicionário viável, realize trocas sucessivas de variáveis básicas por não 
básicas até uma das condições de parada.
Selecione uma variável não básica com custo reduzido que melhore a f.obj (positivo para 
maximização e negativo para minimização) e encontre a variável básica mais restritiva: amaximização e negativo para minimização) e encontre a variável básica mais restritiva: a 
primeira que assumir o valor zero ao aumentarmos o valor da não básica selecionada. 
• Se cNT-cBT⋅B-1⋅N ≤ 0 (custos reduzidos não melhoram a f.obj.), então: PARE! Ótimo encontrado.
• Se existir uma variável não básica que melhore a f.obj. e que possa ser aumentada indefinidamente 
42
(coeficientes da matriz positivos), então: PARE! Problema ilimitado.
AgendaAgenda
Módulo 1 (4 horas) – Modelagem de problemas de PL
historia da Programação Linear;historia da Programação Linear;
modelagem de problemas (foco no setor elétrico: exemplo de contratação de 
energia);
interpretação geométricainterpretação geométrica;
exercícios com Excel;
Módulo 2 (4 horas) – Propriedades das soluções e o Método Simplex
soluções básicas viáveis e suas interpretações;
método simplex;método simplex;
exercícios (hands on).
Módulo 3 (4 horas) – Teoria de dualidade e análise de sensibilidade
Módulo 4 (4 horas) – Decomposição de Benders e PDDE 
43
Exercícios Simplex (otimalidade)Exercícios Simplex (otimalidade)
Mix ótimo de combustível em um carro flex (álcool e gasolina):
A autonomia do álcool é aA (Km/litro) < que a da gasolina aG (Km/litro);
A autonomia do mix é o mix das autonomias;
Os custossão conhecidos e valem respectivamente: cA e cG (ambos em R$/litro);
O tanque de combustível tem volume V (litros);O tanque de combustível tem volume V (litros);
Desejamos percorrer uma distância d (Km) factível (d < aA⋅V) a mínimo custo.
44
Exercícios Simplex (otimalidade)Exercícios Simplex (otimalidade)
Mix ótimo de combustível em um carro flex (álcool e gasolina):
a) Formule o problema e desenhe o seu poliedro, indique o gradiente da f.obj. e a 
á l d blreião viável do problema;
b) Mostre a condição necessária sobre a relação entre os custos (cA/cG) para que o
consumo ótimo seja abastecer apenas com álcool (deixe em função dasj p ( ç
autonomias).
45
Exercícios Simplex (SBV)Exercícios Simplex (SBV)
Suponha o problema de regressão linear multivariada em que se deseja
encontrar os parâmtros do modelo (regressores) minimizando os errose co a os pa â os do ode o ( eg esso es) a do os e os
absolutos entre as observações e a predição do modelo:
a) Desenhe a função módulo de cada erro e mostre que esta é convexa;
b) M t tili it t f bl ã lib) Mostre como utilizar esse conceito para transformar o problema não linear 
abaixo em um problema de PL;
c) Mostre uma segunda formulação para esse problema com menos restrições que
t ia anterior;
d) Mostre que uma SBV ótima em que os parâmetros do modelo sejam todos
diferentes de zero, o plano estará sempre tocando em n+1 pontos.Minimizar∈ℝ | |y ∈ℝ =1. : = − ⋅ − ∀ = 1, … , a1 x2 ei
46
=1x1
Exercícios Simplex (SBV)Exercícios Simplex (SBV)
Mostre que uma SBV ótima em que os parâmetros do modelo sejam todos
diferentes de zero, o plano estará sempre tocando em m+1 pontos:
Temos 2(n+m+1) variáveis e m restrições;Temos 2(n+m+1) variáveis e m restrições;
Se o modelo tiver regressores não nulos, com certeza n+1 das 2(n+1) variáveis a+, a-, b+
e b- estarão na base. As demais estão fora da base (zero), restando assim, um total de 
m-n-1 variáveis básicas a serem definidas.
Das 2m variáveis de erro, apenas m poderiam estar positivas (na base), pois ou o erro é 
positivo ou negativo;
Como já ocupamos n+1 posições com os regressores, n+1 variaveis de erro estarão com 
ambas as componentes + e – zeradas;
Isso implica que o plano terá que, necessariamente tocar em pelo menos n+1 
observações.
Minimizar+, −∈ℝ+ + + −=1+, −∈ℝ+ +, −≥0 =1: + − − + + − − ⋅ + ( + − −) = ∀ = 1
47
. : + + ( )=1 ∀ 1, … ,
Material ExtraMaterial Extra
O modelo a seguir é conhecido como modelo de regressão quantílica tendo 
preferencialmente β∈[0,1];
d β í d l b lQuando β = 0.5, recaímos no caso do valor absoluto;
Mais robusto que a média a valores extremos.
Minimizar+, −∈ℝ++, −∈ℝ+ ⋅ + + (1 − ) ⋅ −=1+, −≥0 . : + − − + + − − ⋅ + ( + − −)1 = ∀ = 1, … ,=1
48
Material ExtraMaterial Extra
Podemos mostrar que o resultado deste modelo faz uma regressão no quantil β das 
observações
Minimizar+ ⋅ + + (1 − ) ⋅ −+, −∈ℝ++, −∈ℝ+ +, −≥0 ( )=1. : + − − + + − − ⋅ + ( + − −)=1 = ∀ = 1, … ,
f(ei)
β1-β
49
ei
Material ExtraMaterial Extra
Podemos mostrar que o resultado deste modelo faz uma regressão no quantil β das 
observações
50