Chapitre 1 · Semestre 5

Recherche opérationnelle, intelligence artificielle et modélisation

Intelligence Artificielle et Recherche Opérationnelle

Cours Exercices Résumé QCM

Objectifs du chapitre — À la fin de ce chapitre, vous saurez :

définir la recherche opérationnelle et situer l'intelligence artificielle par rapport à elle ;

décrire les étapes d'une étude de RO, du problème réel à la décision ;

traduire un problème économique en programme linéaire : variables, objectif, contraintes ;

énoncer les hypothèses de la programmation linéaire et reconnaître les grandes familles de modèles ;

écrire un programme linéaire sous forme canonique et sous forme standard.

1.1 Qu'est-ce que la recherche opérationnelle ?

Définition — Recherche opérationnelle : discipline qui applique des méthodes mathématiques et informatiques pour aider à prendre la meilleure décision possible dans un système soumis à des contraintes (ressources limitées, délais, capacités).

Née pendant la Seconde Guerre mondiale (placement des radars, organisation des convois), la RO s'est diffusée dans l'industrie après 1947, quand George Dantzig a inventé la méthode du simplexe. Elle sert aujourd'hui à planifier la production d'une usine, à organiser les tournées de livraison, à affecter les avions et les équipages d'une compagnie aérienne, à gérer les flux d'un port comme Tanger Med ou à composer un portefeuille financier.

Définition — Intelligence artificielle : ensemble de méthodes qui permettent à une machine de réaliser des tâches qui demandent de l'intelligence à un être humain : raisonner, chercher une solution, reconnaître des formes, apprendre à partir d'exemples.

La RO et l'IA se recoupent largement. La RO cherche des solutions optimales à des problèmes bien formulés ; l'IA apporte deux compléments : des méthodes de recherche approchée (heuristiques, métaheuristiques, chapitre 7) pour les problèmes trop grands, et l'apprentissage automatique (chapitre 8), qui construit des règles de décision à partir de données au lieu de les écrire à la main.

1.2 La démarche d'une étude de recherche opérationnelle

