DCC035 – Pesquisa Operacional

Disciplina ministrada pelo Prof. Alexandre Salles da Cunha para os cursos de Bacharelado em Ciência da Computação e Matemática Computacional da UFMG.

===> Link para versão do curso on-line de Pesquisa Operacional

Panorama do curso:

O curso de Pesquisa Operacional poderia perfeitamente se chamar “Introdução à Otimização Linear e Inteira”, pois esse é essencialmente o conteúdo coberto pela disciplina. Assim, apesar do nome da disciplina sugerir o contrário, o curso não trata de áreas da Pesquisa Operacional como Simulação, Teoria de Filas, etc.

O curso é dividido em três blocos:

• Programação Linear, Modelagem e Algoritmos (aproximadamente 50% do curso).

• Problemas de Fluxo em Redes (aproximadamente 25% do curso).

• Programação Linear Inteira (aproximadamente 25% do curso).

Primeiro bloco:

O curso apresenta uma abordagem para Programação Linear que parte dos elementos mais essenciais para um aluno de graduação que já teve um curso introdutório de Geometria Analítica e Álgebra Linear. Este é o único pré-requisito do curso. Uma exposição à Álgebra Linear Computacional é muito desejável, mas não é imprescindível (a página do curso de Álgebra Linear Computacional ministrado pelo Prof. Alexandre para os cursos de graduação do DCC/UFMG encontra-se aqui.)

Após uma apresentação de modelos de Programação Linear e Inteira, apresentamos o método de Eliminação de Fourier-Motzkin (Método de Projeção) que nada mais é do que uma generalização, para sistemas de desigualdades lineares, do método de Eliminação de Gauss, que resolve sistemas lineares. Com o ferramental de Eliminação de Fourier em mãos, discutimos um algoritmo (elegante, mas não eficiente) para a resolução do Problema de Programação Linear. A Eliminação de Fourier também permite apresentar de uma forma muito elegante e independente o conceito de Dualidade em Programação Linear, assim como o Lema de Farkas e os Teoremas das Alternativas.

Na sequência, discutimos aspectos geométricos da Programação Linear, lançando as bases para a apresentação do Algoritmo Simplex, conferindo a ele uma interpretação algébrica e combinatorial.

Nossa apresentação do Algoritmo Simplex não faz uso dos usuais Tableaus Simplex, comumente empregados na literatura, inclusive em parte daquela que citamos abaixo, como material de apoio para o curso. Nossa apresentação do algoritmo emprega o conceito de dicionário, que pelo que conhecemos foi introduzido por Chvátal [ref. 4], e também utilizado por Vanderbei [ref. 6].

Concluindo o primeiro bloco da disciplina, retornamos à Dualidade em Programação Linear, com uma visão complementar àquela discutida no contexto de projeção. Com o ferramental de dualidade, apresentamos o Algoritmo Dual Simplex, que encerra o primeiro bloco do curso.

Segundo bloco:

No segundo bloco, discutimos problemas de Otimização Combinatória que podem ser resolvidos via Programação Linear, uma vez que são formulados a partir de matrizes de fluxo, totalmente unimodulares. Tais problemas são usualmente denominados Problemas de Fluxo em Redes: Fluxo de Custo Mínimo, Emparelhamento Máximo em um Grafo Bipartido, Árvore Geradora Mínima, Problema do Transporte. Em função da estrutura destes problemas, apresentamos algoritmos polinomiais dedicados a cada um. Alguns destes algoritmos podem ser entendidos como especializações do Método Simplex.

Terceiro bloco:

O terceiro bloco é uma introdução à Programação Linear Inteira e apresenta os conceitos de formulações boas e ideais, algoritmos de planos de corte, algoritmos Branch-and-bound e algumas de suas especializações mais comuns. Também discutimos o paradigma de Programação Dinâmica.

Conteúdo on-line disponível no youtube:

Um conjunto de aulas foi gravado e disponibilizado na plataforma do youtube, como material de apoio para o curso de Pesquisa Operacional. A relação de 55 aulas, equivalentes a cerca de 30 horas gravadas, pode ser encontrado aqui. Na mesma página, são disponibilizados os slides empregados no curso gravado.

Referências Bibliográficas:

O curso foi construído tendo como proposta empregar o melhor da literatura mundial para cobrir cada parte do programa da disciplina. Por esta razão, emprega diversas referências bibliográficas, listadas abaixo.

1. Marco Goldbarg e Henrique Luna. Otimização Combinatória e Programação Linear, 2^a. Edição, Editora Campus, 2005.

2. Nelson Maculan, Márcia Fampa. Otimização Linear, Universidade Federal do Rio de Janeiro, 2004.

3. Christos H. Papadimitriou e Kenneth Steiglitz. Combinatorial Optimization: Algorithms and Complexity, Dover Publications, 1998.

4. Vasek Chvátal, Linear Programming. Freeman, 1980.

5. Dimitris Bertsimas e John N. Tsisiklis. Introduction to Linear Optimization, Athena Scientific, 1997.

6. Robert J. Vanderbei, Linear Programming: Foundations and Extensions, 5^a Edição, Springer, 2020.

7. Richard Kipp Martin, Large Scale Linear and Integer Optimization: A Unified Approach. Kluwer Academic Publishers, 1999.

8. Laurence Wolsey. Integer Programming. Wiley Interscience, 1^a. Edição, 1998.

Programa da disciplina:

Programa do primeiro bloco

• Modelagem de problemas de otimização.

• Eliminação de Fourier-Motzkin e Projeção.

• Resolução de Problemas de Programação Linear via Projeção.

• Lema de Farkas.

• Dualidade via projeção.

• Geometria da Programação Linear.

• Método Simplex.

• Dualidade

• Análise de Sensibilidade

• Método Dual-Simplex

Programa do segundo bloco:

• Matrizes de fluxo, matrizes totalmente unimodulares, dualidade forte.

• Problema de Fluxo de Custo Mínimo.

• Problema do Emparelhamento Máximo em um grafo bipartido. Formulações integrais para o problema em grafos bipartidos e em grafos gerais.

• Problema da Árvore Geradora Mínima, formulações integrais para o problema.

• Problema do Transporte.

Programa do terceiro bloco:

• Programação Dinâmica, problema da Mochila 0/1 e Inteira, caminho mais curto em um grafo acíclico.

• Desigualdades válidas, algoritmos de planos de corte.

• Algoritmos Branch-and-bound e Branch-and-cut.