PHPSimplex

Otimizar os recursos com Programação Linear



Teoria do método Simplex

Preparando o modelo para adaptá-lo ao método Simplex
Tipo de Otimização
Mudança de sinal dos termos independentes
Padronização das restrições
Desenvolvendo o método Simplex
Método Simplex
Método das Duas Fases
Identificando casos anômalos e soluções
Método Gráfico
Exemplo do método Simplex
Ejemplo do método Gráfico
Comparação do método Gráfico com o método Simplex

 

O método Simplex é um processo iterativo que permite melhorar a solução da função objetivo em cada etapa. O processo finaliza quando não é possível continuar melhorando este valor, ou seja, quando se obtenha a solução ótima (o maior ou menor valor possível, segundo o caso, para que todas as restrições sejam satisfeitas).

Com base no valor da função objetivo, em um ponto qualquer, o procedimento consiste em procurar outro ponto que melhore o valor anterior. Como se pode ver no método Gráfico, tais pontos são os vértices do polígono (ou poliedro ou polícoro, se o número de variáveis é maior do que 2) e que faz parte da região determinada pelas restrições a que está sujeito o problema (chamada de região viável). A pesquisa é realizada por meio de deslocamentos pelas arestas do polígono, a partir do vértice atual até um adjacente que melhore o valor da função objetivo. Sempre que exista região viável, e como seu número de vértices e de arestas é finito, será possível encontrar a solução.

O método Simplex baseia-se na seguinte propriedade: se a função objetivo Z não toma seu valor máximo no vértice A, quer dizer que existe uma aresta que parte de A e ao longo da qual o valor de Z aumenta.

Será necessário considerar que o método Simplex trabalha apenas com restrições do problema cujas desigualdades sejam do tipo "≤" (menor ou igual) e seus coeficientes independentes sejam maiores ou iguais a 0. Portanto, é preciso padronizar as restrições para atender aos requisitos antes de iniciar o algoritmo Simplex. Caso apareçam, depois deste processo, restrições do tipo "≥" (maior ou igual) ou "=" (igualdade), ou não seja possível alterá-las, será necessário utilizar outros métodos de resolução, sendo o mais comum, o método das Duas Fases.

Preparando o modelo para adaptá-lo ao método Simplex

A forma padrão do modelo de problema consiste em uma função objetivo, sujeita a certos critérios (as restrições):

Função objetivo: c1·x1 + c2·x2 + ... + cn·xn
sujeita às restrições: a11·x1 + a12·x2 + ... + a1n·xn = b1
a21·x1 + a22·x2 + ... + a2n·xn = b2
...
am1·x1 + am2·x2 + ... + amn·xn = bm
x1,..., xn ≥ 0

O modelo deve atender às seguintes condições:

  1. O objetivo é maximizar ou minimizar o valor da função objetivo (por exemplo, aumentar lucros ou reduzir as perdas, respectivamente).
  2. Todas as restrições devem ser equações de igualdade (identidades matemáticas).
  3. Todas as variáveis (xi) devem ser positivas ou nulas (condição de não-negatividade).
  4. Os termos independentes (bi) de cada equação devem ser não-negativos.

HÉ preciso adaptar o problema de modelagem de acordo à forma padrão para poder aplicar o algoritmo Simplex.

Tipo de Otimização.

Como mencionado, o objetivo do método é otimizar o valor da função objetivo. No entanto, duas opções são apresentadas: obter o maior valor ótimo (maximizar) ou obter o menor valor ótimo (minimizar).

Além disto, existem diferenças no algoritmo entre o objetivo de maximização e de minimização quanto ao critério de parada para finalizar as iterações e as condições de entrada e saída da base. Assim:

No entanto, é possível normalizar o objetivo do problema, a fim de aplicar sempre os mesmos critérios sobre o critério de parada do algoritmo e as condições de entrada e saída nas variáveis da base. Assim, se o objetivo é minimizar a solução pode-se mudar o problema para outro equivalente de maximização, apenas multiplicando a função objetivo por "-1". Ou seja, o problema de minimizar Z é equivalente ao problema de maximizar (-1)·Z. Uma vez obtida a solução, será preciso multiplicar por (-1).

Vantagens: Não será preciso se preocupar com novos critérios de parada, condição de entrada e de saída da base, já que são mantidos.

Desvantagens: No caso em que a função tenha todos os coeficientes de suas variáveis básicas positivas e, adicionalmente, as restrições sejam do tipo de desigualdade "≤", ao fazer a mudança, tais coeficientes ficam negativos cumprindo assim a condição de parada na primeira iteração (na linha de valor da função objetivo todos os valores são positivos ou zero). Neste caso, obtém-se por padrão um valor ótimo para a função igual a 0.

Solução: Não existe este problema, dado que para que a solução seja superior a 0 é necessário que alguma restrição tenha imposto a condição "≥" (que seria um modelo para o método das Duas Fases). No caso mencionado, a solução real deve ser zero.

Mudança de sinal dos termos independentes

Também foi dito que os termos independentes (bi) de cada equação devem ser não negativos para que seja possível usar o método Simplex. Para esse efeito, se alguma das restrições apresenta um termo independente menor que 0, será preciso multiplicar por "-1" ambos os lados da inequação (considerando que esta operação também afeta o tipo de restrição).

Vantagens: Com esta simples modificação de sinais nas restrições correspondentes, torna-se possível a aplicação do método Simplex no problema de modelagem.

