Flashcard FC241296
Como se calcula o custo reduzido de uma variável não-básica e qual condição sobre ele garante que a solução básica ótima não se altera em um problema de maximização?
Programação Linear
CESGRANRIO · 2012
Como se calcula o custo reduzido de uma variável não-básica e qual condição sobre ele garante que a solução básica ótima não se altera em um problema de maximização?
Mostrar resposta e comentário
Resposta
r_j = c_j - c_B B^{-1}a_j e, para maximização, a solução ótima não muda se r_j ≤ 0.Explicação:
O vetor c_B contém os custos das variáveis básicas, B é a matriz base e a_j é a coluna da variável não-básica j nas restrições. Calcula-se \(B^{-1}a_j\), depois o produto escalar \(c_B(B^{-1}a_j)\) e finalmente \(r_j=c_j-c_BB^{-1}a_j\). Se \(r_j\le 0\) (maximização), introduzir j não aumenta Z.
Exemplo:
Se \(B=\begin{pmatrix}1&2\\0&1\end{pmatrix}\), então \(B^{-1}=\begin{pmatrix}1&-2\\0&1\end{pmatrix}\).
Se \(c_B=(4,2)\) e \(a_j=(3,1)^T\), então
\(B^{-1}a_j=\begin{pmatrix}1&-2\\0&1\end{pmatrix}\begin{pmatrix}3\\1\end{pmatrix}=\begin{pmatrix}1\\1\end{pmatrix}\).
Logo \(c_BB^{-1}a_j=4\cdot1+2\cdot1=6\).
Se \(c_j=5\) então \(r_j=5-6=-1\le0\) → variável j não melhora a solução;
Se \(c_j=7\) então \(r_j=7-6=1>0\) → variável j entra na base e melhora Z.
Veja como foi cobrado:
https://flashcardsconcursos.com.br/portal/flashcard/236112
Conteúdo do catálogo FC Concursos · Atualizado em