Simplex

O nome “simplex" está relacionado com o conjunto de restrições lineares que representam geometricamente uma figura chamada simplexo, que é o equivalente aos poliedros no espaço e aos polígonos no plano.

O método Simplex está fundamentado nos seguintes teoremas:

• O conjunto de todas as soluções viáveis de um modelo de Programação Linear forma um conjunto convexo;

• Toda solução compatível básica do sistema de equações lineares de um modelo de Programação Linear é um ponto extremo do conjunto de soluções viáveis, isto é, do conjunto de convexo de soluções;

• Se a função-objetivo possui um ótimo finito, então pelo menos uma solução ótima é um ponto extremo do conjunto convexo de soluções viáveis;

• Se a função-objetivo assume o ótimo em mais de um ponto extremo do conjunto de soluções viáveis, então ela toma o mesmo valor para qualquer ponto do segmento da reta que une esses pontos extremos.

Mas como o software é capaz de resolver um problema de programação linear a partir da formulação matemática?

A resposta está no algoritmo implementado dentro dos programas de otimização, como por exemplo o LPSolve. Geralmente, os programas possuem mais de um algoritmo, e cabe ao usuário escolher qual utilizar durante o processo de otimização. Existem diferentes algoritmos para resolver problemas de PL:

  • Algoritmo Simplex.
  • Método Big M.
  • Método Simplex de duas fases.
  • Método Karmarkar.
  • Outros…

No entanto, o mais famoso é o Simplex, algoritmo que foi desenvolvido por George Dantzig, em 1946. Neste material, será apresentado o algoritmo Simplex para problemas de maximização. O algoritmo pode ser descrito pelos seguintes passos:

  1. Escrever o problema de programação linear na formulação padrão.
  2. Obter uma solução básica viável.
  3. Determinar se a solução básica viável é ótima.
  4. Se a solução básica viável não é ótima, determinar uma variável não básica para trocar de lugar com uma variável básica.
  5. Usar as operações elementares de linhas para encontrar uma nova solução básica viável.

O Método Simplex é um procedimento matricial que percorre os pontos extremos do conjunto das soluções viáveis em busca de uma solução ótima. O algoritmo utiliza um critério na busca de forma que a solução ao seguinte seja sempre “melhor” do que a anterior. Como o conjunto possui um número finito de pontos extremos isso garante que o algoritmo termina em algum ponto, que será uma solução ótima do problema.
Disponível:https://repositorio.ufsc.br/xmlui/bitstream/handle/123456789/126306/Ruana_Maira_Schneider.pdf?sequence=1&isAllowed=y

O simplex é um procedimento matemático, de manipulação da matriz criada com base na forma padrão. Antes de começar a resolver um problema pelo simplex, vamos definir dois conceitos importantes:

  • Solução básica viável = apresenta todas as variáveis não negativas.
  • Variáveis básica = valor diferente de zero, formando uma solução básica viável.
  • Variável não básica = valor igual a zero.

Forma padrão

A forma padrão é uma forma alternativa de apresentar a formulação matemática apenas com o uso de equações. Assim, altere a função objetivo e as restrições, eliminando as inequações, incorporando as variáveis de falta ou de excesso:

  • Se restrição do tipo $<$ ou $\leq$, entrar com variável de falta.
  • Se restrição do tipo $>$ ou $\geq$, entrar com variável de excesso.

Por exemplo, a restrição:

X1 + X2 <= 40

Passa a ser:

X1 + X2 + f1 = 40

Por exemplo, a restrição:

X1 + 2 X2 >= 10

Passa a ser:

X1 + 2 X2 - e1 = 10

Exemplo 1

Max Z=10 X1 + 12 X2
S.a.
X1 + X2 <= 100
X1 + 3 X2 <= 270

Sendo a função objetivo, maximizar e as inequações de restrições são do tipo menor e igual, então o modelo poderá ser resolvido pelo processo padrão do Simplex.

Formulação padrão

Na função objetivo o segundo membro passará para antes da igualdade.Nas restrições adiciona-se as folgas (F), igualando o primeiro membro com o segundo membro.

Z - 10 X1 - 12 X2 = 0
X1 + X2 + F1 = 100
X1 + 3X2 + F2 = 270

