[Guide d’apprentissage MST :: Geogebra] Programmation linéaire 2 (polygones de contraintes)

Programmation linéaire 2 (polygones de contraintes)

jeudi 29 avril 2010
par Pierres
popularité : 28%

GéoGebra ne permet pas de résoudre des systèmes d’inéquations. Par contre, il est possible de réaliser cette tâche malgré tout.

Nous allons démarrer avec les contraintes suivantes :

3 $\leqslant$ x $\leqslant$ 12
4 $\leqslant$ y $\leqslant$ 15
x + y $\leqslant$ 20

Il faut maximiser la fonction : P = 10x + 25y

1. Première étape

La première contrainte (3 $\leqslant$ x $\leqslant$ 12) peut se diviser en deux sous-contraintes :

x $\geqslant$ 3
x $\leqslant$ 12

On peut utiliser l’outil Déplacer Graphique afin de faire afficher le premier quadrant. Donc, déplacez l’espace graphique afin que l’origine se retrouve en bas à gauche dans la zone graphique.

De plus, avec le bouton de droite de la souris, cliquez dans le plan et activé la grille.

GéoGebra ne pouvant nous permettre directement la saisie d’inéquations dans la zone de saisie, nous allons inscrire ces inéquations sous forme d’équations afin de faire tracer deux droites.

Dans la zone de saisie, inscrivez l’équation : x = 3.
Appuyez sur « Entrée ».

Dans la zone de saisie, inscrivez l’équation : x = 12.
Appuyez sur « Entrée ».

Vous aurez ceci à l’écran.

2. Deuxième étape

La deuxième contrainte (4 $\leqslant$ x $\leqslant$ 15) peut se diviser elle aussi en deux sous-contraintes :

y $\geqslant$ 4
y $\leqslant$ 15

GéoGebra ne pouvant nous permettre directement la saisie d’inéquations dans la zone de saisie, nous allons inscrire ces inéquations sous forme d’équations afin de faire tracer deux droites.

Dans la zone de saisie, inscrivez l’équation : y = 4.
Appuyez sur « Entrée ».

Dans la zone de saisie, inscrivez l’équation : y = 15.
Appuyez sur « Entrée ».

Vous aurez ceci à l’écran.

Un rectangle est ainsi formé (croisement des quatre droites). Notre solution se situera dans cet espace.

3. Troisième étape

Passons à la dernière inéquation : x + y $\leqslant$ 20

Tout comme précédemment, nous allons inscrire une équation pour que GéoGebra puisse nous aider. Donc, dans la zone de saisie, inscrivez l’équation : x + y $\leqslant$ 20.
Appuyez sur « Entrée ». Vous aurez ceci à l’écran. Il est possible que vous ayez à ajuster l’affichage afin de voir le résultat de l’affichage de la droite correctement. Vous pouvez réaliser le tout avec la molette de votre souris. Déplacez le tout afin de replacer votre origine en bas à gauche de la zone graphique.

Nous allons déterminer maintenant une zone ombragée (polygone). Nous allons utiliser un point n’appartenant pas à la droite (le point (0,0) par exemple) dans notre inéquation afin de déterminer le polygone à tracer. Nous allons substituer ces valeurs dans notre inéquation.

x + y $\leqslant$ 20

0 + 0 $\leqslant$ 20

0 $\leqslant$ 20 -> Vrai !

Notre zone ombragée sera sous la droite, le point (0,0) nous permettant de vérifier positivement l’inéquation x + y $\leqslant$ 20

Utilisez l’outil Intersection entre deux objets afin de placer les points à l’intersection des droites qui se croisent. Afin de fixer l’intersection, vous cliquez sur une droite et, par la suite, vous cliquez sur l’autre droite qui croise cette dernière. Refaites la même démarche pour les autres droites afin d’obtenir ce qui suit :

Nous allons déterminer maintenant une zone ombragée (polygone). Utilisez l’outil Polygone afin de créer un polygone à partir de ces points.

4. Quatrième étape

Notre zone ombragée forme un polygone où on y trouve 5 points particuliers (A, B, C, D, E). Nous allons tester ces points dans notre fonction à maximiser :

P = 10x + 25y

Nous allons utiliser GéoGebra pour effectuer ces calculs. Nous allons définir :

PA -> fonction à optimiser avec les coordonnées de A
PB -> fonction à optimiser avec les coordonnées de B
PC -> fonction à optimiser avec les coordonnées de C
PD -> fonction à optimiser avec les coordonnées de D
PE -> fonction à optimiser avec les coordonnées de E

Nous allons utiliser un outil de GéoGebra nous permettant d’obtenir les coordonnées d’un point :

x(Point) ->retourne la coordonnée de l’abscisse (x) d’un point
y(Point) ->retourne la coordonnée de l’ordonnée (y) d’un point

Dans la zone de saisie, inscrivez : PA=10*x(A) + 25*y(A) et faites « Entrée » afin de valider votre saisie. Dans la zone algèbre, vous verrez apparaître PA=130.

Pour le point B, vous aurez PB=10*x(B) + 25*y(B). La valeur apparaissant pour PB est 405.

Pour le point C, vous aurez PC=10*x(C) + 25*y(C). La valeur apparaissant pour PC est 425.

Pour le point D, vous aurez PD=10*x(D) + 25*y(D). La valeur apparaissant pour PD est 320.

Pour le point E, vous aurez PE=10*x(E) + 25*y(E). La valeur apparaissant pour PE est 220.

Donc, avec les contraintes de départ que nous avions :

3 $\leqslant$ x $\leqslant$ 12
4 $\leqslant$ y $\leqslant$ 15
x + y $\leqslant$ 20

l’optimisation de la fonction P = 10x + 25y sera les coordonnées de C, soit : x=5 et y=15 qui nous retourne une valeur maximale de 425.

Question ou commentaire?

Documents joints à cet article :

Programmation linéaire 2