Questão 16
Considere o seguinte PPL
(1) Defina o conjunto viável para o PPL.
(2) Defina uma solução viável para o PPL.
(3) Defina uma solução ótima para o PPL.
(4) Quais casos de soluções podem ocorrer para o PPL. Caracterize geometricamente cada caso.
(2) Defina uma solução viável para o PPL.
(3) Defina uma solução ótima para o PPL.
(4) Quais casos de soluções podem ocorrer para o PPL. Caracterize geometricamente cada caso.
Passo 1
O enunciado apresenta um problema de programação linear (PPL) no formato
e pede para darmos quatro definições: (1) conjunto viável, (2) solução viável, (3) solução ótima e (4) caracterização dos possíveis casos de solução, com descrição geométrica.
Passo 2
O conjunto viável é o conjunto de todos os vetores
que satisfazem simultaneamente as restrições. Em notação,
Geometricamente,
é a interseção do hiperplano afim definido por
com o ortante não negativo
, o que forma um politopo (caso seja limitado) ou um politopo não limitado.
Passo 3
Uma solução viável é qualquer vetor
que pertença a
. Ou seja,
Intuitivamente, é qualquer ponto do politopo de restrições.
Passo 4
Uma solução ótima é uma solução viável que maximiza o valor da função objetivo
sobre todo o conjunto viável. Formalmente,
é ótima se
Geomtricamente, o hiperplano de nível
é deslocado até tocar o politopo
na(s) ponto(s) ótimos.
Passo 5
Podem ocorrer quatro situações distintas:
- Inviabilidade:
. Não há interseção entre o hiperplano e o ortante . Geometricamente, não existe ponto que satisfaça todas as restrições. - Ilimitabilidade (unboundedness):
mas a função objetivo não é limitada acima em . Geometricamente, há uma direção de “fuga” dentro de tal que , e deslocando-se indefinidamente nessa direção . - Ótimo único: existe exatamente um vértice
onde o hiperplano de nível tangencia o politopo. Geometricamente, o hiperplano toca num único ponto extremo. - Múltiplas soluções ótimas: existe um aresta ou face de
ao longo da qual o hiperplano é paralelo às restrições de aresta/face. Geometricamente, toda essa aresta ou face é formada por soluções que atingem o mesmo valor ótimo.
Resposta
(1)
(2) viável se
(3) ótima se
e
para todo
(4) Os casos são: inviabilidade ( ), ilimitabilidade (
), ótimo único (toque em um vértice) e múltiplas ótimas (toque ao longo de uma aresta/face).
(2)
(3)
(4) Os casos são: inviabilidade (