Recherche opérationnelle pour les services publics

Recherche opérationnelle pour les services publics

INTRODUCTION

Objectif :

• Initiation aux Raisonnements, Techniques et Outils de la Recherche Opérationnelle

Introduction Générale :

Préambule :

• Qst° : Que vient faire la recherche opérationnelle dans le cadre des Service Publics ?

• Théorique : Service Publics = vocation de servir « Intérêt général »

• Produit par entité supérieure :

• Consommation « collective » => pr ts
• Consommation « gratuite » => accès « sans payer »

• Ds la réalité :

• Très nombreux
• Domaines des compétences variés
• Hiérarchisées institutionnellement

• Historique :

• Création durant l’après-guerre
• Gestion « sans trop se poser de qst° »
• Faible qlté de servie
• Faible productivité
• Imposition qui s’alourdit
• Coût de fonctionnement croissant des équipements

• Gestion « laxiste » remise en qst° => 2 facteurs :

• Crise des finances publiques :

• Cumul des déficits publics
• Seuil critique atteint de la Dette publique
• L’impact des Crises Eco sur l’Endettement des Collectivités Locales

• Emergence de « nvx Courants de Pensée » :

• En Sciences Eco : émergence de l’Eco Publique et Eco Publique Locale + surtout « radicaux » : Ecole du Public Choice, Libertariens …
• En Science de Gestion : émergence – plus récente – du « New Public Management »

• « Courants de pensée » = niveau très théorique => pas très concret sur le terrain
• Recherche opérationnelle intéressant car :

• Permet optimisation sur production, distribution, qlté du service public auprès des citoyens
• Réductions des coûts de production, d’organisation, de distribution … du service public

Recherche opérationnelle :

• Recherche opérationnelle = Discipline Académique de nature Scientifique => très particulière car récente, technique, méconnue et orientée vers l’Appliqué

• Déf = Discipline scientifique

• Récente (moins d’1 siècle d’existence)
• Qui appartient au domaine des Mathématiques => domaine de « l’Analyse »
• « Discipline des méthodes scientifiques utilisables pr élaborer de meilleures décisions. Elle permet de rationaliser, de simuler et d’optimiser l’architecture et le fonctionnement des systèmes de production ou d’organisation » (Association ROADEF- 2024)
• 2 particularités :

• Discipline scientifique « hybride » => pas exclusivement mathématiques

• Mathématique pr formalisation et technique pr résolution
• Informatique pr retranscrire modélisation et résolution ds un langage permettent à la « machine » de traiter le pb

• Discipline scientifique « Appliquée » => conçue uniquement pr le concret

• Centralisation de la dimension « appliquée » ds la démarche scientifique
• Finalité première de la RO est avt tt de résoudre de pbs concrets de la réalité

• Origine :

• Seconde Guerre Mondiale => domaine Militaire

• Royaume-Uni : après défaite en Juin 1940
• Etats-Unis après attaque sur Pearl Harbor en 1942

• Prise de décision de la créat° de la 1ère équipe de RO => 2 types d’acteurs :

• Initiateur Politique : Winston Churchill
• Instigateurs (« lobbyistes ») => proviennent du domaine Universitaire et de la Recherche ou domaine Militaire
• 1ère équipe RO :

• Dépendant du Ministère de la Guerre
• Dirigée par Sir Patrick Blackett (Prix Nobel de Sciences en 1948)
• + vingtaines de scientifiques venant d’horizons divers 
• => « La clique Blackett »
• Utilisé pour perspective défensive entre 1940 et 1942 et offensive de 1943 à 1495
• Ex missions :

• Implantations de radars sur les Côtes Britanniques => Positionnement « optimal » de Radars anti-aériens pour contrer raids allemands
• Planification de Convois Maritimes => Dimensionnement et itinéraire « à moindre risque » de Convois Maritimes pour éviter les Sous-Marins Allemands

• Côté USA :

• Domaine Militaire
• Même acteurs de la prise de décision :

• Initiateur politique : F.D. Roosevelt
• Instigateurs :