Analyser le problème : qui décide, quel est l'objectif, quelles sont les contraintes ?
Construire le modèle : traduire le problème en équations (variables de décision, fonction objectif, contraintes).
Collecter les données : coûts unitaires, capacités, demandes, durées.
Résoudre : méthode exacte (simplexe, algorithme de graphe) ou approchée (heuristique), souvent avec un logiciel (solveur d'Excel, Python, logiciels spécialisés).
Valider : la solution est-elle réaliste ? Que se passe-t-il si les données changent (analyse de sensibilité, chapitre 4) ?
Mettre en œuvre et suivre les résultats.

Le modèle est une simplification : il retient les éléments essentiels et néglige les autres. Un bon modèle est assez simple pour être résolu et assez fidèle pour que sa solution soit utile.

1.3 Les trois composantes d'un programme linéaire

Un programme linéaire (PL) est un modèle d'optimisation dont l'objectif et les contraintes sont des fonctions linéaires des variables.

Définition — Variables de décision : grandeurs que le décideur choisit (quantités à produire, à transporter, à acheter), notées $x_1, x_2, \ldots, x_n$, généralement positives ou nulles.

Définition — Fonction objectif : expression à maximiser (profit, chiffre d'affaires, audience) ou à minimiser (coût, distance, durée) : $Z = c_1 x_1 + c_2 x_2 + \ldots + c_n x_n$.

Définition — Contraintes : inégalités ou égalités qui traduisent les limites du système : $a_{i1} x_1 + \ldots + a_{in} x_n \le b_i$ (ressource disponible), $\ge b_i$ (exigence minimale) ou $= b_i$.

Exemple fil rouge — Un atelier de meubles de Salé. L'atelier fabrique des tables et des chaises. Une table rapporte une marge de 300 DH et demande 2 heures de menuiserie et 1 heure de finition ; une chaise rapporte 200 DH et demande 1 heure de menuiserie et 1 heure de finition. Chaque semaine, l'atelier dispose de 100 heures de menuiserie et de 80 heures de finition ; le bois spécial des plateaux limite la production à 40 tables.

On note $x_1$ le nombre de tables et $x_2$ le nombre de chaises produites par semaine :

$$\max Z = 300\,x_1 + 200\,x_2$$

$$\text{s.c.} \quad \begin{cases} 2x_1 + x_2 \le 100 & \text{(menuiserie)} \\ x_1 + x_2 \le 80 & \text{(finition)} \\ x_1 \le 40 & \text{(bois)} \\ x_1, x_2 \ge 0 \end{cases}$$

Ce programme sera résolu graphiquement au chapitre 2, par le simplexe au chapitre 3, et son dual interprété au chapitre 4.

1.4 Les hypothèses de la programmation linéaire

Hypothèse	Signification	Exemple de violation
Proportionnalité	La contribution de chaque variable est proportionnelle à sa valeur	Remise sur quantité, économies d'échelle
Additivité	Les contributions s'additionnent	Deux produits qui se cannibalisent
Divisibilité	Les variables peuvent prendre des valeurs non entières	On ne fabrique pas 12,5 avions
Certitude	Les coefficients sont connus avec certitude	Demande aléatoire, prix volatils

Quand la divisibilité n'est pas acceptable, on passe à la programmation linéaire en nombres entiers (PLNE) ; quand une variable ne peut valoir que 0 ou 1 (ouvrir ou non un entrepôt, lancer ou non un projet), on parle de variable binaire. Quand l'objectif ou les contraintes ne sont pas linéaires, on parle de programmation non linéaire.

1.5 Les grandes familles de problèmes

Problème de production (mix de produits) : maximiser la marge sous contraintes de capacité.
Problème de mélange (diététique, alimentation animale, raffinage) : minimiser le coût d'un mélange qui respecte des teneurs minimales ou maximales.
Problème de transport et d'affectation (chapitre 5) : acheminer des marchandises au moindre coût, affecter des personnes à des tâches.
Problème de flux et de plus court chemin (chapitre 6) : réseaux routiers, logistiques, de télécommunication.
Ordonnancement (chapitre 6) : planifier les tâches d'un projet.
Problèmes combinatoires (chapitre 7) : sac à dos, voyageur de commerce, tournées de véhicules.

1.6 Forme canonique et forme standard

Un PL de maximisation est sous forme canonique si toutes les contraintes sont des inégalités $\le$ et toutes les variables sont positives. La méthode du simplexe exige la forme standard : toutes les contraintes sont des égalités. On y parvient en ajoutant à chaque contrainte $\le$ une variable d'écart $s_i \ge 0$, qui mesure la ressource non utilisée :

$$2x_1 + x_2 + s_1 = 100 \qquad x_1 + x_2 + s_2 = 80 \qquad x_1 + s_3 = 40$$

Pour une contrainte $\ge$, on retranche une variable d'excédent. Minimiser $Z$ revient à maximiser $-Z$.

1.7 Méthode : modéliser un problème en programme linéaire

Lire l'énoncé et identifier ce que l'on choisit : ce sont les variables (préciser l'unité et la période).
Écrire l'objectif : quelle grandeur maximiser ou minimiser, avec quels coefficients unitaires ?
Lister les ressources limitées (contraintes $\le$), les exigences minimales ($\ge$) et les égalités (bilans).
Ajouter les contraintes de signe (et d'intégrité si nécessaire).
Vérifier les unités de chaque contrainte et tester le modèle sur une solution simple (par exemple $x = 0$).

Les pièges à éviter

Choisir comme variables des grandeurs que le décideur ne contrôle pas (le prix de marché, la demande).
Mélanger les unités (heures et minutes, kilogrammes et tonnes) dans une même contrainte.
Prendre le prix de vente au lieu de la marge dans l'objectif quand les coûts varient selon le produit.
Oublier les contraintes de positivité.
Écrire une contrainte de teneur sous forme non linéaire ($x_1 / (x_1 + x_2) \ge 0{,}3$) au lieu de la linéariser ($x_1 \ge 0{,}3\,(x_1 + x_2)$).

Exercice 1 — Modéliser deux décisions d'entreprise

Partie A — Aliment de bétail à Meknès. Une coopérative prépare des sacs de 100 kg d'aliment pour vaches laitières à partir de maïs (1,2 % de fibres, 9 % de protéines, 3,2 DH le kg) et de tourteau de tournesol (12 % de fibres, 36 % de protéines, 4,5 DH le kg). Chaque sac doit contenir au moins 18 % de protéines et au plus 8 % de fibres.

Définissez les variables et formulez le programme linéaire qui minimise le coût d'un sac.
Montrez qu'un sac composé uniquement de maïs n'est pas réalisable.

Partie B — Plan média d'une marque de couscous. Une entreprise dispose de 360 000 DH pour sa campagne. Un spot radio coûte 6 000 DH et touche 40 000 auditeurs ; un spot télévisé coûte 30 000 DH et touche 250 000 téléspectateurs. La régie impose au plus 8 spots télévisés, et la marque veut au moins 10 spots radio.

Formulez le programme qui maximise l'audience totale. Quelle hypothèse de la programmation linéaire pose problème ? Comment appelle-t-on le modèle adapté ?

Voir le corrigé

1) Aliment de bétail. Variables : $x_1$ = kg de maïs, $x_2$ = kg de tourteau dans un sac.

$$\min Z = 3{,}2\,x_1 + 4{,}5\,x_2$$

$$\text{s.c.} \quad \begin{cases} x_1 + x_2 = 100 & \text{(poids du sac)} \\ 0{,}09\,x_1 + 0{,}36\,x_2 \ge 18 & \text{(protéines : 18 \% de 100 kg)} \\ 0{,}012\,x_1 + 0{,}12\,x_2 \le 8 & \text{(fibres : 8 \% de 100 kg)} \\ x_1, x_2 \ge 0 \end{cases}$$

Les teneurs ont été linéarisées grâce au poids fixe du sac : « au moins 18 % de protéines » devient « au moins 18 kg de protéines ».

2) Avec $x_1 = 100$ et $x_2 = 0$ : protéines $= 9$ kg $< 18$ kg. La contrainte de protéines est violée : le maïs seul est trop pauvre, il faut du tourteau. (À l'inverse, le tourteau seul donnerait 12 kg de fibres, au-delà de la limite de 8 kg.)

3) Plan média. Variables : $x_1$ = nombre de spots radio, $x_2$ = nombre de spots télévisés (audience en milliers).

$$\max Z = 40\,x_1 + 250\,x_2$$

$$\text{s.c.} \quad \begin{cases} 6\,x_1 + 30\,x_2 \le 360 & \text{(budget, en milliers de DH)} \\ x_2 \le 8 & \text{(régie)} \\ x_1 \ge 10 & \text{(présence radio)} \\ x_1, x_2 \ge 0 \text{ et entiers} \end{cases}$$

L'hypothèse de divisibilité ne tient pas : on ne diffuse pas 2,7 spots. Le modèle adapté est un programme linéaire en nombres entiers (PLNE). On peut résoudre le PL continu puis vérifier les solutions entières voisines, mais l'arrondi ne garantit pas l'optimum ; les logiciels utilisent la méthode de séparation et évaluation (branch and bound).

Exercice 2 — Résoudre le plan média

On reprend le plan média de l'exercice 1 : $\max Z = 40\,x_1 + 250\,x_2$ sous $6\,x_1 + 30\,x_2 \le 360$, $x_2 \le 8$, $x_1 \ge 10$, $x_1, x_2$ entiers positifs.

Calculez l'audience obtenue par millier de DH pour chaque média.
Déduisez la solution optimale et l'audience totale.
La régie supprime la limite de 8 spots télévisés. Que devient la solution ?

Voir le corrigé

1) Radio : $40/6 \approx 6{,}67$ milliers d'auditeurs par millier de DH ; télévision : $250/30 \approx 8{,}33$. La télévision est plus « rentable » en audience.

2) On achète le maximum de spots télévisés : $x_2 = 8$ (240 000 DH). Le reste du budget (120 000 DH) finance $120/6 = 20$ spots radio, ce qui respecte $x_1 \ge 10$. Audience : $40 \times 20 + 250 \times 8 = 800 + 2\,000 = \mathbf{2\,800}$ milliers de contacts. Remplacer un spot télévisé par 5 spots radio (même coût) ferait perdre $250 - 200 = 50$ milliers de contacts : la solution est optimale.

