Para quais dos seguintes problemas podemos usar o método dos elipsoides.
Justifique sua resposta. Caso positivo, sugere uma primeira -esfera para começar o método.
(1)
(2) .
(3) .
Passo 1
O enunciado apresenta três problemas de programação linear no plano com objetivo 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: . O conjunto viável deve ser convexo e não vazio. . Precisamos conhecer uma bola (uma “-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 é