Construir o quadro inicial, este irá conter todas as variáveis, as folgas e os termos independentes, chamados de RHS, da função objetivo e das restrições com seus respectivos coeficientes.

Z X1 X2 F1 F2 RHS
1 -10 -12 0 0 0
0 1 1 1 0 100
0 1 3 0 1 270

O objetivo será construir uma nova tabela em que os números da primeira linha sejam todos positivos e assim alcançar a solução ótima.

  • 1° passo: Identificar a variável que entra.

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.
Sendo esta a que possuir o maior valor absoluto. Neste exemplo será a variável X2, que possui o valor -12.

  • 2° passo: Identificar a variável que sai.

Uma vez que se obtém a variável de entrada, é determinado que sairá da base
Dividindo os termos independentes pelos respectivos coeficientes de X2.

100/1 = 100
270/3 = 90

Escolher a linha em que o resultado foi o menor valor positivo, neste caso o menor valor foi 90, então a linha que irá sair será:

0 1 3 0 1 270
  • 3° passo: identificar o elemento pivô.

Será o elemento que está no cruzamento da coluna que entra com a linha que sai. Neste caso o elemento pivô será o número 3.

  • 4° passo: Calcular a "nova linha pivô".

Dividir a linha que sai pelo elemento pivô.

      0     1        3      0       1         270
/3=
      0     0,34     1       0      0,34       90 --->NLP (nova linha pivô)
  • 5° passo: calcular as novas linhas.

Multiplicar a nova linha pivô pelo oposto dos coeficientes da variável que entra e somar pelas linhas respectivas do coeficientes multiplicados.

30ufl9v.png
2mfybrl.jpg

A nova terceira linha é a nova linha pivô.

  • 6° passo: novo quadro contendo todas as novas linhas calculadas:
Z X1 X2 F1 F2 RHS
1 -6 0 0 4 1080
0 0,66 0 1 -0,34 10
10 0,34 1 0 0,34 90

Solução: sempre irá conter as variáveis básicas (VB), as variáveis não básicas (VNB) e o valor de Z. Sendo as variáveis básicas, aquelas cujas colunas possuírem o número 1 e o número 0. Para que a afirmativa Z=1080, segundo este exemplo, seja verdadeira é necessário zerar as variáveis da equação de Z. Como neste caso as variáveis X2 e F1 possuem valor 0, apenas as variáveis X1 e F2 precisam ser zeradas.

j5ko0j.png

A solução não é ótima porque uma das variáveis da função objetivo apresenta valor negativo, sendo que para ela ser ótima, todas as variáveis devem possuir coeficientes positivos.Assim é necessário recalcular, seguindo os mesmos passos anteriores.

  • A variável que entra será a de maior valor negativo, neste caso será a X1.
  • A linha que sai:
10/0,66 = 15,15
90/0,34 = 264,7

|| 0|| 0,66 || 0 || 1 || -0,34 || 10 ||

  • O elemento pivô será 0,66.
  • Nova linha pivô:
      0     0,66    0      1       -0,34         10
/0,66=
      0     1       0      1,52    -0,52         15,15 --->NLP (nova linha pivô)
  • Novas linhas:
250tc87.jpg
fd652e.png
  • Quadro final:
Z X1 X2 F1 F2 RHS
1 0 0 9,12 0,88 1170,9
0 1 0 1,52 -0,52 15,15
0 0 1 -0,52 0,52 84,85
2hrco6c.png

A solução será ótima, visto que os valores das variáveis da função objetivo são positivos.

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

Para maiores entendimentos sobre as diferenças do Método Simplex e Método Duas Fases podemos observar o fluxograma.
2ccqzk5.png

O problema da empresa MatoCerto

Considerando o problema da empresa MatoCerto, acompanhe abaixo a transformação da formulação matemática na forma padrão e a resolução do problema pelo método Simplex.

Formulação matemática:

MaxZ = 60 A + 50 B + 30 C
S.a.
7 A + 4 B + 4 C <= 150
3 A + 4 B + 2 C <= 200

Forma padrão

MaxZ - 60 A - 50 B - 30 C + 0 f1 + 0 f2 = 0
7 A + 4 B + 4 C + f1 = 150
3 A + 4 B + 2 C + f2 = 200

