:!: Página descontinuada, provavelmente o material não é mais acessível.

====== Otimização combinatória (2007/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:** U.\\
**Horário/Sala:** Segunda/Quarta, 10.30-12.10, Sala 107, [[http://www.inf.ufrgs.br/cei/nscad/images/stories/mapa_2006.jpg|prédio 43425]].\\
**Consultas:** Terça, 15-17.\\
**Detalhes:** Vê o {{sy.pdf|programa}}.




===== Notícias =====
  * Primeira aula no dia 06/08/2007.

===== Resultados =====
  * [[2007-2-FF|Freqûencia]]
  * [[2007-2-Notas|Notas]]
  * [[2007-2-Trabalhos|Trabalhos]]






===== Materiais =====

  * {{OC-Notas-2468.pdf|Notas de aula}} (atualizado: 12/11/2007)





==== Aulas ====

^ No.  ^ Data   ^ Tópicos                                              ^ Notas pág. ^  Exercícios  ^  Soluções 	 ^ Leitura ^
|   1  | 06/08 | Administrativa, Introdução: Exemplos e solução gráfica.  |7-10       |3.1	    |    |V1,MF1,2	|
|   2  | 08/08 | Programação linear: Formalização, exemplos, Formas normais.  |11-14  |3.2,3.4    |    |V1,MF2	|
|   3  | 13/08 | Programação linear: Introdução ao método simplex.     |15-19         |3.5,3.6	    |    |V2.1,MF2,3	|
|   4  | 15/08 | Programação linear: Método simplex. Pivot tool.       |19-21         |3.2	    |    |V2.2,2.3,MF3.{1,2} |
|   5  | 20/08 | Programação linear: Sistemas ilimitados. Solução inicial.  |21-24    |V2.1-2.10    |    |V2.4,MF3.3    |
|   6  | 22/08 | Programação linear: Soluções degeneradas.	       |25-30         |		    |    |V3,MF3.6	|
|      | 27/08 | Sem aula          				       |	      |{{e03.pdf|E1}} |{{s03.pdf|S1}} | |
|      | 29/08 | Sem aula          				       |	      |		    |    |		|
|   7  | 03/09 | Programação linear: Laboratório (101).		       |	      |{{e02.pdf|E2}} |{{s02.pdf|S2}} | |
|   8  | 05/09 | Programação linear: Dualidade.			       |33-42	      |		    |    |V5.{1,2,3,4,6},MF4 |
|   9  | 10/09 | Programação linear: Forma matricial e sensitividade.  |42-51         |		    |    |V6.{1,2,3},V7.1|
|  10  | 12/09 | Programação linear: Revisão e exercícios.	       |	      |{{e04.pdf|E3}} |{{s04.pdf|S3}} |	|
|  11  | 17/09 | Programação inteira:Introdução e aplicações.	       |59-81	      |		    |    |W1.{1-4},PS13.1|
|  12  | 19/09 | Programação inteira:Exemplos e formulações.	       |81-84	      |		    |    |W1.{5-7},PS13.1|
|  13  | 24/09 | **Prova 1**					       |	      |{{p01.pdf|P1}}{{p01a.pdf|P1*}} |{{sp01.pdf|SP1}}{{sp01a.pdf|SP1*}}  |  |
|  14  | 26/09 | Programação inteira:Matrizes totalmente unimodulares. |85-91	      |		    |    |W3.{1,2},K5.4,PS13.2	|
|  15  | 01/10 | Programação inteira:Problemas com solução simples.    |	      |{{e05.pdf|E4}} |{{s05.pdf|S4}} |W3.{3,4},PS13.2 |
|  16  | 03/10 | Programação inteira:Problemas com solução simples.    |	      |		    |    |W3.{3,4},PS13.2|
|  17  | 08/10 | Programação inteira:Laboratório (101).		       |	      |{{e06.pdf|E5}} |{{s06.pdf|S5}} |	|
|  18  | 10/10 | Programação inteira:Desigualdades válidas.	       |92-95 	      |		    |    |W8.{1-4}	|
|  19  | 15/10 | Programação inteira:Algoritmos de planos de corte.    |95-100	      |		    |    |W8.{5,6},PS14.1|
|  20  | 17/10 | Programação inteira:Branch-and-bound.		       |100-102	      |{{e07.pdf|E6}} |{{s07.pdf|S6}} |W7,G5.2.3 |
|      | 22/10 | //Semana academica//			               |	      |	            |    |		|
|      | 24/10 | //Semana academica//			               |	      |	            |    |		|
|  21  | 29/10 | Programação inteira: Revisão e exercícios.            |	      |{{E08.pdf|E7}} |{{S08.pdf|S7}} |	|
|  22  | 31/10 | **Prova 2**				               |              |{{p02.pdf|P2}} |{{sp02.pdf|SP2}}    |		|
|  23  | 05/11 | Heurísticas: Busca local, Simulated annealing.        |107-123	      |	            |    |		|
|  24  | 07/11 | Heurísticas: GRASP, Busca Tabu, VNS	               |124-131	      |	            |    |		|
|  25  | 12/11 | Heurísticas: Algoritmos genéticos,meméticos           |133-142	      |	            |    |		|
|  26  | 14/11 | Aproximação				               |	      |	            |    |		|
|  27  | 19/11 | Aproximação				               |	      |	            |    |		|
|  28  | 26/11 | Apresentação de trabalhos.		               |	      |	            |    |	        |
|  29  | 28/11 | Apresentação de trabalhos.                            |	      |	            |    |	        |
|  30  | 03/12 | Apresentação de trabalhos.                            |	      |	            |    |	        |
|      | 05/12 | Aula de revisão.                                      |	      |	            |    |	        |
|      | 10/12 | Prova de recuperação.			               |	      |{{pra.pdf|PR}}|{{spra.pdf|SPR}}    | |
| | | | | | | |
|      | 14/12 | Término oficial das aulas.  |    |    |    |    |

Livros: V=Vanderbei, MF=Maculan,Fampa, W=Wolsey, G=Goldbarg, K=Korte, PS=Papadimitriou/Steiglitz.

==== Bibliografia ====
<html>
<!-- BEGIN BIBLIOGRAPHY livros -->
<!--
    DO NOT MODIFY THIS BIBLIOGRAPHY BY HAND!  IT IS MAINTAINED AUTOMATICALLY!
    YOUR CHANGES WILL BE LOST THE NEXT TIME IT IS UPDATED!
-->
<!-- Generated by: /home/ritt/arch/share/bin/bib2xhtml -s unsortlist livros.bib livros.html -->
<ul class="bib2xhtml">

<!-- Authors: Nelson Maculan and Marcia H Costa Fampa -->
<li><a name="Maculan.Fampa/2006">Nelson</a> Maculan and Marcia
  H.&nbsp;Costa Fampa.
<cite>Otimização linear</cite>.
Editora UnB, 2006.
(livro texto) INF 65.012.122 M175o.</li>

<!-- Authors: Marco Cesar Goldbarg -->
<li><a name="Goldbarg/2005">Marco</a>&nbsp;Cesar Goldbarg.
<a href="http://www.dimap.ufrn.br/~gold/livrootimiza.htm"><cite>Otimização
  combinatória e programação linear : modelos e algoritmos</cite></a>.
Campus, 2005.
INF 65.012.122 G618o2.</li>

<!-- Authors: David G Luenberger -->
<li><a name="Luenberger/2003">David</a>&nbsp;G. Luenberger.
<a href="http://www.stanford.edu/dept/MSandE/people/faculty/luenberger/linear.html"><cite>Linear and nonlinear programming</cite></a>.
Springer, 2nd edition, 2003.</li>

<!-- Authors: Bernhard H Korte -->
<li><a name="Korte/2005">Bernhard</a>&nbsp;H. Korte.
<a href="http://www.or.uni-bonn.de/~vygen/co.html"><cite>Combinatorial
  optimization theory and algorithms</cite></a>.
Springer, 3rd edition, 2005.
INF 65.012.122 K85c.</li>

<!-- Authors: Mokhtar S Bazaraa and John J Jarvis and Hanif D Sherali -->
<li><a name="Mokhtar.Jarvis/2004">Mokhtar</a>&nbsp;S. Bazaraa, John&nbsp;J.
  Jarvis, and Hanif&nbsp;D. Sherali.
<cite>Linear programming and network flows</cite>.
Wiley, 3rd edition, 2004.
ENG 519.852 B362l.</li>

<!-- Authors: Laurence A Wolsey and George L Nemhauser -->
<li><a name="Wolsey.Nemhauser/1999">Laurence</a>&nbsp;A. Wolsey and
  George&nbsp;L. Nemhauser.
<cite>Integer and Combinatorial Optimization</cite>.
Wiley, 1999.</li>

<!-- Authors: Dimitri P Bertsekas -->
<li><a name="Bertsekas/1999">Dimitri</a>&nbsp;P. Bertsekas.
<a href="http://www.athenasc.com/nonlinbook.html"><cite>Nonlinear
  programming</cite></a>.
Athena, 2nd edition, 1999.
INF 65.012.122 B551n.</li>

<!-- Authors: Laurence A Wolsey -->
<li><a name="Wolsey/1998">Laurence</a>&nbsp;A. Wolsey.
<cite>Integer Programming</cite>.
Wiley, 1998.</li>

<!-- Authors: Christos H Papadimitriou and Kenneth Steiglitz -->
<li><a name="Papadimitriou.Steiglitz/1982">Christos</a>&nbsp;H.
  Papadimitriou and Kenneth Steiglitz.
<cite>Combinatorial optimization: Algorithms and complexity</cite>.
Prentice-Hall, dover edition edition, 1982.</li>

<!-- Authors: G Ausiello and P Crescenzi and G Gambosi and V Kann and A
  Marchetti Spaccamela and M Protasi -->
<li><a name="Ausiello.etal/1999">G</a>.&nbsp;Ausiello, P.&nbsp;Crescenzi,
  G.&nbsp;Gambosi, V.&nbsp;Kann, A.&nbsp;Marchetti-Spaccamela, and M.&nbsp;Protasi.
<a href="http://www.nada.kth.se/~viggo/approxbook"><cite>Complexity and
  approximation &ndash; Combinatorial Optimization Problems and their
  Approximability Properties</cite></a>.
Springer-Verlag, 1999.
INF 510.5 C737.</li>

<!-- Authors: Robert J Vanderbei -->
<li><a name="Vanderbei/2001">Robert</a>&nbsp;J. Vanderbei.
<a href="http://www.princeton.edu/~rvdb/LPbook"><cite>Linear programming:
  Foundations and Extensions</cite></a>.
Kluwer, 2nd edition, 2001.</li>

</ul>

<!-- END BIBLIOGRAPHY livros -->
</html>

<html>
<a href="http://www2.clustrmaps.com/counter/maps.php?url=http://www.inf.ufrgs.br/~mrpritt" id="clustrMapsLink"><img width=1 src="http://www2.clustrmaps.com/counter/index2.php?url=http://www.inf.ufrgs.br/~mrpritt" style="border:1px solid;" alt="Locations of visitors to this page" title="Locations of visitors to this page" id="clustrMapsImg" onError="this.onError=null; this.src='http://clustrmaps.com/images/clustrmaps-back-soon.jpg'; document.getElementById('clustrMapsLink').href='http://clustrmaps.com'" />
</a>
</html>