Optimisation linéaire d'un objectif sur un polygone

Terminale Technologique · Mathématiques STMG Terminale

À retenir

• Un objectif linéaire s'écrit z = cx + dy ; il est à maximiser ou à minimiser. • L'ensemble de niveau cx + dy = k est une droite : toutes ces droites sont parallèles. • Optimiser, c'est pousser la droite de niveau jusqu'au dernier contact avec le polygone réalisable. • Si la droite de niveau est parallèle à un côté, il y a une infinité d'optimums.

Le cours

1. Un objectif, des contraintes, un optimum Optimiser, c'est choisir un programme réalisable qui rend une grandeur aussi bonne que possible. La grandeur à optimiser s'appelle l'objectif et s'écrit z = cx + dy. L'atelier cherche à maximiser sa marge, ou à minimiser son coût : dans les deux cas la méthode est identique. • Objectif de maximisation (marge, chiffre d'affaires, production totale) : on veut z le plus grand possible. • Objectif de minimisation (coût, temps passé, matière consommée) : on veut z le plus petit possible. • Un objectif est linéaire si z est une combinaison des variables sans exposant : z = 5x + 8y est linéaire. 2. Les droites de niveau : la représentation qui décide L'ensemble des points où l'objectif vaut une valeur donnée k est l'ensemble de niveau, c'est-à-dire la droite d'équation 5x + 8y = k et toutes ces droites sont parallèles entre elles : optimiser consiste à pousser une droite de niveau vers le haut (ou vers le bas) jusqu'au dernier contact avec le polygone. • Tracer z = 100, puis z = 200 : elles sont parallèles, plus on augmente k, plus la droite monte. • Pour un maximum, on retient la dernière droite qui touche encore le polygone quand on la pousse vers le haut ; pour un minimum, la première qui le touche en partant du bas. Droite de niveauÉquationTest en un point du polygoneConclusion z = 05x + 8y = 0O : 0 = 0passe par l'origine z = 3145x + 8y = 314C = (18\,;\,28) : 90 + 224 = 314touche le polygone en C z = 3205x + 8y = 320D = (0\,;\,40) : 320contact final : maximum 3. Ce qui se passe quand la droite de niveau est parallèle à un côté Si la droite de niveau est parallèle à un côté du polygone, elle peut toucher tout un segment : il y a alors une infinité d'optimums. Ce cas n'est pas une erreur, c'est un résultat, et il signale une situation où deux programmes valent autant l'un que l'autre. • Si les coefficients de l'objectif sont proportionnels à ceux d'une contrainte qui borde le polygone du côté de l'optimum, tout ce côté est optimal. • Deux programmes sont alors équivalents : l'atelier est indifférent entre eux.

Dans ce chapitre