Quadro inicial

Z A B C f1 f2 RNH
1 -60 -50 -30 0 0 0
0 7 4 4 1 0 150
0 3 4 2 0 1 200

Com base na tabela acima, o conjunto de variáveis básicas e o conjunto de variáveis não básicas podem ser assim definido:

VB = {f1, f2}
VNB = {A, B, C}

A passará para o conjunto VB, pois possui o coeficiente mais negativo (ou seja, faz com que a função objetivo aumente mais). Agora é necessário encontrar quem irá passar para o conjunto VNB:

  • Se f1 sai, $A \leq \frac{150}{7}$, $A \leq 21,42$
  • Se f2 sai, $A \leq \frac{200}{3}$, $A \leq 66,66$

Assim, A troca de lugar com f1.

Pivoteamento

Ajuste da linha pivô.

Operação Z A B C f1 f2 RNH
1 -60 -50 -30 0 0 0
linha2 / 7 0 1 4/7 4/7 1/7 0 150/7
0 3 4 2 0 1 200

Com base na linha pivô ajustada, termina-se a troca de A com f1:

Operação Z A B C f1 f2 RNH
linha 1 + 60 linha 2 1 0 -110/7 30/7 60/7 0 9000/7
0 1 4/7 4/7 1/7 0 150/7
linha 3 - 3 linha 2 0 0 16/7 2/7 -3/7 1 950/7

Quadro 1

Z A B C f1 f2 RNH
1 0 -110/7 30/7 60/7 0 9000/7
0 1 4/7 4/7 1/7 0 150/7
0 0 16/7 2/7 -3/7 1 950/7

Com base na tabela acima, o conjunto de variáveis básicas e o conjunto de variáveis não básicas podem ser assim definido:

VB = {A, f2}
VNB = {B, C, f1}

B, que possui o coeficiente mais negativo, passará para o conjunto VB, trocando de lugar com:

  • Se A sai, $B \leq \frac{21,42}{0,57}$, $B \leq 37,6$
  • Se f2 sai, $B \leq \frac{135,71}{2,28}$, $B \leq 59,52$

Assim, B troca de lugar com A.

Pivoteamento

Ajuste da linha pivô:

Operação Z A B C f1 f2 RNH
1 0 -110/7 30/7 60/7 0 9000/7
7/4 * linha 2 0 7/4 1 1 1/4 0 75/2
0 0 16/7 2/7 -3/7 1 950/7

Com base na linha pivô ajustada, termina a troca de B com A:

Operação Z A B C f1 f2 RNH
linha 1 + 110/7 linha 2 1 55/2 0 20 25/2 0 1875
0 7/4 1 1 1/4 0 75/2
linha 3 - 16/7 linha 2 0 -4 0 -2 -1 1 50

Quadro 2

Z A B C f1 f2 RNH
1 55/2 0 20 25/2 0 1875
0 7/4 1 1 1/4 0 75/2
0 -4 0 -2 -1 1 50

Com base na tabela acima, o conjunto de variáveis básicas e o conjunto de variáveis não básicas podem ser assim definido:

VB = {B, f2}
VNB = {A, C, f1}

Não há nenhuma variável que ao entrar faz com que Z aumente. Portanto, esta é a solução final.

O problema da indústria de móveis

Uma empresa moveleira fabrica escrivaninhas, mesas e cadeiras. A fabricação de cada tipo de móvel requer madeira e dois tipos de trabalhos manuais: carpintaria e acabamento.

A escrivaninha demanda 8 8m², 2 e 4 horas respectivamente. A mesa demanda 6 m², 1,5 e 2 horas respectivamente. A cadeira demanda 1 m², 0,5 e 1,5 horas respectivamente. Atualmente, estão disponíveis 48 metros cúbicos de madeira, 20 horas de acabamento e 8 horas de carpintaria. A escrivaninha é vendida por R$ 60, a mesa por R$ 30 e a cadeira por R$ 20. Estima-se que a demanda por escrivaninha e cadeiras seja infinita, mas que apenas 5 mesas podem ser vendidas. Deseja-se maximizar a receita.

