Algoritmo simplex

Simplex é um algoritmo criado pelo matemático George Dantzig que viabiliza a solução de muitos problemas da programação linear. Bastante popular, 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. Abaixo, há a abordagem utilizada por Papadmitriou.

Visão geral

O Simplex permite que se encontre valores ideais em situações em que diversos aspectos precisam ser respeitados. Diante de um problema, são estabelecidas inequações que representam restrições para as variáveis. A partir daí, testa-se possibilidades de maneira a otimizar o resultado da forma mais rápida possível.

O uso mais comum do Simplex é para se maximizar um resultado, ou seja, encontrar o maior valor possível para um total. Problemas típicos para se resolver com o Simplex são os que buscam quantidades ideais de produtos a serem comercializados, com restrições referentes ao armazenamento e à fabricação dos mesmos. A ideia é isolar uma função como sendo o objetivo. As quantidades que se deseja otimizar são representadas por variáveis aqui chamadas de $x_{1},x_{2},etc$ , e a função objetivo apresenta-se como $a_{1}x_{1}+a_{2}x_{2}+etc$ , sendo $a_{1},a_{2},etc$ os coeficientes das variáveis. Estes demonstram a proporcionalidade entre elas. Geralmente são números racionais obtidos no problema que se deseja resolver.

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

Funcionamento

Relacionado à programação linear, que trabalha com funções do 1º grau, a ideia do algoritmo é bem simples. Inicialmente, atribui-se valor zero às variáveis, que seria distante da solução. Em seguida, incrementa-se pouco a pouco a variável que tem maior interferência positiva no resultado da função objetivo, ou seja, a que possui o maior coeficiente. Esta é chamada de "variável ativa" e tem grande importância inicial pois é a mais “lucrativa” delas, ou seja, a que mais nos aproxima da otimização.

Conforme este valor aumenta, o algoritmo testa todas as restrições, até que uma delas não seja satisfeita. Esta restrição recebe o nome de "restrição ativa". Neste momento, conhece-se o valor máximo da variável ativa. O procedimento, então, passa para a próxima variável que nos aproxima da boa solução, sempre levando em consideração o máximo valor que a primeira pôde atingir. A cada mudança destas, o Simplex converte todos os coeficientes (inclusive os da função objetivo) de acordo com os limites encontrados nas sucessivas restrições ativas.

O procedimento é repetido até que o incremento das variáveis apresente-se como um decréscimo do total atingido. Isto é identificado com o sinal negativo à frente dos coeficientes da função objetivo. Ao fim, os valores buscados serão conhecidos por meio de um sistema de equações, estas oriundas do problema inicial.

Minimização

Embora os exemplos quase sempre sejam de maximização, o Simplex também soluciona casos em que se deseja encontrar o menor valor possível. Custos e gastos são alguns dos resultados comumente buscados nestas situações.

Para isto, o algoritmo pode ser perfeitamente adaptado de maneira a solucionar um problema onde se deseja encontrar um resultado pequeno. No entanto, o que muitas das vezes se faz é simplesmente inverter todas as relações, multiplicando os coeficientes por –1 e fazendo com que o problema original seja encarado como uma simples maximização.

Tableau

Já implementado em diversas linguagens diferentes, o Simplex também pode ser aplicado manualmente. O método, conhecido como Tableau, consiste em se colocar todas as informações devidamente organizadas em um quadro, fazendo-se exatamente o que um software faria. Em muitos locais, o Simplex é ensinado desta forma, a fim de que as pessoas tenham um bom domínio da técnica de otimização.

Matrizes

O processamento do algoritmo pode ser feito por meio de um produto de matrizes. Uma vez que os coeficientes estejam devidamente dispostos em linhas e colunas, basta que esta seja multiplicada por uma versão modificada da chamada “Matriz Identidade”, com tamanho igual ao número de variáveis. A versão modificada tem uma linha formada pelos simétricos dos coeficientes da linha referente à restrição violada divididos pelo coeficiente da variável que a violou. Esta linha será correspondente, na ordem, à variável que violou a restrição.

