PHPSimplex

Otimizar os recursos com Programação Linear

Teoria do 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:

O objetivo é maximizar ou minimizar o valor da função objetivo (por exemplo, aumentar lucros ou reduzir as perdas, respectivamente).
Todas as restrições devem ser equações de igualdade (identidades matemáticas).
Todas as variáveis (xi) devem ser positivas ou nulas (condição de não-negatividade).
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:

Objetivo de maximização
Critério de parada: quando na linha Z não aparece nenhum valor negativo.

Condição de entrada na base: o menor valor negativo na linha Z (ou o de maior valor absoluto entre os negativos) indica a variável Pj que entra na base.

Condição de saída da base: depois de obter a variável de entrada, determina-se a variável de saída por meio do menor quociente P0/Pj dos valores estritamente positivos.
Objetivo de minimização
Critério de parada: quando na linha Z não aparece nenhum valor positivo.

Condição de entrada na base: o maior valor positivo na linha Z indica a variável Pj que entra na base.

Condição de saída da base: depois de obter a variável de entrada, determina-se a variável de saída por meio do menor quociente P0/Pj dos valores estritamente negativos.

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.

Restrição do tipo "≤"
Para normalizar uma restrição com uma desigualdade do tipo "≤", adiciona-se uma nova variável, chamada variável de folga xs (com condição de não negatividade: xs ≥ 0). Esta nova variável aparece com coeficiente zero na função objetivo e, somando na equação correspondente (que agora é uma identidade matemática ou equação de igualdade).

a11·x1 + a12·x2 ≤ b1 a11·x1 + a12·x2 + 1·xs = b1
Restrição do tipo "≥"
No caso de uma desigualdade do tipo "≥", deve-se acrescentar também uma nova variável chamada de variável de excesso xs (com condição de não negatividade: xs ≥ 0). Esta nova variável aparece com coeficiente zero na função objetivo e, subtraindo na equação correspondente.

Surge agora um problema com a condição de não negatividade com esta nova variável do problema. As inequações contendo uma desigualdade do tipo "≥" ficariam:

a11·x1 + a12·x2 ≥ b1 a11·x1 + a12·x2 - 1·xs = b1

Ao realizar a primeira iteração do método Simplex, as variáveis básicas não estarão na base e assumirão o valor zero. Neste caso, a nova variável xs, depois de zerar x1 e x2, assumirá o valor -b1 além de não cumprir a condição de não negatividade. É necessário adicionar outra variável xr, chamada de variável artificial, que também aparecerá com coeficiente zero na função objetivo e somando na restrição correspondente. Ficando da seguinte maneira:

a11·x1 + a12·x2 ≥ b1 a11·x1 + a12·x2 - 1·xs + 1·xr = b1
Restrição do tipo "="
Ao contrário do que se poderia pensar, para restrições do tipo "=" (embora já sejam identidades) também é necessário adicionar variáveis artificiais xr. Como no caso anterior, seu coeficiente será zero na função objetivo e aparecerá somando na restrição correspondente.

a11·x1 + a12·x2 = b1 a11·x1 + a12·x2 + 1·xr = b1

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.

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

Método Simplex

Construção da primeira tabela:

As colunas da tabela foram dispostas da seguinte forma: a primeira coluna da tabela contém as variáveis da base (ou variáveis básicas), isto é, aquelas que assumem um valor para fornecer uma solução; a segunda coluna apresenta os coeficientes que tais variáveis básicas têm na função objetivo (esta coluna é chamada Cb); a terceira mostra o termo independente de cada restrição (P0); a partir desta aparece uma coluna para cada uma das variáveis de decisão e folga (Pj) na função objetivo. ). Para obter uma visão mais clara da tabela, uma linha que contém os títulos de cada uma das colunas é incluída.

Sobre esta tabela acrescentam-se duas linhas novas: uma, que lidera a tabela, onde aparecem os coeficientes das variáveis da função objetivo, e uma última linha que indica o valor da função objetivo e os custos reduzidos Zj - Cj.

Os custos reduzidos mostram a possibilidade de melhora na solução Z0. Por este motivo, também são chamados valores indicadores.

A seguir são apresentados o aspecto geral da tabela do método Simplex:

Tabela
			C1	C2	...	Cn
Base	Cb	P0	P1	P2	...	Pn
P1	Cb1	b1	a11	a12	...	a1n
P2	Cb2	b2	a21	a22	...	a2n
...	...	...	...	...	...	...
Pm	Cbm	bm	am1	am2	...	amn
Z		Z0	Z1-C1	Z2-C2	...	Zn-Cn

Todos os valores incluídos na tabela são dados pelo modelo do problema, exceto os valores da linha Z (ou linha indicadora). Estes valores são obtidos da seguinte maneira: Zj = Σ(Cbi·Pj) para i = 1..m, onde se j = 0, P0 = bi e C0 = 0, e caso contrário Pj = aij.