• Domaines universitaires : président université
• Militaire : surtout Aviation
• Secteur privé : Président Bell Laboratories
• Plusieurs équipes de RO engagées sur 2 fronts : Pacifique et Europe

• Scientifiques de Haut Niveau issus des Sciences « Dures »

• J. Von Neumann
• G. Dantzig
• J. Neyman
• A. Tucker

• Missions centrées sur l’aviation militaire :

• Stratégie du « Carpet Bombing »
• Planification de Débarquement Amphibies

• Après la guerre :

• Certains services de RO maintenues au sein de différents Corps d’Armée
• Revente des savoir-faire vers l’enseignement universitaire (grds universités US) et ds le secteur Privé (Industrie et transports)

• Méthodologie en RO

• Démarche => « Chaine » analytique :

• Pb réel => Réflexion => Formulation (littéraire) => Formalisation => Résolution => Simulation => Interprétation

• Paradigmes :

• 2 critères de segmentation : technique employée ou type de pb traité

• « Technique Employée » => 3 grds paradigmes :

• Optimisation : minimiser un ct ou maximiser un bénéfice
• Aléas : Introduction de phénomènes aléatoires ds pb traité
• Duel => Théorie des jeux

• « Type de Pb » traité => plsrs « Familles de Pbs » :

• Pbs d’Affectation : affecter des ouvriers sur des postes de façon à maximiser la productivité
• Pbs de localisation : Implanter un équipement de façon à minimiser le temps de déplacement des usagers
• Pbs d’ordonnancement : minimiser la durée de réalisation d’un projet en ordonnant rationnellement les tâches qui le composent

Optimisation appliquée

• Déf et Cadrage

• Au sens d’Optimisation Mathématique

• Relève du domaine de « l’Analyse » => 1 des grds domaines des mathématiques (nbrs transversalités en pratique)
• Recherche d’un Extrémum (Min ou Max) sur une fonction
• Matérialisé par des « contraintes »
• Solution correspondante pouvant (ou ne pouvant pas) être limitée à un ss-ensemble donné

• Grds familles

• Croissance exponentielle
• 4 gds familles :

• Optimisation Continue/ Optimisation Discrète (Combinatoire)
• Optimisation Linéaire/ Optimisation Non Linéaire
• Optimisation Déterministe/ Optimisation Stochastique
• Optimisation Mono-Objectif/ Optimisation Multi-Objectifs 

• => « Programmation Linéaire » = « Optimisation Linéaire »

FORMALISATION

• Formaliser = traduire un pb réel concret – énoncé de façon littéraire- sous orme d’un Programme Mathématique
• Vocabulaire employé :

• Pgrms à traiter tjrs sous forme algébrique 
• L’Opérateur d’optimisation : soit Max ou Min selon que l’on désire max ou min le prgrm
• La Fonction-Objectif (« Fct° Eco ») : elle correspond à l’expression du prgm :

• xj pour j = 1,…n : les Variables Décisionnelles du Prgrm. C’est-à-dire le Vecteur de solutions que l’on recherche par la procédure d’Optimisation
• cj pour j= 1,….n : Les Coefficients de la Fonction-Objectif

• Les Contraintes correspondent à la partie du Prgrm à optimiser : peuvent être des inégalités ou des égalités mais tjrs sous forme linéaire

• La partie Gauche : nommée Matrice des Premiers Membres et définie sous la forme de A(m,n)
• La partie Droite : nommée Vecteur des Second Membres, définie comme b(m,1)
• La dernière « catégorie » de contraintes est très particulière. Elle correspond à la partie x appartient à R du Prgm. Ce st les « Contraintes de Forme » des Variables Décisionnelles, qui ont une très forte influence sur la Résolution du Programme

• Procédure :

• Cas à traiter

• Usine produit 2 type de ciment C1 (50€/tonne) et C2 (70€/tonne)
• Pr production :

• 1 tonne C1 = 40 min de four + 20 min de broyage
• 1 tonne C2 = 30 min de four et 30 min de broyage

• Sur 1 journée :

