Simplex

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 [e-mail] 3 {guila,schramm}@exatas.unisinos.br 4 [e-mail]

UNIVERSIDADE DO VALE DO RIO DOS SINOS - UNISINOS CENTRO DE CIENCIAS E TECNOLOGICAS PROGRAMAÇÃO EM PESQUISA OPERACIONAL 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 considerados pelos 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 um ponto 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, o simplex 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,