L'optimisation (les polygones de contraintes)

Les polygones de contraintes (inéquations)

On appelle polygone de contraintes la forme géométrique délimitée dans un plan cartésien par la rencontre des diverses régions solutions au système d’inéquations donné. Il s’agit de la région qui contient tous les points qui sont des solutions pour toutes les inéquations données.
Voici le système d’inéquations suivant :


Si on trace chacune de ces inéquations individuellement dans un plan cartésien, on obtient :















Si on superpose toutes ces régions, on obtient une région qui est hachurée par toutes les inéquations. Cette région se nomme polygone de contraintes. Les points qui sont à l’intérieur de ce polygone sont des points solutions de toutes les inéquations.


Les points qui forment les sommets du polygone de contraintes seront particulièrement intéressants. En effet, les points formant les sommets du polygone sont ses extremums , c’est-à-dire ses valeurs maximales et minimales. Et c’est à partir de ces extremums que nous pourrons optimiser un système d’inéquations.

Optimisation

La traduction d’une situation par un système d’inéquations linéaires

Pour optimiser une fonction, il faut tout d’abord traduire chacune des contraintes du problème par une inéquation. Il faut tracer chacune de ces inéquations dans un plan cartésien pour déterminer le polygone de contraintes. Finalement il faut déterminer lequel ou lesquels des sommets du polygone de contraintes nous permettent d’optimiser notre fonction.

L’exemple suivant nous permettra d’expliquer chacune des étapes à suivre pour optimiser une fonction.

Mélanie gagne sa vie grâce à son troupeau de trente chèvres qui produisent chacune au plus 20 litres de lait par semaine. Elle transforme ce lait en deux produits qu’elle vend ensuite au marché : le yogourt et le fromage de chèvre.

Il faut 1,5 litre de lait pour faire un litre de yogourt. Il faut aussi 6 litres de lait pour produire un litre de fromage.

Compte tenu de la demande pour ces produits, Mélanie doit produire au moins trois fois plus de yogourt que de fromage et elle doit produire au moins 200 litres de yogourt par semaine.

Au marché, elle vend son yogourt 36$ le litre et son fromage 6$ le litre.

Combien de litres de yogourt et de litres de fromage, Mélanie doit-elle produire par semaine, si elle désire maximiser ses revenus ?

1. Identifions les variables

x : nombre de litres de yogourt produit par semaine;
y : nombre de litres de fromage produit par semaine.

2. Déterminons les inéquations

Première inéquation

Il faut 1,5 litre de lait pour faire un litre de yogourt. Il faut aussi 6 litres de lait pour produire un litre de fromage.

Les trente chèvres produisent chacune au maximum 20 litres de lait par semaine. Mélanie prend tout ce lait et le transforme en yogourt (1,5 litre de lait par litre de yogourt) et en fromage (6 litres de lait par litre de fromage).

On cherche d’abord la quantité maximale de lait produit. On met ensuite cette quantité en rapport avec la production de chacun des deux produits.

Quantité maximale de lait produit par semaine :

30 chèvres X 20 litres/chèvre = 600 litres de lait pour une semaine.

Ainsi, la somme du lait utiliser pour le yogourt et le fromage ne doit pas dépasser 600L

On peut donc poser l’inéquation suivante :


Deuxième inéquation

Mélanie doit produire au moins trois fois plus de yogourt que de fromage. Autrement dit, la quantité de yogourt doit être au moins trois fois plus grande que la quantité de fromage.

On peut donc poser l’inéquation suivante :


Troisième inéquation

Elle doit produire au moins 200 litres de yogourt par semaine.


Quatrième et cinquième inéquations

Dans ce problème il y a deux autres inéquations qui sont sous-entendues. Le contexte du problème nous oblige à poser aussi les deux inéquations suivantes :


En effet, le nombre de litres de yogourt et le nombre de litres de fromage ne pourront jamais être des nombres négatifs. Ce qui veut dire que les inéquations ne seront tracées que dans le premier quadrant.

En résumé, nous avons donc le système d’inéquations suivant :

La représentation graphique d’un polygone de contraintes

On représente graphiquement chacune des inéquations. Ceci nous permettra de déterminer le polygone de contraintes.

