Trabalho sobre método simplex

TRABALHO SOBRE MÉTODO SIMPLEX

O método Simplex é um algoritmo que permite resolver problemas de Programação Linear. É um procedimento matricial para resolver o modelo de programação linear na forma normal. A ideia básica do método Simplex consiste em resolver repetidas vezes um sistema de equações lineares para obter uma sucessão de SBA, cada uma "melhor" do que a anterior, até se chegar a uma SBA óptima. Esse método caminha pelos vértices da região viável até encontrar uma solução que não possua soluções vizinhas melhores que ela. A solução ótima pode não existir em dois casos: quando não há nenhuma solução viável para o problema, devido a restrições incompatíveis; ou quando não há máximo (ou mínimo), isto é, uma ou mais variáveis podem tender a infinito e as restrições continuarem sendo satisfeitas, o que fornece um valor sem limites para a função objetivo.
Para Problemas de Programação Linear, na forma padrão encontramos as seguintes características para o sistema linear de equações: Todas as variáveis são não-negativas; Todos os bi’ são não-negativos; Todas as equações iniciais do sistema são do tipo “ £ “. Assim, na forma padrão, só encontra-se variáveis de folga.
Se uma das características da forma padrão não ocorrer, casos especiais do método devem ser considerados, como: Empate na entrada (Quando houver empate na escolha da variável que entra na base, deve se tomar a decisão arbitrariamente. A única implicação envolvida é que pode se escolher um caminho mais longo ou mais curto para se chegar à solução ótima); Empate na saída (Poderá ocorrer que durante a escolha de uma variável para sair da base, temos, empate, isto é, duas ou mais variáveis se anulam com o crescimento da variável que está entrando na base. Neste caso ocorre o que chamamos de degeneração (temos uma solução básica factível degenerada). A escolha também é arbitrária (uma das variáveis básicas assume valor zero).Temos, então, que a mesma solução é obtida através de bases diferentes.