# 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 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 quanto EVA, p. 633 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:
** 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.
** 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.