Simplex

Disponível somente no TrabalhosFeitos
  • Páginas : 12 (2858 palavras )
  • Download(s) : 0
  • Publicado : 30 de maio de 2011
Ler documento completo
Amostra do texto
SIMPLEX ANÁLISE COMPLETA
ANDERSON BESTETTI1, EDUARDO RIGHES1, EVERTON FONTOURA2, GUILHERME LAZZARI3, RODRIGO SCHRAMM3, ROGERIO MARTINS4
1

{anderson.bestetti,eduardo.righes}@terra.com.br 2 everton@bage.unisinos.br 3 {guila,schramm}@exatas.unisinos.br 4 rsmm@netu.unisinos.br

UNIVERSIDADE DO VALE DO RIO DOS SINOS - UNISINOS CENTRO DE CIENCIAS E TECNOLOGICAS PROGRAMAÇÃO EM PESQUISAOPERACIONAL PROFESSOR: ARTHUR TORGO GOMEZ

Resumo Neste artigo apresentamos o algoritmo Simplex para resolução de problemas de programação linear. Este algoritmo encontra a solução ótima e não possui a limitação de duas variáveis, que era o caso da resolução gráfica. Fazemos uma análise completa abordando problemas triviais com exemplos. Por fim segue uma análise de alguns casos especiais consideradospelos autores quanto ao Simplex.

1. SOLUÇÃO EXATA PARA OS MODELOS DE PROGRAMAÇÃO LINEAR
O modelo de programação linear (PL) reduz um sistema real a um conjunto de equações ou inequações onde pretendemos otimizar uma função objetivo. Este conjunto deverá ser, em principio, um conjunto indeterminado, de forma que o número das soluções ditas viáveis e infinito. Apesar de a solução ótima estar em umponto extremo do conjunto de soluções viáveis, muitas vezes existem muitos extremos ou vértices, em numero exponencial. Como obter soluções viáveis básicas do sistema de equações Como evitar o teste de todas as soluções viáveis básicas possíveis para garantir a otimização do sistema
   

Nesse contexto que o algoritmo simplex se encaixa. Uma das grandes contribuições à programação matemática, osimplex e um algoritmo geral extremamente eficiente para a solução de sistemas lineares e adaptáveis ao calculo computacional. O Simplex e um algoritmo que se utiliza um ferramental baseado na Álgebra Linear para determinar, por um método iterativo, a solução ótima de um problema de PL. O algoritmo parte de uma solução viável do sistema de equações que constituem as restrições do problema,solução essa normalmente extrema (vértice).

A partir dessa solução inicial vai identificando novas soluções viáveis de valor igual ou melhor que a corrente. Tem assim um critério de escolha, que permite encontrar sempre novos e melhores vértices da envoltória convexa do problema, e um outro critério que consegue determinar se o vértice escolhido e ou não um vértice ótimo. Teorema: O conjunto C dassoluções de um problema de PL e um conjunto convexo.

2. O ALGORITMO PRIMAL SIMPLEX
O algoritmo descreve uma seqüência de passos para a solução de sistemas de equações lineares sujeitos a uma função objetivo. Dispõe de três situações a principio: O método de inversão da matriz básica m x m deduzida a partir de A, uma matriz de restrições m x n. As regras de troca de variáveis dentro da matrizbásica, para que exista garantia de uma continua melhoria da solução ao longo do desenvolvimento dos passos do algoritmo. As regras de parada do algoritmo e a interpretação dessa situação final.
     

O método sugerido na literatura para a resolução do primeiro aspecto e usar operações elementares. Permite-se com o uso dessa técnica que o esforço de inversão já gasto anteriormente seja aproveitadoa cada passo do algoritmo. O segundo critério aborda a escolha da variável com maior contribuição imediata, que varia conforme o caso (maximização ou minimização). O terceiro critério abrange o teste de parada que inclui a identificação das condições em que não existe mais a possibilidade de que uma troca de variáveis na base possa melhorar o critério de otimização. Para problemas simples de PL(duas variáveis) a resposta pode ser obtida através de resolução gráfica, onde teríamos no eixo no eixo das abscissas a variável x1 e no eixo das ordenadas x2, por exemplo. Traçam-se as restrições e a função objetivo e pode-se concluir a solução do problema. Infelizmente, os problemas de PL na maioria das vezes possuem mais do que duas variáveis. Uma forma de encontrar eficiente o ponto extremo...
tracking img