Informações da Disciplina

 Preparar para impressão 
Júpiter - Sistema de Graduação

Instituto de Matemática e Estatística
 
Ciência da Computação
 
Disciplina: MAC0325 - Otimização Combinatória
Combinatorial Optimization

Créditos Aula: 4
Créditos Trabalho: 0
Carga Horária Total: 60 h
Tipo: Semestral
Ativação: 01/01/2012 Desativação:

Objetivos
Ensinar técnicas para o tratamento de problemas de otimização combinatória, em especial aqueles que podem ser formulados como problemas em grafos.
 
 
 
Programa Resumido
O escopo da otimização combinatória e programação inteira. Modelagem de vários problemas usando variáveis 0/1. O problema do transporte. Especialização do método simplex para redes. Aplicações: teorema de Hall, teorema de König, teorema de Dilworth. O problema do transporte capacitado: o método primal-dual. Algoritmos para fluxos máximos em redes. Fluxos de custo mínimo e circulações viáveis: o método "out-of-kilter". Estudo aprofundado de poliedros de alguns problemas não-unimodulares bem resolvidos (emparelhamentos, branchings, etc.).
 
 
 
Programa
O escopo da otimização combinatória e programação inteira. Modelagem de vários problemas usando variáveis 0/1. O problema do transporte. Especialização do método simplex para redes. Aplicações: teorema de Hall, teorema de König, teorema de Dilworth. O problema do transporte capacitado: o método primal-dual. Algoritmos para fluxos máximos em redes. Fluxos de custo mínimo e circulações viáveis: o método "out-of-kilter". Estudo aprofundado de poliedros de alguns problemas não-unimodulares bem resolvidos (emparelhamentos, branchings, etc.).
 
 
 
Avaliação
     
Método
Aplicação de provas e/ou trabalhos.
Critério
Média ponderada de provas e exercícios
Norma de Recuperação
Aplicação de provas e/ou trabalho de recupeção.
 
Bibliografia
     
W.J. Cook, W.H. Cunningham, W.R. Pulleyblank, A. Schrijver, Combinatorial Optimization, John Wiley, 1998.
R.K. Ahuja, T.L. Magnanti, J.B. Orlin, Network Flows: Theory, Algorithms, and Applications, Prentice Hall, 1993.
C.H. Papadimitrou, K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Prentice Hall, 1982.
E. Lawler, Combinatorial Optimization: Networks and Matroids, Holt, Rinehart & Winston, 1976.
V. Chvátal, Linear Programming, Freeman, New York, 1983.
 

Clique para consultar os requisitos para MAC0325

Clique para consultar o oferecimento para MAC0325

Créditos | Fale conosco
© 1999 - 2019 - Superintendência de Tecnologia da Informação/USP