Question 4. (2.0) Considere o problema
(a) Resolva o problema usando o método primal(ou dual) do simplex. Considere como base inicial
.
(b) Acrescente a restrição
ao problema e em seguida encontre a base ótima para o novo problema.
(b) Acrescente a restrição
Passo 1
O enunciado pede para resolver o PL
minimizar
sujeito a
minimizar
sujeito a
Vamos trabalhar no formato de maximização
e usar o método do simplex primal. A base inicial dada é
isto é, as variáveis básicas são
e
.
Passo 2
Calcular a BFS inicial para
.
A matriz básica e o vetor-lado direito são
A matriz básica e o vetor-lado direito são
Então
Logo
e o valor da função-objetivo é
Passo 3
Calcular os custos reduzidos. Os vetores de custos são
, para maximizar, e
.
O vetor dos multiplicadores satisfaz
O vetor dos multiplicadores satisfaz
Para
(coluna
):
logo
entra.
A direção básica é
A direção básica é
Razão mínima
indica que sai
. Faz-se o pivô e a nova base torna-se
.
Passo 4
Com a base
,
A solução básica é
com
. Calcula-se
e verifica-se que os custos reduzidos de
são não-positivos, confirmando a otimalidade.
O valor ótimo é
O valor ótimo é
ou seja
Passo 5
(b) Acrescenta-se a restrição
, que equivale a
Formamos o sistema alargado e propomos a base
.
Passo 6
Resolver
com
. Os multiplicadores
geram custos reduzidos não-positivos para
, então a base
permanece ótima.
Resposta
(a) Base ótima
com
valor ótimo
(b) Com a nova restrição, a base ótima é
e