01 simplex rev

Prévia do material em texto

Otimização em Redes
Allexandre Fortes S. Reis
Coordenadoria de Engenharia de Produção
Departamento de Engenharia Mecânica
Campus Santo Antônio
Universidade Federal de São João Del Rei
10 de agosto de 2017
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 10 de agosto de 2017 1 / 37
Conteúdo
1
Introdução
2
Teoria básica e o Método SIMPLEX
3
Algoritmo SIMPLEX
Exemplo
Exercícios
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 10 de agosto de 2017 2 / 37
Introdução
Método SIMPLEX
i. George B. Dantzig (1947);
ii. Viabiliza a solução de Problemas de Progra-
mação Linear; (PPL);
iii. Procedimento Algébrico baseado em con-
ceitos Geométricos;
iv. Álgebra Linear:
I
Operações entre matrizes;
I
Operações elementares em matrizes;
I
Vetores;
I
Bases vetoriais;
I
Combinações lineares;
I
etc.
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 10 de agosto de 2017 3 / 37
Introdução
Método SIMPLEX
i. George B. Dantzig (1947);
ii. Viabiliza a solução de Problemas de Progra-
mação Linear; (PPL);
iii. Procedimento Algébrico baseado em con-
ceitos Geométricos;
iv. Álgebra Linear:
I
Operações entre matrizes;
I
Operações elementares em matrizes;
I
Vetores;
I
Bases vetoriais;
I
Combinações lineares;
I
etc.
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 10 de agosto de 2017 3 / 37
Introdução
Método SIMPLEX
i. George B. Dantzig (1947);
ii. Viabiliza a solução de Problemas de Progra-
mação Linear; (PPL);
iii. Procedimento Algébrico baseado em con-
ceitos Geométricos;
iv. Álgebra Linear:
I
Operações entre matrizes;
I
Operações elementares em matrizes;
I
Vetores;
I
Bases vetoriais;
I
Combinações lineares;
I
etc.
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 10 de agosto de 2017 3 / 37
Introdução
Método SIMPLEX
i. George B. Dantzig (1947);
ii. Viabiliza a solução de Problemas de Progra-
mação Linear; (PPL);
iii. Procedimento Algébrico baseado em con-
ceitos Geométricos;
iv. Álgebra Linear:
I
Operações entre matrizes;
I
Operações elementares em matrizes;
I
Vetores;
I
Bases vetoriais;
I
Combinações lineares;
I
etc.
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 10 de agosto de 2017 3 / 37
Teoria básica e o Método SIMPLEX
Características
i É o algoritmo mais popular para a resolução de PPL;
ii Tem sua fundamentação em na busca por bases vetoriais que sirvam de solução
para o problema estudado, o melhorando, até que o melhor vértice seja atingido,
caso exista;
iii Através da mudança de bases vetoriais realiza-se uma caminhada nos vértices
da casca convexa;
iv Evita o teste de todas as soluções básicas viáveis (SBV) possíveis para ga-
rantir a otimização do problema;
v Uma SBV é composta por vetores linearmente independentes;
vi Primeiramente, para a resolução, é necessário colocar o PPL na chamada forma
padrão.
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 10 de agosto de 2017 4 / 37
Teoria básica e o Método SIMPLEX
Caracterização de Vértice
i. B: Base Vetorial;
ii. xB: Vetor das variáveis básicas (VB);
iii. xR: Vetor das variáveis não-básicas (VNB);
iv. b: Vetor de termos independentes;
v. Solução básica (SB): é um vetor x tal que, BxB = b e xR = 0
vi. Solução básica viável (SBV): é um vetor x tal que, BxB = b, xR = 0 e xB ≥ 0.
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 10 de agosto de 2017 5 / 37
Teoria básica e o Método SIMPLEX
Partição básica
i. Em um ponto no interior do conjunto (não pertencente a nenhuma aresta não há variáveis
nulas;
ii. Em uma aresta há, pelo menos, uma variável nula;
iii. Em um vértice há, pelo menos, m variáveis não-nulas.
R B
m
n m
n+m
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 10 de agosto de 2017 6 / 37
Método SIMPLEX
Forma Padrão de PPL
max z =
n∑
j=1
cjxj
s.a.:
n∑
j=1
aijxj = bi ∀i = 1, . . . ,m
xj ≥ 0 ∀j = 1, . . . , n
*bi é sempre não-negativo
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 10 de agosto de 2017 7 / 37
Método SIMPLEX
Forma Padrão: Exemplo
max z = f(x) =7x1 + 4x2 + 3x3
s.a.:
2x1 + 4x2 + 3x3 ≤ 8
x1 + 2x2 + 4x3 ≥ 5
3x1 + x2 + x3 = −6
x1 ≥ 0, x2 ≤ 0, x3 ∈ R
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 10 de agosto de 2017 8 / 37
Método SIMPLEX
Forma Padrão: Exemplo
i Restrição "≤":
I
Adiciona-se uma variável de folga;
I
Ex: 2x1 + 4x2 + 3x3 ≤ 8→ 2x1 + 4x2 + 3x3+x4 = 8
ii Restrição "≥":
I
Subtrai-se uma variável de folga;
I
Ex: x1 + 2x2 + 4x3 ≥ 5→ x1 + 2x2 + 4x3−x5 = 5
iii Restrição "=":
I
Não há necessidade de se adicionar ou subtrair uma variável de folga;
iv Existe termo independente bi < 0:
I
Multiplica-se a i-ésima restrição por �-1�;
I
Ex: 3x1 + x2 + x3 = −6 → −3x1 − x2 − x3 = 6
*variável de folga: parte do recurso bi disponível que não foi consumido.
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 10 de agosto de 2017 9 / 37
Método SIMPLEX
Forma Padrão: Exemplo
i Restrição "≤":
I
Adiciona-se uma variável de folga;
I
Ex: 2x1 + 4x2 + 3x3 ≤ 8→ 2x1 + 4x2 + 3x3+x4 = 8
ii Restrição "≥":
I
Subtrai-se uma variável de folga;
I
Ex: x1 + 2x2 + 4x3 ≥ 5→ x1 + 2x2 + 4x3−x5 = 5
iii Restrição "=":
I
Não há necessidade de se adicionar ou subtrair uma variável de folga;
iv Existe termo independente bi < 0:
I
Multiplica-se a i-ésima restrição por �-1�;
I
Ex: 3x1 + x2 + x3 = −6 → −3x1 − x2 − x3 = 6
*variável de folga: parte do recurso bi disponível que não foi consumido.
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 10 de agosto de 2017 9 / 37
Método SIMPLEX
Forma Padrão: Exemplo
i Restrição "≤":
I
Adiciona-se uma variável de folga;
I
Ex: 2x1 + 4x2 + 3x3 ≤ 8→ 2x1 + 4x2 + 3x3+x4 = 8
ii Restrição "≥":
I
Subtrai-se uma variável de folga;
I
Ex: x1 + 2x2 + 4x3 ≥ 5→ x1 + 2x2 + 4x3−x5 = 5
iii Restrição "=":
I
Não há necessidade de se adicionar ou subtrair uma variável de folga;
iv Existe termo independente bi < 0:
I
Multiplica-se a i-ésima restrição por �-1�;
I
Ex: 3x1 + x2 + x3 = −6 → −3x1 − x2 − x3 = 6
*variável de folga: parte do recurso bi disponível que não foi consumido.
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 10 de agosto de 2017 9 / 37
Método SIMPLEX
Forma Padrão: Exemplo
i Restrição "≤":
I
Adiciona-se uma variável de folga;
I
Ex: 2x1 + 4x2 + 3x3 ≤ 8→ 2x1 + 4x2 + 3x3+x4 = 8
ii Restrição "≥":
I
Subtrai-se uma variável de folga;
I
Ex: x1 + 2x2 + 4x3 ≥ 5→ x1 + 2x2 + 4x3−x5 = 5
iii Restrição "=":
I
Não há necessidade de se adicionar ou subtrair uma variável de folga;
iv Existe termo independente bi < 0:
I
Multiplica-se a i-ésima restrição por �-1�;
I
Ex: 3x1 + x2 + x3 = −6 → −3x1 − x2 − x3 = 6
*variável de folga: parte do recurso bi disponível que não foi consumido.
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 10 de agosto de 2017 9 / 37
Método SIMPLEX
Forma Padrão: Exemplo
i Existe variável não-positiva (xk ≤ 0):
I
Cria-se variável x
′
k tal que, xk = −x
′
k;
I
Ex: x2 ≤ 0→ x2 = −x′2, x
′
2 ≥ 0
ii Existe variável livre (xk ∈ R):
I
Faz-se variável xk = x
′
k − x
′′
k tal que, x
′
k,x
′′
k ≥ 0;
x
′
k > x
′′
k ⇔ xk > 0
x
′
k < x
′′
k ⇔ xk < 0
x
′
k = x
′′
k ⇔ xk = 0
I
Ex: x3 ∈ R→ x3 = x′3 − x
′′
3 , x
′
k,x
′′
k ≥ 0
∗k = 1, . . . , n: é um índice genérico para as variáveis.
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 10 de agosto de 2017 10 / 37
Método SIMPLEX
Forma Padrão: Exemplo
i Existe variável não-positiva (xk ≤ 0):
I
Cria-se variável x
′
k tal que, xk = −x
′
k;
I
Ex: x2 ≤ 0→ x2 = −x′2, x
′
2 ≥ 0
ii Existe variável livre (xk ∈ R):I
Faz-se variável xk = x
′
k − x
′′
k tal que, x
′
k,x
′′
k ≥ 0;
x
′
k > x
′′
k ⇔ xk > 0
x
′
k < x
′′
k ⇔ xk < 0
x
′
k = x
′′
k ⇔ xk = 0
I
Ex: x3 ∈ R→ x3 = x′3 − x
′′
3 , x
′
k,x
′′
k ≥ 0
∗k = 1, . . . , n: é um índice genérico para as variáveis.
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 10 de agosto de 2017 10 / 37
Método SIMPLEX
Modelo Original
max z = f(x) =7x1 − 4x2 + 3x3
s.a.:
2x1 + 4x2 + 3x3 ≤ 8
x1 + 2x2 + 4x3 ≥ 5
3x1 + x2 + x3 = −6
x1 ≥ 0, x2 ≤ 0, x3 ∈ R
Modelo na Forma Padrão
max z = f(x) =7x1 + 4x
′
2 + 3x
′
3 − 3x
′′
3 + 0x4 + 0x5
s.a.:
2x1 − 4x
′
2 + 3x
′
3 − 3x
′′
3 + 1x4 + 0x5 = 8
x1 − 2x
′
2 + 4x
′
3 − 4x
′′
3 + 0x4 +−1x5 = 5
− 3x1 + x
′
2 − x
′
3 + x
′′
3 + 0x4 + 0x5 = 6
x1, x
′
2, x
′
3, x
′′
3 , 0x4, 0x5 ≥ 0
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 10 de agosto de 2017 11 / 37
Método SIMPLEX
Modelo Original
max z = f(x) =7x1 − 4x2 + 3x3
s.a.:
2x1 + 4x2 + 3x3 ≤ 8
x1 + 2x2 + 4x3 ≥ 5
3x1 + x2 + x3 = −6
x1 ≥ 0, x2 ≤ 0, x3 ∈ R
Modelo na Forma Padrão
max z = f(x) =7x1 + 4x
′
2 + 3x
′
3 − 3x
′′
3 + 0x4 + 0x5
s.a.:
2x1 − 4x
′
2 + 3x
′
3 − 3x
′′
3 + 1x4 + 0x5 = 8
x1 − 2x
′
2 + 4x
′
3 − 4x
′′
3 + 0x4 +−1x5 = 5
− 3x1 + x
′
2 − x
′
3 + x
′′
3 + 0x4 + 0x5 = 6
x1, x
′
2, x
′
3, x
′′
3 , 0x4, 0x5 ≥ 0
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 10 de agosto de 2017 11 / 37
Algoritmo SIMPLEX
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 10 de agosto de 2017 12 / 37
Algoritmo SIMPLEX
Características
i. Condições notáveis:
I
Otimalidade: escolha da variável que entra na base;
I
Viabilidade: escolha da variável que sai na base;
ii. Operações por linhas usando Gauss-Jordan
I
Linha-pivô (LP): Troca-se as variáveis, se necessário divide-se todos elementos da
linha pelo valor do pivô;
I
Demais linhas (Lk): L
′
k = Lk + λ× LP, onde λ é o coeficiente da linha pivô.
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 10 de agosto de 2017 13 / 37
Algoritmo SIMPLEX
Características
i. Condições notáveis:
I
Otimalidade: escolha da variável que entra na base;
I
Viabilidade: escolha da variável que sai na base;
ii. Operações por linhas usando Gauss-Jordan
I
Linha-pivô (LP): Troca-se as variáveis, se necessário divide-se todos elementos da
linha pelo valor do pivô;
I
Demais linhas (Lk): L
′
k = Lk + λ× LP, onde λ é o coeficiente da linha pivô.
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 10 de agosto de 2017 13 / 37
Resolução de PPL via SIMPLEX
Modelo Original
max z =x1 + 2x2
s.a.:
x1 ≤ 2
x2 ≤ 2
x1 + x2 ≤ 3
x1, x2 ≥ 0
Modelo na Forma Padrão
max z =x1 + 2x2 + 0x3 + 0x4 + 0x5
s.a.:
x1 + 0x2 + 1x3 + 0x4 + 0x5 = 2
0x1 + x2 + 0x3 + 1x4 + 0x5 = 2
x1 + x2 + 0x3 + 0x4 + 1x5 = 3
x1, x2, x3, x4, x5 ≥ 0
Modelo na Forma Matricial
1 0 1 0 00 1 0 1 0
1 1 0 0 1


x1
x2
x3
x4
x5
 =
22
3

AX = b
[
1 2 0 0 0
]

x1
x2
x3
x4
x5

CX
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 10 de agosto de 2017 14 / 37
Resolução de PPL via SIMPLEX
Modelo Original
max z =x1 + 2x2
s.a.:
x1 ≤ 2
x2 ≤ 2
x1 + x2 ≤ 3
x1, x2 ≥ 0
Modelo na Forma Padrão
max z =x1 + 2x2 + 0x3 + 0x4 + 0x5
s.a.:
x1 + 0x2 + 1x3 + 0x4 + 0x5 = 2
0x1 + x2 + 0x3 + 1x4 + 0x5 = 2
x1 + x2 + 0x3 + 0x4 + 1x5 = 3
x1, x2, x3, x4, x5 ≥ 0
Modelo na Forma Matricial
1 0 1 0 00 1 0 1 0
1 1 0 0 1


x1
x2
x3
x4
x5
 =
22
3

AX = b
[
1 2 0 0 0
]

x1
x2
x3
x4
x5

CX
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 10 de agosto de 2017 14 / 37
Resolução de PPL via SIMPLEX
Modelo Original
max z =x1 + 2x2
s.a.:
x1 ≤ 2
x2 ≤ 2
x1 + x2 ≤ 3
x1, x2 ≥ 0
Modelo na Forma Padrão
max z =x1 + 2x2 + 0x3 + 0x4 + 0x5
s.a.:
x1 + 0x2 + 1x3 + 0x4 + 0x5 = 2
0x1 + x2 + 0x3 + 1x4 + 0x5 = 2
x1 + x2 + 0x3 + 0x4 + 1x5 = 3
x1, x2, x3, x4, x5 ≥ 0
Modelo na Forma Matricial
1 0 1 0 00 1 0 1 0
1 1 0 0 1


x1
x2
x3
x4
x5
 =
22
3

AX = b
[
1 2 0 0 0
]

x1
x2
x3
x4
x5

CX
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 10 de agosto de 2017 14 / 37
Resolução de PPL via SIMPLEX
Modelo Original
max z =x1 + 2x2
s.a.:
x1 ≤ 2
x2 ≤ 2
x1 + x2 ≤ 3
x1, x2 ≥ 0
Modelo na Forma Padrão
max z =x1 + 2x2 + 0x3 + 0x4 + 0x5
s.a.:
x1 + 0x2 + 1x3 + 0x4 + 0x5 = 2
0x1 + x2 + 0x3 + 1x4 + 0x5 = 2
x1 + x2 + 0x3 + 0x4 + 1x5 = 3
x1, x2, x3, x4, x5 ≥ 0
Modelo na Forma Matricial
1 0 1 0 00 1 0 1 0
1 1 0 0 1


x1
x2
x3
x4
x5
 =
22
3

AX = b
[
1 2 0 0 0
]

x1
x2
x3
x4
x5

CX
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 10 de agosto de 2017 14 / 37
Resolução de PPL via SIMPLEX
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 10 de agosto de 2017 15 / 37
Resolução de PPL via SIMPLEX
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 10 de agosto de 2017 16 / 37
Resolução de PPL via SIMPLEX
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 10 de agosto de 2017 17 / 37
Resolução de PPL via SIMPLEX
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 10 de agosto de 2017 18 / 37
Resolução de PPL via SIMPLEX
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 10 de agosto de 2017 19 / 37
Resolução de PPL via SIMPLEX
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 10 de agosto de 2017 20 / 37
Resolução de PPL via SIMPLEX
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 10 de agosto de 2017 21 / 37
Resolução de PPL via SIMPLEX
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 10 de agosto de 2017 22 / 37
Resolução de PPL via SIMPLEX
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 10 de agosto de 2017 23 / 37
Resolução de PPL via SIMPLEX
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 10 de agosto de 2017 24 / 37
Resolução de PPL via SIMPLEX
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 10 de agosto de 2017 25 / 37
Resolução de PPL via SIMPLEX
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 10 de agosto de 2017 26 / 37
Resolução de PPL via SIMPLEX
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 10 de agosto de 2017 27 / 37
Resolução de PPL via SIMPLEX
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 10 de agosto de 2017 28 / 37
Resolução de PPL via SIMPLEX
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 10 de agosto de 2017 29 / 37
Resolução de PPL via SIMPLEX
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 10 de agosto de 2017 30 / 37
Resolução de PPL via SIMPLEX
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 10 de agosto de 2017 31 / 37
Resolução de PPL via SIMPLEX
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 10 de agosto de 2017 32 / 37
Resolução de PPL via SIMPLEX
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 10 de agosto de 2017 33 / 37
Resolução de PPL via SIMPLEX
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 10 de agosto de 2017 34 / 37
Exercícios
Resolva o PPL abaixo usando o método SIMPLEX
max z =x1 + 2x2
s.a.:
2x1 + x2 ≤ 8
1x1 + 0x2 ≤ 3
0x1 + 2x2 ≤ 4
x1, x2 ≥ 0
solução: x1 = 2, x2 = 4.
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 10 de agosto de 2017 35 / 37
Dúvidas? Valar joll	oris
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 10 de agosto de 2017 36 / 37
Referências
(1) Arenales, M., Armentano, V., Morabito, R., Yanasse, H. Pesquisa Operacionalpara cursos de engenharia: Modelagem e algoritmos. 2
a
Ed. Rio de Janeiro:
Editora Campus, 2015.
(2) Taha, Hamdy A. Pesquisa operacional. Pearson Education do Brasil, 2008.
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 10 de agosto de 2017 37 / 37
	Introdução
	Teoria básica e o Método SIMPLEX
	Algoritmo SIMPLEX
	Exemplo
	Exercícios