(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.
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
(um PPL). -
é o dual de . -
é o dual de (ou seja, o dual do dual).
As alternativas são:
A.é igual a , pois é redundante aplicar o dual duas vezes.
B.é diferente de , mas eles são equivalentes.
C.é igual a .
D. Não é possível encontrar.
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:
Explicando os símbolos:
-
é o vetor de variáveis do primal; cada componente é uma variável . -
é o vetor de coeficientes da função objetivo; é o coeficiente de . -
é a matriz de coeficientes das restrições; é o coeficiente da restrição na variável . -
é o vetor do lado direito; é o limite da restrição .
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
e
) o dual fica:
onde
tem uma componente
para cada restrição
do primal.
Passo 3
Agora vamos formar o dual do dual (ou seja, o dual de
) de modo explícito, usando índices para ver claramente que voltamos ao primal. Escrevemos o primal componentemente:
para cada restrição temos
para cada restrição
O dual correspondente tem variáveis
e, para cada variável
do primal, uma restrição
com objetivo
e
.
Agora trate o problema
(o dual) como se fosse o “primal” para formar seu dual. Ou seja, na perspectiva de
há:
- variáveis
; - para cada
existe a restrição .
Ao formar o dual de
(que chamamos de
), cada restrição indexada por
vira uma variável nova — vou chamar essa variável de
. E cada variável
do
vira uma restrição em
. Escrevendo isso explicitamente, o objetivo de
era minimizar
; ao formar o dual disso (que será um problema de maximização) obtemos o objetivo
As restrições de
vêm da associação das colunas: para cada índice
(cada variável
do
) teremos
E implicitamente exige-se
(pela construção padrão quando a restrição do
era do tipo
). Note que essas equações são exatamente as mesmas do primal original com
no lugar de
:
Portanto,
tem as mesmas equações, mesmos coeficientes e mesma forma que
; só renomeamos
para
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
O dual
tem variáveis
e é
Agora o dual de
(isto é,
) atribui uma variável a cada uma das últimas restrições (duas restrições → duas variáveis
) e volta a ser exatamente o problema original em
. 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
. Em linguagem matemática comum dizemos que o dual do dual é o primal — ou seja,
coincide com
. 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.
é igual a
.