Terceiro quadrimestre de 2014
Horário: 2a (21:00-23:00) e 4a (19:00-21:00)
Sala de aula: S 502
Professor: Jerônimo C. Pellegrini
Sala do professor: S 805 (bloco B)
Email do professor: jeronimo.pellegrini ufabc edu br
VISTA/REVISÃO
Na quarta, 17/12, teremos vista e revisão das provas das 19:00 20:00!
NA SALA 805 DO BLOCO B!
Novidades
16/12 -- notas finais disponíveis
16/12 -- notas do T5 disponíveis
02/12 -- notas do T4 disponíveis
01/12 -- nova versão das notas de aula (v.63) disponível
29/11 -- nova versão das notas de aula (v.62) disponível
26/11 -- vista/revisão dos testes 1-3 HOJE na aula
(faremos novamente vista/revisão de todos os
testes ao final do curso -- esta é para servir
de feedback antes do T4)
26/11 -- notas do T3 disponíveis
25/11 -- nova versão das notas de aula (v.61) disponível
(corrige alguns erros)
25/11 -- nova versão das notas de aula (v.60) disponível
(inclui um rascunho sobre programação quadrática)
13/11 -- nova versão das notas de aula (v.59) disponível
12/11 -- Lista 4 disponível
12/11 -- Lista 3 disponível
11/11 -- nova versão das notas de aula (v.58) disponível
07/11 -- notas do T2 disponíveis
21/10 -- notas do T1 disponíveis
20/10 -- Lista 2 disponível
20/10 -- nova versão das notas de aula (v.57) disponível
16/10 -- nova versão das notas de aula (v.56) disponível
15/10 -- nova versão das notas de aula (v.55) disponível
08/10 -- Lista 1 disponível
03/10 -- nova versão das notas de aula (v.54) disponível
30/09 -- datas das avaliações disponíveis
29/09 -- 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 cinco pequenos testes T1, T2, T3, T4, T5 e listas de exercícios a serem entregues. O aluno deverá fazer quatro dos testes. Se fizer mais, usaremos as quatro melhores notas.
- Cada teste vale exatamente 0, 1 ou 2.
- A entrega das listas vale 1.
As notas serão convertidas em conceito de acordo com a seguinte regra: seja n a soma das notas nos quatro testes e lista. Então o conceito final será:
- n ∈ [0, 4) → F
- n ∈ [4, 6) → C
- n ∈ [6, 8) → B
- n ∈ [8, 9] → A
Prova substitutiva
Somente para os casos previstos em lei!
Caso o aluno perca uma das provas e apresente justificativa, poderá fazer uma substitutiva no final do quadrimestre.
Datas das avaliações
13/1003/1117/1101/1215/12
Exercícios
- Lista 1 (para 20/10): das notas de aula, exercícios 1, 2, 4, 5, 8, 13, 26, e um dos itens do exercício 3.
- Lista 2 (para 03/11): das notas de aula, exercícios 26, 27, 29 e depois UMA das opções a seguir:
- Lista 3 (para 26/11): das notas de aula, exercícios 32, 37 e UMA das opções a seguir:
- Implemente um algoritmo que transforme primal e dual, dada adescrição genérica de um programa linear (com restrições ≥ , ≤ , = , e variáveis dos dois tipos (positivas e reais).
- Faça o exercício 34
- Lista 4 (para 03/12): das notas de aula, faça o exercício 52, e UMA das opções a seguir:
Conceitos
Resultado dos testes
Programa
Este programa está sujeito a mudanças simples. Grandes mudanças não devem acontecer.
- Programação Linear: modelagem e resolução Gráfica
- 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 Linear Inteira (noções rudimentares)
- Programação convexa (noções rudimentares)
Software
Há uma enorme quantidade de programas que resolvem programação linear. Alguns exemplos:
Exemplos:
- Exemplo de programa linear para ser usado com GLPK (use
glpsol --lp exemplo.lp)
- Exemplo usando Maxima
- Exemplo usando lp_solve
Bibliografia
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
- Notas de aula
- 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.
- Notas de aula de Criptografia: o apêndice sobre Análise de Algoritmos será usado somente para a aula sobre Análise de Algoritmos
- Notas de aula de Álgebra Linear: o Capítulo sobre formas quadráticas aborda o tópico de convexidade de funções. Além disso, pode ser útil para revisar ou relembrar conceitos de Álgebra Linear usados neste curso.
- 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.