(1.5 pontos) Um problema dual na forma padrão possui cinco variáveis não-negativas e três restrições. A solução ótima do dual é
. Qual das opções é verdade sobre o problema primal?
A. No máximo três folgas das restrições do problema primal são não-nulas.
B. O problema primal possui três variáveis e cinco restrições.
C. As variáveis no primal são não-negativas.
D. O problema primal pode ter valor ótimo
(“mais infinito”) ou
(“menos infinito”).
E. Pelo menos três folgas da restrições do problema primal precisam ter valor igual a zero.
A. No máximo três folgas das restrições do problema primal são não-nulas.
B. O problema primal possui três variáveis e cinco restrições.
C. As variáveis no primal são não-negativas.
D. O problema primal pode ter valor ótimo
E. Pelo menos três folgas da restrições do problema primal precisam ter valor igual a zero.
Passo 1
O enunciado nos dá as seguintes informações e pergunta uma única coisa: qual das opções A–E é verdadeira sobre o problema primal, sabendo que
e que a solução ótima do dual é
Informações relevantes listadas:
- O dual tem
variáveis (todas com limite de não-negatividade, segundo o enunciado). - O dual tem
restrições. - Foi dada a solução ótima do dual (valores dos
). - A pergunta é: dentre as opções A, B, C, D, E, qual é verdade sobre o primal?
Passo 2
Relação entre números de variáveis/restrições do primal e do dual (a ideia fundamental):
- Cada restrição do primal corresponde a uma variável do dual.
- Cada variável do primal corresponde a uma restrição do dual.
Ou seja, se o dual temvariáveis e restrições, então o primal tem variáveis e restrições. Essa relação vem diretamente da construção do dual: as dimensões se “transpõem” (matriz vira no problema oposto).
Aplicando ao nosso caso:
- O dual tem
variáveis o primal tem restrições. - O dual tem
restrições o primal tem variáveis.
Portanto, do ponto de vista de tamanho, o primal possui
variáveis e
restrições. Isso corresponde exatamente à opção B.
Passo 3
Vou agora explicar um conceito útil que também aparece nas opções: o que são “folgas” (slacks) e a relação com as variáveis do dual (teorema da complementaridade).
- Quando temos uma restrição do primal do tipo “
”, podemos introduzir uma variável de folga tal que a igualdade vire . Essa mede quanto a restrição está “folgada” (não exatamente igual). - A complementaridade (condição de complementaridade entre soluções ótimas primal/dual) diz, para cada índice
correspondente a uma restrição primal e à variável dual , que em soluções ótimas vale
Isto é: se
então necessariamente
; se
então
. Essa é uma regra ponto-a-ponto entre cada variável dual e a folga da restrição primal correspondente.
Passo 4
Aplicando complementaridade aos dados do enunciado (aqui usamos os valores do vetor
que foram dados):
- Os valores dados do dual são
- Observamos que
e apenas .
Pela complementaridade, para as folgas(que correspondem às restrições do primal) temos
Logo
. O único
que pode ser não-nulo é
.
Passo 5
Consequências numéricas e interpretação das opções A–E com base no que já deduzimos:
- Existem
folgas . Com base nos dados, sabemos que pelo menos dessas folgas são zero ( são obrigatoriamente zero). Portanto: - A afirmação E (“Pelo menos três folgas … precisam ter valor igual a zero”) é verdadeira (na verdade, até mais forte: pelo menos quatro são zero).
- A afirmação A (“No máximo três folgas … são não-nulas”) é também verdadeira, pois, como só
pode ser não-nula, o número de folgas não-nulas é no máximo , o que satisfaz “no máximo três”.
- A afirmação B (“O problema primal possui três variáveis e cinco restrições”) é verdade pelos argumentos de dimensão do Passo 2.
- A afirmação C (“As variáveis no primal são não-negativas”) não pode ser assegurada apenas com a informação dada: a não-negatividade das variáveis primais depende da forma padrão usada e nem sempre é garantida apenas porque o dual tem variáveis não-negativas — portanto não podemos afirmar C com certeza.
- A afirmação D ("O problema primal pode ter valor ótimo
ou ") é equivocada: como o dual tem uma solução ótima finita (os fornecidos), pelo teorema da dualidade forte o primal também tem valor ótimo finito e atingido (ou, minimamente, não pode ser um caso de primal ilimitado contraposto a dual ótimo). Logo D não é correta no contexto dado.
Passo 6
Comparando as opções, as que são verdadeiras com base nas informações são A, B e E (com B sendo uma relação estrutural direta e E/A sendo consequências da complementaridade; E é verdadeira e até conservadora em relação ao que os dados implicam). Entre todas, a afirmação que responde diretamente e sem ambiguidade à pergunta sobre o primal — usando apenas a informação inicial sobre números de variáveis e restrições do dual — é a opção B: ela descreve exatamente quantas variáveis e restrições o primal possui.
Resposta
B