Mathématique m1092

Résoudre un problème d'optimisation

​Dans certaines situations faisant intervenir un système d'inéquations, l'objectif vise à déterminer la solution la plus avantageuse. Cette solution peut correspondre à la valeur la plus élevée, comme dans le cas d'un revenu, ou à la valeur la moins élevée, comme dans le cas d'un coût.

Résoudre une problème d'optimisation, c'est rechercher le couple (x,y) qui, selon le contexte, maximise ou minimise la fonction à optimiser.

La fonction à optimiser, aussi appelée la  fonction objectif, s'écrit généralement sous forme |z=ax+by+c|. Elle permet de comparer des couples (x,y) et de déterminer lequel constitue la solution la plus avantageuse en tenant compte de l'objectif visé.

Résolution d'un problème d'optimisation

Les étapes suivantes permettent de résoudre un problème d'optimisation:

1. Identifier les variables.
2. Traduire les contraintes de la situation par un système d'inéquations.
3. Établir la règle de la fonction à optimiser.
4. Tracer le polygone de contraintes.
5. Déterminer les coordonnées des sommets du polygone de contraintes.
6. Évaluer la fonction à optimiser en chaque sommet du polygone de contraintes.
7. Déduire le ou les sommets dont les coordonnées maximisent (ou minimisent) la fonction à optimiser et donner la réponse.

Il existe deux cas de solutions possibles:

  • Les coordonnées d'un seul point du polygone de contraintes engendrent la solution optimale. Ce point correspond généralement à un sommet du polygone.
  • Les coordonnées de plusieurs points du polygone de contraintes engendrent la solution optimale. Ces points forment généralement un côté du polygone.

Lorsqu'on veut déterminer les sommets qui engendrent la solution optimale, on peut procéder de deux façons:

  • La technique de la droite baladeuse permet de repérer graphiquement les coordonnées du sommet qui engendrent la valeur optimale.
  • La technique des sommets du polygone de contraintes permet de repérer algébriquement les coordonnées du sommet qui engendrent la valeur optimale. 

La droite baladeuse est une droite de pente |\displaystyle -\frac{a}{b}| qui se « balade » dans le plan cartésien.

Lorsque cette droite part de l’origine, le premier sommet que cette droite touche minimisera la situation et le dernier sommet qu’elle touche maximisera la situation.

Exemples de problèmes d'optimisation

Résolution par la technique des sommets du polygone de contraintes

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 litres de lait pour faire 1 litre de yogourt. Il faut aussi 6 litres de lait pour produire 1 litre de fromage.

Compte tenu de la demande pour ses 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. Identifier les variables

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

2. Traduire les contraintes par un système d'inéquations

La somme du lait à utiliser pour le yogourt et le fromage ne doit pas dépasser 600 litres par semaine:
|1,5x + 6y \le 600|

La quantité de yogourt doit être au moins trois fois plus grande que la quantité de fromage:
|x\ge 3y|

Au moins 200 litres de yogourt doit être produit par semaine:
|x\ge 200|

Le nombre de litres de yogourt produit par semaine ne peut pas être négatif:
|x\ge 0|

Le nombre de litres de fromage produit par semaine ne peut pas être négatif:
|y\ge 0|

3. Établir la règle de la fonction à optimiser

Mélanie veut maximiser ses revenus. Elle vend son yogourt 36$ le litre et son fromage 6$ le litre. La fonction à optimiser est donc:
|z = 36x + 6y|

4. Tracer le polygone de contraintes


5. 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 A: (200, 0)
Coordonnées du sommet B: (200, 50)
Coordonnées du sommet C: (400, 0)

6. Évaluer la fonction à optimiser en chaque sommet du polygone


7. Déduire le sommet qui optimise la fonction
Mélanie veut maximiser ses revenus. Comme le sommet C est celui qui procure le revenu maximal, ce sont ses coordonnées qui optimisent notre situation. Mélanie devra donc produire 400 litres de yogourt, mais ne pas produire de fromage afin de s'assurer les revenus les plus élevés possibles.

 

