Questão 14

Considere o PPL
min -x1-2 x2 x1+x2 <= 6 -x1+2 x2 <= 6 x1, x2 >= 0
(1) Defina o conjunto viável do PPL.
(2) Identifique todos os pontos extremos do PPL.

Passo 1

O enunciado trata de um problema de programação linear (PL) em duas variáveis, com a função-objetivo
min -x1-2x2
sujeita às restrições lineares
x1+x2<=6, -,x1+2,x2<=6, x1>=0,;x2>=0
Vamos determinar o conjunto viável (interseção desses meio-planos no x1x2) e depois encontrar seus pontos extremos pela interseção das retas que formam a fronteira.

Passo 2

O conjunto viável S é
S = l(x1,x2)inR^2mid x1+x2<=6,;-,x1+2x2<=6,;x1>=0,;x2>=0r

Passo 3

Para achar os vértices de [S), resolvemos as interseções de cada par de restrições de igualdade e verificamos quais satisfazem todas as desigualdades:
. Interseção de e :
verifica e , logo é viável.
. Interseção de e :
verifica e , logo é viável.
. Interseção de e :
que satisfaz todas as desigualdades e (2,4\ge0].
. Interseção de e :
é trivialmente viável.
Todas as outras interseções de pares de retas caem fora de alguma restrição, portanto os pontos extremo de são os acima.

Passo 4

Concluímos que os pontos extremos do conjunto viável são
(0,0), (6,0), (2,4), (0,3)

Resposta

( 1) S=(x1,x2)inR^2mid x1+x2<=6,;-x1+2x2<=6,;x1>=0,;x2>=0
( 2) Os pontos extremos são (0,0), (6,0), (2,4) e (0,3).

Exercícios relacionados