Aller au contenu
Recherche opérationnelle · L2

Leçon 1 sur 5

Modéliser un problème d'optimisation

Je sais traduire un problème de gestion (production, mélange, ration) en programme linéaire : variables de décision, fonction objectif et contraintes.

  • 1 h
  • 4 exercices corrigés
  • QCM de 5 questions

À la fin de la leçon, vous saurez :

  • Identifier les variables de décision d'un problème
  • Écrire la fonction objectif à maximiser ou minimiser
  • Traduire les ressources et exigences en contraintes linéaires
  • Vérifier les hypothèses de la programmation linéaire et tester si une solution est réalisable

Avant de commencer : Algèbre de L1 : équations et inéquations du premier degré, systèmes linéaires.

1Je découvre

L'atelier de menuiserie de Mamadou, à Kindia, fabrique des tabourets et des tables basses. Chaque tabouret rapporte une marge de 30 000 GNF, chaque table basse 40 000 GNF. Mais les heures de travail sont limitées : chaque semaine, l'atelier dispose de 16 heures de menuiserie et de 14 heures de finition. Un tabouret demande 2 heures de menuiserie et 1 heure de finition ; une table basse, 1 heure de menuiserie et 2 heures de finition. Enfin, les clients n'achètent pas plus de 6 tables basses par semaine.

Mamadou hésite : faut-il produire surtout des tables basses, plus rentables à l'unité, ou des tabourets, qui demandent moins de finition ? En essayant au hasard, il risque de laisser de l'argent sur la table.

Comment écrire ce problème sous une forme mathématique qui permette de trouver la meilleure décision ?

2Je comprends

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

La recherche opérationnelle (RO) regroupe des méthodes mathématiques d'aide à la décision : répartir des ressources limitées, organiser des transports, planifier des tâches. Son outil de base est la programmation linéaire : optimiser (maximiser ou minimiser) une fonction linéaire sous des contraintes linéaires.

La démarche comporte trois temps : modéliser (cette leçon), résoudre (méthode graphique, simplexe), interpréter (dualité, sensibilité).

2. Les trois éléments d'un programme linéaire

Les variables de décision : ce que le décideur choisit. Il faut les définir avec précision, unité et période comprises.

  • x = nombre de tabourets fabriqués par semaine ;
  • y = nombre de tables basses fabriquées par semaine.

La fonction objectif : ce que l'on cherche à maximiser (marge, recette) ou minimiser (coût, distance). En milliers de GNF :

max Z = 30x + 40y

Les contraintes : les limites imposées par les ressources, le marché, la technique.

  • menuiserie : 2x + y ≤ 16 ;
  • finition : x + 2y ≤ 14 ;
  • demande : y ≤ 6 ;
  • non-négativité : x ≥ 0, y ≥ 0.

Méthode pour une contrainte de ressource : consommation totale ≤ disponibilité. On écrit le membre de gauche en additionnant, pour chaque produit, la consommation unitaire multipliée par la quantité.

Il est souvent utile de résumer les données dans un tableau avant d'écrire le modèle :

Tabouret (x)Table basse (y)Disponible
Menuiserie (h)2116
Finition (h)1214
Marge (milliers GNF)3040

3. Les hypothèses de la programmation linéaire

Le modèle suppose :

  • la proportionnalité : doubler la production double la marge et la consommation de ressources (pas de remise sur quantité, pas d'économies d'échelle) ;
  • l'additivité : la marge totale est la somme des marges de chaque produit ; les consommations s'additionnent ;
  • la divisibilité : les variables peuvent prendre des valeurs non entières. Si le résultat doit être entier (on ne vend pas 3,5 tables), on parle de programmation linéaire en nombres entiers, plus difficile ;
  • la certitude : les coefficients (marges, temps, disponibilités) sont connus.

Ces hypothèses sont des simplifications : il faut les garder en tête au moment d'interpréter.

4. Un problème de minimisation : la ration

Un éleveur de Labé veut nourrir ses bœufs avec deux aliments : le tourteau (A) et le son de riz (B). Un sac de A coûte 120 000 GNF et apporte 4 unités de protéines et 2 unités d'énergie ; un sac de B coûte 60 000 GNF et apporte 1 unité de protéines et 3 unités d'énergie. Il lui faut au moins 12 unités de protéines et 18 unités d'énergie par semaine.

Variables : a = sacs de tourteau, b = sacs de son par semaine.

min C = 120a + 60b (en milliers de GNF)

