Programação Matemática

Segundo quadrimestre de 2012
Horário: 2^a (08:00-10:00) e 4^a (10:00-12:00)
Sala de aula:   S502
Professor: Jerônimo C. Pellegrini
Sala do professor: S 805 (bloco B)
Email do professor: jeronimo.pellegrini ufabc edu br

Vista de prova

A vista de prova é amanhã (19/12) das 14:00 às 17:00.

Novidades:

18/12 -- Conceitos após P2 disponíveis
12/12 -- P2 hipotética disponível
04/12 -- Versão 23 das notas de aula disponível
29/11 -- Versão 22 das notas de aula disponível
27/11 -- Amanhã, 28/11, não haverá aula
22/11 -- Lista 3
22/11 -- Versão 21 das notas de aula disponível
20/11 -- Versão 20 das notas de aula disponível
14/11 -- Versão 19 das notas de aula disponível
12/11 -- Versão 18 das notas de aula disponível
12/11 -- Versão 17 das notas de aula disponível
11/11 -- Versão 16 das notas de aula disponível
05/11 -- Conceitos após P1 disponíveis
04/11 -- P1 resolvida com comentários no site
01/11 -- Versão 15 das notas de aula disponível
01/11 -- Versão 14 das notas de aula disponível
31/10 -- Versão 13 das notas de aula disponível
23/10 -- P1 hipotética disponível
23/10 -- Versão 12 do Guia de estudos disponível
23/10 -- Versão 11 do Guia de estudos disponível
22/10 -- Versão 10 do Guia de estudos disponível
21/10 -- Versão 9 do Guia de estudos disponível
17/10 -- Versão 8 do Guia de estudos disponível
16/10 -- Versão 7 do Guia de estudos disponível
15/10 -- Lista 2
15/10 -- Versão 6 do Guia de estudos disponível
15/10 -- Versão 5 do Guia de estudos disponível
14/10 -- Versão 4 do Guia de estudos disponível
14/10 -- Versão 3 do Guia de estudos disponível
13/10 -- Versão 2 do Guia de estudos disponível
10/10 -- Guia de estudos disponível (versão 1)
06/10 -- Exemplos de uso do método Simplex no GLPK e no Maxima
03/10 -- Datas definidas para as provas
28/09 -- Lista 1
28/09 -- Nova indicação de livro: Luenberger
17/09 -- Reinício do curso
------------------------
28/05 -- Início do curso

Ementa

Introdução: Revisões de álgebra linear e conjuntos convexos. Programação linear: Modelagem; Resolução Gráfica; Teoremas Básicos; O método simplex; Simplex revisado; Dualidade; Algoritmos primal-dual e dual-simplex; Análise de sensibilidade.

Requisitos

Álgebra Linear, Geometria Analítica. (GA já é recomendação para AL, mas não custa relembrar)

Avaliação

O conceito final da disciplina poderá ser:

• F - Reprovado. O aluno deve cursar novamente a disciplina.
• C - Desempenho mínimo satisfatório, demonstrando capacidade de uso adequado dos conceitos da disciplina, habilidade para enfrentar problemas relativamente simples e prosseguir em estudos avançados.
• B - Bom desempenho, demonstrando boa capacidade de uso dos conceitos da disciplina.
• A - Desempenho excepcional, demonstrando excelente compreensão da disciplina e do uso da matéria.

A avaliação ser composta de duas provas, P₁ e P₂.

A avaliação final de cada aluno não será o resultado de alguma "conta" feita a partir dos valores das avaliações. O resultado de cada avaliação reflete o desempenho do aluno em todo o curso até aquele instante, e não é apenas uma "nota isolada". Isso significa que cada avaliação leva em conta também o resultado das avaliações anteriores. De maneira simples, cada avaliação mostra qual seria o conceito final do aluno se o curso terminasse naquele instante.

Não há "prova substitutiva", porque tal conceito não faz sentido no sistema de avaliação descrito acima.

Exercícios

• LISTA 1: Luenberger, Cap. 2. (veja a referência na bibliografia)
• LISTA 2
• LISTA 3

Exemplos de prova: P₁ hipotética, P₂ hipotética.

P₁ comentada: aqui

Conceitos

RA	  após P1 após P2
-------------------------
11095709        B       A
16001012        F       B
11052510        F       (F)
11133308        B       B
11030006        F       F
11010409        F       (F)
11097108        B       C
11108609        F       C

Programa aproximado

Este programa está sujeito a mudanças simples. Grandes mudanças não devem acontecer.

Programação Linear: modelagem e resolução Gráfica
Programação Linear Inteira (noções rudimentares)
Análise de Algoritmos (noções rudimentares)
Conjuntos convexos
O método simplex
Dualidade
Algoritmos primal-dual e dual-simplex
Análise de sensibilidade
Algoritmo do elipsóide
Algoritmo de pontos interiores
Aplicações
Programação convexa (noções rudimentares)

Datas das avaliações:

• P₁: 29/10
• P₂: 17/12

Software

Há uma enorme quantidade de programas que resolvem programação linear. Alguns exemplos:

