Resolva pelo Simplex:
Passo 1
O enunciado dá o problema de programação linear abaixo e pede a solução pelo método Simplex:
- Função objetivo a ser minimizada:
- Restrição (uma só):
- Não negatividade:
O que se pede explicitamente: encontrar os valores de
que minimizam
sujeitos à restrição dada, e o valor mínimo
.
Passo 2
Transformação para usar o Simplex de forma direta (explicação didática curta e concreta):
- O Simplex é normalmente apresentado para problemas de maximização na forma padrão com igualdades. Para aplicar o Simplex aqui eu faço duas coisas simples:
- Introduzo uma variável de folga (slack)
para transformar a desigualdade em igualdade. - Como o problema é de minimização, considero a função auxiliar
. Assim, maximizo . Isso é válido pois maximizar é equivalente a minimizar (pois ).
- Introduzo uma variável de folga (slack)
Aplicando 1: a restrição vira igualdade
Aplicando 2: a nova função a maximizar é
Passo 3
Construção da solução básica inicial (explicação do conceito):
- Solução básica inicial natural: colocar todas as variáveis de decisão
e a variável de folga . Isso satisfaz a restrição e é factível. - Valor inicial de
nessa solução: substituir tudo zero em dá .
Escrevendo a equação da base (a partir da igualdade) isolando
:
E a função objetivo (forma de teste de entrada) escrita como
ou, em forma direta para leitura de coeficientes, os coeficientes de
na função
são
.
Passo 4
Critério de escolha da variável que entra na base (ensino do conceito de custo reduzido):
- No Simplex (maximização) escolhe-se como variável que entra aquela com maior coeficiente positivo na função objetivo (maior impacto de aumento em
). Aqui os coeficientes são: -
, , , , , .
-
- Só variáveis com coeficiente positivo podem aumentar
. Temos empate entre e (ambas com coeficiente ). Faço um desempate arbitrário e escolho para entrar na base (poderia ser , mas o procedimento é análogo).
Passo 5
Teste da razão (regra da razão mínima) para decidir quem sai da base:
- A equação da restrição na forma
mostra que ao aumentar a variável básica atual diminui com coeficiente . Mantendo não negatividade, o máximo que pode crescer é dado por
- Assim,
atinge zero primeiro e sai da base. Ou seja, entra e sai.
Passo 6
Pivoteamento (atualizar as equações) — explicação passo a passo das contas:
- Isolo
a partir da equação de . Da equação
despejando
:
logo
- Como após o pivoteamento
vira não básica (será 0 na solução básica), podemos anotar a forma prática:
- Atualizo também a função objetivo
substituindo na expressão original . Substituindo:
Agora junto termos semelhantes:
- Interpretação prática: na nova tabela as variáveis não básicas
aparecem com coeficientes (nosso “custo reduzido”) respectivamente na expressão de . Esses números dizem quanto mudaria (com sinal) se aumentássemos a variável não básica correspondente a partir de zero, mantendo as outras não básicas em zero.
Passo 7
Critério de otimalidade e conclusão do Simplex:
- Para maximização, o critério de otimalidade é: se todos os coeficientes (custos reduzidos) das variáveis não básicas na expressão de
são menores ou iguais a zero, a solução atual é ótima. - Aqui, após o pivoteamento, os coeficientes de todas as variáveis não básicas
são todos negativos ( ). Isso significa que não existe nenhuma variável que, se aumentada, aumentaria . Logo a solução é ótima para o problema de maximização de . - Como maximizar
é equivalente a minimizar , essa solução também é ótima para o problema original de minimização.
Passo 8
Leitura da solução ótima e valor objetivo final (como obter valores das variáveis):
- Da base final temos
(obtido na equação isolada) e todas as demais variáveis de decisão são zero:
- A variável de folga ficou
(como previsto pelo teste da razão). - Valor de
ótimo (da expressão encontrada com todas as não básicas zero) é . - Portanto o valor mínimo do original
é
Breve intuição para fixar: como as variáveis
e
tinham coeficientes negativos na função original (
cada) elas “reduzem” mais o valor de
por unidade, mas
consome menos recurso da restrição (coeficiente
em vez de
para
). Então é melhor aplicar toda a capacidade na
:
.
Resposta
Valor mínimo