Logística/Sistemas de distribuição/Escala de veículos/Algoritmos Branch and Bound para CPEV: diferenças entre revisões
| [edição não verificada] | [edição não verificada] |
Conteúdo apagado Conteúdo adicionado
Sem resumo de edição |
Sem resumo de edição |
||
Linha 2:
:O método [http://en.wikipedia.org/wiki/Branch_and_bound
▲:O método [http://en.wikipedia.org/wiki/Branch_and_bound <i>Branch and Bound</i>] é uma técnica [[w:Algoritmo|algoritmica]], que permite encontrar uma solução óptima de problemas de [[w:Otimização combinatória|optimização]], tem vindo a ser utilizado nos últimos anos na resolução de CPEV simétrico e assimétrico (ACPEV). Mantendo a melhor solução encontrada até até então, ou seja, se a nova solução encontrada for pior que a anterior é abandonada. Por exemplo Imaginando que se pretende fazer uma viagem Lisboa-Porto, em que pela A1 o percurso seriam cerca de 300Km. A próxima solução a procurar terá de ser inferior, caso contrário é abandonada; pois o objectivo é minimizar a distância.
*'''Pode também ter aplicação noutras áreas como:'''
Linha 16 ⟶ 14:
** Problema do corte de stock, [http://en.wikipedia.org/wiki/Cutting_stock_problem <i>Cutting stock problem</i>] (em Inglês)
:Todavia para amostras com maior dimensão, mais complexas ou até para encontrar uma solução mais rapidamente ([[Logística/Referências#refbPEVE|Dorronsoro]] (2007) refere,
▲:Todavia para amostras com maior dimensão, mais complexas ou até para encontrar uma solução mais rapidamente, utilizam-se outros métodos mais eficazes como por exemplo [http://pt.wikipedia.org/wiki/Heur%C3%ADstica_%28computa%C3%A7%C3%A3o%29 heurísticos]. Pois o problema cria árvores muito extensas, o que não torna fácil a sua resolução. ([[Logística/Referências#refbPEVE|AUREN, 2007]])
:Abordado inicialmente por <i>A. H. Land</i> e <i>A. G. Doig</i> em 1960, pioneiros nesta temática no artigo [http://www.jstor.org/pss/1910129 <i>"An automatic method of solving discrete programs problems"</i>] no jornal <i>Econometrica</i>, onde apresentaram um algoritmo númerico simples para programação discreta (que continha variáveis discretas, bem como contínuas). Todavia num trabalho em paralelo <i>Murty, Karel e Little</i> (1962), focavam-se num tipo específico de programação discreta.([[Logística/Referências#refbPEVF|BRUSCO, 2005 , p.4 a 6]])▼
:Por forma, o método [http://www.jstor.org/pss/171617?cookieSet=1 <i>K-Tree</i>] proposto por <i>Fisher</i> um dos mais utilizados, no que se refere a aproximação exacta (na resolução especifica de CPEV). ▼
:Conseguiu resolver um problema com 71 clientes; contudo existem problemas com amostras menores, que ainda não têm solução, devido a algumas restrições inerentes. ([[Logística/Referências#refbPEVE|AUREN, 2007]])▼
▲:Abordado inicialmente por
▲:Por forma, o método [http://www.jstor.org/pss/171617?cookieSet=1 <i>K-Tree</i>] proposto por
▲:Conseguiu resolver um problema com 71 clientes; contudo existem problemas com amostras menores, que ainda não têm solução, devido a algumas restrições inerentes.
:Recentemente como referido,
:Assim
:A solução dessa relaxação produz um limite inferior ao valor de uma solução óptima. Se a solução de relaxação pertencer a <math>\ S</math> ou tenha um custo igual <math>\ \hat s </math> (onde <math>\ \hat s \in S </math>), então a nova solução ou <math>\ \hat s </math> é óptima.
:Caso contrário de acordo com [[Logística/Referências#refbPEVE|Dorronsoro]] (2007), identifica-mos <math>\ n</math> sub-sistemas de <math>\ S
*
*Em caso de não ser encontrada uma solução para o sub-problema esse é abandonada.
*Por outro lado compara-se o limite inferior do sub-problema, com o limite global superior, dado pelo melhor valor encontrado até então. Se for maior ou igual que o actual é abandonado.
*Por final se não for possível abandonar o sub-problema, somo forçados a processar e adicionar o sub-problema à lista de candidatos activos. Segue-se este ciclo até não existirem mais candidatos a sub-problemas, nesse ponto a nossa melhor solução é óptima.
{{AutoCat}}
| |||