PRÉLIMINAIRES

I. Épistémologie et Enjeux Scientifiques du Domaine

Née des contraintes logistiques de la Seconde Guerre mondiale, la Recherche Opérationnelle (RO) formalise l’art de la décision optimale sous contraintes. Son ontologie repose sur la traduction de problèmes managériaux complexes en modèles mathématiques quantifiables, un processus qui la place au carrefour des mathématiques appliquées, de l’informatique et des sciences de gestion. L’enjeu scientifique majeur demeure la lutte contre l’explosion combinatoire. Pour l’ingénieur informaticien, maîtriser la RO signifie acquérir le pouvoir de transformer des données brutes en stratégies actionnables, arbitrant entre coût, temps et performance avec une rigueur algorithmique implacable.

II. Cartographie des Compétences et Transversalité

Cette unité d’enseignement forge un triptyque de compétences indissociables. La formulation mathématique constitue le socle, transformant le chaos industriel en équations linéaires. L’implémentation des algorithmes de graphes ouvre la voie à l’optimisation des flux physiques et informationnels, une compétence cruciale en logistique et télécommunications. Enfin, la maîtrise du simplexe et de ses dérivés arme l’ingénieur d’un outil décisionnel puissant pour l’allocation de ressources rares. Ces savoir-faire irriguent directement l’ingénierie logicielle, l’intelligence artificielle (planification) et la science des données, créant des profils d’ingénieurs à très haute valeur ajoutée.

III. Alignement Stratégique avec les Réalités Opérationnelles

Face aux défis d’infrastructures et de supply chain du continent africain, l’ingénieur en optimisation devient un acteur stratégique de premier plan. Les métiers visés – consultant en RO, concepteur d’algorithmes décisionnels – répondent à des besoins critiques : optimiser les tournées de livraison dans des réseaux routiers imprévisibles, planifier l’allocation d’énergie de sources intermittentes, ou encore maximiser le rendement des chaînes de production locales. Ce cours ancre délibérément chaque concept dans ce contexte, assurant que la compétence acquise soit immédiatement monnayable et socialement pertinente pour catalyser le développement économique local.

Chapitre I. Fondations Mathématiques et Formalisation des Problèmes

I.1 L’art de la modélisation : de l’ambiguïté managériale à la rigueur mathématique

Au cœur de la Recherche Opérationnelle se trouve l’acte de traduction. Il s’agit de convertir un problème de gestion, souvent exprimé en langage naturel et pétri d’ambiguïtés, en un système formel non équivoque. Cette section dissèque ce processus cognitif et méthodologique. L’étudiant apprendra à identifier les variables de décision, à quantifier la fonction-objectif qui mesure la performance, et à transcrire les limitations opérationnelles en un ensemble de contraintes mathématiques. La maîtrise de cette étape initiale conditionne la validité de toute la démarche d’optimisation subséquente.

I.2 Le langage canonique : variables, contraintes et fonction-objectif

Sous l’angle de la précision, tout problème d’optimisation s’articule autour d’une syntaxe stricte. Ce sous-chapitre outille l’étudiant avec ce langage universel. Il explorera la typologie des variables (continues, entières, binaires), la nature des contraintes (égalité, inégalité) et la structure des fonctions-objectifs (linéaires, non-linéaires). Des exemples concrets, allant du problème du sac à dos au régime alimentaire, sont utilisés pour illustrer comment ces trois composantes s’assemblent pour former un modèle mathématique cohérent, prêt à être traité par un algorithme.

I.3 Les frontières de la modélisation : linéarité, certitude et rationalité

La puissance de la modélisation mathématique repose sur des hypothèses simplificatrices dont il faut connaître les limites. Ce segment opère une critique technique de ces postulats. L’hypothèse de linéarité, par exemple, ignore les économies d’échelle ; celle de la certitude occulte la nature stochastique de nombreux paramètres (demande client, temps de transport). En analysant ces angles morts, l’étudiant développe un recul critique, essentiel pour évaluer la robustesse d’un modèle et comprendre quand il risque de produire des recommandations déconnectées de la réalité complexe du terrain.

I.4 Application au contexte local : formaliser l’optimisation d’un réseau de distribution de produits de première nécessité

