EXERCICES DE PROGRAMMATION LINÉAIRE

RÉSOLUS
EXERCICES DE PROGRAMMATION LINÉAIRE

1. Nous avons 210 000 euros à investir en bourse. Ils recommandent deux types d'actions.
Ceux de type A, qui rapportent 10 % et ceux de type B, qui rapportent 8 %. Nous avons
décidé d'investir au maximum 130 000 euros en type A et au moins 60 000 euros en type B.
De plus, nous souhaitons que l’investissement dans le type A soit inférieur au double de
l’investissement dans le type B. Quelle doit être la répartition de l’investissement pour
obtenir l’intérêt annuel maximum ?
Solution
C'est un problème de programmation linéaire.
Nous appelons x le montant que nous investissons en actions de type A
Nous appelons désormais le montant que nous investissons en actions de type B

X20
investissement performance
20
Type A x 0,1x
R1 X+y <210 Tapez B et
0,08 an
000x < 130 210000 0,1x+0,0
R2
000 8y
R3 et 260000
R4 x< 2 ans

Nous traçons les lignes auxiliaires associées aux restrictions pour obtenir la région réalisable
(ensemble de points qui remplissent ces conditions)

r1 r2 (parallèle à OY) r3 (parallèle à OX) r4

x et
x et
x et
x et

0 210000 130000 0 0 60000 0 0

210000 0 130000 65000
La région réalisable est celle peinte en jaune, avec les sommets A, B, C, D et E.

fichier:///E|/METODOS%20QUANTITATIVOS/EJERCICIOS%20SOLVED%20DE%20PROGRAMMACIÓN%[Link][01/09/2014 [Link] a.
EXERCICES DE PROGRAMMATION LINÉAIRE
RÉSOLUS

A(0, 60 000), B(120 000, 60 000), C(130 000, 65 000), D(130 000, 80 000) et E(0, 210 000)
La fonction objectif est :
F(x, y)= 0,1x+0,08y
Si nous dessinons la courbe F(x, y) =0 (en rouge) et la déplaçons, nous pouvons vérifier
graphiquement que le sommet le plus éloigné est D, et donc c'est la solution optimale.
Vérifiez-le analytiquement (c'est-à-dire vérifiez que la valeur maximale de la fonction
objectif, F, est atteinte au sommet D)

2. Dans une pâtisserie, on fabrique deux types de gâteaux : viennois et royal. Chaque
gâteau viennois nécessite un quart de garniture pour chaque kg. de gâteau et produit un
bénéfice de 250 Pts, alors qu'un vrai gâteau a besoin d'un demi-Kg. de remplissage pour
chaque kg. de gâteau et produit 400 Ptas. de bénéfice. En pâtisserie, on peut en préparer
jusqu'à 150 kg par jour. de gâteau et 50 Kg. de remplissage, bien qu'en raison de problèmes
de machines, ils ne puissent pas réaliser plus de 125 gâteaux de chaque type. Combien de
gâteaux viennois et combien de Reales doivent-ils vendre par jour pour un profit maximum ?
Solution
Nous créons d’abord un tableau pour organiser les données :

Gars Non. Gâteau Farci Avantage

T. Viennois x 1.x 0,250x 250x
T. Réel et
[Link] 0,500a 400 ans
150 50

Fonction objectif (doit obtenir son maximum) : f(x, y)=250x+ 400y Sous réserve des
conditions suivantes (restrictions du problème) :

fichier:///E|/METODOS%20QUANTITATIVOS/EJERCICIOS%20SOLVED%20DE%20PROGRAMMACIÓN%[Link][01/09/2014 [Link] a.
EXERCICES DE PROGRAMMATION LINÉAIRE
RÉSOLUS

Nous considérons les lignes auxiliaires des restrictions et dessinons la région réalisable :

Pour 0,25x+0,50y=50, ou x + 2y=200

Les deux autres sont parallèles aux axes. L'axe OY x=125.

Et les autres restrictions (x et y supérieurs ou égaux à zéro) nous disent que les solutions
Vers y
l'axe du
doivent être dans
=125le premier quadrant
Nous avons coloré en jaune la région réalisable :

Trouvons les sommets :

