Exercices corrigés : l'optimisation par programmation linéaire (math CST, secondaire 5)

a) On lit les sommets sur le quadrillage, un par un, en tournant toujours dans le même sens pour n'en oublier aucun : $(0\,;0)$, l'origine ; $(7\,;0)$, sur l'axe des abscisses ; $(2\,;5)$, le point le plus haut ; et $(0\,;3)$, sur l'axe des ordonnées. Un sommet est un point où DEUX frontières se coupent, jamais un point pris au hasard sur un bord. La lecture graphique n'est fiable que si les coordonnées tombent sur des nœuds du quadrillage, ce qui est le cas ici ; dès qu'un sommet tombe entre deux traits, il faut le calculer, et c'est l'objet de l'exercice 3.

b) Pour $d_{1}$ : la pente vaut $\dfrac{5-0}{2-7}=\dfrac{5}{-5}=-1$. Avec le point $(7\,;0)$ : $0=-1\times 7+b$, donc $b=7$, et $d_{1}$ a pour équation $y=-x+7$, qu'on écrit aussi $x+y=7$. Pour $d_{2}$ : la pente vaut $\dfrac{5-3}{2-0}=1$, et l'ordonnée à l'origine se lit directement sur le graphique, $b=3$ : $d_{2}$ a pour équation $y=x+3$. Écrire une frontière sous la forme $x+y=7$ plutôt que $y=-x+7$ n'a rien d'anodin : c'est cette forme-là qui se lit comme une phrase, « le total des deux quantités vaut $7$ », et c'est celle qu'on retrouvera dans les énoncés.

c) On remplace $x$ par $1$ et $y$ par $1$ dans chaque frontière. Pour $d_{1}$ : $1+1=2$, et $2\le 7$, donc le point-test est du côté où $x+y\le 7$. Comme $(1\,;1)$ est visiblement DANS la région, la contrainte est bien $x+y\le 7$. Pour $d_{2}$ : on compare $y$ à $x+3$, soit $1$ à $1+3=4$. Comme $1\le 4$, le point-test est du côté où $y\le x+3$, donc c'est cette contrainte-là. Le point-test est l'outil qui évite tout raisonnement sur « au-dessus » ou « en dessous », mots qui trompent dès que la droite est presque verticale. Un seul interdit : ne jamais prendre un point-test SUR la frontière, il vérifie l'égalité et ne décide de rien.

d) Les deux dernières contraintes se lisent sur les axes : la région ne descend jamais sous l'axe des abscisses, donc $y\ge 0$, et ne passe jamais à gauche de l'axe des ordonnées, donc $x\ge 0$. Le système complet est $x\ge 0$, $y\ge 0$, $x+y\le 7$ et $y\le x+3$. Les inégalités sont LARGES parce que les quatre frontières sont tracées en trait plein : le bord fait partie de la région. Un trait pointillé aurait signifié une inégalité stricte, donc un bord exclu. Ce détail décide de tout dans un problème d'optimisation, puisque la solution optimale se trouve précisément sur un sommet, c'est-à-dire sur le bord : avec des inégalités strictes, l'optimum ne serait jamais atteint.

a) « Pas plus de $60$ plateaux en tout » porte sur la SOMME des deux quantités : $x+y\le 60$. « Au moins $15$ plateaux chauds » porte sur $y$ seul, et « au moins » se traduit par $\ge$ : $y\ge 15$. Le réflexe qui fait gagner des points est de traduire une phrase à la fois, en repérant d'abord DE QUOI on parle, puis le sens de l'inégalité. « Au plus », « ne dépasse pas », « au maximum » donnent $\le$ ; « au moins », « au minimum », « il faut au moins » donnent $\ge$.

b) C'est $x\le 2y$. La phrase dit que le nombre de plateaux FROIDS ne dépasse pas le double du nombre de plateaux CHAUDS, donc la quantité limitée est $x$, et la borne est $2y$. Vérification avec un exemple : avec $20$ plateaux chauds, on peut faire jusqu'à $40$ plateaux froids, et le couple $(40\,;20)$ doit passer. Dans $x\le 2y$ : $40\le 40$, vrai. Dans $2x\le y$ : $80\le 20$, faux. C'est donc bien la première écriture. Cette question tombe à toutes les épreuves parce que la traduction mot à mot trompe : le mot « double » est collé au mot « chauds » dans la phrase, et beaucoup écrivent $2y$ du mauvais côté. La parade est l'exemple chiffré, en dix secondes.

