Algoritmo simplex
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 algoritmo pode ser implementado de várias maneiras diferentes, mas o princípio é basicamente o mesmo. Abaixo, há a abordagem utilizada por [Papadmitriou]. Ao fim do texto, pode-se conferir uma implementação na linguagem de programação Python está disponível no Github.
Uma 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}, 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.
