Math CST, secondaire 5 à Montréal • Optimisation

Fiche de révision : l'optimisation par programmation linéaire

En mathématiques CST de cinquième secondaire, l'optimisation par programmation linéaire est la question la plus prévisible de l'épreuve : le contexte change, la méthode jamais. Presque tous les points perdus le sont sur trois gestes, la traduction d'une phrase en inéquation, le filtrage des sommets et la phrase de conclusion.

Cette fiche ne réexplique pas le cours. Elle dit où partent les points et quel geste exact les garde.

Le fil du chapitre

Le polygone dit ce qui est POSSIBLE, la fonction dit ce qui est MEILLEUR. L'optimum est toujours sur un SOMMET du polygone, et la réponse finale doit être une solution qu'on peut vraiment réaliser.

Ce chapitre fait partie de Mathématique CST, secondaire 5

Avant ce chapitre

Cette fiche suppose ces notions acquises. Si une méthode ci-dessous reste opaque, c'est presque toujours l'une d'elles qui manque, pas la fiche.

Les systèmes d'équationsSecondaire 4 CST Fiche

Remonter plus loin : la chaîne complète (5 chapitres) ↓

Le chemin de remédiation, du plus ancien au plus proche. Un élève qui reprend ce chapitre de zéro le reprend dans cet ordre.

1Nombres réels, racines et ensemblesSecondaire 3
2Expressions algébriques et mise en évidenceSecondaire 3
3Équations et inéquations du premier degréSecondaire 3
4Systèmes d'équations : comparaison et graphiqueSecondaire 3
5Les systèmes d'équationsSecondaire 4 CST

L'essentiel

Les quatre gestes, toujours dans cet ordre

• TRADUIRE : chaque phrase de l'énoncé devient une inéquation, et on ajoute les deux contraintes de positivité $x\ge 0$ et $y\ge 0$ , qui ne sont écrites nulle part.
• TRACER ET RELEVER : on trace les frontières, on colorie la région, et on relève ses SOMMETS. Un sommet est l'intersection de deux frontières QUI APPARTIENT à la région.
• ÉVALUER : on calcule la fonction à optimiser à chaque sommet, dans un tableau à deux colonnes.
• RÉPONDRE : on écrit une phrase avec les mots de l'énoncé, les unités, et la valeur optimale. Le sommet seul n'est pas une réponse.

Les deux droites en pointillé donnent la même fonction

P=5x+4y

pour deux valeurs. En glissant vers le haut, la dernière touchée est le sommet

(6\,;3)

, où

P=42

La fonction à optimiser ne fait PAS partie du système : elle ne trace aucune frontière et ne change jamais le polygone.

La règle des sommets, et la droite baladeuse

• RÈGLE DES SOMMETS : une fonction de la forme $ax+by$ atteint son maximum et son minimum sur un SOMMET du polygone. On ne teste donc jamais l'intérieur de la région.
• DROITE BALADEUSE : tous les points de la droite $ax+by=k$ donnent la même valeur $k$ . Sa pente vaut $-\dfrac{a}{b}$ et ne dépend QUE de la fonction à optimiser. On la fait glisser parallèlement à elle-même ; le dernier sommet touché est l'optimum.
• Changer la fonction ne change pas le polygone : mêmes contraintes, mêmes sommets, seule la table des valeurs est à refaire. Le sommet gagnant, lui, peut changer.
• Une contrainte SATURÉE à l'optimum est une ressource entièrement utilisée. Une contrainte REDONDANTE ne retire aucun point à la région. Une région VIDE signale des exigences incompatibles : on nomme alors la contrainte qui bloque.

Une région non bornée peut avoir un minimum sans avoir de maximum. On le dit dans la conclusion plutôt que d'inventer un sommet.

Les pièges qui coûtent des points

Les erreurs ci-dessous sont celles que je corrige le plus souvent en séance. Chacune coûte des points sur une copie, même quand le raisonnement est juste.

1. Mettre dans le tableau une intersection qui n'est pas dans la région

toute la question, car l'optimum tombe presque toujours sur ce point fantôme

Ce qu'il ne faut pas écrire

« Les droites $x+2y=12$ et l'axe des $x$ se coupent en $(12\,;0)$ , donc $(12\,;0)$ est un sommet. »

