Baixe o app para aproveitar ainda mais
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
Compartilhar