Programação Linear: Método Simplex

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 x1, x2, etc e a função objetivo apresenta-se como a1x1+a2x2+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.

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.