Exercices corrigés : programmation linéaire et optimisation (math SN5)

Règle qui gouverne les trois questions : un point appartient à l'ensemble-solution si et seulement si il vérifie TOUTES les contraintes à la fois. Il suffit donc d'une seule contrainte violée pour le rejeter, et il faut au contraire les vérifier toutes avant d'accepter. On les passe systématiquement en revue, dans l'ordre, sans en sauter.

a) Pour $(3\,;2)$ : $3\geq 0$ ✓ ; $2\geq 0$ ✓ ; $3+2=5\leq 8$ ✓ ; $2\leq 3$ ✓. Les quatre contraintes sont vérifiées, donc le point APPARTIENT à l'ensemble-solution.

b) Pour $(2\,;5)$ : $2\geq 0$ ✓ ; $5\geq 0$ ✓ ; $2+5=7\leq 8$ ✓ ; mais $y\leq x$ demande $5\leq 2$, ce qui est FAUX ✗. Le point n'appartient donc PAS à l'ensemble-solution. Remarquez que trois contraintes sur quatre étaient satisfaites : cela ne suffit pas, et c'est le point de méthode de la question. Géométriquement, $(2\,;5)$ est au-dessus de la droite $y=x$ alors que la contrainte impose d'être en dessous.

c) Pour $(5\,;1)$ : $5\geq 0$ ✓ ; $1\geq 0$ ✓ ; $5+1=6\leq 8$ ✓ ; $1\leq 5$ ✓. Toutes vérifiées, le point APPARTIENT à l'ensemble-solution. Lecture d'ensemble : les deux contraintes de positivité restreignent au premier quadrant, $x+y\leq 8$ coupe par une droite oblique descendante, et $y\leq x$ ne garde que la moitié située SOUS la bissectrice. L'ensemble-solution est donc un triangle, et l'on peut vérifier que $(3\,;2)$ et $(5\,;1)$ y sont bien tandis que $(2\,;5)$ est dans la moitié exclue.

a) Le polygone de contraintes est délimité par les quatre droites frontières $x=0$, $y=0$, $x+y=6$ et $y=2x$, et chaque sommet est l'INTERSECTION de deux d'entre elles. On les cherche donc deux à deux, en ne gardant que les intersections qui respectent l'ensemble des contraintes. Origine : $x=0$ et $y=0$ se coupent en $O(0\,;0)$, qui vérifie bien $0+0\leq 6$ et $0\leq 0$ ✓. Sur l'axe des $x$ : $y=0$ et $x+y=6$ donnent $B(6\,;0)$, qui vérifie $0\leq 12$ ✓. Troisième sommet : l'intersection des deux droites obliques, calculée en b), soit $C(2\,;4)$. Le polygone est donc un TRIANGLE de sommets $O(0\,;0)$, $B(6\,;0)$ et $C(2\,;4)$.

b) On résout le système formé par $y=2x$ et $x+y=6$. En substituant la première dans la seconde : $x+2x=6$, donc $3x=6$ et $x=2$, puis $y=2\times 2=4$. Le sommet est $C(2\,;4)$. Vérification dans les DEUX équations, ce qui est le seul contrôle valable : $y=2x$ donne $4=2\times 2$ ✓ et $x+y=6$ donne $2+4=6$ ✓. Il faut aussi confirmer que ce point respecte les autres contraintes, ici les positivités, ce qui est le cas ✓.

Point de méthode pour tout le chapitre : toutes les intersections de droites frontières ne sont pas des sommets. Il faut à chaque fois tester le point trouvé contre l'ENSEMBLE des contraintes et écarter ceux qui en violent une. Ici, par exemple, $x=0$ et $y=2x$ se coupent aussi en l'origine, ce qui ne crée pas de nouveau sommet, et $x=0$ avec $x+y=6$ donnerait $(0\,;6)$, un point qui viole $y\leq 2x$ puisque $6\leq 0$ est faux : il est donc rejeté et ne figure pas parmi les sommets.