• Limite utilisation four = 6h (360min)
• Limite utilisation broyage = 8h (480min)

• Qst° : quelle qté doit-on fabriquer pr Max le profit ?

• 1ère étape :

• On identifie les Entité (ens elmts de de même nature) => puis leur cardinalité (nbr de chaque entité) => création indexation
• Application :

• Entité 1 : Ciments, de cardinalité n=2 ciments, indicée j=1,2
• Entité 2 : Machines de cardinalité m=2, indicée i =1,2

• 2ème étape :

• Lister les données dépendant d’une ou plsrs entités
• Application :

• Les profits : Vecteur c de taille n, avec cj représentant le profit du ciment j
• Les disponibilités des machines : Vecteur b de taille m, avec bi représentant la disponibilité journalière de la machine i
• Les Temps-machines : Matrice A de taille (m ; n) avec aij représentant le temps de machine i nécessaire au ciment j

• 3ème étape :

• Définir les VD, la Fonction Objectif, et les contraintes
• Application :

• Les VD : Vecteur x de taille n = 2, ac xj représentant la Qté de Ciment j produite
• La Fonction-Objectif : Produit des vecteurs c et x (scalaire), définissant le profit total dégagé
• Les Contraintes :

• Terme de Gauche : Matrice Ax de taille (2 ;2), de terme général aij, xj, définissant les contraintes Temps-m        chien  
• Terme de droite :

• 4ème étape :

• Ecriture du prgrm
• Application :
• Max(z= 50.x1 + 70.x2) sous :

• 40.x1 + 30.x2 < 360
• 20.x1 + 30.x2 <480

• X1>0
• X2>0

• Formalisation spécifique :

• Pb du Sac de Campeur :

• Principe : Sélection optimale de biens sous contrainte d’une capacité limitée
• Illustration : soit un individu décidant de faire partir du camping disposant d’un sac de volume connu et d’un ensemble d’ustensiles présentant un niveau d’utilité donné et un volume donné à priori => Quels st les ustensiles que le campeur doit mettre ds son sac, de façon à maximiser son utilité, sous la contrainte de capacité de son sac ?
• Notations : 

• J/j = 1…n => ensemble des ustensiles de camping
• mj j = 1…n => masse (ou volume) de l’ustensile
• uj j= 1…n => utilité de l’ustensile
• C => résistance (ou volume) du sac
• Xj => Variable décisionnelle, renseignant sur la sélection (ou non) de l’ustensile (j) à l’Optimum

• Programme : Max Z =  sous Xj appartient {0,1}[pic 1]
• Explication :

• Fct°-Objct traduit le fait que l’on cherche à Max l’Utilité des ustensiles sélectionnés
• Le 1er type de contrainte impose que la somme des masses (ou volumes) des ustensiles sélectionnés à l’Optimum ne pt dépasser le résistance (ou volume) du Sac
• Le 2ème type de contrainte correspond aux traditionnelles contraintes d’intégrité en {0,1}, renseignant à l’Optimum i l’ustensile (j) est sélectionné (Xj = 1) ou pas (Xj = 0)

• Pb d’affection :

• 2 catégories d’entités (ouvriers et postes de travail)
• Affectation des entités de 1ère catégorie sur les entités de 2ème catégorie de façon à max un objctf (max productivité)
• Notations : matrice de prod + ensemble V.D => variables binaire (0,1) pr optimum individu sur la tâche (j)
• Formalisation :

• Max [pic 2]
• Sous :

• Somme Xj = 1
• Somme Xij = 1
• Xij appartient [0 ;1]

• Pb de chargement :

• Charger un nbr donné d’objets de tailles (m ou v) variées et connues à l’avance, ds un nbr min de contenants dst les capacités st données à l’avance
• « Big Packing Problem »
• Pb d’optimisation linéaire en [0 ;1]
• Rectorat souhaite conserver archives sur serveurs de stockage avec taille connues => découpage archives en fonction service ac taille fichier définie => Stockage ensbl archives ac min de cts
• Formalisation :

