Modèles de recherche opérationnelle
Pr. BARKATOU
Université Chouaib Doukkali
Faculté des sciences
Pr. BARKATOU Licence
Origines de la recherche opérationnelle
Si la recherche opérationnelle, en abrégé RO, est aujourd’hui
présente dans la plupart des domaines civils, ses racines sont
habituellement attribués aux services militaires. La seconde guerre
mondiale, de part son envergure, créa une besoin urgent d’allouer
de manière efficace des ressources limitées aux différentes
opérations militaires et aux activités au sein de chaque opération.
En particulier, l’organisation militaire britannique, puis américaine,
mis à contribution un grand nombre de scientifiques pour gérer ces
allocations, et s’occuper d’autres problèmes stratégiques et
tactiques. Ce faisant, ils furent appelés à poursuivre des recherches
sur des opérations (militaires), et constituèrent les premières
équipes de RO. Leurs efforts furent signifactifs dans la marche vers
la victoire, par exemple en ce qui touche l’utilisation du radar,
nouvellement développé. Ces succès encouragèrent la poursuite de
l’utilisation de la RO dans d’autres domaines.
Pr. BARKATOU Licence
Origines de la recherche opérationnelle
La croissance importante de l’industrie d’après-guerre entraı̂na des
problèmes, causés par la complexité croissante et la spécialisation
dans les organisations, problèmes en fait proches de ceux présent
lors du conflit. Au début des années 1950’s, la RO avait pénétré
une multitude d’organisations commerciales, industrielles, et
gouvernementales. Et ce n’était que le début. Au moins deux autres
facteurs ont joué un rôle clé dans la croissance rapide de la RO.
Tout d’abord, des progrès substantiels ont été obtenus très tôt afin
d’améliorer les techniques de RO. Ces techniques, dans leur mise
en pratique, furent soutenues par l’essor des outils informatiques.
Pr. BARKATOU Licence
Nature de la recherche opérationnelle
Rechercher sur des opérations touche tous les problèmes reliés à la
conduite et à la coordination des opérations (activı́tés) au sein
d’une organisation. Cette organisation peut représenter des
domaines très divers : l’industrie manufacturière, le transport, la
construction, les télécommuncations, la finance, les soins de santé.
La RO, associée à la révolution informatique, pénètre pratiquement
tous les secteurs d’activités de la vie courante, même si sa présence
est souvent invisible.
Pr. BARKATOU Licence
Nature de la recherche opérationnelle
La première étape de la recherche est l’observation attentive du
problème et sa formulation, ainsi que la collecte de données
associées. Il convient par la suite de construire un modéle
scientifique qui tente l’essence du problème réel. Tout modèle est
une simplification de la réalité, mais cette représentation doit être
sudffisamment précise pour capturer les caractéristiques essentielles
de la situation, et de pouvoir tirer des conclusions valides pour le
problème réelle. Il conviendra dès lors de tester ce modèle, et de le
modifier au besoin.
Pr. BARKATOU Licence
Nature de la recherche opérationnelle
Une caractéristique additionnelle est que la RO essaye souvent de
trouver une meilleure solution (dite solution optimale) pour le
problème examiné. Cette solution peut ne pas être unique. Cette
recherche d’optimalité est un thème important en RO, mais si son
interprétation en terme managériels peut être délicate. Il est
difficile pour un individu de pouvoir maı̂trise tous les aspects du
problèmes à l’étude, de sorte que la RO est généralement plus un
travail d’équipe, avec des experts en mathématiques, statistiques
et probabilités, ingénierie, économie, administration, informatique,
physiques, sciences comportementales, et les techniques spécifiques
de la RO.
Pr. BARKATOU Licence
Modélisation
Un modèle, telle que considéré dans ce cours, est une construction
mathématique utilisée pour représenter certains aspects significatifs
de problèmes du monde réel. Il y a beaucoup de types différents de
modèles mathématiques, mais nous nous focaliserons dans un
premier temps sur les modèles d’optimisation. Il y a trois
composantes principales dans un modèle d’optimisation :
Variables : elles représentent les composantes du modèle qui
peuvent être modifiées pour créer des configurations
différentes.
Contraintes : elles représentent les limitations sur les variables.
Fonction objectif : cette fonction assigne une valeur à chaque
configuration différente. Le terme objectif vient du fait que
l’objectif est d’optimiser cette fonction.
Pr. BARKATOU Licence
Modèles d’optimisation
Programmation Linéaire (PL) : Méthode du Simplexe.
Programmation Non Linéaire (PNL) (Optimisation
numérique) : Algorithmes de descente Gradient, Gradient
conjugué...Lagrangien, Condition KKT.
Programmation Mixte Entière (PME) : Algorithme de
Branch and Bound.
Programmation Stochastique (PS)
Programmation Dynamique (PD)
Théorie des Graphes (TG) : Algorithme Dijkstra (Pb Plus
Court Chemin) ; Algorithme Belleman-Ford (Pb Flot de
réseaux) ; Algorithme Ford-Fulkerson (Pb Flot maximum)
Pr. BARKATOU Licence
Exemple de Modélisation
Un exemple de décisions binaires (oui/non) : Un étudiant en quête
d’une université projette de visiter les campus de trois universités
du Maine au cours d’un voyage unique, débutant et finissant à
l’aéroport de Portland. Les trois établissements sont dans les villes
de Brunswick, Lewiston, et Waterville, et l’étudiant ne veut visiter
chaque ville qu’une seule fois, tout en maintenant le trajet total le
plus court possible. Les distances entre ces villes sont données.
Pr. BARKATOU Licence
Exemple de Modélisation
L’étape la plus importante dans la construction d’un modèle est le
choix des variables qui vont entrer en jeu. Dans le présent cas,
puisque n’importe quel trajet consiste en une série de petits
déplacements entre deux villes, il est raisonnable d’assigner des
variables aux décisions de partir ou non d’une ville vers une autre.
Pour plus de facilités, numérotons les villes comme suit : 1 pour
Portland, 2 pour Brunswick, 3 pour Lewiston et 4 pour Waterville.
Ainsi, nous aurons une variable x12 égale à 1 si l’étudiant voyage
de Portland à Brunswick au cours de son parcours total, et 0 sinon.
Puisqu’il n’y a pas de voyage d’une ville vers cette même ville, nous
avons d’ores et déjà les contraintes suivantes
xii = 0; i = 1, ..., 4.
Pr. BARKATOU Licence
Exemple de Modélisation
Une fois les variables choisies, nous pouvons essayer de formuler le
problème. Ce processus est en fait souvent une manière utiles pour
guider le choix des variables. Chaque ville ne devant être visitée
qu’une seule fois, elle ne peut apparaı̂tre qu’une seule fois comme
ville d’arrivé. En d’autres termes, pour j fixé, xij ne peut être
non-nul que pour un i donné, avec i 6= j. Une manière plus simple
d’encoder cette information est d’écrire, pour j = 1, ..., 4
x1j + x2j + x3j + x4j = 1,
ou encore
i=4
X
xij = 1.
i=1
Pr. BARKATOU Licence
Exemple de Modélisation
Les contraintes formulées jusqu’à présent ne garantissent aucune
forme de trajet ayant même départ et arrivée. Par exemple,
l’affectation x12 = 1, x13 = 1, x14 = 1, x21 = 1, et toutes les autres
variables égales à 0, satisfont les contraintes précédentes. Cette
solution décrit toutefois un schéma de visites impossible puisque
Portland est l’origine de tous les déplacements aux trois autres
villes universitaires, mais n’est destination que depuis Brunswick.
Nous avons évidemment aussi besoin des contraintes :
j=4
X
xij = 1,
j=1
Pr. BARKATOU Licence
Exemple de Modélisation
afin d’assurer que chaque ville ne serve d’origine que pour
exactement un déplacement vers une autre ville. Finalement, afin
d’obtenir un véritable trajet ayant même origine et départ, nous
devons rejeter les affectations qui décrivent des groupes
déconnectés de petits déplacements comme x12 = x21 = 1,
x34 = x43 = 1, avec toutes les autres variables égales à 0. Nous
pouvons forcer ceci avec les contraintes
xij + xji ≤ 1, i, j = 1, ..., 4.
Cette contrainte exclut tout mini-cycle.
Pr. BARKATOU Licence
Exemple de Modélisation
Les contraintes définies, nous devons décrire la distance totale
associé à n’importe quel parcours autorisé. Puisque nos variables
ont seulement comme valeurs possibles 0 ou 1, nous pouvons
multiplier chacune d’elle par la distance correspondante entre les
deux villes indexées aij , i, j = 1, ..., 4, et les additionner :
j=4
i=4 X
X
xij aij .
i=1 j=1
Pr. BARKATOU Licence
Exemple de Modélisation
Notre modèle mathématique consiste à minimiser cette fonction,
dite fonction objectif par rapport aux variables xij , tout en
satisfaisant les contraintes préalablement décrites :
j=4
i=4 X
X
min xij aij
i=1 j=1
s.c. xii = 0; i = 1, ..., 4,
i=4
X
xij = 1,
i=1
j=4
X
xij = 1,
j=1
xij + xji ≤ 1, i, j = 1, ..., 4,
xij ∈ {0, 1}, i, j = 1, ..., 4.
Pr. BARKATOU Licence
Exemple de Modélisation
Le problème d’optimisation ainsi construit constitue un programme
mathématique.
Le problème de visites d’universités est assez petit que pour être
résolu explicitement, sans recourir à des méthodes d’optimisation
numérique. Puisqu’il y a seulement trois parcours significativement
différents, la distance totale associée à chacun d’eux pourrait être
facilement calculée, et nous choisissons le parcours de longueur
minimale, qui est ici :
Portland → Brunswick → Waterville → Lewiston → Portland.
avec une distance totale de 163 miles. Il est cependant clair qu’une
telle stratégie de résolution ne fonctionne plus comme le nombre
de villes augmente.
Pr. BARKATOU Licence
Optimisation numérique
L’optimisation numérique est une branche des mathématiques
appliquées et de l’informatique qui vise à trouver les valeurs
optimales (minima ou maxima) d’une fonction objectif sous
certaines contraintes. Elle est utilisée dans de nombreux domaines
tels que l’ingénierie, l’économie, la physique, et l’apprentissage
automatique.
Pr. BARKATOU Licence
Problèmes d’optimisation
Un problème d’optimisation peut être formulé comme suit :
Minimiser f (x)
sous les contraintes :
g(x) ≤ 0, h(x) = 0,
où :
f (x) est la fonction objectif à minimiser.
g(x) représente les contraintes d’inégalité.
h(x) représente les contraintes d’égalité.
x est le vecteur des variables de décision.
Pr. BARKATOU Licence
Méthodes d’optimisation sans contraintes
La méthode de la descente de gradient est une technique itérative
pour trouver le minimum d’une fonction. Elle consiste à mettre à
jour les variables de décision selon :
xk+1 = xk − α∇f (xk ),
où α est le pas de la méthode.
Pr. BARKATOU Licence
Méthode de Newton
La méthode de Newton utilise la matrice hessienne pour converger
plus rapidement vers le minimum :
xk+1 = xk − H−1 (xk )∇f (xk ),
où H(xk ) est la matrice hessienne de f en xk .
Pr. BARKATOU Licence
Méthodes d’optimisation avec contraintes : Méthode de
Lagrange
La méthode du lagrangien transforme un problème d’optimisation
avec contraintes en un problème sans contraintes en introduisant
des multiplicateurs de Lagrange :
L(x, λ) = f (x) + λ> g(x).
Pr. BARKATOU Licence
Méthodes d’optimisation avec contraintes : Méthode des
points intérieurs
La méthode des points intérieurs est une technique efficace pour
résoudre des problèmes d’optimisation avec contraintes d’inégalité.
Elle consiste à approcher la solution en restant à l’intérieur de la
région réalisable.
Pr. BARKATOU Licence
Applications de l’optimisation numérique
Apprentissage automatique : En apprentissage
automatique, l’optimisation numérique est utilisée pour
entraı̂ner des modèles en minimisant une fonction de perte.
Ingénierie : En ingénierie, l’optimisation est utilisée pour
concevoir des systèmes optimaux, comme la minimisation du
poids d’une structure tout en respectant des contraintes de
résistance.
Économie : En économie, l’optimisation est utilisée pour
maximiser le profit ou minimiser les coûts sous des contraintes
budgétaires.
Pr. BARKATOU Licence
Exemple : Minimisation d’une fonction quadratique
Considérons la fonction quadratique :
1
f (x) = x > Qx + c> x,
2
où Q est une matrice symétrique définie positive et c est un
vecteur. La solution optimale est donnée par :
x∗ = −Q−1 c.
En pratique, on peut utiliser la méthode de la descente de gradient
ou la méthode de Newton pour trouver x∗ .
Pr. BARKATOU Licence
Pr. BARKATOU Licence
Pr. BARKATOU Licence
Pr. BARKATOU Licence
Pr. BARKATOU Licence
Pr. BARKATOU Licence
Pr. BARKATOU Licence
Pr. BARKATOU Licence
Pr. BARKATOU Licence