A maior rede de estudos do Brasil

Grátis
50 pág.
Modulo 2 - Curso de Otimizacao Linear

Pré-visualização | Página 1 de 4

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értices

Crie agora seu perfil grátis para visualizar sem restrições.