Pesquisa Operacional 2

Horários das aulas

• Segundas-feiras de 12:00 as 14:00 (Sala 18 Eixo 3, LABMAT)
• Terças-feiras de 16:00 as 18:00 (Sala 18 Eixo 3, LABMAT)

Ementa e programa

Objetivos da disciplina

• Estudar modelos de problemas variados usando as técnicas de programação linear inteira e programação dinâmica
• Promover o uso de pacotes computacionais de resolução de problemas de programação linear Inteira
• Estudar teoria, algoritmos e aplicações de Otimização em Redes

Textos de referência

• Wolsey, L. A. Integer Programming. 2ed, Wiley, 2021
  [link]
• Goldbarg, M. C.; Luna, H. P. L. Otimização combinatória e programação linear: modelos e algoritmos. Elsevier, 2ed, 2005
  [link]
• Hillier, F. S.; Lieberman, G. J. Introdução à Pesquisa Operacional. McGraw-Hill, 8ed, 2006

Textos complementares

• Maculan, N.; Fampa, M. H. C. Otimização linear. Editora UnB, 2006
  [link versão alternativa]
• Luenberguer; Ye. Linear and Nonlinear Programming. Springer, 2008
  [link 1] [link 2]
• Bazaraa, M. S.; Jarvis, J. J.; Sherali, H. D. Linear Programming and Network Flows. Wiley, 4ed, 2010
  [link 1] [link 2 (1ed de 1977)]

Canais de acesso

• E-mail do professor: leonardo.secchin@ufes.br
• Sala do professor: prédio do Departamento de Matemática Aplicada, sala 08

Formas de avaliação

• provas escritas, listas de exercícios, trabalhos computacionais ou apresentações orais.

Avaliações

Critérios para aprovação

• Média parcial >= 7,0 —–> aprovado(a) (desde que não reprovado(a) por falta)
• Média parcial < 7,0 —–> Avaliação final (desde que não reprovado(a) por falta). Neste caso, média final >= 5,0 —–> aprovado(a).

Conteúdo

A linguagem de programação Julia

Julia é uma linguagem de programação de alto nível surgida em 2012, que implementa várias ferramentas para uso geral em matemática aplicada. Em particular, Julia possui várias ferramentas para otimização. É muito parecida com o Matlab, portanto os códigos são fáceis de entender. Os trabalhos computacionais desta disciplina serão feitos em Julia.

Para uma introdução ao Julia e seu uso em otimização, acesse este link.

Softwares / Interfaces para Julia

• CPLEX
  O CPLEX é um pacote mantido pela IBM e muito utilizado na academia e indústria. Nele há vários métodos para programação linear inteira mista. É um software proprietário, mas estudantes das universidades podem obter licença de uso mediante preencimento de um cadastro.
  • Instruções para download (atualizado em agosto de 2026)

• GLPK
  GLPK é um pacote que implementa vários métodos para programação linear inteira mista. Ao contrário do CPLEX, é software livre, ou seja, você pode instalar e usar sem a necessidade de obter licenças. É uma opção de fácil instalação caso você tenha problemas com o CPLEX.

• Uso dos pacotes no Julia
  Tanto o CPLEX quando o GLPK podem ser utilizados dentro do Julia. Para tanto, basta instalar os pacotes CPLEX.jl e GLPK.jl no seu Julia.
  • Obs: CPLEX.jl não instala o CPLEX automaticamente, você precisa instalá-lo na sua máquina antes; siga as instruções para download. Já GLPK.jl baixa e instala o GLPK automaticamente.
  • Teste executando o código exemplo para o problema de localização de facilidades não capacitado.

Introdução à programação linear inteira mista

1. O modelo de programação linear inteira mista
2. Exemplos de aplicações
   Referências:
   1) Goldbarg, M. C.; Luna, H. P. L. Otimização combinatória e programação linear: modelos e algoritmos. Elsevier, 2ed, 2005
   2) Wolsey, L. A. Integer Programming. 2ed, Wiley, 2021
3. Exemplos de problemas e respectivos pacotes/códigos para uso no Julia, veja este link

Métodos em programação linear inteira mista

1. Relaxação linear e relaxação Lagrangeana
   Referência: Wolsey, L. A. Integer Programming. 2ed, Wiley, 2021

