====== Otimização combinatória (2010/1) ====== //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, 8.30-10.10, Sala 113, [[http://www.inf.ufrgs.br/cei/nscad/images/stories/mapa_2006.jpg|prédio 43425]].\\ **Consultas:** Segunda, 10.30.\\ **Detalhes:** {{sy.pdf|Programa}}. ===== Resultados ===== * [[2010-1-FF|Freqüência]] * [[2010-1-Notas|Notas]] * [[2010-1-Trabalhos|Trabalhos]] ===== Notícias ===== * 8/3/2010: Primeiro dia de aula. * 2/5/2010: [[Dicas exercícios 4]]. ===== Materiais ===== * Página da disciplina em [[2009-2|2009/2]], [[2009-1|2009/1]], [[2008-2|2008/2]], [[2008-1|2008/1]] e [[2007-2|2007/2]]. * {{notas-3302.pdf|Notas de aula}} (atualizado: 03/06/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 | 08/03 | Administrativa, Introdução: Exemplos e solução gráfica. | 7-10 | {{e01.pdf|E1}}, 4.1 | {{s01.pdf|S1}} | V1,MF1,2 | | 2 | 10/03 | Programação linear: Formulação e exemplos. | 11-14 | {{e01a.pdf|E2}}, 4.{2-6} | {{s01a.pdf|S2}} | V1,MF2 | | 4 | 15/03 | Programação linear: Laboratório (103). | | {{e02.pdf|E3}} | {{s02.pdf|S3}} | | | 3 | 17/03 | Programação linear: Forma normal, método simplex, pivô tool. | 15-19 | 4.7 | | V2.1,MF2,3 | | 5 | 22/03 | Programação linear: Método simplex. Sistemas ilimitados. | 19-22 | | | V2.2,2.3,MF3.{1,2} | | 6 | 24/03 | Programação linear: Solução inicial. Soluções degeneradas. | 22-26 | 4.{8-12} | | V2.4,MF3.3 | | 7 | 29/03 | Programação linear: Soluções degeneradas, revisão e exercícios. | 26-34 | | | V3,MF3.6 | | 8 | 31/04 | **Prova 1** (conteúdo 1-7) | | {{p01g.pdf|P1}} | {{sp01g.pdf|SP1}} | | | | | | | {{p01h.pdf|P1}} | {{sp01h.pdf|SP1}} | | | 9 | 05/04 | Programação linear: Dualidade. | 35-42 | | | V5.{1,2,3,4,6},MF4 | | 10 | 07/04 | Programação linear: Método simplex dual. | 43-47 | 4.{16,17} | | V6.{1,2,3},V7.1 | | 11 | 12/04 | Programação linear: Forma matricial e sensitividade. | 47-59 | 4.13 | | V6.{1,2,3},V7.1 | | | | ** Programação inteira ** | | 12 | 14/04 | Programação inteira:Introdução e aplicações. | 69-87 | {{:inf05010:e11.pdf|E4}} | {{:inf05010:s11a.pdf|S4}} | W1.{1-4},PS13.1 | | 13 | 19/04 | Programação inteira:Formulação e exemplos. | 89-94 | 9.{1,3,4-6,8-11,13,15} | | W1.{5-7},PS13.1 | | | 21/04 | //Feriado//: [[wppt>Tiradentes]] | | | | | | 14 | 26/04 | Programação inteira:Laboratório (103). | | | | | | 15 | 28/04 | Programação inteira:Matrizes totalmente unimodulares. | 95-102 | | | W3.{1,2},K5.4,PS13.2 | | 16 | 03/05 | Programação inteira:Problemas com solução simples. | | | | W3.{3,4},PS13.2 | | 17 | 05/05 | Programação inteira:Formulação, revisão e exercícios. | | | | | | 18 | 10/05 | **Prova 2** (conteúdo 9-14+17) | | {{:inf05010:p02e.pdf|P2}} | {{:inf05010:sp02e.pdf|SP2}} | | | 19 | 12/05 | Programação inteira:Desigualdades válidas. | 102-107 | | | W8.{1-4} | | 20 | 17/05 | Programação inteira:Algoritmos de planos de corte. | 107-110 | | | W8.{5,6},PS14.1 | | 21 | 19/05 | Programação inteira:Algoritmos de planos de corte. | 107-110 | | | W8.{5,6},PS14.1 | | | 24/05 | //[[http://semac.inf.ufrgs.br| Semana acadêmica]]// | | {{:inf05010:e13.pdf|E5}} | {{:inf05010:s13.pdf|S5}} | | | | 26/05 | //[[http://semac.inf.ufrgs.br| Semana acadêmica]]// | | | | | | 22 | 31/05 | Programação inteira:Branch-and-bound. | 111-115 | | | W7,G5.2.3 | | 23 | 02/06 | Programação inteira:Revisão e exercícios. | | | | | | | 03/06 | //Feriado//: [[wppt>Corpus Cristi]] | | | | | | 24 | 07/06 | **Prova 3** (conteúdo 15,16,19-23) | | {{:inf05010:p03b.pdf|P3}} | {{:inf05010:sp03b.pdf|SP3}} | | | | | ** Heurísticas e aproximação ** | | 25 | 09/06 | Heurísticas: Busca local, Simulated annealing. | 127-141 | | | | | 26 | 14/06 | Heurísticas: GRASP, Busca Tabu, VNS. | 142-150 | | | | | 27 | 16/06 | Heurísticas: Algoritmos genéticos,meméticos. | 151-160 | | | | | 28 | 21/06 | Algoritmos de aproximação. | | | | | | 29 | 23/06 | Apresentação de trabalhos. | | | | | | 30 | 28/06 | Apresentação de trabalhos. | | | | | | | 07/07 | Prova de recuperação. | | {{:inf05010:pre.pdf|PR}} | {{:inf05010:spre.pdf|SPR}} | | | | | | | | | | | | 17/07 | 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 ==== Locations of visitors to this page