Programação Linear 05

Prévia do material em texto

ENP153 –Programação Linear
Aula 05 –Geometria de Programação Linear
POLIEDROS E CONJUNTOS CONVEXOS
Definição 01
 Um poliedro é um conjunto que pode ser descrito
por, 𝑥 ∈ 𝑅𝑛|𝐴𝑥 ≥ 𝑏 onde 𝐴 é uma matriz
𝑚 × 𝑛 , e 𝑏 é um vetor em 𝑅𝑛.
POLIEDROS E CONJUNTOS CONVEXOS
Definição 02
 Um conjunto 𝑆 ⊂ 𝑅𝑛 é limitado se existe uma
constante 𝐾 tal que o valor absoluto de toda
componente de todo elemento de 𝑆 é menor que,
ou igual, a𝐾.
POLIEDROS E CONJUNTOS CONVEXOS
Definição 03
 Seja 𝑎 um vetor em 𝑅𝑛, não nulo, e 𝑏 um escalar:
a. O conjunto 𝑥 ∈ 𝑅𝑛|𝑎′𝑥 = 𝑏 é um
hiperplano
b. O conjunto 𝑥 ∈ 𝑅𝑛|𝑎′𝑥 ≥ 𝑏 é um semi-
espaço
POLIEDROS E CONJUNTOS CONVEXOS
Definição 04
 Seja 𝛽1, … , 𝛽𝑛 semi-espaços em 𝑅
𝑛, um poliedro
é dado por 𝛽1 ∩ 𝛽2 ∩⋯∩ 𝛽𝑛 , em que 𝑛 é um
escalar finito.
POLIEDROS E CONJUNTOS CONVEXOS
POLIEDROS E CONJUNTOS CONVEXOS
Definição 05
 Um conjunto 𝑆 ⊂ 𝑅𝑛 é convexo se, para qualquer
𝑥, 𝑦 ∈ 𝑆 e qualquer 𝜆 ∈ 0,1 temos que 𝜆𝑥 +
1 − 𝜆 𝑦 também pertence a 𝑆
POLIEDROS E CONJUNTOS CONVEXOS
POLIEDROS E CONJUNTOS CONVEXOS
Definição 06
 Sejam 𝑥1, … , 𝑥𝑘 vetores em 𝑅
𝑛 e 𝜆1, … , 𝜆𝑘
escalares não negativos em queσ𝑘 = 1:
a. O vetor σ𝑖∈𝐾 𝜆𝑖𝑥𝑖é a combinação convexa de
𝑥1, … , 𝑥𝑘
b. A envoltória convexa dos vetores 𝑥1, … , 𝑥𝑘 é o
conjunto de todas as combinações convexas
destes vetores
POLIEDROS E CONJUNTOS CONVEXOS
POLIEDROS E CONJUNTOS CONVEXOS
Teorema 01
 Poliedros são conjuntos convexos
 A interseção de conjuntos convexos é convexa
 A combinação convexa de um número finito de
elementos de um conjunto convexo 𝑆, sempre
pertence a 𝑆
 A envoltória convexa de um número finito de
vetores é um conjunto convexo, logo, é um
poliedro.
PONTOS EXTREMOS E VÉRTICES
Definição 07
 Sejam 𝑃 um poliedro, e 𝑥 ∈ 𝑃, 𝑥 é um ponto extremo
de 𝑃 se não podemos encontrar dois vetores 𝑦, 𝑧 ∈ 𝑃,
diferentes de 𝑥, e um escalar 𝜆 ∈ 0,1 tal que 𝑥 = 𝜆𝑦 +
1 − 𝜆 𝑧
PONTOS EXTREMOS E VÉRTICES
PONTOS EXTREMOS E VÉRTICES
Definição 08
 Seja um poliedro definido pelas seguintes
restrições de desigualdades e igualdades:
 𝑎𝑖
′𝑥 ≥ 𝑏𝑖 , 𝑖 ∈ 𝑀1
 𝑎𝑖
′𝑥 ≤ 𝑏𝑖 , 𝑖 ∈ 𝑀2
 𝑎𝑖
′𝑥 = 𝑏𝑖 , 𝑖 ∈ 𝑀3
 𝑎𝑖 ∈ 𝑅
𝑛, 𝑏𝑖 é um conjunto escalar qualquer
 Se um vetor 𝑥′ satisfaz 𝑎𝑖
′𝑥′ = 𝑏𝑖 para algum 𝑖 ∈
𝑀1, 𝑀2, 𝑀3 , então a restrição correspondente está
ativa em 𝑥′.
PONTOS EXTREMOS E VÉRTICES
PONTOS EXTREMOS E VÉRTICES
Definição 09
 Seja um poliedro 𝑃 definido por restrições de
igualdade e desigualdade, e seja 𝑥′ um elemento
de 𝑅𝑛:
a. O vetor 𝑥′ é uma solução básica se todas as
restrições de igualdade estão ativas
b. Se 𝑥′ é uma solução básica que satisfaz todas as
restrições de desigualdade, então ela é uma
solução básica factível
PONTOS EXTREMOS E VÉRTICES
Teorema 02
 Seja 𝑃 um poliedro não vazio e 𝑥′ ∈ 𝑃. As
seguintes afirmações são equivalentes:
 𝑥′ é um vértice
 𝑥′ é um ponto extremo
 𝑥′ é uma solução básica factível
DEFINIÇÃO DO POLIEDRO NA FORMA PADRÃO
Pela D.01 temos que um poliedro é um conjunto
que pode ser descrito por, 𝑥 ∈ 𝑅𝑛|𝐴𝑥 ≥ 𝑏 onde 𝐴 é
uma matriz 𝑚 × 𝑛 , e 𝑏 é um vetor em 𝑅𝑛.
 As 𝑚 linhas de A devem ser linearmente independentes
entre si
 A dependência linear entre elas demonstra redundância
de equações
DEFINIÇÃO DO POLIEDRO NA FORMA PADRÃO
Dependência e independência linear
 Considere a seguinte matriz 𝐴:
 𝐴 =
1 1 0
1 0 1
5 2 3
 𝐴 é LI ou LD?
DEFINIÇÃO DO POLIEDRO NA FORMA PADRÃO
Dependência e independência linear
 Considere a seguinte matriz 𝐴:
 𝐴 =
1 1 0
1 0 1
5 2 3
×
𝑣1
𝑣2
𝑣3
 𝐴 é LI ou LD?
 2𝑣1 + 3𝑣2 − 𝑣3 = 0 → logo 𝐴 é LD
DEFINIÇÃO DO POLIEDRO NA FORMA PADRÃO
Teorema 03
 Seja um espaço vetorial 𝑉 e 𝑣1, 𝑣2, … , 𝑣3 ∈ 𝑉
 𝑣1 e 𝑣2, não nulos, são LD se, e somente só, 𝑣1 é
múltiplo escalar de 𝑣2, ou seja, 𝑣1 = 𝛼𝑣2