Optimisation d'un problème de programmation linéaire en nombres entiers par la méthode Branch and Bound
Loading...
Date
2017
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
UMMTO
Abstract
Quelques problèmes de la vie courante peuvent être modélisés comme des problèmes combinatoires.Dans notre travail, nous nous intéressons à la résolution des problèmes de programmation linéaire en nombres entiers par la méthode : " Séparation et ?valuation", "Branch and Bound".
Nous présentons les méthodes de résolutions de problèmes d'optimisation proposées dans la littérature. Notre travail est devisé en trois chapitres :
Le premier chapitre présente quelques définitions dont : la programmation mathématique, la programmation linéaire et quelques généralités sur la classification des problèmes et les méthodes de résolutions de problèmes d'optimisation.
Dans le deuxième chapitre, on se focalise sur les méthodes de résolutions exactes. Nous avons illustré avec un exemple chacune de ces méthodes : la méthode graphique, la méthode du simplexe et la méthode dual du simplexe. Onprésente aussi les deux algorithmes : L'algorithme du simplexe et l'algorithme dual du simplexe.
Le troisième chapitre est consacré à la méthode de Séparation et ?valuation "Branch and Bound". Nous avons présenté la méthode, son principe, ces trois procédures essentielles et les trois stratégies de parcours, ainsi que l'algorithme général de la méthode et un exemple d'application avec une implémentation informatique en utilisant le logiciel MATLAB version 2014 et le LpSolve IDE.
Description
41 f.; ill. : 30 cm +(CD-Rom)
Keywords
Programmation linéaire, Programmation mathématique, Simplexe, Branch and Bound, Programmation en nombres entiers