Recherche opérationnelle et applications

Ce document présente les concepts fondamentaux de la recherche opérationnelle, ses techniques principales, ainsi que des applications concrètes en programmation linéaire et en optimisation combinatoire. Il s’adresse aux étudiants et professionnels souhaitant comprendre et appliquer les méthodes d’aide à la décision basées sur des modèles mathématiques.

Introduction à la recherche opérationnelle

Quelques exemples de modèles mathématiques

La recherche opérationnelle vise à modéliser et résoudre des problèmes d’aide à la décision. Un problème typique comporte :

• Alternatives : variables inconnues représentant les choix possibles.
• Restrictions : contraintes que doivent respecter ces variables.
• Fonction objectif : critère à optimiser (minimiser ou maximiser).

Exemple 1 (Achat de billets d’avion) : Un homme d’affaires doit effectuer 5 voyages hebdomadaires entre Fayetteville (FYV) et Denver (DEN), avec différentes options tarifaires (aller-retour, réduction weekend, aller simple). L’objectif est de minimiser le coût total des billets tout en respectant les contraintes de dates.

Définitions importantes :

• Solution admissible : ensemble de valeurs des variables satisfaisant toutes les contraintes.
• Solution optimale : solution admissible qui optimise la fonction objectif.
• Modèle de recherche opérationnelle : problème d’optimisation formulé avec variables, contraintes et fonction objectif, pouvant être linéaire ou non, avec variables continues, entières ou booléennes.

Exemple 2 (Maximisation de la surface d’un rectangle) : On plie un fil de longueur L en rectangle pour maximiser la surface A = l × w sous la contrainte l + w = L. La solution optimale est l = w = L/2.

Méthodes de résolution

Les problèmes simples peuvent être résolus analytiquement, mais la plupart des problèmes pratiques nécessitent des méthodes itératives, exactes ou heuristiques, pour approcher ou atteindre l’optimum.

Tour d’horizon des techniques

Les principales techniques de recherche opérationnelle sont :

• Programmation linéaire
• Programmation en nombres entiers
• Optimisation dans les réseaux
• Programmation non linéaire
• Optimisation multi-critères
• Programmation dynamique
• Modèles stochastiques
• Simulation

Applications de la programmation linéaire

Notions de bases

Un programme linéaire est un modèle mathématique où la fonction objectif et les contraintes sont linéaires en les variables. Il permet d’optimiser l’usage de ressources limitées dans divers domaines.

Exemples de modèles linéaires

Exemple 3 (Production de peinture) : Une société produit deux types de peinture (extérieur et intérieur) à partir de deux matières premières M1 et M2. Les variables sont les quantités produites x1 (extérieur) et x2 (intérieur). Le profit à maximiser est :

max z = 5x1 + 4x2

avec les contraintes :

6x1 + 4x2 ≤ 24
x1 + 2x2 ≤ 6
x2 ≤ 2
x2 − x1 ≤ 1
x1, x2 ≥ 0

Une solution admissible est par exemple x1 = 3, x2 = 1, avec un profit z = 19.

Exemple 4 (Diet problem) : Minimiser le coût d’un aliment pour bétail composé d’orge (x1) et d’arachide (x2) sous contraintes nutritionnelles :

min z = 0.0015x1 + 0.0045x2
s.c.
x1 + x2 ≥ 400
0.09x1 + 0.6x2 ≥ 0.3(x1 + x2)
0.02x1 + 0.06x2 ≤ 0.05(x1 + x2)
x1, x2 ≥ 0

Forme standard et forme canonique d’un programme linéaire

Un programme linéaire peut s’écrire sous deux formes :

• Forme standard : toutes les contraintes sont des égalités, variables non négatives.
• Forme canonique : toutes les contraintes sont des inégalités (≤), variables non négatives.

Par exemple, la forme standard du problème de production de peinture s’écrit en introduisant des variables d’écart s1, s2, s3, s4 :

max z = 5x1 + 4x2
s.c.
6x1 + 4x2 + s1 = 24
x1 + 2x2 + s2 = 6
x2 + s3 = 2
x2 − x1 + s4 = 1
x1, x2, s1, s2, s3, s4 ≥ 0

La représentation matricielle est :

max cT x
s.c. Ax = b
x ≥ 0

Variables pouvant prendre des valeurs négatives

Pour modéliser des variables non restreintes en signe, on les décompose en différence de deux variables non négatives :

x = x+ − x−
x+, x− ≥ 0

Exemple 5 (Vente de hamburgers) : Le fast-food peut commander de la viande supplémentaire (variable x3 non restreinte) avec un coût additionnel. On remplace x3 par x3+ − x3−, toutes deux ≥ 0.

