(0.5 pontos) Um problema primal e seu dual podem ser ambos ilimitados.
◯ Certo. ◯ Errado.
◯ 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.
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
tal que . - 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
Considere o primal na forma de maximização
e o dual correspondente na forma de minimização
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 é factível para o primal e
é factível para o dual, então
Se
Prova simples e intuitiva (passo a passo):
- Como
e , multiplicando por obtemos . Escrevendo em notação transposta, isso é . - Como
e , então . - Juntando as duas desigualdades temos
.
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 com
arbitrariamente grandes:
. Se o dual tivesse alguma solução factível
, pela desigualdade fraca teríamos
para todo
factível, o que impede
de crescer sem limite (pois ficaria sempre ≤
, um número fixo). Logo, não pode existir
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.
Suponha, por absurdo, que o primal seja ilimitado (de maximização), ou seja, existem soluções factíveis
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.