Formulação conceitual

Maximizar a receita
S.a.
Restrição de horas de acabamento
Restrição de horas de carpintaria
Restrição de madeira
Restrição de demanda de mesas

Formulação matemática

Maxz = 60 E + 30 M + 20 C
S.a.
4 E + 2 M + 1,5 C <= 20
2 E + 1,5 M + 0,5 C <= 8
8 E + 6 M + 1 C <= 48
M <= 5

Formulação padrão

MaxZ - 60 E - 30 M - 20 C + 0 f1 + 0 f2 + 0 f3 + 0 f4 = 0
S.a.
4 E + 2 M + 1,5 C + f1 = 20
2 E + 1,5 M + 0,5 C + f2 = 8
8 E + 6 M + 1 C + f3 = 48
M + f4 = 5

Quadro inicial

Z E M C f1 f2 f3 f4 RHS
1 -60 -35 -20 0 0 0 0 0
0 8 6 1 1 0 0 0 48
0 4 2 1,5 0 1 0 0 20
0 2 1,5 0,5 0 0 1 0 8
0 0 1 0 0 0 0 1 5
VB = {f1, f2, f3, f4}
VNB = {E, M, C}

Entra E para o conjunto VB e sai:

  • Se f1 sai: $E \leq 6$
  • Se f2 sai: $E \leq 5$
  • Se f3 sai: $E \leq 4$
  • Se f4 sai: 5/0 $\rightarrow$ $\nexists$

Quadro 1

Z E M C f1 f2 f3 f4 RHS
1 0 10 -5 0 0 30 0 240
0 0 0 -1 1 0 -4 0 16
0 0 -1 0,5 0 1 -2 0 4
0 1 0,75 0,25 0 0 0,5 0 4
0 0 1 0 0 0 0 1 5
VB = {E, f1, f2, f4}
VNB = {M, C, f3}

Entra C para o conjunto VB e sai:

  • Se f1 sai: C negativo $\rightarrow$ NA
  • Se f2 sai: $C \leq 8$
  • Se E sai: $C \leq 16$
  • Se f4 sai: 5/0 $\rightarrow$ $\nexists$

Quadro 2

Z E M C f1 f2 f3 f4 RHS
1 0 10 -5 0 0 30 0 240
0 0 0 -1 1 0 -4 0 16
0 0 -1 0,5 0 1 -2 0 4
0 1 0,75 0,25 0 0 0,5 0 4
0 0 1 0 0 0 0 1 5
VB = {E, C, f1, f4}
VNB = {M, f2, f3}

Como M está na VNB e possui valor zero, esta PL apresenta múltiplas soluções.

O problema da WoodCo

WoodCo produz dois tipos de moirões: extensor de cerca e cerca regular. Uma peça do tipo extensor é vendida a R$ 36 e a peça para cerca regular é vendida a R$ 30. O extensor exige 1 dia de tratamento e 6 litros de produto químico. O moirão regular exige 1 dia de tratamento e 5 litros de produto químico.

No momento, WoodCo possui disponibilidade de 5 dias de tratamento e 10 litros do produto químico. É possível alugar 1 dia de tratamento na empresa vizinha à um custo de R$ 3 e comprar produto químico a um custo de R$ 4 por litro. Resolva o problema de programação linear que maximiza o lucro da WoodCo.

Formulação conceitual

Maximizar lucro = moiroes vendidos - aluguel - insumo comprado
S.a.
Restricao de dias de tratamento
Restricao do produto quimico

Formulação matemática

MaxZ = 36 E + 30 R - 3 DT - 4 LT
S.a.
E + R <= 5 + DT
6 E + 5 R <= 10 + LT

Forma padrão

MaxZ - 36 E - 30 R + 3 DT + 4 LT = 0
S.a.
E + R - DT + f1 = 5
6 E + 5 R - LT + f2 = 10

Quadro inicial

Z E R DT LT f1 f2 RHS
1 -36 -30 3 4 0 0 0
0 1 1 -1 0 1 0 5
0 6 5 0 -1 0 1 10
VB = {f1, f2}
VNB = {E, R, DT, LT}

Entra E para VB e sai:

  • Se f1 sai: $E \leq 5$
  • Se f2 sai: $E \leq \frac{10}{6}$

