Algorítmo Simplex

SUMÁRIO

1 MÉTODO SIMPLEX 1

1.1 OS PASSOS DO MÉTODO SIMPLEX 2

2. ALGORÍTMO SIMPLEX 3

2.1 UMA VISÃO GERAL 3

2.2 FUNCIONAMENTO 4

2.3 MINIMIZAÇÃO 5

2.4 TABLEAU 5

2.5 MATRIZES 5

2.6 NO ESPAÇO N DIMENSIONAL 6

REFERÊNCIAS BIBLIOGRÁFICAS 6

1 Método Simplex

O Método Simplex é uma técnica utilizada para se determinar, numericamente, a solução ótima de um modelo de Programação Linear. Será desenvolvido inicialmente para Problemas de Programação Linear, na forma padrão, mas com 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.

1.1 Os Passos do Método Simplex

Os passos abordados a seguir referem-se a um P.P.L. de minimização.

Para iniciarmos o Método Simplex necessita-se de uma solução básica viável inicial, a qual é, um dos pontos extremos. Este método verifica se a presente solução é ótima. Se esta não for é porque um dos demais pontos extremos adjacentes (vértice) fornecem valor menor para a função objetivo que a atual, quando o problema considerado é de minimização. Ele então faz uma mudança de vértice na direção que mais diminua a função objetivo e verifica se este novo vértice é ótimo.

O processo termina quando estando num ponto extremo, todos os outros pontos extremos adjacentes fornecem valores maiores para a função objetivo. Portanto, a troca de vértice, faz uma variável não básica crescer (assumir valor positivo) ao mesmo tempo em que zera uma variável básica (para possibilitar a troca) conservando a actibilidade do Problema de Programação Linear.

Para isso, escolhemos uma variável, cujo custo relativo é mais negativo (não é regra geral), para entrar na base, e as trocas de vértices são feitas até que não exista mais nenhum custo relativo negativo. A variável que sairá da base é aquela que ao se anular garante que as demais continuem maiores ou iguais a zero, quando aumentamos o valor da variável que entra na base (respeitando a factibilidade).

O Método Simplex compreenderá, portanto, os seguintes passos:

I. Achar uma solução factível básica inicial;

II. Verificar se a solução atual é ótima. Se for, pare. Caso contrário, siga para o

III. passo iii).

IV. Determinar a variável não básica que deve entrar na base;

V. Determinar a variável básica que deve sair da base;

VI. Atualizar o sistema à fim de determinar a nova solução factível básica, e

VII. voltar ao passo ii.

2. Algorítmo Simplex

O algoritmo Simplex é a ferramenta básica da programação linear. O objetivo do algoritmo é transformar uma matriz dada em outra equivalente que contenha um certo “desenho” ou “padrão”.

Simplex é um algoritmo criado por George Dantzig, que viabiliza a solução de diversos problemas da programação linear. Sua popularidade, conforme os autores [EVA, p. 633] 1 e [Papadimitriou, p. 233] 2 , deve-se à sua eficiência pois ainda que seja considerado de complexidade exponencial, raros são os casos em que tal complexidade de fato ocorre. O Simplex encontra boa aceitação em áreas onde diversas necessidades e restrições influenciam em um valor que precisa ser aumentado ou diminuído ao máximo.

O algoritmo pode ser implementado de várias maneiras diferentes, mas o princípio é basicamente o mesmo.

2.1 Uma visão geral

Dado um problema, são estabelecidas inequações que definem restrições para as variáveis. A partir daí, são testadas possibilidades de maneira a otimizar o resultado da forma mais rápida possível.

O uso mais comum do Simplex é o de maximizar, ou minimizar, um resultado, ou seja, encontrar o maior valor possível para um total. A praticidade do algoritmo vem justamente quando há a necessidade de se respeitar restrições inerentes à situação apresentada.

Problemas típicos para se resolver com o Simplex são os que buscam encontrar quantidades ideais de produtos a serem comercializados, sempre com restrições referentes ao armazenamento e à fabricação dos mesmos. A ideia é isolar uma função como sendo o objetivo, aquela cujo resultado será determinado pelas variáveis envolvidas. As quantidades que se deseja otimizar são representadas por variáveis aqui chamadas x_1, x_2, etc, e a função objetivo fica a_1*x_1 + a_2*x_2 + … , sendo a_1, a_2, …, os coeficientes das variáveis, demosntram a proporcionalidade entre elas, geralemente números racionais encontrados no problema que se deseja resolver.

As restrições são apresentadas como inequações. Indicam peculiaridades como o fato de uma empresa só conseguir armazenar um determinado peso ou quantidade dos produtos, por exemplo. Dentre as possibilidades de valores para as variáveis que atendam às restrições, o algoritmo deve encontrar aqueles que deem à função objetivo o maior total possível.

2.2 Funcionamento

Relacionado à programação linear, que trabalha com funções do 1º grau, a ideia do algoritmo é bem simples. Inicialmente, as variáveis são atribuídas com o valor zero. Em seguida, aquela que tem maior interferência positiva no resultado da função objetivo, a que possui o maior coeficiente, é incrementada pouco a pouco. A esta variável damos o