• Maxima é um concorrente livre do Mathematica. O prof. Daniel Miranda e eu fizemos um tutorial muito básico do Maxima; veja também parte do manual que mostra como usar o simplex
• GLPK (GNU Linear Programming Kit) -- veja um tutorial de Rodrigo Ceron, da IBM.
  • No Linux, instale o pacote "glpk".
  • Há um pacote para Windows
• Scilab -- o Scilab resolve programação linear usando o algoritmo de Karmarkar (veja a documentação)
• lp_solve
  • No Linux, instale o pacote "lp-solve"
  • Há versão Windows no Sourceforge
• Octave é um concorrente livre do Matlab. Aqui está a página do manual que trata de otimização
• Mathematica, Maple, Matlab, etc

Exemplos:

• Exemplo de programa linear para ser usado com GLPK (use "glpsol --lp exemplo.lp")
• Exemplo usando Maxima
• Exemplo usando lp_solve

Bibliografia

Notas de aula

Os livros disponíveis na bilioteca tem sua identificação entre colchetes -- por exemplo, [ 519 / PAPAco ]. Os que não existem na biblioteca tem o ISBN entre parênteses: ( ISBN-13: 978-8131203767 ).

Principal

• Matousek, Jiri; Gärtner, Bernd. Understanding and Using Linear Programming. Springer, 2007. Mantém o foco somente em programação linear, mas dentro do que faz é extremamente didático. (ISBN-13: 978-3-540-30697-9 )
• Sinha, S. M. Mathematical Programming: Theory and Methods Elsevier, 2006. ( ISBN-13: 978-8131203767 ). Não tem na biblioteca, mas é muito bom. Inclui uma breve revisão de Álgebra Linear.
• Luenberger, David G.; Ye, Yinyu. Linear and Nonlinear Programming Springer. Springer, 2008. (ISBN-13: 978-0-387-74502-2 ). Disponível pela Springer, dentro da UFABC.
• Minhas notas de aula de Criptografia: o apêndice sobre Análise de Algoritmos será usado somente para a aula sobre Análise de Algoritmos
• Dasgupta, S.; Papadimitriou, C.; Vazirani, U. Algoritmos McGraw-Hill, 2009 [518.1 / DASa], também em Inglês [518.1 / DASa] -- há um capítulo muito resumido sobre programação linear; mas o livro pode ser útil para entender complexidade de algoritmos.

Secundária

• Glenn Hurlbert. Linear Optimization: The Simplex Workbook Springer, 2009 ( ISBN-13: 978-0387791470 ) Muito bom livro! O texto é intercalado com muitos exercícios.
• Papadimitriou, Christos H.; Steiglitz, Kenneth. Combinatorial Optimization: algorithms and complexity. Dover, 1988. [519 / PAPAco] A errata está na página de Ken Steiglitz
• Griva, I, Nash, S. G., Sofer, A. Linear and Nonlinear Optimization Society for Industrial Mathematics, 2008. ( ISBN-13: 978-0898716610) Muito bom livro, extenso.
• Sierksma, G. Linear & Integer Programming: Theory and Practice CRC Press, 2001. ( ISBN-13: 978-0824706739 )
• Strayer, J. K. Linear Programming and Its Applications Springer, 1989. ( ISBN-13: 978-0387969305 )
• Vanderbei, Robert J. Linear Programming: foundations and extensions Kluwer Academic Publishers, 2007. Há uma errata aqui
• Goldbarg M.C., Luna H.P.L., "Otimização combinatória e programação linear- modelos e algoritmos". Campus, RJ, 2000 [511.8 / GOLo2 / 2ed] Não usarei, mas pode ajudar.
• Bazaraa, M. S., Jarvis, J. J. e Sherali, H. D. Linear Programming and Network Flows. New York: John Wiley & Sons, 1990. [519.72 / BAZl4 / 4ª. ed] Muito bom.
• Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C., Algoritmos - Teoria e Prática. Campus, 2002. [005.1 / CORi2]  [005.1 / CORa] Aborda o assunto somente tangencialmente.
• Bertimas, Dimitris; Tsitsiklis, John N.. Introduction to linear Optimization. Nashua: Athena Scientific, 1997. [519.7 / BERi] Bom livro!
• Brickman, Louis Mathematical Introduction to Linear Programming and Game Theory Springer, 1989. ( ISBN-13: 978-0387969312 )
• Thie, P. R.; Keough, G. E. An Introduction to Linear Programming and Game Theory. Wiley, 2008. ( ISBN-13: 978-0470232866 ) Um bom livro.
• Schrijver, A. Theory of Linear and Integer Programming Wiley, 1999. ( ISBN-13: 978-0471982326 ) Ótimo livro, para quem quiser mergulhar na teoria de otimização linear.

"Terciária", se é que faz sentido

• R. K. Sundaram. A First Course in Optimization Theory Cambridge, 1996. ( ISBN-13: 978-0521497701 ) Sobre otimização em geral, e sua relação com Análise e Topologia
• S Boyd, L Vandenberghe. Convex optimization Cambridge, 2004. [519.6 / BOYc] Sobre otimização convexa. Há uma cópia livre do livro.