Simplex é um algoritmo criado por 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 x1 , x2 , etc, e a função objetivo apresenta-se como a1 x1 + a2 x2 + etc, sendo a1, a2, 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.
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.
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.
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.
Estes procedimentos são válidos para problemas de maximização: