FC ConcursosFC Concursos

Questão FC236112

Considere o seguinte problema de Programação Linear: Maximize: Z = 2x1 + 3x2 - 4x3 Sujeito a x1 + x2 + 3x3 ≤ 15 x1 + 2x2 - x3 ≤ 20 x1 ≥ 0 x2 ≥ 0 x3 ≥ 0 Foi acrescentada uma variáve

Programação Linear

CESGRANRIO · 2012

Considere o seguinte problema de Programação Linear:


Maximize: Z = 2x1 + 3x2 - 4x3


Sujeito a


x1 + x2 + 3x3 ≤ 15
x1 + 2x2 - x3 ≤ 20
x1 ≥ 0
x2 ≥ 0
x3 ≥ 0


Foi acrescentada uma variável x4 ao problema, que passou a ser modelado da seguinte forma:


Maximize: Z = 2x1 + 3x2 - 4x3 + k. x4


Sujeito a


x1 + x2 + 3x3 - x4 ≤ 15
x1 + 2x2 - x3 + 2x4 ≤ 20
x1 ≥ 0
x2 ≥ 0
x3 ≥ 0


O valor máximo que o parâmetro k pode assumir sem alterar o valor ótimo da função objetivo encontrado para o problema original é

  1. 0
  2. 1
  3. 2
  4. 3
  5. 5
Mostrar resposta e comentário

Gabarito

B

Comentário do professor

Partimos da solução ótima do problema original: \((x_1,x_2,x_3)=(10,5,0)\), com base formada por \(x_1,x_2\) (ambas restrições ativas).

Calculemos o custo reduzido de \(x_4\). A base \(B\) tem colunas de \(x_1,x_2\): \(B=\begin{pmatrix}1&1\\1&2\end{pmatrix}\), com \(B^{-1}=\begin{pmatrix}2&-1\\-1&1\end{pmatrix}\). O vetor de coeficientes de \(x_4\) nas restrições é \(a_4=(-1,2)^T\).

Então \(B^{-1}a_4=( -4,\,3)^T\) e o produto com os custos básicos \(c_B=(2,3)\) dá \(c_BB^{-1}a_4=2(-4)+3(3)=1\).

O custo reduzido é \(r_4=c_4-c_BB^{-1}a_4=k-1\). Para que \(x_4=0\) permaneça ótimo (ou seja, não melhore a função objetivo), precisamos de \(r_4\le 0\), isto é, \(k\le 1\).

Logo, o maior valor de \(k\) que não altera o valor ótimo é 1.

Conteúdo do catálogo FC Concursos · Atualizado em

Continue aprendendo