Algoritmo simplex

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa


Algoritmo Simplex[editar | editar código-fonte]

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 [1] está disponível no Github.

Uma visão geral[editar | editar código-fonte]

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_1x_1 + a_2x_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 fato de uma empresa só conseguir armazenar um determinado peso ou quantidade dos produtos, por exemplo. Dentre 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[editar | editar código-fonte]

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[editar | editar código-fonte]

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[editar | editar código-fonte]

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[editar | editar código-fonte]

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[editar | editar código-fonte]

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[editar | editar código-fonte]

Formalmente, a complexidade do algoritmo Simplex é tida como exponencial. [Papadimitriou, p. 233] [2] 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[2] quanto [EVA, p. 633] [3] 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[editar | editar código-fonte]

Estes procedimentos são válidos para problemas de maximização:

  1. Introduzir as variáveis de folga, uma para cada desigualdade;
  2. 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;
  3. 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;
  4. 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.
  5. Para escolher a variável que deve deixar a base, deve-se realizar o seguinte procedimento:
    1. 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.
    2. O menor quociente indica a equação cuja respectiva variável básica deverá ser anulada, tornando-se variável não básica.
  6. 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.
  7. Retornar ao passo 4 para iniciar outra iteração.

Referências

  1. Implementação do Simplex como programação linear em Python. Github
  2. a b Algorithms, S. Daguspta, C. H. Papadimitriou e U. V. Vazirani, 2006.
  3. Algorithm Design, Jon Kleinberg, Éva Tardos, 1st ed., 2006, ISBN 0-321-29535-8.

Links externos[editar | editar código-fonte]