(0.5 pontos) Um problema primal e seu dual podem ser ambos ilimitados.
◯ Certo. ◯ Errado.

Passo 1

Enunciado curto: pergunta se é possível que um problema primal e seu dual sejam ambos ilimitados (unbounded).
O que é pedido: responder “Certo” ou “Errado” e justificar.
Informações dadas: apenas a afirmação “Um problema primal e seu dual podem ser ambos ilimitados.” Não há dados numéricos nem figura.

Passo 2

Definições importantes (vou mastigar cada uma):
  • Um problema primal é dito ilimitado (unbounded) quando sua função objetivo pode crescer sem limite dentro do conjunto de soluções factíveis. Formalmente, para um problema de maximização, existe uma sequência de soluções factíveis x^{(k)} tal que c^T x^{(k)} \to +\infty.
  • Um problema (primal ou dual) é factível (feasible) quando existe pelo menos uma solução que satisfaz todas as restrições.
  • O dual aqui será o dual linear clássico associado ao primal; vou escrever uma forma padrão abaixo para ficar concreto.

Passo 3

Vou colocar uma formulação padrão (não muda o argumento, só facilita o raciocínio):
Considere o primal na forma de maximização
\max\{\,c^T x \mid A x \le b,\; x \ge 0\,\},
e o dual correspondente na forma de minimização
\min\{\,b^T y \mid A^T y \ge c,\; y \ge 0\,\}.
Isso é só para termos notação; a propriedade que vou usar vale para pares primal-dual equivalentes em qualquer convenção padrão.

Passo 4

Teorema chave (frase e prova curta, a famosa desigualdade fraca):
Se x é factível para o primal e y é factível para o dual, então
c^T x \le b^T y.
Prova simples e intuitiva (passo a passo):
  1. Como A x \le b e y \ge 0, multiplicando por y^T obtemos y^T A x \le y^T b. Escrevendo em notação transposta, isso é (A^T y)^T x \le b^T y.
  2. Como A^T y \ge c e x \ge 0, então (A^T y)^T x \ge c^T x.
  3. Juntando as duas desigualdades temos c^T x \le (A^T y)^T x \le b^T y.
    Essa é a desigualdade fraca (weak duality).

Passo 5

Agora uso essa desigualdade para responder à pergunta:
Suponha, por absurdo, que o primal seja ilimitado (de maximização), ou seja, existem soluções factíveis x com c^T x arbitrariamente grandes: c^T x \to +\infty. Se o dual tivesse alguma solução factível y, pela desigualdade fraca teríamos c^T x \le b^T y para todo x factível, o que impede c^T x de crescer sem limite (pois ficaria sempre ≤ b^T y, um número fixo). Logo, não pode existir y factível. Portanto, se o primal é ilimitado então o dual é necessariamente infactível. O mesmo raciocínio simétrico mostra que se o dual (minimização) é ilimitado para baixo então o primal é infactível.
Conclusão lógica: não é possível que ambos sejam ilimitados ao mesmo tempo — a existência de um limite infinito do objetivo de um lado força a infactibilidade do outro.

Passo 6

Observação final e moral do estudo:
  • O que pode acontecer é: (i) primal limitado e dual limitado com valores ótimos iguais (caso de óptimo alcançado), (ii) primal ilimitado e dual infactível, (iii) primal infactível e dual ilimitado (dependendo da convenção), (iv) ambos infactíveis. Mas “ambos ilimitados” não ocorre. Isso é uma coisa que cai direto em prova: use a desigualdade fraca como argumento curto e elegante.

Resposta

Errado.

Exercícios relacionados