182 resultados para Programmation
Resumo:
De nombreux problèmes liés aux domaines du transport, des télécommunications et de la logistique peuvent être modélisés comme des problèmes de conception de réseaux. Le problème classique consiste à transporter un flot (données, personnes, produits, etc.) sur un réseau sous un certain nombre de contraintes dans le but de satisfaire la demande, tout en minimisant les coûts. Dans ce mémoire, on se propose d'étudier le problème de conception de réseaux avec coûts fixes, capacités et un seul produit, qu'on transforme en un problème équivalent à plusieurs produits de façon à améliorer la valeur de la borne inférieure provenant de la relaxation continue du modèle. La méthode que nous présentons pour la résolution de ce problème est une méthode exacte de branch-and-price-and-cut avec une condition d'arrêt, dans laquelle nous exploitons à la fois la méthode de génération de colonnes, la méthode de génération de coupes et l'algorithme de branch-and-bound. Ces méthodes figurent parmi les techniques les plus utilisées en programmation linéaire en nombres entiers. Nous testons notre méthode sur deux groupes d'instances de tailles différentes (gran-des et très grandes), et nous la comparons avec les résultats donnés par CPLEX, un des meilleurs logiciels permettant de résoudre des problèmes d'optimisation mathématique, ainsi qu’avec une méthode de branch-and-cut. Il s'est avéré que notre méthode est prometteuse et peut donner de bons résultats, en particulier pour les instances de très grandes tailles.
Resumo:
Lors du transport du bois de la forêt vers les usines, de nombreux événements imprévus peuvent se produire, événements qui perturbent les trajets prévus (par exemple, en raison des conditions météo, des feux de forêt, de la présence de nouveaux chargements, etc.). Lorsque de tels événements ne sont connus que durant un trajet, le camion qui accomplit ce trajet doit être détourné vers un chemin alternatif. En l’absence d’informations sur un tel chemin, le chauffeur du camion est susceptible de choisir un chemin alternatif inutilement long ou pire, qui est lui-même "fermé" suite à un événement imprévu. Il est donc essentiel de fournir aux chauffeurs des informations en temps réel, en particulier des suggestions de chemins alternatifs lorsqu’une route prévue s’avère impraticable. Les possibilités de recours en cas d’imprévus dépendent des caractéristiques de la chaîne logistique étudiée comme la présence de camions auto-chargeurs et la politique de gestion du transport. Nous présentons trois articles traitant de contextes d’application différents ainsi que des modèles et des méthodes de résolution adaptés à chacun des contextes. Dans le premier article, les chauffeurs de camion disposent de l’ensemble du plan hebdomadaire de la semaine en cours. Dans ce contexte, tous les efforts doivent être faits pour minimiser les changements apportés au plan initial. Bien que la flotte de camions soit homogène, il y a un ordre de priorité des chauffeurs. Les plus prioritaires obtiennent les volumes de travail les plus importants. Minimiser les changements dans leurs plans est également une priorité. Étant donné que les conséquences des événements imprévus sur le plan de transport sont essentiellement des annulations et/ou des retards de certains voyages, l’approche proposée traite d’abord l’annulation et le retard d’un seul voyage, puis elle est généralisée pour traiter des événements plus complexes. Dans cette ap- proche, nous essayons de re-planifier les voyages impactés durant la même semaine de telle sorte qu’une chargeuse soit libre au moment de l’arrivée du camion à la fois au site forestier et à l’usine. De cette façon, les voyages des autres camions ne seront pas mo- difiés. Cette approche fournit aux répartiteurs des plans alternatifs en quelques secondes. De meilleures solutions pourraient être obtenues si le répartiteur était autorisé à apporter plus de modifications au plan initial. Dans le second article, nous considérons un contexte où un seul voyage à la fois est communiqué aux chauffeurs. Le répartiteur attend jusqu’à ce que le chauffeur termine son voyage avant de lui révéler le prochain voyage. Ce contexte est plus souple et offre plus de possibilités de recours en cas d’imprévus. En plus, le problème hebdomadaire peut être divisé en des problèmes quotidiens, puisque la demande est quotidienne et les usines sont ouvertes pendant des périodes limitées durant la journée. Nous utilisons un modèle de programmation mathématique basé sur un réseau espace-temps pour réagir aux perturbations. Bien que ces dernières puissent avoir des effets différents sur le plan de transport initial, une caractéristique clé du modèle proposé est qu’il reste valable pour traiter tous les imprévus, quelle que soit leur nature. En effet, l’impact de ces événements est capturé dans le réseau espace-temps et dans les paramètres d’entrée plutôt que dans le modèle lui-même. Le modèle est résolu pour la journée en cours chaque fois qu’un événement imprévu est révélé. Dans le dernier article, la flotte de camions est hétérogène, comprenant des camions avec des chargeuses à bord. La configuration des routes de ces camions est différente de celle des camions réguliers, car ils ne doivent pas être synchronisés avec les chargeuses. Nous utilisons un modèle mathématique où les colonnes peuvent être facilement et naturellement interprétées comme des itinéraires de camions. Nous résolvons ce modèle en utilisant la génération de colonnes. Dans un premier temps, nous relaxons l’intégralité des variables de décision et nous considérons seulement un sous-ensemble des itinéraires réalisables. Les itinéraires avec un potentiel d’amélioration de la solution courante sont ajoutés au modèle de manière itérative. Un réseau espace-temps est utilisé à la fois pour représenter les impacts des événements imprévus et pour générer ces itinéraires. La solution obtenue est généralement fractionnaire et un algorithme de branch-and-price est utilisé pour trouver des solutions entières. Plusieurs scénarios de perturbation ont été développés pour tester l’approche proposée sur des études de cas provenant de l’industrie forestière canadienne et les résultats numériques sont présentés pour les trois contextes.
Resumo:
Cuadernos para el Diálogo (1963-1978) played a key-role in nurturing the intellectual soil for the Spanish Transition to democracy and it has spawned an extensive amount of literature among historians. This work links for the first time the course of this emblematic monthly journal with the short-lived period of methodological and historiographical innovation of Revista Española de Derecho Internacional under the direction of the international jurist Mariano Aguilar Navarro.
Resumo:
Numérifrag, la première partie de ce mémoire, se présente en tant que code source d’un projet de poésie numérique où les balises html ont été trafiquées de manière esthétique. L’effet répétitif et parasitant du code oblige le lecteur à effectuer un travail de décryptage afin de rendre aux poèmes leur lisibilité. Si le texte est linéaire sur papier, la programmation de chaque poème en tant que page web incite le lecteur à naviguer dans l’œuvre et à actualiser son potentiel d’a-linéarité. La seconde partie de ce mémoire, Corps discursif et dispositif dans Le centre blanc de Nicole Brossard, s’intéresse à la notion de dispositif en tant que subversion, dans le recueil Le centre blanc (1970) de Nicole Brossard. L’élaboration de ce dispositif passe par le corps qui s’exprime au-travers du texte et trouve son souffle chez le lecteur, par l’acte d'interprétation.
Development of new scenario decomposition techniques for linear and nonlinear stochastic programming
Resumo:
Une approche classique pour traiter les problèmes d’optimisation avec incertitude à deux- et multi-étapes est d’utiliser l’analyse par scénario. Pour ce faire, l’incertitude de certaines données du problème est modélisée par vecteurs aléatoires avec des supports finis spécifiques aux étapes. Chacune de ces réalisations représente un scénario. En utilisant des scénarios, il est possible d’étudier des versions plus simples (sous-problèmes) du problème original. Comme technique de décomposition par scénario, l’algorithme de recouvrement progressif est une des méthodes les plus populaires pour résoudre les problèmes de programmation stochastique multi-étapes. Malgré la décomposition complète par scénario, l’efficacité de la méthode du recouvrement progressif est très sensible à certains aspects pratiques, tels que le choix du paramètre de pénalisation et la manipulation du terme quadratique dans la fonction objectif du lagrangien augmenté. Pour le choix du paramètre de pénalisation, nous examinons quelques-unes des méthodes populaires, et nous proposons une nouvelle stratégie adaptive qui vise à mieux suivre le processus de l’algorithme. Des expériences numériques sur des exemples de problèmes stochastiques linéaires multi-étapes suggèrent que la plupart des techniques existantes peuvent présenter une convergence prématurée à une solution sous-optimale ou converger vers la solution optimale, mais avec un taux très lent. En revanche, la nouvelle stratégie paraît robuste et efficace. Elle a convergé vers l’optimalité dans toutes nos expériences et a été la plus rapide dans la plupart des cas. Pour la question de la manipulation du terme quadratique, nous faisons une revue des techniques existantes et nous proposons l’idée de remplacer le terme quadratique par un terme linéaire. Bien que qu’il nous reste encore à tester notre méthode, nous avons l’intuition qu’elle réduira certaines difficultés numériques et théoriques de la méthode de recouvrement progressif.
Resumo:
La « pensée mixte » est une approche de la composition caractérisée par l’interaction de trois pensées: la pensée instrumentale, la pensée électroacoustique et la pensée informatique. Elle prend la forme d’un réseau où le compositeur fait des aller-retours entre les trois pensées et réalise des équivalences paramétriques. La pensée instrumentale se rattache à la tradition de l’écriture occidentale, la pensée électroacoustique fait allusion aux pratiques du studio analogique et de la musique acousmatique, et la pensée informatique fait référence aux pratiques numériques de la programmation visuelle et de l’analyse spectrale. Des lieux communs existent où s’opèrent l’interaction des trois pensées: la notion du studio instrumental de Ivo Malec, la notion de musique concrète instrumentale de Helmut Lachenmann, la composition assistée par ordinateur, la musique spectrale, l’approche instrumentale par montage, la musique acousmatique s’inspirant de la tradition musicale écrite et les musiques mixtes. Ces domaines constituent les influences autour desquelles j’ai composé un corpus de deux cycles d’œuvres: Les Larmes du Scaphandre et le Nano-Cosmos. L’analyse des œuvres met en évidence la notion de « pensée mixte » en abordant la pensée électroacoustique dans ma pratique instrumentale, la pensée informatique dans ma pratique musicale, et la pensée instrumentale dans ma pratique électroacoustique.
Resumo:
Numérifrag, la première partie de ce mémoire, se présente en tant que code source d’un projet de poésie numérique où les balises html ont été trafiquées de manière esthétique. L’effet répétitif et parasitant du code oblige le lecteur à effectuer un travail de décryptage afin de rendre aux poèmes leur lisibilité. Si le texte est linéaire sur papier, la programmation de chaque poème en tant que page web incite le lecteur à naviguer dans l’œuvre et à actualiser son potentiel d’a-linéarité. La seconde partie de ce mémoire, Corps discursif et dispositif dans Le centre blanc de Nicole Brossard, s’intéresse à la notion de dispositif en tant que subversion, dans le recueil Le centre blanc (1970) de Nicole Brossard. L’élaboration de ce dispositif passe par le corps qui s’exprime au-travers du texte et trouve son souffle chez le lecteur, par l’acte d'interprétation.
Development of new scenario decomposition techniques for linear and nonlinear stochastic programming
Resumo:
Une approche classique pour traiter les problèmes d’optimisation avec incertitude à deux- et multi-étapes est d’utiliser l’analyse par scénario. Pour ce faire, l’incertitude de certaines données du problème est modélisée par vecteurs aléatoires avec des supports finis spécifiques aux étapes. Chacune de ces réalisations représente un scénario. En utilisant des scénarios, il est possible d’étudier des versions plus simples (sous-problèmes) du problème original. Comme technique de décomposition par scénario, l’algorithme de recouvrement progressif est une des méthodes les plus populaires pour résoudre les problèmes de programmation stochastique multi-étapes. Malgré la décomposition complète par scénario, l’efficacité de la méthode du recouvrement progressif est très sensible à certains aspects pratiques, tels que le choix du paramètre de pénalisation et la manipulation du terme quadratique dans la fonction objectif du lagrangien augmenté. Pour le choix du paramètre de pénalisation, nous examinons quelques-unes des méthodes populaires, et nous proposons une nouvelle stratégie adaptive qui vise à mieux suivre le processus de l’algorithme. Des expériences numériques sur des exemples de problèmes stochastiques linéaires multi-étapes suggèrent que la plupart des techniques existantes peuvent présenter une convergence prématurée à une solution sous-optimale ou converger vers la solution optimale, mais avec un taux très lent. En revanche, la nouvelle stratégie paraît robuste et efficace. Elle a convergé vers l’optimalité dans toutes nos expériences et a été la plus rapide dans la plupart des cas. Pour la question de la manipulation du terme quadratique, nous faisons une revue des techniques existantes et nous proposons l’idée de remplacer le terme quadratique par un terme linéaire. Bien que qu’il nous reste encore à tester notre méthode, nous avons l’intuition qu’elle réduira certaines difficultés numériques et théoriques de la méthode de recouvrement progressif.
Resumo:
La « pensée mixte » est une approche de la composition caractérisée par l’interaction de trois pensées: la pensée instrumentale, la pensée électroacoustique et la pensée informatique. Elle prend la forme d’un réseau où le compositeur fait des aller-retours entre les trois pensées et réalise des équivalences paramétriques. La pensée instrumentale se rattache à la tradition de l’écriture occidentale, la pensée électroacoustique fait allusion aux pratiques du studio analogique et de la musique acousmatique, et la pensée informatique fait référence aux pratiques numériques de la programmation visuelle et de l’analyse spectrale. Des lieux communs existent où s’opèrent l’interaction des trois pensées: la notion du studio instrumental de Ivo Malec, la notion de musique concrète instrumentale de Helmut Lachenmann, la composition assistée par ordinateur, la musique spectrale, l’approche instrumentale par montage, la musique acousmatique s’inspirant de la tradition musicale écrite et les musiques mixtes. Ces domaines constituent les influences autour desquelles j’ai composé un corpus de deux cycles d’œuvres: Les Larmes du Scaphandre et le Nano-Cosmos. L’analyse des œuvres met en évidence la notion de « pensée mixte » en abordant la pensée électroacoustique dans ma pratique instrumentale, la pensée informatique dans ma pratique musicale, et la pensée instrumentale dans ma pratique électroacoustique.
Resumo:
Les travaux de ce mémoire traitent du problème d’ordonnancement et d’optimisation de la production dans un environnement de plusieurs machines en présence de contraintes sur les ressources matérielles dans une usine d’extrusion plastique. La minimisation de la somme pondérée des retards est le critère économique autour duquel s’articule cette étude car il représente un critère très important pour le respect des délais. Dans ce mémoire, nous proposons une approche exacte via une formulation mathématique capable des donner des solutions optimales et une approche heuristique qui repose sur deux méthodes de construction de solution sérielle et parallèle et un ensemble de méthodes de recherche dans le voisinage (recuit-simulé, recherche avec tabous, GRASP et algorithme génétique) avec cinq variantes de voisinages. Pour être en totale conformité avec la réalité de l’industrie du plastique, nous avons pris en considération certaines caractéristiques très fréquentes telles que les temps de changement d’outils sur les machines lorsqu’un ordre de fabrication succède à un autre sur une machine donnée. La disponibilité des extrudeuses et des matrices d’extrusion représente le goulot d’étranglement dans ce problème d’ordonnancement. Des séries d’expérimentations basées sur des problèmes tests ont été effectuées pour évaluer la qualité de la solution obtenue avec les différents algorithmes proposés. L’analyse des résultats a démontré que les méthodes de construction de solution ne sont pas suffisantes pour assurer de bons résultats et que les méthodes de recherche dans le voisinage donnent des solutions de très bonne qualité. Le choix du voisinage est important pour raffiner la qualité de la solution obtenue. Mots-clés : ordonnancement, optimisation, extrusion, formulation mathématique, heuristique, recuit-simulé, recherche avec tabous, GRASP, algorithme génétique
Resumo:
S’appuyant sur l’histoire du genre et du sport, ce mémoire se penche sur l’un des idéaux masculins québécois de la deuxième moitié du XXe siècle : les « hommes forts ». Ainsi, nous tentons ici de mieux comprendre l’association pour cette période entre la force physique et la masculinité. Pour ce faire, la démonstration examine les compétitions de force inscrites à la programmation de cinq festivals populaires se déroulant entre 1967 et 1990 dans différentes régions forestières du Québec : le Festival des Raftsmen de Hull (1967-1973), le Festival des Sucres de Saint-Jean-de-Matha (1974-1984), le Festival du Bûcheron de Normétal (1975-1987), le Festival de la Grosse Bûche de Saint-Raymond (1976-1990) ainsi que le Festival du Bûcheron de Sainte-Aurélie (1979-1986). La consultation de journaux régionaux a permis de mettre en évidence la persistance du modèle du bûcheron traditionnel québécois malgré une tension présente avec le modèle du bûcheron moderne. Le corpus a également souligné les différentes visions accolées aux concurrents des épreuves par les acteurs présents dans les évènements, fait ressortir la mise en scène d’activités à la fois ludiques et professionnelles, exposé des liens décisifs avec l’histoire régionale, mais particulièrement présenté « l’homme fort » comme modèle masculin, sauf exception.
Resumo:
Méthodologie: Équation de Bellman (Programmation dynamique) ; Méthode de la valeur optionnelle
Resumo:
Les techniques des directions d’arrivée (DOA) sont une voie prometteuse pour accroitre la capacité des systèmes et les services de télécommunications en permettant de mieux estimer le canal radio-mobile. Elles permettent aussi de suivre précisément des usagers cellulaires pour orienter les faisceaux d’antennes dans leur direction. S’inscrivant dans ce contexte, ce présent mémoire décrit étape par étape l’implémentation de l’algorithme de haut niveau MUSIC (MUltiple SIgnal Classification) sur une plateforme FPGA afin de déterminer en temps réel l’angle d’arrivée d’une ou des sources incidentes à un réseau d’antennes. Le concept du prototypage rapide des lois de commande (RCP) avec les outils de XilinxTM System generator (XSG) et du MBDK (Model Based Design Kit) de NutaqTM est le concept de développement utilisé. Ce concept se base sur une programmation de code haut niveau à travers des modèles, pour générer automatiquement un code de bas niveau. Une attention particulière est portée sur la méthode choisie pour résoudre le problème de la décomposition en valeurs et vecteurs propres de la matrice complexe de covariance par l’algorithme de Jacobi. L’architecture mise en place implémentant cette dernière dans le FPGA (Field Programmable Gate Array) est détaillée. Par ailleurs, il est prouvé que MUSIC ne peut effectuer une estimation intéressante de la position des sources sans une calibration préalable du réseau d’antennes. Ainsi, la technique de calibration par matrice G utilisée dans ce projet est présentée, en plus de son modèle d’implémentation. Enfin, les résultats expérimentaux du système mis à l’épreuve dans un environnement réel en présence d’une source puis de deux sources fortement corrélées sont illustrés et analysés.
Resumo:
Les étudiantes et étudiants inscrits dans le programme technique Informatique de gestion au collégial ont comme tâche de concevoir, coder et mettre au point divers programmes informatiques. La capacité pour réaliser cette dernière tâche, soit la mise au point de programmes ou débogage de programmes, est très peu développée chez les élèves. Ils ne prennent pas le temps de vérifier si leurs programmes fonctionnent adéquatement. Selon les superviseurs de stage en milieu de travail, ils ne testent pas assez leurs programmes. La procédure pour supprimer les erreurs de programmation qui leur est proposée ne semble pas suffisante en elle-même pour les soutenir dans leur apprentissage. Les ouvrages consultés sur le sujet de la métacognition nous incitent à penser qu’il manque à la procédure de débogage générale une dimension métacognitive qui pourrait leur être enseignée. L’objectif de cette recherche est de développer une stratégie pédagogique socioconstructiviste intervenant sur la métacognition pour soutenir le développement de la capacité à déboguer des programmes informatiques et à améliorer le sentiment d’auto-efficacité des élèves face à cette tâche. L’autoquestionnement semble être une stratégie métacognitive à développer chez les élèves, car il est primordial que les élèves se questionnent avant de débuter et pendant une tâche quelconque, en particulier celle du débogage de programmes. Trop souvent, les élèves escamotent cette étape d’auto-questionnement, ils ont trop hâte de pianoter sur l’ordinateur et voir si cela fonctionne. Notre type d’essai consiste en l’élaboration d’une intervention pédagogique, sa validation et sa mise à l’essai auprès des élèves. Le matériel nécessaire pour l’intervention a été tiré et adapté du livre sur la métacognition de Lafortune et St-Pierre. Plusieurs activités d’apprentissage ont été construites pour ce projet : un exercice de prise de conscience sur des stratégies d’apprentissage efficaces, une activité d’autoévaluation pour vérifier les connaissances des étudiantes et étudiants sur le débogage de programmes et une troisième activité concernant la planification du processus de résolution de problèmes qui a été reprise tout le long de la session. Ces activités ont été mises à l’essai auprès d’un groupe d’étudiants de 2e année en Technique Informatique à la session Hiver 2004. Les résultats de cette mise à l’essai sont intéressants. Dans un premier temps, l’objectif concernant le développement des habiletés métacognitives de planification a été atteint. De même, le développement de la démarche de débogage a été nettement amélioré, car au début, la démarche était très générale et peu efficace tandis qu’à la fin, la démarche était beaucoup plus structurée et détaillée. L’atteinte de l’objectif, concernant le sentiment d’autoefficacité des élèves, est difficile à évaluer car l’objectif semblait être déjà présent au début selon leurs réponses au questionnaire initial. Cela est très surprenant, car les élèves n’ont pas nécessairement une bonne démarche de débogage mais ils pensent que leur démarche est efficace. Les retombées de ce projet ont permis d’approfondir mes connaissances personnelles au sujet de la métacognition, de l’approche socioconstructiviste et du sentiment d’autoefficacité. En ce qui concerne les élèves, ils ont pris conscience de l’importance du débogage de programmes dans leurs fonctions de travail et ils possèdent une procédure efficace de débogage générale qu’ils peuvent utiliser en tout temps. La stratégie pédagogique, les activités prévues et les outils utilisés nécessitent certains ajustements. Entre autres, utiliser davantage la technique du modelage par le professeur en classe et modifier la procédure générale de débogage en la schématisant pour développer davantage l’autoquestionnement chez les élèves.
Resumo:
Dans un contexte de pression toujours plus grande sur les ressources naturelles, une gestion rationnelle des ressources hydriques s'impose. La principale difficulté de leur gestion provient du caractère aléatoire des apports en eau dans le système. Le sujet de cette recherche consiste à développer des méthodes d'optimisation stochastique capable de bien représenter les processus aléatoires. Le cas de Kemano, située en Colombie-Britannique (Canada), illustre les travaux de recherche. L'importante accumulation de neige sur les bassins versants engendre une hydrologie complexe, rendant la gestion du système délicate. La programmation dynamique stochastique est la méthode la plus utilisée pour déterminer la politique de gestion des réservoirs. Mais, son étude fait ressortir que cette méthode ne peut gérer que des modèles simplifiés des processus stochastiques, ne rendant pas compte des complexes corrélations spatio-temporelles des apports hydriques. Ainsi, la politique obtenue peut être de mauvaise qualité. Cette méthode est comparée avec la recherche directe de politique qui n'utilise pas de modèles pour représenter les processus stochastiques, mais évalue la politique sur des scénarios d'apports. Ainsi la recherche directe de politique se révèle globalement plus performante en prenant bien en considération la complexité des apports, mais est limitée par la forme prédéterminée de la politique. De plus, l'optimisation des paramètres en utilisant un algorithme évolutionnaire s'avère lente. La conception d'un algorithme de descente par gradient, combinée à une architecture "acteur-critique" appropriée, permet de réduire notablement le temps d'optimisation. Combinée à une fonction plus complexe employée pour la paramétrisation de la politique de gestion, la méthode permet d'obtenir une politique de qualité significativement supérieure à celle obtenue avec la programmation dynamique stochastique. Les travaux effectués dans le cadre de cette thèse ouvrent la voie à une application opérationnelle de la méthode de recherche directe de politique. L'évaluation en simulation devrait être appréciée des opérateurs en permettant une bonne représentation du système et des apports.