Chapitre 6 – Solutions des problèmes

1. Optimums de Pareto d’un modèle abstrait.

(a) L’ensemble ADM des solutions admissibles est le polygone ABCDEFG illustré dans la
figure ci-dessous.

(b) Les coordonnées des points extrêmes de ADM sont données au tableau suivant.

Point extrême A B C D E F G

Coordonnées (0; 5) (0; 8) (4,333; 8) (10; 2,769) (10; 0,556) (9; 0) (4; 0)

(c) Le tableau suivant indique les valeurs prises par les fonctions-objectifs z1 et z2 en chacun
des points extrêmes de l’ensemble ADM.

Point extrême A B C D E F G
z1 10 16 33,333 45,538 41,111 36 16
z2 130 208 312 312 254,444 216 96
2 Chapitre 6 – L’optimisation multicritère

L’ensemble EVO des valeurs de z1 et z2 pour les solutions de ADM est illustré ci-après.
Exceptionnellement, nous avons utilisé des unités différentes pour les deux axes, afin d'obtenir un
graphique moins étriqué.

(d) Le seul optimum de Pareto de ce modèle est le point D = (10; 2,769).

2. La méthode hiérarchique appliquée à un modèle abstrait.

(a) Le point D = (10; 2,769) est l'unique point où la fonction-objectif z1 atteint sa valeur
maximale z1* = 45,538 (voir problème 1(c)). Il restera évidemment l’unique solution optimale
lorsqu'on ajoute au modèle la contrainte supplémentaire « z1 = 45,538 » et que l'on cherche à
maximiser z2.

(b) La valeur maximale z2* = 312 est atteinte aux sommets C et D (voir problème 1(c)).
Toutefois, seul D maximise z1 lorsque z2 est fixée à la valeur 312.

En conclusion, quel que soit l’ordre suivi, la méthode hiérarchique conduit au point D comme
unique solution optimale. Ce résultat était prévisible, car D est l’unique optimum de Pareto.
Solutions des problèmes 3

3. La méthode de pondération appliquée à un modèle abstrait.

(a) La fonction-objectif z s’écrit :

z = [ 4 x1 + 2 x2 ] + w [ 24 x1 + 26 x2 ] = (4 + 24 w) x1 + (2 + 26 w) x2.

(b) Lorsque w = 0,5, la fonction-objectif z s'écrit : z = 16 x1 + 15 x2. Et alors, z atteint sa valeur

maximale 201,538 quand (x1 ; x2) = (10; 2,769).

(c) Dans les trois cas, la solution obtenue est la même, car le modèle admet un seul optimum
de Pareto.

4. Un problème abstrait comportant 3 variables et 3 objectifs.

(a) Le tableau suivant décrit les trois solutions optimales obtenues et indique les valeurs prises
par les fonctions-objectifs z1, z2 et z3 en chacune de ces solutions.

Objectif x1 x2 x3 z1 z2 z3
z1 0 5 35 290 180 305
z2 35 5 0 150 215 235
z3 0 16,67 0 150 16,67 316,67

(b) La fonction-objectif z s’écrit :

z = [ 3 x1 + 9 x2 + 7 x3 ] + w2 [ 6 x1 + 1 x2 + 5 x3 ] + w3 [ 4 x1 + 19 x2 + 6 x3 ]
= (3 + 6 w2 + 4 w3 ) x1 + (9 + 1 w2 + 19 w3 ) x2 + (7 + 5 w2 + 6 w3 ) x3.

(c) Lorsque w2 = 2 et w3 = 4, la fonction-objectif z s'écrit : z = 31 x1 + 87 x2 + 41 x3. Et alors, z

atteint sa valeur maximale 1870 quand (x1 ; x2 ; x3) = (0; 5; 35).

(d) Nous ajoutons au modèle de l'énoncé des variables de déviation dh+ et dh─ (où h = 1, 2, 3),
ainsi qu'une variable Dmax qui représentera la valeur maximale des 6 variables de déviation.
L'objectif vise essentiellement à minimiser la valeur de Dmax. Mais, comme on cherche à éviter que
les deux variables de déviation dh+ et dh─ associées à un même critère soient non nulles en même
4 Chapitre 6 – L’optimisation multicritère

