Exercício 5
Encontre a solução ótima do seguinte problema de programação linear pelo método simplex tabular:
Passo 1
O enunciado pede: encontrar a solução ótima do problema
Informações relevantes dadas:
- Função objetivo:
a maximizar. - Três restrições lineares com sinais
e termos à direita , e . - Variáveis não-negativas:
.
A partir daqui vamos aplicar o método simplex tabular passo a passo.
Passo 2
Passo inicial: transformar em forma padrão adicionando variáveis folga
(todas
):
Na solução inicial básica temos as variáveis básicas
e
.
A tabela inicial (resumida) de coeficientes para as variáveis e RHS é:
A tabela inicial (resumida) de coeficientes para as variáveis
Explicação rápida do critério de escolha: para maximização escolhemos a variável não-básica com maior valor positivo de
; inicialmente
para todas, logo escolhemos a coluna com maior custo
.
Passo 3
Cálculo do primeiro pivô:
- Valores de
iniciais são simplesmente os custos : . O maior é (coluna de ), então entra na base. - Razão (teste da razão mínima) para escolher linha que sai: só se consideram coeficientes positivos em coluna de
. O mínimo é (primeira linha). Então pivotamos na posição correspondente ao coeficiente em linha 1. - Operação de pivot: vamos transformar a linha 1 para que o coeficiente de
fique dividindo a linha 1 por : - Eliminar
das outras linhas: - Agora a base é
com custos .
Passo 4
Atualizar custos reduzidos e decidir próximo pivô:
- Para calcular
(o valor atual contribuído pela base) usamos a soma , onde são os custos das variáveis básicas e as entradas das colunas. Aqui só tem custo não-nulo , então (coluna de na forma atual). - Calculando
para as variáveis não-básicas (ex.: ): Observação: tem , logo ainda podemos melhorar a solução escolhendo para entrar. - Coluna de
na tabela atual tem coeficientes . Fazemos o teste da razão usando apenas entradas positivas nessa coluna: O menor é , correspondente à terceira linha. Assim o pivot é o coeficiente na linha 3; entra e sai.
Passo 5
Executar o segundo pivot (detalhes das operações com frações — importante para prova sem calculadora):
- Dividir a linha 3 pelo pivot
(equivalente a multiplicar por ): - Eliminar
das outras linhas: - Na linha 1: eliminar
: cálculo coefficient-wise: Simplificando as frações isso dá - Na linha 2: coeficiente de
já era , então permanece - A linha 3 já está na forma pivot (com
com coeficiente ):
- Na linha 1: eliminar
- Agora a base é
com custos .
Passo 6
Verificar optimalidade calculando os custos reduzidos finais:
- Calcular
como .
Vamos aos principais: - Para as variáveis folga também os
são não-positivos (calcularíamos da mesma maneira). - Critério de optimalidade do simplex: quando todos os
para um problema de maximização, a solução atual é ótima. Aqui não existem entradas positivas restantes, logo estamos ótimos.
Passo 7
Ler a solução ótima da tabela final:
- As variáveis básicas e seus RHS (valores) são:
As variáveis não-básicas são . - Valor da função objetivo:
Passo 8
Verificação rápida de consistência (substituir na restrição original para garantir que tudo bate):
Tudo está consistente: duas restrições ativas (igualdade) e a segunda com folga
. A solução é viável e ótima.