Résolution de programmes linéaires

Résolution graphique

Pour deux variables, on peut représenter graphiquement les contraintes et la fonction objectif. L’ensemble des solutions admissibles forme un polyèdre. La solution optimale se trouve généralement à un sommet de ce polyèdre.

Exemple (Production de peinture) : La solution optimale est x1 = 3, x2 = 1.5, correspondant au sommet E du polyèdre formé par les contraintes.

La méthode du simplexe

Le simplexe est un algorithme itératif qui se déplace de sommet en sommet du polyèdre pour améliorer la fonction objectif jusqu’à atteindre l’optimum.

Concepts clés :

• Solution de base : solution obtenue en fixant n − m variables à zéro dans un système de m équations à n inconnues.
• Solution de base réalisable : solution de base où toutes les variables sont ≥ 0.

Exemple 6 (Production de peinture) : La base initiale B = {s1, s2, s3, s4} correspond à x1 = x2 = 0, s1 = 24, s2 = 6, s3 = 2, s4 = 1, solution réalisable au sommet (0,0).

L’algorithme du simplexe procède en trois étapes :

1. Détermination de la variable entrante (celle qui améliore le plus la fonction objectif).
2. Détermination de la variable sortante (celle qui devient nulle en premier en augmentant la variable entrante).
3. Pivotage : mise à jour du système pour échanger les variables en base.

La présentation en tableau permet d’effectuer ces calculs efficacement.

La méthode des deux phases

Lorsque la solution de base admissible n’est pas évidente, la méthode des deux phases introduit des variables artificielles pour trouver une base admissible ou prouver l’incompatibilité du problème.

Cas particuliers

• Solutions optimales multiples : plusieurs solutions optimales existent lorsque la fonction objectif est parallèle à une contrainte active.
• Problèmes non bornés : la fonction objectif peut croître indéfiniment dans une direction admissible.
• Problèmes impossibles : le système de contraintes est incompatible, aucune solution admissible n’existe.

Dualité

Le problème dual

À tout problème primal (maximisation sous contraintes d’égalité), on associe un problème dual (minimisation sous contraintes d’inégalité) :

Primal :

max cT x
s.c. Ax = b
x ≥ 0

Dual :

min bT y
s.c. AT y ≥ c
y non restreint

Exemple 11 illustre la construction du dual à partir d’un primal donné.

Relations primal/dual

Dualité faible : Pour toute solution admissible x du primal et y du dual, on a cT x ≤ bT y. L’égalité implique que x et y sont optimaux.

Dualité forte : Si primal et dual ont des solutions admissibles, leurs valeurs optimales coïncident. Si l’un est non borné, l’autre est infaisable.

Complémentarité : Pour une solution optimale (x,y), on a :

Pour chaque variable xi :

xi (aTi y − ci) = 0

Autrement dit, si xi > 0 alors aTi y = ci, sinon aTi y > ci.

Interprétation économique de la dualité

Dans un problème d’allocation de ressources :

• cj : profit par unité d’activité j
• bi : disponibilité de la ressource i
• aij : consommation de la ressource i par unité d’activité j
• xj : niveau de l’activité j
• yi : valeur d’une unité de la ressource i

La dualité exprime que le profit maximal est limité par la valeur des ressources disponibles. Lorsque le profit est maximal, les ressources sont pleinement exploitées.

Exemple 14 (Production de peinture) : La solution optimale x1 = 3, x2 = 1.5 donne un profit z = 21. Les valeurs duales y1 = 0.75, y2 = 0.5 indiquent l’augmentation du profit par unité supplémentaire de M1 ou M2.

Solveurs et langages de modélisation

Exemple 15 (Production de jouets)

Une société produit trains, camions et voitures avec 3 machines aux disponibilités limitées. Le problème primal maximise le profit sous contraintes de temps machine :

max z = 3x1 + 2x2 + 5x3
s.c.
2x1 + 0x2 + 4x3 ≤ 430
1x1 + 3x2 + 1x3 ≤ 460
1x1 + 2x2 + 0x3 ≤ 420
x1, x2, x3 ≥ 0

Le dual minimise le coût des ressources :

min w = 430y1 + 460y2 + 420y3
s.c.
2y1 + y2 + y3 ≥ 3
3y2 + 2y3 ≥ 2
4y1 + y2 ≥ 5
y1, y2, y3 ≥ 0

Types de solveurs