c) Le temps total de préparation vaut $20x+30y$ minutes, et il ne doit pas dépasser $1500$ : $20x+30y\le 1500$. On divise les trois termes par $10$, puis on peut encore diviser par $1$ seulement, car $2$, $3$ et $150$ n'ont pas de diviseur commun : $2x+3y\le 150$. Simplifier n'est pas facultatif, c'est ce qui rend les calculs de sommets faisables sans calculatrice. Attention à diviser TOUS les termes, le second membre compris : oublier de diviser $1500$ est l'erreur la plus coûteuse du chapitre, parce qu'elle donne une région fausse mais plausible.

d) Le système est : $x\ge 0$, $y\ge 0$, $x+y\le 60$, $y\ge 15$, $x\le 2y$ et $2x+3y\le 150$. Les deux contraintes de positivité ne sont écrites dans aucune phrase de l'énoncé, et pourtant elles font partie du système : on ne prépare pas un nombre négatif de plateaux. Les oublier laisse une région ouverte vers la gauche ou vers le bas, donc des sommets qui n'existent pas. La fonction à optimiser, elle, n'est pas une contrainte et ne se met jamais dans le système : c'est $R(x\,;y)=12x+18y$, en dollars, et on cherche ici à la MAXIMISER.

a) On résout le système des deux équations. La méthode de soustraction va le plus vite ici, car les deux équations ont le même terme $2y$ : $(3x+2y)-(x+2y)=24-12$ donne $2x=12$, donc $x=6$. On reporte dans la première équation : $6+2y=12$, donc $2y=6$ et $y=3$. Le point d'intersection est $(6\,;3)$. Vérification dans la SECONDE équation, celle qui n'a pas servi au report : $3\times 6+2\times 3=18+6=24$, exact. Reporter toujours dans une équation et vérifier dans l'autre, c'est la seule façon d'attraper une erreur de signe sans tout recommencer.

b) Les sommets sont $(0\,;0)$, $(8\,;0)$, $(6\,;3)$ et $(0\,;6)$. On les obtient en croisant les frontières deux à deux : les deux axes donnent l'origine ; l'axe des abscisses et la droite $3x+2y=24$ donnent $(8\,;0)$, car $3x=24$ ; les deux obliques donnent $(6\,;3)$, calculé en a) ; l'axe des ordonnées et la droite $x+2y=12$ donnent $(0\,;6)$, car $2y=12$. Chaque sommet doit ensuite être VÉRIFIÉ dans toutes les contraintes, et c'est précisément ce que la question suivante met en défaut.

c) Un point d'intersection n'est un sommet que s'il appartient à la région, donc s'il respecte TOUTES les contraintes, pas seulement les deux qui l'ont produit. Le point $(12\,;0)$ vérifie $x+2y=12$, mais dans l'autre contrainte : $3\times 12+2\times 0=36$, et $36>24$. Il est donc hors de la région. Le point $(0\,;12)$ vérifie $3x+2y=24$, mais $0+2\times 12=24$, et $24>12$ : hors de la région lui aussi. Sur le dessin, ces deux points sont là où les prolongements en pointillé rencontrent les axes, bien à l'extérieur de la zone colorée. C'est le piège le plus cher du chapitre : on calcule six intersections, on les met toutes dans la table, et l'optimum tombe sur un point qui n'existe pas. Le filtre est mécanique, une ligne de calcul par contrainte restante.

d) Quatre frontières se croisent deux à deux de $\dfrac{4\times 3}{2}=6$ façons : les couples sont axe-axe, axe des $x$ avec chacune des deux obliques, axe des $y$ avec chacune des deux obliques, et les deux obliques entre elles. Or le polygone n'a que $4$ sommets. Deux de ces six intersections, $(12\,;0)$ et $(0\,;12)$, tombent hors de la région et sont éliminées par le filtre de la question c). Autrement dit, le nombre de sommets est au PLUS le nombre de couples de frontières, jamais l'inverse, et il est presque toujours plus petit.

a) En $(4\,;0)$ : $5\times 4+4\times 0=20$. En $(0\,;5)$ : $5\times 0+4\times 5=20$. Les deux points donnent la même valeur, ce qui est normal puisqu'ils sont sur la même droite $5x+4y=20$. Pour la pente, on isole $y$ : $4y=20-5x$, donc $y=-\dfrac{5}{4}x+5$ et la pente vaut $-\dfrac{5}{4}$, soit $-1{,}25$. Retenez ceci, car c'est tout le chapitre : la pente de la droite baladeuse ne dépend QUE des coefficients de la fonction à optimiser, jamais des contraintes. Changer la valeur $20$ en $40$ donne une droite parallèle, jamais une droite d'inclinaison différente.