Le théorème fondamental de la programmation linéaire justifie toute la méthode : une fonction du premier degré en $x$ et $y$ atteint son maximum et son minimum sur un polygone convexe TOUJOURS en un SOMMET. Il est donc inutile d'explorer l'intérieur ou les côtés du polygone, il suffit d'évaluer la fonction aux sommets et de comparer les valeurs obtenues.

a) $F(x\,;y)=3x+2y$ évaluée aux trois sommets. $F(A)=F(0\,;0)=3\times 0+2\times 0=0$. $F(B)=F(6\,;0)=3\times 6+2\times 0=18$. $F(C)=F(2\,;4)=3\times 2+2\times 4=6+8=14$.

b) On compare les trois valeurs, $0$, $18$ et $14$. La fonction est MAXIMALE au sommet $B(6\,;0)$, où elle vaut $18$, et MINIMALE au sommet $A(0\,;0)$, où elle vaut $0$. Une observation qui mérite d'être faite, car elle surprend : le sommet $C(2\,;4)$, pourtant le plus éloigné de l'origine en apparence et le seul à combiner les deux ressources, n'est PAS optimal. C'est que la fonction objectif pèse davantage $x$, avec un coefficient $3$, que $y$, avec $2$, si bien qu'il vaut mieux tout mettre sur $x$. Vérification que la conclusion tient bien : en un point intérieur quelconque, par exemple $(3\,;1)$, on a $F=9+2=11$, bien en dessous du maximum $18$ ✓, conformément au théorème.

a) On applique $R(x\,;y)=4x+5y$ aux quatre sommets. $R(O)=R(0\,;0)=0$. $R(A)=R(0\,;4)=4\times 0+5\times 4=20$. $R(B)=R(3\,;5)=4\times 3+5\times 5=12+25=37$. $R(C)=R(6\,;0)=4\times 6+5\times 0=24$.

b) Le maximum des quatre valeurs $0$, $20$, $37$ et $24$ est $37$, atteint au sommet $B(3\,;5)$. La production qui maximise le revenu est donc $x=3$ et $y=5$, pour un revenu de $37$. Contraste instructif avec l'exercice précédent : ici c'est bien le sommet INTÉRIEUR, celui qui combine les deux productions, qui l'emporte, alors qu'au 3 c'était un sommet d'axe. La raison est le rapport des coefficients : ici $4$ et $5$ sont proches, donc aucune des deux variables n'écrase l'autre et le mélange devient rentable. Retenez qu'on ne peut pas deviner le sommet optimal en regardant le polygone, il faut CALCULER les quatre valeurs.

Contrôle de cohérence à faire systématiquement : le maximum doit être atteint sur la frontière la plus éloignée de l'origine dans la direction où la fonction croît, et $37$ dépasse bien les trois autres valeurs. Un contrôle supplémentaire consiste à tester un point intérieur, par exemple $(2\,;2)$, où $R=8+10=18$, inférieur au maximum ✓.

a) Pour tracer, on procède droite par droite. Chaque frontière se trace par DEUX points, généralement ses intersections avec les axes. Pour $x+y=5$ : en $x=0$ on a $y=5$, en $y=0$ on a $x=5$, on relie $(0\,;5)$ et $(5\,;0)$. Pour $y=x+1$ : en $x=0$ on a $y=1$, en $x=2$ on a $y=3$, on relie $(0\,;1)$ et $(2\,;3)$. On détermine ensuite le bon côté de chaque droite avec un POINT-TEST, l'origine étant le plus commode quand elle n'est pas sur la droite : $0+0=0\leq 5$ ✓, donc on garde le côté de l'origine ; $0\leq 0+1$ ✓, donc on garde encore le côté de l'origine. Le polygone est l'intersection des quatre demi-plans, dans le premier quadrant.

