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:
- 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).
- 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 - Igualar a função objetivo à zero.
Z - 3·X1 - 2·X2 - 0·X3 - 0·X4 - 0·X5 = 0
- 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
- 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.
- 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.
- 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 - Na linha do elemento pivô cada novo elemento é calculado como:
- 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
- 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
- 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.
