[PDF] Mathématiques B30: La programmation linéaire; Module de lélève

View - Download Mathématiques B30: La programmation linéaire; Module de lélève

Previous PDF

Next PDF

Mathématiques B30

La programmation linéaire

Module de l'élève

2002

Mathématiques B30

La programmation linéaire

Module de l'élève

Bureau de la minorité de langue officielle

200
2

P.ii - Math B30 - Programmation linéaire

Liste des objectifs du programme d'études de Mathématiques B30

Objectifs spécifiques

L'élève sera capable de:

C.10 Représenter graphiquement des systèmes d'inéquations C.11 Déterminer les points d'intersection des droites tracées à l'objectif 10 C.12 Déterminer quels sommets d'un polygone formé par un système d'inéquations maximisent ou minimisent une fonction linéaire donnée

Remerciements

Ce module contient en partie des exercices et des exemples adaptés, avec permission, du document de B. Thiessen (Mathematics B 30, Saskatoon Public

School Division, 1999).

P.1 - Math B30 - Programmation linéaire

1. Introduction

En 1947, George Dantzig devait trouver un moyen de résoudre le problème de distribution des provisions de l'armée américaine de manière à minimiser les coûts d'opération. Dantzig utilisa une méthode, la programmation linéaire, dans laquelle la valeur maximale ou minimale d'une fonction mathématique est déterminée en fonction des contraintes du problème. Par exemple, supposons une compagnie qui fabrique deux modèles de montres. En connaissant les contraintes qui lui sont imposées, telles que la quantité de pièces disponibles ainsi que le nombre d'heures de montage nécessaires, elle peut déterminer combien de montres de chaque modèle elle devrait fabriquer afin de maximiser ses revenus. Le monde des affaires n'a pas tardé à reconnaître le potentiel de la méthode de George Dantzig dans la résolution de problèmes économiques complexes. Aujourd'hui, la programmation linéaire est utilisée non seulement dans la gestion des inventaires, le design des usines et la gestion des ressources, mais elle trouve aussi des applications dans les domaines de la santé, de l'environnement, de l'agriculture et des communications. Avant de résoudre des problèmes utilisant la programmation linéaire, nous devons revoir les processus qui permettent de traduire en inéquations les contraintes d'un problème d'optimisation.

2. Définition et graphiques d'inéquations linéaires

2.1 L'inéquation à deux variables

Une inégalité est constituée lorsque deux expressions sont liées par le symbole > ou le symbole <. On trouve aussi des inégalités ayant les symboles ou .

Une inéquation à deux variables contient évidemment deuxLes symboles de la relation d'inégalité sont:

< qui se lit ... est inférieur à ... > qui se lit ... est supérieur à ... qui se lit ... est inférieur ou égal à ... qui se lit ... est supérieur ou égal à ...Ð Une inéquation est un énoncé mathématique comportant une ou des variables mises en relation d'inégalité. Par exemple, ou .

5xY28xyHÐ

P.2 - Math B30 - Programmation linéaire

variables. Par exemple, est une inéquation à deux0xyHÐ variables. Toutefois, nous pouvons aussi dire que est une2xÀ inéquation à deux variables puisqu'elle peut être réécrite sous la forme .

02xyHÀ

Exemple 1 : Écris l'inéquation sous la forme où est la60xH[xk[k constante de l'inéquation.

Solution L'inéquation devient ou .