b) On déplace la droite vers le haut et vers la droite, en gardant sa pente. Tant qu'elle coupe encore la région colorée, la valeur de $P$ peut augmenter. Le dernier point de contact est le sommet $(6\,;3)$ : au-delà, la droite est entièrement au-dessus de la région et plus aucun point admissible ne réalise cette valeur. La droite baladeuse rend visible ce que la règle des sommets affirme : l'optimum d'une fonction linéaire sur un polygone est toujours atteint sur un SOMMET, jamais à l'intérieur. La raison est simple : à l'intérieur, on peut toujours avancer un peu dans la direction qui fait croître $P$.

c) On dresse la table. En $(0\,;0)$ : $P=0$. En $(8\,;0)$ : $P=5\times 8=40$. En $(6\,;3)$ : $P=30+12=42$. En $(0\,;6)$ : $P=24$. Le maximum vaut donc $42$, atteint en $(6\,;3)$, ce qui confirme la lecture graphique. Le sommet $(8\,;0)$, avec $40$, était le concurrent sérieux : l'écart n'est que de $2$, et c'est justement pour cela qu'on ne se fie pas à l'œil seul. La table des sommets est la preuve, la droite baladeuse est la compréhension ; une copie complète montre les deux.

d) Pour $Q=2x+6y$ : en $(0\,;0)$, $Q=0$ ; en $(8\,;0)$, $Q=16$ ; en $(6\,;3)$, $Q=12+18=30$ ; en $(0\,;6)$, $Q=36$. Le maximum est cette fois en $(0\,;6)$, un AUTRE sommet. La région n'a pas bougé d'un millimètre, seule la fonction a changé, et le gagnant change avec elle. C'est la pente qui explique tout : $Q$ donne une droite de pente $-\dfrac{2}{6}=-\dfrac{1}{3}$, presque horizontale, qui balaie la région du bas vers le haut et touche donc le sommet le plus haut. La droite de $P$, de pente $-1{,}25$, est plus raide que le bord $x+2y=12$ mais moins que l'autre, et s'arrête au sommet intérieur. Conclusion à retenir : le polygone dit ce qui est possible, la fonction dit ce qui est meilleur, et on ne peut pas répondre sans les deux.

a) On soustrait la première équation de la seconde : $(3x+y)-(x+y)=16-7$ donne $2x=9$, donc $x=4{,}5$. On reporte : $4{,}5+y=7$, donc $y=2{,}5$. Le sommet est $(4{,}5\,;2{,}5)$. Vérification dans l'équation qui n'a pas servi au report : $3\times 4{,}5+2{,}5=13{,}5+2{,}5=16$, exact. Il faut aussi contrôler la contrainte $x\le 5$, qui n'a pas participé au calcul : $4{,}5\le 5$, le point est bien dans la région.

b) En $(0\,;0)$ : $B=0$. En $(5\,;0)$ : $B=500$. En $(5\,;1)$ : $B=500+60=560$. En $(4{,}5\,;2{,}5)$ : $B=450+150=600$. En $(0\,;7)$ : $B=420$. Le maximum vaut $600$ dollars, atteint en $(4{,}5\,;2{,}5)$. Mathématiquement, le travail est terminé et la règle des sommets a parfaitement fonctionné.

c) Parce qu'on ne fabrique pas quatre lampes et demie. Les variables comptent des OBJETS, donc elles sont entières, et le sommet optimal a des coordonnées décimales. La règle des sommets donne l'optimum sur la région continue, c'est-à-dire une BORNE : le bénéfice réel ne pourra pas dépasser $600$ dollars, mais rien ne garantit qu'il l'atteigne. C'est exactement le genre de conclusion qu'une épreuve attend : on répond à la question posée, pas au calcul effectué.

d) Arrondir donne $(5\,;3)$, qu'il faut tester : $x+y=8$, or la contrainte impose $x+y\le 7$. L'artisan n'a que sept plaques de bois, cette production est IMPOSSIBLE. Arrondir vers le bas donne $(4\,;2)$, admissible, mais $B=400+120=520$ dollars seulement. On cherche donc en testant les points entiers de la région proches du bord : $(5\,;1)$ donne $560$ ; $(4\,;3)$ vérifie $x+y=7\le 7$ et $3x+y=15\le 16$, donc il est admissible, et $B=400+180=580$ ; $(3\,;4)$ donne $300+240=540$. La meilleure production entière est donc $4$ lampes et $3$ horloges, pour $580$ dollars. Deux leçons, et ce sont celles qui se perdent en points : arrondir un optimum n'est PAS une méthode, le point arrondi sort souvent de la région ; et la meilleure solution entière est toujours sur un bord, donc on la cherche le long du bord actif, pas au hasard.