b) Les quatre sommets s'obtiennent en croisant les frontières deux à deux, puis en filtrant. $x=0$ et $y=0$ donnent $(0\,;0)$ ✓. $y=0$ et $x+y=5$ donnent $(5\,;0)$, qui vérifie $0\leq 6$ ✓. $y=x+1$ et $x+y=5$ donnent $(2\,;3)$, calculé en c) ✓. $x=0$ et $y=x+1$ donnent $(0\,;1)$, qui vérifie $0+1\leq 5$ ✓. Les quatre sommets sont donc $(0\,;0)$, $(5\,;0)$, $(2\,;3)$ et $(0\,;1)$. Il faut les énumérer dans l'ordre du contour, en tournant, sinon le polygone tracé se croise lui-même.

c) On résout le système $y=x+1$ et $x+y=5$ par substitution : $x+(x+1)=5$, donc $2x+1=5$, puis $2x=4$ et $x=2$. Alors $y=2+1=3$. Le sommet est $(2\,;3)$. Vérification dans les deux équations : $3=2+1$ ✓ et $2+3=5$ ✓. Contrôle final que ce point respecte aussi les positivités, ce qui est évident ici ✓. Notez que l'intersection $x=0$ avec $x+y=5$ donnerait $(0\,;5)$, un point qui viole $y\leq x+1$ puisque $5\leq 1$ est faux : il est rejeté et n'est pas un sommet, ce qui explique que le polygone en ait quatre et non cinq.

a) On traduit chaque ressource en une inéquation, en additionnant ce que consomme chaque produit. Pour le TRAVAIL : chaque chaise demande $2$ h et chaque table $4$ h, le total $2x+4y$ ne peut dépasser $40$, d'où $2x+4y\leq 40$. Pour les PLANCHES : chaque chaise en demande $3$ et chaque table $2$, d'où $3x+2y\leq 30$. Il faut enfin ajouter les contraintes de positivité, $x\geq 0$ et $y\geq 0$, que l'énoncé ne dit pas mais qui sont imposées par le contexte : on ne fabrique pas un nombre négatif de chaises. Les oublier est une erreur classique, et elle change le polygone.

b) Le bénéfice total additionne les bénéfices unitaires multipliés par les quantités : $B(x\,;y)=15x+30y$. C'est la fonction OBJECTIF, celle qu'on cherchera à maximiser, et elle est du premier degré comme toujours en programmation linéaire.

c) On teste $(4\,;6)$ contre les deux contraintes de ressources. Travail : $2\times 4+4\times 6=8+24=32$, or $32\leq 40$ ✓, il reste même $8$ heures inutilisées. Planches : $3\times 4+2\times 6=12+12=24$, or $24\leq 30$ ✓, il reste $6$ planches. Les positivités sont évidemment vérifiées. La production est donc RÉALISABLE, avec du surplus sur les deux ressources.

d) $B(4\,;6)=15\times 4+30\times 6=60+180=240$ dollars. Un commentaire qui prépare la suite du chapitre : cette production est réalisable mais rien ne dit qu'elle soit OPTIMALE, et le surplus constaté en c) suggère justement qu'on pourrait produire davantage. C'est bien le cas : le sommet $(0\,;10)$ satisfait les deux contraintes, puisque $4\times 10=40\leq 40$ et $2\times 10=20\leq 30$, et rapporte $B=300$ dollars, soit $60$ de plus. La leçon est qu'une solution admissible n'est pas une solution optimale, et que seule l'évaluation à tous les sommets permet de conclure.

a) On teste $(20\,;30)$ contre CHAQUE contrainte, sans s'arrêter à la première satisfaite. Assemblage : $20+30=50$, or $50\leq 50$ ✓, la contrainte est tout juste respectée. Découpe : $2\times 20+3\times 30=40+90=130$, or $130>120$ ✗, la contrainte est VIOLÉE. La réponse est donc NON. C'est exactement le piège annoncé par le titre : un élève qui vérifie l'assemblage, la trouve satisfaite et conclut, perd la question. Il suffit d'UNE contrainte violée pour rejeter un couple, alors qu'il faut TOUTES les vérifier pour l'accepter.

