·
Engenharia de Produção ·
Pesquisa Operacional 2
· 2023/2
Send your question to AI and receive an answer instantly
Recommended for you
16
Slide - Exemplo Resolvido Branch-and-bound - 2023-2
Pesquisa Operacional 2
UFRN
30
Slide - Branch-and-bound - 2023-2
Pesquisa Operacional 2
UFRN
13
Lista - Problema de Transporte Pim - 2023-2
Pesquisa Operacional 2
UFRN
28
Slide - Otimização Combinatória e Programação Inteira - 2023-2
Pesquisa Operacional 2
UFRN
5
Exercício - Branck-and-bound - 2023-2
Pesquisa Operacional 2
UFRN
2
Prova - Pesquisa Operacional 2 2021-2
Pesquisa Operacional 2
UNICAMP
15
Efficient Matheuristics for Solving Production-Routing Problems
Pesquisa Operacional 2
UFSJ
91
Pesquisa Operacional II - Métodos Exatos
Pesquisa Operacional 2
UFSJ
10
Slide - Logística - 2023-2
Pesquisa Operacional 2
UFPR
2
P1 - Pesquisa Operacional 2 - 2023-2
Pesquisa Operacional 2
UFRJ
Preview text
Pesquisa Operacional II Algoritmo de planos de corte Departamento de Engenharia de Produção Universidade Federal do Rio Grande do Norte Melhorando a formulação de programas inteiros Problema de distribuição ◦ n depósitos N = {1,2,...,n} ◦ m clientes M = {1,2,...m} ◦ cij - custo de transporte do depósito j N ao cliente i M. ◦ fj – custo de abertura do depósito j N Quais depósitos abrir de forma a minimizar os custos de distribuição? 2 Melhorando a formulação de programas inteiros Variáveis: xij - fração da demanda do cliente i M atendida pelo depósito j N. 3 senão. 0, é aberto ,1 se o depósito j y j Melhorando a formulação de programas inteiros 4 0 1,0 } { (A1) )1 ( 1 min , x y N j my x D M i x c x y f n j M i ij N j ij j N i M N j ij ij j j x y Melhorando a formulação de programas inteiros 5 (A2) , N j M i y x j ij Restrição alternativa: A formulação fica mais forte substituindo (A1) por (A2)? (A2)=>(A1)? SIM j M i j M i ij j ij my y x y x Melhorando a formulação de programas inteiros 6 (A1) => (A2)? NÃO Suponha x1j =1, x2j = 0, m =2 e yj = 1/2 • (A1) é satisfeita • (A2) não é satisfeita j j j my x x 1 2 1 1/ 2 1 1 j j y x Envoltória convexa Se a formulação for igual a envoltória convexa, a relaxação linear resolve PI ! 7 Método de planos de corte Idéia: tentar aproximar a formulação atual da envoltória convexa. Solução ótima 8 Observações Note que: ◦ não foi preciso "chegar" na envoltória convexa. ◦ não existe a noção de "ramificação", como no branch-and-bound. ◦ cada corte elimina a solução ótima atual do PL. ◦ cada corte não elimina nenhuma solução inteira do problema. ◦ No momento que uma solução inteira é encontrada, ela é a ótima. 9 Dificuldade É necessário encontrar-se um corte que: ◦ elimine a solução ótima do PL atual ◦ não elimine nenhuma solução inteira do problema. Mas como encontrar tais cortes? 10 Cortes de Gomory Resolva a relaxação do PI usando o método simplex. Suponha que o método simplex termina com uma solução fracionária. Então, em alguma linha do dicionário final temos: xi + jN aj xj = bi onde bi é fracionário. 11 Cortes de Gomory Ora uma vez que xi ≥ 0 para todo i, xi + jN aj xj ≤ xi + jN ajxj = bi Uma vez que xi precisa ser inteiro, temos: xi + jN aj xj ≤ bi 12 Exemplo Considere o seguinte problema inteiro: Z x x x x x x x x 2 1 2 1 2 1 2 1 , 4 9 6 4 à sujeito 2 min Z x x x x x x x x x x 2 1 4 2 1 3 2 1 2 1 , 4 9 6 4 à sujeito 2 min 13 Exemplo Resolvemos a relaxação linear deste problema e obtemos uma solução fracionária com x1 = 15/10 e x2=25/10. Uma das linhas do dicionário ótimo é: O corte de Gomory que corta esta solução é dado por 10 25 10 4 10 1 4 3 2 x x x 2 2 x 14 Exemplo Aumentamos então a relaxação linear com o corte encontrado (i.e., x2 + x5 = 2) e resolvemos novamente a relaxação. A solução ótima é desta vez x1 = 3/4 e x2=2. Uma das equações do dicionário ótimo é : O corte de Gomory que corta esta solução é dado por 4 3 4 6 4 1 5 3 1 x x x 0 5 3 1 x x x 15 Exemplo Que em termos das variáveis originais x1 e x2 é: Adicionando-se este corte, temos uma solução ótima inteira com x1 = 1 e x2=2. Logo, esta solução é ótima. 7 5 3 2 1 x x 16 Exemplo −3x₁ + 5x₂ < 7 x₂ < 2 Cortes Especializados Exemplo – Problema de matching Objetivo: Juntar n pessoas nos melhores grupos possíveis de 2. Dados: N = {1,2,...,n} E = { (i,j) NxN: i < j} Cij – valor do par (i,j) 18 Cortes Especializados 19 E i j x N l x x x c ij j l lj l i il ij E j i ij 1,0 } ( , ) { 1 a sujeito max ( , ) , ) ( ( , ) Cortes Especializados 20 1 2 3 6 4 5 1 1 1 1 1 1 0 0 As outras arestas tem cij = - A solução ótima inteira tem custo igual a 2 A solução ótima da relaxação tem custo igual a 3 0.5 0.5 0.5 0.5 0.5 0.5 Cortes Especializados Um corte válido para eliminar esta solução é A relaxação munida desta restrição resulta em uma solução inteira => solução ótima! Generalização da restrição 21 6} ,5,4 { 3,2 } ,1 { 1 j i ijx |impar | 1 S N S x S j S i ij Número de restrições muito grande Cortes Especializados Problema da mochila Para k ≥ 1 e = {i | wi > W/k}, temos o seguinte corte válido: 1 i i k x i x W x w x c i i i i i i i 1,0 } { a sujeito max Branch-and-Bound vs. Planos de Corte Embora mais elegante, planos de corte exigem podem convergir muito lentamente (e.g. cortes de Gomory). Em geral, os pequisadores procuram cortes capazes de cortar o máximo possível do poliedro em questão. Métodos de branch-and-bound possuem várias escolhas a serem testadas. Se escolhas ruins forem tomadas, o número de nós pode rapidamente ocupar todo o espaço de memória do computador. Idéia: branch-and-cut! 23 Caixeiro Viajante HELP! WE'RE LOST! HELP "CAR 54"... AND WIN CASH 54...$1,000 PRIZES ONE...$10,000 GRAND PRIZE © PROCTER & GAMBLE 1962 Help Toody and Muldoon find the shortest round trip route to visit all locations shown on the map. All you do is draw connecting straight lines from location to location to show the shortest round trip route. HERE'S THE CORRECT START... Begin At Chicago, Illinois. From there, lines show correct route as far as Carlisle, Pennsylvania. Next, do you go to Bakersville, Maine or Vines, West Virginia? Check the easy instructions on back of this entry blank for details. Caixeiro Viajante Caixeiro Viajante 25 Explosão combinatória Número de soluções do Caixeiro Viajante é O(n!) n (n-1)! Tempo de CPU 5 24 insignificante 10 362.880 0.003s 15 87 bilhões 20 min 20 1.2x1017 73 anos 25 6.2x1023 470 milhões de anos 26 Modelo Definição das variáveis ◦ Xij =1 se o caixeiro vai diretamente da cidade i para a cidade j, e Xij =0 caso contrário. Definição da função objetivo 27 n i n j ijxij c 1 1 min Modelo Definição das restrições ◦ Deixa-se a cidade i exatamente uma vez ◦ Chega-se na cidade j exatamente uma vez 28 j i j ij n i x : 1,..., para 1 j ii ij n j x : 1,..., 1para Modelo Subrotas ◦ Restrições de eliminação de subrotas. 29 1 , para2 1para n S N S S x i S S j ij
Send your question to AI and receive an answer instantly
Recommended for you
16
Slide - Exemplo Resolvido Branch-and-bound - 2023-2
Pesquisa Operacional 2
UFRN
30
Slide - Branch-and-bound - 2023-2
Pesquisa Operacional 2
UFRN
13
Lista - Problema de Transporte Pim - 2023-2
Pesquisa Operacional 2
UFRN
28
Slide - Otimização Combinatória e Programação Inteira - 2023-2
Pesquisa Operacional 2
UFRN
5
Exercício - Branck-and-bound - 2023-2
Pesquisa Operacional 2
UFRN
2
Prova - Pesquisa Operacional 2 2021-2
Pesquisa Operacional 2
UNICAMP
15
Efficient Matheuristics for Solving Production-Routing Problems
Pesquisa Operacional 2
UFSJ
91
Pesquisa Operacional II - Métodos Exatos
Pesquisa Operacional 2
UFSJ
10
Slide - Logística - 2023-2
Pesquisa Operacional 2
UFPR
2
P1 - Pesquisa Operacional 2 - 2023-2
Pesquisa Operacional 2
UFRJ
Preview text
Pesquisa Operacional II Algoritmo de planos de corte Departamento de Engenharia de Produção Universidade Federal do Rio Grande do Norte Melhorando a formulação de programas inteiros Problema de distribuição ◦ n depósitos N = {1,2,...,n} ◦ m clientes M = {1,2,...m} ◦ cij - custo de transporte do depósito j N ao cliente i M. ◦ fj – custo de abertura do depósito j N Quais depósitos abrir de forma a minimizar os custos de distribuição? 2 Melhorando a formulação de programas inteiros Variáveis: xij - fração da demanda do cliente i M atendida pelo depósito j N. 3 senão. 0, é aberto ,1 se o depósito j y j Melhorando a formulação de programas inteiros 4 0 1,0 } { (A1) )1 ( 1 min , x y N j my x D M i x c x y f n j M i ij N j ij j N i M N j ij ij j j x y Melhorando a formulação de programas inteiros 5 (A2) , N j M i y x j ij Restrição alternativa: A formulação fica mais forte substituindo (A1) por (A2)? (A2)=>(A1)? SIM j M i j M i ij j ij my y x y x Melhorando a formulação de programas inteiros 6 (A1) => (A2)? NÃO Suponha x1j =1, x2j = 0, m =2 e yj = 1/2 • (A1) é satisfeita • (A2) não é satisfeita j j j my x x 1 2 1 1/ 2 1 1 j j y x Envoltória convexa Se a formulação for igual a envoltória convexa, a relaxação linear resolve PI ! 7 Método de planos de corte Idéia: tentar aproximar a formulação atual da envoltória convexa. Solução ótima 8 Observações Note que: ◦ não foi preciso "chegar" na envoltória convexa. ◦ não existe a noção de "ramificação", como no branch-and-bound. ◦ cada corte elimina a solução ótima atual do PL. ◦ cada corte não elimina nenhuma solução inteira do problema. ◦ No momento que uma solução inteira é encontrada, ela é a ótima. 9 Dificuldade É necessário encontrar-se um corte que: ◦ elimine a solução ótima do PL atual ◦ não elimine nenhuma solução inteira do problema. Mas como encontrar tais cortes? 10 Cortes de Gomory Resolva a relaxação do PI usando o método simplex. Suponha que o método simplex termina com uma solução fracionária. Então, em alguma linha do dicionário final temos: xi + jN aj xj = bi onde bi é fracionário. 11 Cortes de Gomory Ora uma vez que xi ≥ 0 para todo i, xi + jN aj xj ≤ xi + jN ajxj = bi Uma vez que xi precisa ser inteiro, temos: xi + jN aj xj ≤ bi 12 Exemplo Considere o seguinte problema inteiro: Z x x x x x x x x 2 1 2 1 2 1 2 1 , 4 9 6 4 à sujeito 2 min Z x x x x x x x x x x 2 1 4 2 1 3 2 1 2 1 , 4 9 6 4 à sujeito 2 min 13 Exemplo Resolvemos a relaxação linear deste problema e obtemos uma solução fracionária com x1 = 15/10 e x2=25/10. Uma das linhas do dicionário ótimo é: O corte de Gomory que corta esta solução é dado por 10 25 10 4 10 1 4 3 2 x x x 2 2 x 14 Exemplo Aumentamos então a relaxação linear com o corte encontrado (i.e., x2 + x5 = 2) e resolvemos novamente a relaxação. A solução ótima é desta vez x1 = 3/4 e x2=2. Uma das equações do dicionário ótimo é : O corte de Gomory que corta esta solução é dado por 4 3 4 6 4 1 5 3 1 x x x 0 5 3 1 x x x 15 Exemplo Que em termos das variáveis originais x1 e x2 é: Adicionando-se este corte, temos uma solução ótima inteira com x1 = 1 e x2=2. Logo, esta solução é ótima. 7 5 3 2 1 x x 16 Exemplo −3x₁ + 5x₂ < 7 x₂ < 2 Cortes Especializados Exemplo – Problema de matching Objetivo: Juntar n pessoas nos melhores grupos possíveis de 2. Dados: N = {1,2,...,n} E = { (i,j) NxN: i < j} Cij – valor do par (i,j) 18 Cortes Especializados 19 E i j x N l x x x c ij j l lj l i il ij E j i ij 1,0 } ( , ) { 1 a sujeito max ( , ) , ) ( ( , ) Cortes Especializados 20 1 2 3 6 4 5 1 1 1 1 1 1 0 0 As outras arestas tem cij = - A solução ótima inteira tem custo igual a 2 A solução ótima da relaxação tem custo igual a 3 0.5 0.5 0.5 0.5 0.5 0.5 Cortes Especializados Um corte válido para eliminar esta solução é A relaxação munida desta restrição resulta em uma solução inteira => solução ótima! Generalização da restrição 21 6} ,5,4 { 3,2 } ,1 { 1 j i ijx |impar | 1 S N S x S j S i ij Número de restrições muito grande Cortes Especializados Problema da mochila Para k ≥ 1 e = {i | wi > W/k}, temos o seguinte corte válido: 1 i i k x i x W x w x c i i i i i i i 1,0 } { a sujeito max Branch-and-Bound vs. Planos de Corte Embora mais elegante, planos de corte exigem podem convergir muito lentamente (e.g. cortes de Gomory). Em geral, os pequisadores procuram cortes capazes de cortar o máximo possível do poliedro em questão. Métodos de branch-and-bound possuem várias escolhas a serem testadas. Se escolhas ruins forem tomadas, o número de nós pode rapidamente ocupar todo o espaço de memória do computador. Idéia: branch-and-cut! 23 Caixeiro Viajante HELP! WE'RE LOST! HELP "CAR 54"... AND WIN CASH 54...$1,000 PRIZES ONE...$10,000 GRAND PRIZE © PROCTER & GAMBLE 1962 Help Toody and Muldoon find the shortest round trip route to visit all locations shown on the map. All you do is draw connecting straight lines from location to location to show the shortest round trip route. HERE'S THE CORRECT START... Begin At Chicago, Illinois. From there, lines show correct route as far as Carlisle, Pennsylvania. Next, do you go to Bakersville, Maine or Vines, West Virginia? Check the easy instructions on back of this entry blank for details. Caixeiro Viajante Caixeiro Viajante 25 Explosão combinatória Número de soluções do Caixeiro Viajante é O(n!) n (n-1)! Tempo de CPU 5 24 insignificante 10 362.880 0.003s 15 87 bilhões 20 min 20 1.2x1017 73 anos 25 6.2x1023 470 milhões de anos 26 Modelo Definição das variáveis ◦ Xij =1 se o caixeiro vai diretamente da cidade i para a cidade j, e Xij =0 caso contrário. Definição da função objetivo 27 n i n j ijxij c 1 1 min Modelo Definição das restrições ◦ Deixa-se a cidade i exatamente uma vez ◦ Chega-se na cidade j exatamente uma vez 28 j i j ij n i x : 1,..., para 1 j ii ij n j x : 1,..., 1para Modelo Subrotas ◦ Restrições de eliminação de subrotas. 29 1 , para2 1para n S N S S x i S S j ij