Resolver os modelos em programação linear, usando o método Simplex.
Max. Lucro
=2 × 1+3 × 2+4 × 3
Sujeito a:
{
x_{1}+x_{2}+x_{3} ≤ 100
2 x_{1}+x_{2} ≤ 210
x_{1} ≤ 80
x_{1} ≥ 0, x_{2} ≥ 0, x_{3} ≥ 0
}
Max. Lucro
=2 × 1+3 × 2+4 × 3
{
x_{1}+x_{2}+x_{3} ≤ 100
2 x_{1}+x_{2} ≤ 210
x_{1} ≤ 80
x_{1} ≥ 0, x_{2} ≥ 0, x_{3} ≥ 0
}
Passo 1
O enunciado pede maximizar o lucro dado por
Informações relevantes fornecidas:
- Função objetivo:
”.
- Variáveis não-negativas.
O que se pede: resolver o problema por programação linear usando o método Simplex e determinar a solução ótima (valores dee o lucro máximo).]
Passo 2
Colocar o problema em forma padrão (igualdades) introduzindo variáveis folga (slack)
:
A solução básica inicial natural é tomar as folgas como variáveis básicas:
A função objetivo escrita como equação para o Simplex:
No Simplex começamos com
e
. O valor inicial de
é
.]
Passo 3
Ideia do Simplex (intuitiva): manter uma solução básica viável e tentar aumentar
trazendo uma variável não-básica para a base (variável que “entra”) enquanto outra sai, escolhendo a variável que mais aumenta
. Isso é feito olhando os coeficientes da função objetivo expressa em termos das não-básicas (reduced costs) e aplicando o teste de razão mínima para garantir viabilidade.
No início temos a forma explícita das igualdades (com as folgas como básicas). A equação objetivo, sem substituições, é
No formato usado para escolher quem entra, olhamos os coeficientes diretos
e, para maximizar, trazemos a variável com maior coeficiente positiva na função objetivo (isto corresponde a escolher a coluna cujo aumento aumenta mais
). Aqui isso é
(coeficiente
). Outra forma equivalente: na forma
escolhemos a coluna com coeficiente mais negativo (aqui
), que também indica
entra.
Aplicar teste de razão mínima para saber qual variável básica sai. Olhamos as equações e as coeficientes da coluna
:
- Na equação 1: coeficiente de
é , razão . - Na equação 2: coeficiente de
é (não restringe). - Na equação 3: coeficiente de
é (não restringe).
Só a primeira equação tem coeficiente positivo em
, logo a razão mínima é
e a variável que sai é
. Portanto pivotamos pela linha 1 e coluna
:
entra e
sai.
Passo 4
Fazer o pivot (algebraicamente): resolver a equação 1 para
:
Substituir essa expressão nas outras equações e na função objetivo para atualizar a base.
Atualizando as demais equações:
- Equação 2 (mantém
):
- Equação 3 (mantém
):
Substituir
na função objetivo:
Escrevendo esta forma de
como
vemos que, na expressão de
em termos das variáveis não-básicas
, os coeficientes em frente a essas variáveis são
, todos não-positivos.
Interpretação de optimalidade (forma prática): quando se escreve
como
, se todos os
então aumentar qualquer variável não-básica (partindo de zero) não aumenta
(pelo contrário, diminui ou mantém). Portanto a solução atual é ótima.
Aqui os coeficientes são
, logo a solução após este pivot é ótima — não há variável que entrando aumente
.]
Passo 5
Determinar a solução ótima avaliando básicos com as não-básicas =
. Após o pivot a base é
e as não-básicas são
. Tomando
:
- Da equação pivotada:
. - Da equação 2:
. - Da equação 3:
.
Calcular:
Verificações rápidas das restrições originais com
:
todas satisfeitas. Como o critério de optimalidade do Simplex foi atendido, esta é a solução ótima.