Embed Size (px)
Citation preview
Résolution graphique
Résoudre graphiquement les problèmes suivants.
Exercice 1
X1 > 0, X2 > 0,
X1 + 2X2 6 10
2X1 + X2 6 11
Max(X1 + X2)
Correction
(0, 0) (11/2, 0)
(4, 3)
(0, 5)
(X1, X2) = (4, 3)Max(X1 + X2) = 7
Exercice 2
X1 > 0, X2 > 0,
X1 − X2 6 0
X1 + X2 > 1
Max(2X1 + X2)
Correction
Solutions non bornées.
Exercice 3
X1 > 0, X2 ∈ R,
−X1 + 5X2 > −4
X1 − X2 > 0
X1 6 6
Max(X1)
Correction
(−1,−1)
(6, 2/5)
(6, 6) Il existe une infinité de solutions de la forme (6, α) où
α ∈[2
5; 6
]. On a Max(X1) = 6.
1
Exercice 4
X1 ∈ R, X2 > 0,
3X1 + X2 > 0
X1 − 3X2 6 0
X1 + X2 6 4
Max(X1 + 2X2)
Correction
(0, 0)
(3, 1)
(−2, 6)
(X1, X2) = (−2, 6)Max(X1 + 2X2) = 10
Exercice 5
X1 > 0, X2 > 0,
X2 6 3
X1 − 3X2 6 4
Min(5X1 − X2)
Correction
(0, 0) (4, 0)
(13, 3)(0, 3)(X1, X2) = (0, 3)
Min(5X1 − X2) = −3
Exercice 6
X1 ∈ R, X2 ∈ R,
2X1 + 3X2 > 3
X1 + X2 6 6
−9X1 + 2X2 > −54
7X1 + X2 > −7
Min(5X1 + X2)
Correction
(6, 0)
(168/31,−81/31)
(−24/19, 35/19)
(−13/6, 49/6)(X1, X2) = (−24/19, 35/19)Min(5X1 + X2) = −85/19
2
Révision : algorithme de Gauss
Exercice 7
Résoudre les systèmes suivants.
1.
{2x+ y = 1
3x+ 7y = −2
2.
x+ y+ z = 8
x+ 2y− z = 0
y+ z = 1
x+ 4y+ z = 1
3.
x+ 2y+ 3z = 1
2x+ 6y+ 13z = 5
x+ 3y+ 6z = 3
4.
x+ y = 0
2x+ y = 1
x+ 2y = −1
Correction
1. (x;y) = (9/11; −7/11)
2. Il n’y a pas de solution.
3. (x;y; z) = (−6; 5; −1)
4. (x;y) = (1; −1)
Forme standard et méthode du simplexe
Résoudre les problèmes suivants par la méthode du simplexe après les avoir mit sous forme standard.
Exercice 8
X1 > 0, X2 > 0,
2X1 − X2 6 1
−X1 + X2 6 1
Min(−2X1 − X2)
Correction
Forme standard : X1 > 0, X2 > 0,
2X1 − X2 6 1
−X1 + X2 6 1
Max(2X1 + X2)
.
Solution : (X1;X2) = (2; 3) et Min(−2X1 − X2) = −7.
Exercice 9
X1 > 0, X2 > 0, X3 > 0,
X1 + X2 6 15
X1 + X3 6 10
X2 + X3 6 15
Max(X1 + X2 + X3)
CorrectionLe problème est déjà sous forme standard.Solution : (X1;X2;X3) = (5; 10; 5) et Max(X1 + X2 + X3) = 20.
Exercice 10
X1 > 0, X2 > 0, X3 > 0,
8X1 − X2 + 7X3 6 0
−2X1 + X2 + X3 6 1
Max(X1 + 2X2 − X3)
3
CorrectionLe problème est déjà sous forme standard.Solution : (X1;X2;X3) = (1/6; 4/3; 0) et Max(X1 + 2X2 − X3) = 17/6.
Exercice 11
X1 6 0, X2 6 0,
−X1 − X2 6 8
X1 − X2 > −4
Min (2X1 − X2)
Correction
Forme standard : X ′1 = −X1 > 0, X ′
2 = −X2 > 0,
X ′1 + X
′2 6 8
X ′1 − X
′2 6 4
Max (2X ′1 − X
′2)
Solution : (X1;X2) = (−6; −2) et Min(2X1 − X2) = −10.
Exercice 12
X1 > 0, X2 6 0,
6X1 + 3X2 6 3
X1 − 2X2 6 −10
Min (−X1 − 4X2)
Correction
Forme standard : X ′1 = X1 > 0, X ′
2 = −X2 > 0,
6X ′
1 − 3X′2 6 3
X ′1 + 2X
′2 6 −10
Max (X ′1 − 4X
′2)
Il n’y a pas de solution.
Exercice 13
X 6 0, Y > 0,
−X+ Y 6 7
Y 6 5
2X+ 5Y > 0
5X+ 2Y 6 0
Max(−X+ 3Y)
Correction
Forme standard : X ′ = −X > 0, Y ′ = Y > 0,
X ′ + Y ′ 6 7
Y ′ 6 5
2X ′ − 5Y ′ 6 0
−5X ′ + 2Y ′ 6 0
Max(X ′ + 3Y ′)
Ce problème est un cas dégénéré et ne se résout pas par la méthode du simplexe. Par chance (sic),il n’y a que deux variables. On peut appliquer la méthode graphique pour arriver à (X; Y) = (−2; 5) etMax(−X+ 3Y) = 17.
Exercice 14
X 6 0, Y ∈ R,
2X− Y 6 2
X > −1
X+ Y 6 0
Max(X− Y)
4
Correction
Forme standard : X ′ = −X > 0, Y+ > 0, Y− > 0, Y = Y+ − Y− ∈ R,
−2X ′ − Y+ + Y− 6 2
X ′ 6 1
X ′ + Y+ − Y− 6 0
Max(−X ′ − Y+ + Y−)
Solution (X, Y) = (−1; −4) et Max(X− Y) = 3.
Modélisation
Modéliser les problèmes suivants et résoudre par la méthode de votre choix.
Exercice 15
Une usine fabrique deux produits P1 et P2. Chaque produit passe dans 3 ateliers A, B et C. La consommationd’énergie pour chaque produit dans chaque atelier est synthétisée dans le tableau suivant :
Consommation P1 P2
Atelier A 1 2
Atelier B 1 1
Atelier C 1 0
exprimé en térawattheure (TW/h).Pour des raisons technique le nombre de TW/h est limité pour chaque atelier. Au maximum 6 pour l’atelier
A, 4 pour le B et 3 pour l’atelier C.Sachant que P1 est deux fois plus rentable que P2 quelle est la meilleur stratégie de production ?
CorrectionSoient P1 et P2 les quantités respectives de produit P1 et P2 fabriqués. L’énoncé s traduit par le problèmelinéaire suivant :
P1 + 2P2 6 6
P1 + P2 6 4
P1 6 3
Max(2P1 + P2)
On peut résoudre ce problème graphiquement ou par la méthode du simplexe. Le résultat est (P1;P2) =(3; 1) pour une rentabilité maximale de 7.
Exercice 16
Un agriculteur possède 90 hectares dans lesquelles il peut planter soit du blé soit du maïs. Le blé nécessite 16litres d’engrais et 14 litres d’insecticide par hectare. Le maïs nécessite 8 litres d’engrais et 35 litres d’insecticidepar hectare. Le prix de vente au kilo du blé est de 1e63 et celui du maïs de 0e87.Sachant qu’un hectare fournit une tonne de blé et 1.7 tonnes de maïs et que l’agriculteur possède deux
cuves : un de 1336 litres d’engrais et une de 1715 litres d’insecticide, de quoi devra se composer saplantation pour maximiser ses revenus ?
CorrectionSoient b le nombre d’hectare de blé et m celui de maïs. L’énoncé se traduit par le problème linéaire suivant :
b+m 6 90
16b+ 8m 6 1336
14b+ 35m 6 1715
Max(1630b+ 1479m)
On peut résoudre se problème graphiquement ou par la méthode du simplexe. Le résultat est (b;m) = (77; 13).Le prix de vente maximal sera 144737e.
5
Exercice 17
Un atelier fabrique deux produits A et B et disposede de 224 heures d’utilisation d’une machine (M1) etde 810 heures d’une machine (M2). Les contrainteset bénéfices pour chaque produit sont résumé dansle tableau suivant.
M1 M2 Bénéfice (e)
A 12 30 500
B 20 90 1000
Optimiser le bénéfice de fabrique de ces deux produits.
CorrectionSoient A et B le nombre respectif de produit A et B fabriqués. L’énoncé se traduit par le problème linéairesuivant :
12A+ 20B 6 224
30A+ 90B 6 810
Max(500A+ 1000B)
On peut résoudre ce problème graphiquement ou par la méthode du simplexe. Le résultat est (A;B) =(8.25; 6.25) pour un bénéfice de 10375e.
Exercice 18
La New Fashion Company fabrique et vend des robes et des blouses de profits respectifs 8e et 6e. La dessind’une robe requiert en moyenne 4 heures tandis qu’une blouse, environ 2 heures. Un tailleur prend 2 heuresà faire une robe et 4 heures à faire une blouse. La NFC dispose chaque jour de 60 heures de temps pourdessiner les vêtements et de 48 heures de temps pour coudre ces vêtements.Combien de robes et de blouses la NFC doit produire pour que son profit soit maximal ?
CorrectionSoient r le nombre de robe et b le nombre de blouse. L’énoncé se traduit par le problème linéaire suivant :
4r+ 2b 6 60
2r+ 4b 6 48
Max(8r+ 6b)
On peut résoudre ce problème graphiquement ou avec la méthode du simplexe. Le résultat est (r;b) = (12; 6)pour un profit maximal de 132e.
Exercice 19
Une entreprise fabrique trois types de bureaux A, B et C. Ils passent successivement par deux ateliers T1 etT2.
Article A B C
Bénéfice (e) 2000 1000 3000
T1 (en heures) 1 1 1
T2 (en heures) 2 1 4
Les ateliers T1 et T2 disposent de respectivement de 50 et 120 heures par jour. Combien faut-il fabriquer debureaux de chaque type pour maximiser le chiffre d’affaire journalier ?
CorrectionSoient A, B et C le nombre de bureaux de type respectif A, B et C. L’énoncé se traduit par le problèmelinéaire suivant :
A+ B+ C 6 50
2A+ B+ 4C 6 120
Max(2000A+ 1000B+ 3000C)
6
Ce problème se résout par la méthode du simplexe pour donner (A;B;C) = (40; 0; 10) comme solution et110000e de bénéfices.
Exercice 20
On a remarqué que l’émission la Matinale constituée de 20 minutes de musique et de 1 minute de publicitéattire 30 000 auditeurs tandis que la Tardive constituée de 10 minutes de musique et de 1 minute de publicitéattire 10 000 auditeurs. Les annonceurs insistent pour qu’au moins 6 minutes par semaine soient consacréesaux publicités de leurs produits tandis que le patron de la station ne peut se permettre de diffuser plus de80 minutes de musique par semaine.
1. Dans ces conditions, combien doit-on diffuser d’émissions de chaque catégorie par semaine si on veutsatisfaire les exigences des annonceurs et du patron de la station tout en maximisant le nombre d’audi-teurs à cette station ?
2. Si maintenant la Matinale n’attirait que 20 000 auditeurs tandis que la Tardive en attirait toujours 10000, que devient la réponse ?
CorrectionSoient m et t le nombre respectif de fois que les émissions "la matinale" et "la tardive" sont diffusée par jour.
1. L’énoncé se traduit par le problème linéaire suivant :m+ t > 6
20m+ 10t 6 80
Max(30000m+ 10000t)
Ce problème se résout graphiquement et admet (m; t) = (2; 4) comme solution, pour 100000 auditeurs.
2. L’énoncé se traduit par le problème linéaire suivant :m+ t > 6
20m+ 10t 6 80
Max(20000m+ 10000t)
Ce problème se résout graphiquement et admet (m; t) ∈ {(0; 8), (1; 6), (2; 4)} comme solution, pour 80000auditeurs.
Exercice 21
Un champion cycliste prépare son entraînement en vue d’une importante compétition.Son entraînement doit se composer chaque semaine d’un certain nombre d’heures de travail en salle et
d’un certain nombre d’heures de travail sur route.Au total, il doit s’entraîner au moins 20 heures chaque semaine et son nombre d’heures de travail sur route
doit être au moins égal au tiers du nombre d’heures de travail en salle.Pour s’entraîner en salle, il retient les services d’un entraîneur spécialisé qui lui coûte 15e l’heure. Cepen-
dant, cet entraîneur n’est disponible que s’il est engagé pour au moins 10 heures par semaine.Pour s’entraîner sur route, il retient les services d’un spécialiste qui lui coûte 12e de l’heure. Ce spécialiste
ne peut pas être disponible pour plus de 15 heures par semaine.Comment notre homme doit-il planifier son entraînement hebdomadaire pour que cela lui coûte le moins
cher possible ?
CorrectionSoient s et r le nombre d’heure respectives en salle et sur route. L’énoncé se traduit par le problème linéairesuivant :
s+ r > 20
−1
3s+ r > 0
s > 10
r 6 15
Min(15s+ 12r)
7
Ce problème se résout graphiquement et admet (s; r) = (10; 10) pour une dépense minimale de 270e.
Problèmes à paramètre
Discuter suivant les valeurs du paramètre α des solutions des problèmes linéaires suivants.On s’appliquera a utiliser la méthode du simplexe.
Exercice 22
X1 > 0, X2 > 0,
X1 6 30
X1 + X2 6 20
Max
(1
2X1 + αX2
)
Correction
Si α <1
2. (X1;X2) = (20; 0) et Max
(1
2X1 + αX2
)= 10.
Si α >1
2. (X1;X2) = (0; 20) et Max
(1
2X1 + αX2
)= 20α.
Exercice 23
X1 > 0, X2 > 0,
X1 + 2X2 6 8
2X1 + X2 6 10
Max(X1 + αX2)
Exercice 24
X1 > 0, X2 > 0,
X1 6 400
X2 6 700
X1 + X2 6 800
2X1 + X2 6 1000
Max((2+ α)X1 + 1.5X2)
Exercice 25
X1 > 0, X2 > 0,
X2 6 10
X1 − X2 6 0
X1 + X2 6 20
Max(αX1 + 2X2)
Exercice 26
X1 > 0, X2 > 0, X3 > 0,
X1 + X2 6 60
X1 + X3 6 36
X2 + X3 6 18
Max(αX1 + (α− 1)X2 + (α+ 1)X3)
8
Exercice 27
Un fermier va au marché pour vendre ses poules. Il ne peut vendre que 60 poules de catégorie 1 et 2, 36poules de catégorie 1 et 3 et 18 poules de catégorie 2 et 3. Une poule de catégorie 2 vaut un eurode moins qu’une poule de catégorie et 1 et une poule de catégorie 3 un euro de plus. Le fermier souhaitevendre ses poules au plus bas prix !
1. Il souhaite également s’acheter une chèvre de 60e avec ses bénéfices. Quel prix de vente doit-il alorsappliquer ?
2. En venant au marché il se rappelle que l’anniversaire de sa femme approche ; il décide d’investir sonbénéfice dans une bague à 90e. Quel devra être alors son prix de vente ?
Grand M
Résoudre les problèmes suivants en utilisant la méthode du grand M.
Exercice 28
X1 > 0, X2 > 0,
X1 − X2 = 2
2X1 + 5X2 = 25
Max(X1 + X2)
CorrectionSolution : (X1;X2) = (5; 3) et Max(X1 + X2) = 8.
Exercice 29
X1 > 0, X2 > 0,
−X1 + X2 = 1
X1 + 2X2 = 2
X1 + X2 = 1
Max(8X1 − 4X2)
CorrectionSolution : (X1;X2) = (0; 2) et Max(8X1 − 4X2) = −8
Exercice 30
X1 > 0, X2 > 0,
−X1 + X2 = −1
4X1 + 5X2 = −13
7X1 + 2X2 = 11
Max(X1)
CorrectionIl n’y a pas de solution.
Exercice 31
X1 > 0, X2 > 0, X3 > 0,
X1 + X2 − X3 = 3
−X1 + 3X2 = −4
Max(−X1 + 2X2 − 2X3)
CorrectionSolution : (X1;X2;X3) = (4; 0; 1) et Max(−X1 + 2X2 − 2X3) = −6.
9
Exercice 32
X1 > 0, X2 > 0, X3 > 0,
X1 − X3 = 0
−X1 + X2 − 2X3 = 9
Max(2X1 − 2X2 + X3)
CorrectionSolution : (X1;X2;X3) = (0; 9; 0) et Max(2X1 − 2X2 + X3) = −18.
Exercice 33
X1 > 0, X2 > 0, X3 > 0,
2X1 − X3 = 0
X2 + X3 = 1
Max(2X1 + 4X2 + X3)
CorrectionSolution : (X1;X2;X3) = (0; 1; 0) et Max(2X1 + 4X2 + X3) = 4.
Exercice 34
X1 > 0, X2 > 0, X3 > 0,
3X1 − X2 − X3 = −1
X1 + 2X2 + X3 = 4
Max(X1 + X2 + X3)
CorrectionSolution : (X1;X2;X3) = (3/4; 0; 13/4) et Max(X1 + X2 + X3) = 4.
Dualité
Énoncer les problèmes duaux aux problèmes suivants. On ne demande pas de les résoudre.
Exercice 35
X1 > 0, X2 > 0,
2X1 − 3X2 6 1
−X1 + X2 6 1
Min(−2X1 − X2)
Correction
Le problème dual est Y1 > 0, Y2 > 0,
2Y1 − Y2 > 2
−3Y1 + Y2 > 1
Min(Y1 + Y2)
Exercice 36
X1 > 0, X2 > 0, X3 > 0,
X1 + X2 6 15
X1 + X3 6 10
X2 + X3 6 15
Max(X1 + X2 + X3)
Correction
10
Le problème dual est Y1 > 0, Y2 > 0, Y3 > 0,
Y1 + Y2 > 1
Y1 + Y3 > 1
Y2 + Y3 > 1
Min(15X1 + 10X2 + 15X3)
Exercice 37
X1 > 0, X2 > 0, X3 > 0,
8X1 − X2 + 7X3 6 0
−2X1 + X2 + X3 6 1
Max(X1 + 2X2 − X3)
Correction
Le problème dual est Y1 > 0, Y2 > 0,
8Y1 − 2Y2 6 1
−Y1 + Y2 6 2
7Y1 + Y2 6 −1
Min(Y2)
Exercice 38
X1 6 0, X2 6 0,
−X1 − X2 6 8
X1 − X2 > −4
Min (2X1 − X2)
Exercice 39
X1 > 0, X2 6 0,
6X1 + 3X2 6 3
X1 − 2X2 6 −10
Min (−X1 − 4X2)
Exercice 40
X 6 0, Y > 0,
−X− Y 6 −2
3X− Y 6 −1
−X+ 2Y 6 4
−2X+ Y > 2
Max(Y − 3X)
Exercice 41
X 6 0, Y ∈ R,
2X− Y 6 2
X > −1
X+ Y 6 0
Min(X− Y)
Flot de flux maximal
11
Exercice 42
On considère le graphe métrique suivant suivant :
A1 //
2
��
B
2
��s
2
@@
3// C
1
??
3// p
1. Justifier qu’il s’agit d’un réseau.
2. Enumérer toutes les coupes possibles dans ce réseau et calculer leur valeur.
3. En appliquant l’algorithme de Ford-Fulkerson, déterminer le flot de flux maximal.
Exercice 43
Parmis les graphes suivants déterminer ceux qui sont des réseaux. Pour les graphes qui sont des réseaux,appliquer l’algorithme de Ford-Fulkerson pour déterminer un flot de flux maximum. On s’attachera dans ce casà déterminer une coupe dont la valeur est le flux du flot trouvé.
1. a17 //
77
%%
67
��
b
87
��
h7 // e c
57
ee
g
27
OO
37
99
97 // f d107
oo
117
OO
127
ee
2. s
10
��
8
))
11
��
13// b
4// c
5
��d
9
))e
7
f
6
ii
12
��
3
��g h
2
TT
1// p
3. A
3
��
8
''s
5
@@
2��
C9// p
B
7
??
4. A
15
��
2
��
3
��s
17
??
8// B
5 //
2
��
D
9
tt
12
��
3 // p
C3
//
11
44
E
8
??
5. C
17
��
9
��s
11//
10
33
12
++
B
10
77
7
''
D4//
2
YY
8
��
p
E
17
LL
6. A
16
((
8##
B
11|| 4
��
C
7
��
15))
s
17
99
19
55
21
%%
p
D
28
XX
9 ..E
13
;;
12
66 F
16
MM
11nn
12
7.A
3
��
9 //
5
��
B17 // C
5
��
5
��
11
��s
13
��
7//
11
??
D
3
��
9 // E
13
OO
9
��
3
��
F
3
��
1oo 5 // p
G7
// H17
// I
9
__
15
??
13