06x[J6x[J

Exemple 2 : Écris l'inéquation sous la forme .280yJJYxkY Solution Il faut d'abord additionner 8 à chaque côté de l'inéquation: . Ensuite, nous divisons par -2, mais en tenant compte 28yJY
que la division s'effectue avec un signe négatif. Ceci implique que nous devons inverser le sens de l'inégalité: . 4y[J Une des habiletés à développer est celle permettant de traduire le contenu d'une phrase déclarative en inéquation (et vice versa). Les exemples suivants illustrent cette habileté.Les exemples précédents nous indiquent quelques propriétés importantes des inéquations que nous résumons ici. •En ajoutant ou en retranchant une même quantité des deux membres d'une inéquation, nous obtenons une inéquation équivalente à celle de départ. Par exemple, et sont

50xJY5xY

équivalentes.

•En divisant ou en multipliant les deux membres d'une inéquation par une même quantité positive, nous obtenons une inéquation équivalente. Par exemple, et sont équivalentes.

26xÐ3xÐ

•En divisant ou en multipliant les deux membres d'une inéquation par une même quantité négative, nous devons changer le sens du symbole d'inégalité afin d'obtenir une inéquation équivalente. Par exemple, devient .

510xJÀ2xÐJ

P.3 - Math B30 - Programmation linéaire

Exemple 3 : Traduis la phase suivante par une inéquation: la valeur de estx supérieure ou égale à moins deux.y

Solution2xyÐJ

Exemple 4 : Traduis la phase suivante par une inéquation: la quantité de nouveaux livres achetés par la bibliothèque municipale est inférieure à 20% de la quantité de livres qui se trouvent déjà à la bibliothèque. Solution Soit , la quantité de nouveaux livres et , le nombre de livres nv déjà à la bibliothèque: ou .0,20nvY 1 5nvY Exemple 5 : Traduis la phase suivante par un système d'inéquations: le nombre de matchs remportés chaque année par cette équipe de football à est compris entre 12 et 16. Solution Soit m, le nombre de matchs remportés par l'équipe. Ici, notre variable sera située dans l'intervalle 12 à 16:

12 16mÀÀ

À toi de jouer! (1)

Écris l'inéquation sous la forme .

360zJ[Jxk[

À toi de jouer! (2)

Traduis la phrase suivante en inéquation: le taux d'intérêt accordé pour un prêt personnel n'est jamais inférieur ou égal à 7 % (à cette succursale bancaire).

P.4 - Math B30 - Programmation linéaire

Exercice 1

1. Écris chacune des inéquations suivantes sous la forme , ouxkYxk[xkÀ

.xkÐ a)260xJY b)2120xJJ[ c)

122xÐ

d)

EF236xxHÐ

e)

1263xJYJ

f)

21032xJÀ

g)17xJ[J h)

22 4535xxHJJÐ

i)9180xJY j)

1538xJÀJ

2. Traduis les phrases suivantes en inéquations en utilisant les variables indiquées

entre parenthèses. a) Le nombre d'animaux ( ) dans ce cirque est supérieur à 24. a b) Le nombre de passagers ( ) dans cet autobus est au moins 45.p c) Ce couple de jeunes adultes veulent un maximum de quatre enfants (e). d) Le nombre de cadres féminins (f) dans cette entreprise est supérieur ou égal au nombre de cadres masculins (m) plus 5 personnes. e) Le nombre d'heures (h) d'activités parascolaires de Miguel est compris entre cinq et huit. f) La vitesse (v) maximale atteinte par cette voiture est de 150 km/h.

P.5 - Math B30 - Programmation linéaire

-10 10 -1 0 10 x y x=3

2.2 La représentation graphique dans le plan cartésien de l'ensemble

solution d'une inéquation à deux variables La représentation graphique dans le plan cartésien d'une inéquation de type tient compte du fait que l'ensemble solution comprend tous les points

3xÐ

