FC ConcursosFC Concursos

Questão FC236130

Dado o problema de programação linear \(Min\, 3x_1-5x_2 \\ s.r. \\ -10x_1+2x_2=20\\6x_1-6x_2 \le 36 \\ x_1 \ge 0 \\ ∀x_2 \, ∈ \mathbb{R}\) O dual desse problema é dado por

Programação Linear

CESGRANRIO · 2010

Dado o problema de programação linear

 

\(Min\, 3x_1-5x_2 \\ s.r. \\ -10x_1+2x_2=20\\6x_1-6x_2 \le 36 \\ x_1 \ge 0 \\ ∀x_2 \, ∈ \mathbb{R}\)

 

O dual desse problema é dado por

  1.  \(Max \, 20y_1-36y_2 \\ s.r. \\ -10y_1-6y_2 \le 3 \\2y_1+6y_2=-5 \\ y_2 \ge 0 \\ ∀y_1 \, ∈ \mathbb{R}\)
  2.  \(Max\, 3y_1-5y_2 \\ s.r. \\ -10y_1-6y_2 \le 20 \\ 2y_1+6y_2=-36 \\ y_1 \ge 0, y_2 \ge 0\)
  3.  \(Max \, 3y_1-5y_2 \\ s.r. \\-10y_1-6y_2 \le 20 \\ 2y_1+6y_2 \le -36 \\ y_2 \ge 0 \\ ∀y_1 \, ∈ \mathbb{R}\)
  4.  \(Min \, 20y_1-36y_2 \\ s.r. \\ -10y_1-6y_2 \le 3 \\ 2y_1+6y_2=-5 \\ y_1 \ge 0,y_2 \ge 0\)
  5.  \(Min \, 3y_1-5y_2 \\ s.r. \\ -10y_1-6y_2 \le 20 \\ 2y_1+6y_2=-36 \\ y_2 \ge 0 \\ ∀y_1 \, ∈ \mathbb{R}\)
Mostrar resposta e comentário

Gabarito

A

Comentário do professor

Partindo do primal dado, associamos uma variável dual a cada restrição: \(y_1\) à igualdade (logo \(y_1\in\mathbb{R}\)) e \(y_2\) à desigualdade \(\le\) (portanto \(y_2\ge0\)).

O objetivo do dual é formado pelos lados-direitos das restrições do primal, resultando em \(Max\;20y_1-36y_2\).

As restrições do dual vêm das colunas da matriz de coeficientes do primal (transposta) e relacionam-se aos sinais das variáveis primais:

para \(x_1\) (com \(x_1\ge0\)) obtemos \( -10y_1-6y_2\le 3\);

para \(x_2\) (livre) obtemos igualdade \(2y_1+6y_2=-5\).

Assim, compilando estes elementos, chega-se exatamente ao dual \(Max\;20y_1-36y_2\) s.r. \( -10y_1-6y_2\le3,\;2y_1+6y_2=-5,\;y_2\ge0,\;y_1\in\mathbb{R}.\)

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

Continue aprendendo