Pesquisa Operacional - Tecnologia da Decisão



Calendário de Atividades da UFPR - ano letivo de 2020
TP052 e TP065

Horários: terças-feiras e quintas-feiras às 17:30

Sala: PA09

Notas: Arquivo (postado em xx/xx/2020)

Ementa TP052: Revisão de Álgebra Linear. Modelos de Programação Linear. O Problema do Transporte. O Problema da Designação. O Método Simplex. Dualidade. Análise de Pós-Otimização.  

Ementa TP065: Modelos de Programação Linear. O Método Simplex. Dualidade. Análise de Pós-Otimização. Utilização de Softwares na Resolução de Problemas de Programação Linear.

Programa
  1. Revisão de álgebra linear: Sistemas de equações e de inequações lineares. Convexidade.
  2. Modelos de Programação Linear: Modelagem (problema da mistura, problemas de  alocação de  recursos, problemas de  planejamento da produção, problema de programação de projetos, problemas de gestão financeira, problema de escalonamento de horários, problema de transporte e designação, problemas de  corte, problemas da mochila).
  3. Modelos de Programação Linear: Solução gráfica. Teoremas fundamentais.
  4. Método Simplex: O Método Simplex. Forma padrão. Transformação de um problema geral para a forma padrão. Casos especiais. Método das duas fases.
  5. Dualidade: Propriedades. Exemplos de formulação do dual. Teorema básico da dualidade. Teorema da folga complementar. Método Dual-Simplex. Interpretação econômica do problema dual.
  6. Análise de pós-otimização: Mudanças dos coeficientes de custos. Mudanças nos recursos. Mudanças nas restrições.

Arquivos
  1. Ementa
  2. Formulação
  3. Resolução gráfica
  4. Teoremas
  5. Método simplex
  6. Simplex duas fases
  7. Dualidade
  8. Dual simplex
  9. Simplex revisado
  10. Pós-otimização
  11. Problema de transportes (solução inicial, método u-v, stepping stone)
  12. Problema de designação
Arquivos diversos

Links - formulação
  1. https://www.youtube.com/watch?v=0oMVVx81kCs
  2. http://people.brunel.ac.uk/~mastjjb/jeb/or/lp.html
  3. https://www.nvc.vt.edu/rmajor/bit5724/Chapter_13.pdf

Listas
  1. http://mayerle.deps.prof.ufsc.br/
  2. Formulação 1, Formulação 1 - respostas, Formulação 2, Formulação 2 - respostas, Formulação 3, Formulação 3 - respostas,
  3. Solução gráfica 1, Solução gráfica 1 - respostas,  Solução gráfica 2, Solução gráfica 3,
  4. Simplex 1, Simplex 2,
  5. Teorema da Folga Complementar, Dualidade,Dualidade 4, Dualidade 4 - respostas
  6. Análise de sensibilidade: exercício resolvido, Análise de Sensibilidade,
  7. Simplex Revisado A, Simplex Revisado B,
  8. Análise de Sensibilidade, Análise de sensibilidade: resolvido, Análise de Sensibilidade,  Lista Análise de Sensibilidade 1, Análise de Sensibilidade 5, Análise de Sensibilidade 5 - respostas
  9. Transporte,
  10. Designação,


Cronograma das Avaliações

Avaliações Data Conteúdo
1a. 16/04/2020 Modelagem. Resolução Gráfica. Teoremas.
2a. 02/06/2020 Simplex. Dualidade.
3a. 25/06/2020 Análise de Sensibilidade.


Exame Final 07/07/2020 Resolução Gráfica. Simplex. Dualidade. Análise de Sensibilidade.


TP053 e TP066

Horários: 

Sala: 

Notas: Arquivo (postado em xx/xx/2020)  

Ementa TP053: Programação Linear Inteira. Otimização em Redes. Programação Dinâmica.

Ementa TP066: Programação Linear Inteira, Binária e Mista. O Problema do Transporte. O Problema da Designação. Otimização em Redes. Algoritmos heurísticos para resolução de Problemas com variáveis inteiras e binárias. Utilização de Softwares para Resolução de PPLI, PPLB e Mista.

Programa
  1. Programação linear inteira, binária e mista: introdução. Modelagem com variáveis binárias. Problema da mochila. Problema de corte. Designação. Cobertura de arcos. Caixeiro viajante. Roteamento de veículos. Localização de facilidades. Método Branch-and-Bound.
  2. Problema do transporte: Exemplos de modelos de transporte. Obtenção da solução inicial. Obtenção da solução ótima. Casos especiais.
  3. Problema da designação: Exemplos de problemas de designação. Algoritmo da designação.
  4. Otimização em redes: Introdução a grafos. Caminho de custo mínimo (Floyd, Dijkstra). Mínima arborescência-MST (Prim, Kruskall). Problema do Caixeiro Viajante-TSP. Problema de roteamento-VRP (Clarke e Wright).
  5. Algoritmos heurísticos para resolução de problemas com variáveis inteiras e binárias: Balas.
  6. Programação Dinâmica: Formulação de modelos de programação dinâmica. Programação dinâmica determinística. Programação dinâmica estocástica. Decisão com horizonte limitado e ilimitado.

