Questão 12

Mostre que o conjunto de soluções viáveis do PPL a seguir é um conjunto convexo.
min & c^T x & A x=b & x >= 0

Passo 1

O enunciado pede para mostrar que o conjunto das soluções viáveis do problema
min;&c^Tx, &Ax = b, &x >= 0
é convexo. O que precisamos usar é a definição de conjunto convexo e o fato de que tanto um hiperplano definido por Ax=b quanto o ortantede x>=0 são conjuntos convexos, e que a interseção de conjuntos convexos é convexa.

Passo 2

Mostramos primeiro que o conjunto
H = ,xinR^n mid Ax = b
é convexo. Tome quaisquer x,yin H e um escalar lambda com 0<=lambda<=1. Então
Al(lambda x + (1-lambda)yr) = lambda,A x + (1-lambda),A y = lambda b + (1-lambda)b = b,
logo lambda x + (1-lambda)yin H. Isso mostra que H é convexo (é um conjunto afim).

Passo 3

Agora mostramos que o ortante
O = ,xinR^n mid x >= 0
é convexo. Sejam x,yin O e 0<=lambda<=1. Como todas as componentes de x e y são não negativas, cada componente de
lambda x + (1-lambda)y também é não negativa. Logo lambda x + (1-lambda)yin O. Assim O é convexo.

Passo 4

O conjunto de soluções viáveis é
F = H ,cap, O
Como H e O são convexos e a interseção de conjuntos convexos é convexa, concluímos que F é convexo.

Resposta

O conjunto viável do PPL, dado por xmid Ax=b,;x>=0, é convexo porque é a interseção de dois conjuntos convexos.

Exercícios relacionados