A maior rede de estudos do Brasil

Grátis
74 pág.
Modulo 1 - Curso de Otimizacao Linear

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

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 1Módulo 1
Prof. Alexandre Street
1
Setembro de 2010
AgendaAgenda
Módulo 1 – Modelagem de problemas de PL
Módulo 2 – Propriedades das soluções e o Método SimplexMódulo 2 – Propriedades das soluções e o Método Simplex
Módulo 3 – Teoria de dualidade e análise de sensibilidade
Módulo 4 – Decomposição de Benders e PDDE 
2
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
Módulo 3 – Teoria de dualidade e análise de sensibilidade
Módulo 4 – Decomposição de Benders e PDDE 
3
Breve História da PLBreve História da PL
Pré simplex
(1823 e 1911) Fourier e o matemático de la Vallée Poussin escreveram trabalhos muito similares à 
ano19471823 1911 1928/33/39
programação linear, mas não obtiveram o impacto que Dantzig teve pela ausência de interesse em se 
otimizar sistemas grandes: não existia computadores até então.
(1928 e 33) von Neumann e Leontief contribuíram com trabalhos independentes em teoria de jogos e 
d l d i d t i i (I t i d t i t t t d l d L ti fem modelagem da industria americana (Interindustry input-output model – que deu a Leontief o 
Nobel em 1976).
(1939) Kantorovich escreveu sua monografia sobre modelos semelhantes aos da PL, mas foi 
completamente ignorado até duas décadas depois por motivos ideológicos na União Soviéticacompletamente ignorado até duas décadas depois por motivos ideológicos na União Soviética.
(1947) Dantzig formulou o problema do planejamento e logística militar como um PL: buscando deixar 
de lado os procedimentos ad hoc de especialistas utilizados como regras para se selecionar uma 
solução dentro viável. 
(3 de outubro de 1947) Dantzig encontra von Neumann em Princeton para mostrar o simplex e pedir 
sua opinião. Ao invés disso, von Neumman o demosntra o desenvolvimento da teoria de dualidade 
utilizando o Lema de Farkas. 
4
No verão de 1947, Dantzig propôs o método simplex para resolver o problema de planejamento e 
obteve resultados melhores que os obtidos pelo algoritmo proposto por von Neumann.
Breve História da PLBreve História da PL
Logo após o simplexPré simplex
(1949) Zero Symposium of mathematical programming na universidade de Chicago
ano19471823 1911 1928/33/39 1949 1950/51/52 1954
(1949) Zero Symposium of mathematical programming na universidade de Chicago.
(1950) Wolfe, Dantzig e outros desenvolveram soluções para lidar com casos degenerados.
(1951) Karush, Kuhn e Tucker começaram a desenvolver a área de Programação não 
li t é d f di õ d ti lid d b i i i i dlinear, através das famosas condições de otimalidade que receberam as iniciais dos nomes 
desses 3 pesquisadores (KKT). Mais tarde, em 1960, a teoria de dualidade foi estendida para 
problemas não lineares.
(1952) Ch C M ll d l i i li ã i l(1952) Charnes, Cooper e Mellon desenvolvem a primeira aplicação comercial para o 
problema de mistura de tipos de petróleo para a fabricação de gasolina.
(1954) William Orchard-Hays da Rand Corporation escreveu o primeiro código comercial 
para resolver problemas genéricos de programação linear. Muitas das idéias teóricas para se 
compactar a inversa de uma matriz, se aproveitar das formas esparsas e garantir 
estabilidade numérica foram implementadas nesse código. Isso fez com que este código se 
t i i l l d PL d t dé d E difi f PL
5
tornasse o principal solver de PL durante décadas. E modificou a forma com que a PL era 
encarada.
Breve História da PLBreve História da PL
8 anos após o 
simplex
Logo após o simplexPré simplex
(1955) Dantzig e Wolfe começaram a desenvolver o princípio da decomposição por de
19471823 1911 1928/33/39 1949/50/51/52 1955 19621958 1984
(1955) Dantzig e Wolfe começaram a desenvolver o princípio da decomposição por de 
problemas com estruturas em bloco e acoplamento através de restrições “complicadas”. 
Publicaram o artigo Princípios da Decomposição em 1959.
(1955) Dantzig publicou o artigo “Linear Programming under Uncertainty” mas desde 1950(1955) Dantzig publicou o artigo Linear Programming under Uncertainty , mas desde 1950 
Cooper já havia pensado no problema de restrições probabilísticas (Chance Constraints).
(1958) Gomory propôs um algoritmo de planos de corte para resolver problemas de 
programação inteira que combinado com algoritmos de Branch and Bound se mostrou aprogramação inteira, que combinado com algoritmos de Branch and Bound se mostrou a 
técnica mais promissora, até os dias de hoje, para resolver problemas inteiros.
(1962) Benders criou a versão dual de decomposição de Dantzig e Wolfe, para problemas 
com estr t ra em blocos triang lar e acoplamento atra és de ariá eis “complicadas”com estrutura em blocos triangular e acoplamento através de variáveis “complicadas”. 
Proposto inicialmente para resolver problemas de programação inteira mista, rapidamente 
foi adaptado para a Programação Estocástica de grande porte por John Birge (1985) e Mario 
Veiga Pereira (1991)
6
Veiga Pereira (1991).
(1984) Karmarkar propôs o algoritmo de pontos interiores com complexidade polinomial.
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étrica;interpretação geométrica;
Exercícios com Excel
Módulo 2 – Propriedades das soluções e o Método Simplex
Módulo 3 – Teoria de dualidade e análise de sensibilidade
Módulo 4 – Decomposição de Benders e PDDE 
7
Modelagem Matemática (Formulação de um Problema)Modelagem Matemática (Formulação de um Problema)
O processo de modelagem é a parte mais importante para se resolver um 
problema de otimização:problema de otimização:
Em geral, um problema bem formulado não garante que este será facilmente 
resolvido, porém um problema mal formulado certamente será muito mais difícil de 
se resolverse resolver.
Existem muitas classificações para formulações matemáticas:
1. Restritos e irrestritos
2. Lineares e não lineares
3. Convexos e não convexos
4 Combinatoriais4. Combinatoriais
5. Etc...
8
Modelagem Matemática (Formulação de um Problema)Modelagem Matemática (Formulação de um Problema)
Em linhas gerais, existem 4 passos básicos para se modelar um problema:
1. Compreensão do problema
id tifi ã d t l t d j t t N t t l t ã• identificação das partes relevantes que se deseja tratar. Nesta parte, geralmente são
excluídas uma série de relações que não implicam em uma direta, ou substancial,
participação no objetivo do problema.
2 Identificação das variáveis de decisão: x = [x x ]T2. Identificação das variáveis de decisão: x = [x1,...,xn]T
• quais são as variáveis que se deseja obter com a resolução do problema, ou seja, o que se
deseja encontrar (otimizar) e os seus respectivos limites superiores e inferiores.
3 Identificar a função objetivo do problema: f(x)3. Identificar a função objetivo do problema: f(x)
• especificar uma função que, dado uma possível configuração das variáveis de decisão,
reproduza o valor que se deseja maximizar ou minimizar (otimizar): lucro, custo,
confiabilidade, chance de se obter algum resultado, distância de algum nível deconfiabilidade, chance de se obter algum resultado, distância de algum nível de
referência, etc...
4. Identificar as condições que as variáveis devem atender : gi(x) ≤ 0 para i=1,...,m
• para serem válidas (viáveis) de serem escolhidas, através de inequações ou equações.para serem válidas (viáveis) de serem escolhidas, através de inequações ou equações.
• É importante ressaltar que se uma possível solução não atender a alguma

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