temps, on pénalisera – faiblement – les variables de déviation. Plus précisément, l'objectif

consistera à minimiser z, où
z = d1─ + d1+ + d2─ + d2+ + d3─ + d3+ + 1000 Dmax.
Les contraintes technologiques du modèle forment trois groupes.
• Il faut d'abord reprendre les 4 inéquations de l'énoncé.
• Il faut ensuite définir les variables de déviation :
3 x1 + 9 x2 + 7 x3 + d1─ – d1+ = 260
6 x1 + 1 x2 + 5 x3 + d2─ – d2+ = 200
4 x1 + 19 x2 + 6 x3 + d3─ – d3+ = 300.
• Il faut enfin s'assurer que Dmax est supérieure à toutes les variables de déviation :
Dmax ≥ dh─ h = 1, 2, 3
Dmax ≥ dh+ h = 1, 2, 3.

La valeur minimale de Dmax est 11,67. Le tableau suivant décrit une solution optimale.
– +
h xh zh dh dh
1 8,33 256,67 3,33 0
2 5 188,33 11,67 0
3 26,67 288,33 11,67 0

(e) Nous reprenons les variables du modèle précédent, sauf Dmax. Les contraintes technolo-
giques sont celles des deux premiers groupes de ce modèle. L'objectif s'écrit :
Min z = d1─ + d1+ + d2─ + d2+ + d3─ + d3+.
La valeur minimale de z est 22,5. Le tableau suivant décrit une solution optimale.
– +
h xh zh dh dh
1 7,5 260 0 0
2 5 187,5 12,5 0
3 27,5 290 10 0

5. Les pommes de terre.

(a) Voici les trois inéquations demandées.

Frites 0,200 x1 + 0,250 x2 ≤ 18 000 (1)

Juliennes 0,200 x1 + 0,100 x2 ≤ 12 000 (2)
Flocons 0,300 x1 + 0,270 x2 ≤ 24 000. (3)
Solutions des problèmes 5

(b) L'ensemble ADM est le polygone OABC de la figure ci-dessous. Les coordonnées des
sommets sont données dans le tableau de la question (c).

(c) La fonction-objectif représentant le profit s'écrit : z1 = 1,2 x1 + x2. Le tableau suivant

donne les valeurs des trois fonctions-objectifs pour les différents sommets de l'ensemble ADM.
On constate que chacune des zh admet un seul optimum. Noter que le sommet A, qui est la
meilleure solution si on retient le 3e critère, est dominé par B selon les deux autres objectifs; que,
de même, C est dominé par B selon z1 et z3.

Point x1 x2 z1 z2 z3
O 0 0 0 0 0
A 0 72 000 72 000 0 72 000
B 40 000 40 000 88 000 40 000 40 000
C 60 000 0 72 000 60 000 0

(de) Les graphiques demandés sont reproduits ci-dessous à gauche (d) et à droite (e) Les
coordonnées des points extrêmes zP sont donnés dans le tableau de la question (c).
(f) Le graphique demandé est identique à celui donné en question (b), car les points P de ADM
et zP de EVO coïncident quand les fonctions-objectifs utilisées sont z2 = x1 et z3 = x2.

(g) Le modèle pertinent comprend les variables x1 et x2 de la question (a), des variables de
déviation dh+ et dh─ (où h = 2, 3), ainsi qu'une variable Dmax qui représentera la valeur maximale
des quatre variables de déviation.
L'objectif vise essentiellement à minimiser la valeur de Dmax. Mais, comme on cherche à éviter que
les deux variables de déviation dh+ et dh─ associées à un même critère soient non nulles en même
temps, on pénalisera – faiblement – les variables de déviation. Plus précisément, l'objectif
consistera à minimiser z, où
z = 0,00001 d2─ + 0,00001 d2+ + 0,00001 d3─ + 0,00001 d3+ + Dmax.
Les contraintes technologiques du modèle forment trois groupes.
• Il faut d'abord reprendre les trois inéquations de la question (a).
• Il faut ensuite définir les variables de déviation :
x1 + d2─ – d2+ = 50 000
x2 + d3─ – d3+ = 55 000.
• Il faut enfin s'assurer que Dmax est supérieure à toutes les variables de déviation :
Dmax ≥ dh─ h = 2, 3
Dmax ≥ dh +
h = 2, 3.

