12.5 Opti mi sation multi objec tif
435
© Dunod – Toute reproduction non autorisée est un délit.
12.5 optI mI satIon multI objec tIf
1
Nous nous inté res sons ici au cas où l’ensemble A des actions poten tielles est défini
impli ci te ment (cf. sec tion 12.2.1). Nous nous res trein drons au cas de la pro gram ma
tion linéaire multi objec tif, sans consi dé rer par exemple les pro blèmes d’opti mi sation
com bi na toire multi objec tif (plus court che min multi objec tif, affec ta tion multi
objec tif, etc.). De plus, nous ne pré sen te rons qu’une façon (parmi bien d’autres) de
rechercher un meilleur com pro mis dans ce contexte.
Soit donc le pro gramme linéaire multi objec tif sui vant, exprimé sous forme
matricielle (on note, ici, D la matrice notée A aux chapitres 8 et 9) :
c
max z 1 5 c
1 # x, max z 2 5 c
2 # x, c, max z p 5 c
p # x
D # x < b
x > 0
où x 5 (x 1 , c, x n )
t
est le vec teurcolonne des variables de déci sion, et
z
j 5 c
j # x 5 a
n
i51
c
j
i x i repré sente la j
e
fonc tion objec tif (j 5 1, c, p),
D est la matrice des contraintes et b est le vec teurcolonne des seconds membres.
Dans la suite, on notera X plutôt que d le domaine (convexe) des solu tions admis
sibles :
X 5 5x : x . 0 et D # x < b6.
Remarque : La nota tion « max », ici quelque peu abu sive, signi fie en fait que
l’on recherche un meilleur com pro mis en regard de p fonc tions objec tifs, cha
cune étant à maxi mi ser.
12.5.1 Tableau des gains, point idéal
Une pre mière idée natu relle pour pro gres ser vers la recherche de ce com pro mis
consiste à opti mi ser indé pen dam ment cha cun des p pro grammes linéaires sui vants :
(PL j ) b
max z j 5 c
j # x
x P X
(j 5 1, c, p)
Soit x
*j
une solu tion opti male du pro gramme (PL j ) et z
*
j la valeur opti
male de sa fonc tion objec tif (j 5 1, c, p). On consti tue le tableau des gains
en don nant la valeur de cha cune des solu tions x
*i
sur chaque fonc tion objec tif
z k 5 c
k # x (i 5 1, c, p ; k 5 1, c, p) – cf. tableau 12.6.
Le point z
* 5 (z
*
1 , c, z
*
p ), dont les coor don nées cor res pondent aux valeurs opti
males de chaque fonc tion objec tif est appelé point idéal (ou zénith). Ces coor don
nées se situent donc sur la dia go nale du tableau des gains.
1. Conseil au lec teur : lire aupa ra vant le cha pitre 8 sur la pro gram ma tion linéaire.
435
© Dunod – Toute reproduction non autorisée est un délit.
12.5 optI mI satIon multI objec tIf
1
Nous nous inté res sons ici au cas où l’ensemble A des actions poten tielles est défini
impli ci te ment (cf. sec tion 12.2.1). Nous nous res trein drons au cas de la pro gram ma
tion linéaire multi objec tif, sans consi dé rer par exemple les pro blèmes d’opti mi sation
com bi na toire multi objec tif (plus court che min multi objec tif, affec ta tion multi
objec tif, etc.). De plus, nous ne pré sen te rons qu’une façon (parmi bien d’autres) de
rechercher un meilleur com pro mis dans ce contexte.
Soit donc le pro gramme linéaire multi objec tif sui vant, exprimé sous forme
matricielle (on note, ici, D la matrice notée A aux chapitres 8 et 9) :
c
max z 1 5 c
1 # x, max z 2 5 c
2 # x, c, max z p 5 c
p # x
D # x < b
x > 0
où x 5 (x 1 , c, x n )
t
est le vec teurcolonne des variables de déci sion, et
z
j 5 c
j # x 5 a
n
i51
c
j
i x i repré sente la j
e
fonc tion objec tif (j 5 1, c, p),
D est la matrice des contraintes et b est le vec teurcolonne des seconds membres.
Dans la suite, on notera X plutôt que d le domaine (convexe) des solu tions admis
sibles :
X 5 5x : x . 0 et D # x < b6.
Remarque : La nota tion « max », ici quelque peu abu sive, signi fie en fait que
l’on recherche un meilleur com pro mis en regard de p fonc tions objec tifs, cha
cune étant à maxi mi ser.
12.5.1 Tableau des gains, point idéal
Une pre mière idée natu relle pour pro gres ser vers la recherche de ce com pro mis
consiste à opti mi ser indé pen dam ment cha cun des p pro grammes linéaires sui vants :
(PL j ) b
max z j 5 c
j # x
x P X
(j 5 1, c, p)
Soit x
*j
une solu tion opti male du pro gramme (PL j ) et z
*
j la valeur opti
male de sa fonc tion objec tif (j 5 1, c, p). On consti tue le tableau des gains
en don nant la valeur de cha cune des solu tions x
*i
sur chaque fonc tion objec tif
z k 5 c
k # x (i 5 1, c, p ; k 5 1, c, p) – cf. tableau 12.6.
Le point z
* 5 (z
*
1 , c, z
*
p ), dont les coor don nées cor res pondent aux valeurs opti
males de chaque fonc tion objec tif est appelé point idéal (ou zénith). Ces coor don
nées se situent donc sur la dia go nale du tableau des gains.
1. Conseil au lec teur : lire aupa ra vant le cha pitre 8 sur la pro gram ma tion linéaire.