3) Il faut garder 10 spots radio (60 000 DH) ; les 300 000 DH restants financent $300/30 = 10$ spots télévisés. Audience : $400 + 2\,500 = \mathbf{2\,900}$ milliers. La contrainte de la régie « coûtait » 100 milliers de contacts.

Exercice 3 — Mettre un programme sous forme standard

Écrivez sous forme standard le programme : $\min Z = 4\,x_1 + 3\,x_2$ sous $2x_1 + x_2 \ge 10$, $x_1 + 3x_2 \ge 12$, $x_1 + x_2 \le 9$, $x_1, x_2 \ge 0$. Interprétez chaque nouvelle variable.

Voir le corrigé

On maximise $-Z$ et on transforme les inégalités :

$$\max\,(-Z) = -4\,x_1 - 3\,x_2 \quad \text{s.c.} \quad \begin{cases} 2x_1 + x_2 - e_1 = 10 \\ x_1 + 3x_2 - e_2 = 12 \\ x_1 + x_2 + s_3 = 9 \\ x_1, x_2, e_1, e_2, s_3 \ge 0 \end{cases}$$

$e_1$, $e_2$ sont des variables d'excédent : de combien on dépasse le minimum exigé ;
$s_3$ est une variable d'écart : capacité non utilisée.

Les variables d'excédent ont un coefficient $-1$ : elles ne fournissent pas de solution de base de départ évidente, d'où le recours, dans le simplexe, à des variables artificielles (méthode du grand M ou en deux phases).

L'essentiel — RO, IA et modélisation

Recherche opérationnelle : méthodes mathématiques pour la meilleure décision sous contraintes (Dantzig, simplexe, 1947).
IA : recherche approchée (heuristiques, métaheuristiques) et apprentissage à partir de données.
Démarche : analyser → modéliser → collecter les données → résoudre → valider (sensibilité) → mettre en œuvre.
Programme linéaire : variables de décision, fonction objectif linéaire, contraintes linéaires, positivité.
Hypothèses : proportionnalité, additivité, divisibilité, certitude.
Variables entières → PLNE (branch and bound) ; variables 0-1 → décisions oui/non.
Familles : production, mélange, transport-affectation, flux et chemins, ordonnancement, combinatoire.
Forme standard : contraintes en égalités grâce aux variables d'écart ($\le$) ou d'excédent ($\ge$) ; $\min Z = -\max(-Z)$.

S'entraîner sur des sujets réels

Des sujets réels de concours (master, licence d'excellence) avec une épreuve de Intelligence Artificielle et Recherche Opérationnelle : énoncé complet et corrigé indicatif.

Voir les 13 sujets de concours en Intelligence Artificielle et Recherche Opérationnelle →