Considere o seguinte conjunto de restrições:
|
|
---|---|
|
|
|
|
|
Passo 1
Beleza, o enunciado é um problema de Programação Linear:
Nós queremos maximizar
Nós queremos maximizar
sujeito a
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: ):
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 é
com valor máximo