IUT Dijon-Auxerre

GEA 2ème année, GMO, 2015-2016

Correction du Contrôle Continu no 1

Exercice 1 : On considère le problème d’optimisation suivant :



 maximiser z = 5x1 + 2x2
 sous 2x1 + x2 ≤ 70


(PI ) x1 ≤ 30 .
x + x ≥ 10

1 2



x1 , x2 ≥ 0


1. Après l’introduction de variables d’écart positives e1 , e2 et e3 , le problème se réécrit sous forme standard de
la manière suivante : 

 maximiser z = 5x1 + 2x2
 sous 2x1 + x2 + e1 = 70


(PS ) x1 + e2 = 30 .
x + x − e = 10

1 2 3



x1 , x2 , e1 , e2 , e3 ≥ 0


2. La troisième contrainte ne permet pas de choix évident d’une variable de base : le choix de e3 comme variable
de base conduirait à une contradiction (e3 serait négatif) et les variables x1 et x2 sont présentes dans les
autres contraintes. On doit donc utiliser la méthode des deux phases et on doit formuler un problème artificiel
pour soit trouver une solution de base réalisable soit détecter l’impossibilité.
Après l’introduction d’une variable artificielle w1 et en intégrant l’objectif dans les contraintes, le problème
artificiel associé à (PI ) s’écrit sous la forme :


 minimiser zA = w1
sous 2x1 + x2 + e1 = 70




x1 + e2 = 30

(PA ) .

 x1 + x2 − e3 + w1 = 10
5x1 + 2x2 − z = 0




x1 , x2 , e1 , e2 , e3 , w1 ≥ 0


Phase I : Nous pouvons maintenant débuter l’application de l’algorithme du simplexe en phase I par la
méthode des tableaux avec pour variables de base initiales e1 , e2 et w1 . Le premier tableau est le suivant :
HH
H v. x1 x2 e1 e2 e3 w1 −z −zA b
v.b. HHH
e1 2 1 1 0 0 0 0 0 70
e2 1 0 0 1 0 0 0 0 30
w1 1 1 0 0 -1 1 0 0 10
−z 5 2 0 0 0 0 1 0 0
−zA 0 0 0 0 0 1 0 1 0

On exprime l’objectif artificiel zA en fonction des ”vraies” variables du problème en mettant à 0 le coefficient
de w1 dans la ligne de −zA par l’opération L5 ← L5 − L3 . On obtient le tableau :

1
 HH
H v. x1 x2 e1 e2 e3 w1 −z −zA b
v.b. HHH
e1 2 1 1 0 0 0 0 0 70
e2 1 0 0 1 0 0 0 0 30
w1 1 1 0 0 -1 1 0 0 10
−z 5 2 0 0 0 0 1 0 0
−zA -1 -1 0 0 1 0 0 1 -10

Nous traitons un problème de minimisation de zA et la ligne de −zA contient des coefficients strictement
négatifs. Nous allons pouvoir faire entrer une nouvelle variable dans la base. Celle-ci doit être telle que le
coefficient correspondant dans la ligne de −zA soit le ”plus négatif” possible. Les variables x1 et x2 sont
ex-æquo et nous choisissons (arbitrairement) de faire entrer x1 dans la base. Pour déterminer la variable
sortante, nous calculons les quotients des coefficients de la colonne de b sur les coefficients de la colonne de
x1 dans les lignes 1 à 3. On obtient :
— 35 pour e1 ,
— 30 pour e2 ,
— 10 pour w1 .
On doit faire sortir de la base la variable correspondant au quotient le plus petit parmi les positifs, c’est-à-dire
w1 . On doit ensuite utiliser la méthode de Gauss-Jordan pour mettre un 1 dans la case repérée par x1 et
x1 et des 0 dans le reste de la colonne de x1 . En effectuant les opérations L1 ← L1 − 2L3 , L2 ← L2 − L3 ,
L4 ← L4 − 5L3 et L5 ← L5 + L3 , on obtient :
HH
H v. x1 x2 e1 e2 e3 w1 −z −zA b
v.b. HHH
e1 0 -1 1 0 2 -2 0 0 50
e2 0 -1 0 1 1 -1 0 0 20
x1 1 1 0 0 -1 1 0 0 10
−z 0 -3 0 0 5 -5 1 0 -50
−zA 0 0 0 0 0 1 0 1 0

Il ne reste plus de coefficient strictement négatif dans la ligne de −zA et l’algorithme s’arrête. La valeur optimale
de l’objectif artificiel est 0 et on a déterminé un sommet de l’ensemble des solutions admissibles pour (PS ) :
   
x1 10
 x2   0 
   
 e1  =  50  .
   
 e2   20 
e3 0