• m = nbr services
• ai = taille des archives du service
• n = nbr serveurs
• bj = capacité du serveur
• cj = ct de location du serveur
• Yj => binaire [0 ;1] => VD qui renseignent sur l’utilisation ou non de chqe serveur à l’optimum
• Xj => binaire [0 ;1] => VD qui renseignent sur l’affectation ou non de chqe archive à chqe serveur utilisé à l’optimum

• Programme :

• Min Z = [pic 3]
• Sous :

• Somme Xij = 1
• Somme (ai.Xi)         (bj.Yj)[pic 4]
• Yj appartient {0 ;1}
• Xij appartient {0 ;1}

• Commentaire :

• Fct° : min ct de locat° des servs utilisés
• C1 : chq archives doit être chargée sur un serv
• C2 : lien pr 2 VD + Somme des tailles archives chargées sur un serveur ne pt excéder la capacité de ce dernier et ceci pr ts les serveurs
• C3 : contrainte intégrité Yj => selection ou non serv à l’optimum
• C4 : contrainte intégrité Xij => affectation ou non archive à un serv à l’optimum

• Pb de Réseau :

• => le pb du + court chemin => graphe ac sommet (site) et arc (distance)
• Quel le plus court chemin pr aller de sommet A au sommet N ?
• Notations :

• I = ens des sommets du graphe
• J = ens des arcs du graphe
• Cj représentant les valeurs associées à chaque arc
• Xj => binaire {0 ;1} => VD qui représenteront le « passage ou non » par les arcs du graphe
• Aij = terme général de la matrice d’incidence sommets-arcs définie par :

• Lignes = m sommets du graphe
• Colonnes = n arcs du graphe
• Termes aij tel que :

• Aij = o => sommet n’appartient pas à l’arc
• Aij = -1 => sommet = 1er sommet de l’arc
• Aij = 1 => sommet = 2ème sommet de l’arc

• Bi = 2nd membres des contraintes

• Bi = -1 pr le somme de départ
• Bi = 1 pr le sommey d’arrivée
• Bi = 0 pr les autres sommets du graphe

• Formalisation :

