02 ppli redes

Prévia do material em texto

Pesquisa Operacional II
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
22 de agosto de 2017
Allexandre Fortes S. Reis (UFSJ) Pesquisa Operacional II 22 de agosto de 2017 1 / 40
Conteúdo
1
Problema Computacional
2
Problemas de Programação Linear Inteira e Mista
3
Exemplos de PPLI
4
Resolução Computacional de PPLI
5
Exercícios
Allexandre Fortes S. Reis (UFSJ) Pesquisa Operacional II 22 de agosto de 2017 2 / 40
Problema Computacional
Tipos de Problema Computacional
1) Problemas de Decisão
2) Problemas de Localização ou de Busca
3) Problemas de Otimização
Allexandre Fortes S. Reis (UFSJ) Pesquisa Operacional II 22 de agosto de 2017 3 / 40
Problema Computacional
Problemas de Decisão
· Dado um conjunto P de pontos turísticos em São João del Rei, existe um
percurso turístico que passa por todos os pontos em P em um único dia?
· Resposta: Sim ou não
Allexandre Fortes S. Reis (UFSJ) Pesquisa Operacional II 22 de agosto de 2017 4 / 40
Problema Computacional
Problemas de Localização ou de Busca
· Dado um conjunto P de pontos turísticos em São João del Rei, encontre um
percurso turístico que passa por todos os pontos em P em um único dia?
· Resposta: percurso turístico
Allexandre Fortes S. Reis (UFSJ) Pesquisa Operacional II 22 de agosto de 2017 5 / 40
Problema Computacional
Problemas de Otimização
· Dado um conjunto P de pontos turísticos em São João del Rei, qual é o per-
curso turístico que passa por todos os pontos em P em uma menor quantidade
de tempo possível?
· Resposta: percurso turístico MAIS rápido
Allexandre Fortes S. Reis (UFSJ) Pesquisa Operacional II 22 de agosto de 2017 6 / 40
Problemas de Otimização
Definição
Otimização. [De otimizar+-ção] S.f. 1. Estat. Processo pelo qual se
determina o valor ótimo de uma grandeza.
Definição
Ótimo. [Do latim optimu] Adj. 3. Estat. Diz-se de grau, quantidade
ou estado que se considera o mais favorável em relação a um determinado
critério.
Allexandre Fortes S. Reis (UFSJ) Pesquisa Operacional II 22 de agosto de 2017 7 / 40
Problemas de Otimização
Definição
Otimização. [De otimizar+-ção] S.f. 1. Estat. Processo pelo qual se
determina o valor ótimo de uma grandeza.
Definição
Ótimo. [Do latim optimu] Adj. 3. Estat. Diz-se de grau, quantidade
ou estado que se considera o mais favorável em relação a um determinado
critério.
Allexandre Fortes S. Reis (UFSJ) Pesquisa Operacional II 22 de agosto de 2017 7 / 40
Problemas de Otimização Combinatória
Definição
Um problema combinatório é um problema que possui um conjunto de
variáveis que para sua solução é exigida uma combinação de um
subconjunto destes elementos.
Para guiar estas combinações de elementos (variáveis), uma função objetivo
a ser otimizada é associada ao problema, além de um conjunto de restrições
para ditar qual combinação é possível ou não (viabilidade).
Contextualização
i Aplicações: Planejamento, Produção, Coordenação, Investimento, Estoque, Transporte, Co-
municação, Roteamento, Localização, Programação, Distribuição, etc.
ii Natureza discreta;
iii Resolução: Algoritmos específicos para Formulações por Problemas de Programação Inteira.
Allexandre Fortes S. Reis (UFSJ) Pesquisa Operacional II 22 de agosto de 2017 8 / 40
Problemas de Otimização Combinatória
Definição
Um problema combinatório é um problema que possui um conjunto de
variáveis que para sua solução é exigida uma combinação de um
subconjunto destes elementos.
Para guiar estas combinações de elementos (variáveis), uma função objetivo
a ser otimizada é associada ao problema, além de um conjunto de restrições
para ditar qual combinação é possível ou não (viabilidade).
Contextualização
i Aplicações: Planejamento, Produção, Coordenação, Investimento, Estoque, Transporte, Co-
municação, Roteamento, Localização, Programação, Distribuição, etc.
ii Natureza discreta;
iii Resolução: Algoritmos específicos para Formulações por Problemas de Programação Inteira.
Allexandre Fortes S. Reis (UFSJ) Pesquisa Operacional II 22 de agosto de 2017 8 / 40
Modelos de Programação Linear Inteira
Características
1 Tem algumas ou até mesmo todas variáveis inteiras, incluindo binárias;
2 Função objetivo e restrições são lineares;
3 Eleva consideravelmente a dificuldade de resolução computacional;
a Polinomial (P): possui resolução determinística
F
Ex.: Árvore Geradora Mínima, Caminho Mínimo, Emparelhamento, Transporte, etc.
b Não-Polinomial (NP): sem resolução determinística no momento
i Completo: Decisão;
ii Difícil: Combinatório;
F
Ex.: Caminho Máximo, Coloração de Grafos, Caixeiro Viajante, Roteamento de Veículos, Localização
de Facilidades, etc.
Allexandre Fortes S. Reis (UFSJ) Pesquisa Operacional II 22 de agosto de 2017 9 / 40
Modelos de Programação Linear Inteira
Programação Linear Inteira Pura
Modelo de programação linear, porém, todas as variáveis de decisão são
inteiras.
Programação Linear Inteira Binária
Modelo de programação linear, porém, só com variáveis de decisão binárias.
Programação Linear Inteira Mista
Modelo de programação linear, com variáveis de decisão inteiras, binárias e
contínuas.
Allexandre Fortes S. Reis (UFSJ) Pesquisa Operacional II 22 de agosto de 2017 10 / 40
Modelos de Programação Linear Inteira
Programação Linear Inteira Pura
Modelo de programação linear, porém, todas as variáveis de decisão são
inteiras.
Programação Linear Inteira Binária
Modelo de programação linear, porém, só com variáveis de decisão binárias.
Programação Linear Inteira Mista
Modelo de programação linear, com variáveis de decisão inteiras, binárias e
contínuas.
Allexandre Fortes S. Reis (UFSJ) Pesquisa Operacional II 22 de agosto de 2017 10 / 40
Modelos de Programação Linear Inteira
Programação Linear Inteira Pura
Modelo de programação linear, porém, todas as variáveis de decisão são
inteiras.
Programação Linear Inteira Binária
Modelo de programação linear, porém, só com variáveis de decisão binárias.
Programação Linear Inteira Mista
Modelo de programação linear, com variáveis de decisão inteiras, binárias e
contínuas.
Allexandre Fortes S. Reis (UFSJ) Pesquisa Operacional II 22 de agosto de 2017 10 / 40
Modelos de Programação Linear Inteira
Modelos Genéricos
PPL
otimizarf(x1, . . . , xn)
s.a.:
gi(x1, . . . , xn)
≤=≥
 bi
xj ≥ 0
PPLI
otimizarf(x1, . . . , xn)
s.a.:
gi(x1, . . . , xn)
≤=≥
 bi
