Departamento de Engenharia de Computação e Automação Industrial - DCA
Faculdade de Engenharia Elétrica e de Computação - FEEC
Universidade Estadual de Campinas - UNICAMP

 

IA881      Otimização Linear

 

Professor

Fernando Gomide

Tutor

 

Conteúdo

Ementa

Ementa resumida

1- Introdução

2- Geometria da programação linear

3- Método simplex

4- Teoria de dualidade e análise de sensibilidade

5- Otimização de sistemas de grande porte

6- Problemas de fluxo em redes

7- Método dos pontos interiores

8- Formulações de programação inteira

9- Métodos de programação inteira

     10- Arte da otimização linear

     11-Aplicações

 

Ementa detalhada

1-Introdução

     1.1-Conceituação da área

      1.2-Exemplos de problemas de programação linear

      1.3-Revisão de álgebra linear e complexidade de algoritmos

2-Geometria da programação linear

2.1-Poliedros e conjuntos convexos

2.2-Pontos extremos, vértices, soluções básicas factíveis

2.3-Degeneração

2.4-Existência e otimalidade de pontos extremos

2.5-Representação e projeção de poliedros

3-Método Simplex

3.1-Condições de otimalidade

3.2-Desenvolvimento do método simplex

3.3-Implementação do método simplex

3.4-Ciclagem, solução básica factível inicial

3.5-Eficiência computacional do método simplex

4-Teoria de dualidade

4.1-Problema dual e teorema de dualidade

4.2-Formas padrão e o método dual simplex

4.3-Lema de Farkas e desigualdades lineares

4.4-Dualidade geral em programação linear

5-Análise de sensibilidade

5.1-Análise local de sensibilidade

5.2-Dependência global do vetor do lado direito

5.3- Dependência global do vetor da função objetivo

5.4-Programação paramétrica

6-Otimização de sistemas de grande porte

     6.1-Geração de colunas

     6.2-Planos de corte

     5.3-Decomposição de Dantzig-Wolfe

     5.4-Programação estocástica e decomposição de Benders

7-Problemas de fluxo em redes

7.1-Grafos, formulação do problema de fluxo em redes

7.2-Algoritmo simplex para redes e algoritmo do ciclo negativo

7.3-Fluxo máximo, métodos duais, caminho mínimo

7.4-Problema da árvore geradora mínima

8-Método dos pontos interiores

            8.1-Algoritmo de escalamento afim e sua convergência

            8.2-Algoritmo de redução

            8.3-Algoritmo path following primal

            8.4-Algoritmo path following dual

9-Formulações de programação inteira

            9.1-Técnicas de modelagem

            9.2-Sugestões para obter formulações fortes

            9.3-Modelagem restrições

10-Métodos de programação inteira

            10.1-Planos de corte

            10.2-Branch and bound

            10.3-Programação dinâmica

            10.4-Algoritmos aproximados, algoritmos evolucionários

            10.5-Busca local, simulated annealing

            10.6-Complexidade

11-Arte da otimização linear

            11.1-Linguagens de modelagem em otimização linear

            11.2-Bibliotecas de otimização linear

            11.3-Aplicações

12-Aplicações

 

Critério de avaliação

          M = (P1 + P2)/2,   E = nota exame

          Se M < 5  então Exame

         Se M  > 5 aprovado

         Se (M+E)/2 < 5  reprovado

         Se (M+E)/2 > 5  aprovado

      Se necessário: exame oral.

Provas

Prova
Data

P1

25/04/2007

P2

13/06/2007

Exame

11/06/2007

 

 

Referências Bibliográficas

Teoria

 

Livro texto:

 

 Introduction to Linear Optimization, D. Bertsimas and J. Tsitsiklis

Atena Scientific, 1997

Outros:

 

Linear Programming and Network Flows. M. Bazaraa, J. Jarvis, H. Sherali,

Wiley Intescience, 2005

 

Linear Programming Foundations and Extensions, R. Vanderbei,

Springer International, 2001

 

 

Periódicos

 

 

 

Críticas, dúvidas e sugestões: