ChronoMath, une chronologie des MATHÉMATIQUES
à l'usage des professeurs de mathématiques, des étudiants et des élèves des lycées & collèges

Notion de programmation linéaire
     Méthode de Dantzig sur un exemple concret (simplexe élémentaire)

La fabrication d'un produit nécessite le mélange de deux constituants chimiques aux noms gréco-scientifico-latins imprononçables, appelés simplement ici A et B, utilisés par flacons d'une contenance de un litre.

Il s'agit de calculer le nombre de flacons de A et le nombre de flacons de B à utiliser par semaine afin de maximiser le bénéfice brut (on omet d'autres coûts, comme ceux du fonctionnement ou de l'amortissement des machines, du salaire des employés, etc.) sachant que l'ensemble de la production hebdomadaire est vendue et en admettant qu'il n'y a pas de pertes en constituants A et B au cours du traitement.

On note x le nombre de flacons de A et y le nombres de flacons de B cherchés. Vérifier que les conditions posées conduisent aux contraintes :

  • 13x - 7y 0,
    car il faut x 35(x + y)/100.
  • 11x - 9y 0
    car il faut y 55(x + y)/100.

  • x + y 32
  • 2x + y 50
  • x + 2y 50

le bénéfice brut hebdomadaire est :

b = 200(x + y) - 40x - 70y , soit : y = (b - 160x)/130

La zone adéquate (celle qui convient) est déterminée en éliminant les régions non conformes en se basant sur le petit schéma général de droite. Pour chaque condition, il suffit de "tester" un point du plan. S'il convient, toute la région située dans le même demi-plan conviendra. S'il ne convient pas, on choisira, l'autre demi-plan. Généralement, on choisit tout simplement l'origine x = 0, y = 0, sauf si la droite gérant la condition passe par l'origine !

 

La zone colorée en jaune foncé ci-dessous est celle des programmes de fabrication possibles eu égard aux conditions posées.

Le coefficient angulaire de la "droite de bénéfice" est -16/13, son ordonnée à l'origine b/130 doit être la plus grande possible, ce qui conduit, en théorie , au point S(14,4 ; 17,6) intersection ci-dessous des droites d'équations respectives x + y = 32 et 11x - 9y = 0. 

Mais notre problème doit posséder une solution en nombres entiers, par conséquent nous choisirons soit x = 14 et y = 18, voire x = 15 et y = 18 afin de pouvoir procéder à la fabrication optimale (avec quelques restes de produit A et B).

Il est bien évident que le problème ci-dessus a été simplifié à l'extrême et que l'on devrait tenir compte de beaucoup plus de paramètres.

De plus, dans les problèmes économiques, le système d'équations et inéquations contient plus de deux variables. La généralisation se fait cependant aisément et des algorithmes puissants ont été étudiés pour résoudre des problèmes.

Le petit problème étudié ici est un cas particulier de la méthode du simplexe mise au point par Dantzig. Le programme optimum est toujours un point frontière du domaine des solutions possibles : ici à l'intersection de deux droites. Ce point maximise ou minimise une forme linéaire exprimant la grandeur à optimiser (en termes de coût, il s'agirait de minimiser).

En dimension 3, la solution optimale se situe en un des sommets d'un polyèdre (intersection de 3 plans).

En dimension n>3, on obtient un "hyperpolyèdre" et le programme optimum est à l'intersection de n hyperplans : en géométrie, dans un espace vectoriel ou affine de dimension n, on appelle ainsi un sous-espace de dimension n-1.

Quand on "se promène" sur les arêtes d'un polyèdre, on dit être sur un simplexe : dans un espace de dimension n, un simplexe est le polyèdre le plus élémentaire (le plus "simple"). Il est constitué de n + 1 points (ses sommets), c'est l'enveloppe convexe de ces points et en tant que tel, au lieu de hyperpolyèdre, on parle plutôt de polytope (appellation d'Alicia Boole Stott).


© Serge Mehl - www.chronomath.com