Recherche opérationnelle

Modéliser un problème de décision

Avant tout calcul, il faut écrire le problème. Quels sont les choix ? Comment les juge-t-on ? Qu'est-ce qui les limite ? Que sait-on vraiment ? Cette page apprend à passer d'un énoncé en français à un modèle que l'on peut résoudre.

Modéliser, c'est traduire. Tout problème de décision se dit avec trois ingrédients : ce que l'on choisit, ce que l'on cherche à obtenir, et ce qui nous limite. Regardez ces trois ingrédients surgir d'un énoncé ordinaire.

Une chocolaterie doit fixer pour la semaine le nombre de caisses de pralines et le nombre de caisses de tablettes à fabriquer. Elle veut gagner le plus d'argent possible, sachant que chaque caisse rapporte 12 € ou 8 €. Mais elle ne dispose que de 100 heures de travail et de 120 kg de cacao, et elle ne vendra pas plus de 35 caisses de pralines ni plus de 50 de tablettes.

Variables de décisionx = caisses de pralines, y = caisses de tablettes

Fonction objectifmaximiser 12 x + 8 y

Contraintes2 x + y ≤ 100 (heures), x + 2 y ≤ 120 (cacao), x ≤ 35, y ≤ 50, x, y ≥ 0

Les planches 1 à 4 examinent chaque ingrédient l'un après l'autre. La planche 5 reprend cette chocolaterie du début à la fin. Les exemples sont inventés pour rester lisibles ; tous les résultats sont calculés sur place dans votre navigateur, et les lectures « contrôle » les confrontent à une seconde méthode.

Planche 1

Les variables de décision : sur quoi a-t-on la main ?

Une variable de décision est une grandeur dont vous fixez la valeur. C'est le point de départ, et la première erreur consiste à y mettre ce qui n'en est pas. Une boulangerie prépare sa fournée du matin : triez ces huit grandeurs.

Bonnes réponses0 sur 8

Le test en trois questions. Puis-je en changer la valeur aujourd'hui ? C'est une variable. Existe-t-elle avant ma décision, sans que j'y puisse rien ? C'est une donnée. Se déduit-elle de ce que j'ai choisi ? C'est un résultat. Attention : cela dépend de la situation. Si la boulangère peut changer ses prix, le prix devient une variable, et le modèle change.

De quelle nature est-elle ?

Une variable peut prendre toutes les valeurs d'un intervalle (des litres, des hectares), seulement des nombres entiers (des camions), ou seulement 0 et 1 (ouvrir ou non une usine). Avec deux variables, voici à quoi ressemble l'ensemble des choix. À droite, ce qu'il en coûte quand le nombre de variables augmente.

Trois natures de variables, deux variables à chaque fois : la décision (point rouge) se promène dans un continu, saute sur un quadrillage, ou bascule entre quatre coins.