b) Les sommets sur les axes d'abord. Origine : $(0\,;0)$. Sur l'axe des $x$, on prend la contrainte la plus SERRÉE : $2x\leq 120$ donne $x\leq 60$, tandis que $x\leq 50$ vient de l'assemblage, donc c'est $50$ qui l'emporte et le sommet est $(50\,;0)$. Sur l'axe des $y$ : $3y\leq 120$ donne $y\leq 40$, contre $y\leq 50$ pour l'assemblage, donc c'est $40$ et le sommet est $(0\,;40)$. Sommet intérieur, à l'intersection des deux obliques : de $x+y=50$ on tire $y=50-x$, qu'on reporte dans $2x+3y=120$, ce qui donne $2x+3(50-x)=120$, soit $2x+150-3x=120$, donc $-x=-30$ et $x=30$, puis $y=20$. Sommet $(30\,;20)$. Vérification : $2\times 30+3\times 20=60+60=120$ ✓ et $30+20=50$ ✓, les deux contraintes sont saturées.

c) $F(x\,;y)=40x+30y$ aux quatre sommets. $F(0\,;0)=0$. $F(50\,;0)=2000$. $F(30\,;20)=1200+600=1800$. $F(0\,;40)=1200$. Le maximum est $2000$ dollars, atteint en $(50\,;0)$ : l'usine doit produire $50$ tables et AUCUNE chaise. Résultat contre-intuitif mais parfaitement logique : une table rapporte $40$ dollars et ne consomme qu'une heure d'assemblage, tandis qu'une chaise n'en rapporte que $30$ ; la table est donc plus rentable sur la ressource qui limite réellement.

d) Avec $G(x\,;y)=40x+45y$, on réévalue aux mêmes sommets, le polygone n'ayant pas changé : $G(0\,;0)=0$ ; $G(50\,;0)=2000$ ; $G(30\,;20)=1200+900=2100$ ; $G(0\,;40)=1800$. L'optimum passe donc au sommet $(30\,;20)$, avec $2100$ dollars. Ce que cela illustre est le cœur de la méthode : la solution optimale dépend de la PENTE de la fonction objectif, autrement dit du rapport de ses coefficients, et non seulement du polygone. Géométriquement, on fait glisser une droite $40x+cy=\text{constante}$ le plus loin possible dans le polygone, et c'est son inclinaison qui décide du dernier sommet touché. Conséquence pratique très concrète : une simple révision du prix de vente d'un produit peut faire basculer toute la stratégie de production, sans qu'aucune ressource ni aucune contrainte n'ait bougé.

a) Pour $(12\,;6)$ : $12\geq 10$ ✓ ; $6\geq 5$ ✓ ; mais le total vaut $12+6=18$, et la contrainte exige $x+y\geq 20$, or $18<20$ ✗. Le couple n'est PAS admissible. Pour $(10\,;8)$ : $10\geq 10$ ✓ ; $8\geq 5$ ✓ ; total $10+8=18$, encore inférieur à $20$ ✗. Il n'est pas admissible non plus. Les deux échouent donc sur la même contrainte, celle du total MINIMAL, et non sur les minima individuels qui étaient respectés. C'est ce que teste la question : une contrainte de type « au moins », écrite $\geq$, se viole en étant trop PETIT, à l'inverse des contraintes $\leq$ habituelles.

b) Les quatre frontières sont $x=10$, $y=5$, $x+y=20$ et $x+y=60$, et chaque sommet croise deux d'entre elles. $x=10$ et $x+y=20$ donnent $y=10$, soit $(10\,;10)$. $y=5$ et $x+y=20$ donnent $x=15$, soit $(15\,;5)$. $y=5$ et $x+y=60$ donnent $x=55$, soit $(55\,;5)$. $x=10$ et $x+y=60$ donnent $y=50$, soit $(10\,;50)$. Chacun vérifie bien les quatre contraintes ✓. Notez que les deux droites $x+y=20$ et $x+y=60$ sont PARALLÈLES et ne se coupent jamais : le polygone est donc une bande oblique tronquée par les deux minima, ce qui lui donne quatre côtés.