Arquivos
  1. Ementa
  2. Formulação - modelos binários
  3. Formulação - modelos clássicos
  4. Formulação - modelos de logística
  5. Formulação - modelos de produção
  6. Branch and bound
  7. Transportes
  8. Designação
  9. Introdução a grafos
  10. Determinação do caminho mínimo (Dijkstra e Floyd-Warshall)
  11. Determinação da árvore geradora mínima (Prim e Kruskall)
  12. Problema do Caixeiro Viajante-TSP (Vizinho mais próximo, Inserção do mais barato, Christofides, Clarke e Wright, 2-opt)
  13. Problema de Roteamento de Veículos-VRP (Clarke e Wright)
  14. Algoritmo de Balas
  15. Programação dinâmica
Arquivos diversos

Listas de exercícios
  1. Livro do Arenales


Cronograma das Avaliações

Avaliações Data Conteúdo
1a. Modelagem. Branch and Bound.
2a. Caminho mínimo. Fluxo máximo. MSP. Designação. Transporte.
3a. TSP. VRP. Algoritmo de Balas.
Exame Final Branch and Bound. Otimização em Redes.


Bibliografia
  1. AMPL - book
  2. Arenales, M., Armentano, V., Morabito, R. e Yanasse, H., Pesquisa Pesquisa operacional para cursos de Engenharia, Rio de Janeiro: Campus, 2006.
  3. Boyd, Stephen, Vandenberghe, Lieven, Convex Optimization, Cambridge University Press, 2009
  4. Dijkstra, E.W. A Note on Two Problems in Connextion with Graphs. Numerische Matehamtik, 269-271 (1959)
  5. Griffin, Christopher, Linear Programming, 2009-2011
  6. Güneş Erdoğan, An open source Spreadsheet Solver for Vehicle Routing Problems, Computers & Operations Research, Volume 84, 2017, Pages 62-72 (link, planilha)
  7. Hillier, F. S. e Lieberman, G. J., Introdução à Pesquisa Operacional, São Paulo: McGraw-Hill, 2010
  8. Hira, D S, Gupta, P K, Problems in Operation Research (Principles & Solution): Principles and Solutions,  S. Chand & Company Pvt. Ltd., 4th edition, 2015 (link)
  9. Integer Linear Programming Tricks, in AIMMS Modeling Guid (link)
  10. Lachtermarcher, Gerson. Pesquisa Operacional na Tomada de Decisões, 4a. Edição, São Paulo, Pearson, 2009
  11. Modeling with Integer Programming, by Laura Galli (link)
  12. Nonconvex piecewise linear functions: Advanced formulations and simple modeling tools, by Joey Huchette and Juan Pablo Vielma (link)
  13. Puccini, A.L., Pizzolato, N.D., Programação Linear, LTC, 1990
  14. Robert Fourer, David M. Gay, and Brian W. Kernighan, AMPL: A Modeling Language for Mathematical Programming, second edition (link)
  15. Sottinen, Tommi, Operations Research with GNU Linear Programming Kit, 2009
  16. Taha, Hamdy A., Pesquisa Operacional, 8a. Edição, São Paulo, Pearson, 2008
  17. Wagner, H.M., Pesquisa Operacional, Prentice Hall do Brasil, 1986


Software
  1. AMPL - http://users.iems.northwestern.edu/~4er/amplweb/DOWNLOADS/details.html#WinStd
  2. LpSolve -  lp_solve_5.5.2.0_IDE_Setup.exe
  3. OpenSolver - https://sourceforge.net/projects/opensolver/
  4. Octave -  http://www.gnu.org/software/octave/doc/interpreter/index.html
  5. Simplex online - http://www.mathstools.com/section/main/simplex_online_calculator#
  6. VRP - solver - http://people.bath.ac.uk/ge277/index.php/vrp-spreadsheet-solver/


Links
  1. Branch and Bound 0,  Branch and Bound 1a e 1b,  Branch and Bound 2, Branch and Bound 3
  2. Transbordo a e Transbordo b,
  3. Problema do Caixeiro Viajante-TSP,
  4. Problema de Roteamento de Veículos-VRP,
  5. ..

contador gratuito de visitas