sous les contraintes :

  • protéines : 4a + b ≥ 12 ;
  • énergie : 2a + 3b ≥ 18 ;
  • a ≥ 0, b ≥ 0.

Ici, les contraintes sont des exigences minimales : « apport total ≥ besoin ».

5. Solution réalisable, solution optimale

  • Une solution réalisable respecte toutes les contraintes.
  • L'ensemble des solutions réalisables (ou domaine réalisable) est l'ensemble de ces points.
  • Une solution optimale est une solution réalisable qui donne la meilleure valeur de l'objectif.

Exemple pour l'atelier : le plan (x, y) = (5, 4) est-il réalisable ?

  • menuiserie : 2 × 5 + 4 = 14 ≤ 16 ✓ ;
  • finition : 5 + 2 × 4 = 13 ≤ 14 ✓ ;
  • demande : 4 ≤ 6 ✓.

Il est réalisable et rapporte Z = 30 × 5 + 40 × 4 = 310, soit 310 000 GNF. Il reste 2 heures de menuiserie et 1 heure de finition inutilisées : ce sont des écarts (ou variables d'écart). On peut sans doute faire mieux… ce que nous verrons dans les leçons suivantes.

Le plan (7, 4), lui, n'est pas réalisable : 2 × 7 + 4 = 18 > 16.

3Je retiens

Je retiens

Un programme linéaire = variables de décision + fonction objectif + contraintes linéaires.

Définir chaque variable avec son unité et sa période (« nombre de tables par semaine »).

Contrainte de ressource : consommation totale ≤ disponibilité ; exigence : apport total ≥ besoin.

Ne jamais oublier les contraintes de non-négativité.

Hypothèses : proportionnalité, additivité, divisibilité, certitude.

Une solution est réalisable si elle respecte toutes les contraintes ; l'optimale est la meilleure d'entre elles.

4Erreurs fréquentes

  • Prendre comme variable une ressource (« heures ») au lieu de la décision (« quantité produite »).
  • Inverser le sens d'une contrainte : une disponibilité donne ≤, un besoin minimal donne ≥.
  • Mélanger les unités (marge en GNF dans un modèle, milliers de GNF dans un autre) : fixer une unité et s'y tenir.
  • Oublier la contrainte de marché ou de non-négativité, ce qui donne des solutions absurdes.
  • Multiplier les quantités entre elles (xy) : le modèle n'est plus linéaire.

5Je m’exerce

1Exercice 1

(Questions de cours) a) Quels sont les trois éléments d'un programme linéaire ? b) Que signifie l'hypothèse de divisibilité ? c) Quelle différence entre solution réalisable et solution optimale ?

Voir le corrigéCacher le corrigé

a) Des variables de décision, une fonction objectif (à maximiser ou minimiser) et des contraintes linéaires (y compris la non-négativité). b) Les variables peuvent prendre des valeurs non entières (par exemple 2,5 unités). c) Une solution réalisable respecte toutes les contraintes ; la solution optimale est, parmi les solutions réalisables, celle qui donne la meilleure valeur de l'objectif.

2Exercice 2

Une coopérative de femmes de Mamou transforme du fonio en deux produits : du fonio précuit (marge 15 000 GNF le sachet) et des galettes (marge 10 000 GNF le paquet). Un sachet demande 0,5 kg de fonio et 1 heure de travail ; un paquet de galettes demande 0,25 kg de fonio et 1 heure de travail. Chaque semaine, la coopérative dispose de 40 kg de fonio et de 100 heures de travail. Elle ne peut pas vendre plus de 60 paquets de galettes par semaine. Écrivez le programme linéaire.

Voir le corrigéCacher le corrigé

Variables : x = sachets de fonio précuit par semaine, y = paquets de galettes par semaine. En milliers de GNF : max Z = 15x + 10y sous les contraintes : fonio 0,5x + 0,25y ≤ 40 ; travail x + y ≤ 100 ; marché y ≤ 60 ; x ≥ 0, y ≥ 0. (On peut multiplier la contrainte de fonio par 4 : 2x + y ≤ 160.)

3Exercice 3

Pour l'éleveur de la partie 4, vérifiez si les rations suivantes sont réalisables et calculez leur coût : a) (a, b) = (2, 5) ; b) (a, b) = (3, 4) ; c) (a, b) = (1, 6).

Voir le corrigéCacher le corrigé

