Programação linear

ALGORITMOS DE PROGRAMAÇÃO LINEAR
Programação Linear Concreta

Paulo Feofiloff
Professor do Departamento de Ciência da Computação do Instituto de Matemática e Estatística da Universidade de São Paulo

novembro de 1997 revisto em 27.7.1999 reformatado em 11.9.2005

Prefácio
O problema básico de programação linear1 consiste no seguinte: dada uma matriz A e vetores b e c, encontrar um vetor x tal que x ≥ 0, Ax = b e cx é mínimo .

O livro discute este problema, suas variantes e generalizações, e a correspondente teoria da dualidade. O que. Nosso ponto de partida é o algoritmo de Gauss-Jordan e o algoritmo Simplex. Toda a teoria da programação linear é deduzida desses dois algoritmos. Do ponto de vista do Simplex, o problema básico tem a seguinte forma: transformar uma matriz dada (a matriz resulta da justaposição de A, b e c) em outra equivalente que contenha um certo “padrão” ou “desenho”. Examinaremos também um representante da família de algoritmos polinomiais de programação linear que surgiu em meados da década –. O algoritmo que discutiremos — uma variante do célebre algoritmo do elipsóide — não é uma alternativa prática para o Simplex,2 mas tem profundas implicações teóricas. O livro não trata dos aspectos mais práticos da programação linear. Assim, por exemplo, o livro não se ocupa das implementações aproximadas do Simplex, que representam números racionais em notação ponto flutuante; em particular, o livro não trata das heurísticas que procuram reduzir os erros de arredondamento de tais implementações. O livro também não trata das dificuldades práticas associadas com a manipulação de matrizes muito grandes, nem de algoritmos especiais para matrizes esparsas.3 Finalmente, o livro não trata de modelagem, que é a arte de reduzir certos problemas de otimização a problemas de programação linear. Todos esses tópicos são muito importantes na prática, mas estão além dos objetivos do livro (e da competência do autor). Como. A atitude do livro é mais