Questão 16

Considere o seguinte PPL
max & c^x & A x=b & x >= 0
(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.

Passo 1

O enunciado apresenta um problema de programação linear (PPL) no formato
max & c^Tx sujeito a & Ax = b, & x >= 0,
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 xinR^n que satisfazem simultaneamente as restrições. Em notação,
F ;=;,xinR^n mid Ax=b,;x>= 0
Geometricamente, F é a interseção do hiperplano afim definido por Ax=b com o ortante não negativo xmid x>=0, o que forma um politopo (caso seja limitado) ou um politopo não limitado.

Passo 3

Uma solução viável é qualquer vetor bar x que pertença a F. Ou seja,
bar x é viável Long<=ftrightarrow Abar x=bebar x>=0 éá
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 c^Tx sobre todo o conjunto viável. Formalmente, hat x é ótima se
hat xinF e c^That x ;>=; c^Tx forall,xinF
Geomtricamente, o hiperplano de nível c^Tx = gamma é deslocado até tocar o politopo F na(s) ponto(s) ótimos.

Passo 5

Podem ocorrer quatro situações distintas:
  1. Inviabilidade: F=emptyset. Não há interseção entre o hiperplano Ax=b e o ortante x>=0. Geometricamente, não existe ponto que satisfaça todas as restrições.
  2. Ilimitabilidade (unboundedness): Fneqemptyset mas a função objetivo não é limitada acima em F. Geometricamente, há uma direção de “fuga” d dentro de F tal que c^Td>0, e deslocando-se indefinidamente nessa direção c^Txto+infty.
  3. Ótimo único: existe exatamente um vértice hat xinF onde o hiperplano de nível tangencia o politopo. Geometricamente, o hiperplano c^Tx=gamma toca F num único ponto extremo.
  4. Múltiplas soluções ótimas: existe um aresta ou face de F ao longo da qual o hiperplano c^Tx=gamma é 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) F=xmid Ax=b,;x>=0
(2) bar x viável se bar xinF
(3) hat x ótima se hat xinF e c^That x>= c^Tx para todo xinF
(4) Os casos são: inviabilidade ( F=emptyset), ilimitabilidade ( c^Txto+infty), ótimo único (toque em um vértice) e múltiplas ótimas (toque ao longo de uma aresta/face).

Exercícios relacionados