Exercices corrigés : la programmation linéaire et l'optimisation (math TS, secondaire 5)

a) Découpe : chaque support prend $2$ minutes et chaque console $1$ minute, pour un total limité à $600$ : $2x+y\le 600$. Soudure : $1$ minute par support et $3$ par console, limité à $900$ : $x+3y\le 900$. Le sens de l'inégalité vient du mot DISPONIBLE : on ne peut pas dépasser, donc c'est un « au plus ». Confondre les deux colonnes du tableau, c'est-à-dire écrire $2x+3y\le 600$, est l'erreur de lecture la plus fréquente : chaque contrainte concerne UNE machine, et prend donc un temps dans chaque colonne de produit.

b) $x\ge 0$ et $y\ge 0$. Elles ne vont pas de soi au sens où il faut les ÉCRIRE : sans elles, le domaine des solutions n'est pas borné du bon côté et le polygone n'existe pas. Mathématiquement, rien dans les deux premières contraintes n'interdit $x=-100$, alors que le contexte l'interdit. Les oublier coûte un point et souvent un sommet.

c) $y\ge 40$. C'est une contrainte de MINIMUM, donc son demi-plan est celui du dessus, et elle coupe le polygone par le bas. Attention au sens : « au moins $40$ » se traduit par $\ge$, pas par $>$, une livraison de $40$ consoles exactement respectant l'engagement.

d) On teste les quatre. Découpe : $2\times 200+150=550\le 600$, respectée. Soudure : $200+3\times 150=200+450=650\le 900$, respectée. Non-négativité : évidemment respectée. Consoles : $150\ge 40$, respectée. Le couple $(200\,;150)$ respecte donc les QUATRE contraintes, il appartient à l'ensemble-solution. On vérifie toujours toutes les contraintes, même quand les premières passent : il suffit d'une seule violation pour exclure un point.

a) Sur l'axe des $x$, $y=0$ : la contrainte de découpe donne $2x=600$, soit $x=300$, et celle de soudure donne $x=900$. La plus contraignante est la première : le sommet est $(300\,;0)$. Sur l'axe des $y$, $x=0$ : la découpe donne $y=600$, la soudure $3y=900$, soit $y=300$. Ici c'est la soudure qui contraint : le sommet est $(0\,;300)$. Prendre à chaque fois la plus PETITE des deux valeurs est ce qui évite de sortir du polygone.

b) On résout $2x+y=600$ et $x+3y=900$. Par substitution : $y=600-2x$, puis $x+3(600-2x)=900$, donc $x+1800-6x=900$, soit $-5x=-900$ et $x=180$. Alors $y=600-360=240$. Le sommet est $(180\,;240)$. Vérification dans la seconde équation : $180+720=900$. C'est bien un sommet du polygone, puisqu'il respecte aussi $x\ge 0$ et $y\ge 0$.

c) Quatre : $(0\,;0)$, $(300\,;0)$, $(180\,;240)$ et $(0\,;300)$. Le polygone est BORNÉ parce que les deux contraintes de ressources sont des maximums : elles ferment la région vers le haut et vers la droite, et les axes la ferment vers le bas et vers la gauche. Un problème qui n'aurait que des contraintes de minimum donnerait une région non bornée, comme à l'exercice 7.

d) $(250\,;120)$ : découpe, $500+120=620>600$, violée. Le point est HORS du polygone, et il est inutile de tester la suite. $(100\,;280)$ : découpe, $200+280=480\le 600$, d'accord ; soudure, $100+840=940>900$, violée. Hors du polygone lui aussi. Les deux points sont proches du bord, et c'est justement pour cela qu'un test numérique vaut mieux qu'un coup d'oeil sur le dessin.

a) $P=5x+8y$, en dollars. On vérifie l'unité en testant un cas simple : $10$ supports et rien d'autre donnent $50$ dollars, ce qui est cohérent.

