Programação Linear 08

Prévia do material em texto

ENP153 –Programação Linear
Aula 08 – Método de eliminação de Fourier-Motzkin
ELIMINAÇÃO DE FOURIER-MOTZKIN
 Um sistema de inequações lineares é um conjunto de inequações
lineares nas mesmas variáveis:
 No qual 𝑥1, … , 𝑥𝑛 são as variáveis, 𝑎11, … , 𝑎𝑚𝑛 são os coeficientes
lineares do sistema de inequações e 𝑏1, … , 𝑏𝑚 são os termos
constantes
ELIMINAÇÃO DE FOURIER-MOTZKIN
 Esse sistema obtém o seguinte formato matricial:
ELIMINAÇÃO DE FOURIER-MOTZKIN
 Seja o sistema de inequações lineares 𝐴𝑥 ≤ 𝑏 , representado
anteriormente:
 Para cada 𝑖, onde 𝑎𝑖1 ≠ 0, podemos multiplicar cada uma das
inequações por
1
𝑎𝑖1
, deixando o valor do coeficiente de 𝑥1 como 0
ou±1.
ELIMINAÇÃO DE FOURIER-MOTZKIN
 Onde 𝐼− = 𝑖: 𝑎𝑖1 < 0 , ou seja, as inequações onde os
coeficientes de 𝑥1 são negativos, 𝐼
+ = 𝑖: 𝑎𝑖1 > 0 , ou seja, as
inequações onde os coeficientes de 𝑥1 são positivos e 𝐼
0 =
𝑖: 𝑎𝑖1 = 0 , ou seja, as inequações onde os coeficientes de 𝑥1 são
nulos, deve-se fazer 𝑎𝑖𝑗
′ =
𝑎𝑖𝑗
𝑎𝑖1
e 𝑏𝑖
′ =
𝑏𝑖
𝑏𝑖1
.
ELIMINAÇÃO DE FOURIER-MOTZKIN
 Assim, o conjunto de índices da linha 𝐼 = 1,…𝑚 é particionado
nos subconjuntos 𝐼−, 𝐼+ e 𝐼0, sendo que algum destes pode ser
vazio. Daqui resulta que 𝑥1, … , 𝑥𝑛 é uma solução do sistema
original se, e somente se, 𝑥1, … , 𝑥𝑛 satisfaz a seguinte restrição:
ELIMINAÇÃO DE FOURIER-MOTZKIN
 Esta inequação diz que 𝑥1 encontra-se em um certo intervalo, que
é determinado por 𝑥2, … , 𝑥𝑛. Essa inequação pode ser reescrita
como:
ELIMINAÇÃO DE FOURIER-MOTZKIN
 Deste modo, podemos resolver o problema combinando cada
inequação do primeiro conjunto de restrições com cada inequação
do segundo conjunto de restrições.
 Juntando os resultados obtidos resolvendo, obtemos uma
projeção do problema no espaço das variáveis 𝑥2, … , 𝑥𝑛. Pode-se
então proceder da mesma forma e eliminar 𝑥2, … , 𝑥𝑛 − 1.
OBSERVAÇÕES
 Se 𝐼−ou 𝐼+ for vazio, o primeiro conjunto de restrições desaparece
e o sistema será inconsistente ou terá uma região ilimitada, pois a
variável 𝑥1 não terá limite superior (𝐼
− = ∅) ou não terá limite
inferior (𝐼+ = ∅).
OBSERVAÇÕES
 Se o conjunto 𝐼0 for vazio e apenas um dos conjuntos 𝐼−ou 𝐼+ for
não vazio, não podemos eliminar a primeira variável. Uma
alternativa é reordenar o sistema e iniciar a eliminação por outra
variável.