• Indépendants : puissants, intégrables via des bibliothèques (ex. CPLEX, XPRESS-MP, glpk).
• Intégrés aux tableurs : faciles d’accès mais moins efficaces pour grands modèles (ex. Excel).
• Langages de modélisation : permettent la séparation modèle/données et l’indépendance vis-à-vis du solveur (ex. AMPL, GNU MathProg).

Exemple de modèle AMPL (production de jouets)

set Toys;
param nMachines;
set Machines := 1..nMachines;

param profit {Toys};
param time {Machines,Toys};
param avail {Machines};

var prod {Toys} >= 0;

maximize total_profit:
  sum{t in Toys} profit[t]*prod[t];

subject to machine_usage {m in Machines}:
  sum{t in Toys} time[m,t] * prod[t] <= avail[m];

Programmation en nombres entiers et optimisation combinatoire

Définitions et exemples

La programmation en nombres entiers impose que certaines variables soient entières. Les problèmes combinatoires consistent à choisir une solution optimale parmi un ensemble fini d’alternatives. Ces problèmes sont souvent difficiles à résoudre.

Exemple 16 (Sélection de projets) : Choisir parmi 5 projets à exécuter sur 3 ans, sous contraintes budgétaires annuelles, pour maximiser le profit total. Variables binaires xj indiquent la sélection du projet j.

max z = 20x1 + 40x2 + 20x3 + 15x4 + 30x5
s.c.
5x1 + 4x2 + 3x3 + 7x4 + 8x5 ≤ 25
7x2 + 9x3 + 4x4 + 6x5 ≤ 25
8x1 + 10x2 + 2x3 + x4 + 10x5 ≤ 25
xj ∈ {0,1}

Exemple 17 (Problème avec coûts fixes) : Optimiser un plan d’abonnement téléphonique combinant coûts fixes et variables, avec variables continues xi et binaires yi.

Problème du voyageur de commerce (Exemple 18)

Visiter n villes une seule fois en minimisant le coût total. Variables binaires xij indiquent si l’arc (i,j) est dans le tour. Contraintes assurent qu’une ville est visitée une fois, et éliminent les sous-tours.

Problème de couverture (Exemple 19)

Minimiser le nombre de téléphones d’urgence installés pour couvrir toutes les rues d’un campus. Variables binaires xi indiquent l’installation aux carrefours.

Contraintes disjonctives (Exemple 20)

Modélisation de contraintes où au moins une contrainte parmi plusieurs doit être satisfaite, par exemple pour ordonnancer des tâches sur une machine. Utilisation de variables binaires auxiliaires yij pour indiquer l’ordre d’exécution des tâches.

Complexité des problèmes et efficacité des algorithmes

La théorie de la complexité classe les problèmes selon leur difficulté :

• Problèmes faciles : existence d’algorithmes efficaces (ex. programmation linéaire, affectation, plus courts chemins).
• Problèmes difficiles : NP-complets, pour lesquels il est peu probable de trouver un algorithme efficace (ex. programmation en nombres entiers, voyageur de commerce).

Glossaire des termes clés

• Recherche opérationnelle : discipline d’aide à la décision utilisant des modèles mathématiques et des algorithmes d’optimisation.
• Solution admissible : solution respectant toutes les contraintes du problème.
• Solution optimale : solution admissible qui maximise ou minimise la fonction objectif.
• Programme linéaire : problème d’optimisation avec fonction objectif et contraintes linéaires.
• Variable d’écart : variable ajoutée pour transformer une inégalité en égalité dans un programme linéaire.
• Simplexe : algorithme itératif pour résoudre les programmes linéaires en se déplaçant de sommet en sommet.
• Dualité : relation entre un problème primal et son problème dual, avec des propriétés d’optimalité et d’interprétation économique.
• Variable binaire : variable prenant uniquement les valeurs 0 ou 1, utilisée en programmation en nombres entiers.
• Contraintes disjonctives : contraintes où au moins une parmi plusieurs doit être satisfaite.
• NP-complet : classe de problèmes pour lesquels aucun algorithme efficace n’est connu.

Points clés à retenir

• La recherche opérationnelle modélise les problèmes d’aide à la décision avec variables, contraintes et fonction objectif.
• La programmation linéaire est une technique centrale, avec des algorithmes efficaces comme le simplexe.
• La dualité offre une interprétation économique et des outils d’analyse complémentaires.
• Les problèmes en nombres entiers et combinatoires sont souvent plus difficiles, nécessitant des méthodes spécifiques.
• Les solveurs et langages de modélisation facilitent la résolution pratique des problèmes complexes.
• La compréhension des propriétés mathématiques (optimalité, dualité, complémentarité) est essentielle pour interpréter les résultats.