Ce qu'il faut écrire

« $(12\,;0)$ donne $3\times 12+2\times 0=36>24$ : il est hors de la région, ce n'est pas un sommet. »

Les deux prolongements en pointillé rencontrent les axes en

(12\,;0)

(0\,;12)

, tous deux à l'extérieur de la zone colorée : ce ne sont pas des sommets.

Pourquoi : Une intersection n'est un sommet que si elle respecte TOUTES les contraintes, pas seulement les deux qui l'ont produite. Le filtre est mécanique : une ligne de calcul par contrainte restante.

2. Oublier les contraintes de positivité

1 à 2 points, et une région ouverte qui donne des sommets inexistants

Ce qu'il ne faut pas écrire

« L'énoncé ne parle pas de nombres négatifs, donc le système est $x+y\le 60$ et $y\ge 15$ . »

Ce qu'il faut écrire

« On ajoute toujours $x\ge 0$ et $y\ge 0$ : on ne fabrique pas un nombre négatif de plateaux. »

Pourquoi : Ces deux contraintes ferment la région du côté des axes. Sans elles, le polygone n'est plus borné et la table des sommets est fausse dès la première ligne.

3. Inverser un rapport du type deux fois plus

toute la modélisation, donc l'exercice entier

Ce qu'il ne faut pas écrire

« Il faut au moins deux fois plus de chaises que de tables, donc $2y\ge x$ . »

Ce qu'il faut écrire

« Avec $10$ tables, il faut au moins $20$ chaises : le couple $(10\,;20)$ doit passer, donc $y\ge 2x$ . »

Pourquoi : La traduction mot à mot trompe parce que le mot « double » est collé au mauvais nom dans la phrase. Un exemple chiffré tranche en dix secondes et ne se trompe jamais.

4. Simplifier une inéquation à moitié

toute la question, et l'erreur est invisible, car la région reste plausible

Ce qu'il ne faut pas écrire

« $20x+30y\le 1500$ donne $2x+3y\le 1500$ . »

Ce qu'il faut écrire

« On divise LES TROIS termes par $10$ : $2x+3y\le 150$ . »

Pourquoi : Une inéquation se divise comme une équation, des deux côtés. Le contrôle : reprendre un point évident, ici $(0\,;50)$ , et vérifier qu'il donne la même réponse dans les deux écritures.

5. Arrondir un sommet optimal décimal

2 points, et souvent la réponse finale du problème

Ce qu'il ne faut pas écrire

« L'optimum est en $(4{,}5\,;2{,}5)$ , donc l'artisan fabrique $5$ lampes et $3$ horloges. »

Ce qu'il faut écrire

« $(5\,;3)$ donne $x+y=8>7$ : impossible. La meilleure production entière est $(4\,;3)$ , pour $580$ dollars. »

Pourquoi : Arrondir n'est pas une méthode : le point arrondi sort très souvent de la région. La meilleure solution entière est toujours sur un bord, donc on la cherche en longeant le bord actif.

6. Tester des points au hasard dans la région

rarement tous les points, mais une réponse fausse une fois sur deux et beaucoup de temps

Ce qu'il ne faut pas écrire

« J'ai essayé $(3\,;3)$ , $(4\,;2)$ et $(5\,;1)$ , le meilleur est $(5\,;1)$ . »

Ce qu'il faut écrire

« La règle des sommets garantit que l'optimum est sur un sommet : j'évalue les quatre sommets et eux seuls. »

Pourquoi : La région contient une infinité de points et on ne peut pas tous les tester. D'un point intérieur, on peut toujours avancer vers un bord et faire croître la fonction : l'optimum ne peut donc pas être à l'intérieur.

7. Confondre le trait plein et le pointillé

1 point, et un optimum déclaré non atteint alors qu'il l'est

Ce qu'il ne faut pas écrire

« Une contrainte du type au plus se trace en pointillé, puisqu'on ne peut pas dépasser. »

Ce qu'il faut écrire

« $\le$ est une inégalité LARGE : trait plein, bord inclus. Le pointillé est réservé à $<$ et $>$ . »

