·

Engenharia de Produção ·

Pesquisa Operacional 2

· 2023/2

Send your question to AI and receive an answer instantly

Ask Question

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 + jN aj xj = bi onde bi é fracionário. 11 Cortes de Gomory  Ora uma vez que xi ≥ 0 para todo i, xi + jN aj xj ≤ xi + jN ajxj = bi  Uma vez que xi precisa ser inteiro, temos: xi + jN 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