ET610 - Programação Linear

Ementa: [pdf]

Comentários Históricos

George Dantzig is properly acclaimed as the "father of linear programming." Linear programming is a mathematical technique used to optimize a situation. It can be used to minimize traffic congestion or to maximize the scheduling of airline flights. He formulated its basic theoretical model and discovered its underlying computational algorithm, the "simplex method," in a pathbreaking memorandum published by the United States Air Force in early 1948. Linear Programming and Extensions provides an extraordinary account of the subsequent development of his subject, including research in mathematical theory, computation, economic analysis, and applications to industrial problems.

Dantzig first achieved success as a statistics graduate student at the University of California, Berkeley. One day he arrived for a class after it had begun, and assumed the two problems on the board were assigned for homework. When he handed in the solutions, he apologized to his professor, Jerzy Neyman, for their being late but explained that he had found the problems harder than usual. About six weeks later, Neyman excitedly told Dantzig, "I've just written an introduction to one of your papers. Read it so I can send it out right away for publication." Dantzig had no idea what he was talking about. He later learned that the "homework" problems had in fact been two famous unsolved problems in statistics.

Source: http://www.pupress.princeton.edu/titles/413.html

Assuntos Ministrados

Aula Assunto
1 - 7/11 Apresentação do Curso e Metodologia
2 - 10/11 Modelos de Programação Linear, Desenvolvimento de Modelos [P87, p.46-50], [S96,11-18], Exercícios [S96, p.18-21]
3 - 14/11 Problema da Dieta [P87, p.52-54], Solução Gráfica (Geométrica) [P87, p.56-58], [S96, p.23-31]
4 - 21/11 Transformação para a Forma Padrão [P87, p.66-70], Convexidade [P87, p.38-42], Teoremas Fundamentais de Programação Linear [P87, p.70-76]
5 - 24/11 Simplex: Método Algébrico [P87, p.77-82], [NA]
6 - 1/12 Simplex: Solução via Quadros (Tableaux) [P87, p.82-87], [NA]
7 - 5/12 Estudo de uma implementação em MATLAB para Simplex via Quadros [NA]
8 - 12/12 Simplex: Implementação Matricial [NA]
9 - 15/12 Exemplo Numérico do Simplex pelo Método Matricial [NA]
10 - 19/12 Estudo de uma implementação em MATLAB para Simplex (Matricial) [NA][P87]
11 - 22/12 Detalhes do Simplex: Degeneração, Ciclagem, Soluções Múltiplas, Teoremas Relacionados [NA]
12 - 16/1 Dualidade: Primal e Dual; Propriedades; Exercícios [P87, p.146-157]
13 - 19/1 Teorema da Dualidade Fraca, Teorema da Dualidade Forte [P87, p.157-159]
14 - 23/1 Revisão, Dúvidas, Discussão.
15 - 26/1 1o. Exercício Escolar
16 - 30/1 Apresentação do Código Simplex pelos Alunos; Testes; Debugging; Orientações.
17 - 2/2 Correção do 1o. EE, Revisão de Prova, Orientações.
18 - 6/2 Teorema da Folga Complementar, Parte I [P87, p.163-166]
19 - 9/2 Teorema da Folga Complementar, Parte II [P87, p.166-171]
20 - 13/2 Aplicação: Problema do Transporte [P87, p.107-127]
21 - 16/2 Exercícios
22 - 23/2 Pop quiz: Problema do Transporte
23 - 27/2 Método Dual-Simplex [P87, p.171-177]; Análise de Pós-optimização [P87, p.186-188]
24 - 2/3 Análise de Pós-optimização [P87, p.189-192]; Programação Paramétrica [P87, p.197-201]
25 - 6/3 Comentários sobre as listas de exercícios; Orientações.
26 - 9/3 Revisão, Dúvidas, Discussão.
27 - 13/3 2o. Exercício Escolar
28 - 16/3 Apresentação do Código (Dual) Simplex pelos Alunos; Testes; Debugging
29 - 20/3 2a. Chamada
30 - 23/3 Leitura
31 - 27/3 Exame Final

Datas Importantes*

1o. EE: 19/janeiro/2006
2o. EE: 9/março/2007
2a. Ch: 13/março/2007
Final: 16/março/2007

*Datas meramente estimadas, passíveis de alterações.

Referências