Terceiro quadrimestre de 2015

Horários:

• diurno 3^a (08:00-10:00) e 5^a (10:00-12:00)
• noturno 3^a (19:00-21:00) e 5^a (21:00-23:00)

Sala de aula:

• diurno S-301-1
• noturno S-302-1

Professor: Jerônimo C. Pellegrini

Sala do professor: S 805 (bloco B)

Email do professor: jeronimo.pellegrini ufabc edu br

SUB

A sub será no horário normal da aula (8:00, 19:00).

Observação dobre notas da T3

Na primeira questão, era essencial dizer quais variáveis eram positivas e quais ficavam negativas -- este é um dos motivos pelos quais muitos ficaram com 1.25 e não 2.5

Novidades

11/12 -- Conceitos finais disponíveis
02/12 -- Conceitos do T4 DIURNO disponíveis
02/12 -- Conceitos do T4 NOTURNO disponíveis
01/12 -- Nova versão das notas de aula disponível (v.85)
29/11 -- Lista 10 (teórica) disponível
29/11 -- Lista 9 (operacional) disponível
29/11 -- Notas do Teste 3, NOTURNO, disponíveis!
27/11 -- Notas do Teste 3, DIURNO, disponíveis!
24/11 -- Nova versão das notas de aula disponível (v.84)
         Correções em prog. inteira e transporte
         Outras melhorias menores
23/11 -- Nova versão das notas de aula disponível (v.83)
19/11 -- Divulgada matéria para T4
15/11 -- Nova versão das notas de aula disponível (v.82)
         (Pequenos erros corrigidos)
11/11 -- Conceitos atualizados após revisão de notas
10/11 -- Divulgada matéria para T3
10/11 -- Nova versão das notas de aula disponível (v.81)
         (Mudança estética)
10/11 -- Nova versão das notas de aula disponível (v.80)
08/11 -- Nova versão das notas de aula disponível (v.79)
         Algoritmo Húngaro explicado de forma inteligível
06/11 -- Nova versão das notas de aula disponível (v.78)
05/11 -- Nova versão das notas de aula disponível (v.77)
05/11 -- Listas 7 (principalmente operacional) e 8 (teórica) disponíveis
05/11 -- Listas 5 (principalmente operacional) e 6 (teórica) disponíveis
04/11 -- Implementação do affine scaling disponível na página das notas
         de aula
04/11 -- Nova versão das notas de aula disponível (v.76)
01/11 -- Nova versão das notas de aula disponível (v.75)
         (Seção sobre affine scaling melhorada)
30/10 -- Lista 4 disponível
29/10 -- Nova versão das notas de aula disponível (v.74)
         Capítulo sobre análise de sensibilidade está melhor
         (Ainda vai melhorar muito)
27/10 -- Conceitos do T2 (NOTURNO) disponíveis
27/10 -- Nova versão das notas de aula disponível (v.73)
         Algoritmo Dual-simplex *MUITO* mais claro, e com
         alguns exemplos. Mas ainda farei melhorias ao longo 
         da semana.
27/10 -- Prova T2 comentada (DIURNO) disponível
27/10 -- Conceitos do T2 (DIURNO) disponíveis
19/10 -- Nova versão das notas de aula disponível (v.72)
16/10 -- Nova versão das notas de aula disponível (v.71)
14/10 -- Nova versão das notas de aula disponível (v.70),
         com muito mais sobre a variável que sai da base
13/10 -- Nova versão das notas de aula disponível (v.69)
09/10 -- Conceitos do Teste 1 NOTURNO também disponíveis
09/10 -- Critério de avaliação modificado (8.75 = A)
09/10 -- Lista 3 disponível
09/10 -- Nova versão das notas de aula disponível (v.68)
08/10 -- Conceitos do Teste 1 DIURNO disponíveis.
07/10 -- Teste 1 comentado (as duas turmas)
03/10 -- Lista 2, somente para alunos com perfil teórico
30/09 -- Lista 1 agora com comentários
29/09 -- Nova versão das notas de aula disponível (v.67)
25/09 -- Nova versão das notas de aula disponível (v.66)
23/09 -- Lista 1 disponível
22/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 quatro pequenos testes T₁, T₂, T₃, T₄.

• Cada teste vale exatamente 0, 1.25 ou 2.5.

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, 5)→F
• n ∈ [5, 7)→C
• n ∈ [7, 8.75)→B
• n ∈ [8.75, 10]→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

• T₁ 06/10
• T₂ 20/10
• T₃ 17/11

• T₄ 01/12

• SUB: 08/12

• exame: 10/12

Quem ficar com F pode fazer o exame; a nota final será 0.6n + 0.4e, onde n é a nota dos testes e e é a nota do exame.

Exercícios

• Lista 1
• Lista 2
• Lista 3
• Lista 4
• Lista 5
• Lista 6
• Lista 7
• Lista 8
• Lista 9
• Lista 10

Resolução

• Teste 1 comentado ( diurno, noturno )
• Teste 2 comentado ( diurno )

Conceitos

Conceitos: diurno; noturno.

Programa

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

1. Programação Linear: modelagem e resolução Gráfica
2. Análise de Algoritmos (noções rudimentares)
3. Conjuntos convexos
4. O método simplex
5. Dualidade
6. Algoritmos primal-dual e dual-simplex
7. Análise de sensibilidade
8. Algoritmo do elipsóide
9. Algoritmo de pontos interiores
10. Aplicações
11. Programação Linear Inteira (noções rudimentares)
12. Programação Convexa (noções rudimentares)

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
• GNU Octave é um concorrente livre do Matlab. Aqui está a página do manual que trata de otimização

• O LibreOffice tem um solver semelhante ao do seu concorrente proprietário, Excel. Este blog post mostra como usá-lo.

• Simplexme, resolvedor online que mostra passos inermediários

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 )
• Stancu-Minasian, I. M., Fractional Programming: theory, methods and applications. Kluwer, 1997. (ISBN-13: 978-94-010-6504-7 )
• Bajalinov, Erik, Linear-Fractional Programming: theory, methods, applications and software. Springer, 2003. ( ISBN-13: 978-1-4613-4822-1 )
• 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"...

• 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.