1 |
Métodos exatos baseados em relaxação lagrangiana e surrogate para o problema de carregamento de paletes do produtor.Oliveira, Lilian Kátia de 13 December 2004 (has links)
Made available in DSpace on 2016-06-02T19:50:17Z (GMT). No. of bitstreams: 1
TeseLKO.pdf: 834201 bytes, checksum: 994d7b70c6b1001f9dec962fafc8b72e (MD5)
Previous issue date: 2004-12-13 / Universidade Federal de Sao Carlos / The purpose of this work is to develop exact methods, based on
Lagrangean and Surrogate relaxation, with good performance to solve the
manufacturer s pallet loading problem. This problem consists of orthogonally arranging
the maximum number of rectangles of sizes (l,w) and (w,l) into a larger rectangle (L,W)
without overlapping. Such methods involve a tree search procedure of branch and
bound type and they use, in each node of the branch and bound tree, bounds derived
from Lagrangean and/or Surrogate relaxations of a 0-1 linear programming formulation.
Subgradient optimization algorithms are used to optimize such bounds. Problem
reduction tests and Lagrangean and Surrogate heuristics are also applied in the
subgradient optimization to obtain good feasible solution. Computational experiments
were performed with instances from the literature and also real instances obtained from
a carrier. The results show that the methods are able to solve these instances, on
average, more quickly than other exact methods, including the software
GAMS/CPLEX. / O objetivo deste trabalho é desenvolver métodos exatos, baseados em
relaxação Lagrangiana e Surrogate, com bom desempenho para resolver o problema de
carregamento de paletes do produtor. Tal problema consiste em arranjar ortogonalmente
e sem sobreposição o máximo número de retângulos de dimensões ( , ) l w ou ( , ) w l
sobre um retângulo maior ( , ) L W . Tais métodos exatos são procedimentos de busca em
árvore do tipo branch and bound que, em cada nó, utilizam limitantes derivados de
relaxações Lagrangiana e/ou Surrogate de uma formulação de programação linear 0 1 − .
Algoritmos de otimização do subgradiente são usados para otimizar estes limitantes.
São aplicados ainda testes de redução do problema e heurísticas Lagrangiana e
Surrogate na otimização do subgradiente para obter boas soluções factíveis. Testes
computacionais foram realizados utilizando exemplos da literatura e exemplos reais,
obtidos de uma transportadora. Os resultados mostram que os métodos são capazes de
resolvê-los, em média, mais rapidamente do que outros métodos exatos, incluindo o
software GAMS/CPLEX.
|
Page generated in 0.0734 seconds