Précis de recherche opérationnelle

Description

Page de titre Préface de P. GUERIN Avertissement Chap. I. INTRODUCTION A LA RECHERCHE OPÉRATIONNELLE Tentative de définition Les domaines d'application Difficultés et dangers de l'optimisation Objectifs et critères. La définition des objectifs et la détermination du critère d'optimisation sont du ressort de l'entrepreneur La R.O. est plus un art qu'une science Rentabilité de la R.O R.O. et gestion But et plan de l'ouvrage PREMIERE PARTIE - LA RECHERCHE OPÉRATIONNELLE, FIL D'ARIANE DANS LES PROBLÈMES COMBINATOIRES DISCRETS Chap. II. STRUCTURES ORDONNÉES. APPLICATIONS DES TREILLIS ET DE L'ALGÈBRE DE BOOLE EN RECHERCHE OPÉRATIONNELLE A. Notions sur les structures ordonnées Relations. Relations binaires. Propriétés Préordre. Équivalence. Ordre Éléments particuliers d'un ensemble ordonné Treillis Exemple d'application d'une structure de treillis à la résolution d'un problème B. Représentation ensembliste des algèbres de Boole. Application à la logique élémentaire 1. Principes de la logique aristotélicienne 2. Expression du principe de contradiction 3. Formules de A. de Morgan. Principe du tiers exclu 4. Commutativité. Idempotence. Eléments neutres 5. Distributivité 6. Vers une axiomatique 7. Implication. Inclusion 8. Formes canoniques C. L'algèbre de Boole binaire Fonction caractéristique. Opérations binaires Tableau de Boole Minimisation d'une fonction booléienne D. Applications élémentaires 1. Etude d'un itinéraire 2. Choix d'investissements 3. Fonctionnelle à optimiser sous contraintes a. Variables booléiennes b. Variables positives entières quelconques Chap. III. ÉLÉMENTS DE LA THÉORIE DES GRAPHES ET DE LA PROGRAMMATION DYNAMIQUE CERTAINE. APPLICATIONS A LA RECHERCHE OPERATIONNELLE (CHEMINS, ORDONNANCEMENTS, FLOTS, AFFECTATION, TRANSPORT OPTIMAUX. RECHERCHE ARBORESCENTE) A. Éléments de la théorie des graphes Al. Qu'est-ce qu'un graphe ? A2. Vocabulaire de la théorie des graphes A3. Chemins de longueur k. Fermeture transitive A4. Forte connexité A5. Recherche des chemins et circuits hamiltoniens A6. Utilité du concept de graphe en recherche opérationnelle B. Notions de programmation dynamique certaine C. Applications aux chemins, ordonnancements, flots, affectation optimaux C1. Problèmes de chemins de valeur optimale a. Algorithme de Ford b. Algorithme de Dantzig c. Méthode matricielle C2. Problèmes d'ordonnancement C3. Problèmes de flot maximal Flot à travers un réseau et théorème de Ford-Fulkerson Recherche d'un flot complet C4. Problèmes d'affectation D. Notions d'arbre et d'arborescence Dl. Arbre. Définition et propriétés élémentaires D2. Quasi-forte connexité. Arborescence E. Applications aux arbres optimaux, transport à coût minimal et recherche arborescente El. Problème de l'arbre de valeur minimale E2. Le problème de transport Considérations préliminaires Résolution pratique du problème de transport Première phase Deuxième phase E3. Problème du voyageur de commerce. Recherche arborescente DEUXIÈME PARTIE - LA RECHERCHE OPÉRATIONNELLE CONTRE LE HASARD Chap. IV. NOTIONS SUR LES PROCESSUS ALÉATOIRES ET LA PROGRAMMATION DYNAMIQUE STOCHASTIQUE A. Processus aléatoires Al. Introduction aux problèmes stochastiques A2. Notion de processus stochastique A3. Chaîne de Markov à espace d'état discret A4. Processus de Markov homogène à espace d'état discret A5. Processus de naissance. Processus de Poisson. Processus de mort Processus de naissance Processus de Poisson Loi exponentielle Processus de mort A6. Processus de naissance et de mort B. Notion de programmation dynamique stochastique Chap. V. USURE ET RENOUVELLEMENT DES ÉQUIPEMENTS 1. Données discrètes. Courbe de survie expérimentale 2. Loi de survie. Forme analytique 3. Probabilité de consommation. Taux d'approvisionnement 4. Calcul des approvisionnements à réaliser 5. Un autre compromis : l'entretien préventif 6. Stratégie de remplacement (exemple) Chap. VI. LES PHÉNOMÈNES D'ATTENTE 1. Généralités sur les phénomènes d'attente 2. Loi des arrivées. Loi des services 3. File à une station. Système ouvert 4. File à S stations 5. Application numérique 6. Cas des systèmes fermés 7. Probabilité de dépasser une certaine attente Chap. VII. VERS UNE GESTION SCIENTIFIQUE DES STOCKS 1. Généralités sur les problèmes de stocks 2. Le "modèle" de Wilson 3. Critique des modèles certains 4. Modèles pas-à-pas 5. Stock d'alerte 6. Stock de sécurité 7. Exemple de calcul analytique 8. Règles concernant certaines demandes importantes Chap.VIII.MÉTHODES DE SIMULATION A. CARACTÈRES GÉNÉRAUX DES SIMULATIONS B. SIMULATIONS CERTAINES C. SIMULATIONS STOCHASTIQUES D. NOMBRES AU HASARD E. SIMULATION D'UNE GESTION DE STOCKS TROISIÈME PARTIE - LA RECHERCHE OPÉRATIONNELLE DANS LES PROBLÈMES COMBINATOIRES CONTINUS Chap. IX. LA PROGRAMMATION LINÉAIRE Généralités A. Exemple de programme linéaire 1. Problème de maximisation 2. Première forme algébrique 3. Signification géométrique 4. Difficultés de généralisation B. Introduction à l'algorithme du simplexe 1. Problème de maximisation 2. Règle pratique (maximisation) C. Dualité D. Critiques des résultats. Paramétrisation 1. Critique de la programmation linéaire 2. Paramétrage des coefficients de la fonction économique 3. Paramétrage du second membre E. Problèmes en entiers. Méthode des troncatures F. Compléments théoriques 1. Hyperplans. Demi-espaces. Cônes convexes,Cônes polyédriques convexes 2. Lemme de Minkowski-Farkas 3. Cône dual. Théorème de Farkas 4. Définition équivalentes d'un cône polyédrique convexe 5. Théorème de Weyl 6. Tronçons. Enveloppes convexes. Polyèdres convexes 7. Théorème de Motzkin G. Dégénérescences 1. Dégénérescence de première espèce 2. Dégénérescence de deuxième espèce QUATRIÈME PARTIE - LA RECHERCHE OPÉRATIONNELLE ET LES PROBLÈMES DE CONCURRENCE Çhap. X. INTRODUCTION A LA THÉORIE DES JEUX - NOTIONS SUR LES JEUX D'ENTREPRISES A. Éléments de la théorie des jeux à deux personnes A1. Jeu à deux personnes et à point-selle A2. Notion de stratégies mixtes A3. Exemple d'application économique. Dominance. Réduction d'un jeu B. Notions sur les jeux d'entreprises B1. Généralités B2. Mécanisme comptable dans un jeu d'entreprises B3. Jeu des comptes B4. Classification, but et résultats des jeux d'entreprises B5. Modèles d'entreprises CINQUIÈME PARTIE - EXERCICES ET PROBLÈMES Exercices sur le chapitre II. Applications des treillis et de l'algèbre de Boole Exercices sur le chapitre III. Applications des graphes et de la programmation dynamique certaine Exercices Sur le chapitre IV. Processus aléatoires et programmation dynamique stochastique Exercices sur le chapitre V.Usure et renouvellement des équipements Exercices sur le chapitre VI. Les phénomènes d'attente Exercices sur le chapitre VII. Problèmes de stocks Exercices sur le chapitre VIII. Simulations Exercices sur le chapitre IX. Programmes linéaires Exercices sur le chapitre X. Théorie des jeux SIXIÈME PARTIE - EXEMPLES DE PROGRAMMES Avertissement I. Phénomènes d'attente II. Programme linéaire P.F.I III. Gestion de stock. Mise en oeuvre d'une simulation IV. Théorie des graphes Méthode de description d'un graphe en machine Chemins hamiltoniens Programme de transformation de graphe Algorithme de Ford Recherche du flot maximal et programme d'affectation V. Exemples divers Tracé des courbes de survie Politique de maintenance Programme de transport ANNEXES Extrait d'une table de nombres au hasard Valeurs de la fonction de répartition normale Valeurs de P_m (répartition de Poisson) Table de la distribution de χ² (Pearson) Table de la distribution de t (Student) BIBLIOGRAPHIE SOMMAIRE (de langue française)