Tiêu đề °COURS Recherche opérationnelle SMI5 FSR RABAT 16 17.pdf ✅

Pr. M. ABBAD & Pr. K. RAHHALI RECHERCHE OPÉRATIONNELLE Sciences Mathématiques et Informatique Semestre 5 2016-2017 Faculté des Sciences Rabat
FACULTÉ DES SCIENCES – RABAT www.fsr.ac.ma Année universitaire : 2016 - 2017
Table des matières 1 Programmation Linéaire (PL) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.1 Introduction 5 1.2 Fondement de la Programmation Linéaire 9 1.3 Méthode de Simplexe 12 1.3.1 Algorithme de simplexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 1.4 La Phase I de la Méthode de Simplexe 15 1.5 Dualité 18 1.6 Étude de sensibilité 20 1.6.1 Modification du second membre des contraintes . . . . . . . . . . . . . . . . 21 1.6.2 Modification des coefficients de la fonction objectif . . . . . . . . . . . . . . 22 1.7 Exercices 23 2 PL en Nombres Entiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 2.1 Introduction 27 2.2 Méthodes de coupe 28 2.2.1 Principe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 2.2.2 Méthode des formes entières (coupes de Gomory) . . . . . . . . . . . . . . . 29 2.2.3 Algorithme primal-dual de Gomory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 2.3 Méthode de recherche arborescentes par séparation et évalua- tion 34 2.3.1 Principe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 2.3.2 Méthode de séparation et évaluation (Branch and Bound) . . . . . . . . 34 2.3.3 Algorithme de séparation et évaluation . . . . . . . . . . . . . . . . . . . . . . . . . 38
2.4 Conclusion 43 2.5 Exercices 43 3 Chemins Optimaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 3.1 Introduction à la théorie des graphes 45 3.2 ALGORITHME DE MOORE-DIJKSTRA (1959) 46 3.3 ALGORITHME DE BELLMAN-KALABA 48 3.4 ALGORITHME DE FLOYD (1962) 50 3.5 Applications 53 3.6 Exercices 56 4 Problèmes des Flots . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 4.1 Introduction 59 4.2 Flot maximal Coupe minimale 59 4.3 Algorithme de FORD-FULKERSON (1956) 61 4.4 Algorithme d’obtention d’un flot de valeur v0 donnée 65 4.5 Algorithme d’obtention d’un flot de valeur maximale et de coût minimum : Algorithme de KLEIN (1967) 68 4.6 Exercices 72