du plan répondant aux conditions de l'inéquation. Ainsi, dans le cas de EF,xy l'inéquation , l'ensemble solution comprend tous les points situés sur la3xÐ frontière délimitée par et tous les points à la droite de cette frontière3xZ (nommée droite-frontière), comme l'illustre la figure suivante. Sur le graphique précédent la région ombrée est aussi nommée demi-plan fermé. Un demi-plan est dit ouvert si la droite-frontière est pointillée. Une telle situation se produit lorsque le symbole d'inégalité est < ou >. Par exemple, dans le cas de l'inégalité , les 3x[ points appartenant à la droite ne font3xZ pas partie de l'ensemble solution. Le graphique prend alors l'allure ci-contre.

P.6 - Math B30 - Programmation linéaire

-10 10 -1010 x y -10 10 -1 0 10 x y

De la même manière, nous

représenterons l'ensemble solution d'une inéquation telle par le demi-plan fermé

3yÀ

dont la droite-frontière est située à . Tous les points qui

3yZEF,xy

satisfont les exigences de cette inéquation feront partie de l'ensemble solution. Exemple 6 : Représente l'ensemble solution de l'inéquation sur le plan

1xÀJ

cartésien.

Solution Puisque le symbole

d'inégalité est inférieur ou

égal, les points qui

appartiennent à la droite- frontière feront 1xZJ partie intégrante de l'ensemble solution. Le graphique suivant montre que le plan fermé comprend également la région à la gauche de la droite-frontière.

À toi de jouer! (3)

Représente l'ensemble solution de l'inéquation sur le plan cartésien. 1y[J

P.7 - Math B30 - Programmation linéaire

P.8 - Math B30 - Programmation linéaire

Une inéquation qui comporte plus d'une variable, telle que ouax by cHÀ peut aussi être représentée dans le plan cartésien. Les exemplesax by cHÐ suivants illustrent la démarche à suivre pour obtenir une telle représentation graphique. Exemple 7 : Soit l'inéquation . Représente graphiquement l'ensemble

2xyHÀ

solution.

Solution • Isolons :

y2yxÀJ H • Trouvons deux points appartenant à la droite-frontière afin de tracer celle-ci. La droite-frontière est représentée par l'équation . Nous pouvons utiliser un tableau des valeurs afin

2yxZJ H

de trouver deux points appartenant à cette droite. Par exemple, il est relativement facile de trouver l'ordonnée à l'origine et l'abscisse à l'origine de cette droite en remplaçant par 0 et x ensuite par 0. y xy 0

022yZHZ

022xxZJ H û Z

0

Nous plaçons ensuite ces

deux points sur le graphique et nous traçons la droite- frontière.

P.9 - Math B30 - Programmation linéaire

-10 10 -1010 x y • Il faut par la suite déterminer de quel côté de la droite-frontière se trouve le restant des points appartenant à l'ensemble EF,xy solution. Nous pouvons déterminer ceci en utilisant un point quelconque du plan cartésien et en vérifiant si celui-ci répond aux exigences de l'inéquation. Par exemple, le graphique montre que le point est situé sous la droite-frontière. Vérifions EF0,0 si satisfait aux exigences de l'inéquation en remplaçant les EF0,0 variables et de l'inéquation . Ainsi, , cexy2xyHÀ

002HÀ

qui est vrai. La région qui correspond à l'ensemble solution comprend non seulement la droite-frontière, mais également la partie située sous cette dernière. Nous devons ombrer cette partie du plan cartésien.

P.10 - Math B30 - Programmation linéaire

-10 10 -1010 x y Exemple 8 : Soit l'inéquation . Représente graphiquement

21xyJÐJ

l'ensemble solution.

Solution • Isolons :

y21xyJÐJ

Soustraire 21yxJÐJ J2x

Diviser par -1 et changer le sens du

21

11yxJJJÀJJ

symbole d'inégalité

21yxÀH

• Trouvons deux points appartenant à la droite-frontière afin de tracer celle-ci. La droite-frontière est représentée par l'équation . Nous pouvons utiliser un tableau des valeurs afin

21yxZH

de trouver deux points appartenant à cette droite. xy 0

2(0) 1 1yZHZ

102 12xxZHûZJ

0 Nous plaçons ensuite ces deux points sur le graphique et nous traçons la droite-frontière.

P.11 - Math B30 - Programmation linéaire

-10 10 -1010 x y • Pour déterminer de quel côté de la droite-frontière se trouve le restant des points appartenant à l'ensemble solution, nous EF,xy allons encore une fois utiliser un point du plan cartésien et vérifier si celui-ci répond aux exigences de l'inéquation. Par exemple, le graphique montre que le point est situé au-

EF3,2J

dessus de la droite-frontière. Vérifions si satisfait aux

EF3,2J

exigences de l'inéquation en remplaçant les variables et dexy l'inéquation . Ainsi, ? Puisque ce21xyJÐJE23 2 1JJ ÐJ n'est pas vrai, nous devons conclure que la région qui correspond à l'ensemble-solution comprend la droite-frontière et la partie située sous cette dernière. Nous devons ombrer cette partie du plan cartésien.

À toi de jouer! (4)

Représente graphiquement l'ensemble solution de chacune des inéquations suivantes. a) b)

34xyHY624xyJÐ

P.12 - Math B30 - Programmation linéaire

Exercice 2

1. Dans chacun des cas suivants, représente le demi-plan correspondant à

l'inéquation donnée. a)

2xÐJ

b)2yÀ c)28xÀ d)4x[ e)2xyJÀJ f)23 3xyHYJ g)43yxJ[J h)23120xyHJÀ i)963xyÐJ j)1xyJJ ÀJ