La valeur minimale de Dmax est 12 778. Le tableau suivant décrit une solution optimale.
– +
h xh zh dh dh
1 37 222
2 42 222 37 222 12 778 0
3 42 222 12 778 0
Solutions des problèmes 7

(h) Nous considérons d'abord le modèle consistant à maximiser

z4 = x1 + x2
sous les trois contraintes de la question (a), ainsi que les contraintes de non-négativité usuelles.
Une solution optimale est obtenue en posant : x1 = x2 = 40 000. En principe, il faudrait
maintenant maximiser le profit z1 en ajoutant au modèle précédent la contrainte
x1 + x2 = 80 000.
Mais cette étape est inutile dans le présent contexte : en effet, la solution (x1 ; x2) = (40 000 ;
40 000) correspond au sommet B, qui est l'optimum de z1, même en l'absence de l'exigence que
l'objectif z4 soit fixé à son maximum de 80 000.

6. Les affiches de Vunéon.

(a) Voici les trois inéquations demandées.

Séparation x1 + 1,5 x2 ≤ 800 (1)

Montage 0,50 x1 + x2 ≤ 2 500 (2)
Contrôle 0,04 x1 + 0,1 x2 ≤ 40. (3)

(b) La figure de gauche ci-dessous donne la région admissible du modèle linéaire continu
comprenant les trois inéquations de la question (a), ainsi que les contraintes de non-négativité
usuelles. La contrainte « Montage » n'est pas représentée sur le graphique, car elle est évidemment
redondante : considérons, en effet, un point (x1; x2) du 1er quadrant qui satisfait à la première
contrainte technologique; alors
0,50 x1 + x2 ≤ x1 + 1,5 x2 ≤ 800 ≤ 2 500,
la 1re inéquation découlant de la non-négativité des variables x1 et x2; ainsi, le temps exigé par le
plan de production (x1; x2) n'excède pas les 2 500 heures disponibles dans l'atelier M.I. et la
contrainte « Montage » est nécessairement satisfaite.

D'après les résultats de la colonne z1 du tableau de droite, tous les points du segment [B; C] dont
les deux coordonnées sont entières optimisent la fonction-objectif z1 = 500 x1 + 750 x2.
 Point x1 x2 z1 z2

O 0 0 0 0

A 0 400 300 000 24 000

B 500 200 400 000 22 000

C 800 0 400 000 16 000

(c) D'après les résultats de la colonne z2 du tableau ci-dessus, le point A est l'unique optimum
de la fonction-objectif z2 = 20 x1 + 60 x2.

(d) Considérons tour à tour chacun des deux ordres possibles.

• z1 suivie de z2. Il s'agit de résoudre le modèle PLTE dont l'objectif est de maximiser z2 et dont
les contraintes technologiques sont les trois inéquations de la question (a), ainsi que l'équation
suivante, qui fixe le profit hebdomadaire z1 à sa valeur optimale 400 000 :
500 x1 + 750 x2 = 400 000.
On obtient l'optimum de Pareto (x1 ; x2) = (500; 200) pour lequel z1 = 400 000 et z2 = 22 000.

• z2 suivie de z1. Cette fois, le modèle initial – dont l'objectif est de maximiser z2 – admet une
seule solution optimale, qui correspond au sommet A = (0; 400) de la figure ci-dessus. Par
conséquent, dans le second modèle où l'on fixe l'impact z2 des affiches à sa valeur optimale,
(x1 ; x2) = (0; 400) est la seule solution admissible et donc la solution optimale. Le profit
hebdomadaire découlant de cet optimum de Pareto est de 300 000 dollars.

Choisir entre ces deux optimums de Pareto revient à arbitrer entre un profit hebdomadaire
additionnel de 100 000 dollars et un impact additionnel de 2 000 personnes.

(e) La fonction-objectif z s’écrit :

