• Français
    • English
  • Français 
    • Français
    • English
  • Login
View Document 
  •   Savoirs UdeS Home
  • Sciences
  • Sciences – Mémoires
  • View Document
  •   Savoirs UdeS Home
  • Sciences
  • Sciences – Mémoires
  • View Document
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

All of Savoirs UdeSDomains & CollectionsBy Issue DateAuthorsTitlesSubjectsDirectorsThis CollectionBy Issue DateAuthorsTitlesSubjectsDirectors

My Account

Login

Statistics

View Usage Statistics

Nouvelles formulations et algorithmes inédits pour le problème de découpe bidimentionnelle

Thumbnail
View/Open
MR05880.pdf (7.642Mb)
Publication date
2004
Author(s)
Blanchette, Carl
Show full document record
Abstract
Dans ce mémoire, il sera question du problème de découpe à deux dimensions fréquemment rencontré dans l’industrie du papier, du verre et du textile. Ce problème consiste à découper un ensemble de rectangles de dimensions et de valeurs connues à partir d’un patron rectangulaire en cherchant à maximiser la valeur totale des rectangles découpés ou à minimiser la perte obtenue lors de cette coupe. Dans un premier temps, nous formulons le problème comme un modèle général non linéaire maximisant la valeur totale découpée et nous effectuons ensuite certaines transformations afin d’obtenir un modèle de programmation linéaire mixte. Nous présentons également une suite de variantes qui diffèrent du modèle principal au niveau de certaines contraintes. Cela a pour but d’améliorer la résolution du programme relaxé augmentant ainsi l’efficacité de l’approche algorithmique. Afin de résoudre la variante la plus efficace, nous présentons une nouvelle approche basée sur diverses relaxations lagrangiennes de celle-ci pour minimiser la borne supérieure obtenue à l’aide d’une méthode de sous-gradients. Enfin, nous construisons une procédure basée sur une technique arborescente utilisant une borne inférieure associée à une solution réalisable provenant habituellement d’une heuristique qui génère celle-ci à partir de la solution du problème lagrangien. Finalement, des problèmes tests (de petites et moyennes dimensions) tirés de la littérature ou générés aléatoirement démontrent la performance de notre algorithme.
URI
http://savoirs.usherbrooke.ca/handle/11143/4633
Collection
  • Sciences – Mémoires [1658]

DSpace software [version 5.4 XMLUI], copyright © 2002-2015  DuraSpace
Contact Us | Send Feedback
 

 


DSpace software [version 5.4 XMLUI], copyright © 2002-2015  DuraSpace
Contact Us | Send Feedback