c) $C(x\,;y)=3x+2y$ aux quatre sommets. $C(10\,;10)=30+20=50$. $C(15\,;5)=45+10=55$. $C(55\,;5)=165+10=175$. $C(10\,;50)=30+100=130$. Le MINIMUM est $50$ dollars, atteint en $(10\,;10)$ : la composition la moins coûteuse est $10$ barres et $10$ boissons. On cherche bien ici un minimum et non un maximum, et il faut lire la consigne : appliquer machinalement « on prend la plus grande valeur » donnerait $175$, exactement la pire réponse.

d) Pour un MINIMUM, l'optimum se colle aux petites valeurs, donc à la frontière $x+y=20$ : les deux sommets qui la portent, $(10\,;10)$ et $(15\,;5)$, donnent $50$ et $55$, tandis que ceux de la frontière $x+y=60$ donnent $175$ et $130$, bien plus. La contrainte $x+y\leq 60$ est donc INACTIVE : on pourrait la supprimer, ou la remplacer par $x+y\leq 1000$, sans changer la solution optimale. Elle deviendrait en revanche indispensable si l'on cherchait à MAXIMISER $C$ : sans elle, le polygone serait non borné vers le haut, $x$ et $y$ pourraient croître indéfiniment et le coût aussi, si bien qu'AUCUN maximum n'existerait. C'est elle qui ferme le polygone et rend le problème bien posé, l'optimum étant alors $(55\,;5)$ avec $175$ dollars. Retenez le principe : une contrainte peut être inactive pour un objectif et décisive pour un autre, et un problème de maximisation exige toujours un polygone BORNÉ dans la direction où la fonction croît.

a) On traduit chaque ressource. Oranges : un litre de jus d'orange en consomme $3$ kg et le jus de pomme n'en consomme pas, d'où $3x\leq 240$, soit $x\leq 80$. Pommes : $2y\leq 120$, soit $y\leq 60$. Embouteillage : la ligne traite au plus $120$ L au total, tous jus confondus, d'où $x+y\leq 120$. Positivités : $x\geq 0$ et $y\geq 0$. Objectif : maximiser $P(x\,;y)=2x+1{,}5y$. Notez la structure particulière de ce problème : les deux premières contraintes ne portent chacune que sur UNE variable, ce sont des droites verticale et horizontale, et seule la troisième est oblique.

b) Les cinq sommets, en tournant le long du contour. $(0\,;0)$, l'origine. $(80\,;0)$, croisement de $y=0$ et $x=80$ ; vérification : $80+0=80\leq 120$ ✓. $(80\,;40)$, croisement de $x=80$ et $x+y=120$, puisque $y=120-80=40$ ; vérification : $40\leq 60$ ✓. $(60\,;60)$, croisement de $y=60$ et $x+y=120$, puisque $x=120-60=60$ ; vérification : $60\leq 80$ ✓. $(0\,;60)$, croisement de $x=0$ et $y=60$ ; vérification : $0+60\leq 120$ ✓. Le polygone a donc cinq côtés, ce qui est normal avec cinq contraintes toutes actives quelque part.

c) Tableau des valeurs de $P(x\,;y)=2x+1{,}5y$. Sommet $(0\,;0)$ : $P=0$. Sommet $(80\,;0)$ : $P=160+0=160$. Sommet $(80\,;40)$ : $P=160+60=220$. Sommet $(60\,;60)$ : $P=120+90=210$. Sommet $(0\,;60)$ : $P=0+90=90$. Le maximum est $220$ dollars, atteint en $(80\,;40)$ : l'entreprise doit produire $80$ L de jus d'orange et $40$ L de jus de pomme. Observez que le second meilleur sommet, $(60\,;60)$, n'est qu'à $10$ dollars derrière : l'écart est faible, ce qui signifie que la solution est peu robuste et qu'une petite variation des prix pourrait la faire basculer, exactement comme à l'exercice 7.

