Lorsqu’on résout un problème d’optimisation, on cherche la solution qui maximise ou minimise la fonction à optimiser qui, elle, est déterminée selon un objectif. On le fait en respectant des contraintes qui sont représentées sous la forme d’un système d’inéquations. Dans le plan cartésien, ces inéquations forment un polygone de contraintes et l’un des sommets de ce polygone correspond à la solution recherchée.
-
Identifier les variables.
Pour déterminer les variables, on doit s’intéresser aux éléments qui varient et non à l’élément qu’on cherche à optimiser. Dans les problèmes étudiés au secondaire, il y a toujours 2 variables seulement.
-
Traduire les contraintes par un système d'inéquations.
Chaque contrainte est associée à une seule inéquation. De plus, si les variables représentent des quantités qui ne peuvent pas être négatives, on doit poser les contraintes de positivité (non-négativité). Voici un tableau contenant quelques expressions qu’on retrouve régulièrement dans les contraintes ainsi que les inégalités qu’elles représentent.
|
Symbole |
Mots-clés |
|---|---|
|
|x<y| |
|x| est plus petit que |y,| |x| est inférieur à |y,| |x| vaut (strictement) moins que |y,| etc. |
|
|x\leq y| |
|x| est plus petit ou égal à |y,| |x| est inférieur ou égal à |y,| |x| ne doit pas dépasser |y,| |x| est au maximum égal à |y,| |x| vaut au plus autant que |y,| etc. |
|
|x>y| |
|x| est plus grand que |y,| |x| est supérieur à |y,| |x| doit dépasser |y,| |x| vaut (strictement) plus que |y,| etc. |
|
|x\geq y| |
|x| est plus grand ou égal à |y,| |x| est supérieur ou égal à |y,| |x| est au minimum égal à |y,| |x| vaut au moins autant que |y,| etc. |
-
Établir la règle de la fonction à optimiser |\boldsymbol{(z).}|
La fonction à optimiser s'écrit sous la forme |z=ax+by+c,| où |x| et |y| sont les variables et où |z| représente la quantité qu’on cherche à maximiser ou à minimiser. Il arrive souvent que |z| représente un cout ou un revenu. Dans ces cas, il est possible d’utiliser une autre variable, comme |C| ou |R.|
-
Tracer le polygone de contraintes.
Pour y arriver, on doit représenter toutes les inéquations dans le plan cartésien. Le polygone de contraintes représente la région du plan cartésien qui contient l’intersection des ensembles-solutions de toutes les inéquations.
-
Déterminer les coordonnées des sommets du polygone de contraintes.
Pour déterminer les coordonnées d’un sommet, on doit prendre les équations des 2 droites frontières qui forment ce sommet et résoudre le système d’équations. Pour y arriver, on peut utiliser la méthode de comparaison, la méthode de substitution ou la méthode de réduction.
-
Trouver le sommet optimal (avec un tableau ou une droite baladeuse).
Il faut remplacer |x| et |y| dans la fonction à optimiser par chaque couple déterminé à l’étape précédente. Il peut être utile de se faire un tableau pour compiler les résultats. On peut aussi utiliser la droite baladeuse pour réduire le nombre de sommets à évaluer. Il faut analyser les différentes valeurs de |z| et déterminer laquelle est la plus avantageuse selon notre objectif.
-
Donner une réponse complète.
Pour répondre à la question, on doit écrire une phrase complète dans laquelle on retrouve le couple |(x,y)| qui maximise ou minimise la fonction, ainsi que la valeur de |z| associée à ce couple.
Il existe une façon de réduire le nombre de sommets à évaluer pour trouver la solution optimale. Il s’agit de la technique de la droite baladeuse.
La droite baladeuse est une droite de pente |-\dfrac{a}{b}| qui se « balade » dans le plan cartésien, où |a| et |b| sont les paramètres de la fonction à optimiser |(z=ax+by+c).|
Lorsqu'on glisse la droite baladeuse dans le plan cartésien, le premier et le dernier sommet du polygone de contraintes que cette droite touche sont les points qui vont soit minimiser, soit maximiser la situation.
Dans l'animation ci-dessous, tu peux modifier les paramètres |a| et |b| de la fonction à optimiser à l'aide des curseurs. Tu peux également déplacer les sommets du polygone de contraintes et glisser la droite baladeuse. Pour cela, tu n'as qu'à déplacer le point vert qui est placé sur la droite baladeuse. Tu remarqueras que, lorsqu'on déplace une droite baladeuse, celle-ci garde toujours la même pente.
Pour valider ta compréhension à propos des problèmes d'optimisation de façon interactive, consulte la MiniRécup suivante.
Voici un exemple complet de résolution d’un problème d’optimisation. Dans ce problème, la solution optimale est déterminée à l’aide d’un tableau.
Mélanie gagne sa vie grâce à son troupeau de |30| chèvres qui produisent chacune au plus |20| litres de lait par semaine. Elle utilise ce lait pour créer |2| produits qu’elle vend ensuite au marché : le yogourt et la crème.
Il faut |1{,}5\ \text{L}| de lait pour faire |1\ \text{L}| de yogourt. Il faut aussi |6\ \text{L}| de lait pour produire |1\ \text{L}| de crème.
Compte tenu de la demande pour ses produits, Mélanie doit produire au moins |3| fois plus de yogourt que de crème et elle doit produire au moins |200\ \text{L}| de yogourt par semaine.
Au marché, elle vend son yogourt |36\ $| le litre et sa crème, |10\ $| le litre.
Combien de litres de yogourt et de litres de crème Mélanie doit-elle produire par semaine si elle désire maximiser ses revenus?
-
Identifier les variables
|x :| nombre de litres de yogourt produits par semaine
|y :| nombre de litres de crème produits par semaine -
Traduire les contraintes par un système d'inéquations
|
Contrainte |
Inéquation |
|---|---|
|
Il faut |1{,}5\ \text{L}| de lait pour |1\ \text{L}| de yogourt et |6\ \text{L}| de lait pour faire |1\ \text{L}| de crème. |
||1{,}5x + 6y \le 600|| |
|
La quantité de yogourt doit être au moins |3| fois plus grande que la quantité de crème. |
||x\ge 3y|| |
|
Au moins |200| litres de yogourt doivent être produits par semaine. |
||x\ge 200|| |
|
Le nombre de litres de yogourt produits par semaine ne peut pas être négatif. |
||x\ge 0|| |
|
Le nombre de litres de crème produits par semaine ne peut pas être négatif. |
||y\ge 0|| |
-
Établir la règle de la fonction à optimiser |\boldsymbol{(z)}|
Mélanie veut maximiser ses revenus. Elle vend son yogourt |36\ $/\text{L}| et sa crème |10\ $/\text{L}.| La fonction à optimiser est donc la suivante.||R = 36x + 10y||où
|R :| revenus |(\$)| pour la vente de yogourt et de crème
-
Tracer le polygone de contraintes
Remarque : Les ensembles-solutions des différentes inéquations sont représentés à l’aide des flèches.
Par ailleurs, le polygone de contraintes est un triangle. Il a donc 3 sommets. Cela implique que 2 des inéquations ne sont pas directement utilisées pour former le polygone. En effet, l’inéquation |x\ge0| n’est pas utile, puisque l’inéquation |x\ge200| implique déjà que les |x| soient supérieurs à |0.| De plus, pour des |x| supérieurs à |200,| les solutions de l’inéquation |1{,}5x+6y\le600| respectent automatiquement l’inéquation |x\ge3y.|
-
Déterminer les coordonnées des sommets du polygone de contraintes
À l'aide des méthodes pour résoudre un système d'équations linéaires, on peut déterminer les coordonnées des différents sommets du polygone de contraintes.
Coordonnées du sommet |\boldsymbol{A}|
Le sommet se trouve à l’intersection des droites |x=200| et |y=0.| Ses coordonnées sont donc les suivantes.||A(200,0)||
Coordonnées du sommet |\boldsymbol{B}|
Le sommet se trouve à l’intersection des droites |1{,}5x+6y=600| et |x=200.| Pour trouver les coordonnées, on remplace |x| dans la première équation par |200| et on trouve le |y| correspondant.||\begin{align}1{,}5x+6y&=600\\1{,}5(200)+6y&=600\\300+6y&=600\\6y&=300\\y&=50\end{align}||Ses coordonnées sont donc les suivantes.||B(200,50)||
Coordonnées du sommet |\boldsymbol{C}|
Le sommet se trouve à l’intersection des droites |1{,}5x+6y=600| et |y=0.| Pour trouver les coordonnées, on remplace |y| dans la première équation par |0| et on trouve le |x| correspondant.||\begin{align}1{,}5x+6y&=600\\1{,}5x+6(0)&=600\\1{,}5x&=600\\x&=400\end{align}||Ses coordonnées sont donc les suivantes.||C(400,0)||
-
Trouver le sommet optimal
|
Sommet du polygone |
Fonction à optimiser |
Revenus pour la vente de yogourt et de crème |
|---|---|---|
|
|A(200,0)| |
|\begin{align} R(x,y) &= 36x+10y \\ R(200,0) &= 36(200)+10(0) \\ &=7\ 200 + 0 \\ &= 7\ 200\ \$ \end{align}| |
|7\ 200\ \$| |
|
|B(200,50)| |
|\begin{align} R(x,y) &= 36x+10y \\ R(200,50) &= 36(200)+10(50) \\ &=7\ 200 + 500 \\ &= 7\ 700\ \$ \end{align}| |
|7\ 700\ \$| |
|
|C(400,0)| |
|\begin{align} R(x,y) &= 36x+10y \\ R(400,0) &= 36(400)+10(0) \\ &=14\ 400 + 0 \\ &= 14\ 400\ \$ \end{align}| |
|14\ 400\ \$| |
Mélanie veut maximiser ses revenus. Comme le sommet |C| est celui qui procure le revenu maximal, ce sont ses coordonnées qui optimisent la situation.
-
Donner une réponse complète
Mélanie doit produire |400\ \text{L}| de yogourt, mais ne pas produire de crème afin de s'assurer les revenus les plus élevés possibles, c’est-à-dire |14\ 400\ \$| par semaine.
Remarque : Dans cet exemple, on peut également utiliser la technique de la droite baladeuse afin de cibler les sommets qui optimisent la fonction avec laquelle on travaille. Il faut ensuite évaluer les 2 sommets en question dans la fonction à optimiser pour déterminer le sommet qui maximise.
Dans ce 2e exemple, on ajoute une contrainte. Cela consiste à ajouter une nouvelle inéquation qui va changer le polygone de contraintes.
Victor est vendeur de planches à roulettes. Il vend ses planches professionnelles |300\ $| et ses planches standards |50\ $.| À cause de ses finances et de la grandeur de son magasin, il doit respecter certaines contraintes quant à la quantité de planches à roulettes offertes. Le polygone ci-dessous illustre ces contraintes.
|x :| nombre de planches professionnelles
|y :| nombre de planches standards
Victor veut faire une grande vente au cours de la prochaine fin de semaine. Jean-Luc, son conseiller aux ventes, lui suggère d'avoir au plus |80| planches professionnelles dans son magasin.
Est-ce que Victor devrait suivre le conseil de Jean-Luc?
Comme Victor cherche à maximiser ses profits, la fonction à maximiser est la suivante.||z=300x+50y||
À l’aide de la fonction à optimiser, on calcule les profits à partir du polygone initial.
|
Sommet du polygone initial |
Fonction à optimiser |
Profit |
|---|---|---|
|
|A(30,90)| |
|z=300(30)+50(90)| |
|13\ 500\ \$| |
|
|B(20,40)| |
|z=300(20)+50(40)| |
|8\ 000\ \$| |
|
|C(50,10)| |
|z=300(50)+50(10)| |
|15\ 500\ \$| |
|
|D(110,50)| |
|z=300(110)+50(50)| |
|35\ 500\ \$| |
Selon le polygone initial, le profit maximal est de |35\ 500\ $.|
En ajoutant la nouvelle contrainte proposée par Jean-Luc, on obtient le polygone suivant.
On calcule le profit associé aux 2 nouveaux sommets du polygone.
|
Sommet du polygone proposé par Jean-Luc |
Fonction à optimiser |
Profit |
|---|---|---|
|
|E(80,65)| |
|z=300(80)+50(65)| |
|27\ 250\ \$| |
|
|F(80,30)| |
|z=300(80)+50(30)| |
|25\ 500\ \$| |
Réponse : On remarque qu’avec la proposition de Jean-Luc, le profit maximal serait de |27\ 250\ $.| Victor ne doit donc pas suivre le conseil de Jean-Luc, car il aurait une perte de profit de |8\ 250\ $.|
Au moment de déterminer une solution optimale pour une situation, il est possible de tomber sur des cas particuliers.
Lorsque des inéquations de contraintes comportent les symboles d’inégalité stricte |<| ou |>,| les droites ne sont pas incluses dans l’ensemble-solution. Sur le graphique, on a une ligne pointillée. Si le sommet qui optimise la fonction est sur une ou plusieurs droites pointillées, on doit rejeter cette solution, puisqu’elle ne respecte pas toutes les contraintes. Il faut donc tester les points près de ce sommet qui font partie de l’ensemble-solution et choisir le meilleur.
Selon le contexte, il arrive que les valeurs de |x| et |y| soient des nombres entiers. C’est le cas, par exemple, lorsque |x| et |y| représentent un nombre d’objets, d’animaux ou de personnes. Par contre, les coordonnées des sommets du polygone de contraintes ne sont pas nécessairement entières. Si c’est le cas, il faut alors choisir le point ayant des coordonnées entières et faisant partie de l’ensemble-solution qui optimise la situation.
Dans l’exemple suivant, ni le sommet |A| ni le sommet |B| n’ont des coordonnées entières. Si |A| est le sommet qui optimise la fonction |z,| alors le point à coordonnées entières qui est la solution optimale et qui respecte le contexte est le couple |(7,2)| ou le couple |(6,3).|
Il arrive que 2 sommets du polygone optimisent la fonction et donnent la même valeur de |z.| Lorsque c’est le cas, cela signifie que tous les points situés sur le segment qui relie ces 2 sommets sont des solutions optimales. Il y a donc plusieurs réponses possibles.
Dans l’exemple suivant, les sommets |A(3,6)| et |C(-1,-1)| maximisent tous les 2 la fonction avec une valeur |z| de |3.| Ainsi, tous les points sur le segment |\overline{AC}| l’optimisent également. Le point |D(0;0{,}75)| en est la preuve, car il donne aussi un |z| de |3.|
|
Sommet du polygone |
Règle d'optimisation |
Valeur de |\boldsymbol{z}| |
|---|---|---|
|
|A(3,6)| |
|z=-7(3)+4(6)| |
|3| |
|
|B(4,-3)| |
|z=-7(4)+4(-3)| |
|-40| |
|
|C(-1,-1)| |
|z=-7(-1)+4(-1)| |
|3| |
|
|D(0; 0{,}75)| |
|z=-7(0)+4(0{,}75)| |
|3| |
Lorsqu’une situation a plusieurs solutions optimales, il arrive que la mise en situation fournisse une fonction à optimiser supplémentaire. Cela permet d’éliminer certaines des solutions et de trouver celle qui optimise les 2 fonctions.
Dans l’exemple suivant, il y a 2 fonctions à optimiser. Il faut alors commencer par trouver les solutions qui maximisent la quantité de vivres à acheminer. À partir de ces solutions, on peut ensuite déterminer celle qui minimise le cout d’achat.
On transporte des vivres pour des sinistrés dans 2 sortes de contenants : des sacs et des caisses.
Le polygone ci-dessous représente les contraintes associées au nombre de sacs et au nombre de caisses qu’il est possible d’utiliser.
Chaque sac permet de transporter |10\ \text{kg}| de vivres et chaque caisse permet d'en transporter |25\ \text{kg}.| On veut maximiser la quantité de vivres à acheminer aux sinistrés. Par ailleurs, on peut se procurer des sacs pour |2\ \$| chacun et des caisses pour |8\ \$| chacune. On veut également minimiser les dépenses reliées à l'achat de ces contenants.
La 1re fonction à optimiser concerne la quantité de vivres à acheminer. La règle est |Q=10x+25y.| On veut la maximiser.
La 2e fonction à optimiser concerne le cout des contenants. La règle est |C=2x+8y.| On veut la minimiser.
On commence par trouver quel(s) sommet(s) maximise(nt) la 1re fonction.
|
Sommet du polygone |
Règle d'optimisation |
Quantité de vivres |
|---|---|---|
|
|A(60,61)| |
|Q=10(60)+25(61)| |
|2\ 125\ \text{kg}| |
|
|B(60,96)| |
|Q=10(60)+25(96)| |
|3\ 000\ \text{kg}| |
|
|C(85,86)| |
|Q=10(85)+25(86)| |
|3\ 000\ \text{kg}| |
Les sommets |B| et |C| permettent de maximiser la quantité de vivres à acheminer. Ainsi, tous les points sur le segment qui les relie sont des solutions. Toutefois, comme le nombre de sacs et le nombre de caisses doivent être des nombres entiers, on peut limiter les solutions aux couples suivants : |(60,96),| |(65,94),| |(70, 92),| |(75, 90),| |(80, 88)| et |(85, 86).| Pour trouver ces couples, on teste dans la règle de la droite frontière bleue toutes les valeurs entières de |x| entre |60| et |85| et on retient celles qui sont associées à une valeur de |y| entière.
Ensuite, on peut analyser ces couples à l’aide de la 2e fonction qui a pour but de minimiser le cout.
|
Couple |
Règle d'optimisation |
Cout |
|---|---|---|
|
|(60,96)| |
|C=2(60)+8(96)| |
|888\ \$| |
|
|(65,94)| |
|C=2(65)+8(94)| |
|882\ \$| |
|
|(70,92)| |
|C=2(70)+8(92)| |
|876\ \$| |
|
|(75,90)| |
|C=2(75)+8(90)| |
|870\ \$| |
|
|(80,88)| |
|C=2(80)+8(88)| |
|864\ \$| |
|
|(85,86)| |
|C=2(85)+8(86)| |
|858\ \$| |
Ainsi, avec |85| sacs et |86| caisses, on maximise la quantité de vivres à acheminer |(3\ 000\ \text{kg})| tout en minimisant le cout relié à l’achat des contenants |(858\ \$).|