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.

• Les tolérances de composition pour le médicament fabriqué conduisent, en proportion, à au moins 35% de constituant A et 55% de B. Les coûts des autres éléments entrant dans la fabrication sont tenus pour négligeables.
  

• On doit traiter les produits A et B au moyen de deux appareils qui ne peuvent fonctionner (chacun) plus de 50 heures par semaine.
  

• Pour A, il faut utiliser la première machine pendant 2 heures et la seconde pendant 1 heure.
  
• Pour B, on utilise la première machine pendant 1 heure et la seconde pendant 2 heures.
  
• La législation sur les médicaments impose une restriction des livraisons en A et B :
  au total, 32 litres par semaine.
• Pour la fabrication, les constituants A et B sont achetés respectivement 40 F et 70 F le litre.
  
• Le produit fini (le médicament obtenu) est vendu 20 F en flacons contenant 10 cl de mélange.

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 :

le bénéfice brut hebdomadaire est :

 ➔  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).

• Sur une droite c'est un segment;

• Dans le plan, c'est un triangle (ce sont des cas limites eu égard au vocabulaire polyèdre);

• Dans l'espace usuel, le simplexe est le tétraèdre : objet polyédrique le plus élémentaire.