Remerciez-le!

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

13/05/2015 1 Programmation linéaire en nombres entiers Prof. M. EL MEROUANI Dép

13/05/2015 1 Programmation linéaire en nombres entiers Prof. M. EL MEROUANI Département de Statistique et Informatique Appliquées à la Gestion 1 Pr. Mohamed El Merouani Université Abdelmalek Essaâdi Faculté Polydisciplinaire de Tétouan 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’affectation), 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. 2 Pr. Mohamed El Merouani 13/05/2015 2 Méthodes naïves • Pour résoudre cette classe de problèmes, dans le cas où le domaine réalisable est fini, 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 3 Pr. Mohamed El Merouani Exemple montrant que la méthode d’arrondi est limitée Min Z=-x1-x2 Sujet à -2x1+2x2=1 16x1-14x2=7 x1,x2≥0 et entières Ce problème admet comme solution optimale continue: x=(7; 7.5)t avec Z=-14.5 (Par la méthode graphique ou le Simplexe) 4 Pr. Mohamed El Merouani 13/05/2015 3 Exemple montrant que la méthode d’arrondi est limitée • Les solutions arrondies sont: Remarquons que ces solutions arrondies et ne sont pas réalisables et, en plus, elles sont très éloignées de la solution optimale entière x*=(3;3)t du problème 5 t 7) (7; x = 14 − = Z t 8) (7; x ~ = 15 ~ − = Z avec avec et x x ~ 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 1: 10 variables є {1,2,3,…,9},ce qui donne: 910=3 486 784 401, soit plus de 3.109 cas, – Cas 2: 50 variables binaires, soit 250 cas. Ces deux exemples montrent clairement que même avec des problèmes de tailles moyennes, le nombre de comparaisons à effectuer par la méthode d’énumération explicite est tellement grand que la méthode devient inefficace. 6 Pr. Mohamed El Merouani 13/05/2015 4 Méthodes efficaces • Méthode de Séparation et Évaluation (Branch & Bound Method), • Méthode de coupes, • Méthode de Benders, • Méthode des Groupes. 7 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≥0 et entier avec x=(x1,x2,…,xn)t, c=(c1,c2,…,cn)t, b=(b1,b2,…,bm)t et A est une matrice réelle de type (m,n). 8 Pr. Mohamed El Merouani 13/05/2015 5 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, alors on dira qu’on a un problème de programmation linéaire mixte. 9 Pr. Mohamed El Merouani Notations (P) : problème d’optimisation F(P) : domaine réalisable de (P) V(P) : valeur optimale de (P) 10 Pr. Mohamed El Merouani 13/05/2015 6 Notions de base • Notion de Partitionnement, • Notion de Relaxation, • Notion de Suspension de fouille (Stérilisation ou Fathoming) 11 Pr. Mohamed El Merouani Partitionnement • On dit que le problème (P) est partitionné en sous-problèmes (P1), (P2), …, (Pq) si F(P1), …, F(Pq) constituent une partition de F(P). Autrement dit, si: 1. toute solution réalisable de (P) est réalisable pour exactement un sous-problème (Pj); 2. toute solution réalisable pour l’un des sous- problèmes (Pj) est réalisable pour (P). 12 Pr. Mohamed El Merouani 13/05/2015 7 Exemple • Le problème (P) dont le domaine réalisable F(P)={xj=0 ou 1} peut être partitionné en deux problèmes (P1) et (P2) de même fonction objectif et ayant respectivement comme domaine réalisable: F(P1)={xj=0} et F(P2)={xj=1} 13 Pr. Mohamed El Merouani Exemple • Le problème (P) dont le domaine réalisable F(P)={0≤xj≤2 et xj entier} peut être partitionné en trois problèmes (P1), (P2) et (P3) de même fonction objectif et ayant respectivement comme domaine réalisable: F(P1)={xj=0} , F(P2)={xj=1} et F(P3)={xj=2}. 14 Pr. Mohamed El Merouani 13/05/2015 8 Exemple • Le problème (P) dont le domaine réalisable F(P)={0≤xj≤4 et xj entier} peut être partitionné en deux problèmes (P1) et (P2) de même fonction objectif et ayant respectivement comme domaine réalisable: F(P1)={0≤xj≤2 et xj entier} et F(P2)={3≤xj≤4 et xj entier}. 15 Pr. Mohamed El Merouani Stratégie vague et globale de résolution • Essayer de solutionner (P) • Sans succès, alors partitionner (P) en deux ou plusieurs sous problèmes que l’on place dans une liste. • Sélectionner un problème dans la liste=problème candidat (PC). • Essayer de solutionner (PC): – Avec succès, alors sélectionner un autre problème dans la liste, – Sans succès, alors partitionner (PC) et placer ses descendants dans la liste. • Le processus est répété tant que la liste est non vide. 16 Pr. Mohamed El Merouani 13/05/2015 9 Remarque • Chaque fois qu’on réussit, on identifie un élément de F(P) et on retient la meilleure solution de (P) rencontrée jusqu’ici (Point candidat ou incumbent) 17 Pr. Mohamed El Merouani Relaxation • Le problème (P) est dit relaxé si certains contraintes sont relâchées, c’est-à-dire si certains contraintes ne sont pas prises en considération. • Le problème relaxé sera noté par (PR). Exemple: Min ctx Min ctx (P) Sujet à Ax≥b (PR) Sujet à Ax≥b x≥0 et entier x≥0 18 Pr. Mohamed El Merouani 13/05/2015 10 Relaxation: Propriétés 1. F(P) F(PR) 2. F(PR)=Ø => F(P)=Ø 3. V(PR)≤V(P) (pour un problème de minimisation) 4. Si une solution optimale de (PR) est dans F(P), alors c’est aussi une solution optimale de (P). 19 ⊆ Pr. Mohamed El Merouani Critères de cessation de fouille (Stérilisation ou Fathoming) • Notons par Zs la valeur de la fonction objectif au point candidat ou incumbent et considérons un problème candidat (PC) d’un problème d’optimisation. • Le (PC) est dit stérilisé si l’un des critères suivants est satisfait: 1. F(PCR)=Ø (=> oublier (PC)) 2. V(PCR)≥Zs (=> oublier (PC)) 3. Une solution optimale du (PCR) est réalisable pour (PC) (avec V(PCR)<Zs) (=> oublier (PC)) 20 Pr. Mohamed El Merouani 13/05/2015 11 Remarque • Si ces critères ne s’appliquent pas avec la solution optimale de (PCR), alors on peut: – Engendrer des descendants de (PC) ou – Sélectionner une autre relaxation plus « adéquate » pour essayer d’appliquer les critères de « Fathoming ». 21 Pr. Mohamed El Merouani Procédure générale • Étape1: la liste des candidats contient (P), Zs=+∞ • Étape 2: Terminer si la liste est vide: si au moins une solution réalisable de (P) a été rencontrée, alors ce point incumbent est une solution optimale de (P). Autrement, F(P)≠Ø. • Étape 3: Choisir un problème dans la liste qui devient (PC). Eliminer (PC) de la liste. • Étape 4: Identifier une relaxation (PCR) de (PC). 22 Pr. Mohamed El Merouani 13/05/2015 12 Procédure générale • Étape 5: Traiter (PCR) • Étape 6: Si F(PCR)=Ø, alors aller à l’étape 2. • Étape 7: Si V(PCR)≥Zs, alors aller à l’étape 2. • Étape 8: -Si la solution optimale de (PCR) est réalisé pour (PC), alors nous venons d’identifier une nouvelle solution de (P). -Si V(PC)=V(PCR)<Zs, alors poser Zs=V(PC), et cette solution constitue le nouvel « point incumbent ». Retourner à l’étape 2. 23 Pr. Mohamed El Merouani Procédure générale • Étape 9: Si on décide de poursuivre avec (PC), aller à l’étape 10. Autrement, aller à l’étape 11. • Étape 10: Modifier la relaxation de (PC) pour en obtenir une nouvelle qu’on note (PCR). Aller à l’étape 5. • Étape 11: Partitionner (PC) et placer les nouveaux sous-problèmes dans la liste. Aller à l’étape 2. 24 Pr. Mohamed El Merouani 13/05/2015 13 Bibliographie • Y. Benadada & A. El Hilali Alaoui :«Programmation Mathématique, de la modélisation à la résolution», Edition Kawtar Print, Rabat, 2012. Pr. Mohamed El Merouani 25 uploads/Geographie/ programmation-lineaire-en-nombres-entiers-premiere-partie-pdf.pdf