Résolution par la technique de la droite baladeuse

On peut résoudre le problème précédent d'une autre façon. Les cinq premières étapes sont identiques. Toutefois, à l'étape 6, plutôt que de résoudre algébriquement la situation, on peut la résoudre à l'aide du graphique et de la technique de la droite baladeuse.

6. Évaluer la fonction à optimiser à l'aide de la droite baladeuse

Dans le graphique du polygone de contrainte, on trace la droite de la fonction à optimiser lorsqu'elle est égale à 0. Ici, on trace la droite |0 = 36x + 6y|.

On déplace la droite baladeuse parallèlement à celle qu’on vient de tracer. Lorsqu’on déplace la droite baladeuse vers la droite, le premier sommet que celle-ci 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.


7. Déduire le sommet qui optimise la fonction

Mélanie veut maximiser ses revenus. Comme le sommet C est celui qui est rencontré en dernier par la droite baladeuse, ce sont ses coordonnées qui optimisent notre situation. Mélanie devra donc produire 400 litres de yogourt mais ne pas produire de fromage afin de s'assurer les revenus les plus élevés possibles.

 

Problème à solution non unique

Le comité des finissants d'une école organise une vente de biscuits et de muffins pour amasser des fonds pour leur bal de fin d'étude. Le comité doit vendre un maximum de 320 desserts. Il doit y avoir au moins 120 biscuits et au plus 160 muffins. De plus, il doit y avoir au plus 4 fois plus de biscuits que de muffins de vendus. Finalement, le coût d'un muffin et le coût d'un biscuit sont les mêmes, soient 2,50$.

Le comité des finissants désire maximiser ses revenus. Combien de muffins et de biscuits doit-il vendre afin d'y parvenir?

1. Identifier les variables

x: nombre de biscuits
y: nombre de muffins

2. Traduire les contraintes par un système d'inéquations

Le nombre de desserts vendus ne doit pas dépasser 320:
|x + y \le 320|

La quantité de biscuit doit être au plus quatre fois plus grande que la quantité de muffins:
|x\le 4y|

Au moins 120 biscuits doivent être vendus:
|x\ge 120|

Au plus 160 muffins doivent être vendus:
|y\le 160|

Le nombre de biscuits ne peut pas être négatif:
|x\ge 0|

Le nombre de muffins ne peut pas être négatif:
|y\ge 0|

3. Établir la règle de la fonction à optimiser

Le comité des finissants veut maximiser ses revenus. Les biscuits et les muffins sont vendus chacun 2,50$ l'unité. La fonction à optimiser est donc:
|z = 2,5x + 2,5y|

4. Tracer le polygone de contraintes


5. 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 A: (120, 160)
Coordonnées du sommet B: (120, 30)
Coordonnées du sommet C: (256, 64)
Coordonnées du sommet D: (160, 160)

6. Évaluer la fonction à optimiser pour chaque sommet du polygone

Si on remplace les variables de la fonction à optimiser par les coordonnées de chacun des sommets, on obtient les valeurs suivantes:
Le sommet A donne un revenu de 700$.
Le sommet B donne un revenu de 375$.
Le sommet C donne un revenu de 800$.
Le sommet D donne un revenu de 800$.

7. Déduire le sommet qui optimise la fonction

Dans ce cas, le revenu associé aux sommets C et D est le même. Par conséquent, tous les points du côté |\overline{C D}| du polygone de contraintes donnent aussi un revenu de 800$. On peut donc choisir n'importe quel point ayant des coordonnées entières sur ce côté pour déterminer la solution optimale. Il existe alors plus d'une solution possible.

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

m1092i1.JPG

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 conseils 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

m1092i2.JPG

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$. Victor ne doit donc pas suivre les conseils de Jean-Luc, car il aura une perte de profit de 8250$.

Les vidéos



Les exercices
Les références