2.26.
Soit le problème de Programmation Linéaire suivant :
Solution :
a) Modifions la deuxième contrainte et la quatrième contrainte afin que leur second membre soit
positif. Ce qui permettra d’obtenir une solution de base admissible. Ce programme peut donc
s’écrire comme :
Forme Canonique Forme standard
Max Z = –10x1 + 4x2 + 4x3 Max Z = –10x1 + 4x2 + 4x3 + 0x4 +0x5+0x6+0x7 – Mx8 – Mx9
Sous les contraintes Sous les contraintes :
–2x1 + x2 + x3 ≤ 4 –2x1 + x2 + x3 + x4 =4
x1 + 2x2 + x3 ≥ 1 x1 + 2x2 + x3 – x5 + x8 =1
– x1 – 2x2 + 3x3 ≤ 2 – x1 – 2x2 + 3x3 + x6 =2
x1 – x2 + x3 2 x1 – x2 + x3 – x7 + x9 = 2
et xj 0 ; j = 1, 2, 3 et xj 0 (j = 1, 2, … 7).
De la forme standard, on peut identifier la matrice I0 formée avec les vecteurs x4, x8, x6 et x9. En lisant les
mêmes variables dans le tableau optimal donné partiellement, on forme la matrice K-1 suivante :
x 4 x8 x6 x9
2 0 − 3/ 2 5/ 2
1 0 −1 2 . Il ne reste plus qu’à compléter ce tableau en multipliant K-1 par les colonnes
1 0 − 1/ 2 3 / 2
6 − 1 − 9 / 2 17 / 2
des variables manquantes, à savoir x1, x3, x5, x7 et Voi, après avoir introduit à gauche du tableau les
colonnes ci et i et en bas la ligne des j.
x1 x3 x5 x7 Voi x1 x3 x5 x7 Voi
2 0 − 3 / 2 5 / 2 − 2 1 0 0 4 0 0 0 − 5 / 2 10
1 0 −1 2 1 1 −1 0 1 = 1 0 0 −2 6
1 0 − 1 / 2 3 / 2 − 1 3 0 0 2 0 1 0 − 3/ 2 6
6 − 1 − 9 / 2 17 / 2 1 1 0 − 1 2 0 0 1 − 17 / 2 31
On obtient alors le tableau optimal suivant :
ci i x1 x2 x3 x4 x5 x6 x7 x8 x9 voi
4 2 0 1 0 2 0 –3/2 –5/2 0 5/2 10
–10 1 1 0 0 1 0 –1 –2 0 2 6
4 3 0 0 1 1 0 –1/2 –3/2 0 3/2 6
0 5 0 0 0 6 1 –9/2 –17/2 –1 17/2 31
ch –10 4 4 0 0 0 0 –M –M Z=4
xi 6 10 6 31
j –2 –2 –4 M M
b) Le dual est :
2
Prof. KAMIANTAKO Miyamueni et Allii Exercices corrigés de MQE
Min Z* = 4y1 – y2 + 2y3 – 2y4 Min Z* = 4y1 – y2 + 2y3 – 2y4+ 0y5 +0y6 +0y7 +My8+My9
Sous les contraintes Sous les contraintes
–2y1 – y2 – y3 – y4 ≥ –10 –2y1 – y2 – y3 – y4 –y5 = –10
y1 – 2y2 – 2y3 + y4 ≥ 4 y1 – 2y2 – 2y3 + y4 – y6 + y8 =4
y1 – y2 + 3y3 – y4 ≥ 4 y1 – y2 + 3y3 – y4 – y7 + y9 = 4
et yj 0 ; j = 1, 2, 3,4 et yj 0 ; j = 1, 2, … 9
Forme Canonique Forme standard
c) Solution du dual
2.27. Résoudre par le dual le programme suivant:
Minimiser Z = 10x1 + 7x2 + 6x3
S/C 3x1 + 4x2 + 2x3 ≥ 15,
2x1 + 3x2 + x3 ≥ 9
x1 + 2x2 + 6x3 ≥ 18,
x2 + x3 ≥ 5
avec x1 ≥ 0, j = 1, 2, 3
2.30. Un étudiant de l'UK
Solution :
Le tableau ci-après résume les données du problème. Soit x1 le nombre de sorties avec Mamie et x2
le nombre de sorties avec Nono.
x1 0 x2 0
Budget par sortie 60 40 480
Heures libres 5 5 50
Energie en calorie 300 600 5400
Max 20 30
Max = 20x1+30x2
60 x1 + 40 x 2 480
5 x1 + 5 x 2 50
s.c.
300 x1 + 600 x 2 5400
x1 0, x 2 0
Le programme ayant seulement 2 variables principales, on peut le résoudre par la méthode
graphique qui nous donne un ensemble convexe avec 5 sommets O, A, B, C, et D dont les
coordonnées sont :
3
Prof. KAMIANTAKO Miyamueni et Allii Exercices corrigés de MQE
O(0, 0) : 0 = 0 (20) + 0 (30) = 0 -
A (0,9) : A = 0 (20) + 9 (30) = 270 -
B (2,8) : B = 2 (20) + 8 (30) =280 -
C (4, 6) : C = 4 (20) + 6 (30) = 260 10 -
D (8, 0) : D = 8 (20) + 0 (30) = 160 A -
- B
L’étudiant organisera 2 heures de sorties avec -
Mamie et 8 avec Nono, ce qui lui rapportera - C
280 unités de loisirs. 5-
-
-
-
-
- | | | | | | | | | | | | | | | | | |
0 5 D 10 15
Si, dans les contraintes fonctionnelles, on remplace les variables xj par leurs valeurs optimales, on
obtient :
60(2) + 40 (8) = 440 < 480
5 (2) + 5 (8) = 50 = 50
300 (2) + 600 (8) = 5400 = 5400
On constate que les deux dernières contraintes sont saturées. Les ressources correspondantes sont rares
car elles ont été pleinement utilisées à l’optimum.
Le simplexe :
Forme canonique Forme standard
Max = 20x1+30x2 Max = 20 x1 + 30 x2 + 0 x3 + 0 x4 +0 x5
60 x1 + 40 x 2 480 Sous contraintes
5 x1 + 5 x 2 50 60 x1 + 40 x 2 + x3 = 480
s.c. 5 x1 + 5 x 2 + x4 = 50
300 x1 + 600 x 2 5400
x1 0, x 2 0 300 x1 + 600 x 2 + x5 = 5400
x1 0, x 2 0, x3 0, x 4 0, x5 0
20 40 0 0 0
ci i x1 x2 x3 x4 x5 Voi Voi/aie
0 3 60 40 1 0 0 480 12
0 4 5 5 0 1 0 50 10
0 5 300 600 0 0 1 5400 9→s
j = cj − zj 20 30↑e =0
0 3 40 0 1 0 –1/15 120 3
0 4 5/2 0 0 1 –5/600 5 2→ s
30 2 1/2 1 0 0 1/600 9 18
4
Prof. KAMIANTAKO Miyamueni et Allii Exercices corrigés de MQE
j = cj − zj 5↑e –1/20 = 270
0 3 0 0 1 –16 20/300 40
20 1 1 0 0 2/5 -–1/300 2
30 2 0 1 0 –1/5 1/300 8
j = cj − zj –2 –1/30 = 280
Le problème dual c’écrit :
Min * = 480 y1 + 50 y2 + 5400 y3
Sous contraintes
60 y1 +5 y2 + 300 y3 20
40 y1 + 5y2 + 600 y3 30
avec y1 0, y2 0 et y3 0
2.37c. Une entreprise dispose de 470 iris
Réponse :
Soit x1, le nombre de bouquets de la première espèce et x2, le nombre de bouquets de la deuxième
espèce. Le problème est de maximiser le prix de vente total R = 39 x1 + 31 x2, sous les contraintes
5 x1 + 2x2 470 et 2x1 + 3 x2 320 avec x1 0 et x2 0.
Ce problème peut être résolu par la méthode graphique car le nombre de variables principales est
égal à 2. L’algorithme du simplexe donne le tableau suivant :
39 31 0 0
ci i x1 x2 x3 x4 Voi Voi/aie
0 3 5 2 1 0 470 94→ s
0 4 2 3 0 1 320 160
j = cj − zj 39 ↑e 31 1 R=0
39 1 1 2/5 1/5 0 94 235
0 4 0 11/5 –2/5 1 132 60→ s
j = cj − zj 82/5↑e –39/5 R = 3666
39 1 1 0 3/11 –2/11 70
31 2 0 1 –2/11 5/11 60
j = cj − zj –5 –7 R = 4590
Tous les j sont négatifs. Le tableau est donc optimal. Ainsi l’entreprise devra vendre 70 bouquets
de 5 iris bleus et 2 tokyos, ainsi que 60 bouquets de 2 iris bleus et 3 tokyos pour gagner un revenu
maximum de 4590 F.
3.27.La société Vetryck envisage de fusionner avec la société Ocayna. Cette stratégie impose des
investigations particulières tant du point de vue des simulations d’évolution de l’environnement
que celui des choix commerciaux liés à ces simulations. L’étude donne les résultats suivants :
Trois simulations parallèles peuvent être retenues pour l’évolution de l’environnement :
- H1 : environnement conforme aux prévisions initiales ;
- H2 : banalisation du produit ;
- H3 : banalisation du produit et apparition de concurrents.
5
Prof. KAMIANTAKO Miyamueni et Allii Exercices corrigés de MQE
Trois stratégies possibles font l’objet d’une attention particulière :
- S1 : distribution par magasins spécialisés à travers le réseau classique ;
- S2 : distribution dans les magasins « grand public » ;
- S3 : distribution par réseau spécialisé appartenant à l’entreprise liée.
Les conséquences financières ont été évaluées comme suit (espérance mathématique des flux
de trésorerie relatifs aux ventes de produits X en millions de francs) :
Etat de l’environnement
H1 H2 H3
S1 –0,25 –0,63 –0,16
S2 0,06 0,03 0,02
S3 0,23 0,15 0,23
1. Indiquer le choix stratégique à suggérer aux dirigeants supposés être :
a) modérément optimistes à 60 %.
b) Indécis
2. Les probabilités pour que H1 et H2 se réalisent sont fixées à 0,2 et 0,6 respectivement.
Quel critère utilisez-vous dans ce cas et indiquez le choix stratégique s’y rapportant.
Solution :
Question 1
a : Critère de Hurwicz avec = 0,60
0,6 (–0,16) + 0,4 (–0,63) = – 0,096 – 0,252 = – 0,348
0,6 (0,06) + 0,4 (0,02) = 0,036 + 0,008 = 0,044
0,6 (0,23) + 0,4 (0,15) = 0,138 + 0,06 = 0,198
Choix : distribution par réseau spécialisé appartenant à l’entreprise
b : Critère de l’insatisfaction (minimax regret)
0,48 0,78 0,33
R = 0,17 0,12 0,021
0 0 0
Regret maximum
0,78
0,21
0,0 (minimax regret)
Choix : distribution par réseau spécialisé appartenant à l’entreprise
Question 2 : Critère de Laplace
Les probabilités pour que H1 et H2 se réalisent sont fixées à 0,2 et 0,6 respectivement.
Quel critère utilisez-vous dans ce cas et indiquez le choix stratégique s’y rapportant.
0,2 (–0,25) + 0,6 (–0,16) + 0,4 (–0,63) = – 0,05 – 0,096 – 0,252 = – 0,398
0,2 (0,06) + 0,6 (0,03) + 0,4 (0,02) = 0,012 + 0,018 + 0,008 = 0,038
0,2 (0,23) + 0,6 (0,15) + 0,4 (0,23) = 0,046 + 0,09 + 0,092 = 0,228
6
Prof. KAMIANTAKO Miyamueni et Allii Exercices corrigés de MQE
Choix : distribution par réseau spécialisé appartenant à l’entreprise
3.33 Idem que l’exercice précédent
Etats de l’environnement
H1 H2 H3
S1 8,8 8,2 5,3
S2 9,2 7,5 5,7
S3 9 7,8 6,2
1. Indiquez le choix stratégique à suggérer aux dirigeants supposés :
a) Indécis
b) Prudent
c) modérément optimistes à 70 %.
2. Les probabilités pour que H1 et H3 se réalisent sont fixées à 0,3 et 0,5 respectivement.
Quel critère utilisez-vous dans ce cas et indiquez le choix stratégique s’y rapportant.
Solution :
Question 1
a) Critère de Savage
0,4 0 0,9
R = 0 0,7 0,5
0,2 0,4 0
Regret maximum
0,9
0,7
0,4 (minimax regret)
Choix : distribution par réseau spécialisé appartenant à l’entreprise
b) Critère de la prudence
Etats de l’environnement Minima des lignes
H1 H2 H3
S1 8,8 8,2 5,3 5,3
S2 9,2 7,5 5,7 5,7
S3 9 7,8 6,2 6,2 Maximin
Choix : distribution par réseau spécialisé appartenant à l’entreprise
c) Critère de Hurwicz avec = 0,70
0,7 (8,8) + 0,3 (5,3) = 6,16 + 1,59 = 7,75
0,7 (9,2) + 0,3 (5,7) = 6,44 + 1,71 = 8,15
0,7 (9,0) + 0,3 (6,2) = 6,3 + 1,86 = 8,16
Choix : distribution par réseau spécialisé appartenant à l’entreprise
Question 2 : Critère de Laplace
7
Prof. KAMIANTAKO Miyamueni et Allii Exercices corrigés de MQE
0,3 (8,8) + 0,2 (8,2) + 0,5 (5,3) = 2,64 + 1,64 + 2,65 = 6,93
0,3 (9,2) + 0,2 (7,5) + 0,5 (5,7) = 2,76 + 1,50 + 2,85 = 7,11
0,3 (9,0) + 0,2 (7,8) + 0,5 (6,2) = 2,70 + 1,56 + 3,10 = 7,36
Choix : distribution par réseau spécialisé appartenant à l’entreprise
3.35. La Bralima et la Bracongo sont
Réponse :
La matrice du jeu est :
Bracongo
D S N
Bralima
D 0 2 5
S 3 –1 6
N –4 –3 0
La stratégie S de la BRALIMA domine la stratégie N. Ceci est vrai aussi pour la BRACONGO.
On peut donc éliminer la dernière ligne et la dernière colonne.
Il n’y a pas de point – selle. C’est donc un jeu de stratégies mixtes.
0 2
Considérons la sous-matrice A = .
3 −1
− 1 − 2
1 1
p1 p2 = − 3 0
=
− 4 − 2 = 2 1
− 1 − 2 1 −6 3 3
1 1 1
− 3 0
− 1 − 3
1 1
q1 q 2 = −2 0
=
− 3 − 3 = 1 1
− 1 − 2 1 −6 2 2
1 1 1
− 3 0
0 2
3 −1 −6
et V = = = 1.
− 1 − 2 1 − 6
1 1
− 3 0 1
La Bralima va s’assurer un gain moyen de 1 en faisant les démonstrations avec la probabilité
de 2/3 et des spots publicitaires avec la probabilité de 1/3.
De son côté, la BRACONGO va s’assurer de ne pas perdre en moyenne plus de 1 en adoptant
les démonstrations dans 50 % des cas et spots publicitaires dans les 50 autres % des cas.
Aucune de 2 n’a intérêt à ne rien faire (N est une stratégie qui dominée par S).
8
Prof. KAMIANTAKO Miyamueni et Allii Exercices corrigés de MQE
Question 4. Un projet informatique
Réponse :
Le dictionnaire des précédents ci-après nous permet de déterminer les niveaux des sommets.
X P(X) Niveaux
A -
B - N0 = {A, B}
C B N1 = {C, D}
D A N2 = {E, F, G}
E C, D N3 = {H}
F C, D
G D
H E, F, G
D’où le graphe MPM ordonné selon les niveaux des sommets :
0 0 9 9 11 15
A 9 D 2
2 G 4
2
8 3
4 5
199 19 22 22
11 11
5 4 1
E H FIN
C0 C1 C2 C3
0 2 5 7 11 14
B C F
Le projet sera réalisé en 22 jours. Le délai de 25 jours sera donc respecté.
a. Détermination des DTO
Evénements DTO
Début te = 0
A tA = 0
B tB = 0
C tC = tB + 5 = 0 + 5 = 5
D tA = tA + 9 =0 + 9 = 9
E tE = max {tD + 2, tC + 4} = max {9 + 2, 5 + 4} = max {11, 9} = 11
F tF = max {tD + 2, tC + 4} = max {9 + 2, 5 + 4} = max {11, 9} = 11
G tG = {tD + 2} = 9 + 2 = 11
H tF = max {tG + 4, tE + 9, tF + 5} = max {11 + 4, 11 + 8, 11 + 5} = max {15, 19, 16} = 19
Fin (s) tF = tH + 3 = 19 + 3 = 22
B) Détermination des DTA
DTO du graphe inversé
Fin (s) Tfin = ts = 22
9
Prof. KAMIANTAKO Miyamueni et Allii Exercices corrigés de MQE
H tH = tfin – 3 = 22 – 3 = 19
G tG = tH – 4 = 19 – 4 = 15
E tE = tH – 8 = 19 – 8 = 11
F tF = tH – 5 = 19 – 5 = 14
D tD = min {tG – 2, tE – 2, tF – 2} = min {15 – 2, 11 – 2, 14 – 2} = min {13, 9, 12} = 9
C tc = min {tE – 4, tF – 4} = min {11 – 4, 14 – 4} = min { 7, 10} = 7
B tB = tC – 5 = 7 – 5 = 2
A tA = tD – 9 = 9 – 9 = 0
Début