a) L'encadrement donne $20x+10y\ge 300$, qu'on divise par $10$ : $2x+y\ge 30$. Les groupes donnent $x+y\ge 20$. Les deux minimums donnent $x\ge 6$ et $y\ge 4$, qui rendent inutiles les contraintes de positivité. Le système est donc $x\ge 6$, $y\ge 4$, $2x+y\ge 30$ et $x+y\ge 20$. La fonction à MINIMISER est $C(x\,;y)=600x+350y$, en dollars. Remarquez que toutes les inégalités vont dans le même sens, $\ge$ : la région est ouverte vers le haut et vers la droite, ce qui est normal pour un problème de minimum, où embaucher davantage est toujours possible mais toujours plus cher.

b) Trois intersections sont dans la région. La droite $x=6$ coupe $2x+y=30$ en $(6\,;18)$, et on vérifie $x+y=24\ge 20$ : admissible. Les deux obliques se coupent quand $2x+y=30$ et $x+y=20$ ; par soustraction $x=10$, puis $y=10$ : le point $(10\,;10)$ vérifie $x\ge 6$ et $y\ge 4$, admissible. Enfin $y=4$ coupe $x+y=20$ en $(16\,;4)$, et $2x+y=36\ge 30$ : admissible. On écarte $(13\,;4)$, intersection de $y=4$ et de $2x+y=30$, car $x+y=17$, et $17<20$ : ce point laisse trois groupes sans adulte.

c) En $(6\,;18)$ : $C=3600+6300=9900$ dollars. En $(10\,;10)$ : $C=6000+3500=9500$ dollars. En $(16\,;4)$ : $C=9600+1400=11000$ dollars. Le minimum vaut $9500$ dollars, pour $10$ moniteurs et $10$ aides-moniteurs. On vérifie que cette embauche tient les quatre exigences : elle encadre $20\times 10+10\times 10=300$ enfants, exactement le minimum ; elle fournit $20$ adultes pour $20$ groupes, exactement le minimum ; et les deux planchers $6$ et $4$ sont largement dépassés. Les deux contraintes qui décident sont donc l'encadrement et les groupes, et elles sont toutes deux tendues au maximum : c'est la signature d'une solution optimale de minimisation.

d) Avec $C_{2}(x\,;y)=600x+250y$ : en $(6\,;18)$, $C_{2}=3600+4500=8100$ dollars ; en $(10\,;10)$, $C_{2}=6000+2500=8500$ dollars ; en $(16\,;4)$, $C_{2}=9600+1000=10600$ dollars. Le minimum passe à $8100$ dollars, en $(6\,;18)$ : la municipalité a maintenant intérêt à embaucher le minimum de moniteurs et beaucoup d'aides. La région admissible n'a pas changé, et pourtant la décision, elle, a changé. C'est la leçon du chapitre, vue ici dans un cas concret : une subvention de $100$ dollars par aide ne déplace aucune contrainte, mais elle fait basculer la solution d'un sommet à un autre, et elle fait économiser $1400$ dollars par semaine.

a) La place donne $x+y\le 40$, les soins donnent $2x+y\le 60$, les semences donnent $x\le 25$, et on ajoute $x\ge 0$ et $y\ge 0$. Le revenu est $R(x\,;y)=30x+20y$, en dollars, et on le maximise. Notez que la contrainte de semences ne porte que sur $x$ : elle se trace comme une droite VERTICALE, ce qui déroute quand on cherche une pente. Une contrainte à une seule variable est toujours une droite parallèle à un axe.

b) Proposition du chef de culture, $(25\,;10)$ : la place donne $25+10=35\le 40$, vrai ; les soins donnent $2\times 25+10=60\le 60$, vrai, tout juste ; les semences donnent $25\le 25$, vrai, tout juste aussi. Elle est admissible, et $R=750+200=950$ dollars. Proposition du jardinier, $(0\,;40)$ : $0+40=40\le 40$, vrai ; $0+40=40\le 60$, vrai ; $0\le 25$, vrai. Admissible également, avec $R=800$ dollars. Le chef de culture avait donc tort de croire qu'utiliser toutes les semences suffit : saturer une contrainte n'est pas un objectif, c'est une conséquence.

