Lista 5 PL

Prévia do material em texto

ER500 - 1s2015
Lista 6: Faces e Direções
Questão 1: Considere o conjunto poliédrico abaixo:
x1 − x2 + x3 ≤ 10
2x1 − x2 + 2x3 ≤ 40
3x1 − 2x2 + 3x3 ≤ 50
x1, x2, x3 ≥ 0
Identifique as facetas, arestas, pontos extremos e direções extremas.
Questão 2: Seja
X = (x1, x2) : x1 − x2 ≤ 3, 2x1 + x2 ≤ 4, x1 ≥ −3
Ache todos os pontos extremos de X e represente x = (0, 1) com uma combinação linear convexa
dos pontos extremos.
Questão 3: Ache todos os pontos extremos e direções extremas dos conjuntos poliédricos:
(a) X = (x1, x2, x3, x4) : x1, x2, x3, x4 ≥ 0,−x1 + x2 − 2x3 ≤ 1,−2x1 − x3 + 2x4 ≤ 2
(b) X = (x1, x2, x3) : x1, x2, x3 ≥ 0, x1 + x2 + x3 ≤ 1,−x1 + 2x2 ≤ 4
(c) X = (x1, x2, x3) : x1, x2, x3 ≥ 0, x1 + x2 + x3 ≤ 5,−x1 + x2 + 2x3 ≤ 6
Questão 4: O seguinte conjunto possui alguma direção? Por que?
−x1 + x2 ≤ 4
x1 + x2 + x3 ≤ 6
x1, x2, x3 ≥ 0
Questão 5: Considere o seguinte problema:
max z = 2x1 + 3x2
s.a −x1 + x2 ≤ 0
−3x1 + 2x2 ≥ −3
x1, x2 ≥ 0
(a) Resolva o problema geometricamente no espaço (x1, x2).
(b) Identfique as regiões no espaço (x1, x2) onde as variáveis de folga x3 e x4 são iguais a zero.
1
(c) Para cada ponto extremo, identifique quais são as variáveis básicas e quais são as variáveis não básicas.
Questão 6:Considere o seguinte PPL:
min z = x1 − 2x2 − 3x3
s.a x1 + 2x2 + x3 ≤ 14
x1 + 2x2 + 4x2 ≥ 12
x1 − x2 + x3 = 2
x1, x2 livres, x3 ≤ −3
(a) Coloque o problema na forma padrão.
(b) Coloque o problema na forma canônica da minimização.
(c) Converta o problema em um problema de maximização.
Questão 7: Considere o seguinte problema
max z = x1 − x2
s.a −x1 + 2x2 ≤ 0
−3x1 + x2 ≥ −3
x1, x2 ≥ 0
(a) Resolva o problema geometricamente no espaço (x1, x2).
(b) Identifique as regiões no espaço (x1, x2) onde as variáveis de folga x3 e x4 são iguais a zero.
Questão 8: Seja xT =(5 4 5 0 0) uma solução factível do problema:
max z = 10x1 + 24x2 + 20x3 + 20x4 + 255
s.a x1 + x2 + 2x3 + 3x4 + 5x5 ≤ 19
2x1 + 4x2 + 3x3 + 2x4 + x5 ≤ 57
x1, x2, x3, x4, x5 ≥ 0
A partir dessa solução determine uma solução básica factível.
2