====== Otimização combinatória (2010/2) ======
//If one would take statistics about which mathematical problem is using up most of the computer time in the world, then ... the answer would probably be linear programming. (Laszlo Lovasz)//
:!: Bem-vindo à otimização combinatória.
===== Informações gerais =====
**Carga horária:** 60 h (em 30 aulas de 2h)\\
**Créditos:** 4\\
**Súmula:** Modelagem matemática, programação linear e não-linear. Programação inteira e solução via métodos exatos. Algoritmos de aproximação e heurísticas.\\
**Turma:** A.\\
**Horário/Sala:** Segunda/Quarta, 10.30-12.10, Sala 113, [[http://www.ufrgs.br/ufrgs/localize/mapas/vale/pop_vale.asp?mapa=5|prédio 43425]].\\
**Consultas:** Segunda, 15.30.\\
**Detalhes:** {{sy.pdf|Programa}}.
===== Resultados =====
* [[2010-2-FF|Freqüência]]
* [[2010-2-Notas|Notas]]
* [[2010-2-Trabalhos|Trabalhos]]
===== Notícias =====
* 4 de outubro: entrega lista 5.
* Segunda aula prática no Lab. 104.
===== Materiais =====
* Página da disciplina em [[2010-2|2010/2]], [[2010-1|2010/1]], [[2009-2|2009/2]], [[2009-1|2009/1]], [[2008-2|2008/2]], [[2008-1|2008/1]] e [[2007-2|2007/2]].
* {{notas-3474.pdf|Notas de aula}} (atualizado: 06/10/2010)
* Polítopo { x\in\R^3 | 0 < = x_i < =1, x_1+x_2 < = 1, x_1+x_3 < = 1, x_2+x_3 < = 1 }
{{:inf05010:cimtriangle.png?200}}
==== Aulas ====
^ No.^ Data ^ Tópicos ^ Notas pág. ^ Exercícios ^ Soluções ^ Leitura ^
| | | ** Programação linear ** |
| 1 | 09/08 | Exemplos e solução gráfica. | 9-11 | {{e01.pdf|E1}} | {{s01.pdf|S1}} | V1,MF1,2 |
| 2 | 11/08 | Formulação, exemplos. | 11-13 | {{e01a.pdf|E2}} | {{s01a.pdf|S2}} | V1,MF2 |
| 3 | 16/08 | Laboratório de formulação (102). | | {{e02b.pdf|E3}} | | |
| 4 | 18/08 | Forma matricial e normal. Introdução Simplex. | 13-20 | V2.{1,2,8,9,12} | | |
| 5 | 23/08 | Método simplex. Sistemas ilimitados. | 21-23,26 | | | V2.1,MF2,3 |
| 6 | 25/09 | Método simplex. Pivot tool. Fase I. | 24-29 | V2.{3-7,10,11} | | V2.{2,3,4},MF3.{1,2,3} |
| 7 | 30/09 | Soluções degeneradas. | 30-37 | {{e03c.pdf|E4}}, V3.{1-3,7} | {{s03c.pdf|S4}} | V3,MF3.6 |
| 8 | 01/09 | Revisão e exercícios. | | | | |
| | 06/09 | ** Sem aula ** | | | | |
| 9 | 08/09 | ** Prova 1** | | {{p01i.pdf|P1}} | {{sp01i.pdf|SP4}} | |
| 10 | 13/09 | Dualidade. | 39-45 | V5.1,V6.6 | | V5.{1,2,3,4,6},MF4 |
| 11 | 15/09 | Folgas complementares, Método simplex dual | 46-50 | V5.5 | | V6.{1,2,3},V7.1 |
| | 20/09 | [[wppt>Revolução Farroupilha]] | | | | |
| 12 | 22/09 | Análise de sensibilidade. | 56-63 | V6.{1,2},V7.{1,2,3} | | V6.{1,2,3},V7.1 |
| | | ** Programação inteira ** |
| 13 | 27/09 | Introdução e aplicações. | 77-95 | {{e05b.pdf|E5}} | {{s05a.pdf|S4}} | W1.{1-4},PS13.1 |
| 14 | 29/09 | Exemplos e formulações. | 97-102 | | | W1.{5-7},PS13.1 |
| 15 | 04/10 | Laboratório de formulação (102). | | {{e06b1.pdf|E6}} | | |
| 16 | 06/10 | Revisão e exercícios. | | | | |
| 17 | 11/10 | **Prova 2** | | {{p02f.pdf|P2}} | {{sp02f.pdf|SP2}} | |
| 18 | 13/10 | Matrizes totalmente unimodulares. | 103-107 | | | W3.{1,2},K5.4,PS13.2 |
| | 18/10 | //[[http://semac.inf.ufrgs.br | Semana acadêmica]]// | | | | |
| | 20/10 | //[[http://semac.inf.ufrgs.br | Semana acadêmica]]// | | | | |
| 19 | 25/10 | Problemas com solução simples. | 109-110 | | | W3.{3,4},PS13.2 |
| 20 | 27/10 | Desigualdades válidas. | 111-115 | | | W8.{1-4} |
| | 01/11 | Dia do servidor público | | | | |
| 21 | 03/11 | Algoritmos de planos de corte. | 115-119 | | | W8.{5,6},PS14.1 |
| 22 | 08/11 | Branch-and-bound. | 119-122 | {{e10a.pdf|E7}} | {{s10a.pdf|S7}} | W7,G5.2.3 |
| 23 | 10/11 | Revisão e exercícios. | | {{p03a.pdf|E8}} | {{sp03a.pdf|S8}} | |
| | 15/11 | [[wppt>Proclamação da república]] | | | | |
| 24 | 17/11 | **Prova 3** | | {{p03c.pdf|P3}} | {{sp03c.pdf|SP3}} | |
| | | ** Heurísticas e aproximação ** |
| 25 | 22/11 | Busca local, Simulated annealing. | 135-149 | | | |
| 26 | 24/11 | GRASP, Busca Tabu, VNS. | 149-158 | | | |
| 27 | 29/11 | Algoritmos genéticos, meméticos. | 159-168 | | | |
| 28 | 01/12 | Algoritmos de aproximação. | | | | |
| 29 | 06/12 | Apresentação de trabalhos. | | | | |
| 30 | 08/12 | Apresentação de trabalhos. | | | | |
| | 15/12 | Prova de recuperação. | | {{prf.pdf|PR}} | {{sprf.pdf|SPR}} | |
| | | | | | | |
| | 23/12 | Término oficial das aulas. | | | | |
Livros: V=Vanderbei, MF=Maculan,Fampa, W=Wolsey, G=Goldbarg, K=Korte, PS=Papadimitriou/Steiglitz.
==== Ferramentas ====
* [[http://www.maths.ed.ac.uk/LP-Explorer|LP explorer]]
* [[http://campuscgi.princeton.edu/~rvdb/JAVA/pivot/simple.html|Vanderbei's simple pivot tool]]
* [[http://www.gnu.org/software/glpk|GNU Linear programming kit]]
==== Bibliografia ====
- Nelson Maculan and Marcia
H. Costa Fampa.
Otimização linear.
Editora UnB, 2006.
INF 65.012.122 M175o.
- Marco Cesar Goldbarg.
Otimização
combinatória e programação linear : modelos e algoritmos.
Campus, 2005.
INF 65.012.122 G618o2.
- David G. Luenberger.
Linear and nonlinear programming.
Springer, 2nd edition, 2003.
- Bernhard H. Korte and Jens Vygen.
Combinatorial
optimization theory and algorithms.
Springer, 4th edition, 2008.
INF 65.012.122 K85c.
- Mokhtar S. Bazaraa, John J.
Jarvis, and Hanif D. Sherali.
Linear programming and network flows.
Wiley, 3rd edition, 2004.
ENG 519.852 B362l.
- Laurence A. Wolsey and
George L. Nemhauser.
Integer and Combinatorial Optimization.
Wiley, 1999.
- Dimitri P. Bertsekas.
Nonlinear
programming.
Athena, 2nd edition, 1999.
INF 65.012.122 B551n.
- Laurence A. Wolsey.
Integer Programming.
Wiley, 1998.
- Christos H.
Papadimitriou and Kenneth Steiglitz.
Combinatorial optimization: Algorithms and complexity.
Prentice-Hall, dover edition, 1982.
- G. Ausiello, P. Crescenzi,
G. Gambosi, V. Kann, A. Marchetti-Spaccamela, and M. Protasi.
Complexity and
approximation – Combinatorial Optimization Problems and their
Approximability Properties.
Springer-Verlag, 1999.
INF 510.5 C737.
- Robert J. Vanderbei.
Linear programming:
Foundations and Extensions.
Kluwer, 2nd edition, 2001.
- Juraj Hromkovic.
Algorithmics for hard problems.
Springer, 2001.
INF 65.012.122 H873a.
