PHPSimplex

Otimizar os recursos com Programação Linear



Exemplo (parte 1): método Simplex

Solução através do método Simplex do Problema seguinte:

Maximizar Z = f(x,y) = 3x + 2y
sujeita às restrições: 2x + y ≤ 18
  2x + 3y ≤ 42
  3x + y ≤ 24
  x ≥ 0 , y ≥ 0

Consideram-se as seguintes fases:

  1. Realizar uma mudança de variáveis e normalizar o sinal dos termos independentes.

    Realiza-se uma mudança na nomenclatura das variáveis. Estabelecendo a seguinte correspondência:

    • x passa a ser X1
    • y passa a ser X2

    Como os termos independentes de todas as restrições são positivos não é necessário fazer nada. Caso contrário, se deverá multiplicar por "-1" ambos os lados da inequação (considerando que esta operação também afeta o tipo de restrição).

  2. Normalizar as restrições.

    As inequações são transformadas em equação adicionando variáveis de folga, de excesso e artificiais, conforme a tabela a seguir:

    Tipo de desigualdade Tipo de variável que aparece
    - excesso + artificial
    = + artificial
    + folga

    Neste caso, deve-se introduzir uma variável de folga (X3, X4 e X5) em cada uma das restrições do tipo ≤, para convertê-las em igualdades, resultando o sistema de equações lineares:

    2·X1 + X2 + X3 = 18
    2·X1 + 3·X2 + X4 = 42
    3·X1 + X2 + X5 = 24
  3. Igualar a função objetivo à zero.
    Z - 3·X1 - 2·X2 - 0·X3 - 0·X4 - 0·X5 = 0
  4. Escrever a tabela inicial do método Simplex.

    A tabela inicial do método Simplex é composta por todos os coeficientes das variáveis de decisão do problema original e as de folga, excesso e artificiais adicionadas no passo 2 (nas colunas, sendo P0 o termo independente e o resto das variáveis Pi coincidem com Xi), e as restrições (das linhas). A coluna Cb contém os coeficientes das variáveis que estão na base.

    A primeira linha é formada pelos coeficientes da função objetivo, enquanto que a última linha contém o valor da função objetivo e os custos reduzidos Zj - Cj.

    A última linha é calculada da seguinte forma: Zj = Σ(Cbi·Pj) para i = 1..m, onde se j = 0, P0 = bi e C0 = 0, e caso contrário Pj = aij. Embora seja a primeira tabela do método Simplex e que todos os Cb sejam nulos, pode-se simplificar o cálculo, e assim termos Zj = -Cj.

    Tabela I . Iteração 1
          3 2 0 0 0
    Base Cb P0 P1 P2 P3 P4 P5
    P3 0 18 2 1 1 0 0
    P4 0 42 2 3 0 1 0
    P5 0 24 3 1 0 0 1
    Z   0 -3 -2 0 0 0

  5. Critério de parada.

    Se o objetivo é maximizar, quando na última linha (linha indicadora) não exista nenhum valor negativo entre os custos reduzidos (colunas P1 em diante) a condição de parada é alcançada.

    Neste caso, o algoritmo chega ao final, porque já não existe possibilidade de melhoria. O valor de Z (coluna P0) é a solução ótima do problema.

    Outra possibilidade é que na coluna da variável de entrada à base, todos os valores são negativos ou nulos. Isto indica que o problema não se encontra delimitado e sua solução sempre poderá ser melhorada. Neste caso, não será necessário continuar realizando iterações indefinidas e pode-se finalizar o algoritmo.

    Caso contrário, as seguintes etapas são executadas de forma iterativa.

  6. Escolha da variável de entrada e saída da base.

    Em primeiro lugar, determina-se a variável que entra na base. Para isto é escolhida a coluna em que o valor da linha Z seja o menor entre todos os negativos. Neste caso seria a variável X1 (P1) de coeficiente -3.

    Se houver dois ou mais coeficientes iguais que satisfazem a condição anterior (caso de empate), então se optará pela variável que seja básica.

    A coluna da variável que entra na base chama-se coluna pivô (na cor verde).

    Depois de obter-se a variável que entra na base, determina-se qual será a variável que sairá da mesma. A decisão é baseada em um cálculo simples: dividir cada termo independente (coluna P0) entre o elemento correspondente da coluna pivô, desde que ambos elementos sejam estritamente positivos (maior que zero). É escolhida a linha cujo resultado é mínimo.

    Se houver algum elemento menor ou igual a zero não se realiza tal cálculo. Caso todos os elementos da coluna pivô tenham esta condição, o critério de parada seria satisfeito e o problema teria uma solução não delimitada (ver teoria do método Simplex).

    Neste exemplo: 18/2 [=9] , 42/2 [=21] y 24/3 [=8]

    O termo da coluna pivô que na divisão anterior deu lugar ao menor quociente positivo, indica a linha de variável de folga que sai da base. Neste caso, resulta ser X5 (P5), de coeficiente 3. Esta linha chama-se linha pivô (na cor verde).

    Se ao realizar o cálculo dos quocientes, dois ou mais resultados satisfaçam o critério para a escolha do elemento de saída da base (caso de empate), é escolhida a variável não-básica (sempre que possível).

    A intersecção da linha pivô e coluna pivô marca o elemento pivô, neste caso o 3.

  7. Atualizar a tabela.

    Os novo valores da tabela devem ser calculados como é explicado a seguir:

    • Na linha do elemento pivô cada novo elemento é calculado como:
      Novo Elemento Linha Pivô = Elemento Anterior Linha Pivô / Pivô
    • Nas demais linhas, cada elemento é calculado como:
      Novo Elemento Linha = Elemento Anterior Linha - (Elemento Anterior Linha na Coluna Pivô * Novo Elemento Linha Pivô)

    Com isto se normaliza o elemento pivô e seu valor torna-se 1, enquanto que os demais elementos da coluna pivô são anulados (análogo ao método de Gauss-Jordan).

    A seguir, mostra-se os cálculos da linha P4:

    Anterior Linha P4 42 2 3 0 1 0
      - - - - - -
    Elemento Anterior Linha na Coluna Pivô 2 2 2 2 2 2
      x x x x x x
    Nova Linha Pivô 8 1 1/3 0 0 1/3
      = = = = = =
    Nova Linha P4 26 0 7/3 0 1 -2/3

    A tabela correspondente a esta segunda iteração é:

    Tabela II . Iteração 2
          3 2 0 0 0
    Base Cb P0 P1 P2 P3 P4 P5
    P3 0 2 0 1/3 1 0 -2/3
    P4 0 26 0 7/3 0 1 -2/3
    P1 3 8 1 1/3 0 0 1/3
    Z   24 0 -1 0 0 1
  8. Ao verificar o critério de parada observado não é cumprido, já que entre os elementos da última linha há o valor de um negativo, -1. Neste caso, novamente realiza-se a iteração nos passos 6 e 7.
    • 6.1. A variável que entra na base é X2 (P2), pois é a variável que corresponde à coluna em que se encontra o coeficiente -1.
    • 6.2. Para calcular a variável de saída, dividem-se os termos da coluna P0 entre os termos correspondentes da nova coluna pivô: 2 / 1/3 [=6] , 26 / 7/3 [=78/7] e 8 / 1/3 [=24]. Como o menor quociente positivo é 6, a variável que sai da base é X3 (P3).
    • 6.3. O elemento pivô é 1/3.
    • 7. Atualizando novamente os valores da tabela se obtém:

      Tabela III . Iteração 3
            3 2 0 0 0
      Base Cb P0 P1 P2 P3 P4 P5
      P2 2 6 0 1 3 0 -2
      P4 0 12 0 0 -7 1 4
      P1 3 6 1 0 -1 0 1
      Z   30 0 0 3 0 -1
  9. Uma nova verificação do critério de parada revela que entre os elementos da linha indicadora, novamente temos um negativo, -1. Significa que ainda não se chegou à solução ótima e é preciso continuar iterando (passos 6 e 7):
    • 6.1. A variável que entra na base é X5 (P5), pois é a variável que corresponde ao coeficiente -1.
    • 6.2. A variável de saída é escolhida realizando o cálculo do quociente dos termos da coluna de termos independentes e os termos correspondentes da nova coluna pivô: 6/(-2) [=-3] , 12/4 [=3], e 6/1 [=6]. Nesta ocasião é X4 (P4).
    • 6.3. O elemento pivô é 4.
    • 7. Depois de atualizar todas as linhas, tem-se a seguinte tabela:

      Tabela IV . Iteração 4
            3 2 0 0 0
      Base Cb P0 P1 P2 P3 P4 P5
      P2 2 12 0 1 -1/2 1/2 0
      P5 0 3 0 0 -7/4 1/4 1
      P1 3 3 1 0 3/4 -1/4 0
      Z   33 0 0 5/4 1/4 0
  10. Fim do algoritmo.

    Observa-se que na última linha, todos os coeficientes são positivos, satisfazendo assim o critério de parada.

    A solução ótima é dada pelo valor de Z na coluna dos termos independentes (P0), neste exemplo: 33. Na mesma coluna, pode-se ver o ponto em que é atingido, observando as linhas correspondentes das variáveis de decisão que entraram na base: X1 = 3 e X2 = 12.

    Desfazendo a mudança de variáveis é obtido x = 3 e y = 12.

Resolver com PHPSimplex.

Copyright ©2006-2017 PHPSimplex. Todos os direitos reservados. Termos e condições.
Siga-nos no Twitter
X

PHPSimplex
Versão 0.81

Copyright ©2006-2017. Todos os direitos reservados.

Desenvolvido por:
Daniel Izquierdo Granja
Juan José Ruiz Ruiz

Tradução para o Inglês por:
Luciano Miguel Tobaria

Tradução para o Francês por:
Ester Rute Ruiz

Tradução para o Português por:
Rosane Bujes