Quadro 1

Z E R DT LT f1 f2 RHS
1 0 0 3 -2 0 6 60
0 0 1/6 -1 1/6 1 1/6 10/3
0 1 5/6 0 -1/6 0 1/6 5/3
VB = {E, f1}
VNB = {R, DT, LT, f2}

Entra LT para VB e sai:

  • Se f1 sai: $LT \leq \frac{10}{3} * \frac{1}{6}$
  • Se E sai: LT negativo $\rightarrow$ NA

Quadro 2

Z E R DT LT f1 f2 RHS
1 0 0 3 -2 0 6 60
0 0 1/6 -1 1/6 1 1/6 10/3
0 1 5/6 0 -1/6 0 1/6 5/3
VB = {E, LT}
VNB = {R, DT, f1, f2}

Entra DT para VB:

  • Se LT sai: DT negativo $\rightarrow$ NA
  • Se E sai: DT negativo $\rightarrow$ NA

Como não é possível escolher uma variável para fazer a troca, o problema não tem solução. Mas, onde está o problema que leva o caso acima a não apresentar solução? Numa rápida análise, percebe-se que falta para o problema um limite para os dias a serem alugados e insumos a serem comprados.

Praticando

Exercício 1

Resolva o problema de programação linear abaixo pelo algoritmo Simplex:

MaxZ = 3 X1 + 5 X2
S.a.
X1 <= 4
2 X2 <= 12
3 X1 + 5 X2 <= 18

Exercício 2

Resolva o problema de programação linear abaixo pelo algoritmo Simplex:

MaxZ = 2 X1 + X2
S.a.
2 X1 + 5 X2  <= 60
X2 <= 10
X1 + X2 <= 18
3 X1 + X2 <= 44

Vídeo sobre a teoria do Método Simplex

Vídeos de exercícios resolvidos:

Para melhor fixação da matéria, segue vídeos com resolução de problemas pelo Simplex.

1° vídeo:

2° vídeo:

3° vídeo:

4° vídeo:

5° vídeo:

6º vídeo:


7° vídeo, como resolver um problema pelo método Simplex utilizando o Excel:

8º vídeo: Algoritmo Simplex pelo Excel.

Minimização com o Simplex

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.

Minimizando

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

No vídeo a seguir, é possível entender com maiores detalhes a minimização pelo método simplex.

Fonte: http://www.phpsimplex.com/pt/teoria_metodo_simplex.htm

Figura-3-Fluxograma-descritivo-do-metodo-Simplex-Fonte-Lachtermarcher-2009.jpg

O primeiro passo do simplex consiste em encontrar uma solução básica factível inicial.
No passo seguinte o vértice corrente é deslocado ao vértice adjacente na direção em que
mais aumenta a função objetivo Z. Caso a função objetivo tenha melhorado o passo deve
ser repetido. Estas iterações acontecem até que não exista melhora no valor de Z, indicando
que a solução ótima foi obtida na penúltima iteração.

Resolvendo PL Usando método Simplex:

O método iterativo normalmente inicia no ponto de origem A. Logo após, é analisada se a utilização de um ponto com x1 ou x2 maior que 0 poderia melhorar a função objetivo z. Analisando a função objetivo podemos afirmar que sim.

O projeto Simplex exige que se melhore apenas uma variável por vez, analisando qual delas traria uma maior taxa de melhora para a função objetivo. Para o exemplo citado, o valor da função objetivo aumentará em 2 para cada unidade de x1 e 3 para cada unidade de x2. Portanto, a variável escolhida seria x2. A figura mostra que x2 será aumentado até alcançar o ponto extremo B.

Logo após, o valor de x1 será aumentado até alcançar o ponto C que é o ótimo. Portanto, o método percorre um caminho pelas bordas, até atingir um valor ótimo.

10z6cf6.png

fonte: https://otimizacao.js.org/simplex_about.html

Estrutura de representação para o método simplex:

ic6wxz.png

fonte: https://otimizacao.js.org/simplex_about.html

Salvo indicação em contrário, o conteúdo desta página é licenciado sob Creative Commons Attribution-ShareAlike 3.0 License