Plan :
INTRODUCTION I. PRESENTATION DE LA RECHERCHE OPERATIONNELLE 7 II. DOMAINES D'APPLICATION 7 2.1) Les problèmes combinatoires 7 2.2) Les problèmes aléatoires 7 2.3) Les problèmes de concurrence 7 III. PROPRIETES DE LA R.O. INTERDISCIPLINAIRE 7 PROGRAMMATION LINEAIRE I. PROBLEMATIQUE DE LA PROGRAMMATION LINEAIRE 10 1.1) Introduction 10 1.2) Exemple 10 1.3) Forme canonique 11 1.4) Formulation générale 12 1.5) Interprétation géométrique 12 1.6) Forme standard 13 II. CONVEXITE 14 III. METHODE DU SIMPLEXE 14 3.1) Exemple avec deux variables 14 3.2) Méthode des tableaux 16 3.3) Méthode des 2 phases et méthode M 24 3.4) Paramétrisation des coeff. de la fn éco. 27 IV. DUALITE : 32 PROBLEMES DE TRANSPORT I. EXEMPLE DE L'USINE 37 1.1) Problème : répartition des expéditions 37 1.2) Modélisation du problème 38 1.3) Représentation graphique 39 1.4) Méthode plus rapide (des regrets) 40 1.5) Changement de base 40 1.6) Cas de dégénérescence 42 II. RECHERCHE D’UNE SOLUTION INITIALE 42 2.1) Règle du coin Nord-Ouest ("hasard") 42 2.2) Règle de Balas-Hammer : 43 LES GRAPHES I. DEFINITION – VOCABULAIRE 47 1.1) Graphe 47 1.2) Chemins 48 II. MATRICES ASSOCIEES A UN GRAPHE 49 2.1) Matrice latine 49 2.2) Matrices booléenne et arithmétique 50 III. CONNEXITE – FORTE CONNEXITE 51 3.1) Connexité 51 3.2) Forte connexité 51 3.3) Fermeture transitive 52 3.4) Recherche des classes fortement connexes, des circuits hamiltoniens 53 3.5) Méthode de Georges DEMOUCRON 53 CHEMIN DE VALEUR OPTIMALE I. ALGORITHME DE FORD 58 II. ALGORITHME DE FORD-FULKERSON 59 2.1) flot à travers un réseau 59 2.2) Procédure 60 2.3) Recherche d’un flot complet initial 61 2.4) Exercices 64 III. PROBLEME D’AFFECTATION 64 3.1) Exercices 66 ORDONNANCEMENT I. INTRODUCTION 69 II. METHODES D’ORDONNANCEMENT 70 2.1) Méthode MPM 70 2.2) Méthode PERT 72 2.3) Comparaison des deux méthodes 73 III. EXERCICES 74 PROCESSUS STOCHASTIQUES I. INTRODUCTION 77 1.1) Historique 77 1.2) Définition d'un Processus Stochastique 77 II. LES CHAINES DE MARKOV A ESPACE D'ETATS DISCRET 78 2.1) Probabilités et matrice de transition 78 2.2) Probabilités de transition en m étapes 78 III. GRAPHE DES TRANSITIONS – CLASSIFICATION DES CHAINES 79 3.1) Exemple sur les processus aléatoires 79 IV. DISTRIBUTION DES ETATS D'UNE CHAINE 80 V. ETUDE DES CHAINES REDUCTIBLES 80 VI. LES CHAINES DE MARKOV A TEMPS CONTINU 80 VII. COMPORTEMENT ASYMPTOTIQUE DES CHAINES 80 VIII. PROCESSUS DE NAISSANCE ET DE MORT 80 FIABILITE I. INTRODUCTION 83 II. GENERALITES - TERMINOLOGIE 83 2.1) Fonction de défaillance et fn de fiabilité 83 2.2) Taux d’avarie ou taux de défaillance 83 III. LOIS UTILISEES 86 3.1) Loi exponentielle 86 3.2) Loi de Weibull 86 IV. FIABILITE D’UN SYSTEME ET DE SES COMPOSANTS 87 4.1) Système à structure en série 87 4.2) Système à structure parallèle 87 4.3) Systèmes à structure mixte 88 V. EXERCICES 88 5.1) Exercice n° 1 88 5.2) Exercice n° 2 89 5.3) Exercice n° 3 89