Pourquoi : C'est le caractère strict ou large de l'inégalité qui décide du trait, pas le sens de la comparaison. Comme l'optimum se trouve sur un sommet, donc sur le bord, un bord exclu changerait complètement la conclusion.

8. S'arrêter au sommet sans répondre à la question

1 à 2 points de communication, systématiquement retirés à l'épreuve unique

Ce qu'il ne faut pas écrire

« L'optimum est $(10\,;10)$ . »

Ce qu'il faut écrire

« La municipalité embauche $10$ moniteurs et $10$ aides-moniteurs, pour un coût minimal de $9500$ dollars par semaine. »

Pourquoi : Un couple de nombres n'est pas une réponse : l'énoncé parlait d'employés et de dollars. La phrase de conclusion reprend les mots du contexte, les unités et la valeur optimale.

Quelle méthode choisir

Que faire selon ce que l'énoncé vous donne

On regarde sous quelle FORME arrivent les contraintes, puis ce que la question demande exactement.

Si Un texte, avec des ressources et des limites → traduire phrase par phrase, ajouter $x\ge 0$ et $y\ge 0$ , puis écrire la fonction à part

Exemple : « au plus $60$ plateaux » donne $x+y\le 60$

vérifier chaque rapport du type double ou moitié avec un exemple chiffré
Si Une région déjà tracée → lire les sommets sur le quadrillage, et retrouver chaque frontière par sa pente et son ordonnée à l'origine

Exemple : un bord joignant $(7\,;0)$ à $(2\,;5)$ a pour équation $x+y=7$

trait plein, inégalité large ; trait pointillé, inégalité stricte
Si Un système d'inéquations → calculer les intersections deux à deux, puis FILTRER celles qui ne respectent pas toutes les contraintes

Exemple : quatre contraintes donnent six intersections et souvent quatre sommets

c'est l'étape où se perd le plus de points de toute la question
Si Les variables comptent des objets ou des personnes → chercher le meilleur point ENTIER admissible en longeant le bord actif

Exemple : l'optimum $(4{,}5\,;2{,}5)$ n'est pas réalisable, $(4\,;3)$ l'est

l'optimum décimal reste une BORNE que la réponse réelle ne dépassera pas
Si Deux exigences se contredisent → montrer que la région est vide et nommer la contrainte qui bloque

Exemple : $x\ge 12$ , $y\ge 20$ et $x+y\le 30$ : impossible, car $12+20=32$

une bonne réponse chiffre ce qu'il faudrait relâcher, ici deux places

Si la fonction à optimiser change en cours de problème, on ne retrace RIEN : on refait seulement la table des valeurs aux mêmes sommets.

La rédaction attendue

Le correcteur coche des étapes. Les voici dans l'ordre, avec la phrase de conclusion qu'il attend mot pour mot.

Résoudre un problème d'optimisation en entier

Quand l'utiliser : L'énoncé décrit une situation avec deux quantités à choisir, des limites, et demande le maximum ou le minimum de quelque chose.

1 Définir les deux variables en une phrase, avec leur unité : « soit $x$ le nombre de... ».
2 Écrire le système de contraintes, positivité comprise, et simplifier chaque inéquation.
3 Écrire la fonction à optimiser À PART du système, et dire si on la maximise ou la minimise.
4 Donner les sommets, chacun justifié par les deux frontières qui le produisent et vérifié dans les autres contraintes.
5 Dresser la table des valeurs, puis conclure par une phrase avec les mots de l'énoncé et les unités.

Phrase de conclusion

« Le profit est maximal au sommet $(10\,;15)$ : l'atelier doit produire $10$ chandails et $15$ sacs, pour un profit de $465$ dollars. »

Le piège : Mettre la fonction à optimiser dans le système, avec un signe d'inégalité inventé. Elle n'a pas de frontière et ne coupe rien : elle se contente d'être évaluée.

Barème : En général $2$ points pour le système, $1$ point pour la fonction, $2$ points pour les sommets, $1$ point pour la table et $1$ point pour la conclusion chiffrée.

Vérifier avant de rendre

Cinq minutes de vérification récupèrent plus de points qu'un exercice de plus commencé à la hâte.

Chaque sommet passe toutes les contraintes