xj ≥ 0, ∀j = 1, . . . , q
xj ∈ Z+, ∀j = q + 1, . . . , n
Allexandre Fortes S. Reis (UFSJ) Pesquisa Operacional II 22 de agosto de 2017 11 / 40
Modelos de Programação Linear Inteira
Modelos Genéricos
PPL
otimizarf(x1, . . . , xn)
s.a.:
gi(x1, . . . , xn)
≤=≥
 bi
xj ≥ 0
PPLI
otimizarf(x1, . . . , xn)
s.a.:
gi(x1, . . . , xn)
≤=≥
 bi
xj ≥ 0, ∀j = 1, . . . , q
xj ∈ Z+, ∀j = q + 1, . . . , n
Allexandre Fortes S. Reis (UFSJ) Pesquisa Operacional II 22 de agosto de 2017 11 / 40
Modelos de Programação Linear Inteira
Allexandre Fortes S. Reis (UFSJ) Pesquisa Operacional II 22 de agosto de 2017 12 / 40
Modelos de Programação Linear Inteira
Exemplo de aplicação
Uma confeitaria produz dois tipos de bolos de sorvete (BS): chocolate e creme. Cada lote de
bolo de chocolate é vendido com um lucro de 3 unidades monetárias, e os de creme com um
lucro de 1. Contratos de venda impõem que sejam produzidos no mínimo 10 lotes de bolos de
chocolate por dia e que o total de lotes fabricados nunca seja menor que 20. O mercado só é capaz
de consumir até 40 lotes de bolos de creme e 60 de chocolate. As máquinas depreparação do
sorvete disponibilizam 180 horas de operação, sendo que cada lote de bolos de chocolate consome
2 horas de trabalho e cada lote de bolos de creme 3 horas. Determinar o esquema de produção
que maximize os lucros com a venda dos bolos de sorvete.
Modelagem
i Variáveis: xj quantidade de lotes de BS fabricados de creme (x1) ou chocolate (x2);
ii Função objetivo: max f(x) = x1 + 3x2;
iii Restrições:
I
Disponibilidade de máquina: 3x1 + 2x2 ≤ 180;I
Limitação de lotes do BS de creme: x1 ≤ 40;I
Limitação de lotes do BS de chocolate: x2 ≤ 60;I
Contratos de venda: x2 ≥ 10 e x1 + x2 ≥ 20;I
todos devem ser não-negativos: x1, x2 ≥ 0.
Allexandre Fortes S. Reis (UFSJ) Pesquisa Operacional II 22 de agosto de 2017 13 / 40
Modelos de Programação Linear Inteira
Exemplo de aplicação
Uma confeitaria produz dois tipos de bolos de sorvete (BS): chocolate e creme. Cada lote de
bolo de chocolate é vendido com um lucro de 3 unidades monetárias, e os de creme com um
lucro de 1. Contratos de venda impõem que sejam produzidos no mínimo 10 lotes de bolos de
chocolate por dia e que o total de lotes fabricados nunca seja menor que 20. O mercado só é capaz
de consumir até 40 lotes de bolos de creme e 60 de chocolate. As máquinas de preparação do
sorvete disponibilizam 180 horas de operação, sendo que cada lote de bolos de chocolate consome
2 horas de trabalho e cada lote de bolos de creme 3 horas. Determinar o esquema de produção
que maximize os lucros com a venda dos bolos de sorvete.
Modelagem
i Variáveis: xj quantidade de lotes de BS fabricados de creme (x1) ou chocolate (x2);
ii Função objetivo: max f(x) = x1 + 3x2;
iii Restrições:
I
Disponibilidade de máquina: 3x1 + 2x2 ≤ 180;I
Limitação de lotes do BS de creme: x1 ≤ 40;I
Limitação de lotes do BS de chocolate: x2 ≤ 60;I
Contratos de venda: x2 ≥ 10 e x1 + x2 ≥ 20;I
todos devem ser não-negativos: x1, x2 ≥ 0.
Allexandre Fortes S. Reis (UFSJ) Pesquisa Operacional II 22 de agosto de 2017 13 / 40
Modelos de Programação Linear Inteira
Modelo
max f(x) = x1 + 3x2
3x1 + 2x2 ≤ 180
x1 ≤ 40
x2 ≤ 60
x2 ≥ 10
x1 + x2 ≥ 20
x1, x2 ≥ 0
1 Seria possível produzir lotes fracionários de
BS?
R: Talvez para o caso do sorvete sim..
2 Mas e quando se trata de elementos indivi-
siveis, como pessoas, animais, peças, jogos,
viagens, etc?
3 Como resolver esse impasse?
Allexandre Fortes S. Reis (UFSJ) Pesquisa Operacional II 22 de agosto de 2017 14 / 40
Modelos de Programação Linear Inteira
Modelo
max f(x) = x1 + 3x2
3x1 + 2x2 ≤ 180
x1 ≤ 40
x2 ≤ 60
x2 ≥ 10
x1 + x2 ≥ 20
x1, x2 ≥ 0
1 Seria possível produzir lotes fracionários de
BS?
R: Talvez para o caso do sorvete sim..
2 Mas e quando se trata de elementos indivi-
siveis, como pessoas, animais, peças, jogos,
viagens, etc?
3 Como resolver esse impasse?
Allexandre Fortes S. Reis (UFSJ) Pesquisa Operacional II 22 de agosto de 2017 14 / 40
Modelos de Programação Linear Inteira
Modelo
max f(x) = x1 + 3x2
3x1 + 2x2 ≤ 180
x1 ≤ 40
x2 ≤ 60
x2 ≥ 10
x1 + x2 ≥ 20
x1, x2 ≥ 0
1 Seria possível produzir lotes fracionários de
BS?
R: Talvez para o caso do sorvete sim..
2 Mas e quando se trata de elementos indivi-
siveis, como pessoas, animais, peças, jogos,
viagens, etc?
3 Como resolver esse impasse?
Allexandre Fortes S. Reis (UFSJ) Pesquisa Operacional II 22 de agosto de 2017 14 / 40
Modelos de Programação Linear Inteira
Modelo
max f(x) = x1 + 3x2
3x1 + 2x2 ≤ 180
x1 ≤ 40
x2 ≤ 60
x2 ≥ 10
x1 + x2 ≥ 20
x1, x2 ≥ 0
1 Seria possível produzir lotes fracionários de
BS?
R: Talvez para o caso do sorvete sim..
2 Mas e quando se trata de elementos indivi-
siveis, como pessoas, animais, peças, jogos,
viagens, etc?
3 Como resolver esse impasse?
Allexandre Fortes S. Reis (UFSJ) Pesquisa Operacional II 22 de agosto de 2017 14 / 40
Modelos de Programação Linear Inteira
Reescrevendo o Modelo
max f(x) = x1 + 3x2
3x1 + 2x2 ≤ 180
x1 ≤ 40
x2 ≤ 60
x2 ≥ 10
x1 + x2 ≥ 20
x1,x2 ∈ Z+
Tabela: Pontos Extremos da Envoltória do Problema BS
Pontos
Examinados
(x1, x2) f(x)
A (40,10) 70
B (40,30) 130
C (20,60) 200
D (0,60) 180
E (0,20) 60
F (10,10) 40
Allexandre Fortes S. Reis (UFSJ) Pesquisa Operacional II 22 de agosto de 2017 15 / 40
Modelos de Programação Linear Inteira
Reescrevendo o Modelo
max f(x) = x1 + 3x2
3x1 + 2x2 ≤ 180
x1 ≤ 40
x2 ≤ 60
x2 ≥ 10
x1 + x2 ≥ 20
x1,x2 ∈ Z+
Tabela: Pontos Extremos da Envoltória do Problema BS
Pontos
Examinados
(x1, x2) f(x)
A (40,10) 70
B (40,30) 130
C (20,60) 200
D (0,60) 180
E (0,20) 60
F (10,10) 40
Allexandre Fortes S. Reis (UFSJ) Pesquisa Operacional II 22 de agosto de 2017 15 / 40
Modelos de Programação Linear Inteira
Reescrevendo o Modelo
max f(x) = x1 + 3x2
3x1 + 2x2 ≤ 180
x1 ≤ 40
x2 ≤ 60
x2 ≥ 10
x1 + x2 ≥ 20
x1,x2 ∈ Z+
Tabela: Pontos Extremos da Envoltória do Problema BS
Pontos
Examinados
(x1, x2) f(x)
A (40,10) 70
B (40,30) 130
C (20,60) 200
D (0,60) 180
E (0,20) 60
F (10,10) 40
Allexandre Fortes S. Reis (UFSJ) Pesquisa Operacional II 22 de agosto de 2017 15 / 40
Modelos de Programação Linear Inteira
A realidade...
max f(x) = x1 + 19x2
x1 + 20x2 ≤ 50
x1 + x2 ≤ 20
x1, x2 ∈ Z+
Gráfico
x1
x2
x∗ x∗
Solução linear (relaxada):
x1 =
170
9
≈ 18, 8
x2 =
30
19
≈ 1, 58
f(x∗) = 440
9
= 48, 8
Pontos
Examinados
f(x)
x1 = 19 x2 = 2 inviável
x1 = 19 x2 = 1 38
x1 = 18 x2 = 2 inviável
x1 = 18 x2 = 1 37
Solução linear e inteira:
x1 = 10
x2 = 2
f(x∗) = 48
Diferença de ≈ 21% entre o ótimo
inteiro inspecionado (38) e o ótimo
inteiro 48.
Allexandre Fortes S. Reis (UFSJ) Pesquisa Operacional II 22 de agosto de 2017 16 / 40
Modelos de Programação Linear Inteira
A realidade...
max f(x) = x1 + 19x2
x1 + 20x2 ≤ 50
x1 + x2 ≤ 20
x1, x2 ∈ Z+
Gráfico
x1
x2
x∗
x∗
Solução linear (relaxada):
x1 =
170
9
≈ 18, 8
x2 =
30
19
≈ 1, 58
f(x∗) = 440
9
= 48, 8
Pontos
Examinados
f(x)
x1 = 19 x2 = 2 inviável
x1 = 19 x2 = 1 38
x1 = 18 x2 = 2 inviável
x1 = 18 x2 = 1 37
Solução linear e inteira:
x1 = 10
x2 = 2
f(x∗) = 48
Diferença de ≈ 21% entre o ótimo
inteiro inspecionado (38) e o ótimo
inteiro 48.
Allexandre Fortes S. Reis (UFSJ) Pesquisa Operacional II 22 de agosto de 2017 16 / 40
Modelos de Programação Linear Inteira
A realidade...
max f(x) = x1 + 19x2
x1 + 20x2 ≤ 50
x1 + x2 ≤ 20
x1, x2 ∈ Z+
Gráfico
x1
x2
x∗
x∗
Solução linear (relaxada):
x1 =
170
9
≈ 18, 8
x2 =
30
19
≈ 1, 58
f(x∗) = 440
9
= 48, 8
Pontos
Examinados
f(x)
x1 = 19 x2 = 2 inviável
x1 = 19 x2 = 1 38
x1 = 18 x2 = 2 inviável
x1 = 18 x2 = 1 37
Solução linear e inteira:
x1 = 10
x2 = 2
f(x∗) = 48
Diferença de ≈ 21% entre o ótimo
inteiro inspecionado (38) e o ótimo
inteiro 48.
Allexandre Fortes S. Reis (UFSJ) Pesquisa Operacional II 22 de agosto de 2017 16 / 40
Modelos de Programação Linear Inteira
A realidade...
max f(x) = x1 + 19x2
x1 + 20x2 ≤ 50
x1 + x2 ≤ 20
x1, x2 ∈ Z+
Gráfico
x1
x2
x∗
x∗
Solução linear (relaxada):
x1 =
170
9
≈ 18, 8
x2 =
30
19
≈ 1, 58
f(x∗) = 440
9
= 48, 8
Pontos
Examinados
f(x)
x1 = 19 x2 = 2 inviável
x1 = 19 x2 = 1 38
x1 = 18 x2 = 2 inviável
x1 = 18 x2 = 1 37
Solução linear e inteira:
x1 = 10
x2 = 2
f(x∗) = 48
Diferença de ≈ 21% entre o ótimo
inteiro inspecionado (38) e o ótimo
inteiro 48.
Allexandre Fortes S. Reis (UFSJ) Pesquisa Operacional II 22 de agosto de 2017 16 / 40
Modelos de Programação Linear Inteira
A realidade...
max f(x) = x1 + 19x2
x1 + 20x2 ≤ 50
x1 + x2 ≤ 20
x1, x2 ∈ Z+
Gráfico
x1
x2
x∗
x∗
Soluçãolinear (relaxada):
x1 =
170
9
≈ 18, 8
x2 =
30
19
≈ 1, 58
f(x∗) = 440
9
= 48, 8
Pontos
Examinados
f(x)
x1 = 19 x2 = 2 inviável
x1 = 19 x2 = 1 38
x1 = 18 x2 = 2 inviável
x1 = 18 x2 = 1 37
Solução linear e inteira:
x1 = 10
x2 = 2
f(x∗) = 48
Diferença de ≈ 21% entre o ótimo
inteiro inspecionado (38) e o ótimo
inteiro 48.
Allexandre Fortes S. Reis (UFSJ) Pesquisa Operacional II 22 de agosto de 2017 16 / 40
Modelos de Programação Linear Inteira
A realidade...
max f(x) = x1 + 19x2
x1 + 20x2 ≤ 50
x1 + x2 ≤ 20
x1, x2 ∈ Z+
Gráfico
x1
x2
x∗
x∗
Solução linear (relaxada):
x1 =
170
9
≈ 18, 8
x2 =
30
19
≈ 1, 58
f(x∗) = 440
9
= 48, 8
Pontos
Examinados
f(x)
x1 = 19 x2 = 2 inviável
x1 = 19 x2 = 1 38
x1 = 18 x2 = 2 inviável
x1 = 18 x2 = 1 37
Solução linear e inteira:
x1 = 10
x2 = 2
f(x∗) = 48
Diferença de ≈ 21% entre o ótimo
inteiro inspecionado (38) e o ótimo
inteiro 48.
Allexandre Fortes S. Reis (UFSJ) Pesquisa Operacional II 22 de agosto de 2017 16 / 40
Modelos de Programação Linear Inteira
A realidade...
max f(x) = x1 + 19x2
x1 + 20x2 ≤ 50
x1 + x2 ≤ 20
x1, x2 ∈ Z+
Gráfico
x1
x2
x∗
x∗
Solução linear (relaxada):
x1 =
170
9
≈ 18, 8
x2 =
30
19
≈ 1, 58
f(x∗) = 440
9
= 48, 8
Pontos
Examinados
f(x)
x1 = 19 x2 = 2 inviável
x1 = 19 x2 = 1 38
x1 = 18 x2 = 2 inviável
x1 = 18 x2 = 1 37
Solução linear e inteira:
x1 = 10
x2 = 2
f(x∗) = 48
Diferença de ≈ 21% entre o ótimo
inteiro inspecionado (38) e o ótimo
inteiro 48.
Allexandre Fortes S. Reis (UFSJ) Pesquisa Operacional II 22 de agosto de 2017 16 / 40
Modelos de Programação Linear Inteira
A realidade...
max f(x) = x1 + 19x2
x1 + 20x2 ≤ 50
x1 + x2 ≤ 20
x1, x2 ∈ Z+
Gráfico
x1
x2
x∗ x∗
Solução linear (relaxada):
x1 =
170
9
≈ 18, 8
x2 =
30
19
≈ 1, 58
f(x∗) = 440
9
= 48, 8
Pontos
Examinados
f(x)
x1 = 19 x2 = 2 inviável
x1 = 19 x2 = 1 38
x1 = 18 x2 = 2 inviável
x1 = 18 x2 = 1 37
Solução linear e inteira:
x1 = 10
x2 = 2
f(x∗) = 48
Diferença de ≈ 21% entre o ótimo
inteiro inspecionado (38) e o ótimo
inteiro 48.
Allexandre Fortes S. Reis (UFSJ) Pesquisa Operacional II 22 de agosto de 2017 16 / 40
Modelos de Programação Linear Inteira
Características
i Em inúmeras situações, as variáveis de decisão não poderão assumir valores
contínuos;
ii Por exemplo, quando se referem a pessoas, configurações, objetos físicos, etc,
soluções fracionárias perdem o sentido prático;
iii Poderíamos pensar que este problema não seria tão grave se trabalhássemos
com uma formulação contínua e, após a solução final, empregássemos alguma
estratégia de arredondamento;
iv O que pode parecer, ingenuamente, uma solução �razoável�, pode ser uma
péssima ideia na prática.
v Em raros casos, resolver um problema de programação linear contínua equivale
a resolver um problema de programação linear inteira
Allexandre Fortes S. Reis (UFSJ) Pesquisa Operacional II 22 de agosto de 2017 17 / 40
Problemas de Programação Linear Inteira e Mista
Problema do Caixeiro Viajante - PCV
É descrito por um conjunto de n cidades e uma matriz de distância entre elas, tendo o seguinte
objetivo: o Caixeiro Viajante deve sair de uma cidade, dita cidade origem, visitar cada uma das
n − 1 cidades restantes apenas uma única vez e retornar à cidade origem percorrendo a menor
distância possível. Em outras palavras, deve ser encontrada uma rota fechada de comprimento
mínimo que passe exatamente uma única vez por cada cidade.
Características:
i o mais famoso problema de otimização combinatória;
ii origem no jogo A Volta ao Mundo, de Hamilton (1857)
iii NP-Difícil;
iv Aplicações: operações de máquinas em manufatura, otimização do movimento de ferramentas de corte, otimização
de perfurações em placas de circuito impresso, roteamento de veículos, distribuição de tarefas etc.
Allexandre Fortes S. Reis (UFSJ) Pesquisa Operacional II 22 de agosto de 2017 18 / 40
Problemas de Programação Linear Inteira e Mista
Formulação para o Problema do Caixeiro Viajante
min
n∑
i=1
n∑
j 6=i,j=1
cijxij
s.t.:
n∑
j 6=i,i=1
xij = 1 ∀j = 1, . . . , n
n∑
j 6=i,j=1
xij = 1 ∀i = 1, . . . , n
ui − uj + nxij ≤ n− 1 1 ≤ i 6= j ≤ n
xij ∈ {0, 1} ∀i, j = 1, . . . , n
ui ∈ Z+ ∀i = 1, . . . , n
Allexandre Fortes S. Reis (UFSJ) Pesquisa Operacional II 22 de agosto de 2017 19 / 40
Problemas de Programação Linear Inteira e Mista
Resolução para o PCV
i Força Bruta*: O(n!);
ii Programação Dinâmica: O(n22n);
iii Branch-and-bound
1
ou demais técnicas de enumeração
2
;
iv Algoritmos de Melhoria Progressiva;
Aplicações
i Rotas de ônibus escolares;
ii Programação da Tripulação;
iii Movimentação de Materiais em De-
pósito;
iv Programação de Operação de Má-
quinas;
v etc.
*Impraticável para 20 cidades
1
Até 60 cidades;
Branch-and-cut
2
Até 85.900 cidades;
Allexandre Fortes S. Reis (UFSJ) Pesquisa Operacional II 22 de agosto de 2017 20 / 40
Problemas de Programação Linear Inteira e Mista
Resolução para o PCV
i Força Bruta*: O(n!);
ii Programação Dinâmica: O(n22n);
iii Branch-and-bound
1
ou demais técnicas de enumeração
2
;
iv Algoritmos de Melhoria Progressiva;
Aplicações
i Rotas de ônibus escolares;
ii Programação da Tripulação;
iii Movimentação de Materiais em De-
pósito;
iv Programação de Operação de Má-
quinas;
v etc.
*Impraticável para 20 cidades
1
Até 60 cidades;
Branch-and-cut
2
Até 85.900 cidades;
Allexandre Fortes S. Reis (UFSJ) Pesquisa Operacional II 22 de agosto de 2017 20 / 40
Problemas de Programação Linear Inteira e Mista
Problema da Mochila
Dada uma mochila de capacidade C e um conjunto de n itens, cada um con um
peso pi,∀i = 1, .., n e um valor associado vi,∀i = 1, .., n. A ideia é maximizar o
valor carregado pela mochila.
Aplicações
i Orçamento e Investimento de Capital;
ii Corte e empacotamento;
iii Carregamento de Veículos;
iv Carregamento de Contêineres;
v Dimensionamento de Armazéns;
vi entre outros.
Allexandre Fortes S. Reis (UFSJ) Pesquisa Operacional II 22 de agosto de 2017 21 / 40
Problemas de Programação Linear Inteira e Mista
Problema da Mochila
Dada uma mochila de capacidade C e um conjunto de n itens, cada um con um
peso pi,∀i = 1, .., n e um valor associado vi,∀i = 1, .., n. A ideia é maximizar o
valor carregado pela mochila.
Aplicações
i Orçamento e Investimento de Capital;
ii Corte e empacotamento;
iii Carregamento de Veículos;
iv Carregamento de Contêineres;
v Dimensionamento de Armazéns;
vi entre outros.
Allexandre Fortes S. Reis (UFSJ) Pesquisa Operacional II 22 de agosto de 2017 21 / 40
Problemas de Programação Linear Inteira e Mista
Problema da Mochila: Formulações
max
n∑
j=1
vjxj
s.t.:
n∑
j=1
pjxj ≤ C
xj ∈ Z+, ∀j = 1, . . . , n
Clássico.
max
n∑
j=1
vjxj
s.t.:
n∑
j=1
pjxj ≤ C
xj ∈ {0, 1}, ∀j = 1, . . . , n
Binário.
max
n∑
j=1
vjxj
s.t.:
n∑
j=1
pjxj ≤ C
xj ≤ lj , ∀j = 1, . . . , n
xj ∈ Z+, ∀j = 1, . . . , n
Limitado
Problemas Correlatos
i Soma de subconjuntos;
ii Mochila Múltipla;
iii Mochila 0-1 Multidimensional;
iv Mochila Max-Min 0-1;
v Mochila de Escolha Múltipla;
vi Mochila Encapsulada;
vii Mochila Decomposta;
viii Mochila Multiperíodo;
ix Mochila Quadrática;
x Mochila com Estrutura Matróide.
Allexandre Fortes S. Reis (UFSJ) Pesquisa Operacional II 22 de agosto de 2017 22 / 40
Problemas de Programação Linear Inteira e Mista
Problema da Mochila: Formulações
max
n∑
j=1
vjxj
s.t.:
n∑
j=1
pjxj ≤ C
xj ∈ Z+, ∀j = 1, . . . , n
Clássico.
max
n∑
j=1vjxj
s.t.:
n∑
j=1
pjxj ≤ C
xj ∈ {0, 1}, ∀j = 1, . . . , n
Binário.
max
n∑
j=1
vjxj
s.t.:
n∑
j=1
pjxj ≤ C
xj ≤ lj , ∀j = 1, . . . , n
xj ∈ Z+, ∀j = 1, . . . , n
Limitado
Problemas Correlatos
i Soma de subconjuntos;
ii Mochila Múltipla;
iii Mochila 0-1 Multidimensional;
iv Mochila Max-Min 0-1;
v Mochila de Escolha Múltipla;
vi Mochila Encapsulada;
vii Mochila Decomposta;
viii Mochila Multiperíodo;
ix Mochila Quadrática;
x Mochila com Estrutura Matróide.
Allexandre Fortes S. Reis (UFSJ) Pesquisa Operacional II 22 de agosto de 2017 22 / 40
Problemas de Programação Linear Inteira e Mista
Problema da Mochila: Formulações
max
n∑
j=1
vjxj
s.t.:
n∑
j=1
pjxj ≤ C
xj ∈ Z+, ∀j = 1, . . . , n
Clássico.
max
n∑
j=1
vjxj
s.t.:
n∑
j=1
pjxj ≤ C
xj ∈ {0, 1}, ∀j = 1, . . . , n
Binário.
max
n∑
j=1
vjxj
s.t.:
n∑
j=1
pjxj ≤ C
xj ≤ lj , ∀j = 1, . . . , n
xj ∈ Z+, ∀j = 1, . . . , n
Limitado
Problemas Correlatos
i Soma de subconjuntos;
ii Mochila Múltipla;
iii Mochila 0-1 Multidimensional;
iv Mochila Max-Min 0-1;
v Mochila de Escolha Múltipla;
vi Mochila Encapsulada;
vii Mochila Decomposta;
viii Mochila Multiperíodo;
ix Mochila Quadrática;
x Mochila com Estrutura Matróide.
Allexandre Fortes S. Reis (UFSJ) Pesquisa Operacional II 22 de agosto de 2017 22 / 40
Problemas de Programação Linear Inteira e Mista
Problema da Mochila: Formulações
max
n∑
j=1
vjxj
s.t.:
n∑
j=1
pjxj ≤ C
xj ∈ Z+, ∀j = 1, . . . , n
Clássico.
max
n∑
j=1
vjxj
s.t.:
n∑
j=1
pjxj ≤ C
xj ∈ {0, 1}, ∀j = 1, . . . , n
Binário.
max
n∑
j=1
vjxj
s.t.:
n∑
j=1
pjxj ≤ C
xj ≤ lj , ∀j = 1, . . . , n
xj ∈ Z+, ∀j = 1, . . . , n
Limitado
Problemas Correlatos
i Soma de subconjuntos;
ii Mochila Múltipla;
iii Mochila 0-1 Multidimensional;
iv Mochila Max-Min 0-1;
v Mochila de Escolha Múltipla;
vi Mochila Encapsulada;
vii Mochila Decomposta;
viii Mochila Multiperíodo;
ix Mochila Quadrática;
x Mochila com Estrutura Matróide.
Allexandre Fortes S. Reis (UFSJ) Pesquisa Operacional II 22 de agosto de 2017 22 / 40
Problemas de Programação Linear Inteira e Mista
Problema de Roteamento de Veículos - PRV
1 Introduzido por Dantzig e Ramser (1959);
2 Generalização do Problema do Caixeiro Viajante;
3 Representa um importante componentes dos sistemas de distribuição e transporte;
4 Classificações:
i Respeitar a capacidade do veículo (rota) (PRVC).
ii Atender às demandas de coleta e entrega (PRVCE);
iii Respeitar as janelas de tempo (PRVJT);
Allexandre Fortes S. Reis (UFSJ) Pesquisa Operacional II 22 de agosto de 2017 23 / 40
Problemas de Programação Linear Inteira e Mista
PRV: Caracterização
1 Função objetivo: Busca minimizar o custo de transporte, distância percorrida, tempo ou até
mesmo o tamanho da frota;
2 Restrições:
a Cada nó ou cliente é visitado uma única vez por um único veículo;
b Cada rota é iniciada num depósito e finalizada no mesmo depósito;
c Todas as demandas ou ofertas de todos os clientes devem ser satisfeitas.
Terminologia para o PRVC
G = (N,A): um grafo completo e não-direcionado;
N = {0, 1, ..., n, n + 1}: é o conjunto de nós;
A = {(i, j) : i, j ∈ N, i 6= j}: é o conjunto de arco;
{0, n + 1}: representam o depósito e sua cópia, onde estão localizados os veículos;
k: Total de veículos (rotas) idênticos
C: Capacidade dos veículos;
i ∈ N = N \ {0, n + 1}: Conjunto de nós cliente;
di ≤ C, ∀i ∈ N : demanda não-negativa.
cij , ∀(i, j) ∈ A: Matriz de custos
Allexandre Fortes S. Reis (UFSJ) Pesquisa Operacional II 22 de agosto de 2017 24 / 40
Problemas de Programação Linear Inteira e Mista
PRV: Caracterização
1 Função objetivo: Busca minimizar o custo de transporte, distância percorrida, tempo ou até
mesmo o tamanho da frota;
2 Restrições:
a Cada nó ou cliente é visitado uma única vez por um único veículo;
b Cada rota é iniciada num depósito e finalizada no mesmo depósito;
c Todas as demandas ou ofertas de todos os clientes devem ser satisfeitas.
Terminologia para o PRVC
G = (N,A): um grafo completo e não-direcionado;
N = {0, 1, ..., n, n + 1}: é o conjunto de nós;
A = {(i, j) : i, j ∈ N, i 6= j}: é o conjunto de arco;
{0, n + 1}: representam o depósito e sua cópia, onde estão localizados os veículos;
k: Total de veículos (rotas) idênticos
C: Capacidade dos veículos;
i ∈ N = N \ {0, n + 1}: Conjunto de nós cliente;
di ≤ C, ∀i ∈ N : demanda não-negativa.
cij , ∀(i, j) ∈ A: Matriz de custos
Allexandre Fortes S. Reis (UFSJ) Pesquisa Operacional II 22 de agosto de 2017 24 / 40
Problemas de Programação Linear Inteira e Mista
Formulação do PRV por Uma Mercadoria para o PRV
min
∑
(i,j)∈A
cijxij
s.t.: ∑
(0,j)∈A
x0j = k
∑
(i,0)∈A
xi0 = k
∑
(i,j)∈A
xij = 1 ∀i ∈ N \ {0}
∑
(i,j)∈A
xij = 1 ∀j ∈ N
∑
(0,j)∈A
f0j =
∑
i∈N
di
∑
(i,j)∈A
fij −
∑
(j,i)∈A
fji = dj ∀j ∈ N
∑
(i,j)∈A
fij ≤ Cxij
xij ∈ {0, 1} ∀(i, j) ∈ A
fij ≥ 0 ∀(i, j) ∈ A
Allexandre Fortes S. Reis (UFSJ) Pesquisa Operacional II 22 de agosto de 2017 25 / 40
Problemas de Programação Linear Inteira e Mista
Formulação por Arcos Capacitados para o PRV
min
∑
q∈Q
∑
(i,j)∈A
cijx
q
ij
s.t.: ∑
q∈Q
q≥dj
∑
(i,j)∈A
x
q
ij = 1 ∀j ∈ N
∑
q∈Q
q≥di
∑
(j,i)∈A
x
q
ji = 1 ∀j ∈ N
∑
q∈Q
∑
(0,j)∈A
x
q
0j = k
∑
(i,n+1)∈A
x
0
i,n+1 = k
∑
(i,j)∈A
x
q
ij =
∑
(j,i)∈A
x
q−dj
ji ∀j ∈ N e ∀q ≥ dj
∑
q∈Q
∑
(0,j)∈A
qx
q
0j =
∑
i∈N
di
x
q
ij ∈ {0, 1} ∀(i, j) ∈ A, q ∈ Q
Allexandre Fortes S. Reis (UFSJ) Pesquisa Operacional II 22 de agosto de 2017 26 / 40
Problemas de Programação Linear Inteira e Mista
Formulação por Duas Mercadorias para o PRV
min
∑
(i,j)∈A
cijxij
s.t.: ∑
j∈N
(fij − fji) = 2di ∀i ∈ N
∑
j∈N
f0j =
∑
i∈N
di
∑
j∈N
fj0 = kC −
∑
i∈N
di
∑
j∈N
f(n+1),j = kC
fij + fji = Cxij ∀{i, j} ∈ A∑
j∈N:i<j
xij +
∑
j∈N:i>j
xji = 2 ∀i ∈ N
fij ≥ 0, fji ≥ 0 ∀{i, j} ∈ A
xij ∈ {0, 1} ∀{i, j} ∈ A
Allexandre Fortes S. Reis (UFSJ) Pesquisa Operacional II 22 de agosto de 2017 27 / 40
Problemas de Programação Linear Inteira e Mista
O Problema da Localização
de Facilidades (PLF)
São dadas n potenciais localizações para a
instalação de facilidades e m clientes que
devem ser atendidos por estas facilidades. O
custo fixo de instalar uma facilidade é igual a
fj , ∀j = 1, . . . , n. Existe também o custo
cij , ∀(i, j) ∈ A para atender um cliente i a
partir da facilidade j. Cada cliente deve ser
alocado a uma única facilidade. Procura-se
então determinar os locais onde devem ser
instaladas as facilidades de modo a minimizar
o custo total. Um cliente só pode ser alocado
a uma facilidade se ela tiver sido instalada.
Allexandre Fortes S. Reis (UFSJ) Pesquisa Operacional II 22 de agosto de 2017 28 / 40
Problemas de Programação Linear Inteira e Mista
Formulação para o PLF
min
n∑
j=1
fjyj +
n∑
j=1
m∑
i=1
cijxij
s.t.:
m∑
i=1
xij ≤ Cjyj , ∀j = 1, . . . , n
n∑
j=1
xij ≥ Di, ∀i = 1, . . . ,m
n∑
j=1
yj ≥ 1
yj ∈ {0, 1} ∀j = 1, . . . , n
xij ≥ 0 ∀(i, j) ∈ A
Aplicações
i Armazéns;
ii Processamento;
iii Lojas;
iv Hospitais;
v Polícia;
vi Bombeiros;
vii Antenas;
viii Estações de Tratamento de Água e Esgoto;
ix Estações de Transporte Público;
x Estações Elétricas e Represas;
Allexandre Fortes S. Reis (UFSJ) Pesquisa Operacional II 22 de agosto de 2017 29 / 40
Problemas de Programação Linear Inteira e Mista
Formulação para o PLF
min
n∑
j=1
fjyj +
n∑
j=1
m∑
i=1
cijxij
s.t.:
m∑
i=1
xij ≤ Cjyj , ∀j = 1, . . . , n
n∑
j=1xij ≥ Di, ∀i = 1, . . . ,m
n∑
j=1
yj ≥ 1
yj ∈ {0, 1} ∀j = 1, . . . , n
xij ≥ 0 ∀(i, j) ∈ A
Aplicações
i Armazéns;
ii Processamento;
iii Lojas;
iv Hospitais;
v Polícia;
vi Bombeiros;
vii Antenas;
viii Estações de Tratamento de Água e Esgoto;
ix Estações de Transporte Público;
x Estações Elétricas e Represas;
Allexandre Fortes S. Reis (UFSJ) Pesquisa Operacional II 22 de agosto de 2017 29 / 40
Problemas de Programação Linear Inteira e Mista
Problemas de Cobertura, Empacotamento e Particionamento
i Covering, Packing and Partitioning Problems;
ii Estrutura semelhante;
iii Selecionar uma coleção de subconjuntos (r) de um conjunto (R);
iv Diversas aplicações em PPLIM;
v Constituindo Cobertura (≥), Empacotamento (≤) ou Partição (=);
Formulações
min
∑
r∈R
crλr
s.t.: ∑
r∈R
airλr≥1 ∀i ∈ N
∑
r∈R
λr = k
λr ∈ {0, 1} ∀r ∈ R
Cobertura
min
∑
r∈R
crλr
s.t.: ∑
r∈R
airλr≤1 ∀i ∈ N
∑
r∈R
λr = k
λr ∈ {0, 1} ∀r ∈ R
Empacotamento
min
∑
r∈R
crλr
s.t.: ∑
r∈R
airλr=1 ∀i ∈ N
∑
r∈R
λr = k
λr ∈ {0, 1} ∀r ∈ R
Particionamento
Allexandre Fortes S. Reis (UFSJ) Pesquisa Operacional II 22 de agosto de 2017 30 / 40
Problemas de Programação Linear Inteira e Mista
Problemas de Cobertura, Empacotamento e Particionamento
i Covering, Packing and Partitioning Problems;
ii Estrutura semelhante;
iii Selecionar uma coleção de subconjuntos (r) de um conjunto (R);
iv Diversas aplicações em PPLIM;
v Constituindo Cobertura (≥), Empacotamento (≤) ou Partição (=);
Formulações
min
∑
r∈R
crλr
s.t.: ∑
r∈R
airλr≥1 ∀i ∈ N
∑
r∈R
λr = k
λr ∈ {0, 1} ∀r ∈ R
Cobertura
min
∑
r∈R
crλr
s.t.: ∑
r∈R
airλr≤1 ∀i ∈ N
∑
r∈R
λr = k
λr ∈ {0, 1} ∀r ∈ R
Empacotamento
min
∑
r∈R
crλr
s.t.: ∑
r∈R
airλr=1 ∀i ∈ N
∑
r∈R
λr = k
λr ∈ {0, 1} ∀r ∈ R
Particionamento
Allexandre Fortes S. Reis (UFSJ) Pesquisa Operacional II 22 de agosto de 2017 30 / 40
Problemas de Programação Linear Inteira e Mista
Problemas de Cobertura, Empacotamento e Particionamento
Considere o conjunto R = {1, 2, 3, 4, 5} e os seguintes subconjuntos r1 = {1, 2}, r2 =
{1, 3, 5}, r3 = {2, 4, 5}, r4 = {3}, r5 = {1}, r6 = {4, 5}
1 Cobertura: requer que a união dos subconjuntos seja igual a R, assim, r1 ∪ r3 ∪ r4 = R;
2 Empacotamento: requer que a união de subconjuntos disjuntos
∗
seja igual a R, assim, r4 ∩
r5 ∩ r6 = ∅;
3 Particionamento: Uma partição é então uma cobertura e empacotamento em relação a R.
Os subconjuntos r1, r4, r6 são disjuntos r1 ∩ r4 ∩ r6 = ∅ e sua união r1 ∪ r4 ∪ r6 = R;
∗
não possuem elementos em comum.
Allexandre Fortes S. Reis (UFSJ) Pesquisa Operacional II 22 de agosto de 2017 31 / 40
Problemas de Programação Linear Inteira e Mista
Problemas de Cobertura, Empacotamento e Particionamento
Considere o conjunto R = {1, 2, 3, 4, 5} e os seguintes subconjuntos r1 = {1, 2}, r2 =
{1, 3, 5}, r3 = {2, 4, 5}, r4 = {3}, r5 = {1}, r6 = {4, 5}
1 Cobertura: requer que a união dos subconjuntos seja igual a R, assim, r1 ∪ r3 ∪ r4 = R;
2 Empacotamento: requer que a união de subconjuntos disjuntos
∗
seja igual a R, assim, r4 ∩
r5 ∩ r6 = ∅;
3 Particionamento: Uma partição é então uma cobertura e empacotamento em relação a R.
Os subconjuntos r1, r4, r6 são disjuntos r1 ∩ r4 ∩ r6 = ∅ e sua união r1 ∪ r4 ∪ r6 = R;
∗
não possuem elementos em comum.
Allexandre Fortes S. Reis (UFSJ) Pesquisa Operacional II 22 de agosto de 2017 31 / 40
Problemas de Programação Linear Inteira e Mista
Problemas de Cobertura, Empacotamento e Particionamento
Considere o conjunto R = {1, 2, 3, 4, 5} e os seguintes subconjuntos r1 = {1, 2}, r2 =
{1, 3, 5}, r3 = {2, 4, 5}, r4 = {3}, r5 = {1}, r6 = {4, 5}
1 Cobertura: requer que a união dos subconjuntos seja igual a R, assim, r1 ∪ r3 ∪ r4 = R;
2 Empacotamento: requer que a união de subconjuntos disjuntos
∗
seja igual a R, assim, r4 ∩
r5 ∩ r6 = ∅;
3 Particionamento: Uma partição é então uma cobertura e empacotamento em relação a R.
Os subconjuntos r1, r4, r6 são disjuntos r1 ∩ r4 ∩ r6 = ∅ e sua união r1 ∪ r4 ∪ r6 = R;
∗
não possuem elementos em comum.
Allexandre Fortes S. Reis (UFSJ) Pesquisa Operacional II 22 de agosto de 2017 31 / 40
Problemas de Programação Linear Inteira e Mista
Problemas de Cobertura, Empacotamento e Particionamento
Considere o conjunto R = {1, 2, 3, 4, 5} e os seguintes subconjuntos r1 = {1, 2}, r2 =
{1, 3, 5}, r3 = {2, 4, 5}, r4 = {3}, r5 = {1}, r6 = {4, 5}
1 Cobertura: requer que a união dos subconjuntos seja igual a R, assim, r1 ∪ r3 ∪ r4 = R;
2 Empacotamento: requer que a união de subconjuntos disjuntos
∗
seja igual a R, assim, r4 ∩
r5 ∩ r6 = ∅;
3 Particionamento: Uma partição é então uma cobertura e empacotamento em relação a R.
Os subconjuntos r1, r4, r6 são disjuntos r1 ∩ r4 ∩ r6 = ∅ e sua união r1 ∪ r4 ∪ r6 = R;
∗
não possuem elementos em comum.
Allexandre Fortes S. Reis (UFSJ) Pesquisa Operacional II 22 de agosto de 2017 31 / 40
Métodos Exatos para PPLI
Mais utilizados
Tem certa inteligência e em comum eles têm a implementação do método Simplex
(Revisado) e do Método de Pontos Interiores (Primal Dual).
i Branch-and-bound ou Ramificar e limitar (1960);
ii Cortes:
I
Cortes de Gomory (1958) e Chvátal-Gomory (1973);
I
Inteiros (Primais e Duais);
I
Combinatórios;
I
Interseção;
I
Método de Decomposição de Benders.
iii Geração de Colunas ou Decomposição de Dantzig-Wolfe (1960);
iv Branch-and-Cut, Branch-and-Price, Branch-Price-and-Cut ou Branch-Cut-and-
Price;
v etc.
Allexandre Fortes S. Reis (UFSJ) Pesquisa Operacional II 22 de agosto de 2017 32 / 40
Métodos Exatos para PPLI
Mais utilizados
Tem certa inteligência e em comum eles têm a implementação do método Simplex
(Revisado) e do Método de Pontos Interiores (Primal Dual).
i Branch-and-bound ou Ramificar e limitar (1960);
ii Cortes:
I
Cortes de Gomory (1958) e Chvátal-Gomory (1973);
I
Inteiros (Primais e Duais);
I
Combinatórios;
I
Interseção;
I
Método de Decomposição de Benders.
iii Geração de Colunas ou Decomposição de Dantzig-Wolfe (1960);
iv Branch-and-Cut, Branch-and-Price, Branch-Price-and-Cut ou Branch-Cut-and-
Price;
v etc.
Allexandre Fortes S. Reis (UFSJ) Pesquisa Operacional II 22 de agosto de 2017 32 / 40
Métodos Exatos para PPLI
Mais utilizados
Tem certa inteligência e em comum eles têm a implementação do método Simplex
(Revisado) e do Método de Pontos Interiores (Primal Dual).
i Branch-and-bound ou Ramificar e limitar (1960);
ii Cortes:
I
Cortes de Gomory (1958) e Chvátal-Gomory (1973);
I
Inteiros (Primais e Duais);
I
Combinatórios;
I
Interseção;
I
Método de Decomposição de Benders.
iii Geração de Colunas ou Decomposição de Dantzig-Wolfe (1960);
iv Branch-and-Cut, Branch-and-Price, Branch-Price-and-Cut ou Branch-Cut-and-
Price;
v etc.
Allexandre Fortes S. Reis (UFSJ) Pesquisa Operacional II 22 de agosto de 2017 32 / 40
Métodos Exatos para PPLI
Mais utilizados
Tem certa inteligência e em comum eles têm a implementação do método Simplex
(Revisado) e do Método de Pontos Interiores (Primal Dual).
i Branch-and-bound ou Ramificar e limitar (1960);
ii Cortes:
I
Cortes de Gomory (1958) e Chvátal-Gomory (1973);
I
Inteiros (Primais e Duais);
I
Combinatórios;
I
Interseção;
I
Método de Decomposição de Benders.
iii Geração de Colunas ou Decomposição de Dantzig-Wolfe (1960);
iv Branch-and-Cut, Branch-and-Price, Branch-Price-and-Cut ou Branch-Cut-and-
Price;
v etc.
Allexandre Fortes S. Reis (UFSJ) Pesquisa Operacional II 22 de agosto de 2017 32 / 40
Métodos Exatos para PPLI
Mais utilizados
Tem certa inteligência e em comum eles têm a implementação do método Simplex
(Revisado) edo Método de Pontos Interiores (Primal Dual).
i Branch-and-bound ou Ramificar e limitar (1960);
ii Cortes:
I
Cortes de Gomory (1958) e Chvátal-Gomory (1973);
I
Inteiros (Primais e Duais);
I
Combinatórios;
I
Interseção;
I
Método de Decomposição de Benders.
iii Geração de Colunas ou Decomposição de Dantzig-Wolfe (1960);
iv Branch-and-Cut, Branch-and-Price, Branch-Price-and-Cut ou Branch-Cut-and-
Price;
v etc.
Allexandre Fortes S. Reis (UFSJ) Pesquisa Operacional II 22 de agosto de 2017 32 / 40
Métodos Exatos para PPLI
Solvers
Em comum eles têm a implementação do método SIMPLEX e do Método
de Pontos Interiores (Primal Dual).
1
IBM ILOG CPLEX;
2
GUROBI;
3
GLPK � GNU Linear Programming Kit;
4
COIN-OR CLP;
5
LINDO;
6
Xpress Optimizer;
7
Solvers de Planilhas Eletrônicas;
8
etc.
Allexandre Fortes S. Reis (UFSJ) Pesquisa Operacional II 22 de agosto de 2017 33 / 40
Métodos Exatos para PPLI
GLPK: O Problema de Localização de Facilidades
Uma companhia está em um processo de planejamento para instalação de novas unidades produtivas, devido ao
aumento da demanda. A instalação pode ocorrer em até 5 locais diferentes (j) e estão preocupadas em atender três
zonas de consumo diferentes (i). Sendo que cada região tem uma demanda mínima (Di) e cada planta tem uma
capacidade produtiva a se considerar, se instalada (Cj).
Dados
Tabela: Custos de conexão
Zonas de Consumo (i)
1 2 3 Oferta
P
l
a
n
t
a
s
(
j
)
1 5 2 3 10000
2 4 3 4 20000
3 9 7 5 30000
4 10 4 2 40000
5 8 4 3 30000
Demanda 30000 20000 20000
Tabela: Custos ($) de
instalação
Plantas (j) Custo ($)
1 175000
2 300000
3 375000
4 500000
5 200000
Allexandre Fortes S. Reis (UFSJ) Pesquisa Operacional II 22 de agosto de 2017 34 / 40
Métodos Exatos para PPLI
GLPK: O Problema de Localização de Facilidades
Uma companhia está em um processo de planejamento para instalação de novas unidades produtivas, devido ao
aumento da demanda. A instalação pode ocorrer em até 5 locais diferentes (j) e estão preocupadas em atender três
zonas de consumo diferentes (i). Sendo que cada região tem uma demanda mínima (Di) e cada planta tem uma
capacidade produtiva a se considerar, se instalada (Cj).
Dados
Tabela: Custos de conexão
Zonas de Consumo (i)
1 2 3 Oferta
P
l
a
n
t
a
s
(
j
)
1 5 2 3 10000
2 4 3 4 20000
3 9 7 5 30000
4 10 4 2 40000
5 8 4 3 30000
Demanda 30000 20000 20000
Tabela: Custos ($) de
instalação
Plantas (j) Custo ($)
1 175000
2 300000
3 375000
4 500000
5 200000
Allexandre Fortes S. Reis (UFSJ) Pesquisa Operacional II 22 de agosto de 2017 34 / 40
Métodos (Meta)Heurísticos para PPLI
Mais utilizados
Trabalham o conceito de alteração da solução corrente e exploração de ótimos locais.
1 Heurísticas Construtivas
2 Heurísticas de Refinamento
i Método da Descida/Subida (Descent/Uphill Method)
ii Busca pelo Primeiro de Melhora
iii Método Randômico de Descida/Subida
iv Método Randômico Não Ascendente/Descendente
v Descida em Vizinhança Variável
vi Busca em Vizinhança de Grande Porte
3 Metaheurísticas
i Busca em Vizinhança Variável
ii Iterated Local Search
iii GRASP
iv Simulated Annealing
v Busca Tabu
vi Multi-Start
vii Guided Local Search
viii Algoritmos Genéticos
ix Scatter Search
x Colônia de Formigas
xi Algoritmos Meméticos
xii Annealing Microcanônico
xiii Otimização Microcanônica
Allexandre Fortes S. Reis (UFSJ) Pesquisa Operacional II 22 de agosto de 2017 35 / 40
Mas o que isso tem a ver com Otimização em Redes?
Matriz Unimodular
Dado um poliedro P = {x ≥ 0|Ax = b}
A = [aij ] e aij ∈ {−1, 0, 1}
det A = −1 ou det A = 1
b ∈ Z+
P = PI = {x ∈ Z+|Ax = b}
Exemplo: ∥∥∥∥∥
1 1 0 −1
−1 0 1 −1
0 −1 0 −1
∥∥∥∥∥
Allexandre Fortes S. Reis (UFSJ) Pesquisa Operacional II 22 de agosto de 2017 36 / 40
Exercício
Indústria Reddy Mikks Ltda
1) A Reddy Mikks produz tintas para interiores e exteriores com base em duas
matérias-primas,M1 eM2. A tabela abaixo apresenta os dados básicos de consumo
e disponibilidade de recursos. Para este problema, escreva o modelo matemático
de PPL, resolva usando o SIMPLEX.
Tabela: Produção de tintas da Reddy Mikks
Interior Exterior disp.
M1 6 4 24
M2 1 2 6
Lucro 5 4
2) Reescreva o modelo agora com a restrição de integralidade e encontre a solução
ótima por inspeção. Em quanto ela se distancia da solução relaxada?
Allexandre Fortes S. Reis (UFSJ) Pesquisa Operacional II 22 de agosto de 2017 37 / 40
Exercício
(a) Figura com Restrições (b) Casca Convexa Contínua e Inteira
Allexandre Fortes S. Reis (UFSJ) Pesquisa Operacional II 22 de agosto de 2017 38 / 40
Dúvidas? Valar joll	oris
Allexandre Fortes S. Reis (UFSJ) Pesquisa Operacional II 22 de agosto de 2017 39 / 40
Referências
(1) Notas de aula Professor Dr. Marco Antônio Carvalho (DECOM/UFOP);
(2) Notas de aula Professor Dr. Gustavo Peixoto (DECOM/UFOP);
(3) Goldbarg, Marco e Goldbarg, Elizabeth. Grafos: Conceitos, algoritmos e apli-
cações (2012);
(4) Taha, Hamdy. Pesquisa Operacional (2008);
Allexandre Fortes S. Reis (UFSJ) Pesquisa Operacional II 22 de agosto de 2017 40 / 40
	Problema Computacional
	Problemas de Programação Linear Inteira e Mista
	Exemplos de PPLI
	Resolução Computacional de PPLI
	Exercícios