(1) Resolva o problema (18)-(21) usando o método primal do simplex.
(2) Encontre o problema dual associado ao problema (18)-(21) e resolva o mesmo.
(3) Supondo que o lado direito da restrição (19) do problema (18)-(21) seja acrescido de uma unidade. A base ótima do problema (18)-(21) é ótima para o novo problema?
(4) Supondo que o vetor de custos do problema (18)-(21) seja alterado para (2, 1, 1). A base ótima do problema (18)-(21) é ótima para o novo problema?
(5) Se uma variável for incluída ao problema (18)-(21) com custo igual a -1 e com os coeficientes na restrições igual a (2,1). A base ótima do problema (18)-(21) é ótima para o novo problema?
Passo 1
O enunciado dá um problema de programação linear com três variáveis e duas restrições de tipo “<=\)”. O objetivo é maximizar
\[x_{1} - x_{2} + 2x_{3}
Para usar o método primal do simplex, vamos (a) introduzir as folgas s_{1},s_{2}\], (b) montar o tableau inicial, \text{(c)} escolher variável de entrada por coeficiente negativo no \(z-row e (d) pivotar até não haver mais coeficiente negativo no z-row.
em que a linha z armazena os \emph{reduced costs} -c_j. Como há coeficientes negativos em z nas colunas x_{1} e x_{3}, escolhemos primeiro x_{3} (maior valor absoluto de coeficiente negativo).
Passo 3
Pivot em coluna x_{3}, linha s_{2} (\min\{6/1,\;9/3\}=3). Dividindo a linha s_{2} por 3 e atualizando as demais linhas:
Pelo gráfico ou resolvendo o sistema de igualdades em \{y_{1}-y_{2}=1,\;y_{1}+3y_{2}=2\} obtém-se
y_{1}=\frac54,\quad y_{2}=\frac14,
com custo mínimo 6\cdot\frac54+9\cdot\frac14=39/4, igual ao primal.
Passo 7
Supondo que o RHS da primeira restrição (6) vire 7, o novo b=(7,9). A base ótima é dada pelas colunas de x_{1},x_{3}, cujo inverso B^{-1} multiplicado em b gera
x_{B}=B^{-1}b=(3,4)\ge0.
Como as reduções de custo não mudam com alteração de b, a base continua viável e ótima.
Passo 8
Se o vetor de custos virar c'=(2,1,1), mantida a base \{x_{1},x_{3}\}, calculamos o reduced cost de s_{2} e achamos