c) Proposition de la comptable, $(20\,;20)$ : la place donne $40\le 40$, vrai ; les soins donnent $40+20=60\le 60$, vrai ; les semences donnent $20\le 25$, vrai. Elle est admissible, et $R=600+400=1000$ dollars. C'est la meilleure des trois. Ce n'est pas un hasard : $(20\,;20)$ est le sommet où se croisent la contrainte de place et celle de soins, et les deux autres propositions sont aussi des sommets, mais moins bons. La table complète des cinq sommets le confirme : $(0\,;0)$ donne $0$, $(25\,;0)$ donne $750$, $(25\,;10)$ donne $950$, $(20\,;20)$ donne $1000$ et $(0\,;40)$ donne $800$ dollars.

d) La production $(22\,;18)$ n'est pas admissible : les soins demanderaient $2\times 22+18=62$ heures, or la serre n'en a que $60$. Le total de $40$ plateaux et les semences, eux, passeraient, ce qui est exactement le piège : un couple peut satisfaire trois contraintes sur quatre et rester impossible. On vérifie TOUTES les contraintes avant de calculer le revenu, jamais l'inverse. Quant aux productions intérieures, elles sont inutiles à tester à cause de la règle des sommets : une fonction de la forme $ax+by$ atteint toujours son maximum sur un sommet du polygone. D'un point intérieur, on peut toujours ajouter un plateau de tomates ou un plateau de fines herbes, donc augmenter le revenu, tant qu'on n'a pas buté sur un bord.

1) FAUX. Le sommet où se croisent les deux obliques n'est qu'un candidat parmi les autres, et il arrive souvent qu'il perde. Contre-exemple pris à l'exercice 4 : sur la région de sommets $(0\,;0)$, $(8\,;0)$, $(6\,;3)$ et $(0\,;6)$, la fonction $Q=2x+6y$ vaut $30$ au sommet des deux obliques $(6\,;3)$, mais $36$ en $(0\,;6)$, qui est l'intersection d'une oblique et d'un AXE. Version correcte : on évalue la fonction à TOUS les sommets, sans en privilégier aucun.

2) FAUX dans sa conclusion. Il est vrai qu'un point optimal respecte toutes les contraintes, mais la région en contient une infinité et on ne peut pas tous les tester. La règle des sommets dit exactement pourquoi ce n'est pas nécessaire : une fonction de la forme $ax+by$ atteint son maximum et son minimum sur des SOMMETS du polygone. Version correcte : on teste les sommets, et eux seuls. Seule exception, un problème à variables entières, où l'on cherche ensuite le meilleur point entier le long du bord actif, comme à l'exercice 5.

3) FAUX. C'est la nature STRICTE ou LARGE de l'inégalité qui décide du trait, pas le sens de l'inégalité. « Au plus $60$ plateaux » se traduit par $x+y\le 60$, une inégalité large, donc un trait PLEIN et un bord inclus. Le pointillé est réservé aux inégalités strictes, $<$ ou $>$, qui traduisent « strictement moins de » ou « plus de, sans l'atteindre ». Version correcte : $\le$ et $\ge$ donnent un trait plein, $<$ et $>$ un trait pointillé.

4) FAUX, et c'est ce qui rend le chapitre économique. Le polygone vient des CONTRAINTES, la fonction à optimiser n'en fait pas partie. Changer $P=5x+4y$ en $Q=2x+6y$ ne déplace aucune frontière : la région est identique, les sommets sont les mêmes, il n'y a que la table des valeurs à refaire. C'est exactement ce qu'on a vu à l'exercice 4, puis à l'exercice 6 avec la subvention. Version correcte : on retrace le polygone seulement si une CONTRAINTE change.

5) FAUX, pour deux raisons distinctes. D'abord, la région peut être VIDE : si un club exige au moins $12$ canots et au moins $20$ kayaks alors qu'il n'a que $30$ emplacements, aucune combinaison ne passe, puisque $12+20=32>30$. Ensuite, même non vide, une région ouverte peut ne pas admettre de maximum : avec $x\ge 6$ et $y\ge 4$ seulement, le revenu $30x+20y$ grandit sans limite. Version correcte : un problème a une solution si la région est non vide ET bornée du côté où l'on optimise.

a) Les frontières sont les deux axes et les deux droites obliques. Les axes se coupent en $(0\,;0)$, qui vérifie tout. La droite $x+y=30$ coupe l'axe des abscisses en $(30\,;0)$ : on vérifie l'entretien, $2\times 30+0=60\le 90$, admissible. Elle coupe l'axe des ordonnées en $(0\,;30)$ : $2\times 0+3\times 30=90\le 90$, admissible tout juste, le point est sur la droite d'entretien. La droite d'entretien, elle, coupe les axes en $(45\,;0)$ et $(0\,;30)$, et $(45\,;0)$ est hors de la région puisque $45+0=45>30$. Les sommets sont donc bien les trois annoncés.