BCC463 - Otimização em Redes - 2023-2

Carga horária da disciplina: 4 horas/aula


Professor(es) em 2023-2

Turma 11 Professor:
Marco Antonio Moreira de Carvalho - www | e-mail

Horários:
Segunda-feira (08h20 - 10h00)
Quarta-feira (08h20 - 10h00)

Objetivos

Ao final do curso é esperado que o aluno tenha capacidade de identificar problemas de otimização que podem ser modelados como problema de fluxo em redes, esteja capacitado para gerar os dados necessários e analisar as soluções de um determinado problema pelo uso de algoritmos de fluxo em redes e seja capaz de implementar algoritmos para os principais problemas de fluxo em redes, tais como o problema de caminho mínimo, de fluxo máximo e de fluxo com custo mínimo, utilizando uma linguagem de programação.

Ementa

Conceitos básicos sobre grafos; modelos de fluxos em redes; algoritmos do caminho mínimo, do fluxo máximo e do fluxo com custo mínimo; aplicações e implção de algoritmos especializados.

Conteúdo Programático

- Conceitos básicos sobre grafos
        - Notação e definições
        - Representação em redes
        - Exemplos de modelos em redes
- Problemas de caminho mínimo
        - Introdução
        - Aplicações
        - Algoritmos de solução e implementações
- Problema de fluxo máximo
        - Introdução
        - Aplicações
        - Fluxos e cortes
        - Teorema do fluxo máximo – corte mínimo
        - Algoritmos de solução e implementações
- Problemas de fluxo com custo mínimo
        - Introdução
        - Aplicações
        - Algoritmos de solução e implementações
- Aplicações
        - Problemas de designação
        - Problemas de emparelhamento
        - Problemas de roteamento
        - Problemas de sequenciamento

Bibliografia

- AHUJA, Ravindra K.; MAGNANTI, Thomas L; ORLIN, James B. Network flows: theory, algorithms and applications. Englewood Cliffs: Prentice-Hall, 1993.
- GOLDBARG, Marco Cesar; GOLDBARG, Elizabeth Ferreira Gouvêa. Grafos:  conceitos, algoritmos e aplicações . Rio de Janeiro: Elsevier, 2012.
- BAZARAA, M. S; JARVIS, John J; SHERALI, Hanif D. Linear programming and network flows. 2. ed. New York: J.Wiley, 1990. 
- FRAZER, J. Ronald. Applied linear programming. Englewood Cliffs, N.J.: Prentice-Hall, 1968.
- CHVATAL, V. Linear programming. New York: W. H. Freeman, 1983.

Bibliografia complementar

- ARENALES, M.; ARMENTANO, V.; MORABITO, R.; YANASSE, H.; Pesquisa Operacional para cursos de engenharia: Modelagem e algoritmos. Rio de Janeiro: Editora Campus, 2007.
- GOLDBARG, M.; LUNA, H.P.L.; Otimização Combinatória e Programação Linear. 2. ed. Editora Campus, 2005.
- WOLSEY, L.A. Integer Programming. Wiley, 1998.
- BAZARAA, M. S; JARVIS, John J; SHERALI, Hanif D. Linear programming and network flows. 2. ed. New York: J.Wiley, 1990.
- HU, T. C. Integer programming and network flows. Reading: Addison Wesley, 1970.

Departamento de Computação  |  ICEB  |  Universidade Federal de Ouro Preto
Campus Universitário Morro do Cruzeiro  |  CEP 35400-000  |  Ouro Preto - MG, Brasil
Telefone: +55 31 3559-1692  |  decom@ufop.edu.br