Logarithme décimal du nombre de combinaisons, selon le nombre de variables. Lignes grises : ce qu'un ordinateur examinant un milliard de combinaisons par seconde parcourt en une seconde, un an, et depuis le début de l'Univers (13,8 milliards d'années).

Nombre de variables

Valeur maximale de chaque variable entière

Combinaisons entières–

Combinaisons si variables binaires–

Temps pour tout examiner–

Contrôle : combinaisons comptées une à une–

Le même problème peut s'écrire de plusieurs façons

Il faut affecter n employés à n tâches. On peut dire « une liste : qui fait quoi », ou écrire une matrice de variables binaires : x_ij = 1 si l'employé i prend la tâche j. La seconde écriture autorise bien plus de combinaisons, dont presque toutes sont absurdes : ce sont les contraintes qui devront les éliminer.

La matrice x_ij. Une case bleue vaut 1. Admissible : un seul 1 par ligne et par colonne. Lignes et colonnes en faute : en rouge.

Nombre d'employés et de tâches

Variables binaires–

Matrices possibles–

Admissibles, comptées une à une–

Contrôle : n !–

Part de matrices admissibles–

–

Ce qu'il faut retenir. Choisir ses variables, c'est choisir le langage du problème. Un bon choix permet d'écrire simplement l'objectif et les contraintes : toutes les quantités du modèle doivent pouvoir se calculer à partir des variables. Pensez aussi à fixer leur unité : caisses, tonnes, heures. Beaucoup d'erreurs viennent de là.

Planche 2

La fonction objectif : selon quoi juger une décision ?

La fonction objectif attribue une note à chaque décision. Changer de note, c'est changer de meilleure décision, même si rien d'autre ne bouge. Une commande de 100 pièces doit être répartie entre deux machines : x pièces sur A (rapide), le reste sur B (lente). Une seule variable, trois façons de juger.

En haut, le travail de chaque machine : le délai est celui de la dernière à finir. Le trait rouge marque la date promise. En dessous, les trois notes selon x, chacune avec son meilleur point.

Chaque point est une répartition, vue par son délai et son coût. En bleu, les décisions efficaces : on ne peut y améliorer un critère sans dégrader l'autre. En gris, les autres : une décision fait mieux sur les deux tableaux.

Pièces sur la machine A (x)

Coût à la pièce sur A

Pénalité par heure de retard

Délai promis

Coût C(x)–

Délai D(x)–

Bénéfice B(x)–

Meilleur x : coût / délai / bénéfice–

Contrôle : formules contre recherche numérique, plus grand écart sur x–

C(x) = c_A x + 0,04 x² + 8 (100 − x) + 0,01 (100 − x)² ; D(x) = max( x / 4 ; (100 − x) / 2,5 ) ; B(x) = 1 500 − C(x) − p · max(0 ; D(x) − D₀)

Ce qu'il faut retenir. Le moins cher, le plus rapide et le plus rentable sont trois décisions différentes : le modèle ne peut pas choisir à votre place ce qui compte. Pour concilier deux critères, on en convertit un en argent (ici la pénalité de retard), ou on le transforme en contrainte (« délai ≤ 20 h »), ou on présente toute la courbe bleue au décideur. Minimiser f revient au même que maximiser −f : le sens n'est qu'une convention.

Planche 3

Les contraintes : ressources, capacités, budget, demande

Une contrainte est une condition que toute décision doit respecter. Chacune retire une partie des choix possibles. Un exploitant répartit ses plantations entre pommiers (x hectares) et poiriers (y hectares). Retirez les contraintes pour voir ce qu'elles font, puis remettez-les.

Zone bleue : les plans admissibles. Rouge qui s'efface : ce que vient de retirer une contrainte. Trait vert : les plans de même valeur que l'optimum, marqué d'un point rouge.

–

Plan optimal (pommiers ; poiriers)–

Valeur de l'objectif–

Aire de la zone admissible–

Même aire, 40 000 points au hasard–

Contrôle, toutes les intersections de droites : écart–

Famille	Ce qu'elle dit	Forme habituelle	Ici
Ressource	On ne consomme pas plus que ce qu'on a	consommation ≤ stock	3x + 6y ≤ eau disponible
Capacité	L'outil ou le lieu a une limite	activité ≤ capacité	x + y ≤ surface
Budget	Une ressource exprimée en argent	dépense ≤ enveloppe	5x + 3y ≤ budget
Demande	Il faut livrer au moins, ou on ne vend pas plus que	production ≥ commande, ou ≤ marché	x ≥ contrat, y ≤ marché

Quatre expériences. Tout retirer en maximisant : le bénéfice devient infini, signe qu'il manque une contrainte. Minimiser le coût sans le contrat : la meilleure décision est de ne rien planter, résultat exact d'un modèle mal posé. Monter le contrat à 90 ha : la zone disparaît, le problème n'a plus de solution. Observer la liste : une contrainte saturée décide de l'optimum, les autres ont une marge et n'influencent rien tant qu'elles ne sont pas atteintes.

Planche 4

Modèles déterministes et modèles intégrant l'incertitude

Un modèle est déterministe si toutes ses données sont supposées connues : même décision, même résultat. C'est simple et souvent suffisant. Mais si la demande est incertaine, il faut dire ce qu'on en sait et ce qu'on redoute. Prenons un produit à la demande moyenne de 100 : vendu, il rapporte une marge ; invendu, il fait perdre de l'argent. Combien en fabriquer ? La réponse dépend de la façon d'écrire le problème.

Orange pointillé : le profit que croit obtenir le modèle déterministe, qui remplace la demande par sa moyenne. Bleu : le profit moyen réel, compte tenu du hasard. Lettres : les quantités choisies par chaque méthode du tableau.

Les semaines défilent. Chaque point qui tombe est une demande tirée au hasard, rouge si elle dépasse la quantité fabriquée (rupture). Trait noir : la quantité de la méthode sélectionnée (cliquez sur une ligne du tableau pour en changer). Courbe : la loi supposée.

Incertitude sur la demande (écart-type σ)

Marge par produit vendu

Perte par produit invendu

Niveau de service exigé (méthode C)

Profit promis par le modèle déterministe–

Profit moyen réel de ce même plan–

Meilleur profit moyen possible–

Contrôle de B : recherche numérique du maximum, écart sur la quantité–

Contrôle de la méthode sélectionnée : formule / 200 000 tirages–

Semaines animées : profit moyen observé–

Le piège de la moyenne. Remplacer une donnée incertaine par sa moyenne ne donne pas le résultat moyen : le profit moyen est toujours inférieur au profit calculé à la demande moyenne, car une demande plus forte que prévu ne rapporte rien de plus si le stock est épuisé, tandis qu'une demande plus faible laisse des invendus. Mettez σ à 0 : les cinq méthodes coïncident. Augmentez-le : elles divergent, et aucune n'a tort. Elles ne répondent pas à la même question, et c'est au décideur de dire laquelle est la sienne.

Ce qu'on sait	Modèle adapté	Prix à payer
Les données varient peu, ou la décision se corrige facilement	Déterministe, avec une analyse de sensibilité	Risque de sous-estimer l'aléa
On connaît la loi, ou on a un bon historique	Stochastique : optimiser l'espérance, sur des scénarios	Plus de données et de calcul ; le résultat dépend de la loi
Un échec coûte très cher (sécurité, service public)	Contrainte en probabilité : « respectée 95 fois sur 100 »	Rendement moyen moindre
On ne connaît qu'une fourchette, pas de loi fiable	Robuste : se protéger du pire cas, ou du pire regret	Plan parfois très prudent

Planche 5

L'exemple complet : combien de pralines et de tablettes ?

Reprenons la chocolaterie de l'introduction : deux produits, des ressources limitées. Suivez la construction du modèle ligne après ligne, jusqu'à la solution, puis laissez entrer l'incertitude.

→→→→→

Variablesx, y ≥ 0 : caisses de pralines et de tablettes

Objectifmaximiser

Heures de travail

Cacao

Demandex ≤ 35 et y ≤ 50

Incertitudeheures et demandes deviennent aléatoires

Heures de travail disponibles

Cacao disponible

Marge d'une caisse de pralines

Marge d'une caisse de tablettes

–

Votre plan (cliquez sur la figure)–

Sa marge–

Heures utilisées–

Cacao utilisé–

Optimum avec des fractions de caisse–

Optimum en caisses entières–

Contrôle : intersections de droites, écart / plans entiers examinés–

Une heure de plus rapporte–

Un kilo de cacao de plus rapporte–

Ce qu'il faut garder

Trois questions

Sur quoi ai-je la main ? Selon quoi je juge ? Qu'est-ce qui m'empêche ? Les réponses donnent les variables, l'objectif et les contraintes. Chaque quantité du modèle doit se calculer à partir des variables.

Une quatrième question

Que sais-je vraiment des données ? Si elles sont sûres, le modèle déterministe suffit. Sinon, il faut dire ce que l'on sait : une loi, une fourchette, un niveau de risque accepté.

Un réflexe

Une réponse absurde est un signal utile. « Ne rien faire » ou « gagner l'infini » signifie qu'il manque une contrainte. « Pas de solution » signifie qu'on en demande trop. Le calcul dit vrai : c'est l'écriture qu'il faut revoir.

Cinq erreurs de modélisation fréquentes

Erreur	Symptôme	Remède
Prendre un résultat pour une variable	Deux variables liées par une égalité	Ne garder que ce que l'on choisit vraiment
Mélanger les unités	Des heures additionnées à des minutes, des caisses à des kilos	Écrire l'unité de chaque terme de chaque ligne
Oublier une contrainte	Solution infinie, nulle, ou inapplicable sur le terrain	Montrer la solution à ceux qui devront l'appliquer
Confondre objectif et contrainte	On optimise le délai alors qu'il suffisait de le tenir	Demander : faut-il le meilleur, ou simplement assez bon ?
Oublier le hasard	Résultats toujours inférieurs à ce qui était annoncé	Simuler le plan avant de le croire

Pour aller plus loin

Une fois le problème écrit, il reste à le résoudre. Ce cahier poursuit avec Introduction à la recherche opérationnelle (la démarche d'une étude), La recherche opérationnelle (le simplexe et les prix duaux), Le problème du sac à dos (variables binaires), Le problème d'affectation, Décision sous incertitude et programmation stochastique (vendeur de journaux, valeur de la prévision) et Décider avec des probabilités imprécises (quand même la loi est mal connue).

Sur les calculs. Planche 4 : demande normale, profit moyen par la formule de la perte normale, confronté à une intégration numérique et à la simulation ; la petite probabilité d'une demande négative est négligée. Les méthodes robustes utilisent la fourchette μ ± 2σ. Planche 5 : les heures suivent une loi normale d'écart-type égal à la moitié de celui de la demande, en pourcentage ; si les heures manquent, les deux productions sont réduites dans la même proportion, sans frais supplémentaires ; une caisse invendue perd 9 € (pralines) ou 6 € (tablettes). Le plan « avec incertitude » est le meilleur plan en caisses entières sur 600 scénarios, puis jugé sur 20 000 autres.