Face aux défis logistiques de l’approvisionnement des zones enclavées en RDC, la formalisation est la première étape vers l’efficience. Ce cas pratique guide l’étudiant dans la modélisation d’un problème concret : minimiser les coûts de transport pour un distributeur de médicaments depuis un entrepôt central à Kinshasa vers des centres de santé périphériques. Il devra définir les variables (quantités par route), la fonction-objectif (coût total du carburant et des péages) et les contraintes (capacité des véhicules, demande de chaque centre, état des routes).

Chapitre II. Programmation Linéaire : Modélisation et Formulation Industrielle

II.1 Géométrie de l’optimisation : polyèdres convexes et solutions admissibles

Un programme linéaire dessine une réalité géométrique fascinante. L’ensemble des solutions respectant les contraintes forme une région appelée polyèdre convexe, et la solution optimale se trouve nécessairement à l’un de ses sommets. Cette section explore cette intuition fondamentale. Comprendre cette correspondance entre l’algèbre des inéquations et la géométrie des formes permet de visualiser le processus d’optimisation. L’étudiant saisira pourquoi la recherche d’un optimum peut se réduire à une exploration intelligente des “coins” de l’espace des solutions possibles, un concept clé pour l’algorithme du simplexe.

II.2 Mécanismes de formulation : du problème de production au modèle standard

Pour qu’un solveur puisse traiter un problème, celui-ci doit être mis sous une forme canonique. Ce sous-chapitre détaille les techniques de transformation : introduction de variables d’écart pour convertir les inégalités en égalités, et gestion des variables non restreintes. À travers l’exemple classique d’une usine fabriquant plusieurs produits avec des ressources partagées (heures-machine, matières premières), l’étudiant apprendra à construire pas à pas la matrice des contraintes et le vecteur des coûts. Cette compétence technique est le passage obligé entre la modélisation conceptuelle et l’implémentation numérique.

II.3 Au-delà de la ligne droite : la critique de l’hypothèse de proportionnalité

L’hypothèse de proportionnalité de la programmation linéaire, stipulant qu’un doublement des ressources entraîne un doublement de la production, est une simplification puissante mais souvent irréaliste. Ce segment analyse ses failles. Dans de nombreux processus industriels, des phénomènes de rendement croissant ou décroissant invalident cette linéarité. Cette analyse critique prépare l’étudiant à identifier les situations où la programmation linéaire est inappropriée et à anticiper le besoin de modèles plus complexes (non-linéaires ou entiers), évitant ainsi des décisions stratégiques basées sur des prémisses erronées.

II.4 Mise en situation : allocation optimale des terres pour une coopérative agricole au Kivu

Considérant une coopérative agricole disposant de parcelles aux rendements variés et d’un accès limité à l’eau et aux engrais, l’enjeu est de maximiser le revenu total. Ce cas d’étude applique la programmation linéaire pour déterminer l’assolement optimal entre plusieurs cultures (café, manioc, haricots). L’étudiant formulera le problème en définissant les surfaces allouées à chaque culture comme variables de décision, le revenu attendu comme fonction-objectif, et les contraintes liées à la disponibilité des terres, de l’eau, de la main-d’œuvre et des intrants.

Chapitre III. Algorithmique du Simplexe et Analyse de Sensibilité

III.1 L’innovation de Dantzig : le principe de l’itération pivotale

En 1947, George Dantzig a révolutionné la prise de décision en concevant l’algorithme du simplexe. Son génie fut de proposer une méthode systématique pour naviguer sur les sommets du polyèdre des solutions admissibles, en améliorant la fonction-objectif à chaque étape jusqu’à atteindre l’optimum. Ce chapitre expose la logique profonde de cette approche itérative. L’étudiant comprendra le concept de base réalisable, de variable entrante et sortante, qui constituent le moteur de l’un des algorithmes les plus influents du XXe siècle.

III.2 Le tableau du simplexe : une mécanique de résolution systématique

Le tableau du simplexe est l’outil opératoire qui implémente l’algorithme de Dantzig. Cette section en détaille la construction et la manipulation, pas à pas. L’étudiant apprendra à initialiser le tableau, à identifier la colonne pivot (variable entrante) en utilisant les coûts réduits, à déterminer la ligne pivot (variable sortante) via le test du ratio minimum, et à effectuer les opérations de pivotage pour passer à une nouvelle solution de base. Cette maîtrise technique permet de résoudre manuellement des problèmes de petite taille et de comprendre le fonctionnement interne des solveurs.

III.3 Pathologies algorithmiques : dégénérescence, cycles et complexité