z = [500 x1 + 750 x2 ] + w [20 x1 + 60 x2 ] = (500 + 20 w) x1 + (750 + 60 w) x2.
Le coefficient w représente la diminution du profit hebdomadaire que la direction de Vunéon serait
prête à accepter pour obtenir que l'impact total des affiches augmente de 1 personne.

(f) Lorsque w est positif et petit, la portion z1 est prépondérante et la fonction-objectif z atteint
son maximum au sommet B = (500; 200). Mais, une valeur élevée de w favorise le sommet A =
(0; 400) dont la 2e coordonnée est la plus grande. La valeur critique wc où A devient l'optimum
s'obtient en résolvant l'équation d'équilibre « zA = zB », qui se récrit :
300 000 + 24 000 wc = 400 000 + 22 000 wc.
Solutions des problèmes 9

Il vient : wc = 50.

Note. Le lecteur trouvera dans la feuille (g) du fichier MOG6-06.xlsx un tableau où sont calculées, en
fonction de w, les valeurs de z en chacun des sommets O, A, B et C. Il constatera que l'unique optimum
de z est B quand 0 < w < 50, et A quand w > 50. Lorsque w = 50, les sommets A et B, et par conséquent
tous les points du segment [A; B], donnent à z la même valeur 1 500 000.

9. Les vendeurs de FÉÉ.

(a) Le modèle d'affectation de FÉÉ repose sur des variables binaires vij (i = 1, 2, 3, 4, 5 et j = 1,
2, 3, 4, 5) définies de la façon suivante :
vij = 1 si le candidat i est affecté à la succursale j.
Comme chaque candidat doit être placé dans une et une seule succursale et que chaque succursale
doit recevoir un seul candidat, la somme si des variables de la ligne Ei, de même que le total tj des
variables de la colonne Tj, doivent être égaux à 1, quelle que soit la rangée considérée (voir p. 82-83) :
vi1 + vi2 + vi3 + vi4 + vi5 = 1 i = 1, 2, 3, 4, 5
v1j + v2j + v3j + v4j + v5j = 1 j = 1, 2, 3, 4, 5.
Le premier objectif consiste à minimiser les coûts de déplacement z1, où
z1 = 1030 v11 + 1157 v12 + … + 1200 v23 + … + 1305 v55.
Le tableau suivant décrit les affectations d'une solution optimale; le coût minimal de déplacement
est de 6 141 dollars.
Candidat 1 2 3 4 5
Succursale 1 3 2 5 4

(b) Il s’agit cette fois de maximiser l’adaptabilité z2, où

z2 = 55 v11 + 66 v12 + … + 67 v23 + … + 80 v55.
Le tableau suivant décrit les affectations d'une solution optimale; la somme maximale des cotes
d’adaptabilité est 416.
Candidat 1 2 3 4 5
Succursale 3 2 4 5 1

(c) Enfin, on se donne comme objectif de maximiser le volume des ventes z3, où
z3 = 8200 v11 + 6500 v12 + … + 8900 v23 + … + 9500 v55.
Le tableau suivant décrit les affectations d'une solution optimale; le volume maximal des ventes
est 44 200 dollars.
10 Chapitre 6 – L’optimisation multicritère

Candidat 1 2 3 4 5
Succursale 4 3 1 2 5

(d) Le tableau ci-dessous donne les valeurs optimales des fonctions-objectifs dans les différents
modèles considérés. Noter que, dans celui de la 2e ligne, « z1 suivie de z2 », l'objectif est de
maximiser l’adaptabilité z2 et les contraintes technologiques sont les 10 équations du modèle
décrit en (a), auxquelles s'ajoute une contrainte additionnelle exigeant que les coûts de
déplacement soient fixés au minimum de 6 141 dollars :
1030 v11 + 1157 v12 + … + 1200 v23 + … + 1305 v55 = 6 141.
De même, dans le modèle de la 3e ligne, « z1 suivie de z2, puis de z3 », l'objectif est de maximiser
le volume des ventes z3; enfin, les contraintes technologiques, au nombre de 12, sont celles du
modèle précédent, auxquelles s'ajoute une équation qui force la fonction-objectif z2 à prendre la
valeur optimale 376 atteinte dans ce modèle :
55 v11 + 66 v12 + … + 67 v23 + … + 80 v55 = 376.

