Show simple document record

dc.contributor.advisorDion, Jean-Guyfr
dc.contributor.advisorBenchakroun, Abdelhamidfr
dc.contributor.authorBlanchette, Carlfr
dc.date.accessioned2014-05-16T15:35:31Z
dc.date.available2014-05-16T15:35:31Z
dc.date.created2004fr
dc.date.issued2004fr
dc.identifier.urihttp://savoirs.usherbrooke.ca/handle/11143/4633
dc.description.abstractDans 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.fr
dc.language.isofrefr
dc.publisherUniversité de Sherbrookefr
dc.rights© Carl Blanchettefr
dc.titleNouvelles formulations et algorithmes inédits pour le problème de découpe bidimentionnellefr
dc.typeMémoirefr
tme.degree.disciplineMathématiquesfr
tme.degree.grantorFaculté des sciencesfr
tme.degree.levelMaîtrisefr
tme.degree.nameM. Sc.fr


Files in this document

Thumbnail

This document appears in the following Collection(s)

Show simple document record