Pour chaque sommet retenu, substituer ses coordonnées dans les contraintes qui n'ont PAS servi à le calculer. Une seule ligne fausse suffit à l'éliminer.

$(12\,;0)$ vérifie $x+2y=12$ mais donne $3x+2y=36>24$ : il est rejeté.
Le point-test n'est jamais sur la frontière

Pour décider du côté d'un demi-plan, prendre un point franchement à l'intérieur, l'origine quand elle convient. Un point sur la droite vérifie l'égalité et ne décide de rien.

pour $x+y\le 7$ , tester $(1\,;1)$ : $2\le 7$ , donc la région est bien du côté de l'origine.
Le nombre de sommets est vraisemblable

Compter les frontières : avec $n$ frontières il y a au plus $\dfrac{n(n-1)}{2}$ intersections, et toujours moins de sommets. Un polygone à cinq contraintes qui donnerait huit sommets signale un point fantôme.

quatre contraintes donnent six intersections, dont quatre sommets seulement.
La réponse est réalisable

Relire la question : si $x$ et $y$ comptent des objets, un optimum décimal n'est pas une réponse. Chercher alors le meilleur point entier admissible.

$(4{,}5\,;2{,}5)$ donne la borne $600$ dollars, mais la réponse réelle est $(4\,;3)$ et $580$ dollars.

L'exercice type décortiqué

Un atelier de sérigraphie, du texte à la phrase de conclusion

Un atelier imprime des chandails et des sacs. Un chandail demande $3$ heures de travail, un sac $1$ heure, et l'atelier dispose de $45$ heures. Chaque article consomme une pièce de tissu et l'atelier n'en a que $25$ . Enfin, il ne possède que $12$ pochoirs de chandail.

Un chandail rapporte $24$ dollars et un sac $15$ dollars. Quelle production maximise le profit ?

Étape 1

Soit $x$ le nombre de chandails et $y$ le nombre de sacs. Contraintes : $3x+y\le 45$ pour les heures, $x+y\le 25$ pour le tissu, $x\le 12$ pour les pochoirs, plus $x\ge 0$ et $y\ge 0$ .

Pourquoi

Les deux contraintes de positivité ne sont dans aucune phrase de l'énoncé et font pourtant partie du système : elles ferment la région du côté des axes.

Étape 2

Fonction à MAXIMISER : $P(x\,;y)=24x+15y$ , en dollars. Elle s'écrit à part du système.

Pourquoi

La fonction ne trace aucune frontière. L'écrire dans le système avec un signe d'inégalité inventé est l'erreur qui fait perdre le point de modélisation.

Étape 3

Sommets : $(0\,;0)$ ; $(12\,;0)$ , car $3\times 12=36\le 45$ ; $(12\,;9)$ , intersection de $x=12$ et $3x+y=45$ ; $(10\,;15)$ , intersection de $3x+y=45$ et $x+y=25$ ; et $(0\,;25)$ .

Pourquoi

Chaque sommet est vérifié dans les contraintes qui ne l'ont pas produit. En $(12\,;9)$ : $x+y=21\le 25$ , il est admissible.

Étape 4

Table : $P(0\,;0)=0$ ; $P(12\,;0)=288$ ; $P(12\,;9)=288+135=423$ ; $P(10\,;15)=240+225=465$ ; $P(0\,;25)=375$ .

Pourquoi

On évalue TOUS les sommets, même ceux qui semblent perdants : l'écart entre $423$ et $465$ ne se devine pas sur le dessin.

Étape 5

Maximum : $465$ dollars au sommet $(10\,;15)$ . Les deux contraintes saturées sont les heures, $3\times 10+15=45$ , et le tissu, $10+15=25$ .

Pourquoi

Les coordonnées sont entières, donc la réponse est directement réalisable. Les contraintes saturées disent quelles ressources sont épuisées, ce que l'énoncé demande souvent en dernière question.

Étape 6

Conclusion : $10$ chandails et $15$ sacs, pour un profit maximal de $465$ dollars.

Pourquoi

La phrase reprend les mots de l'énoncé et l'unité. Sans elle, le couple $(10\,;15)$ ne vaut pas le point de communication.

Conclusion rédigée

