• Français
    • English
  • Français 
    • Français
    • English
  • Se connecter
Visualiser le document 
  •   Accueil de Savoirs UdeS
  • Sciences
  • Sciences – Mémoires
  • Visualiser le document
  •   Accueil de Savoirs UdeS
  • Sciences
  • Sciences – Mémoires
  • Visualiser le document
JavaScript is disabled for your browser. Some features of this site may not work without it.

Parcourir

Tout Savoirs UdeSDomaines et collectionsDates de publicationAuteursTitresSujetsDirecteursCette collectionDates de publicationAuteursTitresSujetsDirecteurs

Mon compte

Se connecter

Statistiques

Voir les statistiques d'utilisation

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

Thumbnail
Visualiser/Ouvrir
blanchette_carl_MSc_2004.pdf (12.92Mb)
Date de publication
2004
Auteur(s)
Blanchette, Carl
Afficher la notice détaillée
Résumé
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 [1706]

DSpace software [version 5.4 XMLUI], copyright © 2002-2015  DuraSpace
Communiquer avec nous | Envoyer des commentaires
 

 


DSpace software [version 5.4 XMLUI], copyright © 2002-2015  DuraSpace
Communiquer avec nous | Envoyer des commentaires