Algoritmos de Programação Linear
O problema básico de programação linear consiste no seguinte: dada uma matriz A e vetores b e c, encontrar um vetor x tal que
x ≥ 0 , A x = b e c x é mínimo.
Eis um exemplo concreto: encontrar números não negativos x1 , x2 , . . . , x8 que satisfaçam as restrições
| 5 x1 | − | 14 x2 | + | 32 x3 | + | 2 x4 | − | 97 x5 | + | 8 x6 | + | 3 x7 | + | 4 x8 | = | 832 |
| 22 x1 | + | 4 x2 | + | 0 x3 | − | 77 x4 | + | 3 x5 | + | 8 x6 | + | 0 x7 | + | 4 x8 | = | −13 |
| 0 x1 | + | 0 x2 | + | 1 x3 | + | 11 x4 | + | 0 x5 | − | 66 x6 | + | 0 x7 | + | 22 x8 | = | 33 |
| −1 x1 | − | 2 x2 | − | 3 x3 | + | 0 x4 | + | 0 x5 | + | 0 x6 | + | 0 x7 | + | 33 x8 | = | 555 |
e minimizem o valor da expressão
| −3 x1 | + | 94 x2 | − | 95 x3 | + | 96 x4 | + | 90 x5 | + | 90 x6 | + | 1 x7 | + | 90 x8 | = | 999 |
O livro discute esse problema, suas variantes e generalizações, e a correspondente teoria da dualidade.
Nosso ponto de partida é o algoritmo de Gauss-Jordan e o
algoritmo Simplex.
Toda a teoria de 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 para o problema de programação linear. O algoritmo que discutiremos — uma variante do célebre algoritmo do elipsóide — não é uma alternativa prática para o Simplex (outros algoritmos da família, entretanto, competem com o Simplex) 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 em notação ponto-flutuante; em particular, o livro não trata das heurísticas que procuram reduzir os erros de arredondamento e melhorar o desempenho médio de tais implementações. O livro também não trata das dificuldade práticas associadas com a manipulação de matrizes muito grandes, nem de algoritmos especiais para matrizes esparsas. Finalmente, o livro não trata de modelagem, que é a arte de transformar certos problemas de otimização em 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).
A atitude do livro é mais matemática e conceitual que tecnológica. Em outra dimensão, a atitude é mais algébrica que geométrica. O enfoque é algorítmico: toda a teoria é derivada dos algoritmos, particularmente do Simplex.
Os algoritmos são descritos de maneira precisa, em linguagem razoavelmente informal. Para tornar isso possível, é necessário introduzir definições limpas para os conceitos de matriz e vetor e uma notação suficientemente poderosa para descrever partes desses objetos. O livro procura dizer com precisão o quê cada algoritmo faz e não apenas como faz o quê faz. O comportamento dos algoritmos é descrito por meio de invariantes, e o seu desempenho de pior caso é analisado.
O universo natural da programação linear é o dos números racionais. O livro supõe, portanto, que dispomos de um agente computacional capaz de executar aritmética racional exata. Uma das versões do Simplex manipula os numeradores e denominadores dos números racionais em separado e portanto só usa aritmética inteira. Segue daí uma versão do Teorema da Dualidade que especifica delimitações superiores para o número de dígitos das soluções do problema de programação linear.
O livro evita o uso indiscriminado de ferramentas da álgebra linear,
porque tais ferramentas são, em geral,
mais sofisticadas que as situações concretas que
pretendemos enfrentar.
O livro evita também as hipóteses simplificadoras
tão comuns em outros textos sobre o assunto
(por exemplo, a hipótese de que nossas matrizes têm
posto pleno
e a hipótese de que dispomos de uma solução viável
ao iniciar a execução do Simplex).
Tais hipóteses pouco contribuem para simplificar a discussão.
Este livro é dirigido a qualquer pessoa que queira compreender as interconexões lógicas entre as várias peças desse quebra-cabeças que é a programação linear. Em particular, o texto se destina a estudantes de graduação e pós-graduação em matemática aplicada, computação e engenharia. O livro não tem pré-requisitos formais, mas exige uma certa maturidade matemática.
Versões preliminares do livro foram usadas nos cursos de graduação e pós-graduação em Ciência da Computação no Instituto de Matemática e Estatística da Universidade de São Paulo.
O subtítulo
Programação Linear Concreta
é uma alusão ao Concrete Mathematics
de Graham, Knuth e Patashnik.
Para explicar o título, o prefácio daquele livro diz:
The course titleEspero que o leitor perdoe o autor por essa alusão pretenciosa ao Concrete Mathematics.Concrete Mathematicswas originally intended as an antidote toAbstract Mathematics[ . . . ]. Abstract mathematics is a wonderful subject, [ . . . ] But [ . . . ] The goal of generalization had become so fashionable that a generation of mathematicians has become unable to relish beauty in the particular, to enjoy the challenge of solving quantitative problems, or to appreciate the value of technique.