Para quais dos seguintes problemas podemos usar o método dos elipsoides.
Justifique sua resposta. Caso positivo, sugere uma primeira n-esfera para começar o método.
(1) max z=x1+3 x2
x1+x2 >= 3 x1-2 x2 <= 2 -x1+2 x2 <= 4 x1,2 >= 0
(2) max z=x1+3 x2
x1+x2 <= 3
x1-2 x2 <= 2
-x1+2 x2 <= 4
x1,2 >= 0.
(3) max z=x1+3 x2
x1+x2 <= 3
x1-2 x2 >= 4
-x1+2 x2 <= 4
x1,2 >= 0.

Passo 1

O enunciado apresenta três problemas de programação linear no plano (x1,x2) com objetivo max z = x1+3x2 e diferentes conjuntos de restrições lineares. Queremos verificar em quais desses problemas podemos usar o método dos elipsoides. Para isso precisamos de dois fatos sobre o método:
1. O conjunto viável deve ser convexo e não vazio.
2. Precisamos conhecer uma bola (uma “ n-esfera”) que contenha todo o conjunto viável para usá-la como elipsoide inicial.

Passo 2

Problema (
Observe que a interseção das duas restrições
)
e
(ou )
é a faixa compreendida entre duas retas paralelas de inclinação . Acrescente : isso empurra o conjunto para cima/à direita, e a condição não impede que sigamos indo para mantendo todas as desigualdades. Logo o conjunto viável é convexo mas não é limitado.
Sem limite, não há uma bola conhecida que o contenha, então não podemos aplicar o método dos elipsoides no problema ( ).

Passo 3

Problema (
Aqui a primeira desigualdade define o triângulo ({x_{1},x_{2}\ge0,;x_{1}+x_{2}\le3}], que é compacto. As outras duas apenas cortam pedaços desse triângulo, mantendo-o limitado e não vazio. Portanto o conjunto é convexo, não vazio e compacto.
Isso satisfaz as condições do método dos elipsoides.
Para escolher uma -esfera inicial que contenha todo o conjunto viável, note que em qualquer ponto viável temos
Logo todo o conjunto está dentro do quadrado . Uma bola que contenha esse quadrado é, por exemplo,
Aqui o centro é e o raio .

Passo 4

Problema (
Da segunda restrição vem . Não existe que seja ao mesmo tempo e . Logo o conjunto viável é vazio. Sem ponto viável, não há o que otimizar e o método não se aplica.

Resposta

Podemos usar o método dos elipsoides apenas no problema ( 2).
Como primeira 2-esfera (bola em R^2) inicial, uma sugestão é
l,xinR^2m|l|x - (1,5,1,5)r|2<= tfrac3raiz2r,
pois contém todo o conjunto viável de ( 2).

Exercícios relacionados