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 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 , e t c {\displaystyle x_{1},x_{2},etc} , e a função objetivo apresenta-se como a 1 x 1 + a 2 x 2 + e t c {\displaystyle a_{1}x_{1}+a_{2}x_{2}+etc} , sendo a 1 , a 2 , e t c {\displaystyle 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.
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.
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.
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 ( n m 4 ) {\displaystyle O(nm^{4})} , em termos de n {\displaystyle n} variáveis e m {\displaystyle 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 ( m n ) {\displaystyle 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 m ) {\displaystyle m+n \choose m} , o que leva a complexidade final à exponencial em n {\displaystyle 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.
Estes procedimentos são válidos para problemas de maximização:
