Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Programmation lineaire en nombres entiers premiere partie pdf

Université Abdelmalek Essa? di Faculté Polydisciplinaire de Tétouan Programmation linéaire en nombres entiers Prof M EL MEROUANI Département de Statistique et Informatique Appliquées à la Gestion Pr Mohamed El Merouani Introduction ? La plupart des problèmes issus de la gestion des Entreprises se présentent sous forme de programmes linéaires dont les variables prennent des valeurs entières ? Par exemple les problèmes provenant de la GRH problèmes d ? a ?ectation les problèmes d ? allocation des ressources problème de sac à dos les problèmes d ? emploi du temps ? etc ? Ce type de problèmes s ? appellent programmes linéaires en nombres entiers Pr Mohamed El Merouani C Méthodes na? ves ? Pour résoudre cette classe de problèmes dans le cas o? le domaine réalisable est ?ni nous pouvons être tentés par les méthodes na? ves ? Les méthodes na? ves ?? Méthode d ? arrondi Arrondir la solution optimale du problème continu ?? Méthode d ? énumération explicite de toutes les solutions réalisables Seulement certains problème de petite taille Pr Mohamed El Merouani Exemple montrant que la méthode d ? arrondi est limitée Min Z -x -x Sujet à - x x x - x x x ? et entières Ce problème admet comme solution optimale continue x t avec Z - Par la méthode graphique ou le Simplexe Pr Mohamed El Merouani C Exemple montrant que la méthode d ? arrondi est limitée ? Les solutions arrondies sont x t avec Z ?? et x t avec Z ?? Remarquons que ces solutions arrondies x et x ne sont pas réalisables et en plus elles sont très éloignées de la solution optimale entière x t du problème Pr Mohamed El Merouani Limite de la méthode d ? énumération explicite ? Considérons un problème de programmation linéaire en nombres entiers et distinguons à titre d ? exemple les deux cas suivants ?? Cas variables ? ? ce qui donne soit plus de cas ?? Cas variables binaires soit cas Ces deux exemples montrent clairement que même avec des problèmes de tailles moyennes le nombre de comparaisons à e ?ectuer par la méthode d ? énumération explicite est tellement grand que la méthode devient ine ?cace Pr Mohamed El Merouani C Méthodes e ?caces ? Méthode de Séparation et Évaluation Branch Bound Method ? Méthode de coupes ? Méthode de Benders ? Méthode des Groupes Pr Mohamed El Merouani Préliminaire ? Considérons le problème de programmation linéaire en nombres entiers Min ctx PLE Sujet à Ax ? b x ? et entier avec x x x ? xn t c c c ? cn t b b b ? bm t et A est une matrice réelle de type m n Pr Mohamed El Merouani C Préliminaire ? On parlera de problème de programmation linéaire continue lorsqu ? on ne prend pas en considération les contraintes d ? intégrité on dira qu ? on a relaxé ces contraintes ? Par contre si certaines variables peuvent ne pas être entières