Malgré son efficacité pratique stupéfiante, l’algorithme du simplexe n’est pas sans failles théoriques. La dégénérescence peut entraîner des itérations sans amélioration de la solution, voire des cycles infinis (un phénomène rare mais possible). De plus, des exemples comme le cube de Klee-Minty montrent que sa complexité peut être exponentielle dans le pire des cas. Ce segment analyse ces cas pathologiques, non pour discréditer l’algorithme, mais pour forger une compréhension mature de ses performances et introduire les règles (comme celle de Bland) qui garantissent sa terminaison.

III.4 Analyse post-optimale : évaluer la robustesse d’un plan de production à Lubumbashi

Une fois la solution optimale trouvée pour une usine minière, une question cruciale se pose : que se passe-t-il si le coût d’un réactif chimique augmente ou si une machine tombe en panne ? Ce cas pratique utilise l’analyse de sensibilité et les prix duaux (shadow prices) issus du tableau final du simplexe pour répondre. L’étudiant apprendra à calculer les plages de variation des coûts et des ressources pour lesquelles la solution optimale reste inchangée. Il fournira ainsi des recommandations managériales robustes face à l’incertitude des marchés et aux aléas opérationnels.

Chapitre IV. Théorie des Graphes pour la Logistique et l’Ordonnancement

IV.1 Des ponts de Königsberg aux réseaux modernes : la puissance de l’abstraction par les graphes

L’intuition d’Euler face au problème des sept ponts de Königsberg a fondé une discipline entière. La théorie des graphes modélise des systèmes complexes en un ensemble de sommets (entités) et d’arêtes (relations). Cette section établit ce vocabulaire fondamental : graphes orientés et non orientés, pondérés, chemins, cycles, connexité. L’étudiant saisira comment des problèmes aussi divers qu’un réseau social, une carte routière ou les dépendances entre tâches d’un projet peuvent être unifiés et analysés sous cette même structure mathématique élégante et puissante.

IV.2 L’arsenal algorithmique : Dijkstra, Kruskal et Ford-Fulkerson

Pour naviguer et optimiser ces structures, un arsenal d’algorithmes classiques est indispensable. Ce sous-chapitre se concentre sur l’implémentation et la complexité des algorithmes fondamentaux. L’algorithme de Dijkstra pour le plus court chemin, celui de Kruskal ou Prim pour l’arbre couvrant de poids minimum, et l’algorithme de Ford-Fulkerson pour le flot maximum sont disséqués. L’étudiant devra être capable de les dérouler sur des exemples et de comprendre leur domaine d’application spécifique, de la conception de réseaux de fibre optique à la gestion de pipelines.

IV.3 Les limites du statique : quand les graphes doivent s’adapter au temps réel

Les algorithmes classiques supposent souvent un graphe statique, dont les poids et la topologie sont fixes. Or, la réalité opérationnelle est dynamique : le trafic routier évolue, des liens de communication tombent, la demande fluctue. Cette analyse critique explore les limites de l’approche statique et introduit la notion de graphes dynamiques et temporels. Elle sensibilise l’étudiant aux défis computationnels que pose la nécessité de recalculer des chemins optimaux en temps réel, ouvrant la voie vers des algorithmes plus adaptatifs et résilients.

IV.4 Optimisation d’un réseau de transport fluvial sur le fleuve Congo

Le fleuve Congo est une artère vitale mais complexe pour le transport de marchandises. Ce cas d’étude charge l’étudiant de modéliser le réseau fluvial comme un graphe pondéré où les villes portuaires sont les sommets et les tronçons navigables les arêtes. En utilisant l’algorithme de Dijkstra, il calculera les routes les plus rapides pour des barges. Avec Ford-Fulkerson, il déterminera la capacité maximale de transport de marchandises entre Matadi et Kisangani, en tenant compte des capacités limitées de certains biefs ou ports intermédiaires.

Chapitre V. Heuristiques et Métaheuristiques pour l’Optimisation Complexe

V.1 Le mur de la complexité : l’émergence des problèmes NP-difficiles

Pour de nombreux problèmes d’optimisation industrielle, comme le célèbre problème du voyageur de commerce, trouver la solution optimale exacte devient computationnellement infaisable dès que la taille du problème augmente. Cette section introduit la théorie de la complexité (P vs NP) pour expliquer pourquoi ces problèmes sont si “durs”. L’étudiant comprendra la nécessité d’abandonner la quête de l’optimalité garantie pour adopter une nouvelle philosophie : celle des heuristiques, qui visent à trouver de très bonnes solutions, rapidement, sans pouvoir prouver qu’elles sont les meilleures.

