Méthode des sommets pour rechercher un optimum

Terminale Technologique · Mathématiques STMG Terminale

À retenir

• Sur un polygone (région bornée et non vide), le maximum et le minimum d'un objectif linéaire sont atteints en au moins un sommet. • La méthode des sommets : système complet, liste des sommets, évaluation de z en chacun, comparaison. • Maximum et minimum ne se classent pas de la même façon : le sens de l'optimisation doit être écrit d'abord. • Contrôle final obligatoire : coordonnées entières et cohérence avec les ressources.

Le cours

1. Pourquoi l'optimum est toujours un sommet Sur un côté du polygone, l'objectif varie linéairement : le maximum et le minimum y sont donc atteints à une extrémité. Comme tous les côtés sont eux-mêmes reliés aux sommets, un optimum sur le bord se trouve toujours en un sommet. Un point intérieur, lui, peut toujours être amélioré en se déplaçant dans le sens du gradient : il n'est jamais optimal. • Le long d'un segment, z est une fonction affine de la position : son extremum est à un bout. • Le bord du polygone est une réunion de segments : l'optimum du bord est un sommet. • Un point intérieur n'est jamais optimal, car le gradient permet toujours de monter. • Il suffit donc d'évaluer z en un nombre fini de points : les sommets. SommetProgramme (x\,;\,y)z = 5x + 8yContraintes saturéesRang O(0\,;\,0)0x = 0, y = 04 A(25\,;\,0)5 25 = 1254x+y = 100, y = 03 C(18\,;\,28)90 + 224 = 3142x+3y=120, 4x+y=1002 D(0\,;\,40)8 40 = 3202x+3y=120, x = 01 2. La méthode des sommets, étape par étape La procédure est courte, mais son ordre est impératif : un sommet oublié fausse la conclusion, et une valeur calculée sur un point non réalisable est sans valeur. • 1. Écrire le système complet, positivité comprise, et vérifier que la région est bornée. • 2. Déterminer les sommets : axes, puis croisements de frontières, chaque point étant testé dans toutes les inéquations. • 3. Évaluer z en chaque sommet, en une seule ligne de calcul. • 4. Comparer : la plus grande valeur pour un maximum, la plus petite pour une minimisation. 3. Ce qui fait échouer la méthode Les erreurs suivantes donnent toutes une réponse plausible mais fausse : elles se gagnent en allant trop vite, jamais par un calcul difficile. • Confondre le signe du classement : en minimisation, c'est la plus petite valeur qui gagne. • Oublier la positivité et évaluer un sommet situé hors du premier quadrant.

Dans ce chapitre