Exercício 3
Utilizando o método simplex tabular, resolva o problema de programação linear abaixo:
Passo 1
O enunciado pede: minimizar a função objetivo
sujeito às restrições
Informações relevantes fornecidas:
- Variáveis de decisão:
com . - Três desigualdades do tipo
(podemos introduzir variáveis folga). - Objetivo é minimizar
.
As perguntas implícitas: encontrar os valores deque minimizam e o valor mínimo de .
Passo 2
Estratégia (sem detalhes técnicos profundos ainda): o método simplex tabular funciona naturalmente para maximização. Para usar o simplex clássico transformamos a minimização em maximização multiplicando a função objetivo por
. Definimos
e vamos maximizar
sujeito às mesmas restrições. Depois, o valor ótimo de
será
.
Também introduzimos variáveis de folga (slack)
para transformar as desigualdades em igualdades:
A solução básica inicial é
com
.
Passo 3
Montamos o tableau inicial (colunas:
; RHS = termos independentes). Coeficientes de
(a maximizar) são
. A tabela inicial (representação compacta) é:
Linha 1 (equação 1, base
,
):
Linha 2 (equação 2, base
,
):
Linha 3 (equação 3, base
,
):
Linha objetivo (custos reduzidos
; inicialmente
porque
):
Explicação rápida: escolhemos como variável a entrar aquela com maior custo reduzido positivo (pois maximizamos
).
Passo 4
Primeira iteração — escolha da variável a entrar:
tem
(maior positivo), entra na base. Fazemos teste de razão (RHS dividido pelo coeficiente positivo na coluna de
) para determinar a linha pivô:
Menor razão é
-> pivô na linha 2, elemento pivô =
(coeficiente de
na linha 2). Tornamos essa linha a linha básica de
dividindo por
(já está 1). Agora eliminamos
das demais linhas.
Linha 2 (nova, base
,
):
Atualizamos linha 1: linha1 := linha1 − 3·linha2
Atualizamos linha 3: linha3 := linha3 − 1·linha2
Calculamos agora os custos reduzidos
. Regra:
onde o somatório é sobre linhas básicas; agora
correspondendo às bases
. Como somente
tem
e sua linha é a linha 2, temos
. Portanto
Logo
O valor atual de
(RHS da função objetivo) é
.
Passo 5
Segunda iteração — escolha da variável a entrar: coluna
tem custo reduzido
, então
entra. Fazemos teste de razão usando coeficientes positivos da coluna
:
Menor razão é
-> pivô na linha 3, elemento pivô =
. Dividimos a linha 3 por
para ter 1 na posição pivô.
Linha 3 (nova base
,
) após divisão por 2:
Eliminamos
das outras linhas:
Linha 1 := linha1 − 4·linha3
Linha 2 := linha2 + 1·linha3 \quad (porque coeficiente era
)
Passo 6
Atualizamos os custos reduzidos com as novas bases. As variáveis básicas agora são
com
. Calculamos
.
Multiplicando linhas:
Somando:
Os custos reduzidos
são:
O valor atual de
é
.
Passo 7
Condição de otimalidade (para maximização): todos os custos reduzidos
devem ser ≤ 0. Aqui os custos reduzidos são
, todos ≤ 0. Portanto a solução atual é ótima para o problema de maximização de
.
Lemos a solução básica do tableau final:
- linha 1 (base
): ; - linha 2 (base
): ; - linha 3 (base
): .
As variáveis não básicas são.
Verificação rápida nas restrições originais:
Valor ótimo encontrado para
é
. Lembrando que
, então o valor mínimo buscado é
.