« L'atelier doit imprimer $10$ chandails et $15$ sacs : c'est la production admissible qui rapporte le plus, soit $465$ dollars, et elle utilise entièrement les $45$ heures et les $25$ pièces de tissu. »

L'erreur classique sur cet exercice : L'erreur classique ici est de retenir $(15\,;0)$ , intersection de $3x+y=45$ et de l'axe des abscisses, en oubliant que les pochoirs imposent $x\le 12$ . Ce point donne $P=360$ , une valeur plausible, et la copie ne s'aperçoit de rien.

À savoir par cœur

• Quatre gestes : traduire, tracer et relever les sommets, évaluer, répondre par une phrase.
• « Au plus » donne $\le$ , « au moins » donne $\ge$ , et on ajoute toujours $x\ge 0$ et $y\ge 0$ .
• Un rapport du type « deux fois plus » se vérifie sur un exemple chiffré, jamais mot à mot.
• Un sommet est une intersection QUI APPARTIENT à la région : on la teste dans les autres contraintes.
• Règle des sommets : l'optimum d'une fonction $ax+by$ est toujours sur un sommet.
• La droite baladeuse a pour pente $-\dfrac{a}{b}$ , qui ne dépend que de la fonction.
• Changer la fonction ne change pas le polygone, seulement la table des valeurs.
• Inégalité large, trait plein et bord inclus ; inégalité stricte, trait pointillé.
• Un optimum décimal n'est pas une réponse quand on compte des objets : on cherche le meilleur point entier.

Questions fréquentes

Comment savoir de quel côté de la droite se trouve la région ?

On prend un point-test qui n'est pas sur la droite, l'origine quand elle ne figure pas sur la frontière, et on remplace ses coordonnées dans l'inéquation. Si l'inégalité est vraie, la région est du côté du point-test, sinon elle est de l'autre côté. Un point pris sur la droite vérifie l'égalité et ne décide de rien.

Pourquoi l'optimum est-il toujours sur un sommet ?

Parce que la fonction à optimiser est de la forme ax plus by, donc ses lignes de niveau sont des droites parallèles. En les faisant glisser, la dernière qui touche encore la région la touche en un sommet, ou le long d'un bord entier si elle lui est parallèle. D'un point intérieur, on peut toujours avancer un peu et faire mieux.

Que faire si le sommet optimal a des coordonnées décimales ?

Si les variables comptent des objets ou des personnes, ce sommet n'est pas une réponse : il donne seulement une borne que le résultat réel ne dépassera pas. On n'arrondit pas, car le point arrondi sort souvent de la région. On teste les points entiers voisins qui respectent toutes les contraintes, en longeant le bord actif, et on garde le meilleur.

Que veut dire une contrainte saturée à l'optimum ?

Cela veut dire que la ressource correspondante est entièrement utilisée : l'inégalité devient une égalité au point optimal. C'est souvent ce que la dernière question demande d'interpréter, par exemple pour dire quelles heures de travail sont épuisées et quelle matière première reste en surplus.

Que répondre si le système n'a aucune solution ?

On montre par le calcul que deux exigences sont incompatibles, on dit que la région est vide et qu'il n'existe donc aucun optimum. Une bonne réponse ne s'arrête pas là : elle nomme la contrainte qui bloque et chiffre ce qu'il faudrait relâcher pour rendre le problème possible.

Passer à la pratique

Exercices corrigés : L'optimisation par programmation linéaire

Une méthode se prouve sur une copie, pas sur une fiche. La série du même chapitre reprend chacun de ces pièges dans un exercice, avec le corrigé rédigé étape par étape.

10 exercices corrigés
100 points
150 minutes

Faire les exercices

Fiche suivante Les mathématiques financières

Voir aussi

Toutes les fiches Tous les exercices Série d'exercices : l'optimisation par programmation linéaire (CST 5)Série d'exercices : les systèmes d'équations (CST 4)Fiche : la théorie des graphes (CST 5)Tutorat en math CST 5 à Montréal

Vous cherchez un tuteur en math CST à Montréal ?

Contactez-moi pour une première séance. On travaille sur des exercices du niveau réel des évaluations de cinquième secondaire, jusqu'à l'épreuve unique du Ministère.

Me contacter WhatsApp

Site par Studio Squalli