• Min ([pic 5]
• Sous :

• Somme (j=1 ; i=D) de (aij.Xj) = -1
• Somme (j=1) de (aij.Xj) = 0 si i différent de A ;D
• Somme (j=1 ; i=A) de (aij.Xj) = 1
• Xj appartient à {0 ;1} ac j compris entre 1 et n

• Commentaires :

• Fct° : somme des arcs retenus à l’optimum, pondérée par le tmps de déplacement
• C1 : Formalise le pt de Départ (D) du réseau de transport => 2nd mbr = -1
• C3 :  Formalise le pt d’Arrivée (A) du réseau de transport => 2nd mbr = 1
• 2ème jeu de C : Formalise les sommets intermédiaires, parcourus ou pas dans l’itinéraire => 2nd mbre = 0
• 4ème jeu de C : VD Binaires

RESOLUTION

• Intro :

• 2 aspects à distinguer ds la phase de résolution :

• Dimension « Fondamentale » de la Réso de PL
• Dimension « Appliquée » de la Réso de PL

• Préambule :

• Méthodes de résolutions st complexes et extrêmement techniques
• Prennent forme via algorithmes :

• Procédure de calcul
• Processus itératif

• Présentation « intuitive » => distinction :

• Méthodes pr Programmation Linéaire « Classique » (PLNR)
• Méthodes pr Programmation Linéaire Entière (PLNE ou PL(0 ;1))

• Méthodes de Résolution en PLNR :

• Intro :

• Pr Programmation linéaire nbr réels
• 3 « Grands Familles » de méthodes :

• Méthodes de pts frontière : Type-SIMPLEXE => les + connues => créée par G. Dantzig (1943)
• Méthodes de pts extérieurs : Type-Ellipsoïde => les + complexes => créée par L. Khatchiyan (1979)
• Méthodes de pts intérieurs : Type-Parcours => les + récentes => créée par N. Karmarker (1984)

• Intuition :

• 3 familles de méthodes st très différentes ds leur fonctionnement => algo différents les des autres (+complexes)
• Mais même intuition basique et simpliste :

• Ens des contraintes st représentés ss la forme d’un polyèdre
• Ex ac PL ac 2VD et représentation graph :

• Contraintes symbolisées ac droites
• Solutions symbolisées ac zone polygonale entre les droites de contraintes
• Fct° représentée ac 1 autre droite
• Solution optimale = meilleur sommet de croisement entre droite fct° et droite contrainte (le + haut possible)

• Intérêt :

• => résolution PL ac 2 VD par représentation graph (pas plus de 2 VD !)
• On constate que solut° optimale se trouve tjrs sur l’un des sommets => résolt° = recherche sur ens sommets du polyèdre => cette recherche diffère entre chque « groupes de familles »

• 1ère méthode = recherche en déplaçant sur le polytope
• 2ème méthode = recherche en déplaçant ds le polytope
• 3ème méthode = recherche en déplaçant hors du polytope

• Type-SIMPLEXE = « Se promener » sur la Surface du Polytope, en transitant par les arêtes, d’un sommet à son sommet adjacent
• Type-Parcours = Algorithme MPI => « Plonger » ds le Polytope, pr remonter progressivement « en surface » jusqu’au sommet optimal
• Type-Ellipsoïde = « resserrement » progressif d’ellipsoïdes- de volumes décroissants – « englobant » le polytope jusqu’au contact avec le sommet optimal

• Méthode de résolution en PLNE/PLZU

• Autre solut° : + complexe et + couteuse
• PLNE : x appartient à N (vs PLNR : x appartient à R+)
• PLNE : solution = pt (vs PLNR : solution = zone)
• Familles de méthodes :

• Méthodes exactes :

• Arborescentes ou coupes
• Principes : utilisation méthode traditionnelle ac adaptation pr nb entier 
• Solution optimale/ globale mais tmps de calcul important
• Rq : solveur Excel = méthode de type Branch-and-bound pr les PL en nb entiers ou {0 ;1}

• Méthodes approchées :

• Types : « de décomposition », « génération de colonnes », ou « relaxation Lagrangienne »
• Principe : simplification ou modif pour résolution via d’autres méthodes d’optimisation
• + rapides mais non garantie de l’obtention de l’optimum global
• Techniquement complexe et de – en - utilisée

• Méthodes Heuristiques :

• Types : « heuristiques à Parcours », « heuristiques par déplacement », « métaheuristiques », « méthodes hybridées », …
• Principe : résolution sur la base d’une « bonne idée » ou d’une « analogie » issue d’une autre Science
• Tes rapides mais permet d’obtenir uniquement une « bonne solution » (pas de garantie d’optimum global)

• => pr palier « l’inefficacité » des méthodes traditionnelles

• CCL :

• Résolution :

• Méthode PLNR st arrives « à maturité » (possibilité de traitment ac millions de VD)
• Optimisation entière fait face à un dilemne :

• Obtenir solution opti ac tmps de calcul très élevé
• Obtenir une « bonne solution » ac tmps de calcul réduit

• …

ASPECTS PRATIQUES

• Préambule :

• Utilisation solveur
• Solveur = logicel dt la finalité se résume à permettre la résolution de Programmes d’optimisation de tts types et de ttes tailles
• Il existe différents types de solveurs
• On se limite ici à l’utilisation du « Spreadsheet Add-in »

• Petit programme informatique qui vient se « greffer » sur un tableur => résout pbs mise en forme sur le tableur
• Fonctionnalité ac double principe :

• Utilisation des fonctionnalités d’Excel pr recréer le programme d’optimisation
• Utilisation des techniques de résolutions via interface pour résoudre le pb d’optimisation mise en forme ds le tbleur
• Voir exemple « Production de ciment »

• Utilisation :

• 2 étapes : recréation du pb sur Excel et utilisation solveur pr résoudre pb
• Etape 1 :

• Fonctionne à partir de cellules pr rentrer données
• Utilisation des fonctions Excel pr calculer indicateurs
• => permet de renter les données du pb et recréer les relations mathématiques qui y sont lié

...