O que é o 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 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.

​

Método Algébrico

​

• Fase I:

  –Determine inicialmente a partição básica factível A=[B N]. A rigor, precisamos de dois vetores de índices básicos e não-básicos:

    (B1, B2, ..., Bm) e (N1, N2, ..., Nn-m)

  –Os vetores das variáveis básicas e não-básicas são, respectivamente:

    xTB=(xB1, xB2, ..., xBm) e xTN= (xN1, xN2, ..., xNn-m)

  –Faça iteração=1

​

• Fase II: {início da iteração simplex}

​

  –Passo 1: {cálculo da solução básica}

   x*B=B-1b //ou, equivalentemente, resolve o sistema BxB=b

   x*N=0

​

  –Passo 2: {cálculo dos custos relativos}

      2.1) {vetor multiplicador simplex}

             –λT= cTBB-1

      2.2) {custos relativos}

             –c*NJ=cNJ-λTaNJ j=1,2, ..., n-m

      2.3) {determinação da variável a entrar na base}

             –c*Nk=minimo(c*NJ, j=1,2, ..., n-m) //a variável xNk entra na base

​

  –Passo 3: {teste da otimalidade}

     •Se c*Nk>=0, então: pare //solução na iteração atual é ótima

​

  –Passo 4: {cálculo da direção simplex}   

      •y=B-1aNk

​

  –Passo 5: {determinação do passo e variável a sair da base}

     •Se y<=0, então: pare //problema não tem solução ótima finita. f(x)-> -∞

     •Caso contrário, determine a variável a sair da base pela razão mínima

     –ε*=x*Bl/yl =minimo(x*Bi/yi tal que yi>0) //a variável xBl sai da base

​

  –Passo 6: {atualização: nova partição básica, troque a l-ésima coluna de B pela k-ésima coluna de N}

      •Matriz básica nova: B=[aB1...aBl-1 aNk aBl+1 ... aBm]

      •Matriz não-básica nova: N=[aN1...aNk-1 aBl aNk+1 ... aNn-m]

      •iteração=iteração+1

      •Retorne ao passo 1

​

​

Método Gráfico

​

Para solucionar pelo método gráfico é necessário que x1 e x2 sejam >= 0, o ponto ótimo, ou seja o ponto que maximiza o valor de Z, obedecidas todas as restrições, só pode estar no 1º quadrante. Vamos representar a primeira restrição com 70x1 + 70x2 = 4900, ela passa pelos pontos (70,0) e (0,70), e a segunda restrição é 90x1 + 50x2 = 4500 no quais seus respectivos pontos são (50,0) e (0,90). Traçando-as temos:

​

​

​

​

​

​

​

​

​

​

​

A partir disso temos a 3º restrição 2x1 = 80, e a 4º que tem como igualdade 3x2 = 180, veja abaixo como ficou:

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

Como todas as restrições foram traçadas temos o chamado Espaço Solução que é o conjunto de todos os pontos candidatos a serem o ponto ótimo, ou seja, todos os pontos que “obedecem” a todas as restrições do modelo. 

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​