Video Transcript
Dans cette vidéo, on va apprendre comment trouver la solution optimale d’un système linéaire qui a une fonction objectif et de multiples contraintes. La méthode qu’on va utiliser pour trouver cette solution optimale s’appelle la programmation linéaire. Commençons par définir ce terme.
La programmation linéaire est une méthode qui permet de trouver une solution optimale c’est-à-dire maximale ou minimale pour une fonction objectif du premier degré bornée par des contraintes représentées par des inéquations du premier degré. Considérons une fonction affine qui est une fonction à deux variables 𝑥 et 𝑦 telle que 𝑓 de 𝑥, 𝑦 égale 𝑎𝑥 plus 𝑏𝑦 plus 𝑐. On l’appelle la fonction objectif et elle est définie pour toutes valeurs de 𝑥 et 𝑦. Comme indiqué dans la méthode de programmation linéaire, on inclut également des contraintes représentées par des inéquations du premier degré. Par exemple, 𝑥 et 𝑦 peuvent être supérieur ou égal à zéro. On peut également avoir des contraintes impliquant les deux variables. Par exemple, 𝑥 plus 𝑦 est inférieur ou égal à cinq.
Étant donné cette fonction objectif et un ensemble de contraintes, on doit trouver une solution optimale qui maximisera ou minimisera la fonction objectif. On peut représenter cela sur un graphique bidimensionnel. Commençons par tracer un plan cartésien comme indiqué. On peut maintenant utiliser les contraintes pour trouver une région correspondante sur le graphique. Premièrement, puisque 𝑥 est supérieur ou égal à zéro, on peut tracer une droite à 𝑥 égale zéro. Dans ce cas, il s’agit d’une droite pleine. Cependant, si l’inégalité était une inégalité stricte, 𝑥 est supérieur à zéro, on utiliserait une droite pointillée.
À ce stade, on peut ombrager l’extérieur ou l’intérieur de la région qui nous intéresse. On sait que toutes les valeurs de 𝑥 à gauche de cette droite verticale seront en dehors de notre région. Donc, dans cet exemple, on va hachurer l’extérieur de la région. On peut faire quelque chose de similaire avec la prochaine contrainte. Puisque 𝑦 est supérieur ou égal à zéro, On peut tracer une droite à 𝑦 égale zéro. La région sous l’axe des 𝑥 ne sera pas dans notre région réalisable. Considérons maintenant la troisième contrainte. 𝑥 plus 𝑦 est inférieur ou égal à cinq. Afin de représenter cela sur notre graphique, on va d’abord tracer la droite de l’équation 𝑥 plus 𝑦 égale cinq. Lorsqu’on substitue 𝑥 est égal à zéro dans cette équation on a 𝑦 est égal à cinq. De même, lorsque 𝑦 est égal à zéro, 𝑥 est égal à cinq. On peut donc conclure que, les points avec pour coordonnées zéro, cinq et cinq, zéro seront sur cette droite.
Ensuite, on doit déterminer quelle région du graphique représente cette inéquation du premier degré. Une façon de le faire est d’écrire une expression pour 𝑦. Si on soustrait 𝑥 des deux côtés de l’inégalité, on a 𝑦 est inférieur ou égal à moins 𝑥 plus cinq. Cela signifie que la droite tracée a pour équation 𝑦 égale moins 𝑥 plus cinq. Par conséquent, la région où la coordonnée 𝑦 est inférieure à moins 𝑥 plus cinq est en dessous de la droite car c’est là que les coordonnées 𝑦 sont plus petites. On peut donc hachurer la région au-dessus de la droite. On a maintenant une région hachurée en vert qui correspond aux trois contraintes. C’est ce qu’on appelle la région réalisable. Et tout point situé en dehors de cette région enfreint au moins une des contraintes.
Tout point dans cette région réalisable est une potentielle solution optimale pour la fonction objectif. Cependant, cela nous pose un problème, car il existe un nombre infini de solutions dans cette région. Et c’est là qu’une propriété incroyable de cette méthode intervient. Chaque fois qu’on a une région réalisable bien définie, comme dans ce cas, les seuls points que nous devons vérifier pour une solution optimale sont les sommets de la région réalisable, dans ce cas les points avec les coordonnées zéro, zéro ; zéro, cinq ; et cinq, zéro. Ce sont les seuls points où on peut avoir une valeur maximale ou minimale. Afin de comprendre pourquoi c’est le cas, considérons une représentation tridimensionnelle.
En général, notre fonction objectif prend deux variables, dans ce cas 𝑥 et 𝑦. Et cette fonction a une certaine valeur. On va l’appeler une valeur 𝑧. Et on peut tracer cela sur un axe des 𝑧 du repère. Puisque notre fonction objectif a des valeurs 𝑥 et 𝑦, elle ne sera pas représentée par une droite, mais plutôt par un plan. En d’autres termes, si on devait tracer la fonction objectif pour toutes les valeurs de 𝑥 et 𝑦, on aurait un plan qui ressemble à ceci, où les points sur ce plan représentent toutes des valeurs de 𝑧 ou de la fonction objectif pour chaque combinaison possible de valeurs d’entrée 𝑥 et 𝑦. Cela signifie que 𝑧 pourrait être plus l’infini ou moins l’infini. Cependant, pour un problème de programmation linéaire, seul un sous-ensemble de ces valeurs de 𝑧 est possible. Ce sont les valeurs de 𝑧 qui correspondent aux valeurs 𝑥 et 𝑦 dans la région réalisable.
Pour voir quel est cet ensemble réalisable de valeurs de 𝑧, on peut projeter vers le haut sur le plan. Lorsqu’on fait cela, on crée une autre région triangulaire. Mais celle-ci suit la pente de notre plan. Si on considère les sommets de la région réalisable dans le repère cartésien, on remarque que ceux-ci correspondent aux valeurs maximales et minimales de 𝑧. Cela signifie que la solution maximale et minimale est située sur l’un de ces sommets. Bien que cela ne soit pas une preuve concluante que la solution optimale se situe à l’un des sommets de la région réalisable, cela suggère au moins que cela est plausible. Cependant, cela est vrai. Peu importe le type de plan qu’on a et son inclinaison, lorsqu’on projette la région réalisable sur celui-ci, un ou plusieurs sommets représentent la solution optimale.
En résumé, pour trouver une solution optimale, on substitue les coordonnées des sommets de la région réalisable dans la fonction objectif. Faire cela pour tous les sommets nous permet de trouver la solution maximale et minimale. Voyons maintenant comment cela fonctionne en pratique.
En utilisant la programmation linéaire, déterminez les valeurs minimale et maximale de la fonction 𝑝 est égale à quatre 𝑥 moins trois 𝑦 étant donné que 𝑥 est supérieur ou égal à zéro, 𝑦 est supérieur ou égal à zéro, 𝑥 plus 𝑦 est inférieur ou égal à neuf, et 𝑦 est supérieur ou égal à cinq.
En plus des informations de la question, on nous donne un graphique qui montre la région réalisable pour nos contraintes. Il y a quatre contraintes représentées par des inéquations du premier degré. Notons que puisque 𝑦 doit être supérieur ou égal à zéro et supérieur ou égal à cinq, on peut juste considérer la deuxième inéquation. Ceci est représenté par la droite horizontale passant par cinq sur l’axe des 𝑦. L’inéquation 𝑥 est supérieur ou égal à zéro est représentée par la droite 𝑥 est égal à zéro. Et la région réalisable est tout ce qui se trouve sur ou à droite de cette droite, toutes les valeurs de 𝑥 supérieures ou égales à zéro.
Enfin, on a la droite 𝑥 plus 𝑦 égale neuf. Et puisque 𝑥 plus 𝑦 est inférieur ou égal à neuf ou 𝑦 est inférieur ou égal à moins 𝑥 plus neuf, alors la région réalisable contient tous les points sur ou en dessous de cette droite. Si notre inégalité était strictement inférieure à, la région réalisable serait juste en dessous de la droite.
Dans cette question, on nous demande de trouver les valeurs minimale et maximale de la fonction 𝑝 égale quatre 𝑥 moins trois 𝑦. Et en utilisant la programmation linéaire, on sait que celles-ci se trouvent à l’un des sommets de notre région réalisable. Ces trois sommets ont des coordonnées zéro, cinq ; zéro, neuf ; et quatre, cinq. Ce n’est qu’à ces valeurs que notre fonction peut être optimale, c’est-à-dire avoir une valeur minimale ou maximale. Si on substitue 𝑥 par zéro et 𝑦 par cinq dans la fonction, on a 𝑝 est égal à quatre multiplié par zéro moins trois multiplié par cinq. Cela est égal à moins 15. Au point zéro, neuf, on a 𝑝 est égal à quatre multiplié par zéro moins trois multiplié par neuf. Qui est égal à moins 27.
Enfin, au sommet de la région réalisable, où 𝑥 est égal à quatre et 𝑦 est égal à cinq, on a 𝑝 est égal à un. Nous choisissons simplement la valeur minimale et maximale de ces trois résultats. Nous voyons que moins 27 est la valeur minimale et un est la valeur maximale. Les valeurs minimale et maximale de la fonction 𝑝 est égale à quatre 𝑥 moins trois 𝑦 soumise aux contraintes données sont moins 27 et un.
On va maintenant traiter un deuxième exemple dans son contexte.
Une petite entreprise teint des chemises de couleur unie ou tie-dye, et elle veut décider du nombre de chemises de chaque couleur à produire pour une vente à venir. L’entreprise a un budget de 240 dollars. Acheter une chemise non teintée coute deux dollars. Teindre une chemise de couleur unie coute 0,5$ de plus tandis que teindre avec un motif tie-dye en coute 1,5$. L’entreprise n’a que huit heures pour fabriquer toutes les chemises pour la vente. Et il faut deux minutes pour produire une chemise de couleur unie et 10 minutes pour produire une chemise tie-dye. Ils décident de faire une représentation graphique pour maximiser leurs profits, sachant qu’ils gagnent huit dollars pour chaque chemise de couleur unie et 10 dollars pour chaque chemise tie-dye. Soit 𝑥 le nombre de chemises de couleur unie et 𝑦 le nombre de chemises tie-dye.
Cette question comporte trois parties, qu’on va examiner sous peu. Avant de faire cela, considérons certaines des informations qui nous sont données. Il existe deux types de chemises fabriquées par l’entreprise, les chemises de couleur unie représentées par 𝑥 et les chemises tie-dye représentées par 𝑦. On va résoudre ce problème en utilisant la programmation linéaire en définissant d’abord une fonction objectif et quelques contraintes sous forme d’inéquations du premier degré. L’entreprise veut maximiser son profit. Et on nous dit qu’ils gagnent huit dollars pour chaque chemise de couleur unie et 10 dollars pour chaque chemise tie-dye. Cela signifie que le profit en dollars 𝑃 est égal à huit 𝑥 plus 10𝑦. On peut également écrire cela comme une fonction en 𝑥 et 𝑦 telle que 𝑓 de 𝑥, 𝑦 égale huit 𝑥 plus 10𝑦.
Les contraintes imposées à l’entreprise sont à la fois temporelles et financières. Si on considère d’abord l’aspect financier, on nous dit que l’entreprise a un budget de 240 dollars. On nous dit qu’une chemise non teintée coûte deux dollars et qu’il faut 50 cents supplémentaires pour la teindre en couleur unie et un dollar 50 pour la teindre avec un motif tie-dye. Fabriquer une chemise de couleur unie coute donc deux dollars 50. Puisque l’entreprise en fabrique 𝑥, on peut écrire cela comme 2,5𝑥. Fabriquer une chemise tie-dye coûte trois dollars 50. Et on peut écrire cela comme 3,5𝑦. Nous savons que la somme de ces termes doit être inférieure ou égale à 240 car le budget disponible était de 240 dollars.
Considérons maintenant les contraintes temporelles. On nous dit qu’il faut deux minutes pour produire une chemise de couleur unie et 10 minutes pour produire une chemise tie-dye. L’entreprise a huit heures ou 480 minutes pour fabriquer toutes les chemises. On peut représenter cela par l’inéquation deux 𝑥 plus 10𝑦 est inférieur ou égal à 480. On va maintenant libérer de l’espace et examiner les trois parties de cette question.
Les trois parties de la question sont les suivantes. Quelle des options suivantes représente la région réalisable ? Indiquez la fonction objectif. Combien de chaque type de chemise l’entreprise doit-elle produire pour maximiser ses profits ?
On a déjà répondu à la deuxième partie de cette question. La fonction objectif ou la fonction de profit dans cette question 𝑓 de 𝑥, 𝑦 est huit 𝑥 plus 10𝑦. Dans la première partie de cette question, on a quatre graphiques avec les droites 2,5𝑥 plus 3,5𝑦 égale 240 et deux 𝑥 plus 10𝑦 égale 480 tracées dessus. Nous savons que deux 𝑥 plus 10𝑦 doit être inférieur ou égal à 480. Cela signifie que la région réalisable se situe en dessous de cette droite. On peut donc exclure l’option (B).
On nous dit également que 2,5𝑥 plus 3,5𝑦 est inférieur ou égal à 240. La région réalisable doit donc également être située sous la droite bleue sur nos graphiques. Cela exclut l’option (C). Pour décider si le graphique (A) ou le graphique (D) est le bon, on doit considérer deux autres contraintes. Puisqu’on ne peut pas faire un nombre négatif de chemises, 𝑥 et 𝑦 doivent être chacun supérieur ou égal à zéro. Cela signifie que la région réalisable doit être située au-dessus de l’axe des 𝑥 et à droite de l’axe des 𝑦. On peut donc exclure l’option (A) puisqu’une partie de la région réalisable est dans la région 𝑥 inférieur à zéro. La bonne réponse à la première partie de notre question est donc l’option (D).
On va maintenant libérer de l’espace et résoudre la troisième partie de cette question. On rappelle que nous devons déterminer le nombre de chaque type de chemise que l’entreprise doit produire pour maximiser ses profits. On rappelle aussi que la fonction de profit ou objectif était huit 𝑥 plus 10𝑦 et que la région réalisable était soumise à quatre contraintes. On sait que les potentielles valeurs maximales de la fonction se trouvent aux sommets de la région réalisable. On va donc commencer par déterminer les coordonnées de ces points. Tout d’abord, on a le point zéro, zéro. On sait que lorsqu’une droite coupe l’axe des 𝑥, 𝑦 est égal à zéro. Et lorsqu’on introduit cela dans l’équation, 2,5𝑥 plus 3,5𝑦 égale 240, on obtient 𝑥 est égal à 96. Les coordonnées de ce sommet sont donc 96, zéro.
De même, lorsqu’une droite coupe l’axe des 𝑦, la coordonnée 𝑥 est zéro. Lorsqu’on substitue cela dans l’équation deux 𝑥 plus 10𝑦 égale 480 on obtient 𝑦 est égal à 48 et un autre sommet à zéro, 48. Le quatrième sommet de notre région réalisable est le point d’intersection de nos deux droites diagonales. Une façon de résoudre ce problème serait de trouver une solution des équations simultanées indiquées. Il existe plusieurs façons de les résoudre. Une façon est de multiplier la deuxième équation par deux. Cela nous donne l’équation cinq 𝑥 plus sept 𝑦 égale 480.
Si on réécrit la première équation en dessous puis on soustrait les deux équations, on a trois 𝑥 moins trois 𝑦 égale zéro. Si on ajoute trois 𝑦 aux deux côtés de cette équation, et on divise ensuite par trois, on voit que 𝑥 est égal à 𝑦. On peut ensuite substituer cela dans la première équation de telle sorte que deux 𝑦 plus 10𝑦 soit égal à 480. Lorsqu’on résout cela, on a 𝑦 égale 40 et puisque 𝑥 est aussi égal à cela. Le quatrième sommet a les coordonnées 40, 40.
On peut maintenant substituer chacune de ces coordonnées tour à tour dans notre fonction objectif. Il est important de noter ici que l’un de ces points pourrait être la solution optimale et que ce ne sera pas nécessairement le point d’intersection que nous venons de trouver. Lorsqu’on substitue les valeurs de 𝑥 et 𝑦, la fonction objectif est égale à zéro, 480, 768 et 720. Sachant que l’entreprise veut maximiser son profit, elle choisit la valeur la plus élevée. Puisque 𝑥 représente le nombre de chemises de couleur unie et 𝑦 le nombre de chemises tie-dye, produire 96 chemises de couleur unie et zéro chemise teinte maximiserait le profit. En supposant que toutes les chemises soient vendues, cela rapporterait un bénéfice de 768 dollars.
On va maintenant résumer les points clés de cette vidéo. La programmation linéaire est une méthode qui permet de trouver une solution optimale pour une fonction objectif de premier degré bornée par des contraintes représentées par des inéquations de premier degré. On a vu que la région bornée par les contraintes est la région réalisable et que les solutions optimales se trouvent aux sommets de cette région.
