CCP9018 - Otimização Combinatória e em Grafos
Esta é a página principal da disciplina de Otimização Combinatória e em Grafos, ofertada ao Programa de Pós-Graduacao Modelagem e Métodos Quantitativos da Universidade Federal do Ceará (https://mmq.ufc.br/pt/).
Docente
Prof. Bruno A. Prata
Ementa
Tipos de problemas de otimização combinatória e de otimização em redes. Abordagem para problemas de empacotamento e cobertura via programação linear inteira e algoritmos de aproximação. Problemas de Caminho: formulações do problema de caminho mínimo como problema de programação linear e dinâmica, princípios básicos de programação dinâmica, algoritmos de rotulação, algoritmos de Dantzig, Dijkstra, Floyd. Problemas de fluxo: teorema max flow/min cut, algoritmos de aumento de fluxo, algoritmos de balanceamento de excessos, implementação com árvores dinâmicas; algoritmos para fluxo de custo mínimo (polinomial e do tipo simplex), algoritmos do tipo scaling. Árvore geradora, árvore geradora mínima, algoritmos de Prim e Kruskal. Fluxos em redes, modelos de programação linear inteira.
Software
Durante a disciplina será utilizada a linguagem Julia (https://julialang.org/). Recomenda-se o uso das IDE's Visual Studio Code (https://code.visualstudio.com/) ou Atom (https://atom.io/).
Aulas
| Aula | Assunto | Videoaula |
|---|---|---|
| 1 | Linguagem, ambiente integrado de desenvolvimento e resolvedor. | https://youtu.be/SJjVKnqHV9o |
| 2 | O problema da mochila | https://youtu.be/5Sru3c2_AQg |
| 3 | O problema de agrupamento capacitado | https://youtu.be/ScNjYdBpKAQ |
| 4 | O problema de corte de estoque | https://youtu.be/s8acQJiJLQg |
| 5 | O problema de empacotamento unidimensional | https://youtu.be/uaasTgcfH3o |
| 6 | O problema de empacotamento bidimensional | https://youtu.be/_dPsC5giaXQ |
| 7 | Problemas de cobertura e particionamento de conjuntos | https://youtu.be/i8eQadmaCEw |
| 8 | Problema de máquinas paralelas não-relacionadas | https://youtu.be/3SM6OhB8_Lo |
Bibliografia recomendada
- AHUJA, R.K.; MAGNANTI, T.L.; ORLIN, J.B. Network Flows: Theory, Algorithms, and Applications. Prentice Hall, USA, 1993.
- BAZARAA, M.; JARVIS, A.; SHERALI, H. Linear Programming and Network Flows. Wiley, 4ª. edição, 2011
- SZWARCFITER, J. Grafos e Algoritmos Computacionais. Campus, 2ª. Edição, 1986.
- ARENALES, M.; ARMENTANO, V.; MORABITO, R; YANASSE, H. Pesquisa Operacional. Editora Campus (Elsevier), 2ª. Edição, 2011.
- GOLDBARG, M.C. e LUNNA, H.P.L. Otimização Combinatória e Programação Linear: Modelos e Algoritmos. 2ª Edição .Editora Campus Ltda, Rio de Janeiro, 2005.
- PAPADIMITRIOU, C.H.; STEIGLITZ, K. Combinatorial Optimization: algorithms and complexity. Dover Publications, 1998.