O Metodo Simplex

3 - DESENVOLVIMENTO DO METODO SIMPLEX

        O método SIMPLEX de resolução de problemas de programação linear foi desenvolvido e aperfeiçoado pelo matemático norte-americano George Dantzig. Por seu trabalho, que foi publicado no ano de 1947 e apresentou à comunidade matemática mundial o algoritmo do SIMPLEX. Dantzig ficou conhecido como o pai da programação linear.

A palavra SIMPLEX é usualmente empregada na Topologia (ramo da matemática que estuda a convergência, a convexidade e a continuidade). Ela é generalização do conceito de triângulos e outras dimensões (uma dimensão é dada pelo seu espaço e o número de pontos que o determinam).

Matematicamente, o termo SIMPLEX pode ser definido como a região contida em Rm resultante da intersecção de semiespaços de n+1 vértices em N dimensões. Isso significa um segmento de linha sobre uma linha, um triângulo sobre um plano, um tetraedro em um espaço tridimensional, e assim por diante.  

Quanto ao seu nome, o SIMPLEX é assim chamado por representar sempre o polígono mais simples de sua dimensão. Por exemplo, em R2, o triângulo é o polígono com menor número de vértices e de arestas. Em R3, o tetraedro é o polígono que possui o menor número de vértices, arestas e faces.

 Desse modo, constatamos que Dantzig, valendo-se de toda a sua genialidade matemática, usou as propriedades topológicas dos polígonos do tipo SIMPLEX para desenvolver um método capaz de solucionar problemas de programação linear.

O método desenvolvido por Dantzig tornou-se tão conhecido que, quando se fala em SIMPLEX, as pessoas costumam associar o nome ao algoritmo de resolução de problemas de programação linear, e não mais à teoria matemática do ramo da Topologia que o originou.

O Método Simplex

O método SIMPLEX determina a solução ótima de um problema de programação linear e, em certas circunstâncias, permite concluir que o problema tem múltiplas soluções, é inviável ou ilimitado.

De modo geral, o SIMPLEX busca, a partir de uma primeira solução básica viável, percorrer de forma iterativa os vértices de um polígono até alcançar uma solução considerada ótima para o problema.

Na prática, a utilização do SIMPLEX se dá mediante uma sequência de etapas que se inicia com a redução do sistema linear à forma canônica, passa pela construção do quadro SIMPLEX, pela determinação da solução básica inicial, pela escolha das variáveis que entram e das variáveis que saem da base, pelo cálculo da nova solução básica e pelo teste dessa nova solução.

Embora nosso objetivo seja trabalhar com um sistema de equações, a maioria dos problemas não é formada apenas por equações. Em geral, as restrições são inequações.

Para poder resolver um modelo de programação linear via SIMPLEX, temos que reduzir seu sistema algébrico à forma canônica. Isso significa adequar o modelo de programação linear à “linguagem” utilizada pelo SIMPLEX.

A forma canônica de um modelo de programação linear é dada na forma:

Maximizar Z = c1x1 + c2x2 +..........+cnxn

Sujeito à        

                a11x1 + a12x2 +.........+a1nxn = b1

                a21x1 + a22x2 +.........+a2nxn = b2

                a31x1 + a32x2 +.........+a3nxn = b3

........................................................................................

                am1x1 + am2x2 +.........+amnxn = bm

com

                x1 ≥ 0, x2 ≥ 0,.....,xn ≥ 0

onde:

cj = contribuição unitária atribuída à variável xj.

aij = coeficiente de xj na restrição i;

bi = valor limite da restrição i;

i = 1, 2, 3,...., m; e

j = 1, 2, 3,....,n.