b) $(0\,;0)$ : $P=0$. $(300\,;0)$ : $P=1500$. $(180\,;240)$ : $P=900+1920=2820$. $(0\,;300)$ : $P=2400$. La table doit être écrite en entier sur la copie, même quand un sommet est visiblement mauvais : c'est elle qui justifie la réponse.

c) Le maximum est $2820$ dollars, atteint en $(180\,;240)$ : l'atelier produit $180$ supports et $240$ consoles. On vérifie que ce plan sature les deux machines : découpe $360+240=600$ minutes, soudure $180+720=900$ minutes. Les deux ressources sont utilisées à fond, ce qui est le signe habituel d'un optimum en sommet intérieur.

d) Parce que la fonction économique est LINÉAIRE. Sur un segment du bord, elle s'écrit comme une fonction affine d'un paramètre qui parcourt le segment : elle est donc monotone, et sa plus grande valeur est atteinte à une extrémité, c'est-à-dire en un sommet. À l'intérieur du polygone, on peut toujours se déplacer dans la direction qui fait croître $P$ jusqu'à toucher le bord. Tester quatre points remplace donc l'examen d'une infinité, et c'est tout l'intérêt de la méthode.

a) $5x+8y\ge 2400$. Cette inéquation vient S'AJOUTER aux quatre contraintes, elle ne les remplace pas : une solution avantageuse reste avant tout une solution réalisable.

b) Sur l'axe des $y$, $x=0$ donne $8y=2400$, soit $y=300$ : c'est exactement le sommet $(0\,;300)$, la droite de seuil passe donc par un sommet du polygone. Le second point est sur la frontière de découpe : on résout $5x+8y=2400$ et $2x+y=600$. De la seconde, $y=600-2x$, d'où $5x+8(600-2x)=2400$, soit $5x+4800-16x=2400$, donc $-11x=-2400$ et $x=\dfrac{2400}{11}\approx 218{,}2$, puis $y=600-\dfrac{4800}{11}=\dfrac{1800}{11}\approx 163{,}6$. On vérifie que le point est bien sur le bord : son abscisse est comprise entre $180$ et $300$, donc il appartient au segment de découpe, et la soudure y vaut $\dfrac{7800}{11}\approx 709$ minutes, en dessous des $900$ disponibles. Les coordonnées ne tombent pas juste, et c'est normal : une droite de seuil n'a aucune raison de passer par un point entier.

c) La région avantageuse est décrite par les cinq inéquations réunies : $2x+y\le 600$, $x+3y\le 900$, $x\ge 0$, $y\ge 0$ et $5x+8y\ge 2400$. C'est un triangle, coincé entre la droite de seuil et le coin du polygone, dont les sommets sont $(0\,;300)$, $(180\,;240)$ et $(218{,}2\,;163{,}6)$. Tous ses points respectent les contraintes ET rapportent au moins $2400$ dollars : ce sont les plans que le gestionnaire peut retenir.

d) $(120\,;230)$ : contraintes, $240+230=470\le 600$ et $120+690=810\le 900$, d'accord ; profit, $600+1840=2440\ge 2400$, d'accord. Il est AVANTAGEUX. $(150\,;180)$ : contraintes, $300+180=480\le 600$ et $150+540=690\le 900$, d'accord, donc le plan est réalisable ; profit, $750+1440=2190<2400$, refusé. Il est réalisable mais PAS avantageux, et la distinction est exactement ce que la question évalue : un plan peut être parfaitement faisable et ne pas atteindre l'objectif fixé.

a) $Q(0\,;0)=0$. $Q(300\,;0)=600$. $Q(180\,;240)=360+1440=1800$. $Q(0\,;300)=0+1800=1800$. Deux sommets donnent la MÊME valeur maximale, ce qui n'arrive jamais par hasard.

