Remerciez-le!

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

RECHERCHE OPÉRATIONNELLE Dr. Tchalla Ayékotan Messan Joseph Enseignant-chercheu

RECHERCHE OPÉRATIONNELLE Dr. Tchalla Ayékotan Messan Joseph Enseignant-chercheur à l’Université de Lomé 2 TABLE DES MATIÈRES 1 Théorie des graphes 7 1.1 Graphe non orienté . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.1.1 Déﬁnitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.1.2 Représentation graphique d’un graphe non orienté . . . . . . . . . . . 8 1.1.3 Quelques types de Graphes . . . . . . . . . . . . . . . . . . . . . . . . 8 1.1.4 Graphe partiel et sous graphe . . . . . . . . . . . . . . . . . . . . . . 9 1.1.5 Degré d’un sommet, degré d’un graphe . . . . . . . . . . . . . . . . . 10 1.1.6 Chaîne, cycle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.1.7 Représentation non graphique d’un graphe non orienté . . . . . . . . 12 1.2 Coloration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.2.1 Stable d’un graphe . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.2.2 Coloration des sommets d’un graphe . . . . . . . . . . . . . . . . . . 13 1.2.3 Encadrement du nombre chromatique . . . . . . . . . . . . . . . . . . 14 1.3 Graphe orienté . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.3.1 Chemin-circuit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 1.3.2 Représentation non graphique de digraphe . . . . . . . . . . . . . . . 16 1.3.3 Détermination des plus courts chemins . . . . . . . . . . . . . . . . . 18 2 Ordonnancement 25 2.1 Méthode de résolution : méthode PERT . . . . . . . . . . . . . . . . . . . . 25 2.1.1 Modélisation d’un problème d’ordonnancement à l’aide d’un graphe PERT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 2.1.2 Détermination des dates au plus tôt . . . . . . . . . . . . . . . . . . . 28 2.1.3 Détermination des dates au plus tard . . . . . . . . . . . . . . . . . . 30 3 Flot dans les graphes 33 3.1 Déﬁnitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 3.2 Problème du ﬂot maximum . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 3.2.1 Algorithme de Ford et Fulkerson . . . . . . . . . . . . . . . . . . . . . 36 3 4 Programmation Linéaire (PL) ou Optimisattion Linéaire (OL) 43 4.1 Exemple de programme linéaire . . . . . . . . . . . . . . . . . . . . . . . . . 43 4.2 Forme générale d’un programme linéaire . . . . . . . . . . . . . . . . . . . . 44 4.3 Formes matricielles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 4.4 Forme canonique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 4.4.1 Forme standard des problèmes . . . . . . . . . . . . . . . . . . . 46 4.4.2 Réduction à la forme standard d’un problème de programma- tion linéaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 4.5 Quelques domaines d’intervention de la programmation linéaire . . . . . . . 47 4.5.1 Modélisation de quelques problème de PL . . . . . . . . . . . . . . . 47 4.6 Bases-Solution de base- Solution de base réalisable . . . . . . . . . . . . . . . 48 4.6.1 Déﬁnitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 4.6.2 Procédure pour la construction des solutions de base . . . . . 49 4.7 La méthode du Simplexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 4.7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 4.7.2 Conditions d’optimalité . . . . . . . . . . . . . . . . . . . . . . . . . . 58 4.7.3 Algorithme du simplexe . . . . . . . . . . . . . . . . . . . . . . . . . 63 4.7.4 Remarques sur la méthode du simplexe pour les problème dégénérés . 68 4.7.5 Sélection du pivot . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 4.8 Théorie de la dualité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 4.8.1 problème dual . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 4.8.2 théorémes fondamentaux de la dualité . . . . . . . . . . . . . . . . . 70 4.8.3 Relation entre le primal et le dual . . . . . . . . . . . . . . . . . . . . 70 4.8.4 Écarts complémentaires . . . . . . . . . . . . . . . . . . . . . . . . . 71 4 RECHERCHE OPÉRATIONNELLE : GÉNÉRALITÉS La recherche opérationnelle (RO) est l’ensemble des techniques et méthodes utilisées pour pourvoir résoudre les questions d’utilisation optimale des ressources dans les problèmes d’or- ganisation. C’est la discipline des mathématiques appliquées qui aide à de meilleurs prises décisions dans les domaines comme l’industrie, l’économie, la ﬁnance, le marketing et la pla- niﬁcation d’entreprise... La recherche opérationnelle est née pendant la seconde guerre mondiale des eﬀorts conju- gués d’éminents mathématiciens (dont von Neumann, Dantzig, Blackett) à qui il avait été demandé de fournir des techniques d’optimisation des ressources militaires. Le premier suc- cès de cette approche à été obtenu en 1940 par le Prix Nobel de physique Patrick Blackett qui résolut un problème d’implantation optimale de uploads/Science et Technologie/cours.pdf