====== Otimização combinatória (2011/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. Turma A: ANFV, [[http://www.ufrgs.br/ufrgs/localize/mapas/vale/pop_vale.asp?mapa=5|prédio 43412]]. Turma B: 106, prédio novo.\\ **Consultas:** Segunda, 15.30.\\ **Detalhes:** {{sy.pdf|Programa}}. ===== Resultados ===== * [[2011-2-FF|Frequência]] * [[2011-2-Notas|Notas]] * [[2011-2-Trabalhos|Trabalhos]] ===== Notícias ===== * Laboratório na segunda: **sala 101, prédio novo**. ===== Materiais ===== * Página da disciplina em [[2011-2|2011/2]], [[2011-1|2011/1]], [[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]]. * {{ca-notas-3777.pdf|Notas de aula}} (atualizado: 9/5/2011) ==== Aulas ==== ^ No.^ Data ^ Tópicos ^ Notas pág. ^ Exercícios ^ Soluções ^ Leitura ^ | || ** Programação linear ** ||||| | 1 | 08/08 | Exemplos e solução gráfica. | 9-11 | {{e01-11-2.pdf|E1}} | {{s01-11-2.pdf|S1}} | V1,MF1,2 | | 2 | 10/08 | Formulação, exemplos. | 11-13 | 5.1-5.13 | | V1,MF2 | | 3 | 15/08 | Laboratório de formulação (101). | | {{e02c.pdf|E2}} | {{s02c.pdf|S2}} | | | | 17/08 | //Sem aula// | | | | | | 4 | 22/08 | Forma matricial e normal. Introdução Simplex. | 13-20 | 5.14-5.17 | | | | 5 | 24/08 | Método simplex. Sistemas ilimitados. | 21-23,26 | | | V2.1,MF2,3 | | 6 | 29/08 | Método simplex. Pivot tool. Fase I. | 24-29 | | | V2.{2,3,4},MF3.{1,2,3} | | 7 | 31/08 | Soluções degeneradas. | 30-37 | 5.18 | | V3,MF3.6 | | 8 | 05/09 | Revisão e exercícios. | | 5.19,5.21,5.22, {{e03b.pdf|E3}} | {{s03b.pdf|S3}} | | | | 07/09 | [[wppt>Proclamação da indepedência]] | | | | | | 9 | 12/09 | ** Prova 1** | | {{p01k.pdf|P1}} | {{sp01k.pdf|SP1}} | | | 10 | 14/09 | Dualidade. | 39-45 | | | V5.{1,2,3,4,6},MF4 | | 11 | 19/09 | Folgas complementares, Método simplex dual | 46-50 | | | V6.{1,2,3},V7.1 | | 12 | 21/09 | Método Simplex dual. | 46-50 | | | V6.{1,2,3},V7.1 | | 13 | 26/09 | Análise de sensibilidade. | 56-63 | | | V6.{1,2,3},V7.1 | | || ** Programação inteira ** ||||| | 14 | 28/09 | Introdução e aplicações. | 77-95 | {{e05b1.pdf|E3}} | {{s05b1.pdf|S3}} | W1.{1-4},PS13.1 | | | 03/10 | //[[http://semac.inf.ufrgs.br | Semana acadêmica]]// | | | | | | | 05/10 | //[[http://semac.inf.ufrgs.br | Semana acadêmica]]// | | | | | | 15 | 10/10 | Laboratório de formulação (102). | | {{e06a1.pdf|E4}} | | | | | 12/10 | [[wppt>Nossa senhora aparecida]] | | | | | | 16 | 17/10 | Exemplos e formulações. | 97-102 | | | W1.{5-7},PS13.1 | | 17 | 19/10 | Revisão e exercícios. | | | | | | 18 | 24/10 | **Prova 2** | | {{p02h.pdf|P2}} | {{sp02h.pdf|SP2}} | | | 19 | 26/10 | Matrizes totalmente unimodulares. | 103-107 | | | W3.{1,2},K5.4,PS13.2 | | 20 | 31/10 | Problemas com solução simples. | 109-110 | | | W3.{3,4},PS13.2 | | | 02/11 | [[wppt>Finados]] | | | | | | 21 | 07/11 | Desigualdades válidas. | 111-115 | | | W8.{1-4} | | 22 | 09/11 | Algoritmos de planos de corte, Branch-and-bound | 115-122 | {{E10b.pdf|E5}} | {{s10b.pdf|S5}} | W7,W8.{5,6},PS14.1,G5.2.3 | | | 14/11 | **Dia do servidor público** | | | | | | 23 | 16/11 | Revisão e exercícios. | | | | | | 24 | 21/11 | **Prova 3** | | {{p03e.pdf|P3}} | {{sp03e.pdf|SP3}} | | | || ** Heurísticas e aproximação ** ||||| | 25 | 23/11 | Busca local, Simulated annealing. | 135-149 | | | | | 26 | 28/11 | GRASP, Busca Tabu, VNS. | 149-158 | | | | | 27 | 30/11 | Algoritmos genéticos, meméticos. | 159-168 | | | | | 28 | 05/11 | Algoritmos de aproximação. | | | | | | 29 | 12/12 | Apresentação de trabalhos. | | | | | | 30 | 14/12 | Apresentação de trabalhos. | | | | | | | 19/12 | Prova de recuperação. | | | | | | | | | | | | | | | 21/12 | Término oficial das aulas. | | | | | Livros: V=Vanderbei, MF=Maculan,Fampa, W=Wolsey, G=Goldbarg, K=Korte, PS=Papadimitriou/Steiglitz. ==== Material ==== * {{r.tex|Template em LaTeX}} para a lista de exercícios e {{r.pdf|uma versão compilada}}. ==== 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