2. Método de enumeração e poda (Branch-and-bound)
   1. Pré-processamento
      Referências:
      1) Hillier, F. S.; Lieberman, G. J. Introdução à Pesquisa Operacional. McGraw-Hill, 8ed, 2006
      2) Wolsey, L. A. Integer Programming. 2ed, Wiley, 2021
      • Pré-processamento de PL’s: fixação de variáveis, aperto de limitantes das variáveis e identificação de restrições redundantes
      • Identificação de PL’s inviáveis ou ilimitados
      • Estratégias adicionais de pré-processamento para problemas com variáveis inteiras e binárias: aperto de restrições

   2. Inserção de restrições no quadro simplex e o método dual simplex (conteúdo de PO I, revisão)
      Referência: Bazaraa, M. S.; Jarvis, J. J.; Sherali, H. D. Linear Programming and Network Flows. Wiley, 4ed, 2010

   3. Branch-and-bound baseado em relaxação linear
      Referências:
      1) Wolsey, L. A. Integer Programming. 2ed, Wiley, 2021
      2) Goldbarg, M. C.; Luna, H. P. L. Otimização combinatória e programação linear: modelos e algoritmos. Elsevier, 2ed, 2005

   4. Branch-and-bound - exemplos com variáveis inteiras e binárias
      Referências:
      1) Wolsey, L. A. Integer Programming. 2ed, Wiley, 2021
      2) Goldbarg, M. C.; Luna, H. P. L. Otimização combinatória e programação linear: modelos e algoritmos. Elsevier, 2ed, 2005

   5. Exemplo de problema inviável em que branch-and-bound fracassa
      Referência: Jeroslow. Trivial integer programs unsolvable by branch-and-bound. Mathematical Programming 6, 105-109 (1974)
      • Código Julia
3. Método de planos de corte
   Referência: Wolsey, L. A. Integer Programming. 2ed, Wiley, 2021
   1. Desigualdades válidas
   2. Esquema geral do método
4. Método Branch-and-cut
   Referência: Wolsey, L. A. Integer Programming. 2ed, Wiley, 2021
   1. Cortes de Chvatal-Gomory
   2. Cortes fracionários de Gomory via quadro simplex
5. Método de geração de colunas
   Referências:
   1) Wolsey, L. A. Integer Programming. 2ed, Wiley, 2021
   2) Maculan, N.; Fampa, M. H. C. Otimização linear. Editora UnB, 2006
   3) Tópico 6 deste link
   1. Geração de colunas aplicado ao problema de corte de estoque (cutting stock)
      • Código Julia com instâncias do problema
   2. Decomposição de Dantzig-Wolfe

6. Comentários sobre os métodos Branch-and-price e Branch-cut-and-price
   Referência: Wolsey, L. A. Integer Programming. 2ed, Wiley, 2021

7. Comentários sobre o uso de heurísticas/metaheurísticas no contexto de métodos enumerativos
   Referências:
   1) Wolsey, L. A. Integer Programming. 2ed, Wiley, 2021
   2) Goldbarg, M. C.; Luna, H. P. L. Otimização combinatória e programação linear: modelos e algoritmos. Elsevier, 2ed, 2005

Otimização em redes

Referência: Bazaraa, M. S.; Jarvis, J. J.; Sherali, H. D. Linear Programming and Network Flows. Wiley, 4ed, 2010

1. Conceitos básicos (grafos, árvore etc)
2. Exemplos: caminho mínimo, fluxo máximo, fluxo de custo mínimo, problemas do transporte e atribuição
3. Problema do transporte: resolução via simplex
   1. Matriz totalmente unimodular
   2. Obtendo uma base inicial viável
   3. Quadro simplex
   4. Caso particular: problema de atribuição
      • Relaxação linear, matriz totalmente unimodular e integralidade das soluções
4. Problema de fluxo de custo mínimo
   1. Método simplex de rede
5. Problema do menor caminho
   1. Algoritmo de Dijkstra para custos não negativos

Programação dinâmica

Referência: Hillier, F. S.; Lieberman, G. J. Introdução à Pesquisa Operacional. McGraw-Hill, 8ed, 2006

1. Princípios da programação dinâmica
2. Exemplo simples: sequência de Fibonacci
3. Problema da mochila 0-1
4. Exemplo protótipo, seção 10.1 do livro de Hillier e Lieberman
5. Exemplos da seção 10.3 do livro de Hillier e Lieberman
6. Outros exemplos
   1. Subset sum
   2. O algoritmo de Dijkstra (tópico anterior) usa conceitos de programação dinâmica