b) La droite $Q=1800$ s'écrit $2x+6y=1800$, soit $y=-\dfrac{1}{3}x+300$ : sa pente vaut $-\dfrac{1}{3}$. La frontière de soudure $x+3y=900$ s'écrit $y=-\dfrac{1}{3}x+300$ : même pente et même ordonnée à l'origine, les deux droites sont donc CONFONDUES, ce qui explique les deux valeurs égales de la question a). La figure montre une droite de niveau plus basse, $Q=1200$, pour que le parallélisme se voie : toutes les droites $Q=\text{constante}$ glissent sur la même direction. Plus généralement, la pente de la fonction économique $ax+by$ vaut $-\dfrac{a}{b}$, et celle d'une contrainte $cx+dy$ vaut $-\dfrac{c}{d}$ : l'égalité $\dfrac{2}{6}=\dfrac{1}{3}$ annonce le parallélisme avant tout tracé.

c) Tous les points du SEGMENT joignant $(0\,;300)$ à $(180\,;240)$ sont optimaux, et ils donnent tous $Q=1800$. Vérification sur un point intermédiaire, $(90\,;270)$ : $Q=180+1620=1800$, et les contraintes sont respectées, $180+270=450\le 600$ et $90+810=900\le 900$. Il y a donc une INFINITÉ de plans optimaux, et la réponse attendue est la description du segment, pas un point choisi au hasard.

d) Tout critère que la fonction économique ne mesure pas : la place de stockage, la demande réelle du marché pour chaque article, le délai de livraison, l'usure des machines, ou la préférence d'un client. C'est exactement la situation où une entreprise choisit une solution AVANTAGEUSE parmi plusieurs optimales, et le programme attend qu'on le dise en une phrase, sans inventer de chiffres.

a) La contrainte $y\ge 40$ coupe le bas du polygone. Sur $x=0$, le sommet bas devient $(0\,;40)$. Sur la droite $y=40$, la frontière de découpe donne $2x+40=600$, donc $x=280$ : le sommet est $(280\,;40)$. Il faut vérifier que ce point respecte la soudure : $280+120=400\le 900$, d'accord. Les deux autres sommets sont inchangés, $(180\,;240)$ et $(0\,;300)$, tous deux au-dessus de $y=40$.

b) $(0\,;40)$ : $P=320$. $(280\,;40)$ : $P=1400+320=1720$. $(180\,;240)$ : $P=2820$. $(0\,;300)$ : $P=2400$.

c) Le maximum reste $2820$ dollars, en produisant $180$ supports et $240$ consoles. La commande ferme n'a RIEN changé, et c'est une réponse en soi : l'optimum précédent produisait déjà $240$ consoles, bien au-delà des $40$ exigées, donc la nouvelle contrainte n'est pas ACTIVE. Une contrainte qui n'est pas active peut être ajoutée ou retirée sans déplacer l'optimum, et le dire explicitement vaut des points.

d) Aucune. Découpe : $2\times 180+240=600$ minutes sur $600$. Soudure : $180+3\times 240=900$ minutes sur $900$. Les deux machines sont SATURÉES, ce qui explique que l'optimum soit au croisement des deux frontières. Pour gagner davantage, il faudrait acheter du temps de machine, et c'est exactement la question de l'exercice 9.

a) Liant : $2x+y\ge 12$. Fines : $x+2y\ge 12$. Non-négativité : $x\ge 0$ et $y\ge 0$. Le sens est ici $\ge$, parce qu'il s'agit d'exigences minimales et non de ressources limitées. La fonction économique est $C=40x+30y$, en dollars, et on la MINIMISE.

b) Sommet sur l'axe des $y$ : $x=0$ donne $y\ge 12$ pour le liant et $y\ge 6$ pour les fines, donc le point le plus bas est $(0\,;12)$. Sommet sur l'axe des $x$ : $y=0$ donne $x\ge 6$ et $x\ge 12$, donc $(12\,;0)$. Sommet intérieur : on résout $2x+y=12$ et $x+2y=12$. De la première, $y=12-2x$, d'où $x+24-4x=12$, soit $-3x=-12$ et $x=4$, puis $y=4$. Le sommet est $(4\,;4)$, et il respecte bien les deux contraintes avec égalité.

c) $C(0\,;12)=360$ dollars. $C(4\,;4)=160+120=280$ dollars. $C(12\,;0)=480$ dollars. Le minimum est $280$ dollars, pour $4$ tonnes de chaque granulat. Vérification des exigences : liant $8+4=12$, fines $4+8=12$, les deux sont atteintes exactement, sans gaspillage.