Affectations Valeurs des zh

Ordre
1 2 3 4 5 z1 z2 z3
z1 1 3 2 5 4 6141 – –
z1 suivie de z2 2 3 1 4 5 6141 376 –
z1 suivie de z2, puis de z3 2 3 1 4 5 6141 376 41 500
z2 3 2 4 5 1 – 416 –
z2 suivie de z3 3 2 1 4 5 – 416 36 800
z2 suivie de z3, puis de z1 3 2 1 4 5 6452 416 36 800
z3 4 3 1 2 5 – – 44 200
z3 suivie de z2 4 3 2 1 5 – 354 44 200
z3 suivie de z2, puis de z1 4 3 2 1 5 7039 354 44 200

Les 3e, 6e et 9e lignes de ce tableau décrivent des optimums de Pareto.

(e) Le tableau suivant résume les valeurs des trois fonctions-objectifs pour les solutions
trouvées en (a), (b) et (c).
Solution optimale z1 z2 z3
de (a) 6141 376 41 500
de (b) 7420 416 32 300
de (c) 7458 337 44 200
Solutions des problèmes 11

Convenons d'attribuer des poids de 1, –20 et –5 aux trois critères. La fonction-objectif, que l'on
cherchera à minimiser, s'écrit alors :
z = 1 z1 – 20 z2 – 5 z3
= – 41 070 v11 – 32 663 v12 – … – 44 640 v23 – … – 47 795 v55.
Le tableau suivant décrit les affectations d'une solution optimale. Si on implante cette solution,
les coûts de déplacement s'élèveront à 7 039 dollars, la somme z2 des cotes d’adaptabilité sera
égale à 354 et le volumes estimé des ventes atteindra 44 200 $, soit le maximum possible.
Candidat 1 2 3 4 5
Succursale 4 3 2 1 5

Noter que cette solution coïncide avec celle obtenue de la méthode hiérarchique dans le cas de
l'ordre « z3 suivie de z2, puis de z1 ».

(f) Nous ajoutons aux modèles considérés précédemment des variables de déviation dh+ et dh─
(où h = 1, 2, 3), ainsi qu'une variable Dmax qui représentera la valeur maximale des 6 variables de
déviation.
L'objectif vise essentiellement à minimiser la valeur de Dmax. Mais, comme on cherche à éviter que
les deux variables de déviation dh+ et dh─ associées à un même critère soient non nulles en même
temps, on pénalisera – faiblement – les variables de déviation. Plus précisément, l'objectif
consistera à minimiser z, où
z = d1─ + d1+ + d2─ + d2+ + d3─ + d3+ + 1000 Dmax.
Les contraintes technologiques du modèle forment trois groupes.
• Il faut d'abord reprendre les 10 équations du modèle d'affectation de la question (a) :
vi1 + vi2 + vi3 + vi4 + vi5 = 1 i = 1, 2, 3, 4, 5
v1j + v2j + v3j + v4j + v5j = 1 j = 1, 2, 3, 4, 5.
• Il faut ensuite définir les variables de déviation :
1030 v11 + 1157 v12 + … + 1200 v23 + … + 1305 v55 + d1─ – d1+ = 6800
55 v11 + 66 v12 + … + 67 v23 + … + 80 v55 + d2─ – d2+ = 350
8200 v11 + 6500 v12 + … + 8900 v23 + … + 9500 v55 + d3─ – d3+ = 40 000.
• Il faut enfin s'assurer que Dmax est supérieure à toutes les variables de déviation :
Dmax ≥ dh─ h = 1, 2, 3
Dmax ≥ dh+ h = 1, 2, 3.

Le tableau suivant décrit les affectations d'une solution optimale de ce modèle. Si cette solution
est implantée, il en coûtera 6 895 $ en frais de déplacement (d1─ = 0 et d1+ = 95), la somme des
12 Chapitre 6 – L’optimisation multicritère

cotes d’adaptabilité sera de 294 points (d2─ = 56 et d2+ = 0), les ventes estimées s'élèveront à
40 100 $ (d3─ = 0 et d3+ = 100). La déviation maximale est d3+.
Candidat 1 2 3 4 5
Succursale 5 4 2 1 3

