(1 ponto) Seja § um PPL, seja (D1) o dual de §, e seja (D2) o dual de (D1).
A. (D1) é igual a (D2), pois é redundante aplicar o dual duas vezes.
B. § é diferente de (D2), mas eles são equivalentes.
C. § é igual a (D2).
D. Não é possível encontrar (D2).
E. Nenhuma das anteriores.

Passo 1

O enunciado dá as seguintes informações e pede que a gente escolha a alternativa correta:
  • Tem-se um problema linear original chamado (P) (um PPL).
  • (D1) é o dual de (P).
  • (D2) é o dual de (D1) (ou seja, o dual do dual).
    As alternativas são:
    A. (D1) é igual a (D2), pois é redundante aplicar o dual duas vezes.
    B. (P) é diferente de (D2), mas eles são equivalentes.
    C. (P) é igual a (D2).
    D. Não é possível encontrar (D2).
    E. Nenhuma das anteriores.

Passo 2

Primeiro, vamos lembrar o que significa formar o dual de um problema linear de forma explícita (aqui vou usar a forma canônica mais comum — é a que os professores adoram pedir na prova). Considere o problema primal escrito assim:
\text{maximizar } z = c^{T}x
\text{sujeito a } Ax \le b
x \ge 0.
Explicando os símbolos:
  • \,x é o vetor de variáveis do primal; cada componente é uma variável x_j.
  • \,c é o vetor de coeficientes da função objetivo; c_j é o coeficiente de x_j.
  • \,A é a matriz de coeficientes das restrições; a_{ij} é o coeficiente da restrição i na variável x_j.
  • \,b é o vetor do lado direito; b_i é o limite da restrição i.
A regra prática para construir o dual é: cada restrição do primal vira uma variável do dual, cada variável do primal vira uma restrição do dual, sinais e tipos das desigualdades trocam de forma previsível. Para a forma acima (max com \le e x\ge0) o dual fica:
\text{minimizar } w = b^{T}y
\text{sujeito a } A^{T}y \ge c
y \ge 0,
onde y tem uma componente y_i para cada restrição i do primal.

Passo 3

Agora vamos formar o dual do dual (ou seja, o dual de (D1)) de modo explícito, usando índices para ver claramente que voltamos ao primal. Escrevemos o primal componentemente:
para cada restrição i temos
\sum_{j} a_{ij} x_{j} \le b_{i}.
O dual correspondente tem variáveis y_{i} e, para cada variável j do primal, uma restrição
\sum_{i} a_{ij} y_{i} \ge c_{j},
com objetivo \text{min } \sum_{i} b_{i} y_{i} e y_{i}\ge0.
Agora trate o problema (D1) (o dual) como se fosse o “primal” para formar seu dual. Ou seja, na perspectiva de (D1) há:
  • variáveis y_{i};
  • para cada j existe a restrição \sum_{i} a_{ij} y_{i} \ge c_{j}.
Ao formar o dual de (D1) (que chamamos de (D2)), cada restrição indexada por j vira uma variável nova — vou chamar essa variável de x'_{j}. E cada variável y_{i} do (D1) vira uma restrição em (D2). Escrevendo isso explicitamente, o objetivo de (D1) era minimizar \sum_{i} b_{i} y_{i}; ao formar o dual disso (que será um problema de maximização) obtemos o objetivo
\text{maximizar } \sum_{j} c_{j} x'_{j}.
As restrições de (D2) vêm da associação das colunas: para cada índice i (cada variável y_{i} do (D1)) teremos
\sum_{j} a_{ij} x'_{j} \le b_{i}.
E implicitamente exige-se x'_{j} \ge 0 (pela construção padrão quando a restrição do (D1) era do tipo \ge). Note que essas equações são exatamente as mesmas do primal original com x'_{j} no lugar de x_{j}:
\text{maximizar } \sum_{j} c_{j} x'_{j}
\text{sujeito a } \sum_{j} a_{ij} x'_{j} \le b_{i}\quad\text{para todo }i
x' \ge 0.
Portanto, (D2) tem as mesmas equações, mesmos coeficientes e mesma forma que (P); só renomeamos x'_{j} para x_{j} se quisermos identificar exatamente as variáveis.

Passo 4

Para deixar tudo bem claro e amistoso, um mini-exemplo numérico (pra você visualizar): suponha
\text{max } z = 2x_{1}+3x_{2}
\text{s.a. } x_{1}+2x_{2} \le 4,
3x_{1}+x_{2} \le 3,
x_{1},x_{2}\ge0.
O dual (D1) tem variáveis y_{1},y_{2} e é
\text{min } 4y_{1}+3y_{2}
\text{s.a. } y_{1}+3y_{2} \ge 2,
2y_{1}+y_{2} \ge 3,
y_{1},y_{2}\ge0.
Agora o dual de (D1) (isto é, (D2)) atribui uma variável a cada uma das últimas restrições (duas restrições → duas variáveis x'_{1},x'_{2}) e volta a ser exatamente o problema original em x'_{1},x'_{2}. Ou seja, na prática você recupera o mesmo sistema de equações com os mesmos coeficientes. Isso ilustra que não houve perda de informação e que a operação “dual” é uma involução (aplicá-la duas vezes retorna o problema original).

Passo 5

Comentário sobre igualdade vs equivalência: tecnicamente, ao formar o dual do dual você pode achar o mesmo conjunto de equações e coeficientes que estavam em (P). Em linguagem matemática comum dizemos que o dual do dual é o primal — ou seja, (D2) coincide com (P). Em provas costuma-se aceitar tanto a afirmação “são iguais” quanto “são equivalentes” dependendo da notação, mas a forma canônica mostra igualdade estrutural: mesmos coeficientes, mesmas restrições, mesmos sinais.

Resposta

C. (P) é igual a (D2).

Exercícios relacionados