Programação linear

Páginas: 298 (74312 palavras) Publicado: 10 de fevereiro de 2013
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 vetorx 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 profundasimplicaçõ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áticasassociadas 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 é maismatemática e conceitual que tecnológica. Em outra dimensão, a atitude é mais algébrica que geométrica. O enfoque é
Neste contexto, o termo programação significa planejamento. Não se trata de uma referência à programação de computadores. 2 Outros algoritmos da família, entretanto, competem com o Simplex. 3 O leitor interessado nesses tópicos deve consultar os livros de Chvátal [Chv83] e Golub e VanLoan [GL96].
1

i

Feofiloff

ii

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 livroprocura dizer com precisão o que cada algoritmo faz e não apenas como faz o que 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. Uma das versões do Simplex(capítulo 12 manipula em separado os numeradores e denominadores dos números racionais 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 queas situações concretas que é preciso enfrentar. O livro evita também as “hipóteses simplificadoras” (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) tão comuns em outros textos sobre o assunto. Tais hipóteses pouco contribuiriam para simplificar a discussão. Para quem. Este livro é dirigido a...
Ler documento completo

Por favor, assinar para o acesso.

Estes textos também podem ser interessantes

  • Programação linear
  • Programação Linear
  • Programação Linear
  • Programação linear
  • Programação linear
  • Programação linear
  • programação linear
  • Programação linear

Seja um membro do Trabalhos Feitos

CADASTRE-SE AGORA!