(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 é y_{1}=3, y_{2}=1, y_{3}=1, y_{4}=0, y_{5}=7. 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 +\infty (“mais infinito”) ou -\infty (“menos infinito”).
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
\text{o problema dual (na forma padrão) tem }5\text{ variáveis não-negativas e }3\text{ restrições}ãáãçõ
e que a solução ótima do dual é
y_{1}=3,\; y_{2}=1,\; y_{3}=1,\; y_{4}=0,\; y_{5}=7.
Informações relevantes listadas:
  • O dual tem 5 variáveis (todas com limite de não-negatividade, segundo o enunciado).
  • O dual tem 3 restrições.
  • Foi dada a solução ótima do dual (valores dos y_i).
  • 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 tem n_D variáveis e m_D restrições, então o primal tem m_D variáveis e n_D restrições. Essa relação vem diretamente da construção do dual: as dimensões se “transpõem” (matriz A vira A^\top no problema oposto).
Aplicando ao nosso caso:
  • O dual tem 5 variáveis \Rightarrow o primal tem 5 restrições.
  • O dual tem 3 restrições \Rightarrow o primal tem 3 variáveis.
Portanto, do ponto de vista de tamanho, o primal possui 3 variáveis e 5 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 “ \le”, podemos introduzir uma variável de folga s_i\ge0 tal que a igualdade vire \text{(esquerda)} + s_i = \text{(direita)}. Essa s_i 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 i correspondente a uma restrição primal e à variável dual y_i, que em soluções ótimas vale
y_i \cdot s_i = 0.
Isto é: se y_i>0 então necessariamente s_i=0; se s_i>0 então y_i=0. 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 y que foram dados):
  • Os valores dados do dual são \;y_{1}=3,\; y_{2}=1,\; y_{3}=1,\; y_{4}=0,\; y_{5}=7.
  • Observamos que y_1>0,\; y_2>0,\; y_3>0,\; y_5>0 e apenas y_4=0.
    Pela complementaridade, para as folgas s_i (que correspondem às 5 restrições do primal) temos
y_i>0 \Rightarrow s_i=0.
Logo s_1=0,\; s_2=0,\; s_3=0,\; s_5=0. O único s_i que pode ser não-nulo é s_4.

Passo 5

Consequências numéricas e interpretação das opções A–E com base no que já deduzimos:
  • Existem 5 folgas s_1,\dots,s_5. Com base nos y_i dados, sabemos que pelo menos 4 dessas folgas são zero ( s_1,s_2,s_3,s_5 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ó s_4 pode ser não-nula, o número de folgas não-nulas é no máximo 1, 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 +\infty ou -\infty") é equivocada: como o dual tem uma solução ótima finita (os y_i 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

Exercícios relacionados