d) Parce que la région s'étend vers le haut et vers la droite, c'est-à-dire vers les grandes quantités. En s'y déplaçant, le coût $40x+30y$ augmente indéfiniment : il n'y a donc pas de coût maximal, la question n'aurait pas de réponse. Le coût MINIMAL, lui, est atteint sur le bord inférieur de la région, qui est borné par les trois sommets. La règle générale : dans une région non bornée, l'extremum existe du côté où la région est fermée, et il faut le dire avant de conclure.

a) La découpe passe à $720$ minutes : $2x+y\le 720$. Le nouveau sommet intérieur est l'intersection de $2x+y=720$ et $x+3y=900$. Par substitution, $y=720-2x$, d'où $x+3(720-2x)=900$, soit $x+2160-6x=900$, donc $-5x=-1260$ et $x=252$, puis $y=720-504=216$. Le sommet est $(252\,;216)$. Vérification : $252+3\times 216=252+648=900$.

b) $P=5\times 252+8\times 216=1260+1728=2988$ dollars. Les autres sommets restent moins bons : $(360\,;0)$ donne $1800$ dollars, $(0\,;300)$ donne toujours $2400$.

c) Le profit passe de $2820$ à $2988$ dollars, soit $168$ dollars de plus, pour une location de $150$ dollars. Le gain net est de $18$ dollars par semaine : la location est rentable, mais de peu. Une réponse qui s'arrête à « le profit augmente » manque la question : il fallait comparer l'augmentation au COÛT, et conclure par une phrase de décision.

d) Les deux machines sont saturées à l'optimum, donc les deux locations déplaceraient réellement le sommet : aucune n'est à écarter d'emblée. Pour les départager sans tout recalculer, on compare ce que rapporte une minute de chaque ressource. Ici, $120$ minutes de découpe rapportent $168$ dollars, soit $1{,}40$ dollar la minute. Il suffit de faire le même calcul pour la soudure et de garder la plus rentable. Le raisonnement général : seule une contrainte ACTIVE mérite d'être desserrée, et une contrainte inactive ne rapporterait rien du tout.

a) $R(0\,;0)=0$. $R(300\,;0)=9000$. $R(180\,;240)=5400+2400=7800$. $R(0\,;300)=3000$. Le maximum est $9000$ dollars, atteint en $(300\,;0)$ : le gérant ne produirait QUE des supports.

b) Le comptable choisit $(180\,;240)$, le gérant $(300\,;0)$. Les deux plans sont optimaux, mais pour des objectifs différents : il n'y a pas de contradiction, seulement deux questions distinctes. Un problème d'examen qui change la fonction économique en cours de route attend précisément cette observation.

c) Profit du plan du gérant : $P(300\,;0)=1500$ dollars, contre $2820$ pour le plan du comptable, soit $1320$ dollars de moins. Chiffre d'affaires du plan du comptable : $R(180\,;240)=7800$ dollars, contre $9000$, soit $1200$ dollars de moins. Chacun perd sur le critère de l'autre, et c'est ce chiffrage qui permet une vraie discussion.

d) La droite $P=\text{constante}$ a pour pente $-\dfrac{5}{8}=-0{,}625$, celle de $R=\text{constante}$ a pour pente $-\dfrac{30}{10}=-3$. La première est peu inclinée et sort du polygone par le coin supérieur, en $(180\,;240)$ ; la seconde est très inclinée et en sort par la droite, en $(300\,;0)$. Repère utile : les pentes des deux frontières valent $-2$ et $-\dfrac{1}{3}$. Une fonction économique de pente comprise entre les deux désigne le sommet intérieur ; une pente plus raide que $-2$ désigne $(300\,;0)$, et une pente plus douce que $-\dfrac{1}{3}$ désigne $(0\,;300)$. C'est la règle qui permet de prévoir le sommet optimal AVANT de dresser la table.