FC ConcursosFC Concursos

Questão FC236124

Considere a formulação de um problema de programação linear em notação matricial Maximizar Z = cx Sujeito a Ax ≤ b para x ≥ 0 onde: A é uma matriz (m x n), b é um vetor coluna (m x

Programação Linear

CESGRANRIO · 2012

Considere a formulação de um problema de programação linear em notação matricial

 

Maximizar Z = cx


Sujeito a Ax ≤ b para x ≥ 0


onde:


A é uma matriz (m x n), b é um vetor coluna (m x 1), c é um vetor linha (1 x n), x é um vetor coluna n x 1, e y é um vetor linha (1 x m)


O problema dual dessa formulação pode ser representado por

  1. Maximizar Z = xb      Sujeito a xA ≥ c para x ≥ 0 A é uma matriz (m x n), b é um vetor coluna (m x 1), c é um vetor linha (1 x n), x é um vetor coluna (n x 1), e y é um vetor linha (1 x m)
  2. Maximizar W = bx      Sujeito a Ax ≤ c para x ≤ 0 A é uma matriz (m x n), b é um vetor coluna (m x 1), c é um vetor linha (1 x n), x é um vetor coluna (n x 1), e y é um vetor linha (1 x m)
  3. Minimizar W = yb      Sujeito a yA ≥ c para y ≥ 0 A é uma matriz (m x n), b é um vetor coluna (m x 1), c é um vetor linha (1 x n), x é um vetor coluna (n x 1), e y é um vetor linha (1 x m)
  4. Minimizar W = yb      Sujeito a yA ≥ c para y ≥ 0 A é uma matriz (n x m), b é um vetor coluna (m x 1), c é um vetor linha (n x 1), x é um vetor coluna (n x 1), e y é um vetor linha (m x 1)
  5. Minimizar Z = cx      Sujeito a Ax ≤ b para x ≥ 0 A é uma matriz (n x 1), b é um vetor coluna (m x 1), c é um vetor linha (1 x n), x é um vetor coluna (n x 1), e y é um vetor linha (1 x m)
Mostrar resposta e comentário

Gabarito

Certo

Comentário do professor

Minimizar W = yb sujeito a yA ≥ c e y ≥ 0 é exatamente o dual do primal dado: \( \max Z = cx\) s. a. \(Ax \le b,\; x\ge0\).

Explicação curta: para qualquer vetor dual viável \(y\) com \(y\ge0\) e \(yA\ge c\), e qualquer \(x\) primal viável com \(x\ge0\) e \(Ax\le b\), vale

\( (yA - c)x \ge 0 \Rightarrow yAx \ge cx\), e como \(Ax\le b\) e \(y\ge0\) então \(yAx \le yb\). Assim \(cx \le yb\), mostrando que \(yb\) é um limite superior para \(Z\).

Dimensionalmente: \(y\) é linha \(1\times m\), \(b\) coluna \(m\times1\) (produto escalar), e \(yA\) resulta em \(1\times n\), compatível com \(c\) (\(1\times n\)).

Portanto a formulação apresentada na alternativa é a correta representação do problema dual.

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

Continue aprendendo