Simplex

Existem diferentes algoritmos para resolver problemas de PL como: Simplex, o Big M, o Simplex de duas fases, o Karmarkar, dentre outros. No entanto, o mais famoso é o Simplex, desenvolvido por George Dantzig, em 1946. Neste material, será apresentado o algoritmo Simplex para problemas de maximização. O algoritmo pode ser implementado 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 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.

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

O exemplo abaixo apresenta um modelo matemático de um problema de maximização de duas variáveis, contendo duas restrições. Ambas as restrições são inequações do tipo '<='.

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

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

Quadro inicial

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

Análise de quadro

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.

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.

Análise do quadro

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

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ô)
  • 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

Análise do quadro

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

O problema da empresa MatoCerto

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.

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.

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.

Vídeos complementares

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