En plaçant les trois inéquations dans le graphique, on obtient ceci:



L’ensemble des solutions répondant aux trois contraintes est représenté par la superposition des trois régions solutions, jaune, bleue et rouge. Il s’agit de l’ensemble solution du problème c’est notre polygone de contrainte :


La fonction à optimiser

La fonction à optimiser c’est ce que l’on veut maximiser ou minimiser dans le problème.
Dans l’exemple, Mélanie veut maximiser ses revenus. Elle veut gagner le plus d’argent possible. Alors la fonction à optimiser sera par rapport aux revenus de Mélanie.

Dans un autre problème, on aurait pu vouloir minimiser par exemple un temps de production alors la fonction à optimiser aurait été construite à partir des données pour le temps de production.

Posons la fonction à optimiser.

Puisqu’on veut maximiser les revenus et bien ce sont les informations suivantes qui vont être utilisées pour écrire mathématiquement la fonction à optimiser ou la règle d’optimisation :

Au marché, elle vend son yogourt 36$ le litre et son fromage 6$ le litre.

Donc nous pouvons écrire que les revenus de Mélanie sont calculés de la façon suivante :

R=36x+6y

(où R représente les revenus)

La recherche des solutions

Ce sont les extremums du polygone de contrainte qui permettront de maximiser ou minimiser une fonction d’optimisation. Il faut donc trouver les coordonnées des sommets de notre polygone de contraintes.

Les sommets de notre polygone de contraintes sont formés par la rencontre de deux droites. Les coordonnées du point d’intersection se trouvent à être le couple solution d’un système de deux équations linéaires. Pour trouver les coordonnées des sommets du polygone, il faudra donc résoudre chacun des systèmes d’équations. Il existe plusieurs méthodes pour résoudre un système d’équations linéaires .

Trouvons les coordonnées des sommets du polygone de contraintes


On peut utiliser deux méthodes pour déterminer lequel ou lesquels des sommets maximisera ou minimisera la fonction.


Première méthode : La méthode du tableau d’optimisation

Cette méthode consiste à construire un tableau pour trouver le point qui optimise la solution. On calcule à l’aide de la fonction à optimiser, le résultat pour chaque sommet du polygone de contraintes.

Reprenons notre exemple

Puisqu'on veut maximiser les revenus, on choisira le point (400,0), c'est-à-dire que l'on ne produira que du yogourt.

Deuxième méthode : La méthode de la droite baladeuse

La droite baladeuse est une droite se balade dans le plan cartésien. Lorsque cette droite part de l’origine, le premier point que cette droite touche minimisera la situation et le dernier point qu’elle touche maximisera la situation.

Traçons la droite baladeuse

Pour tracer la droite baladeuse, il suffit de prendre la fonction à optimiser et de mettre cette fonction égale à zéro. On isole par la suite la variable y puis on trace cette droite dans notre graphique.

Pour notre exemple

R=36x+6y

On remplace R par 0 et on isole la variable y, ce qui donne l'équation suivante dans le graphique :

On la déplace parallèlement à celle qu’on vient de tracer. Lorsqu’on déplace la droite vers la droite, le premier sommet que la droite va rencontrer sera le sommet qui permettra de minimiser la fonction.

Pour notre exemple, la droite baladeuse rencontrera le sommet A en premier. C’est le sommet qui minimisera la fonction.

Si on continue de déplacer la droite baladeuse de notre exemple vers la droite, elle rencontrera le sommet B en deuxième et rencontrera pour terminer le sommet C. Le sommet C sera donc le sommet qui maximisera la fonction.



Pour connaître le revenu minimum ou maximum, on remplacera les coordonnées des sommets dans la fonction à optimiser.

Ajout d'une contrainte à un problème d'optimisation

L'ajout d'une contrainte dans un polygone consiste à ajouter une nouvelle inéquation qui va changer celui-ci.

Victor est vendeur de planches à roulettes Il vend ses planches amateurs 50$ et ses planches professionnelles à 300$. à tout moment il doit respecter certaines contraintes quant à la quantité de planches à roulettes offertes dans son magasin. Le polygone ci -dessous illustre ces contraintes.

x: le nombre de planches professionnelles

y: le nombre de planches amateurs