Este produto de matrizes faz com que sempre se tenha uma relação dos coeficientes já modificados de acordo com as restrições e os melhores valores possíveis para as variáveis até o momento. O processo é repetido até que se encontre o ótimo resultado, ou seja, quando não mais for possível aprimorar o total sem desrespeitar as restrições.

No espaço N dimensional

Se analisado sob a ótica geométrica, o Simplex trabalha na construção de um polítopo com um número de dimensões igual à quantidade de variáveis do problema. A solução ótima sempre será o conjunto de coordenadas de um dos vértices deste polítopo. A cada incrementação de uma variável, é como se o Simplex percorresse uma das arestas, sempre em busca do vértice perfeito.

Complexidade

Formalmente, a complexidade do algoritmo Simplex é tida como exponencial. Papadimitriou, p. 233 ^[1] mostra que, em uma implementação ingênua, cada iteração em busca da melhor solução tem, a princípio, complexidade $O(nm^{4})$ , em termos de $n$ variáveis e $m$ restrições. Porém, com a abordagem de transformação linear onde a cada iteração todo o sistema é transformado de maneira que o vértice anterior seja a nova origem, a complexidade por iteração torna-se $O(mn)$ . Naturalmente, questiona-se quantas iterações são necessárias até se atingir o critério de parada. Um limite superior para este número é $m+n \choose m$ , o que leva a complexidade final à exponencial em $n$ . Felizmente, tanto Papadimitriou^[1] quanto EVA, p. 633 ^[2] relatam que, na prática, são raros os problemas que tomam esta complexidade e, por isto, o algoritmo Simplex é altamente utilizado.

Algoritmo com um Tableau

Estes procedimentos são válidos para problemas de maximização:

Introduzir as variáveis de folga, uma para cada desigualdade;
Montar um quadro para os cálculos, colocando os coeficientes de todas as variáveis com os respectivos sinais e, na última linha, incluir os coeficientes da função objetivo transformada;
Estabelecer uma solução básica inicial, usualmente atribuindo valor zero às variáveis originais e achando valores positivos para as variáveis de folga;
Como próxima variável a entrar na base, escolher a variável não básica que oferece, na última linha, a maior contribuição para o aumento da função objetivo (ou seja, tem o maior valor negativo). Se todas as variáveis que estão fora da base tiverem coeficientes nulos ou positivos nesta linha, a solução atual é ótima. Se alguma dessas variáveis tiver coeficiente nulo, isto significa que ela pode ser introduzida na base sem aumentar o valor da função objetivo. Isso quer dizer que temos uma solução ótima, com o mesmo valor da função objetivo.
Para escolher a variável que deve deixar a base, deve-se realizar o seguinte procedimento:
1. Dividir os elementos da última coluna pelos correspondentes elementos positivos da coluna da variável que vai entrar na base. Caso não haja elemento nenhum positivo nesta coluna, o processo deve parar, já que a solução seria ilimitada.
2. O menor quociente indica a equação cuja respectiva variável básica deverá ser anulada, tornando-se variável não básica.
Usando operações válidas com as linhas da matriz, transformar o quadro de cálculos de forma a encontrar a nova solução básica. A coluna da nova variável básica deverá se tornar um vetor identidade, onde o elemento 1 aparece na linha correspondente à variável que está sendo anulada.
Retornar ao passo 4 para iniciar outra iteração.

Referências

↑ ^a ^b Algorithms, S. Daguspta, C. H. Papadimitriou e U. V. Vazirani, 2006.
↑ Algorithm Design, Jon Kleinberg, Éva Tardos, 1st ed., 2006, ISBN 0-321-29535-8.

Ligações externas

Metodo Simplex Descrição do método Simplex
Método Simplex das Duas Fases Descrição do método Simplex das Duas Fases
PHPSimplex: ferramenta online para resolver problemas de programação linear por Daniel Izquierdo e Juan José Ruiz da Universidade de Málaga (UMA, Espanha).
Calculadora online para o método Simplex e Duas Fases por Mathstools

[livro_papadimitriou-1] Algorithms, S. Daguspta, C. H. Papadimitriou e U. V. Vazirani, 2006.

[livro_eva-2] Algorithm Design, Jon Kleinberg, Éva Tardos, 1st ed., 2006, ISBN 0-321-29535-8.

[1]

[2]