V.2 Au-delà de la recherche exhaustive : recuit simulé, algorithmes génétiques et recherche tabou

Face à l’explosion combinatoire, les métaheuristiques proposent des stratégies de recherche intelligentes inspirées par la nature ou la physique. Ce sous-chapitre présente les mécanismes de trois approches majeures : le recuit simulé, qui explore l’espace des solutions en s’autorisant à dégrader temporairement la solution ; les algorithmes génétiques, qui miment l’évolution darwinienne ; et la recherche tabou, qui évite de retomber dans des minima locaux déjà visités. L’étudiant en saisira les principes pour pouvoir choisir la méthode la plus adaptée à un problème donné.

V.3 Le dilemme du praticien : paramétrage fin et absence de garantie d’optimalité

L’un des débats les plus vifs en RO concerne la validation des solutions heuristiques. Comment faire confiance à un résultat qu’on ne peut prouver optimal ? De plus, la performance de ces algorithmes dépend crucialement du réglage de nombreux paramètres (taux de refroidissement, taille de la population, etc.), un processus qui s’apparente parfois à un “art sombre”. Cette section aborde ces questions pragmatiques, en fournissant des méthodes pour comparer les heuristiques entre elles et pour évaluer la qualité d’une solution par rapport à des bornes théoriques.

IV.4 Application frugale : ordonnancement des délestages électriques à Kinshasa

Dans un contexte de production électrique insuffisante pour couvrir la demande, la gestion des coupures tournantes (délestage) est un problème d’ordonnancement complexe et socialement sensible. Ce cas d’étude final charge l’étudiant de développer une heuristique pour planifier les délestages. L’objectif est de minimiser l’impact économique global tout en respectant des contraintes d’équité entre les quartiers et en assurant l’alimentation continue des infrastructures critiques (hôpitaux, pompes à eau). C’est une application directe de l’optimisation sous forte contrainte pour l’amélioration du service public.

ANNEXES

A. Guide de Démarrage Rapide : PuLP pour le Prototypage en Python

PuLP est une bibliothèque Python open-source qui permet de formuler des problèmes de programmation linéaire et en nombres entiers de manière intuitive et lisible. Cette annexe fournit un guide pratique pour l’ingénieur en optimisation. Elle montre comment installer la bibliothèque, définir des variables, des contraintes et une fonction-objectif en utilisant une syntaxe proche de la notation mathématique, puis lancer un solveur externe (comme CBC, inclus par défaut) pour obtenir la solution. C’est l’outil idéal pour le prototypage rapide et la validation de modèles avant un déploiement à plus grande échelle.

B. Prise en Main du Solveur GLPK (GNU Linear Programming Kit)

Pour le concepteur d’algorithmes décisionnels qui a besoin de performance et de portabilité, le GNU Linear Programming Kit (GLPK) est une référence. Écrit en C et utilisable via une interface en ligne de commande ou des API dans divers langages, il offre une solution robuste et gratuite pour des problèmes de grande taille. Cette annexe se concentre sur l’utilisation de son langage de modélisation, GNU MathProg, qui permet de séparer clairement la description du modèle mathématique des données du problème, une pratique essentielle pour la maintenance et la réutilisation des modèles en environnement de production.

C. Visualisation et Analyse de Graphes avec NetworkX

Un consultant en recherche opérationnelle doit être capable de communiquer ses résultats de manière percutante. NetworkX, une bibliothèque Python, est l’outil parfait pour l’analyse et la visualisation de réseaux. Cette annexe démontre comment créer, manipuler et étudier la structure de graphes complexes. Elle guide l’utilisateur pour implémenter les algorithmes du Chapitre IV (Dijkstra, etc.) en quelques lignes de code, mais surtout pour générer des visualisations graphiques qui rendent les solutions (plus court chemin, flux maximal) immédiatement compréhensibles pour un public non-technique, facilitant ainsi l’aide à la décision.

Lire aussi :

Cours de Territoire : dynamique spatiale, pratique sociale et durabilité, licence-3, TER1354

Cours de Système d'information géographique, master-1, SIG2111

Cours de Sociologie Critique du Développement, master-1, SCD2121

Cours de Géodésie et Physique du Globe, master-1, GPG2121

Cours de Gestion des projets, master-2, GEP2231

Cours de Théorie et Statistiques Inverses Géophysiques, master-2, TSI2231