Observa-se, ao se realizar o método Simplex, que nesta primeira tabela ocupa a base todas as variáveis de folga e, assim (todos os coeficientes das variáveis de folga são 0, na função objetivo) o valor inicial de Z é zero.

Pela mesma razão, não é necessário calcular os custos reduzidos na primeira tabela, sendo possível determinar diretamente, como a mudança de sinal dos coeficientes de cada variável na função objetivo, isto é, -Cj.

Critério de parada:
O critério de parada é satisfeito quando a linha indicadora não contenha nenhum valor negativo entre os custos reduzidos (quando o objetivo é a maximização), isto é, não existe possibilidade de melhoria.

Uma vez satisfeito o critério de parada, o valor de cada variável que atinja a solução ótima está na coluna P0, indicando na base a que variável corresponde este valor. Se uma variável não aparece na base, significa que seu valor é zero. Da mesma forma o valor ótimo da função objetivo (Z), que se encontra na coluna P0, linha Z.

Caso o critério de parada não seja cumprido, é necessário realizar mais uma iteração do algoritmo, isto é, determinar a variável que se torna básica e a que deixa de ser, encontrar o elemento pivô, atualizar os valores da tabela e comprovar, novamente, se satisfaz o critério de parada.

Também é possível determinar 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. Esta situação ocorre quando na coluna da variável de entrada à base, todos os valores são negativos ou nulos.
Escolha da variável que entra na base:
Quando uma variável se torna básica, ou seja, entra na base, começa a fazer parte da solução. Observando os custos reduzidos da linha Z, é decidido que entra na base a variável da coluna em que esta seja o menor valor (ou o maior valor absoluto) entre os negativos.
Escolha da variável que sai da base:
Uma vez que se obtém a variável de entrada, é determinado que sairá da base, a variável daquela linha cujo o quociente P0/Pj seja o menor valor, dos estritamente positivos, (sendo que esta operação deverá ser feita unicamente quando Pj seja superior a 0).
Elemento pivô:
O elemento pivô da tabela é marcado pela intersecção entre a coluna da variável de entrada e a linha da variável de saída.
Atualização da tabela:
As linhas que correspondem à função objetivo e os títulos permanecerão inalterados na nova tabela. Os demais valores 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ô)
Desta forma logra-se que todos os elementos da coluna da variável entrante sejam nulos, exceto o da linha da variável de saída em que o valor será 1. (É similar a usar o método de Gauss-Jordan para resolver sistemas de equações lineares).

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.

Construção da primeira tabela:

É elaborada de maneira análoga à tabela inicial do método Simplex, porém com algumas diferenças.

Como mencionado, nesta primeira fase é solucionado um problema auxiliar (minimização da soma das variáveis artificiais), com uma função objetivo auxiliar. Portanto, na primeira linha da tabela, onde constam os coeficientes das variáveis da função objetivo, aparecerão todos os termos zero, exceto os coeficientes de variáveis artificiais. O valor de cada um destes coeficientes é "-1" porque a soma destas variáveis está sendo minimizada (lembre-se que minimizar Z' é o mesmo que maximizar (-1)·Z').

A outra diferença para a primeira tabela é que agora é preciso calcular a linha Z (ou linha indicadora).

Tabela
		C0	C1	C2	...	Cn-k	...	Cn
Base	Cb	P0	P1	P2	...	Pn-k	...	Pn
P1	Cb1	b1	a11	a12	...	a1n-k	...	a1n
P2	Cb2	b2	a21	a22	...	a2n-k	...	a2n
...	...	...	...	...	...	...	...	...
Pm	Cbm	bm	am1	am2	...	amn-k	...	amn
Z		Z0	Z1	Z2	...	Zn-k	...	Zn

Sendo Zj = Σ(Cbi·Pj) - Cj para i = 1..m, onde se j = 0, P0 = bi y C0 = 0, e caso contrário Pj = aij.

Critério de parada e passagem à fase 2:
O critério de parada é o mesmo que ocorre no método Simplex normal. Isto é, quando na linha indicadora nenhum dos valores dos custos reduzidos é negativo (tendo em vista que o objetivo é maximização de (-1)·Z').

Depois de haver satisfeito o critério de parada, é preciso determinar se é possível passar para segunda fase para obter a solução ótima do problema original. Isto é feito observando o resultado obtido na primeira fase: se o seu valor for 0, isso significa que o problema original tem solução e é possível calcular, caso contrário, indica que é um problema não factível e sem solução.

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.

Eliminar coluna de variáveis artificiais:
Caso tenhamos concluído que o problema original tem solução, devemos preparar nossa tabela para a segunda fase. Este passo é muito simples, trata-se simplesmente de eliminar as colunas correspondentes às variáveis artificiais.
Construção da tabela inicial:
A tabela inicial, neste caso, mantém-se muito similar à última tabela da primeira fase. Deve ser modificada a linha da função objetivo pela linha do problema original e calcular novamente a linha Z (da mesma forma que na primeira tabela da fase 1).

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).