UNIVERSITÉ PARIS OUEST NANTERRE LA DÉFENSE
U.F.R. SEGMI
Master d’économie
Année universitaire 2012 – 2013
Cours de M. Desgraupes
Méthodes Numériques
Document 4 : Corrigé des exercices d’optimisation linéaire
1 Programmation linéaire
. . . . . . . . . . . . . . . . . . . . . . . . . . .
.
Méthode du simplexe .
. . . . . . . . . . . . . . . . . . . . . . . . . . .
.
.
Raffinerie de pétrole .
Méthode des variables ajoutées . . . . . . . . . . . . . . . . . . . . . . . .
Indices d’octane .
. . . . . . . . . . . . . . . . . . . . . . . . . .
Fabrique de pièces détachées . . . . . . . . . . . . . . . . . . . . . . . . .
Plan de production de moteurs
. . . . . . . . . . . . . . . . . . . . . . . .
Excavation et matériaux de carrière . . . . . . . . . . . . . . . . . . . . . .
.
.
.
.
.
2 Dualité
Main d’oeuvre et équipements
. . . . . . . . . . . . . . . . . . . . . . . .
Trois techniques de production . . . . . . . . . . . . . . . . . . . . . . . .
Production en heures-machines . . . . . . . . . . . . . . . . . . . . . . . .
1
1
4
6
11
13
15
17
19
19
21
22
1 Programmation linéaire
Corrigé ex. 1 : Méthode du simplexe
Programme 1
Max (x1 + 2x2)
x1 + 3x2 ≤ 21
−x1 + 3x2 ≤ 18
x1 − x2 ≤ 5
x1 et x2 ≥ 0
On introduit des variables d’écart, ce qui conduit aux équations suivantes pour les
contraintes du problème :
x1 + 3x2 + x3
= 21
−x1 + 3x2 + x4 = 18
= 5
x1 − x2 + x5
Le premier tableau du simplexe s’écrit :
1
x1
1
-1
1
-1
x2
3
3
-1
-2
x3
1
0
0
0
x4
0
1
0
0
x5
0
0
1
0
x3
x4
x5
21
18
5
0
La variable entrante est x2 qui correspond à l’élément le plus négatif de la dernière
ligne. La variable sortante se calcule en trouvant le plus petit rapport positif entre la
colonne de droite et la colonne de x2 (colonne entrante) :
Min
(cid:16) 21
3
(cid:17)
,
18
3
=
18
3
= 6
Donc x4 est la variable sortante. La ligne de x4 sert de ligne pivot et on exécute une
transformation du pivot autour de la valeur 3 (à l’intersection de la ligne de x4 et de la
colonne de x2).
On obtient le tableau suivant :
x1
2
-1/3
2/3
-5/3
x2
0
1
0
0
x3
1
0
0
0
x4
-1
1/3
1/3
2/3
x5
0
0
1
0
x3
x2
x5
3
6
11
12
Maintenant c’est x1 qui entre et x3 qui sort car :
Min
(cid:16) 3
2
(cid:17)
,
11
2/3
=
3
2
Un nouveau pivot autour du nombre 2 (à l’intersection de la ligne de x3 et de la colonne
de x1) conduit au tableau suivant :
x1
1
0
0
0
x2
0
1
0
0
x3
1/2
1/6
-1/3
5/6
x4
-1/2
1/6
2/3
-1/6
x5
0
0
1
0
x1
x2
x5
3/2
13/2
10
29/2
Maintenant c’est x4 qui entre et x5 qui sort car :
Min
(cid:16) 13/2
1/6
(cid:17)
,
10
2/3
=
10
2/3
= 15
Un nouveau pivot autour du nombre 2/3 (à l’intersection de la ligne de x5 et de la
colonne de x4) conduit au tableau suivant :
x5
3/4
-1/4
3/2
1/4
x1
x2
x4
9
4
15
17
x1
1
0
0
0
x2
0
1
0
0
x3
1/4
1/4
-1/2
3/4
x4
0
0
1
0
2
Ce tableau correspond à l’optimum car il n’y a plus de termes négatifs dans la
dernière ligne. On obtient donc comme solution :
x∗
1 = 9
x∗
2 = 4
x∗
3 = 0
x∗
4 = 15
x∗
5 = 0
La première et la troisième contrainte sont saturées.
Programme 2
Min (x1 − 3x2)
3x1 − 2x2 ≤ 7
−x1 + 4x2 ≤ 9
−2x1 + 3x2 ≤ 6
x1 et x2 ≥ 0
On transforme le problème en une maximisation en changeant le signe de la fonc-
tion objectif :
On introduit ensuite les variables d’écart comme ceci :
Max (−x1 + 3x2)
3x1 − 2x2 + x3 = 7
−x1 + 4x2 + x4 = 9
−2x1 + 3x2 + x5 = 6
x1 et x2 ≥ 0
Le tableau de départ pour la méthode du simplexe est donc :
x1
3
-1
-2
1
x2
-2
4
3
-3
x3
1
0
0
0
x4
0
1
0
0
x5
0
0
1
0
x3
x4
x5
7
9
6
0
La variable entrante est x2 qui correspond à l’élément le plus négatif de la dernière
ligne. La variable sortante se calcule en trouvant le plus petit rapport positif entre la
colonne de droite et la colonne de x2 (colonne entrante) :
Min
(cid:16) 9
4
(cid:17)
,
6
3
=
6
3
= 2
Donc x5 est la variable sortante. La ligne de x5 sert de ligne pivot / on exécute une
transformation du pivot autour de la valeur 3 (à l’intersection de la ligne de x5 et de la
colonne de x2).
Cela conduit au tableau suivant :
3
x1
5/3
5/3
-2/3
-1
x2
0
0
1
0
x3
1
0
0
0
x4
0
1
0
0
x5
2/3
-4/3
1/3
1
x3
x4
x2
11
1
2
6
Cette fois la variable x1 entre dans la base et la variable x4 sort car :
(cid:16) 11
5/3
1
5/3
Min
3
5
=
(cid:17)
,
Le pivot se fait autour de la valeur 5/3 (à l’intersection de la ligne de x4 et de la
colonne de x1). On obtient alors le tableau suivant :
x1
0
1
0
0
x2
0
0
1
0
x3
1
0
0
0
x4
-1
3/5
2/5
3/5
x5
2
-4/5
-1/5
1/5
x3
x1
x2
10
3/5
12/5
33/5
Il n’y a plus de terme négatif dans la dernière ligne et on est donc à l’optimum. La
solution est :
x∗
1 = 3/5
x∗
2 = 12/5
x∗
3 = 10
x∗
4 = 0
x∗
5 = 0
La deuxième et la troisième contrainte sont saturées. Il ne faut pas oublier de re-
changer le signe de la fonction objectif : la valeur à l’optimum est -33/5 (alors que la
case inférieure droite du tableau indique 33/5 car ce tableau correspond à la maximisa-
tion de −f ).
Corrigé ex. 2 : Raffinerie de pétrole
On désigne par x1 et x2 les quantités de brut 1 et 2 qu’il faut traiter. La fonction
objectif est la marge totale, qu’il faut maximiser :
Les contraintes de production s’expriment sous la forme suivante :
Max (3x1 + 4x2)
0, 25x1 + 0, 35x2 ≤ 825
0, 30x1 + 0, 30x2 ≤ 750
Publicité
0, 45x1 + 0, 35x2 ≤ 1065
qui se simplifient sous la forme suivante :
5x1 + 7x2 ≤ 16500
x1 + x2
≤ 2500
9x1 + 7x2 ≤ 21300
4
Si on note x3, x4, x5 les variables d’écart, les contraintes deviennent :
5x1 + 7x2 + x3 = 16500
x1 + x2 + x4
= 2500
9x1 + 7x2 + x5 = 21300
Les tableaux du simplexe sont successivement :
Tableau 1
x1
5
1
9
-3
x2
7
1
7
-4
x3
1
0
0
0
x4
0
1
0
0
x5
0
0
1
0
16500
2500
21300
0
x3
x4
x5
x2 entre et x3 sort.
Tableau 2
x1
5/7
2/7
4
-1/7
x1 entre et x4 sort.
Tableau 3
x1
0
1
0
0
x2
1
0
0
0
x2
1
0
0
0
x3
1/7
-1/7
-1
4/7
x4
0
1
0
0
x5
0
0
1
0
16500/7
1000/7
4800
66000/7
x2
x4
x5
x3
1/2
-1/2
1
1/2
x4
-5/2
7/2
-14
1/2
x5
0
0
1
0
x2
x1
x5
2000
500
2800
9500
Il n’y a plus de terme négatif dans la dernière ligne et on est donc à l’optimum. La
solution est :
x∗
1 = 500
x∗
2 = 2000
x∗
3 = 0
x∗
4 = 0
x∗
5 = 2800
La valeur à l’optimum est f ∗ = 9500. La première et le deuxième contrainte sont
saturées : les quotas imposés pour l’essence et le gasoil sont atteints. La troisième
présente un écart de 140 (le tableau indique 2800 mais cette contrainte avait été divisée
par 20 avant d’être insérée dans le tableau) : cela signifie que le quota de 1065 imposé
sur le fuel n’est pas atteint et qu’on fabrique seulement 1065 − 140 = 925 milliers de
m3 de fuel.
5
Corrigé ex. 3 : Méthode des variables ajoutées
Les deux programmes d’optimisation de cet exercice présentent une difficulté sup-
plémentaire pour appliquer la méthode du simplexe : on ne peut pas démarrer le sim-
plexe à partir de l’origine (c’est-à-dire à partir du point de coordonnées nulles) car ce
point ne vérifie pas les contraintes. L’origine ne fait pas partie du domaine réalisable.
Il faut donc trouver un point de départ dans le domaine réalisable, autrement dit
trouver un point à coordonnées positives qui vérifie les équations des contraintes. On
utilise pour cela la méthode des variables ajoutées. Elle consiste à introduire des va-
riables supplémentaires x1,a, x2,a, . . . dans les contraintes et à chercher à les annuler.
Comme ce sont des variables positives, il suffit d’annuler leur somme et on en fait un
problème d’optimisation en fixant comme objectif de minimiser cette somme :
Min
(cid:88)
xj,a
j
Il y a autant de variables ajoutées qu’il y a de contraintes.
Programme 1
Max (x1 − x2 + x3)
−3x1 + 2x2 + x3 = 1
x1 − x2 − x3 + x4 = 3
x1 + 4x2 + 2x3 − 2x4 = 1
x1, x2, x3 et x4 ≥ 0
On introduit 3 variables positives x1,a, x2,a, x3,a dans les contraintes et on cherche
à minimiser la fonction objectif x1,a + x2,a + x3,a. On se ramène à un problème de
maximisation en changeant le signe de cette fonction objectif. Le problème s’écrit donc
sous la forme suivante
Max (−x1,a − x2,a − x3,a)
−3x1 +2x2 +x3
+x1,a
x1 −x2 −x3 +x4
x1 +4x2 +2x3 −2x4
+x2,a
= 1
= 3
+x3,a = 1
avec les contraintes
x1, x2, x3, x4, x1,a, x2,a, x3,a ≥ 0
La fonction objective initiale du problème est pour le moment ignorée. Le problème
avec les variables ajoutées peut se traiter au moyen de la méthode du simplexe ordi-
naire. La configuration de départ consiste à annuler les variables x1, x2, x3, x4 qui sont
ainsi des variables hors-base. Les variables de base sont donc au départ :
x1,a = 1
x2,a = 3
x3,a = 1
Très important : il faut veiller à ce que la fonction objectif (−x1,a − x2,a − x3,a)
soit exprimée en fonction des variables hors-base. C’est une règle qui doit toujours être
vérifiée :
6
À tous les stades de la méthode du simplexe, la fonction objectif et les variables
de base doivent être exprimées en fonction des variables hors-base.
On doit donc, avant de commencer, extraire x1,a, x2,a, x3,a en fonction de x1, x2, x3, x4
et les remplacer dans la fonction objectif. On a :
x1,a = 1 + 3x1 − 2x2 − x3
x2,a = 3 − x1 + x2 + x3 − x4
x3,a = 1 − x1 − 4x2 − 2x3 + 2x4
D’où
−x1,a − x2,a − x3,a = −5 − x1 + 5x2 + 2x3 − x4
À partir de là, la méthode du simplexe s’applique sans problèmes.
Tableau 1
x1
-3
1
1
1
x2
2
-1
4
-5
x3
1
-1
2
-2
x4
0
1
-2
1
x1,a
1
0
0
0
x1,a
0
1
0
0
x3,a
0
0
1
0
x1,a
x2,a
x3,a
1
3
1
-5
x2 entre et x3,a sort.
Tableau 2
x1
-7/2
5/4
1/4
9/4
x2
0
0
1
0
x3
0
-1/2
1/2
1/2
x4
1
1/2
-1/2
-3/2
x1,a
1
0
0
0
x1,a
0
1
0
0
x3,a
-1/2
1/4
1/4
5/4
x1,a
x2,a
x2
1/2
13/4
1/4
-15/4
x4 entre et x1,a sort.
Tableau 3
x1
-7/2
3
-3/2
-3
x1 entre et x2,a sort.
Tableau 4
x1
0
1
0
0
x2
0
0
1
0
x2
0
0
1
0
x3
0
-1/2
1/2
1/2
x4
1
0
0
0
x1,a
1
-1/2
1/2
3/2
x1,a
0
1
0
0
x3,a
-1/2
1/2
0
1/2
x4
x2,a
x2
1/2
3
1/2
-3
x3
-7/12
-1/6
1/4
0
x4
1
0
0
0
x1,a
5/12
-1/6
1/4
1
x1,a
7/6
1/3
1/2
1
x3,a
1/12
1/6
1/4
1
x4
x1
x2
4
1
2
0
Dans le dernier tableau, les trois variables ajoutées sont sorties de la base. Elles
sont donc nulles, ce qui était l’objectif. Cela signifie que les variables qui sont main-
tenant dans la base constituent une solution à coordonnées positives pour le système
7
des contraintes. On a donc trouvé un point de départ pour résoudre le problème de
l’exercice. C’est le point de coordonnées (ici x3 est nulle car elle est hors-base ) :
x1 = 1
x2 = 2
x3 = 0
x4 = 4
On peut donc maintenant traiter le problème posé à partir du point trouvé. On com-
mence par supprimer, dans le dernier tableau calculé, les colonnes des variables ajou-
tées :
x1
0
1
0
x2
0
0
1
x3
-7/12
-1/6
1/4
x4
1
0
0
4
1
2
x4
x1
x2
Dans ce tableau, on voit que les variables x1, x2 et x4 sont dans la base et que
la variable x3 est hors-base. On peut l’interpréter comme le système de contraintes
suivant :
− 7
12 x3 + x4 = 4
x1 − 1
6 x3 = 1
Publicité
x2 + 1
4 x3 = 2
La dernière ligne doit contenir la fonction objectif initiale x1 − x2 + x3 mais celle-
ci doit être exprimée, comme toujours, en fonction de la ou des variable(s) hors-base
uniquement. Le système précédent permet facilement de tout exprimer en fonction de
x3. On trouve :
Le tableau du simplexe s’écrit donc
x1 − x2 + x3 = −1 +
17
12
x3
x1
0
1
0
0
x2
0
0
1
0
x3
-7/12
-1/6
1/4
-17/12
x4
1
0
0
0
x4
x1
x2
4
1
2
-1
La variable x3 entre et x2 sort. Par pivot, on obtient le tableau suivant :
x3
0
0
1
0
x2
7/3
2/3
4
17/3
26/3
7/3
8
31/3
x4
1
0
0
0
x1
0
1
0
0
x4
x1
x3
On est maintenant à l’optimum et la solution du problème est :
x∗
1 = 7/3
x∗
2 = 0
x∗
3 = 8
x∗
4 = 26/3
La valeur à l’optimum est f ∗ = 31/3.
8
Programme 2
Max (x1 + 2x2 + 3x3)
x1 + x2 ≤ 5
2x1 + 2x2 − x3 = 6
12x1 + 8x2 − 5x3 = 32
x1, x2 et x3 ≥ 0
Dans ce problème, la première contrainte est une inégalité, donc il faut commencer par
introduire une variable d’écart x4. On introduit ensuite les variables ajoutées comme
dans l’exercice précédent. Le problème s’écrit sous la forme
Max (−x1,a − x2,a − x3,a)
avec le système de contraintes suivant :
x1 +x2
2x1 +2x2 −x3
12x1 +8x2 −5x3
+x4 + x1,a
+x2,a
= 5
= 6
+x3,a = 32
avec x1, x2, x3, x4, x1,a, x2,a, x3,a ≥ 0.
La configuration de départ consiste à annuler les variables x1, x2, x3, x4 qui sont
ainsi des variables hors-base. Les variables de base sont donc au départ :
x1,a = 5
x2,a = 6
x3,a = 32
Très important : il faut veiller à ce que la fonction objectif (−x1,a − x2,a − x3,a)
soit exprimée en fonction des variables hors-base. On doit donc, avant de commencer,
extraire x1,a, x2,a, x3,a en fonction de x1, x2, x3, x4 et les remplacer dans la fonction
objectif. On a :
x1,a = 5 − x1 − x2 − x4
x2,a = 6 − 2x1 − 2x2 + x3
x3,a = 32 − 12x1 − 8x2 + 5x3
D’où
−x1,a − x2,a − x3,a = −43 + 15x1 + 11x2 − 6x3 + x4
À partir de là, la méthode du simplexe s’applique sans problèmes :
Tableau 1
x1
1
2
12
-15
x2
1
2
8
-11
x3
0
-1
-5
6
x4
1
0
0
-1
x1,a
1
0
0
0
x1,a
0
1
0
0
x3,a
0
0
1
0
x1,a
x2,a
x3,a
5
6
32
-43
x1 entre et x3,a sort.
Tableau 2
9
x1
0
0
1
0
x2
1/3
2/3
2/3
-1
x3
5/12
-1/6
-5/12
-1/4
x2 entre et x2,a sort.
Tableau 3
x1
0
0
1
0
x2
0
1
0
0
x3
1/2
-1/4
-1/4
-1/2
x4 entre et x1,a sort.
Tableau 4
x4
1
0
0
-1
x4
1
0
0
-1
x1,a
1
0
0
0
x1,a
0
1
0
0
x3,a
-1/12
-1/6
1/12
5/4
x1,a
x2,a
x1
7/3
2/3
8/3
-3
x1,a
1
0
0
0
x1,a
-1/2
3/2
-1
3/2
x3,a
0
-1/4
1/4
1
x1,a
x2
x1
2
1
2
-2
x1
0
0
1
0
x2
0
1
0
0
x3
1/2
-1/4
-1/4
0
x4
1
0
0
0
x1,a
1
0
0
1
x1,a
-1/2
3/2
-1
1
x3,a
0
-1/4
1/4
1
x4
x2
x1
2
1
2
0
Dans le dernier tableau, les trois variables ajoutées sont sorties de la base. Elles
sont donc nulles, ce qui était l’objectif. Cela signifie que les variables qui sont main-
tenant dans la base constituent une solution à coordonnées positives pour le système
des contraintes. On a donc trouvé un point de départ pour résoudre le problème de
l’exercice. C’est le point de coordonnées (ici x3 est nulle car elle est hors-base ) :
x1 = 1
x2 = 2
x3 = 0
x4 = 2
On peut donc maintenant traiter le problème posé à partir du point trouvé. On com-
mence par supprimer, dans le dernier tableau calculé, les colonnes des variables ajou-
tées :
x1
0
0
1
x2
0
1
0
x3
1/2
-1/4
-1/4
x4
1
0
0
2
1
2
x4
x2
x1
Dans ce tableau, on voit que les variables x1, x2 et x4 sont dans la base et que
la variable x3 est hors-base. On peut l’interpréter comme le système de contraintes
suivant :
1
2
x2 −
x1 −
x3 + x4 = 2
1
4
1
4
x3 = 1
x3 = 2
10
La dernière ligne doit contenir la fonction objectif initiale x1 + 2x2 + 3x3 mais
celle-ci doit être exprimée, comme toujours, en fonction de la ou des variable(s) hors-
base uniquement. Le système précédent permet facilement de tout exprimer en fonction
de x3 qui est ici l’unique variable hors-base. On trouve :
x1 + 2x2 + 3x3 = 4 +
15
4
x3
Le tableau du simplexe s’écrit donc
x1
0
0
1
0
x2
0
1
0
0
x3
1/2
-1/4
-1/4
-15/4
x4
1
0
0
0
x4
x2
x1
2
1
2
4
La variable x3 entre et x4 sort. Par pivot, on obtient le tableau suivant :
x1
0
0
1
0
x2
0
1
0
0
x3
1
0
0
0
x4
2
1/2
1/2
15/2
x3
x2
x1
4
2
3
19
On est maintenant à l’optimum et la solution du problème est :
x∗
1 = 3
x∗
2 = 2
x∗
3 = 4
x∗
4 = 0
La valeur à l’optimum est f ∗ = 19.
Publicité
Corrigé ex. 4 : Indices d’octane
On désigne par x1A et x2A (resp. x1B et x2B) le nombre de barils de P1 et de P2
utilisés pour fabriquer les essences A (resp. B).
Indice d’octane des essences A et B :
IA =
71x1A + 99x2A
x1A + x2A
71x1B + 99x2B
x1B + x2B
Les contraintes s’écrivent : IA ≥ 96 et IB ≥ 85, ce qui conduit, après regroupe-
IB =
ment des termes, aux inégalités suivantes :
(cid:40)
25x1A − 3x2A ≤ 0
≤ 0
x1B − x2B
11
Les containtes de disponibilité des ressources P1 et P2 s’écrivent comme ceci :
(cid:40)
x1A + x1B ≤ 3900
x2A − x2B ≤ 5000
La fonction objectif est :
f = 3, 75(x1A + x2A) + 2, 75(x1B + x2B)
+ 1, 25(3900 − x1A − x1B) + 2, 25(5000 − x2A − x2B)
= 2, 5x1A + 1, 5x2A + 1, 5x1B + 0, 5x2B + 16125
Notons x(cid:48)
1, x(cid:48)
simplexe s’écrit :
2, x(cid:48)
3, x(cid:48)
4 les variables d’écart. Le tableau de départ de la méthode du
Tableau 1
x1A
25
0
1
0
-2,5
x2A
-3
0
0
1
-1,5
x1B
0
1
1
0
-1,5
x2B
0
-1
0
1
-0,5
x(cid:48)
1
1
0
0
0
0
x(cid:48)
2
0
1
0
0
0
x(cid:48)
3
0
0
1
0
0
x(cid:48)
4
0
0
0
1
0
0
0
3900
5000
16125
x(cid:48)
1
x(cid:48)
2
x(cid:48)
3
x(cid:48)
4
x1A entre et x(cid:48)
1 sort.
Tableau 2
x1A
1
0
0
0
0
x2A
-3/25
0
3/25
1
-1,8
x1B
0
1
1
0
-1,5
x2B
0
-1
0
1
-0,5
x(cid:48)
1
1/25
0
-1/25
0
0,1
x(cid:48)
2
0
1
0
0
0
x(cid:48)
3
0
0
1
0
0
x(cid:48)
4
0
0
0
1
0
0
0
3900
5000
16125
x1A
x(cid:48)
2
x(cid:48)
3
x(cid:48)
4
x2A entre et x(cid:48)
4 sort.
Tableau 3
x1A
1
0
0
0
0
x2A
0
0
0
1
0
x1B
0
1
1
0
-1,5
x2B
3/25
-1
-3/25
1
1,3
x(cid:48)
1
1/25
0
-1/25
0
0,1
x1B entre et x(cid:48)
2 sort.
Tableau 4
x1A
1
0
0
0
0
x2A
0
0
0
1
0
x1B
0
1
0
0
0
x2B
3/25
-1
22/25
1
-0,2
x(cid:48)
1
1/25
0
-1/25
0
0,1
x(cid:48)
2
0
1
0
0
0
x(cid:48)
2
0
1
-1
0
1,5
x(cid:48)
3
0
0
1
0
0
x(cid:48)
3
0
0
1
0
0
x(cid:48)
4
3/25
0
-3/25
1
1,8
x(cid:48)
4
3/25
0
-3/25
1
1,8
600
0
3300
5000
25125
x1A
x(cid:48)
2
x(cid:48)
3
x2A
600
0
3300
5000
25125
x1A
x1B
x(cid:48)
3
x2A
12
x2B entre et x(cid:48)
3 sort.
Tableau 5
x1A
1
0
0
0
0
x2A
0
0
0
1
0
x1B
0
1
0
0
0
x2B
0
0
1
0
0
x(cid:48)
1
1/22
-1/22
-1/22
1/22
1/11
x(cid:48)
2
3/22
-3/22
-25/22
25/22
14/11
x(cid:48)
3
-3/22
25/22
25/22
-25/22
2,5/11
x(cid:48)
4
3/22
-3/22
-3/22
25/22
19,5/11
150
3750
3750
1250
25875
x1A
x1B
x2B
x2A
On est maintenant à l’optimum. La solution est
x∗
1A = 150
x∗
2A = 1250
x∗
1B = 3750
x∗
2B = 3750
f ∗
= 25875
On fabrique donc 1400 (= 150+1250) barils d’essence A et 7500 (= 3750+3750)
barils d’essence B.
Les quatre variables d’écart sont nulles, ce qui signifie que les quatre contraintes
sont saturées : il n’y a aucun reliquat de produits P1 et P2 et les indices d’octane
obtenus sont respectivement de 96 et 85.
Corrigé ex. 5 : Fabrique de pièces détachées
On désigne par x1 et x2 le nombre de lots de 100 pièces de type A et B respective-
ment.
Les contraintes de disponibilité des trois ateliers conduisent aux inéquations sui-
vantes :
2x1 + x2
≤ 200
x1 + 4, 5x2 ≤ 540
4x1 + 3x2 ≤ 480
Si on note x3, x4, x5 les variables d’écart, les contraintes deviennent :
= 200
2x1 + x2 + x3
x1 + 4, 5x2 + x4 = 540
4x1 + 3x2 + x5 = 480
La marge sur coût variable unitaire réalisée pour les lots de type A, compte-tenu du
nombre d’unités d’oeuvre requis et de leur coût de fabrication, est :
c1 = 138 − [(10 × 2) + (12 × 1) + (14 × 4)] = 50
Pour les lots de type B, on obtient de même :
c2 = 136 − [(10 × 1) + (12 × 4, 5) + (14 × 3)] = 30
13
La marge totale est c1x1 + c2x2. On cherche donc à maximiser la marge :
Max (50x1 + 30x2)
Le premier tableau du simplexe est donc :
x1
2
1
4
-50
x2
1
4,5
3
-30
x3
1
0
0
0
x4
0
1
0
0
x5
0
0
1
0
x3
x4
Publicité
x5
200
540
480
0
La variable x1 entre dans la base. On forme les rapport positifs entre la colonne de
droite et la colonne entrante et on cherche le plus petit :
Min
(cid:16) 200
2
,
540
1
,
480
4
(cid:17)
=
200
2
= 100
C’est donc la variable x3 qui sort et on fait une transformation du pivot autour du
nombre 2 (à l’intersection de la ligne de x3 et de la colonne de x1).
On obtient le tableau suivant :
x1
1
0
0
0
x2
1/2
4
1
-5
x3
1/2
-1/2
-2
25
x4
0
1
0
0
x5
0
0
1
0
x1
x4
x5
100
440
80
5000
La variable x2 entre maintenant dans la base. Puis :
Min
(cid:16) 100
1/2
(cid:17)
,
440
4
,
80
1
= 80
donc la variable x5 sort et on fait une transformation du pivot autour du nombre 1 (à
l’intersection de la ligne de x5 et de la colonne de x2).
on obtient, après pivot, le tableau suivant :
0
0
0
0
1
0
15/2
-2
15
1
0
0
-4
1
5
120
80
5400
x4
x2
C’est l’optimum. La solution est donc :
x∗
1 = 60
x∗
2 = 80
x∗
3 = 0
x∗
4 = 120
x∗
5 = 0
f ∗ = 5400
La première et la troisième contrainte sont saturées, autrement dit les atelier T et M
sont utilisés à plein, tandis que dans l’atelier F il reste 120 unités d’oeuvre inutilisées.
14
Corrigé ex. 6 : Plan de production de moteurs
Temps opératoire Temps opératoire
Temps
disponible
pour le modèle A pour le modèle B (en heures)
unitaire
unitaire
Emboutissage
Soudure
Peinture
50 mn
30 mn
20 mn
40 mn
20 mn
10 mn
2500 h
1000 h
800 h
Coût
variable de
l’heure
150 e
60 e
20 e
Les prix de vente sont fixés à 215 e pour le modèle A et 150 e pour le modèle B.
On désigne par x1 et x2 les quantités de moteurs des deux types A et B qui vont
être produites.
Calculons les marges bénéficiaires résultant de ces fabrications. Pour le modèle
A, le prix de vente unitaire est de 215 et on doit retirer les coûts de fabrication qui
dépendent du temps passé dans les trois ateliers (attention les temps sont en minutes et
les coûts sont exprimés à l’heure). On trouve donc :
c1 = 215 − (50 × 150 + 30 × 60 + 20 × 30)/60 = 50
De même pour les moteurs de type B on obtient :
c1 = 150 − (40 × 150 + 20 × 60 + 10 × 30)/60 = 25
L’objectif est de maximiser la marge totale :
Max(50 x1 + 25 x2)
Il y a des contraintes de disponibilité qui s’expriment de la manière suivante (en
mettant tous les temps en minutes) :
50x1 + 40x2 ≤ 2500 × 60
30x1 + 20x2 ≤ 1000 × 60
20x1 + 10x2 ≤ 800 × 60
Il y a d’autre part une contrainte de marché qui impose un quota maximal sur le
nombres de moteurs de type A :
x1 ≤ 1800
On introduit des variables d’écart x3, x4, x5, x6 dans les quatre contraintes :
50x1 +40x2 +x3
30x1 +20x2
20x1 +10x2
+x4
+x5
x1
= 2500 × 60
= 1000 × 60
= 800 × 60
+x6 = 1800
Le tableau de démarrage du simplexe s’écrit comme ceci :
Tableau 1
15
x1
60
30
20
1
-50
x2
40
20
10
0
-25
x3
1
0
0
0
0
x4
0
1
0
0
0
x5
0
0
1
0
0
x6
0
0
0
1
0
150000
60000
48000
1800
0
x3
x4
x5
x6
La variable x1 entre dans la base et la variable x6 en sort car :
Min
(cid:16) 150000
60
,
60000
30
,
48000
20
,
1800
1
(cid:17)
= 1800
Tableau 2
x1
0
0
0
1
0
x2
40
20
10
0
-25
x3
1
0
0
0
0
x4
0
1
0
0
0
x5
0
0
1
0
0
x6
-60
-30
-20
1
50
42000
6000
12000
1800
90000
x3
x4
x5
x1
Maintenant la variable x2 entre dans la base et la variable x4 en sort car :
Min
(cid:16) 42000
40
,
6000
20
,
12000
10
(cid:17)
=
6000
20
= 300
Tableau 3
x1
0
0
0
1
0
x2
0
1
0
0
0
x3
1
0
0
0
0
x4
-2
0,05
-0,5
0
1,25
x5
0
0
1
0
0
x6
0
-1,5
-5
1
12,5
30000
300
9000
1800
97500
x3
x2
x5
x1
On a atteint l’optimum. La solution est :
x∗
1 = 1800
x∗
2 = 300
x∗
3 = 30000
x∗
5 = 9000
x∗
6 = 0
f ∗ = 97500
La deuxième et la quatrième contrainte sont saturées : les valeurs 1,25 et 12,5 dans
la dernière ligne du tableau sont les prix duaux π4 et π6 associés. On fabrique le maxi-
mum envisagé de moteurs de type A et l’atelier de soudure fonctionne à plein. Le
premier atelier (emboutissage) est sous-utilisé : il reste 500 (=30000/60) heures dispo-
nibles. De même, dans le troisième atelier, il reste 9000/60=150 heures disponibles.
16
Corrigé ex. 7 : Excavation et matériaux de carrière
On désigne par x1 et x2 les quantités qui seront extraites des deux carrières. La
redevance à acquitter est de 19, 40 × 103x1 + 20 × 103x2 et on cherche à la minimiser.
Pour simplifier les calculs, on divise les coefficients par 103, d’où le problème :
Min (19, 40x1 + 20x2)
Les rendements liés au concassage des matériaux conduisent aux inéquations sui-
vantes qui expriment que les quantités obtenues doivent pouvoir couvrir les besoins
imposés par le contrat :
0, 36 × 103x1 + 0, 45 × 103x2 ≥ 13500
0, 40 × 103x1 + 0, 20 × 103x2 ≥ 11200
0, 16 × 103x1 + 0, 10 × 103x2 ≥ 5000
Ces inéquations peuvent être réécrites de la manière suivante :
4x1 + 5x2 ≥ 150
2x1 + x2 ≥ 56
8x1 + 5x2 ≥ 250
Elles montrent en particulier qu’on ne peut pas démarrer le simplexe à partir de
l’origine (0, 0). En renversant le sens des inégalités et en introduisant les variables
d’écart, on obtient :
−4x1 −5x2 +x3
−2x1 −x2
−8x1 −5x2
+x4
= −150
= −56
+x5 = −250
Il existe des méthodes pour trouver un point de démarrage pour le simplexe : cela
revient, une fois qu’on a introduit les variables d’écart, à résoudre un système d’équa-
tions linéaires en coordonnées positives. Une des méthodes possibles est la méthode
des valeurs ajoutées (mais on ne l’utilisera pas ici).
Dans le cas particulier de cet exercice, on peut se contenter plus simplement de
déterminer un point valide sur l’un des axes. Par exemple, si on regarde les intersec-
tions des contraintes avec l’axe vertical (x1 = 0), on trouve les valeurs 30, 50, 56.
Comme le domaine se trouve au-dessus de ces points, on choisit le point de coordon-
nées (0, 56) comme point de départ. On peut vérifier qu’il satisfait effectivement les
trois contraintes : il est sur la droite de la deuxième contrainte, donc x4 = 0.
On part donc de la situation suivante :
(cid:26) x1 = 0
x4 = 0
x2 = 56 x3 = 130 x5 = 30
Les variables x1 et x4 sont des variables hors-base. On doit donc exprimer les autres
variables en fonction de celles-ci. On obtient :
x2 = 56 − 2x1 + x4
x3 = 130 − 6x1 + 5x4
x5 = 30 − 2x1 + 5x4
17
et donc
2x1 +x2
6x1
2x1
−x4
+x3 −5x4
= 56
= 130
−5x4 +x5 = 30
De même la fonction objectif s’écrit, en fonction de x1 et x4, comme ceci :
f = 1120 − 20, 6x1 + 20x4
O...