Desvantagens: Pode ser que as restrições nas quais teremos que modificar os sinais das constantes, os tipos de desigualdade são "≤" (tornando a operação do tipo "≥"), sendo necessário desenvolver o método das Duas Fases. Esta desvantagem não é controlável, ainda que poderia ocorrer o caso contrário e ser benéfico, se os termos independentes negativos são apresentados em todas as restrições com desigualdade do tipo "≥". Caso exista alguma restrição do tipo "=" não significa nenhuma vantagem ou desvantagem, uma vez que seria aplicado de qualquer forma o método das Duas Fases.

Padronização das restrições

Outra condição do modelo padrão do problema é que todas as restrições sejam equações de igualdade (também chamada de restrições de igualdade), por isso é necessário converter as restrições de desigualdade ou inequações em tais identidades matemáticas.

A condição de não negatividade das variáveis (x1,..., xn ≥ 0) é a única exceção e se mantém inalterada.

No último caso, é evidente que as variáveis artificiais representam uma violação das leis da álgebra, de modo que será necessário garantir que as variáveis artificiais tenham um valor 0 na solução final. Esta é a responsabilidade do método das Duas Fases e por isso, sempre que apareça este tipo de variável, se deverá realizar este procedimento.

A tabela a seguir resume a desigualdade, o tipo de variável que aparece na equação padrão, assim como seu sinal:

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

Desenvolvendo o método Simplex

Uma vez padronizado o modelo pode acontecer que seja necessário aplicar o método Simplex ou o método das Duas Fases. Observe na figura os procedimentos para alcançar a solução do problema de modelagem.

Algoritmo do Simplex

A seguir, explica-se passo a passo os pontos de cada método, especificando os aspectos a considerar.

Método Simplex
Método das Duas Fases

O método das Duas Fase é utilizado quando aparecem variáveis artificiais na forma canônica ou padrão do problema. A primeira fase consiste em resolver o problema Z auxiliar para minimizar a soma das variáveis artificiais visando obter o valor de zero (para evitar inconsistências matemáticas). Depois de resolver este primeiro problema, e contanto que o resultado seja o esperado, a tabela resultante é reorganizada para utilizá-la na segunda fase do problema original.

Caso contrário, o problema não é factível, ou seja, não tem solução e não será necessário continuar com a segunda fase.

FASE 1

A primeira fase é muito similar ao método Simplex, com a exceção da construção da primeira tabela, além de ser necessário estudar o resultado obtido para determinar se a segunda fase será desenvolvida.

Neste caso, a última tabela desta fase será, com algumas modificações, utilizada como tabela inicial para a segunda fase.

FASE 2

A segunda fase do método das Duas Fases é desenvolvida exatamente como no método Simplex, com a exceção de que antes de iniciar as iterações deve-se eliminar as colunas que correspondem às variáveis artificiais, e reconstruir a tabela inicial.

A partir deste ponto, todas as iterações até alcançar a solução ótima do problema não apresentam nenhuma diferença do método Simplex.

Identificando casos anômalos e soluções

Solução ótima: quando o critério de parada é satisfeito e não existam variáveis artificiais na base com valor positivo (os valores são indicados na coluna P0), a otimização foi alcançada. O valor Z0 atual é a solução ótima do problema, cumprindo para as variáveis que estão na base. Caso trate-se de um problema de minimização, o valor ótimo obtido deverá ser multiplicado por "-1".

Soluções infinitas: satisfeito o critério de parada, se alguma variável de decisão não-básica tem um valor 0 na fila Z, significa que existe outra solução que fornece o mesmo valor ótimo para a função objetivo. Neste caso, o problema admite infinitas soluções, todas as quais abrangidas dentro do segmento (ou parte do plano, região de espaço, etc., conforme o número de variáveis do problema) definido por A·X1 + B·X2 = Z0. Através de uma nova iteração e fazendo com que a variável de decisão que tenha 0 na linha Z entre na base, é obtida uma solução diferente para o mesmo valor ótimo.

Solução ilimitada (unbounded): se toda coluna da variável que entra na base tem todos os seus elementos negativos ou nulos, trata-se de um problema não-limitado, ou seja, que tem solução ilimitada. Não há valor ótimo concreto para a função objetivo, mas à medida que os valores das variáveis são aumentados, o valor Z também aumenta sem violar qualquer restrição.

Não existe solução: quando nenhum ponto satisfaz às restrições do problema, ocorre a inviabilidade, não existindo nenhuma solução possível para ele. Neste caso, uma vez terminadas todas as iterações do algoritmo, existem na base variáveis artificiais em que o valor é superior a zero.

Empate de variável de entrada: quando ocorre um empate na escolha da variável entrante, pode-se optar por qualquer uma delas sem que isto afete a solução final. Por outro lado, se ela influencia o número de iterações necessárias para obter a solução. É aconselhável optar pelas variáveis básicas, já que elas são as que farão parte da solução ótima.

Empate de variável de saída: novamente é possível optar por qualquer uma delas. No entanto, a fim de não ampliar o problema e evitar que a entrada fique em um ciclo infinito (caso degenerado), discrimina-se a favor das variáveis de decisão fazendo que permaneçam na base. No caso de ser a primeira fase do método das Duas Fases, se optará por retirar da base as variáveis artificiais.

Curiosidade na fase 1: ao finalizar a fase 1, caso o problema original tenha solução, todas as variáveis artificiais na linha indicadora devem ter o valor "1".

O elemento pivô pode ser nulo?: Não, o elemento pivô sempre será estritamente positivo já que apenas realizam-se os quocientes entre os valores não-negativos e maiores que zero (em um problema de maximização).

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