Le O(0,0), le A(125, 0) et le D(0, 100) se rencontrent directement (ce sont les intersections
avec les axes de coordonnées)
On observe que la restriction y<125 est redondante (c'est-à-dire « restante »)
Résoudre le système :
x + 2y = 200
X+¥ = 150
, par réduction on obtient y=50, x=100

Un autre sommet est le point C(100, 50)

Et le dernier sommet qui nous manque est obtenu en résolvant le système :

fichier:///E|/METODOS%20QUANTITATIVOS/EJERCICIOS%20SOLVED%20DE%20PROGRAMMACIÓN%[Link][01/09/2014 [Link] a.
EXERCICES DE PROGRAMMATION LINÉAIRE
RÉSOLUS
X+y=150
X=125
Dont la solution est : X=125, Y=25 B(125, 25)

Les sommets de la région sont O(0,0), A(125,0), B(125,25) et C(100,50) et D(0,100), Si l'on
trace le vecteur directeur de la fonction objectif f (x, y)=250x+ 400y Soit 250x+ 400y =0,
y=-(250/400)x=-125x/200

x ET
0 0
200 -125

On voit graphiquement que la solution est le point (100, 50), puisque c'est le sommet le plus
éloigné (le dernier que l'on trouve en déplaçant les lignes 250x+400y=0)
Nous le vérifions avec la méthode analytique, c'est-à-dire en utilisant le théorème qui dit que
s'il existe une solution unique, elle doit être trouvée dans l'un des sommets.
La fonction cible était : f(x, y)=250x+400y, en remplaçant dans les sommets obtenus
f(125,0)=31 250
f(125,25)=31 250+10 000=41 250
f(100,50)=25 000+20 000=45 000
f(0,100)=40 000

Le profit maximum est de 45 000 et est obtenu au point (100, 50)

Conclusion : 100 gâteaux viennois et 50 gâteaux royaux doivent être vendus.

3. Une école prépare une excursion pour 400 élèves. La société de transport dispose de 8
autocars de 40 places et de 10 autocars de 50 places, mais elle ne dispose que de 9
chauffeurs. La location d'un grand autocar coûte 80 euros et celle d'un petit, 60 euros.
Calculez combien de chaque type utiliser pour que l'excursion soit la plus économique
possible pour l'école.

fichier:///E|/METODOS%20QUANTITATIVOS/EJERCICIOS%20SOLVED%20DE%20PROGRAMMACIÓN%[Link][01/09/2014 [Link] a.
EXERCICES DE PROGRAMMATION LINÉAIRE
RÉSOLUS
Solution
C'est un problème de programmation linéaire, dans ce cas ce que nous voulons c'est rendre
la fonction objectif minimale.
On appelle x le nombre de bus de 40 places et y le nombre de bus de 50 places loués par
l'école.
Alors nous avons x < 8 , et
Puisqu’il n’y a que 9
conducteurs, on vérifie
que : x +y
Puisque 400 étudiants doivent s'adapter, il faut
vérifier :
40x +50y >400, ce qui serait simplifié serait 4 x +5y
Par conséquent, les restrictions qui nous permettront de calculer la région réalisable
(ensemble de points de solution où toutes les conditions sont remplies) sont

La fonction objectif est F(x, y)= 60x+ 80y

Nous traçons les lignes auxiliaires, r1 r2 r3 r4
et

10
0 9 10 0
Ainsi que celui qui correspond à F(x, y)=0 qui est dessiné en rouge.
En tenant compte des contraintes (R4 est la partie supérieure et R3 est la partie inférieure), la
région réalisable est trouvée. Sur le dessin c'est la partie jaune.

Les sommets sont (0, 8), (0, 9) et (5, 4), ce dernier est le point d'intersection des droites r3 et
r4

par réduction

fichier:///E|/METODOS%20QUANTITATIVOS/EJERCICIOS%20SOLVED%20DE%20PROGRAMMACIÓN%[Link][01/09/2014 [Link] a.
EXERCICES DE PROGRAMMATION LINÉAIRE
RÉSOLUS
en soustrayant les deux équations, nous avons x = 5 et en substituant dans la 1ère
équation, y = 4
En résolvant graphiquement, nous arrivons au point (5, 4) étant la solution du problème. La
solution optimale.
Vérifiez-le en substituant tous les sommets de F(x, y) et que c'est celui qui donne la valeur la
plus basse (méthode analytique).

4. Une entreprise possède deux mines : la mine A produit chaque jour 1 tonne de fer de
haute qualité, 3 tonnes de fer de qualité moyenne et 5 tonnes de fer de mauvaise qualité. La
mine B produit chaque jour 2 tonnes de chacune des trois qualités. L'entreprise a besoin d'au
moins 80 tonnes de minerai de haute qualité, 160 tonnes de qualité moyenne et 200 tonnes
de basse qualité. Sachant que le coût journalier de l'opération est de 2000 euros dans
chaque mine, combien de jours doit fonctionner chaque mine pour que le coût soit minime ?
Solution
Nous organisons les données dans un tableau :

jours Haute Qualité Faible Coût quotidien

Le mien A x qualité1x moyenne
3x qualité 5x 2000x
Le mien B et
2 ans 2 ans 2 ans 2000 ans
80 160 200
La fonction objectif C(x, y)=2000x + 2000y
X+2y 2 80 3x+ 2y > 160 5x+2y= 200 x> 0
Les restrictions sont : 20

Nous obtenons la région réalisable en traçant les lignes auxiliaires : r1 x + 2y=80, r2 3x + 2y=
160 et r3 5x + 2y=200 dans le premier quadrant et en considérant la région non bornée
déterminée par le système de contraintes :

Les sommets sont les points A(0, 100), B(20, 50), C(40, 20), D(80, 0), qui se trouvent lors de
la résolution du système déterminé deux à deux par les droites auxiliaires et ( et qu'ils se
situent dans la région réalisable).

fichier:///E|/METODOS%20QUANTITATIVOS/EJERCICIOS%20SOLVED%20DE%20PROGRAMMACIÓN%[Link][01/09/2014 [Link] a.
EXERCICES DE PROGRAMMATION LINÉAIRE
RÉSOLUS

r2 à r3

ce qui nous donne le point (40, 20)

3x+2a =160(vérifiez-le)
51+2= 200
ce qui nous donne le point (20, 50)

n’est pas nécessaire de calculer r3 puisqu’il se situe en dehors de la région des réalisables.
r1 Il
Le graphique montre que le premier point atteint en déplaçant la droite C(x, y)=0 est (40,
20). Alors la solution est de travailler 40 jours dans la mine A et 20 jours dans la mine B.
(méthode graphique)
Nous le vérifions en appliquant la méthode analytique :
C(0, 100)=2000,100=200000
C(20, 50)=2000,20+2000,50=40000 + 100000= 140000
C(40, 20)= 2000. 40+2000,20=80000 + 40000= 120000 coût minimum
C(80, 0)= 2000,80 =160000

5. Une usine d'atelier automobile va être organisée où travailleront des électriciens et des
mécaniciens. En raison des besoins du marché, il est nécessaire qu'il y ait un nombre de
mécaniciens supérieur ou égal à celui des électriciens et que le nombre de mécaniciens ne
dépasse pas le double de celui des électriciens. Au total, 30 électriciens et 20 mécaniciens
sont disponibles. Le bénéfice journalier de l'entreprise est de 250 euros par électricien et de
200 euros par mécanicien. Combien d’ouvriers de chaque classe faut-il choisir pour obtenir le
profit maximum et quel est ce profit ?
Soit x = nombre d'électriciens
y = nombre de mécaniciens
La fonction objectif
Yax
y<2xI
<30
<20
x>0
f (x, y)=250x+ 200y, contraintes 20

On voit graphiquement (ligne rouge) que la solution optimale se trouve au point (20, 20).

La région réalisable serait pour ces

contraintes :

fichier:///E|/METODOS%20QUANTITATIVOS/EJERCICIOS%20SOLVED%20DE%20PROGRAMMACIÓN%[Link][01/09/2014 [Link] a.
EXERCICES DE PROGRAMMATION LINÉAIRE
RÉSOLUS
Donc:
20 électriciens et 20 mécaniciens donnent le profit maximum, et celui-ci est de 9 000
euros, puisque f(x, y) =250,20+200,20=9000

6. Pour parcourir un certain itinéraire, une compagnie aérienne souhaite offrir, au

maximum, 5 000 sièges de deux types : T (économique) et P (premier). Le bénéfice
correspondant à chaque siège de type T est de 30 euros, tandis que le bénéfice de type P
est de 40 euros.
Le nombre de places de type T ne peut excéder 4 500 et le type P doit être, au maximum,
le tiers des places de type T proposées.
Calculez combien de chaque type doivent être proposés pour que les profits soient
maximaux. Solution
Soit x le nombre proposé de type T, et le nombre proposé de type P.
Non. Revenu
Touristique x 30x
D'abord et
40 ans
Total 5000 30x +40 ans
La fonction objectif est : f(x, y)=30x +40y
Les sommets A(0, 5000), B(3750, 1250), C(4500, 500) et D(4500, 0) (vérifiez le point B en
résolvant le système correspondant)

Les restrictions :

La région
réalisable :

La méthode graphique nous donne que le point solution est B (3750, 1250)

fichier:///E|/METODOS%20QUANTITATIVOS/EJERCICIOS%20SOLVED%20DE%20PROGRAMMACIÓN%[Link][01/09/2014 [Link] a.
EXERCICES DE PROGRAMMATION LINÉAIRE
RÉSOLUS

Vérifier les résultats en utilisant la méthode analytique (en remplaçant les points sommets
en f et en voyant que la valeur maximale est obtenue en B)

À suivre

Si vous souhaitez plus d'exercices, consultez les exercices d'examen modèle et les
exercices de sélectivité.

Cahier du 2ème Bach Mathématiques au lycée

fichier:///E|/METODOS%20QUANTITATIVOS/EJERCICIOS%20SOLVED%20DE%20PROGRAMMACIÓN%[Link][01/09/2014 [Link] a.