d) On vérifie chaque ressource au sommet optimal $(80\,;40)$. Oranges : $3\times 80=240$ kg consommés sur $240$ disponibles, la ressource est SATURÉE. Embouteillage : $80+40=120$ L sur $120$, SATURÉE également. Pommes : $2\times 40=80$ kg consommés sur $120$ disponibles, donc un SURPLUS de $120-80=40$ kg de pommes, soit un tiers de l'approvisionnement inutilisé. Interprétation pour l'entreprise, qui est le vrai livrable de la question : pour augmenter le profit, il faudrait obtenir plus d'ORANGES ou plus de capacité d'EMBOUTEILLAGE, les deux ressources qui bloquent. Acheter plus de pommes ne servirait strictement à rien, puisqu'on n'utilise déjà pas celles qu'on reçoit. C'est la lecture la plus utile d'un résultat de programmation linéaire : les contraintes saturées désignent les goulots d'étranglement, celles qui ne le sont pas désignent le gaspillage.

a) Le temps de travail : un bracelet et un collier prennent chacun $1$ heure, et l'artisan dispose d'au plus $8$ heures, d'où $x+y\leq 8$. Les perles : l'énoncé fournit directement $x+3y\leq 12$, un collier en consommant trois fois plus qu'un bracelet. Les quantités ne peuvent être négatives, d'où $x\geq 0$ et $y\geq 0$. Le système est donc $x\geq 0$, $y\geq 0$, $x+y\leq 8$ et $x+3y\leq 12$.

b) On croise les frontières deux à deux, en gardant à chaque fois la contrainte la plus SERRÉE. Origine : $(0\,;0)$. Sur l'axe des $x$, où $y=0$ : la première contrainte donne $x\leq 8$ et la seconde $x\leq 12$, donc c'est $8$ qui limite et le sommet est $(8\,;0)$ ; le point $(12\,;0)$ est rejeté car il violerait $x+y\leq 8$. Sur l'axe des $y$, où $x=0$ : la première donne $y\leq 8$ et la seconde $y\leq 4$, donc c'est $4$ qui limite et le sommet est $(0\,;4)$. Intersection des deux obliques : on soustrait $x+y=8$ de $x+3y=12$, ce qui élimine $x$ d'un coup et donne $2y=4$, donc $y=2$ puis $x=8-2=6$, soit le sommet $(6\,;2)$. Les quatre sommets sont $(0\,;0)$, $(8\,;0)$, $(6\,;2)$ et $(0\,;4)$.

c) $P=2x+3y$ aux quatre sommets. $P(0\,;0)=0$. $P(8\,;0)=16+0=16$. $P(6\,;2)=12+6=18$. $P(0\,;4)=0+12=12$. Le maximum est $P=18$, atteint au sommet $(6\,;2)$. L'artisan doit donc produire $6$ bracelets et $2$ colliers par jour, pour un profit de $18$ dizaines de dollars, soit $180$ dollars. Le théorème fondamental est une fois de plus confirmé : l'optimum d'une fonction linéaire sur un polygone est toujours en un SOMMET, il suffit donc d'en comparer un nombre fini au lieu d'explorer une infinité de points.

d) Au sommet $(6\,;2)$, on teste chaque contrainte. Travail : $x+y=6+2=8$, exactement la limite de $8$ heures, donc SATURÉE. Perles : $x+3y=6+6=12$, exactement la réserve, donc SATURÉE elle aussi. Les DEUX contraintes obliques sont donc actives simultanément, ce qui est la situation typique d'un sommet intérieur optimal : l'artisan travaille à pleine capacité sur ses deux ressources à la fois, sans gaspiller ni temps ni perles. Les contraintes de positivité, elles, ne sont PAS actives puisque $x=6>0$ et $y=2>0$. Lecture économique, et c'est la question qu'un patron poserait : puisque les deux ressources sont saturées, augmenter la production exigerait d'augmenter les DEUX, une heure de plus ne servant à rien sans perles supplémentaires, et inversement. Contrôle du raisonnement : avec une heure de travail en plus, le sommet deviendrait l'intersection de $x+y=9$ et $x+3y=12$, soit $y=1{,}5$ et $x=7{,}5$, pour un profit de $15+4{,}5=19{,}5$, un gain réel mais faible qui montre bien que le temps n'est pas le seul verrou.