(g) Nous reprenons les variables du modèle précédent (sauf Dmax). Les contraintes technolo-
giques sont celles des deux premiers groupes du modèle précédent. Les pénalités de déviation
positives des critères z2 et z3 que l'on cherche à maximiser, de même que la pénalité de déviation
négative du critère z1 que l'on cherche à minimiser, sont a priori posées égales à 0; enfin, on
attribue des pénalités de 1, 20 et 5 respectivement aux variables d1+, d2─ et d3─. En résumé,
l'objectif s'écrit de la façon suivante :
Min z = d1+ + 20 d2─ + 5 d3─.
Le tableau suivant décrit les affectations d'une solution optimale de ce modèle, pour laquelle la
fonction-objectif z prend la valeur 0. Si cette solution est implantée, il en coûtera 6 141 $ en
frais de déplacement (d1─ = 659 et d1+ = 0), la somme des cotes d’adaptabilité sera de 375 points
(d2─ = 0 et d2+ = 25), les ventes estimées s'élèveront à 41 500 $ (d3─ = 0 et d3+ = 1500).
Candidat 1 2 3 4 5
Succursale 2 3 1 4 5

10. Pollution.

(a) Nous décrivons d'abord le modèle linéaire utilisé. Il comporte neuf variables de décision.
Les trois premières résument le plan de production de l'entreprise et sont définies de la façon
suivante :
xj = nombre d'unités de Pj produites heddomadairement.
Les six autres sont des variables de déviation et seront définies comme d'habitude dans des
équations qui relient les cibles d'André aux variables xj.

Les contraintes technologiques se regroupent en trois catégories. Il faut d'abord que, dans chaque
atelier, le temps utilisé n'excède pas le temps disponible.
Atelier A 0,20 x1 + 0,2 x2 + 0,4 x3 ≤ 1 500
Atelier B 0,25 x1 + 0,4 x2 + 0,5 x3 ≤ 1 500
Atelier C 2 x1 + 4 x2 + 1 x3 ≤ 5 000.
Solutions des problèmes 13

Le plan de production doit respecter l'exigence du banquier et doit comporter au moins 1 500
unités de P1.
Banquier x1 ≥ 1 500
Min P1 1 x1 + 3 x2 + 2 x3 ≥ 5 000.
Enfin, il faut inclure trois équations qui définissent les variables de déviation.
Cible de pollution 2 x1 + 1 x2 + 2 x3 + d1─ – d1+ = 6 000
Cible de P2 x2 + d2─ – d2+ = 200
Cible de P3 x3 + d3─ – d3+ = 2 000.

L'objectif de notre modèle consiste à mimimiser la somme pondérée des déviations. Nous
posons : w1– = 0, car André ne voudra sûrement pas pénaliser un plan de production qui pollue
peu. De même, les clients privilégiés mentionnés dans l'énoncé ne s'offusqueraient sans doute
pas que les quantités produites dépassent les minimums requis; nous accordons donc un poids nul
à tout excédent aux cibles des objectifs 2 et 3. Les poids des trois autres variables de déviation
proviennent de l'énoncé. En résumé :
Min z = d1+ + 3 d2─ + 2 d3─.
Le tableau suivant décrit une solution optimale (zh désigne la valeur de l'objectif numéro h : par
exemple, z1 = 2 x1 + 1 x2 + 2 x3).

– +
h xh zh dh dh
1 1500 6300 0 300
2 100 100 100 0
3 1600 1600 400 0

(b) On reprend le modèle de la question (a), mais l'objectif s'écrit cette fois :
Min z = 10 d1+ + 2 d2─ + 1 d3─.
La solution optimale est la même.
Note. La solution optimale de ce modèle est peu sensible au poids de d1+. En effet, posons: z' = w d1+ + 2
d2─ + 1 d3─. La fonction z' atteint son mimimum sol opt celle de (a) quand w ≥ wc et autre (voir tableau ci-
dessous) quand 0 ≤ w ≤ wc. Et valeur critique wc = 2/7 = 0,2857 …
– +
h xh zh dh dh
1 1500 7000 0 1000
2 0 0 200 0
3 2000 2000 0 0