Aulas

• Aula 1 - 5/agosto
  • Escopo da disciplina (tópicos que serão vistos na disciplina)
  • Preliminares (conceitos básicos sobre grafos e programação linear) veja aqui
• Aula 2 7/agosto
  Cap 1. OC / POC linear/ Modelagem de problemas usando variáveis 0/1
  
  • Problemas PO,PNL,PL,PLI,PL/01,POC, POC linear)
  • Relação entre POC linear e PL/01
  • Modelagem: Problema da mochila. 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.

  Não houve aula nos dias 12 e 14 - professora esteve fora de SP (evento e banca).

• Aula 3 - 19/agosto
  • Cap 1. (cont) Modelagem de problemas usando variáveis 0/1 (cont.)
    Problema do caminho múnimo. Como lidar com restriçãoes disjuntivas.
• Aula 4 - 21/agosto
  • Cap 1. (cont) Como modelar escolhas de restriçãoes a serem satisfeitas. Formulaçãoes para o Problema do Caixeiro Viajante (TSP - Traveling Salemsan problem). O Problema da Árvore Gerador Mínima (Minimum Spanning Tree - MST): discussão sobre formulações equivalentes ou mais fortes. Comentários sobre a Lista 1 (veja no Paca).

  AVISO: Inscrevam-se no Paca, na disciplina MAC0325/MAC5781-Otimização Combinatória: https://paca.ime.usp.br -- Material e Listas -- disponibilizados no Paca.

• Aula 5 - 26/agosto
  • 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 6 - 28/agosto
  • Cap 2. MSR (cont.) - árvore geradora (base)
• Aula 7 - 09/setembro
  • MSR (cont.)- Recapitulação do Método Simplex (PL geral), folgas complementares, teorema da dualidade, condição de otimalidade (vetor dos custos reduzidos). Uma iteração do MSR
• Aula 8 - 11/setembro
  • MSR (cont)- Uma iteração do MSR. Caracterização: quando o probl. é ilimitado.
• Aula 9 - 16/setembro
  • Atualização da variável dual; solução inicial: como encontrar (quando existe), certificar não-existência, ou decompor o problema.
• Aula 10 - 18/setembro
  • Decomposição em subproblemas. Degenerescência e ciclagem; regra para evitar ciclagem
• Aula 11 - 23/setembro
  • Estrutura de dados para implementação do MSR. -- material novo em aula.
  • Aplicações (modelagem como problemas de fluxo em redes (PT)).
• Aula 12 - 25/setembro
  • Cap 3. - O Teorema da Integralidade e suas aplicações em problemas combinatórios. (Trazer cap3 na aula - material no Paca.)
• Demais aulas -- consultar em https://paca.ime.usp.br, a disciplina MAC0325/MAC5781-Otimização Combinatória: Material e Listas -- a partir de agora serão dsiponibilizados no paca.