Aulas

• Aula 1 - 9/agosto
  • Escopo da disciplina (PNL/PL/PLI/POC/POC linear)
  • Cap 1. Modelagem de problemas usando variáveis 0/1: Problema da mochila.
• Aula 2 - 11/agosto
  • Cap 1 (cont.) Modelagem de problemas usando variáveis 0/1. Problema do caminho mínimo. Problema do empacotamento unidimensional (bin packing).
• Aula 3 - 16/agosto
  • Cap 1 (cont.) Modelagem de problemas usando variáveis 0/1. Problema do emparelhamento máximo e problema da cobertura mínima. Caso especial em que o grafo é bipartido (versão cardinalidade) -- dualidade em PL. Teorema min-max de König. Tipos especiais de restrições.
  • Lista 1 (exercícios para casa)
• Aula 4 - 18/agosto
  • Cap.1 (cont.) Modelagem 0/1: Árvore Geradora Mínima e TSP.
  • Cap 2 PL's com estruturas especiais: simplex para redes.
    • Descrição algébrica do Método Simplex (geral): viabilidade primal, folgas complementares; condição de parada: viabilidade dual.
    • Formulação do PT (Problema do Transporte); matriz de incidência de um grafo orientado; condição sobre as demandas.
• Aula 5 - 23/agosto
  • MSR (Método Simplex para Redes)
• Aula 6 - 25/agosto
  • MSR (cont.)
• Aula 7 - 30/agosto
  • MSR (cont) - reconhecimento de probl. é ilimitado. Como encontrar uma solução inicial.
• Aula 8 - 01/setembro
  • Decomposição em subproblemas. Degenerescência e ciclagem; regra para evitar ciclagem
• Aula 9 - 01/setembro
  • Decomposição em subproblemas. Degenerescência e ciclagem; regra (de Cunningham) para evitar ciclagem (conceito de árvore fortemente viável)
• Aula 10 - 13/setembro
  • Modelagem (como probl. PT)
• Aula 11 - 15/setembro
  • Mais modelagem
• Aula 12 - 20/setembro
  • Cap.3 - PT: o teorema da integralidade e suas aplicações em problemas combinatórios.
  • Sobre um resultado mais geral (Teorema de Hoffman & Kruskal - poliedro inteiro). Conceito de matriz T.U. (Totalmente Unimodular) -- exercício
• Aula 13 - 22/setembro
  • Aplic. Teorema da integralidade
  • problema do casamento perfeito; matrizes duplamente estocásticas
• Aula 14 - 27/setembro
  • Aplic. MSR + Teorema da integralidade: emparelhamento máximo e cobertura mínima. (Teorema min-max de König)
• Aula 15 - 29/setembro
  • Cap. 4 O problema do transporte capacitado
    • Algoritmo, regras para evitar ciclagem, etc