Techniques et concepts de l'entreprise, de la finance et de l'économie 
(et fondements mathématiques)

Une introduction à la programmation linéaire

logo

 

 

 

 

 

 

 

 

 

 

Régionnement du plan par fonctions affines

Les techniques d’optimisation sous contrainte(s) ! Très vaste sujet ! Qu’il s’agisse de trouver une meilleure combinaison d’actions à investir ou de produits à fabriquer, nous voici sur l’un des terrains favoris des mathématiques appliquées. Cette page n’est qu’une introduction. Son niveau est celui d'une terminale STMG (Sciences et Technologies du Management et de la Gestion) ou jadis d'une première ES spécialité maths.

Régionnement du plan

Nous savons tous que l'on détermine les points d'intersection de fonctions affines grâce à des systèmes d'équations. Remplaçons les équations par des inéquations, ajoutons une ou des contraintes et bienvenue en programmation linéaire !

Graphiquement, ceci consiste à sélectionner des zones délimitées par des droites.

Ce type d'exercice répond à des problèmes concrets dont la principale difficulté consiste à transcrire les données en inéquations.

Comme aucun ajout théorique n’est nécessaire, passons directement à un exemple qui aura valeur d'explication. Celui que je vous propose est la forme condensée d’un problème donné au bac STG (options M, CFE et GSI), Polynésie, juin 2008.

M. François va ouvrir un marché « puces et brocante » sur son terrain. Il y a délimité 120 emplacements. L’installation des exposants commencera à 6 h, le dernier exposant devra avoir fini de s’installer à 8 h. Il prévoit que chaque exposant arrivant :

- avec une voiture, paiera 10 euros de redevance et disposera de deux emplacements pour installer son stand.

- avec un fourgon, paiera 16 euros de redevance et disposera de trois emplacements.

Il faut en moyenne 1 mn à une voiture pour se garer et 4 mn à un fourgon. Pour des raisons de sécurité, chaque exposant ne peut commencer à se garer que lorsque le précédent a fini de se garer.

M. François souhaite déterminer le nombre de voitures et le nombre de fourgons nécessaires pour que sa recette soit maximale.

Partie A : on note x le nombre de voitures et y le nombre de fourgons. Écrire un système d’inéquations correspondant aux contraintes du problème.

Ça vous inspire ? Une contrainte classique est que x et y sont supérieurs ou égaux à zéro. Ici, nous pouvons ajouter le temps d’installation en minutes : x + 4y ≤ 120.

Quant aux emplacements, on les formalise ainsi : 2x + 3y ≤ 120.

Comme nous allons tracer des droites sur un plan, il est pratique d’isoler y dans le système, d’où :

exemple de système pour optimisation

L’énoncé demandait ensuite une représentation graphique. Ci-dessous, la partie rosée correspond à la zone « possible » (frontières incluses).

exemple de zone possible

La question suivante proposait d’examiner plusieurs combinaisons de voitures et de fourgons. Ainsi, 50 voitures et 20 fourgons constituent une combinaison tout à fait impossible. Aucune des deux inégalités n’est vérifiée. La visite de 30 voitures et 15 fourgons ne pose en revanche aucun problème et on voit bien que le point (30 ; 15) fait partie de la zone rose. Enfin, 24 voitures et 24 fourgons semblent constituer une combinaison acceptable mais le graphique n’étant pas très précis, on s’en assure algébriquement.

Temps d’installation : 24 + (4 × 24) = 120. Emplacements : (2 × 24) + (3 × 24) = 120.

C’est pile poil la combinaison optimale ! Mais patience, ce n’est pas obligatoirement celle qui rapporte le plus d'argent…

Partie B : On note R la recette de la journée. Exprimer R en fonction de x et de y.

Pas la moindre difficulté : R = 10x + 16y.

Montrer que la droite D d’équation y = -(5 / 8)x + 10 correspond à une recette de 160 euros.

On est bien dans un sujet du bac. Dans la réalité, on partirait au contraire d’une recette à atteindre pour déterminer une équation…  Pour l’instant, multiplions les membres de cette équation par 16, et on trouve bien 16y + 10x = 160.

Représenter la droite D dans le repère précédent.

Voir ci-dessous. En x = 0, on sait que y = 10. Par ailleurs, D coupe l’axe des abscisses en -(5 8)x + 10 = 0. Donc en x = 16.

Trouver le couple d’entiers (x ; y) qui permet d’obtenir la recette maximale.

On décale cette droite parallèlement jusqu’au dernier point possible sur la frontière de la zone rose. On retombe alors sur 24 voitures et 24 fourgonnettes (on s’en serait vaguement douté…).

décalage

Calculer alors cette recette maximale et répondre au problème posé.

Et une question enfantine pour le digestif…

(24 × 10 €) + (24 × 16 €) = 624 €. M. François doit accueillir 24 voitures et 24 fourgonnettes pour enregistrer la recette maximale qui s’établit à 624 €.

NB : cet exemple illustre une situation simpliste. L'utilisation concrète des techniques d'optimisation requiert des courbes plutôt que des droites, et les fonctions sont à plusieurs variables...

 

programmeurs

 

© JY Baudot - Droits d'auteur protégés