Victor veut faire une grande vente au cours du week-end prochain. Jean-Luc, son conseiller aux ventes, lui suggère d'avoir au plus 80 planches professionnelles dans son magasin.

Est-ce que Victor doit suivre les conseilles de Jean-Luc?

À partir de la fonction optimiser, on calcule d'abord le profit maximal dans le polygone sans la nouvelle contrainte.

z=300x+50y

Sommet      z=300x+50y                     Profit             
(20,40)       z=300(20)+50(40)          8 000$
(30,90)       z=300(30)+50(90)          13 500$
(110,50)     z=300(110)+50(50)        35 500$
(50,10)       z=300(50)+50(10)         15 500$

Le profit maximal est de 35 500$. En ajoutant la nouvelle contrainte, on retrouve le polygone suivant



On refait le calcul du profit maximal en fonction des nouveaux sommets.

z=300x+50y

Sommet           z=300x+50y                 Profit
(20,40)            z=300(20)+50(40)       8 000$
(50,10)            z=300(50)+50(10)      15 500$
(80,30)            z=300(80)+50(30)      25 500$
(80,65)            z=300(80)+50(65)      27 250$
(30,90)            z=300(30)+50(90)      13 500$

On remarque que le profit maximal est de 27 250$ donc il ne doit pas suivre les conseils de Jean-Luc, car il aura une perte de profit de 8250$.

Traceur de fonctions

Pour t'aider a bien représenter ton polygone de contrainte, utilise notre outil Traceur de fonctions :

Clique sur "Préfères-tu écrire tes propres équations" et utilises les symboles <, >, ≤, ≥ pour tracer tes fonctions.

Les exercices

QUESTION 1

Cynthia est membre de l'équipe des Jeunes entrepreneurs de son école.  Son projet est de peindre des motifs sur des vases et des sucriers.  Elle met 2 heures pour peindre les motifs d'un vase et 3 heures pour ceux d'un sucrier.  Durant l'année scolaire, elle consacrera un maximum de 120 heures à son projet et prévoit peindre un maximum de 50 objets.  Pour répondre à la demande de ses clients, elle devra peindre au moins 10 sucriers.  Chaque vase sera ensuite vendu 14$ et les sucriers seront vendus à 10$ chacun. Combien de vases et de sucriers doit-elle vendre pour maximiser ses profits?

RÉPONSE 1

Dans ce problème, il y a un certain nombre de vases (x) et de sucriers (y).

Cynthia a une contrainte de temps dans sa production :

2x + 3y < 120 ---> le symbole signifie plus petit ou égal, symbole qui manque dans les Forums.

Elle a aussi des contraintes de production :

x + y < 50

et y > 10

Donc les mêmes objets sont soumis à deux types de contraintes différentes, mais cela n'empêche pas de bâtir le système d'inéquations.

Marc-Antoine

QUESTION 2

Comment on sort correctement les contraintes ?
x : est des macintosh et y des cortland

Le double du nombre de pommiers produisant des pommes Cortland sera inferieur ou egal au triple du nombre de pommiers produisants des pommes macintosh. En fait, sil plante 300 pommiers de moinds produisant des pommes macintosh, leur nombre devra etre au maximum le quadruple du nombre de pommiers produisant des pommes Cortland,

RÉPONSE 2

x : est des macintosh et y des cortland

Le double du nombre de pommiers produisant des pommes Cortland sera inferieur ou egal au triple du nombre de pommiers produisants des pommes macintosh.

se traduit par ...

2y <= 3x

Et puis...

s'il plante 300 pommiers de moins produisant des pommes macintosh, leur nombre devra etre au maximum le quadruple du nombre de pommiers produisant des pommes Cortland,

se traduit par ...

x - 300 <= 4y

Simon

QUESTION 3

Je dois trouver le polygone de contrainte avec mes contraintes, comment faire ?

x + grand ou = a 0

y + grand ou = a o

x + y + petit ou = a 44

y+ grand x

x + petit ou = 18

RÉPONSE 3

On trace ces équations dans un plan cartésien, en remplaçant les signes d'inégalité par des "=".


Les références Théorie et exemple d’optimisation

  • MELS
  • Rogers
  • Réunir Réussir
  • Fondation Réussite Jeunesse