Considere o seguinte conjunto de restrições:
X1+2 X2+2 X3+4 X4 <= 40
2 X1-X2+X3+2 X4 <= 8
4 X1-2 X2+X3-X4 <= 10
X1 ; X2 ; X3 ; X4 >= 0
Max z=8 X1+6 X2+3 X3-2 X4

Passo 1

Beleza, o enunciado é um problema de Programação Linear:
Nós queremos maximizar
z = 8X1 + 6X2 + 3X3 - 2X4
sujeito a
X1 + 2X2 + 2X3 + 4X4 <= 40, 2X1 - X2 + X3 + 2X4 <= 8, 4X1 - 2X2 + X3 - X4 <= 10, X1,X2,X3,X4>=0
Conteúdo: método Simplex. Vamos precisar de slack variables (variáveis de folga), montar a tabela inicial, escolher a coluna de entrada (variável que aumenta o valor de z) e a linha de saída (regra da razão mínima), pivotar e iterar até não haver mais custos reduzidos negativos.

Passo 2

Transformando as desigualdades em igualdades, adicionamos variáveis de folga X1+2X2+2X3+4X4 + s1 = 40, 2X1 - X2 + X3 + 2X4 + s2 = 8, 4X1 -2X2 + X3 - X4 + s3 = 10, Xi,sj>=0 :
E escrevemos a função-objetivo na forma de linha .
Tabela inicial (básicas: ):
Básica B
1 2 2 4 1 0 0 40
2 -1 1 2 0 1 0 8
4 -2 1 -1 0 0 1 10
-8 -6 -3 2 0 0 0 0
Como tem -8 e -6 na linha , podemos melhorar . Entramos com (mais negativo).

Passo 3

Primeiro pivot:
  • Coluna de entrada: .
  • Razões:
    • ← mínimo, sai .
      Pivot em . Após as operações de linha, a tabela vira:
Básica B
0 2.5 1.75 4.25 1 0 -0.25 37.5
0 0 0.5 2.5 0 1 -0.5 3
1 -0.5 0.25 -0.25 0 0 0.25 2.5
0 -10 -1 0 0 0 2 20
Agora o custo reduzido de é , o mais negativo. Vamos pivotar em .

Passo 4

Segundo pivot:
  • Coluna de entrada: .
  • Razões válidas:
    • coeficiente 0 (não entra)
    • coeficiente negativo (descartamos)
      Logo sai . Pivot em . Após normalizar e zerar a coluna, a tabela fica:
Básica B
0 1 0.7 1.7 0.4 0 -0.1 15
0 0 0.5 2.5 0 1 -0.5 3
1 0 0.6 0.6 0.2 0 0.2 10
0 0 6 17 4 0 1 170
Agora todos os custos reduzidos (coluna nas variáveis não-básicas) são ≥0. Chegamos ao ótimo.

Resposta

A solução ótima é
X1 = 10, X2 = 15, X3 = 0, X4 = 0,
com valor máximo
max z = 170

Exercícios relacionados