a) Protéines : 4 × 2 + 5 = 13 ≥ 12 ✓ ; énergie : 2 × 2 + 3 × 5 = 19 ≥ 18 ✓. Réalisable ; coût 120 × 2 + 60 × 5 = 540, soit 540 000 GNF. b) Protéines 12 + 4 = 16 ✓ ; énergie 6 + 12 = 18 ✓. Réalisable ; coût 360 + 240 = 600, soit 600 000 GNF. c) Protéines 4 + 6 = 10 < 12 ✗ : non réalisable (la ration manque de protéines), même si son coût (480 000 GNF) est plus faible.

4Exercice 4

(Type examen) Une entreprise de Boké livre du ciment à partir de deux dépôts, D1 (60 tonnes disponibles) et D2 (40 tonnes), vers trois chantiers C1, C2, C3 qui demandent respectivement 30, 45 et 25 tonnes. Le coût de transport par tonne (en milliers de GNF) est : de D1 vers C1, C2, C3 : 8, 6, 10 ; de D2 vers C1, C2, C3 : 9, 12, 7. a) Définissez les variables de décision. b) Écrivez la fonction objectif. c) Écrivez les contraintes d'offre, de demande et de non-négativité. d) Vérifiez que le plan « D1 envoie 15 t à C1 et 45 t à C2 ; D2 envoie 15 t à C1 et 25 t à C3 » est réalisable et calculez son coût. e) Combien de variables et de contraintes (hors non-négativité) compte le modèle ?

Voir le corrigéCacher le corrigé

a) xij = tonnes transportées du dépôt i vers le chantier j, avec i = 1, 2 et j = 1, 2, 3 : six variables. b) min C = 8x11 + 6x12 + 10x13 + 9x21 + 12x22 + 7x23 (milliers de GNF). c) Offre : x11 + x12 + x13 ≤ 60 ; x21 + x22 + x23 ≤ 40. Demande : x11 + x21 = 30 ; x12 + x22 = 45 ; x13 + x23 = 25 (on peut écrire ≥). Non-négativité : xij ≥ 0. Comme l'offre totale (100 t) égale la demande totale (100 t), les contraintes d'offre seront saturées. d) D1 envoie 15 + 45 = 60 ≤ 60 ✓ ; D2 envoie 15 + 25 = 40 ≤ 40 ✓ ; C1 reçoit 15 + 15 = 30 ✓ ; C2 reçoit 45 ✓ ; C3 reçoit 25 ✓. Coût : 8 × 15 + 6 × 45 + 9 × 15 + 7 × 25 = 120 + 270 + 135 + 175 = 700, soit 700 000 GNF. e) Six variables et cinq contraintes (deux d'offre, trois de demande).

Cherchez d’abord seul, sur votre cahier, puis ouvrez le corrigé pour comparer.

6Je vérifie

Choisissez une réponse pour chaque question : la correction s’affiche aussitôt.

1Dans le problème de l'atelier, la variable de décision x est :
Voir la réponse

Réponse B : le nombre de tabourets fabriqués par semaine. On choisit les quantités à produire ; les heures sont des ressources.

2Une disponibilité de 16 heures se traduit par une contrainte :
Voir la réponse

Réponse A : de type ≤. On ne peut pas consommer plus que ce qui est disponible.

3Laquelle de ces fonctions n'est pas linéaire ?
Voir la réponse

Réponse C : Z = 4xy. Le produit de deux variables rend le modèle non linéaire.

4Le plan (x, y) = (6, 4) de l'atelier (2x + y ≤ 16 ; x + 2y ≤ 14 ; y ≤ 6) est :
Voir la réponse

Réponse A : réalisable. 12 + 4 = 16 ; 6 + 8 = 14 ; 4 ≤ 6 : toutes les contraintes sont respectées.

5L'hypothèse de proportionnalité signifie que :
Voir la réponse

Réponse B : la contribution de chaque produit est proportionnelle à sa quantité. Pas de remise sur quantité ni d'économies d'échelle dans le modèle.

Karamö, votre enseignant

Il a lu cette leçon. Posez-lui votre question : il vous répond ici.

Connectez-vous pour poser vos questions à Karamö.

Vous avez fini la leçon ?

Avec un compte Kharandi gratuit, vous cochez les leçons terminées et vous suivez votre progression, cours par cours.

Karamö
Un point pas clair ? Dites à Karamö ce qui vous bloque dans cette leçon : il vous l’explique autrement, pas à pas, sans faire le travail à votre place. Demander à Karamö
Signaler une erreur dans cette leçon

Toutes les leçons de Recherche opérationnelle

Pose ta question à Karamö