2. Détermine si les points font partie de l'ensemble solution de chacune des

inéquations suivantes. a)

EF5,2 ; 4 2 19xyH[

b)

EF6,3 ; 2 14xyJJ[J

c)

EF10, 8 ; 18xyJJÀ

d)

12, ; 2 32xyăēHÐJĄĔąĕ

e)

E3,5 ; 8xyJHÐ

3. Détermine l'inéquation qui correspond au graphique ci-dessous.

P.13 - Math B30 - Programmation linéaire

2.3 Graphiques de systèmes d'inéquations

Les problèmes d'optimisation que nous allons résoudre à l'aide de la programmation linéaire vont compter plus d'une inéquation. Autrement dit, nous devrons solutionner des systèmes d'inéquations. L'exemple suivant montre comment on trouve l'ensemble solution d'un système d'inéquations. Exemple 9 : Détermine graphiquement l'ensemble solution du système d'inéquations suivant. 2 1x xyÐ

HÀJ

Solution Dans un premier temps, nous allons représenter graphiquement la solution de la première inéquation:

2xÐ

Ensuite, nous allons tracer la droite-frontière de la seconde inéquation et identifier de quel côté de cette droite se trouve le restant de l'ensemble solution pour cette inéquation. La droite- frontière correspond à l'équation .

1xyHZJ

xy 0 (0) 1 1yZJZJ

01 1xxHZJûZJ

0 Après avoir placé ces deux points et tracé la droite-frontière, nous représentons le restant de l'ensemble solution.

P.14 - Math B30 - Programmation linéaire

La région hachurée correspond à l'ensemble solution du système d'inéquations 2 1x xyÐ

HÀJ

Pour simplifier la représentation de l'ensemble solution des systèmes d'inéquations, nous allons ombrer uniquement la région qui correspond à cet ensemble solution. Ainsi, pour le système précédent, le graphique prend l'allure suivante.

P.15 - Math B30 - Programmation linéaire

Exemple 10 : Trouve l'ensemble solution du système d'inéquations suivant: 26
30
0 0yx xy xquotesdbs_dbs47.pdfusesText_47

[PDF] Mathématiques : L'algorithme d'Euclide PGCD

[PDF] Mathématiques : L'algorithme De Différences PGCD

[PDF] Mathématiques : La Géometrie dans l'espace

[PDF] Mathématiques : le cosinus

[PDF] Mathématiques : le idéal P d'une personne selon la formule de LORENTZ

[PDF] Mathématiques : les fonctions

[PDF] mathématiques : les fonctions affines

[PDF] Mathématiques : Montrer que pour tout x de R, f(x) inférieur ou égal à 8 Pour quelle(s) valeur(s) a-t-on f(x)= 8

[PDF] Mathématiques : Narration de recheche

[PDF] Mathématiques : Narration de recherche

[PDF] Mathématiques : nombres entiers consécutifs

[PDF] Mathématiques : Nombres entiers et rationnels

[PDF] Mathématiques : Pourcentage :

[PDF] Mathématiques : Problème : 3ème PGCD

[PDF] Mathématiques : problème : équations