On peut maintenant supprimer les variables artificielles et l’objectif artificiel pour passer à la phase II de
maximisation de z.

Phase II La phase II débute avec le tableau suivant :

HH
H v. x1 x2 e1 e2 e3 −z b
v.b. HHH
e1 0 -1 1 0 2 0 50
e2 0 -1 0 1 1 0 20
x1 1 1 0 0 -1 0 10
−z 0 -3 0 0 5 1 -50

2
 Nous traitons un problème de maximisation de z et la ligne de −z contient des coefficients positifs. Nous allons
pouvoir faire entrer une nouvelle variable dans la base. Celle-ci doit être telle que le coefficient correspondant dans
la ligne de −z soit le ”plus positif” possible. Il s’agit de e3 . Pour déterminer la variable sortante, nous calculons les
quotients des coefficients de la colonne de b sur les coefficients de la colonne de e3 dans les lignes 1 à 3. On obtient :
— 25 pour e1 ,
— 20 pour e2 ,
— −10 pour x1 .
On doit faire sortir de la base la variable correspondant au quotient le plus petit parmi les positifs. On choisit donc
de faire sortir e2 . On doit ensuite utiliser la méthode de Gauss-Jordan pour mettre un 1 dans la case repérée par
e2 et e2 puis des 0 dans le reste de la colonne de e4 . En effectuant les opérations L1 ← L1 − 2L2 , L3 ← L3 + L2 et
L4 ← L4 − 5L2 , on obtient :
HH
H v. x1 x2 e1 e2 e3 −z b
v.b. HHH
e1 0 1 1 -2 0 0 10
e3 0 -1 0 1 1 0 20
x1 1 0 0 1 0 0 30
−z 0 2 0 -5 0 1 -150

Cette fois, x2 est la variable entrante. Nous calculons les quotients des coefficients de la colonne de b sur les
coefficients de la colonne de x2 dans les lignes 1 à 3 :
— 10 pour e1 ,
— −20 pour e3 ,
— ∞ pour x1 ,
et nous choisissons de faire sortir e1 de la base.
Les opérations L2 ← L2 + L1 et L4 ← L4 − 2L1 donnent :
HH
H v. x1 x2 e1 e2 e3 −z b
v.b. HHH
x2 0 1 1 -2 0 0 10
e3 0 0 1 -1 1 0 30
x1 1 0 0 1 0 0 30
−z 0 0 -2 -1 0 1 -170

Il ne reste plus de coefficient strictement positif dans la ligne de −z (sauf dans la case repérée par −z et −z) et
l’algorithme s’arrête. On a déterminé une solution optimale du problème (PI ) :

z ∗ = 170

atteinte en (x∗1 , x∗2 ) = (30, 10).

Exercice 2 :
1. (a) Définition des variables : Pour i = 1, 2, on note xi le nombre d’instruments Ci produits en un mois.
(b) Définition des contraintes :
i. Contrainte liée au nombre de systèmes de palettes disponibles chaque mois :

x1 ≤ 30.

ii. Contrainte liée au nombre de branches d’embouchure disponibles chaque mois :

x1 + x2 ≤ 100.

3
 iii. Contrainte liée au nombre de soudures réalisables en un mois :
1
x1 + x2 ≤ 35,
2
soit en multipliant par 2
2x1 + x2 ≤ 70.
iv. Contrainte liée au contrat avec le distributeur :

x1 + x2 ≥ 10.

v. Contraintes de ”bon sens” :

x1 ∈ N et x2 ∈ N
que l’on relâche en x1 , x2 ≥ 0.
(c) Définition de l’objectif : Le facteur d’instruments souhaite maximiser sa marge mensuelle brute :

z = 5x1 + 2x2

exprimée en centaines d’euros.

(d) Formulation du problème :


 maximiser z = 5x1 + 2x2
sous 2x1 + x2 ≤ 70




x1 ≤ 30

(P) .

 x1 + x2 ≤ 100
x1 + x2 ≥ 10




x1 , x2 ≥ 0


(e) On remarque que ce problème est très similaire au problème (PI ) de l’Exercice 1. Plus précisément, les
deux problèmes ne diffèrent que par la contrainte x1 + x2 ≤ 100 présente dans (P) mais pas dans (PI ).
2. La contrainte présente dans (P) mais pas dans (PI ) n’est pas saturée par la solution optimale de (PI ) :
(x∗1 , x∗2 ) = (30, 10) (30 + 10 = 40 < 100). On en déduit qu’une solution optimale de (P) est

z ∗ = 170

atteinte en (x∗1 , x∗2 ) = (30, 10). Le facteur d’instruments maximisera sa marge mensuelle brute en produisant
30 cors d’harmonie et 10 cors naturels par mois. Sa marge mensuelle brute sera alors de 17000¤.