République Algérienne Démocratique et Populaire

Ministère de l’Enseignement Supérieur et de la Recherche Scientifique

Université Abderrahmane Mira-Béjaia

Faculté des Sciences Exactes

Département de Recherche Opérationnelle

Mémoire de fin d’étude

pour l’obtention de Diplôme de Master
Spécialité :Modélisation Mathématique et évaluation Des Performance Des
Réseaux

Thème

Optimisation Fractionnaire
Multiobjectifs

Présenté par : Encadré par :

Abdelkader Toufik M me Younsi-Abbaci Leila

• Devant le jury :
• Président :M r Kabyl Kamal

• Examinatrice :M me Lazari Nassima

Année universitaire : 2021/2022

 Remerciements

Je tiens tout d’abord à remercier Dieu le tout puissant et miséricordieux,

qui m’a donné la force et la patience d’accomplir ce modeste travail.

je tiens également à remercier ma promotrice Mme Abbaci Leila, pour

son soutien et sa disponibilité durant toute la période du travail.

j’adresse aussi Mes vifs remerciements aux membres des jurys pour avoir
bien voulu examiner et juger ce travail :

• M r k.Kabyl qui m’a fait l’honneur d’accepter la présidence du jury.

• M me N.Lazari qui ma fait l’honneur d’examiner ce travail.

Je n’oublie pas ma chère famille pour leur contribution, leur soutien et

leur patience.

Enfin, j’adresse mes plus sincères remerciements à tous mes proches et

amis, qui m’ont toujours encouragées au cours de la réalisation de ce
mémoire. . . .
 Dédicaces

Je dédié ce modeste travail :

A ma famille, mais aucune dédicace ne serait témoin de mon profond

amour, mon immense gratitude et mon plus grand respect pour eux pour
leurs soutien durant tous mon cycle d’étude.

J’offre aussi ce travail

A tous mes amie, et à tous ceux que j’aime et qui ont contribué de loin ou
de près afin de réaliser ce travail.

A ma promotrice pour ça patience avec moi.

Ainsi à tous le corps administratif, et à vous chers lecteurs.

...
Table des matières

1 Programmation Linéaire Fractionnaire 10

1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.2 Domaines d’applications des problèmes fractionnaires . . . . . . . . . . . . 10
1.3 Formulation du programme Linéaire fractionnaire . . . . . . . . . . . . . . 10
1.4 Le modèle générale d’un programme Linéaire fractionnaire . . . . . . . . . 11
1.5 Rappel sur l’optimisation convexe . . . . . . . . . . . . . . . . . . . . . . . 12
1.5.1 Convexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.6 Résolution d’un programme linéaire fractionnaire . . . . . . . . . . . . . . 13
1.6.1 La résolution graphique en nombres entiers . . . . . . . . . . . . . . 13
1.6.2 La résolution analytique . . . . . . . . . . . . . . . . . . . . . . . . 15
1.6.3 Méthode de Cambini et Al [24] . . . . . . . . . . . . . . . . . . . . 17
1.6.4 la méthode de Dinkelbach[14] . . . . . . . . . . . . . . . . . . . . . 18
1.6.5 la méthode de gradiant . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

2 Généralité sur l’optimisation multiobjectifs 20

2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.2 Notion fondamentale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.2.1 Définition du problème . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.3 Problématique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.3.1 La relation de dominance . . . . . . . . . . . . . . . . . . . . . . . . 23
2.3.2 Optimalité de Pareto . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.3.2.1 Effcacité forte . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.3.2.2 Efficacité faible . . . . . . . . . . . . . . . . . . . . . . . . 24
2.3.3 Point particuliers . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.4 Structure du front de Pareto . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.5 Classification des méthodes de résolution . . . . . . . . . . . . . . . . . . . 28
2.5.1 Méthode ε contrainte [8] . . . . . . . . . . . . . . . . . . . . . . . . 28
2.5.2 Méthode dite "but programmé ou Goal programming" . . . . . . . . 29
2.5.3 Méthode des sommes pondérées [30] . . . . . . . . . . . . . . . . . . 30

4
TABLE DES MATIÈRES

2.6 Approche de résolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

2.6.1 Approche Scalaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.6.2 Approche Pareto . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
2.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

3 Programmation Linéaire Fractionnaire MultiObjectifs en Nombres En-

tiers 33
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.2 Formulation du problème . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.2.1 Complexité du problème . . . . . . . . . . . . . . . . . . . . . . . . 35
3.2.2 Solutions supportées et non supportées . . . . . . . . . . . . . . . . 36
3.3 Méthodes de résolution d’un programme linéaire en nombres entiers . . . . 37
3.3.1 La méthode de gomory [27] . . . . . . . . . . . . . . . . . . . . . . 37
3.3.2 Méthode de Branch et Bound . . . . . . . . . . . . . . . . . . . . . 38
3.4 Résolution du problème . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.4.1 Méthodes de Abbas et Moulaï [19] . . . . . . . . . . . . . . . . . . . 41
3.4.2 Méthode de Chergui et Moulaï [20] . . . . . . . . . . . . . . . . . . 46
3.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

4 Approche de résolution du problème MOIFLP 48

4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
4.2 Définition du problème . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
4.2.1 Problème fractionnaire multi-objectif . . . . . . . . . . . . . . . . . 48
4.2.2 Transformation du problème (MOLIFP) vers un problème mono-
objectif [30] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
4.3 Exemple numérique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
4.4 Présentation du logiciel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
4.4.1 Interface de logiciel : . . . . . . . . . . . . . . . . . . . . . . . . . . 51
4.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

5
Table des figures

1.1 Graphe de l’exemple. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

2.1 Représentation de l’espace des décisions et l’espaces objectifs correspondant. 22

2.2 Schéma de résolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.3 Illustration des différentes définitions. . . . . . . . . . . . . . . . . . . . . . 27
2.4 La représentation de la surface de compromis . . . . . . . . . . . . . . . . 28
2.5 Représentation graphique de la méthode de la somme pondérée . . . . . . 31

3.1 Solutions supportées et non supportées . . . . . . . . . . . . . . . . . . . . 36

3.2 Principe de Branch and Bound . . . . . . . . . . . . . . . . . . . . . . . . 40
3.3 itération 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
3.4 itération 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
3.5 itération 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.6 itération 6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

6
Liste des tableaux

3.1 simplexe optimal associé à la base B. . . . . . . . . . . . . . . . . . . . . . 37

4.1 Résultats de l’optimisation en faisant varier les poids w1 et w2 . . . . . . . 53

7
Introduction générale

La Recherche Opérationnelle peut être définie comme l’ensemble des méthodes et des
techniques rationnelles orientées vers la recherche du meilleur choix dans la façon d’opérer
en vue d’aboutir au résultat visé ou au meilleur résultat possible.

La programmation fractionnaire a attiré l’attention de nombreux chercheurs dans le passé.

La principale raison de l’intérêt dans la programmation fractionnaire provient du fait que
modèles de programmation pourraient mieux répondre aux problèmes réels si l’on consi-
dère l’optimisation des le rapport entre les propriétés physiques et / ou les quantités écono-
miques. Etude bibliographique révèle de larges applications de programmation fractionnaire
dans différents domaines allant de la l’ingénierie à l’économie.

Dans un problème mono-objectifs,un seul objectifs exprimé en fonction des variable de

décision doit être otimisé.cependant dans les situation rencontrées en pratique,la consi-
dération d’un seul objectifs ne permet pas une bonne modélisation du problème. Avoir
comme but de se ramener à une seule fonction objectif peut aussi biaiser la modélisation.
L’optimisation multiobjectifs autorise ces degrés de liberté qui manquaient en optimisation
mono-objectif. La recherche ne nous donnera plus une solution unique mais une multitude
de solutions. La première notion d’optimalité a été introduite par Francis Ysidro Edge-
worth [21] en 1881, elle a été utilisée de manière plus formelle par l’économiste italien
Vilfredo Pareto [22] en 1896. Ces solutions sont appelées solutions de Pareto et l’ensemble
de solutions que l’on obtient à la fin de la recherche est la surface de compromis.
A cet effet, nous avons structuré notre travail comme suit :

• Chapitre 1 :Nous Nous sommes intéressés à la programmation linéaire fractionnaire

en nombres entiers, en rappelant les définitions de base et quelques méthodes de
résolution de ce type de problème.
• Chapitre 2 : Nous avons donné les principales définitions liées à l’optimisation
linéaire multi-objectifs puis les problématiques spécifiques à ce domain sont exposées
et étudiées. Parmi ces problématiques, nous avons parlé en particulier de la structure

8
LISTE DES TABLEAUX

de l’ensemble Pareto et le choix des méthodes de résolution.

• Chapitre 3 : est consacré à la présentation des problèmes de programmation multi-
objectifs linéaire fractionnaire en nombre entier (M OILF P )et à l’étude les méthodes
principales de résolution.
• Chapitre 4 : est consacré sur l’approche de résolution qui consiste à convertir le
problème multiobjectifs fractionnaire linéaire vers un problème mono-objectif.
• Enfin, le mémoire s’achèvera par une conclusion générale.

9
Chapitre 1
Programmation Linéaire Fractionnaire

1.1 Introduction
Les programmes linéaire fractionnaires , c’est-à-dire les programmes dont l’objectif s’ex-
prime comme le rapport de deux fonctions, linèaires ou non linèaires, en variables rèelles,
en variables entières, en variables mixtes ou en variables 0-1 apparaissent dans plusieurs
domaines de la recherche opèrationnelle tels que les bases de donnèes, l’ingènierie, l’opti-
misation combinatoire, la programmation stochastique, l’informatique et l’èconomie.

1.2 Domaines d’applications des problèmes fraction-

naires
Comme domaines d’applications des problèmes fractionaires soumis à un ensembles de
contraintes, nous pouvons citer par exemple[28] :

– Le domaine des finances où il est souvent question d’optimiser un rapport de deux

fonctions telles que [dette/ capitaux propres], [rendement/employé].
– Le domaine de l’économie offre une large éventail d’applications. En effet, la mesure
de l’efficacité des systèmes étudiés s’exprime sous forme de rapports entre les critères
techniques et/ou économiques. Par exemple, [rendement/risque].

1.3 Formulation du programme Linéaire fractionnaire

Les programmes fractionnaires consistent à optimiser un objectif mis sous la forme d’un
rapport de deux fonctions linèaires ou non linèaires, soumis à un ensemble de contraintes[1].

10
CHAPITRE 1. PROGRAMMATION LINÉAIRE FRACTIONNAIRE

Etant donné f, h et gi , i=1, m des fonctions réelles définies sur Rn . Désignons par X
un sous-ensemble de Rn sur lequel h ne s’annule pas. Le problème de programmation frac-
tionnaire consiste à déterminer un élément x∗ de X maximisant la fonction f /h sur un
domaine défini par le système de contraintes { x ∈ X : gi (x)6 0, i=1· · · m }.Un problème
de programmation fractionnaire est donc de la forme suivante :


 f (x)

 min Z(x) =
h(x)




(P F L) =  s.c



 gi (x) ≤ 0 i = 1 · · · m
 x∈X


avec :
Les fonctions f, h et gi , i = 1, m, sont continues sur Rn
h(x)> 0, ∀ x ∈ X
soit la solution réalisable S est donnée par :
S = {gi (x) ≤ 0, x ∈ X}.

Définition 1.3.1. . Le problème (PF) de maximisation est appelé problème fractionnaire

concave-convexe si f est concave et les fonction h et gi pour i=1, m sont convexes.
. Le problème (PF) de minimisation est appelé problème fractionnaire convexe-concave si
f et les fonctions gi pour i=1, m sont convexes et h concave [2].

1.4 Le modèle générale d’un programme Linéaire frac-

tionnaire
Lorsque dans le programme fractionnaire (P F L) les fonctions f, h et gi , i=1, m sont des
n
fonctions linéaires ou affines de la variable x ∈ R+ . Alors le problème (PF) d’optimisation
est appelé programme fractionnaire linéaire (PFL), ou programme hyperbolique, et prend
alors la forme suivante :

 pt x + α

 min Z(x) =
qtx + β




(P F L) =  s.c
 Ax ≤ b



 x≥0


Où α et β sont des réels, p et q sont des vecteurs de Rn avec q est un vecteur non nul,
A est une matrice réelle de format (m× n) et b est un vecteur de Rm . Désignons par S

11
 CHAPITRE 1. PROGRAMMATION LINÉAIRE FRACTIONNAIRE

l’ensemble
{ x ∈ Rn : Ax ≤ b, x ≥0 }
avec : qx + β 6= 0, ∀x ∈ S.

Il est claire que si q est un vecteur nul avec β 6= 0 , alors (PFL) n’est autre qu’un pro-
blème de programmation linéaire. Si de plus , les variables sont astreintes à ne prendre que
des valeurs entières (x∈ Z n ), on parle dans ce cas de problème de programmation linéaire
fractionnaire en nombre entiers ou encore problème hyperbolique discret, noté (ILFP), qui
fait une partie d’objet de nos préocupations dans la suite de ce travail.

1.5 Rappel sur l’optimisation convexe

Définition 1.5.1. Une fonction f : Rn → R est dite concave si et seulement si :
∀(x, y) ∈ Rn × Rn , ∀λ ∈ [0, 1], f (λx + (1 − λ)y) ≥ λf (x) + (1 − λ)f (y)

Définition 1.5.2. Une fonction f : Rn → R est dite convexe si et seulement si :

∀(x, y) ∈ Rn × Rn , ∀λ ∈ [0, 1], f (λx + (1 − λ)y) ≤ λf (x) + (1 − λ)f (y)

Définition 1.5.3. Soit f : Rn → R une fonction différentiable sur Rn . Alors, f est dite
pseudo-concave si et seulement si :(x,y) ∈ Rn × Rn tel que Of (x)(y − x) ≤ 0, on a :
f (y) ≤ f (x).

Définition 1.5.4. Soit f : Rn → R une fonction différentiable sur Rn . Alors, f est dite
pseudo-convexe si et seulement si :(x,y) ∈ Rn × Rn tel que Of (x)(y − x) ≥ 0, on a :
f (y) ≥ f (x).

Définition 1.5.5. On dit qu’une fonction f : Rn → R est quasi-convexe si et seulement

si :
∀(x, y) ∈ Rn × Rn , ∀λ ∈ [0, 1], f (λx + (1 − λ)y) ≤ max{f (x), f (y)}
f
Lemme 1.5.1. Si est une fonction fractionnaire linéaire sur un ensemble D de Rn telle
h
que ∀x ∈ D : h(x) > 0, alors [3] :

• pour chaque couple (x,y) ∈ D2 , on a :

f (x) f (y f (x)
– ≤ si et seulement si O[ ](y − x) ≥ 0
h(x) h(y h(x)
f (x) f (y) f (x)
– < si et seulement si ∇[ ](y − x) > 0
h(x) h(y) h(x)
f
• est simultanément pseudo-concave et pseudo-convexe.
h

12
CHAPITRE 1. PROGRAMMATION LINÉAIRE FRACTIONNAIRE

1.5.1 Convexité
L’ensemble X est dit convexe si tout segment joignant deux points quelconques de X
est inclus dans X.
La convexité est le premier indicateur de la difficulté du problème. En effet, certaines
méthodes sont dans l’incapacité de résoudre des problèmes non convexes de manière opti-
male.

1.6 Résolution d’un programme linéaire fractionnaire

1.6.1 La résolution graphique en nombres entiers

Comme l’a noté Steuer[23], Les programmes fractionnaires linéaires présentent un in-
térêt particulier mis en évidence par la linéarité des courbes niveaux de leurs fonctions
critères. En effet, pour illustrer cet aspect, considérons une Z-courbe niveau quelconque de
t
la fonction critère : Z= pqt x+α
x+β

après simplification, nous obtenons :

Z(q t x + β)= pt x + α
(p − Zq)t x =Zβ − α

qui est une expression linéaire de la Z-courbe niveau de la fonction critère. Puisque Z
est quelconque, on voit que chaque courbe niveau du critère fractionnaire linéaire est li-
néaire sur S, à condition que le dénominateur ne soit pas nul sur S. Donc, si un programme
fractionnaire linéaire unicritère possède une solution optimale, alors au moins un point
extrême de S est optimal.
En dépit de la linéarité de la courbe niveau de la fonction objectif, les courbes niveaux ne
sont pas parallèles (lorsque p 6= 0, q 6= 0 et p 6= wq pour tout w ∈ R) comme ils le sont en
programmation linéaire. L’ensemble rotation est l’ensemble de tous les points d’intersec-
tion entre la 0-courbe niveau du numérateur et la 0-courbe niveau du dénominateur[23].
L’ensemble rotation est appelé point de rotation dans R2 et axe de rotation dans R3 . Les
points de cet ensemble sont déterminés par la résolution du système suivant :
pt x = −α et q t x = −β

Exemple illustratif

Considérons le programme fractionnaire linéaire suivant :

13
CHAPITRE 1. PROGRAMMATION LINÉAIRE FRACTIONNAIRE

x1 + x2 − 1


 max Z=
5x1 + x2 − 1




s.c.





(P F L) =  5x1 + 2x2 ≥ 6




x1 ≤ 3
x2 ≤ 3






x1, x2 ≥ 0
dont le graphe est donné par la figure suivante :

Figure 1.1 – Graphe de l’exemple.

Donc la courbe de niveau Z est l’ensemble des points x = (x1, x2) satisfaisant l’équation :
(1 − 5Z)x1 + (1 − Z)x2 = 1 − Z
donc pour :
Z = 0 ⇐⇒ x1 + x2 = 1 courbe de niveau 0
Z = 1 ⇐⇒ x1 = 0 courbe de niveau 1

Les lignes discontinues représentent les 0-courbes niveaux du numérateur et du dénomi-

nateur dont l’intersection est le point de rotation r=(0,1). La flèche circulaire dénote le
gradient de la fonction fractionnaire linéaire critère et indique le sens et l’angle avec les-
quels se déplacent les courbes de niveaux. Donc, en faisant déplacer la courbe de niveau 0
autour du point de rotation suivant le sens de rotation trigonométrique, nous pouvons voir
que le point optimal x4 =(0,3) de valeur optimale Z ∗ = 1 est l’intersection du domaine S
avec la courbe de niveau Z = 1.

14
CHAPITRE 1. PROGRAMMATION LINÉAIRE FRACTIONNAIRE

1.6.2 La résolution analytique

Dans la littérature émergent trois grande stratégies de résolution d’un programme frac-
tionnaire
1- La résolution directe : Le programme reste sous sa forme originale.
2- La résolution par paramétrisation : Dans cette stratégie en modifient la fonction
objectif sans toucher l’ensemble des contraintes.
3- La résolution d’un programme équivalent : On change la fonction objectif et
l’ensemble des contraintes.
La résolution directe

Dans cette stratégie de résolution, le programme fractionnaire est traité sous sa forme ori-
ginale c’est à dire sans modifier ni la fonction objectif ni l’ensemble des contraintes, elle est
utilisé pour résoudre les problèmes fractionnaires linéaires continus, entiers, bivalentes(0-
1), mixtes.
Pour la recherche d’une solution optimale d’un programme hyperbolique en variables conti-
nues sans faire aucun changement au programme initial il existe plusieurs algorithmes et
parmi les plus récents, celui de A. Cambini et al[24]. qui permet aussi d’optimiser le pro-
blème hyperbolique sur un domaine de solutions réalisables S non borné. On considère
donc le programme hyperbolique continu (PFL) :

 pt x + α

 min
qtx + β




(P F L) = s.c
Ax ≤ b





x≥0



Où α et β sont des réels, p et q sont des vecteurs de Rn avec q est un vecteur non nul,
A est une matrice réelle de format (m× n) et b est un vecteur de Rm . Désignons par S
l’ensemble {x ∈ Rn : Ax ≤ b, x ≥ 0}

La résolution par paramétrisation

à l’inverse de la résolution directe, on construit un problème à objectif simplifié, com-

binaison linéaire du numérateur et du dénominateur par l’intermédiaire d’un paramètre,
tout en gardant inchangé l’ensemble des contraintes. Une séquence de résolutions de ce
type de problème fournit une solution du programme fractionnaire. Cette méthode a été
utilisée pour les différents programmes fractionnaires linéaires et non linéaires, en variables
continues comme en variables discrètes, sur des domaines bornés.

Afin de simplifier l’objectif du programme mathématique, un paramètre est introduit per-

mettant de ramener un programme hyperbolique en un programme paramétré linéaire,
tout en gardant l’ensemble des contraintes inchangé. Ainsi le programme obtenu peut être

15
CHAPITRE 1. PROGRAMMATION LINÉAIRE FRACTIONNAIRE

résolu " paramétriquement " : une séquence de résolutions de tels programmes à objectif
simplifié engendre une suite de solutions convergeant vers une solution optimale du pro-
gramme fractionnaire initial.
Proposée initialement en 1956 par Isbell et Marlow [25] pour des programmes hyperbo-
liques, ce n’est qu’à partir de 1967 que cette approche a connu un grand élan avec Din-
kelbach qui là généralisée aux programmes fractionnaires non linéaires. Soit le programme
hyperbolique suivant :

 pt x + α

 min Z(x) = t
q x+β




(P F L) =  s.c



 Ax ≤ b
 x≥0


Où α et β sont des réels, p et q sont des vecteurs de Rn avec q est un vecteur non nul,
A est une matrice réelle de format (m × n) et b est un vecteur de Rm . Désignons par S
l’ensemble {x ∈ Rn : Ax ≤ b, x ≥ 0}

le programme paramétré est un programme linéaire dont l’objectif est fonction de ¸ λ ∈ R :

min (pt − λq t )x + α − λβ



s.c


(P F L) =


 Ax ≤ b
x≥0


Remarquons que cette nouvelle fonction à maximiser est linéaire alors que celle du pro-
gramme (PFL) ne l’est pas.
t ∗
Soit x une solution optimale de (PFL) et ¸λ∗ = pqt xx∗ +α
+β
.
Dinkelbach[14] a montré que :
Z(λ) = 0 ⇔ λ = λ∗

et qu’une solution optimale de (P F Lλ∗ ) est aussi solution optimale de (PFL).

Ainsi, résoudre (PFL) est équivalent à trouver λ avec Z(λ) = 0

La résolution d’un programme équivalent

La transformation du programme fractionnaire en un programme équivalent à objectif non

fractionnaire est obtenue par un changement de variables [26]. A l’inverse de l’approche
paramétrée, ce changement de variables induit l’ajout d’une contrainte et d’une variable.
Plus précisément, cette transformation, proposée par Charnes et Cooper [29] pour le pro-
gramme hyperbolique en variables continues, Cette transformation en un programme li-
néaire équivalent a pour but d’appliquer les algorithmes standards tels que la méthode du
Simplexe.

16
CHAPITRE 1. PROGRAMMATION LINÉAIRE FRACTIONNAIRE

Soit le problème (PFL) suivant :


 pt x + α

 max Z(x) =
qtx + β




(P F L) = s.c
Ax ≤ b





x≥0



En fait le changement de variable suivant :

1 1 y
z= q t x+β
y = ( qt x+β )x x= z

alors :
maxZ = z(pt x + α)

max Z = z(pt ( yz ) + α) = pt y + αz .................................(1)

Ax ≤ b ⇔ A( yz ) ≤ b ⇔ Ay − bz ≤ 0.....................(2)

1 1
z= q t x+β
⇔ (q t x + β) =
z
⇔ (q t ( yz ) + β)z = 1

⇔ q t y + βz = 1............................(3)
y
x≥0⇔ z
≥ 0 ⇔ y ≥ 0 et z > 0.....................(4)

Alors de (1), (2), (3) et (4) en obtient le problème fractionnaire linéaire équivalent (PFLE)
suivant : 



max pt y + αz
 s.c



(P F LE) =  Ay − bz 6 0



 q t y + βz = 1
 y > 0, z > 0


1.6.3 Méthode de Cambini et Al [24]

la méthode proposé par Cambini et Al[24] utilise le concept de solution niveau optimale
dont la définition est la suivante :

Définition 1.6.1. un point x∗ est une solution niveau optimale pour le problème(P F L)si
et seulement si x∗ est une solution optimale du problème :

17
CHAPITRE 1. PROGRAMMATION LINÉAIRE FRACTIONNAIRE



 min f (x) = cx + c0
(Px∗ )  Ax ≤ b, x ≥ 0

qx = qx∗
De plus,si x∗ est un point extrême de X = {x ∈ Rn /Ax ≤ b, x ≥ 0} on dira que x∗ est une
solution optimale niveau de base .

théorème 1.6.1. un point x0 est une solution optimale du problème (P F L) si et seulement

si le vecteur gradiant réduit γ̂ = dˆ0 ĉ−ĉ0 dˆ et tel que γ̂j ≤ 0 pour tout indice hors base j ∈ N .

Algorithme 1 :Algorithme de Cambini et Al

Etape 1
Trouvé la solution optimle niveau x1 .
si une telle solution n’existe pas, alors supx∈S Z(x) = +∞,Terminer.
Sinon, poser k = 1 et aller à l’étape 2.
Etape 2 :
Si J = j/q̂j > 0 = ∅ ; , terminer. xi est une solution optimale du problème (PFL).
Sinon, soit k tel que p̂q̂kk = maxj∈J p̂j /q̂j
Si γ̂k > 0, aller à l’étape 3
Si γ ≤ 0, terminer. xi est une solution optimale de (PLE).
Etape 3 :
La variable hors base xNk entre dans la base en moyennant une opération pivot.
Si une telle opération est possible, Poser i := i + 1 et aller à l’étape 2.
Si une telle opération n’est pas possible. Terminer : supx∈S Z(x) = p̂q̂kk .

1.6.4 la méthode de Dinkelbach[14]

Une des stratégies les plus célébres et générales pour la résolution des programmes
fractionnaire (non nécessairement linéaires) est l’approche paramétrique décrite par Din-
kelbach [14]. dans le cas de la programmation fractionnaire linéaire,cette méthode réduit
la solution d’un problème à la solution d’une séquence de programmes linéaires.
Considérons le problème de programmation fractionnaire suivant :

f (x)

min Z(x) =




h(x)
(P F L)



s.c
x∈S


L’ensemble S est supposé non vide, compact(ent un ensemble fermé) dans Rn , les fonc-
tions f (x), h(x) sont des fonctions continues à valeurs réelles dans S, h(x) > 0, ∀x ∈ S Le
problème paramétré associe Q(λ)consiste à simplifier l’objectif en combinant linéairement
le numérateur et le dénominateur par l’intermédiare d’un paramètre réel λ.

18
CHAPITRE 1. PROGRAMMATION LINÉAIRE FRACTIONNAIRE



min v(λ) = f (x) − λh(x)
(Q(λ))  s.c

x ∈ S, λ ∈ R
En notant λ∗ la valeur optimale de (P F L), le résultat fondamental liant le programme
fractionnaire au programme paramétré associé est donné par :

théorème 1.6.2. [14] Toute solution optimale λ∗ de problème Q(λ∗ ) est une solution op-
timale du problème (P F L).
En tant que fonction de la variable λ, la valeur optimale v(λ) du programme paramétré
vérifie quelques propriétés que nous résumons ci-aprés :

proposition 1.6.1 :[14]

La fonction λ → v(λ) est continue, strictement décroissante, convexe v(0) > 0 et v(λ) tend
vers −∞ quand λ tend vers +∞.
Si de plus le programme est hyperbolique, alors v est linéaire par morceaux.
En particulier, l’équation v(λ) = 0 admet une solution unique λ∗ , plus précisément :

proposition 1.6.2 :[14]

• v(λ) = 0 ⇔ λ = λ∗
• v(λ) > 0 ⇔ λ < λ∗
• v(λ) < 0 ⇔ λ > λ∗

1.6.5 la méthode de gradiant

ne nécessite aucun changement de variables ni l’ajout de nouvelle variables ou de
contraintes et l’utilisation de la méthode classique du simplexe reste toujours possible.en
effet dans cette méthode une séquence de programme linéaire sont résolus,dans chacun de
ces programmes linéaires l’objectif fractionnaire est remplacé par le gradiant de ce dernier
au point optimale du programme précédent

1.7 Conclusion
Dans ce chapitre nous avons fait un rapelle sur quelques notions mathématiques, telle
que les définitions, les notions de convexité, et les fonctions convexe généralisées. nous avons
donné un aperçu sur la programmation fractionnaire linéaire telle que le modèle générale,
les domaines d’applications, et les quatre grandes méthodes de résolution : graphique,
dirècte, par paramétrisation, et la résolution avec un programme équivalent.

19
Chapitre 2
Généralité sur l’optimisation multiobjectifs

2.1 Introduction
Dans la vie réelle, les ingénieurs sont face à des problèmes de complexité augmantante
qui surgissent quotidiennement dans divers secteurs (transport, télécommunication, écono-
mie, ...etc). Parmi ces problèmes, on retrouve les problémes d’optimisation multi-objectifs
décrits sous plusieurs objectifs à optimiser.

Un problème d’optimisation multi-objectifs consiste à rechercher les meilleures solutions

compromis entre les critères à optimiser, connues par les solutions Pareto optimales, qui
correspondent mieux aux préférences du décideur. L’une des questions les plus difficiles est
donc liée à l’identification de ces solutions ou d’une approximation de celles-ci pour des
problèmes complexes.

Ce chapitre présente le contexe de l’optimisation multi-objectifs qui sera le cadre de notre

travail, Nous introduisons les principales définitions telles que la dominance, la surface de
compromis ainsi les principales approches de résolution.

2.2 Notion fondamentale

2.2.1 Définition du problème
Tout d’abord définissons trois notions de base d’un problème d’optimisation multi-
objectifs :

– Fonction objectif : La fonction objectif est la fonction à optimiser (maximiser ou

mini- miser), appelée aussi fonction d’adaptation, fonction coût, ou encore perfor-
mance. On la note Z(x).
– Paramètre : Le paramètre est une variable qui exprime une donnée quantitative

20
CHAPITRE 2. GÉNÉRALITÉ SUR L’OPTIMISATION MULTIOBJECTIFS

ou qualitative au problème (exemple : coût, temps, taux d’erreur, ...etc). Ce sont

les variables de la fonction objectif, appelée aussi variables de conception, variables
d’optimisation ou encore variables de projet.
– Contrainte : La contrainte est une condition qui doit être respectée par le vecteur
de décision pour trouver la solution admissible.

Un problème d’optimisation multiobjectifs consiste à optimiser k fonctions objectifs simul-

taniment (k ≥ 2). Il est définit sous la forme suivante :
(
optimiser Z(x) = (Z1 (x), Z2 (x), ...., Zk (x))
(P M O)
s.c x ∈ S
Où :

– x = (x1 , x2 , x3 , .....xn )t ∈ Rn représente le vecteur de décision avec i = 1, n

– Rn s’appelle espace de décision.
– Z(x) = (Z1 (x), Z2 (x), ..., Zk (x)) ∈ Rk représente le vecteur des fonctions objectifs
avec Zi les fonctions objectifs (k ≥ 2).
– Rk s’appelle espace des critères ou espace des objectifs.
Avec :

Z : Rn → Rk
x 7→ Z(x) = (Z1 (x), Z2 (x), ..., Zk (x))

Et :

Zi : Rn → R
x 7→ Zi (x), i = i, k.

– S est l’ensemble des solutions réalisables, S ⊂ Rn .

– D = Z(S) est l’image de S par Z, il s’appelle espace des critères réalisables
D ⊂ Rk , il est donnée par : D = Z(S) = {z ∈ Rk /z = Z(x); x ∈ S}
Où z est le vecteur de l’espace des critères qui correspond à la solution réalisable x.
pour cela nous avons présenté l’espace de décision et l’espace des critères dans la figure
suivante :

21
CHAPITRE 2. GÉNÉRALITÉ SUR L’OPTIMISATION MULTIOBJECTIFS
z2

variables de décission
x = (x1 , x2 ) Espace objectifs ou espace
x2 Espace de décision des critères: D = Z(S)
z

•S •
z1

z3
x1
Figure 2.1 – Représentation de l’espace des décisions et l’espaces objectifs correspondant.

2.3 Problématique
La difficulté principale d’un problème multiobjectif est qu’il n’existe pas de définition
de la solution optimale. Le décideur peut simplement exprimer le fait qu’une solution est
préférable à une autre mais il n’existe pas une solution meilleure que toutes les autres.

Dés lors résoudre un problème multiobjectif ne consiste pas à rechercher la solution

optimale mais l’ensemble des solutions satisfaisantes pour lesquelles on ne pourra pas ef-
fectuer une opération de classement. Les méthodes de résolution de problème multiobjectif
sont donc des méthodes d’aide à la décision car le choix final sera laissé au décideur.

Pour répondre à ce problème, il existe deux types de comportement. Le premier et de

ramener un problème multiobjectif à un problème uni-critère au risque d’enlever toute si-
gnification au problème. Le second comportement est d’apporter des réponses au problème
au prenant en compte l’ensemble mono-objectif. La différence entre ces deux communautés
s’exprime dans le schéma ci-dessous. Soit le décideur intervient dés le début de la définition
du problème, en exprimant sa préférence, afin de transformer un problème multiobjectif en
un problème uni-critère. Soit le décideur effectue son choix dans l’ensemble des solutions
proposées par le solveur multi-objectif.

22
CHAPITRE 2. GÉNÉRALITÉ SUR L’OPTIMISATION MULTIOBJECTIFS

Problème
Multi-objectifs

Résolution Intervention
Multi-objectifs du décideur
le décideur choisit un poids
pour chaque objecif et les
combine tous ensemble
Ensemble de Problème
plusieurs Mono-objectif
solutions Pareto

le décideur choisit une

solution parmi l’ensemble de
solutions Pareto obtenues Résolution
Intervention
du décideur Mono-objectifs

SOLUTION
UNIQUE

Figure 2.2 – Schéma de résolution

Les problèmes multiobjectif ont en général un ensemble de solutions optimales dont

les valeurs des fonctions sont en fait les meilleurs compromis possibles dans l’espace des
fonctions objectif. Il faut donc utiliser une autre définition de la "meilleure solution",afin
de déterminer exactement quelle solution peut être considéré meilleure par rapport à une
autre. Le concept de "l’optimalité de Pareto" (Pareto, 1896)[4]est ainsi utilisé pour établir
une hiérarchie entre les solutions d’un problème multi-objectif en vue de déterminer si une
solution appartient réellement à l’ensemble des meilleurs compromis.

2.3.1 La relation de dominance

Notation : Si le vecteur U domine le vecteur V , on note alors U ≺ V la relation binaire
de dominance.
Définitions : La relation binaire de dominance notée ≺ :

– n’est pas réflexive, car un vecteur ne se domine pas lui même.

– n’est pas symétrique, car on n’a jamais U ≺ V et V ≺ U .

23
CHAPITRE 2. GÉNÉRALITÉ SUR L’OPTIMISATION MULTIOBJECTIFS

– est transitive, car U ≺ V et V ≺ U implique U ≺ W .

– n’est pas antisymétrique, en raison de l’existence de solutions Pareto-équivalentes.
Au final , on conclut que la relation de dominance est donc une relation d’ordre partiel
strict sur l’espace des critères réalisables [5].

Remarque 2.3.1. Notons que U ≮ V n’implique pas V ≺ U .

2.3.2 Optimalité de Pareto

Les problèmes rencontrés dans la vie réelle sont souvent décrits à l’aide de plusieurs
critères ou objectifs, c’est l’optimisation multiobjectifs qui consiste à optimiser simultané-
ment plusieurs fonctions[6],[7]. Cependant, ces fonctions objectifs ont la particularité d’être
souvent conflictuelles et contradictoires entre elles, ce qui explique que dans la plupart du
temps on trouve une multitude de solutions en résolvant un problème d’optimisation mul-
tiobjectifs. La solution n’est pas unique contrairement au problème mono-objectif, mais un
ensemble de solutions connu comme l’ensemble des solutions "Pareto optimales". En éffet,
il définit la formule suivante :
"Dans un problème multiobjectifs, il existe un équilibre tel que l’on ne peut pas améliorer
un objectif sans détériorer au moins un des autres objectifs".
Cet équilibre est appelé optimum de Pareto, point non dominé ou encore solution efficace.
La définition de l’ensemble de Pareto optimalité provient directement de la notion de do-
minance d’après cette équivalence :

Une solution x∗ est Pareto optimale si et seulement s’il n’existe aucun point x ∈ S telle
que :

ci x ≤ ci x∗ , ∀i = 1, k,avec c ∈ R

Et

ci x < ci x∗ , pour au moins un i = 1, k,avec c ∈ R

2.3.2.1 Effcacité forte

Une solution x∗ est fortement efficace si et seulement s’il n’existe pas un vecteur de
décision x tel que : ci x < ci x∗ , ∀i = 1, k

Autrement dit, une solution est fortement efficace si son vecteur objectif est fortement
dominé.

2.3.2.2 Efficacité faible

Une solution x∗ est faiblement efficace si et seulement s’il n’existe pas un vecteur de
décision x tel que ci x ≤ ci x∗ , ∀i = 1, k.

24
CHAPITRE 2. GÉNÉRALITÉ SUR L’OPTIMISATION MULTIOBJECTIFS

Autrement dit, une solution est faiblement efficace si son vecteur objectif est faiblement
dominé.

Remarque 2.3.2. Toute solution efficace est faiblement efficace et l’inverse est faux.

2.3.3 Point particuliers

Point idéal
Le point idéal est un vecteur de Rk dont les coordonnées sont les valeurs minimales de
chacune des fonctions objectifs pris séparément. D’une autre manière, c’est le vecteur qui
minimise chacune des fonctions objectifs fi pris séparément.

Z ∗ = (z1∗ , z2∗ , ...zk∗ )

avec

Zi∗ = min(fi (x)), ∀i = 1, k

x∈S

Remarque 2.2.1
– Le point idéal n’appartient pas à l’espace des critères réalisables car les objectifs sont
contradictoires.
– Le point idéal est appelé aussi vecteur des valeurs les plus préférées de chaque objectif
fi , ainsi le point idéal peut être utilisé comme point de référence.
– Le point de référence est un vecteur qui définit les valeurs souhaitables (buts) qu’il
faut atteindre par chaque objectif fi .

Matrice des gains

Soit xi la solution optimale en minimisant le critère fi . La matrice carrée de dimension

(k × k) formée par :

zi∗ = min(f i(x)) = fi (xi ), ∀i = 1, k

x∈S

Et

zij = fi (xj ), ∀i = 1, k, ∀j = 1, k et i 6= j.

est appelée matrice des gains ("payoff matrix").

• Les éléments de la diagonale principale de cette matrice représentent en fait le point

idéal.

25
CHAPITRE 2. GÉNÉRALITÉ SUR L’OPTIMISATION MULTIOBJECTIFS

···
 
Z11 = Z1 (x1 ) Z12 Z1k

 Z 21 Z22 = Z2 (x2 ) ··· Z2k 

 .
.. .
.. ... .. 
.
 
 
Z1k Zk2 · · · Zkk = Zk (xk )

avec :
x1 est la solution optimale de z1∗ = minx∈S Z1 (x).
x2 est la solution optimale de z2∗ = minx∈S Z2 (x).
..
.
xk est la solution optimale de zk∗ = minx∈S Zk (x).
Remarque 2.3.3. Si pour un objectif Zi , le problème admet plusieurs solutions optimales,
la matrice des gains n’est donc pas unique. En effet, la colonne j de la matrice dépendra
de la solution choisie xi .
Point Nadir
le vecteur nadir z nad correspond aux bornes supérieures de chaque objectifs sur la surface
de Pareto et non pas dans tout l’espace réalisable S.

z nad = (z1nad , z2nad , ..., zknad )

avec
zinad = max (Zi (x)), ∀i = 1, k
x∈XP areto

Remarque 2.3.4.
– On peut définir le point nadir de la matrice des gains, où z nad se trouve sur le
maximum de la ligne de la matrice des gains pour un problème à minimiser.
– Le point nadir est le vecteur des valeurs les plus mauvaises de chaque critères Zi , il
est utilisé comme point de réservation.
– Le point nadir sert à restreindre l’espace de recherche, il est utilisé dans certaines
méthodes d’optimisation interactives.
– A titre d’exemple, on peut utiliser le point idéal et le point nadir pour la normali-
sation des valeurs des objectifs par :
Zi −zi∗
zinorm = zinad −zi∗

Une visualisation de l’ensemble des différentes définitions est illustrée sur la Figure
suivante :

26
CHAPITRE 2. GÉNÉRALITÉ SUR L’OPTIMISATION MULTIOBJECTIFS

Figure 2.3 – Illustration des différentes définitions.

2.4 Structure du front de Pareto

L’objectif est donc de fournir aux décideurs un ensemble de solution de Pareto, afin
qu’ils puissent ensuite choisir les solutions qui les intéressent le plus.

Représentation du front Pareto

Toutes les représentations de surface de compromis ou front de Pareto ne sont pas équi-
valentes. En effet, la représentation idéale du front Pareto devra être constituée de points
"solution" de notre problème répartis de manière uniforme sur la surface de compromis
(voir figure)

27
CHAPITRE 2. GÉNÉRALITÉ SUR L’OPTIMISATION MULTIOBJECTIFS

Figure 2.4 – La représentation de la surface de compromis

2.5 Classification des méthodes de résolution

L’optimisation multiobjectifs consiste à définir des méthodes efficaces de résolution où
tous les objectifs sont pris en compte, et d’après la classification des méthodes de résolution
multiobjectifs on constate qu’il n’existe pas de méthodes de résolution efficaces et adaptées
à tous les types de problèmes.

2.5.1 Méthode ε contrainte [8]

Cette méthode permet de transformer le problème d’optimisation multiobjectif en un
problème mono objectif. La méthode consiste à convertir (m − 1) des m objectifs du pro-
blème en contraintes et d’optimiser séparément l’objectif restant [8]. La démarche est la
suivante :
• Nous choisissons un critère à optimiser prioritairement.
• Nous transformons le problème conservant l’objectif prioritaire et nous nous trans-
formons les autres objectifs en des contraintes d’inégalité Le problème peut être
reformulé de la manière suivante :


 maximiser Zi (x)
s.c


(Pε


 Zj (x) ≤ εj , ∀j 6= i, j = 1, k
x∈S


L’approche par ε-contrainte doit aussi être appliquée plusieurs fois en faisant varier le vec-
teur ε pour trouver un ensemble de points Pareto optimaux. Cette approche a l’avantage

28
CHAPITRE 2. GÉNÉRALITÉ SUR L’OPTIMISATION MULTIOBJECTIFS

par rapport à la précédente de ne pas être trompée par les problèmes non convexes[9].

théorème 2.5.1. [10] Pour tout vecteur ε = (ε1 ; ε2 ; ..., εk ) tel que le problème (Pε ) a
une solution optimale alors cette solution est Pareto optimale pour le problème (P M O).

Exemple illustratif
Soit le problème multiobjectifs suivant :


 max Z1 (x) = −3x1 + x2




 max Z2 (x) = x1 + 2x2
max Z3 (x) = 2x1 + x2


(P )


 3x1 − x2 ≤ 6
x2 ≤ 2




2

x = (x1 , x2 ) ∈ R+


Résoudre le problème en considérant le critère 3 comme prioritaire avec

ε = (ε1 , ε2 )t = (1, 3)t


 max Z(x) = 2x1 + x2
3x1 − x2 ≤ 6





x2 ≤ 2


(Pε )


 −3x1 + x2 ≤ 1
x1 + 2x2 ≤ 3




2

x ∈ R+


La résolution de (P ε) par la méthode du simplexe nous donne la solution optimale

x∗ = (x1 , x2 )t = (0, 0)t

Donc, cette solution est Pareto optimale pour le problème initial d’après le théorème (2.5.1).

2.5.2 Méthode dite "but programmé ou Goal programming"

Cette méthode, qui relève d’une théorie très avancée dans le domaine des problèmes
multiobjectifs, a été initialement conçue par (Charnes et Cooper [11]) cette méthode dans
laquelle le décideur fixe un but Ti , i = 1, k à atteindre pour chaque objectif Zi . Ces
valeurs sont ensuite ajoutées au problème comme des contraintes supplémentaires. La nou-
velle fonction objectif est modifiée de façon à minimiser la somme des écarts entre les
résultats et les buts à atteindre.
Pk
minx∈S i=1 (Zi (x) − Ti )

Remarque 2.5.1.

29
CHAPITRE 2. GÉNÉRALITÉ SUR L’OPTIMISATION MULTIOBJECTIFS

1. Cette méthode a l’avantage de fournir un résultat même si un mauvais choix initial

a conduit le décideur à donner un ou plusieurs buts non réalisables.
2. La méthode est facile à mettre en oeuvre mais la définition des buts à atteindre est
une question délicate.

2.5.3 Méthode des sommes pondérées [30]

Cette méthode de résolution d’un problème de programmation multiobjectifs est la
plus évidente et, probablement, la plus couramment utilisée en pratique. Elle consiste à
transformer un problème multiobjectifs en un problème qui combine les différentes fonctions
objectif du problème en une seule fonction Z de façon linéaire, l’idée de cette méthode est
d’associer une pondération ωk à chaque objectif Z k et de résoudre le problème Pω suivant :
 Pp

 max Z(x) = k=1 ωk Zk (x)
(Pω )  s.c

x∈S

Où ω est un vecteur de :
p
Λ = {ω ∈ Rp ,
X
ωk = 1, ωk ≥ 0, k = 1, 2, ...p}
k=1

où les poids ωk sont compris dans l’intervalle [0, 1]. Différents poids fournissent différentes
solutions. La solution de ce problème est une solution Pareto optimale. Il a été montré que
pour toute solution supportée x∗ il existe un vecteur ω telle que x∗ soit une solution de Pω .
Une solution supportée étant une solution appartenant à fermeture convexe de l’ensemble
des solutions. En revanche, les solutions non supportées ne peuvent être trouvées par cette
méthode. Ainsi, pour les problèmes pour lesquels le front Pareto est convexe il sera possible
de trouver l’ensemble du front Pareto avec cette méthode.

Graphiquement, la solution optimale donnée par la méthode de la somme pondérée est

le point tangent d’un hyperplan d’équation pk=1 ωk Zk (x) = c avec le front de Pareto du
P

problème considéré, tel que c est minimum et x est une action.(voir la figure)

30
CHAPITRE 2. GÉNÉRALITÉ SUR L’OPTIMISATION MULTIOBJECTIFS

Figure 2.5 – Représentation graphique de la méthode de la somme pondérée

2.6 Approche de résolution

2.6.1 Approche Scalaire
Méthode d’agrégation des objectifs [12]
Cette méthode est la plus largement utilisée en pratique et la plus efficace du point de
vu informatique car elle est très facile à implémenter. D’ailleurs, elle est l’une des premières
méthodes utilisées pour résoudre les problèmes multiobjectifs [12].

Elle consiste à ramener le problème multiobjectifs en un problème mono-objectifs. Elle

somme tous les objectifs en affectant à chacun d’entre eux un coefficient de poids. Le
décideur choisit les poids en fonction de l’importance relative des objectifs. Le problème
multiobjectifs (P M O) devient sous la forme suivante :
( Pk
max i=1 λi Zi (x) combinaison linéaire des Zi
(Pλ )
x∈S

Où :
Pk
λi ≥ 0, ∀i = 1, k et i=1 λi = 1

La résolution du problème multi-objectifs (P M O) consiste à résoudre le problème para-

métrique (Pλ ). La solution obtenue dépend fortement des coefficients choisis pour les poids.
Cette méthode a été développée pour la généralisation des solutions non dominées. Elle
est très efficace et applicable pour produire une solution non dominée initiale et peut être
employée comme solution initiale pour d’autre technique.

théorème 2.6.1. [31]

31
CHAPITRE 2. GÉNÉRALITÉ SUR L’OPTIMISATION MULTIOBJECTIFS

Toute solution optimale du problème (Pλ ) est une solution Pareto optimale pour le
problème multi-objectifs (P M O) si tous les poids sont strictement positifs.

théorème 2.6.2. [31]

Si le problème multiobjectifs (P M O) est convexe et si x∗ est une solution Pareto opti-
male alors :

∃λ = (λ1 , λ2 , ...λk ), tel que x∗ est une solution optimale pour (Pλ ).

Cette méthode est très simple à mettre en oeuvre et elle est d’une grande efficacité, sa
difficultés est la détermination du poids de chaque critère par le décideur.

2.6.2 Approche Pareto

Les approches Pareto utilisent la notion de dominance pour comparer les solutions et
leur affecter un score ou sélectionner des solutions [13].
Ces approches ont connu un important développement en conjonction avec les algorithmes
évolutionnistes à population à partir de la seconde moitié des années 90. Elles sont devenues
la principale approche employée pour résoudre les problèmes multiobjectifs du fait de leur
capacité à trouver un ensemble potentiellement efficace via la recherche menée sur une
population de solutions. De manière générale, les algorithmes évolutionnistes multiobjectifs
affectent un score à une solution selon qu’elle est dominée ou non par d’autres solutions
de la population courante et éventuellement si elle domine d’autres solutions.

2.7 Conclusion
Dans ce chapitre, nous Nous sommes intéressées principalement au problème d’optimi-
sation multiobjectifs. En premier lieu, nous avons présenté le concept de base du problème
multiobjectifs linéaire. Ensuite nous avons introduit les principales définition et notions
nécessaires à la présentation des problèmes multiobjectifs, parmi ces définition nous ci-
tons le concept de dominance. En dernier lieu, nous avons présenté quelques méthodes de
résolution.ainsi que la caractérisation des approches de résolution.

32
Chapitre 3
Programmation Linéaire Fractionnaire
MultiObjectifs en Nombres Entiers

3.1 Introduction
La plupart des problèmes rencontrés en pratique sont de nature multiobjectifs. En ef-
fet, un problème d’optimisation multiobjectifs fractionnaire consiste à optimiser simultané-
ment plusieurs objectifs souvent contradictoires et parfois complémentaires. Contrairement
à l’optimisation mono-objectif, la résolution d’un problème multiobjectifs nous donne une
multitude de solutions, un ensemble de solutions connu comme l’ensemble des solutions ef-
ficaces.Toute solution de cet ensemble est optimale dans le sens qu’aucune amélioration ne
peut être faite sur un critère sans dégradation d’au moins un autre critère. Si les fonctions
objectifs sont linéaires, que l’ensemble des solutions réalisables est défini par des contraintes
linéaires, et si les variables x prennent des valeurs entières, alors on parle d’un programme
linéaire fractionnaire multiobjectif en Nombres Entiers.
A travers ce chapitre, qui a pour objectif principal la présentation du contexte de la pro-
grammation linéaire multiobjectifs fractionnaire en nombres entiers (M OLF P ), nous pré-
sentons les notions de base et les définitions nécessaires, ainsi que les principaux résultats
liés à la théorie de la programmation linéaire multiobjectifs en nombres entiers[15]. Nous
introduisons aussi quelques méthodes de résolution pour ce type de problème et nous don-
nons une description détaillée de ces méthodes accompagnées chacune par un exemple
illustratif.

3.2 Formulation du problème

Le problème de la programmation linéaire fractionnaire multiobjectifs (MOLFP :Mul-
tiple Objective Linear Fractional Programming problem) est l’un des modèles les plus
populaire utilisés dans la prise de décision à critères multiples. La formule générale de ce
problème peut être donnée comme suit :

33
CHAPITRE 3. PROGRAMMATION LINÉAIRE FRACTIONNAIRE
MULTIOBJECTIFS EN NOMBRES ENTIERS

c1 x + α 1

max Z1 (x) =



d1 x + β 1



c2 x + α 2





 max Z2 (x) = 2
d x + β2




c3 x + α 3



max Z3 (x) = 3


(M OLIF P ) d x + β3
 ..
.




cp x + α p



max Zp (x) = p



d x + βp




s.c





Ax ≤ b, x > 0


où le nombre d’objectifs est p ≥ 2,A ∈ Rm×n ,b ∈ Rm , et pour chaque fonction objectif Z k ,

k = 1, p,on a ck = (ck1 , ck2 , ...ckn ) ∈ R1×n , dk = (dk1 , dk2 , ...dkn ) ∈ R1×n .
On suppose que la région admissible non vide S = {x ∈ Rn /Ax ≤ b, x ≥ 0} est borné, et
la f onction dk x + β k > 0 est positif sur S pour chaque k = 1, p.
Dans de nombreuses situation réelles modélisables par la programmation mathématique,les
variables intervenant dans la modélisation sont soumises à être totalement en nombre
entiers,on parle de problème de programmation multi-objectifs linéaire fractionnaire en
nombre entiers(M OILF P : Multiple Objective integer Linear Fractional Programming
problem)

c1 x + α 1

max Z1 (x) =



d1 x + β 1



c2 x + α 2





 max Z2 (x) = 2
d x + β2




c3 x + α 3



max Z3 (x) = 3


d x + β3




(M OLIF P )  .



 .



 .
cp x + α p



max Zp (x) = p



d x + βp




s.c





x∈D


où D = S ∩ Z, Z est l’ensemble des entiers relatifs.

Comme pour les problème de programmation linéaire multiobjectifs, la résolution des pro-
blèmes de programmation linéaire fractionnaire multiobjectifs est de déterminer toutes les
solution efficaces.

34
CHAPITRE 3. PROGRAMMATION LINÉAIRE FRACTIONNAIRE
MULTIOBJECTIFS EN NOMBRES ENTIERS
théorème 3.2.1. Soit le problème unicritère linéaire suivant[16] :
 p k
max
P

 k=1 λk Z (x)
(Pλ )  s.c

x ∈ S, etλk ∈ ∧, ∀k = 1, p

La solution x∗ est efficace pour le problème (PR ) si et seulement si x∗ est une solution
optimale du problème paramétrique (Pλ )(∧ = {λk : kk=1 = 1 et 0 ≤ λk ≤ 1 λk > 0 ∀k =
P

1, p})
D’après ce théorème, l’ensemble efficient du problème (PR ) sans les contraintes d’intégrité
est bien caractérisé par les solutions du problème paramétrique (Pλ ), λ ∈ ∧. Ces solutions
se trouvent sur la frontière de S , elles sont appelées solution supportées.

Différemment du cas continu, la difficulté principale rencontrée lorsqu’on traite les pro-
blèmes multiobjectifs à variables discretes est l’existence de solutions efficaces pour (P )
qui ne sont pas optimales pour (Pλ ) et ce en raison de non-convexité du domaine réali-
sable, ces solutions efficaces sont dites solutions non supportées (le front Pareto de (P ) est
l’union de l’ensemble des solutions non supportées de (P ).

La nature des problèmes de programmation linéaire en variables continues et les problèmes

de programmation linéaire en variables discrètes est différente. Contrairement à la program-
mation linéaire continue où on s’intéresse seulement aux solutions sommets du polyèdre,
les solutions optimales du problème discret peuvent se trouver à l’intérieur du polyèdre et
par conséquent la recherche d’une solution optimale d’un problème de programmation en
nombres entiers est souvent NP-complet et peut être même NP-difficile.

Il faut noter cependant que, si un problème d’optimisation combinatoire est facile à ré-
soudre, il n’est pas forcément de même pour sa version multi-objectif.

3.2.1 Complexité du problème

La complexité d’un algorithme est le nombre d’opérations élémentaires(affectations,
comparaisons, opérations arithmétiques) éfféctuées par cet algorithme. Ce nombre s’éx-
prime en fonction de la taille n des données.
On s’intéresse au coût exact quand c’est possible, mais également au coût moyen (que se
passe-t-il si en moyenne sur toutes les exécutions du programme sur des données de taille n
), au cas le plus favorable, ou bien au pire cas. On dit que la complexité de l’algorithme est
O(f (n)) où f est d’habitude une combinaison de polynômes, logarithmes ou exponentielles.
Ceci reprend la notation mathématique classique, et signifié que le nombre d’opérations
effectuées est borné par cf(n), où c est une constante, lorsque n tend vers l’infini.
Les algorithmes usuels peuvent être classées en un certain nombre de grandes classes de
complexité.

35
CHAPITRE 3. PROGRAMMATION LINÉAIRE FRACTIONNAIRE
MULTIOBJECTIFS EN NOMBRES ENTIERS
• Les algorithmes sous-linéaires, dont la complexité est en général en o(log n). C’est le
cas de la recherche d’un élément dans un ensemble ordonné fini de cardinal n.
• Les algorithmes linéaires en complexité o(n) ou en o(n log n) sont considérés comme
rapides, comme l’évaluation de la valeur d’une expression composée de n symboles
ou les algorithmes optimaux de tri .
• Plus lents sont les algorithmes de complexité située entre o(n2 ) et o(n3 ), c’est le cas
de la multiplication des matrices et du parcours dans les graphes.
• Au delà, les algorithmes polynômiaux en o(nk ) pour k > 3 sont considérés comme
lents, sans parler des algorithmes exponentiels (dont la complexité, est supérieure
à tout polynôme en n), que l’on s’accorde à dire inutilisables dés que la taille des
données est supérieure à quelques dizaines d’unités.

3.2.2 Solutions supportées et non supportées

Les problèmes de programmation linéaire multiobjectifs en nombres entiers ont la par-
ticularité d’avoir le domaine de décision non convexe, ce qu’il en résulte que sa résolution
est complexe et difficile à traiter. En effet, les méthodes classiques qui permettent de trou-
ver les solutions efficaces ne sont plus valables pour les problèmes (M OILP ) car certaines
solutions ne peuvent pas être obtenues.
De ce principe, on répartie l’ensemble des solutions efficaces en deux sous ensembles : les
solutions supportées et les solutions non supportées.
Solutions Supportées notées SES : elles appartiennent aux portions convexes du front de
Pareto (elles se situent sur l’enveloppe convexe de la frontière de Pareto).On obtient ces
solutions en optimisant une agrégation linéaire des objectifs, c’est à dire transformer un
problème multiobjectifs en un problème mono-objectifs.
Solutions Non Supportées notées SENS : elles se trouvent dans les parties non convexe.

Remarque 3.2.1. L’ensemble des solutions du problème (M OILP ) est égal à l’union des
solutions supportées SES et des solutions non supportées SENS.

f2 Solution supportées
Solution non supportées

f1
Figure 3.1 – Solutions supportées et non supportées

36
CHAPITRE 3. PROGRAMMATION LINÉAIRE FRACTIONNAIRE
MULTIOBJECTIFS EN NOMBRES ENTIERS

3.3 Méthodes de résolution d’un programme linéaire

en nombres entiers
3.3.1 La méthode de gomory [27]
C’est une méthode qui a été développée par Ralph E : Gomory[27] en 1958 a
fin de résoudre les problèmes (P LN E). L’idée principale de cette méthode est d’ajouter
des contraintes linéaires qui n’excluent aucun point entier réalisable, une par une jusqu’à
ce que la solution optimale de la relaxation soit entière.
Dans une première étape, on utilise l’algorithme du simplexe pour résoudre le programme
(P L) a
fin de chercher une solution de base optimale, si elle existe, on choisit une variable de
base non entière et on génère une inéquation sur la contrainte associée à cette variable a
fin de couper la région de faisabilité courante, étant donnée une base optimale B du
problème (P L).
Le tableau optimale correspondant est donné par :

xB Â = B −1 A b̂ = B −1 b
−Z ĉ = c − ΠA Z − cB B −1 b

Table 3.1 – simplexe optimal associé à la base B.

Où :

• π = cB (AB )−1 : est dit vecteur multiplicateur relatif à la base B.

• ĉ = c − πA : est dit vecteur coût réduit relatif à la base B avec ĉB = 0
Si la solution optimale de (PL) est entière, donc elle est solution optimale du problème
(ILP). Sinon, parmi les variables de base, choisissons xi , i ∈ B dont la valeur est fraction-
naire. La ième ligne du tableau optimal est donnée par :

P
xi + j∈N âij xj = b̂i ...........(1)
Où :
âij : est un élément de la matrice optimale des contraintes Â.
N : est l’ensemble des indices hors-base.
B : est l’ensemble des indices de base.
Etant donné un nombre réel α, on désigne par bαc le plus grand entier inférieur ou égal à
α.
hαi = α − bαc est appelée la partie fractionnaire de α et bαc sa partie entière.

37
CHAPITRE 3. PROGRAMMATION LINÉAIRE FRACTIONNAIRE
MULTIOBJECTIFS EN NOMBRES ENTIERS
Puisque toutes les variables sont positives ou nulles, on a :

j∈N bα̂ij cxj ≤

P P
j∈N α̂ij xj

de (1) on a :

j∈N bα̂ij cxj ≤ b̂i .

P
xi +

Comme le membre gauche est entier dans cette inégalité, la partie droite (second
membre) peut être remplacée par sa partie entière.

j∈N bα̂ij cxj ≤ bb̂i c ......(2)

P
xi +

En soustrayant (1) de (2) on obtient :

j∈N hα̂ij ixj ≥ hb̂i i

P

En ajoutant une variable d’écart xs à cette dernière inéquation, on obtient la coupe de

Gomory définie par :

− j∈N hα̂ij ixj + xs =−hb̂i i

P

On introduit cette contrainte dans le tableau optimal du simplexe et en utilisant le dual du

simplexe, on résout le nouveau problème formé qui nous permet d’obtenir soit une solution
optimale entière ou bien une impossibilité de continuation de l’itération.

3.3.2 Méthode de Branch et Bound

La méthode de Branch et Bound appelée également méthode par séparation et éva-
luation, est la méthode la plus utilisée pour résoudre d’une façon exacte des problèmes
(PLNE). En effet, cette méthode est basée principalement sur deux procédures. En premier
lieu la séparation ou appelée encore le branchement, qui consiste à subdiviser l’ensemble des
solutions réalisables en un sous-ensemble. En deuxième lieu l’évaluation qui nous permet
de déterminer les solutions qui n’appartiennent pas à l’ensemble des solutions réalisables.
Cette méthode est très efficace, en effet son énumération des solutions d’une manière intelli-
gente permet d’éliminer des solutions partielles qui ne mènent pas à la solution recherchée.

Principe de la méthode
• On construit un arbre de recherche dont le problème initial est la racine.
• On divise le problème en sous-problèmes : l’optimum peut appartenir à l’un de ces
sous-problèmes.

38
CHAPITRE 3. PROGRAMMATION LINÉAIRE FRACTIONNAIRE
MULTIOBJECTIFS EN NOMBRES ENTIERS
- On élimine tout problème infaisable.
- Si possible, on calcule la solution du sous-problème.
- Sinon on calcule une borne inférieure, si elle est supérieure à la meilleure solution
déjà obtenue, on élimine le sous-problème considéré.
- Dans le cas restant, on subdivise à nouveau le domaine.

Etape de résolution
On présente les étapes nécessaires de résolution comme suit : (on donne ici la démarche
pour un problème de maximisation).

1/ Résolution de (PL) avec l’algorithme du simplexe

Résoudre le (P L) correspondant (sans contraintes de variables entières), la valeur de Z
du tableau optimal donne une borne supérieure au (P LN E) notée par ZBS .
Arrondir cette solution aux valeurs entiéres les plus proches et réalisables et calculer à
nouveau la valeur de la fonction objectif du (P LN E). Appelons cette valeur ZBI .
ainsi ZBI ≤ Zopt du (P LN E) ≤ ZBS

2/ Séparation
• Construire deux sous-ensembles à l’aide d’une variable non entière, soit xk cette
variable, représentons par [x∗k ] la partie entière de xk .
• Pour éliminer la solution non entière xk , on crée deux branches (deux sous-problèmes),
on obtient une branche avec xk ≤ [x∗k ] et l’autre avec xk ≥ [x∗k ] + 1.
Les deux sous-problèmes sont obtenus en ajoutant au programme linéaire (P L) précédent
(celui d’où provient la séparation), la contrainte xk ≤ [x∗k ] pour un des sous-problèmes et
la contrainte xk ≥ [x∗k ] + 1 pour l’autre sous-problème.

Toutes les solutions entières réalisables sont maintenant contenues dans l’un ou l’autre
des sous-problèmes.

3/ Résolution des sous-problèmes et détermination de nouvelles

bornes pour Z, s’il y a lieu
• Il s’agit de résoudre chaque sous-problème par l’algorithme du simplexe, notons par
M BSD, la meilleure borne supérieure disponible de Z, elle correspond à la valeur
maximale de la fonction objectif des deux sous-problèmes que nous venons de ré-
soudre.

39
CHAPITRE 3. PROGRAMMATION LINÉAIRE FRACTIONNAIRE
MULTIOBJECTIFS EN NOMBRES ENTIERS
• Nous révisons également la borne inférieure de Z, notons cette valeur par M BID,
la meilleure borne inférieure disponible, elle correspond à la valeur maximale de la
fonction objectif de toutes les solutions entières obtenues jusqu’à présent.

4/ Critère d’arrêt de l’exploitation d’une branche

La procédure de branchement est achevée lorsque l’une des conditions suivantes est
satisfaite :
(a) Le sous-problème de la branche considérée n’admet pas de solution réalisable.
(b) La solution entière obtenue pour le sous-problème de la branche est réalisable mais la
valeur Z obtenue est plus petite ou égale à M BID(Z ∗ ≤ M BID), ainsi une branche est
terminée aussitôt qu’on obtient une solution entière.
(c) Le sous-problème de la branche considérée admet une solution optimale non entière
mais sa valeur z ∗ est inférieure ou égale a celle d’un autre sous-problème à solution entière.

5/ Critère d’optimalité
Toutes les branches sont saturées, donc on termine avec la procédure de séparation.
La solution optimale de (P LN E) est la solution entière qui donne la meilleure borne
inférieure pour Z(M BID), à l’optimum on aura M BID = M BSD = Zopt de (P LN E).

6/ Continuer le processus de séparation

Dans le cas où la solution obtenue dans l’un des sous-ensembles de chaque branche
est non entière, on poursuit le processus de séparation à partir du sous-ensemble ayant la
valeur de Z ∗ la plus élevée.

S1

S2 S3 S4

S5 S6 S7 S8 S9 S10

Figure 3.2 – Principe de Branch and Bound

3.4 Résolution du problème

Le problème de la programmation multi-objrctifs linéaire fractionnaire (MOLFP) a
été largement étudié par plusieurs auteurs. De nombreuses études et applications ont été

40
CHAPITRE 3. PROGRAMMATION LINÉAIRE FRACTIONNAIRE
MULTIOBJECTIFS EN NOMBRES ENTIERS
rapportées dans la litérature, nous citons entre autre[17]. Cependant, le problème multi-
objectifs linéaire fractionnaire à variables entières (MOILFP) n’a pas reçu autant d’at-
tention que le problème (MOLFP). On ne trouve que très peu de méthodes dédiées au
problème (MOILFP), voir par exemple [18].

3.4.1 Méthodes de Abbas et Moulaï [19]

La méthode proposée par (Abbas et Moulaï)[19] pour résoudre le problème (MOLIFP)
est une généralisation de leur méthode du problème(MOLIFP),détaillée dans [19]
Afin de résoudre le problème (MOLIFP) une approche consistant à résoudre une séquence
finie de problèmes de programmation fractionnaire linéaire discrète.
Considérons le problème de programmation linéaire fractionnaire entier mono-objectif
donné sous la forme suivante.
c1 x + α 1

max Z 1 (x) =



d1 x + β 1




s.c
Ax ≤ b, x > 0


Remarque 3.4.1. Notons qu’à la place de Z 1 , on peut de façon similaire considérer une
autre fonction objectif Z k pour tout k = 1, p
La recherche des solutions réalisables entières du problème (MOLIFP) nécessite l’introduc-
tion des notations suivantes :

• S1 = {x ∈ Rn1 /A1 x ≤ b1 , A1 ∈ Rm1×n1 , b1 ∈ Rm1 , x ≥ 0}.S1 est la région tronquée

courante de S obtenue par des coupes de Gomory successives.
• x11 = (x11,j ) est la solution optimale entière donnant Z11 obtenue sur S1 .
• B11 est une base de S1 .
• a11,j ∈ Rm1 ×1 sont les vecteurs activités de (x11,j ) appropriés à la région tronquée
courante S1 .
1
• y1,j = x11,kj = (B11 )−1 a11,j où y1,j
1
∈ Rm1 ×1 , k ∈ Rp .
• I1 = {j/a11,j ∈ B11 }, et N1 = {j/a11,j ∈
/ B11 }.
• c1j est la j ème composante du vecteur c1 , d1j est la j ème composante du vecteur d1 .
• c11,1 = c1k y1,kj
1
etd11,1 = d1k y1,kj
1
P P
k∈I1 k∈I1 .
1
Z1,1
• Z 1 (x11 ) = 1
Z1,2
1
Où Z1,1 = c1 x11 + α1 et Z1,2
1
= d1 x11 + β 1 .
• γ 11,j = Z1,2
1
(c1j − c11,j ) − Z11 (d1j − d11,j le coût réduit relatif à la jième composante du
vecteur gradient réduit γ 11 .
• Γ1 = {j/j ∈ N1 et γ 11,j = 0}
pour k ≥ 2
• Sk = {x ∈ Rnk = Ak x ≤ bk , Ak ∈ Rmk ×nk , bk ∈ Rmk , x ≥ 0}

41
CHAPITRE 3. PROGRAMMATION LINÉAIRE FRACTIONNAIRE
MULTIOBJECTIFS EN NOMBRES ENTIERS
• Sk est la région courante tronquée de S obtenues aprés l’application de la coupe
j∈Nk−1 xj ≥ 1.
P

Où jk−1 ∈ Γk − 1et d’éventuelles successives coupes de Gomory.

• x1k = x11,j est la k ème solution optimale entière du problème (MOLIFP) obtenue sur
Sk à l’étape k
• xqk = {xqk,j sont les (Pk−1 ) solution entière, lorsqu’elles existes alternatives à x1k .
Où pk est un nombre entier et q ∈ {2, ...., pk }
• Bk1 est une base de de Sk .
• a1k,j ∈ Rmk ×1 sont les vecteurs activités de x1k,j sous Sk .
1
• yk,j 1
= (yk,ij ) = (Bk1 )−1 a1k,j Où yk,j
1
∈ Rmk ×1 .
• Ik = {j : a1k,j ∈ Bk1 } indices de base de Bk1 .
/ Bk1 } indices hors base de Bk1 .
• Nk = {j : a1k,j ∈
1 1 1
• Zk,j
P
= i∈Ik ci yk,ij

• Zi (x1k ) = ci x1k
1
• Γk = {j : j ∈ Nk et Zk,j 1
− Ck1 = 0} Où Zk,j 1
= cBk1 yk,j , c1j est la j ème correspondante
du vecteur c1 et cBk1 est le vecteur coût des variables de base associées à Bk1 dans le
vecteur c1 .
Ainsi,Γk est l’ensemble correspondant à la solution x1k .

théorème 3.4.1. Le point x1k de S est une solution optimale du problème fractionnaire(MOLIFP)
si et seulement si le vecteur gradient réduit γ est tel que γ 1k,j ≤ 0 pour tout indice j ∈ Nk .

Corollaire 3.1 La solution x1k du problème (MOLIFP) est unique si et seulement si le

vecteur gradient réduit γ est tel que γ 1k,j < 0 pour tout indice j ∈ Nk .

Remarque 3.4.2. Il peut arriver que la solution optimale x0 du problème (MOLIFP)

ne soit pas unique, dans ce cas , il existe une autre solution réalisable x1 6= x0 avec
Z 1 (x1 ) = Z 1 (x0 ). On dit alors que x1 est une solution optimale alternative de x0 .

Algorithme de la Méthode
Pour résoudre un problème fractionnaire linéaire en nombres entiers à objectifs mul-
tiples (MOLIFP), une procédure basée sur une technique de coupe plane est présentée dans
les étapes suivantes :
Etape(1) : Résoudre le problème (MOLFP) par n’importe quelle méthode directe de la
programmation fractionnaire discrète. Soit x11 sa solution optimale entière sur S1 , construire
l’ensemble Γ1 .

1
Etape (2) : 1/ - Si γ1,j < 0 pour tout indice j ∈ N1 , x11 est l’unique solution optimale sur

42
CHAPITRE 3. PROGRAMMATION LINÉAIRE FRACTIONNAIRE
MULTIOBJECTIFS EN NOMBRES ENTIERS
S1 .
Enregistrer le premier vecteur efficace (non dominé) par (Z 1 (x11 ), ..., Z p (x11 )) pour construire
l’ensemble des points efficaces Ef f0 . Tronquer le point x11 par la coupe de Dantzig j∈N1 xj ≥
P

1.

Par application de la méthode duale du simplexe relative à la programmation fraction-

naire,on obtient une solution réalisable entière x21 = (x12,j ) dans la région tronquée S2 .
Rajouter le vecteur correspondant (Z 1 (x21 ), ..., Z p (x21 ) à Ef f0 s’il n’est pas dominé par l’un
des précédents vecteurs critères efficaces (non dominés). Enregistrer l’ensemble Ef f1 .

2/ Sinon, il existe un indice j1 ∈ N1 pour lequelγ 1k,j = 0 Déterminer dans ce cas toutes les
solutions qui lui sont alternatives, éliminer celles qui ne sont pas efficaces et mettre à jour
l’ensemble Ef f0 . Appliquer la coupe j∈N1 /{j,1} xj ≥ 1 pour tronquer l’arête Ej,k−1 .
P

Etape (k ≥ 2) : Choisir un indice jk−1 ∈ Γk−1 et explorer l’arête Ej,k−1 pour déter-
miner d’éventuelles solutions entières réalisables x1k−1 . Augmenter l’ensemble Ef fk−2 par
les vecteurs critères non dominés correspondants pour construire Ef fk−1 . Tronquer L’arête
Ej,k−1 par la coupe j∈Nk−1 /{j,k−1} xj ≥ 1.
P

Etape finale : Le procédure s’arrête lorsque la méthode duale du simplexe est infaisable,
indiquant ainsi que la région tronquée courante ne contient aucun point réalisable entier
et que l’ensemble des point efficaces est complètement déterminé.

Exemple illustratif
Soit le problème de programmation multi-objectifs linéaire fractionnaire en nombres
entiers suivant : 
x1 − 4

 max Z1 (x) =
−x2 + 3



−x1 + 4



max Z2 (x) =





 x2 + 1
(P ) max Z3 (x) = −x1 + x2




 s.c − x1 + 4x2 ≤ 0
x1 − 12 x2 ≤ 4





2x2 ≤ 7





x1 , x2 ≥ 0, et entiers


Etape 1 :Résoudre le problème linéaire fractionnaire unicritère suivant :


x1 − 4

 max Z1 (x) =
−x2 + 3




(P1 ) s.c − x1 + 4x2 ≤ 0
x1 − 12 x2 ≤ 4





x1 , x2 ≥ 0 et entiers


43
CHAPITRE 3. PROGRAMMATION LINÉAIRE FRACTIONNAIRE
MULTIOBJECTIFS EN NOMBRES ENTIERS
Les solution entière optimal x11 = (4, 0)sur le domaine S1 = S est obtenue au tableau 1 et
tableau 2 suivants.

Figure 3.4 – itération 2

Figure 3.3 – itération 1

On a I1 = {1, 3, 4}, N1 = {2, 5}, Γ1 = {j ∈ N1 /γ 1j = 0} = {2}, le premier triplet corres-

pondant à x11 = (4, 0)est (Z1 (4, 0), Z2 (4, 0), Z3 (4, 0)) = (0, 0, −4).

Etape 2 :On a Γ 6= ∅,prendre l’indice j1 = 2 et parcourir l’arête Ej1 = E2 ,on calcule

d’abord le nombre θj1 = min{ 43 = 1 6= 0ce qui prouve qu’il existe une solution x21 alternative
àx11 sur l’arête Ej1 et sa valeur est x21 = (4, 1) et son triplet correspondant(0, 0, −3) domine
le triplet(0, 0, −4)d’oùEf f0 = {(0, 0, −3)}.
l’arête Ej1 est tronquée par la coupe j∈N1 /{2} xj ≥ 1 ce qui donne x5 ≥ 1.
P

on rajoute cette coupe au tableau 1 et on applique la méthode Dual de Simplexe pour

obtenir une nouvelle solution réalisable entière optimal x12 = (3, 0)donnée au tableau 2.le
triplet correspondant ( −1 3
, 1, −3) est non dominé d’oùEf f1 = {(0, 0, −3), ( −1
3
, 1, −3)}.

Etape 3 :On a N2 = {2, 6} et comme Γ2 = ∅ donc la solution x12 = (3, 0) est unique.
cette solution est tronquée par la coupe de Dantzig j inN2 xj ≥ 1 c’est à dire x1 + x6 ≥ 1.
P

Après application de la méthode Dual de Simplexe, la nouvelle solution entière optimale

x13 = (2, 0) est obtenue au tableau 3 suivant :

44
CHAPITRE 3. PROGRAMMATION LINÉAIRE FRACTIONNAIRE
MULTIOBJECTIFS EN NOMBRES ENTIERS

Figure 3.5 – itération 3

le triplet non dominé ( −23

, 2, −2) obtenu est rajouté à Ef f1 pour construire l’ensemble
Ef f2 = {(0, 0, −3), ( 3 , 1, −3), ( −2
−1
3
, 2, −2)}.
De manière similaire ,les itération se poursuivent jusqu’à l’étape (6) où on obtient le tableau
6 final suivant :

Figure 3.6 – itération 6

45
CHAPITRE 3. PROGRAMMATION LINÉAIRE FRACTIONNAIRE
MULTIOBJECTIFS EN NOMBRES ENTIERS
Lors de l’application de la méthode Dual du Simplexe, l’opération usuelle de pivot de-
vient impossible indiquant que le domaine tronqué restant ne contient aucun point entier
réalisable et que toutes les solution efficaces du problème étudié ont été obtenues.D’où
l’ensemble Ef f des points non dominés du problème (P1 ) est :
Ef f = {(0, 0, −3); ( −1
3
, 1, −3); ( −2
3
, 2, −2); (−1, 3, −1); ( −4
3
, 4, 0)} ce qui correspond à l’en-
semble des solutions efficaces suivant Ef f = {(4, 1); (3, 0); (2, 0); (1, 0); (0, 0)}.

Discussion :
Dans la première étape,un calcul considérable est nécessaire pour obtenir une première
solution entière optimale du problème linéaire fractionnaire en nombre entiers (P1 ) est la
méthode doit passer en revue tous les points entières de l’ensemble des solutions réalisables
ce qui alourdit d’avantages la complexité de l’algorithme.

3.4.2 Méthode de Chergui et Moulaï [20]

L’approche adoptée dans cette méthode [20] pour générer toutes les solutions efficaces
du problème (M OIF LP ) est basée sur la résolution du programme linéaire fractionnaire
(P)suivant,à chaque étape (k)de l’algorithme :

c1 x + α 1

max Z 1 (x) =



d1 x + β 1

(P ) 


s.c
x ∈ Sk


où S0 = S et sans contraintes d’intégrité des variables.

Soit x∗k la solution entière obtenue après résolution du problème (P) on note Bk l’ensemble
des indices des variables de base et Nk l’ensemble des indices des variables hors base de x∗k .

Soit γ kj la j ème composante du vecteur gradient réduit γ k défini pour chaque critère k, k ∈
{1, ...., p} par :
k k k k
γ k = β ck − αk d Où ck , d , β et αk sont les valeur mises à jour de ck , dk , β k et αk respec-
tivement.
On définit l’ensemble Hk en x∗l par :

Hk = {j ∈ Nk , |∃k ∈ {1, ...., p} : γ kj > 0} {j ∈ Nk , |γ kj = 0, ∀k ∈ {1, ..., p}}

S

Ainsi, l’ensemble Sk+1 est définit par Sk+1 = {x ∈ Sk | j∈Hk xj ≥ 1}.

P

Algorithme de la méthode
L’algorithme de génération de toutes les solutions entères efficaces du programme(M OILF P )
est présenté dans les étapes suivants :

46
CHAPITRE 3. PROGRAMMATION LINÉAIRE FRACTIONNAIRE
MULTIOBJECTIFS EN NOMBRES ENTIERS

Etape(0) : Initialization : Créer le premier noeud avec le programme (P )(Ef f = ∅Ef f

étant l’ensemble des des solutions efficaces du problème multi-objectif (M OILF P ))

. Etape(1) :Étape génerale : Tant qu’il existe un noeud k non encore sondé qui corres-
pond à la région Sk ,faire :
Résoudre le programme linéire fractionnaire correspondant (P ) par la méthode duale du
simplexe (la méthode,est utilisée juste au début pour la résolution du programme initial
(p) (c’est à dire pour S0 = S ).
• Si le programme (P) n’a pas de solutions réalisables, alors le noeud correspondant
est sondé.
• Sinon, soit xk la solution optimale. Si xk n’est pas entière, aller à l’étape(a), sinon
aller à l’étape (b).
Étape(1.a) : Séparation Choisir une coordonnée non entière xk,j de xk et séparer le noeud
k actuel en deux noueds r, r ≥ k + 1, et h = r + 1 ,Dans le tableau courant du simplexe, la
contrainte xj ≤ bxk,j c est rajoutée et un nouveau domaine est considéré au noeud r et de
façon similaire, la contrainte xj ≥ bxk,j + 1 est rajoutée pour obtenir un autre domaine au
noeud h = r + 1 (chaque programme créé doit être résolu en utilisant le même processus
jusqu’à ce qu’une solution entière réalisable soit trouvée).

Etape(1.b) : Mise à jour de l’ensemble Ef f Si le vecteur Z(xk ) n’est pas dominé

par le vecteur Z(x) pour toute solution x ∈ Ef f , alors Ef f = Ef f {xk }.
S

S’il existe x ∈ Ef f tel que Z(xk ) domine Z(x), Ef f = Ef f /{x} {xk }.

S

Déterminer les ensembles Nk etHk ;

• Si Hk = ∅, alors le noeud correspondant est sondé. Aller à l’étape (1) ;
• Sinon, rajouter la coupe j∈Hk xj ≥ 1 au programme (P). Aller à l’étape (1).
P

3.5 Conclusion
A travers ce chapitre, nous avons pris connaissance des problèmes de programmation
linéaire fractionnaire multi-objectifs en nombres entiers et la formule mathématique de
ce type de problème. Ainsi,Nous avons cité quelques méthodes classiques scalarisantes
qui transforment le problème fractionnaire multiobjectifs en problème mono-objectif. Puis,
nous avons introduit dans ce chapitre les méthodes de résolution d’un problème (M OILF P )
ont été présentées, dont la dernière servira comme support pour la résolution de notre pro-
blème principal.

47
Chapitre 4
Approche de résolution du problème MOIFLP

4.1 Introduction
La programmation est un ensemble d’outils et de technique permettant de résoudre
des problèmes mathématiques par ordinateurs, elle sert a trouver une solution optimale
de n’importe quel type de problème. Le processus de résoudre un problème mathématique
exige un grand nombre de calculs donc il est mieux de l’éxécuter par machine . Pour cela
on a choisit le logiciel LINGO qui est spécifié pour résoudre des problèmes d’optimisations
(linéaire,non linéaire,convexe ,non convexe,..etc). Il comporte un éventail de commandes
qui peuvent être appelées à tout moment.

4.2 Définition du problème

Dans cette partie, nous nous sommes particulièrement intéressés aux problèmes multi-
objectifs fractionnaire linéaire en nombre entier. L’appoche de résolution proposée consiste
à convertir le problème étudié en un problème mono-objectif en utilisant la méthode de
la somme pondérée. Dans cette étape, les poids relatifs sont attribués en fonction de l’im-
portance relative de la fonction objectif. Enfin, la solution obtenue est un ensemble non
dominé.

4.2.1 Problème fractionnaire multi-objectif

Considérons le problème(MOLIFP) :

ck x + α k

max Zk (x) = , ∀k = 1, p



dk x + β k

(M OLIF P ) 


s.c
x∈D


avec D l’ensemble des entiers relatifs

48
CHAPITRE 4. APPROCHE DE RÉSOLUTION DU PROBLÈME MOIFLP

4.2.2 Transformation du problème (MOLIFP) vers un problème

mono-objectif [30]
En utilisant la méthode de la somme pondérée pour résoudre le problème (MOLIFP).
Elle est à la fois la méthode la plus simple et la plus connue dans le domaine de prise
de décision multicritère. Comme son nom l’indique, la méthode de la somme pondérée
consiste à pondérer les différents critères du problème de décision multicritères avec des
nombres réels appelés poids wk , qui représentent l’importance de chaque critère dans le
processus de décision. Une fois l’importance des différents critères quantifiée, la méthode
choisit l’action qui minimise ou maximise la somme pondérée des critères. La méthode de
la somme pondérée consiste à maximiser une fonction U définie comme suit :
p
ωk Z k .
X
U (x) = (4.1)
k=1
p
X
où ω1 , ω2 ,..., ωk et les valeurs pondérées pour k = 1, 2, ..., p, de telle sorte que ωk = 1.
k=1

Enfin, le problème multiojectifs (M OLIF P ) est transformé vers un prolème mono-

objctifs de la manière suivante :

 Pp ck x + α k

 max Uk (x) = k=1 ωk
dk x + β k




(Pω ) s.c
x∈



 D
 Pp

k=1 ωk = 1


le problème obtenu est un problème quadratique fractionnaire (c’est à dire la fonction

objectif U(x)n’est pas linéaire)

théorème 4.2.1. [30] Si xb est une solution optimale du problème paramétrique (Pω ) pour
un certain ω > 0, alors xb est efficace pour le problème (M OILF P ).

4.3 Exemple numérique

Considérons le problème de programmation fractionnaire multi-objectif suivant :

49
CHAPITRE 4. APPROCHE DE RÉSOLUTION DU PROBLÈME MOIFLP

x1 + 3x2 + 32 x3

1
max Z (x) = 1


x + 34 x2 + 87 x3



2 1


3x1 + x2 + x3


max Z 2 (x) = 1



x + x2 + 29 x3


2 1



s.c





x1 + 2x2 − x3 ≤ 26 (4.2)



 −2x1 + 3x2 + x3 ≤ 32
x1 + x2 + x3 ≤ 37





x1 + 2x2 + x3 ≤ 30





−2x1 + 4x3 ≤ 25





xi ≥ 0, entiers i = 1, 2, 3


Après,la transformation du problème multiobjectifs vers le problème mono-objectifs,en

utilisant la méthode de somme pondérée on aura le problème suivant :

x1 + 3x2 + 23 x3

 3x1 + x2 + x3
max U (x) = w1 1 + w2 1


3 7
x + x2 + 29 x3




 x + 4 x2 + 8 x3
2 1 2 1
s.c





x1 + 2x2 − x3 ≤ 26




−2x1 + 3x2 + x3 ≤ 32 (4.3)

x1 + x2 + x3 ≤ 37








 x1 + 2x2 + x3 ≤ 30
−2x1 + 4x3 ≤ 25





xi ≥ 0, entiers i = 1, 2, 3



Nous utiliserons le logiciel lingo pour résolution des problèmes fractionnaire quadratique
en nombre entier

4.4 Présentation du logiciel

LINGO nous permet de formuler rapidement et facilement nos problèmes d’optimisation
linéaire, non-linéaire ou en nombres entiers. Grâce à ses outils de modélisation, les modéles
sont exprimés de manière transparente à l’aide de sommes et de variables indicées.
La méthode ne diffère guère de la méthode traditionnelle avec crayon et papier, mais les
modéles seront plus faciles à réutiliser et mettre à jour. Il possède quatre solveurs qu’il
utilise afin de résoudre les différents types de modèles :
• Solveur direct.
• Solveur linéaire
• Solveur non linéaire.
• Méthode de type séparation et évaluation.
de plus,LINGO est :
• Un moyen pour confirmer que l’optimum trouver est l’optimum global.

50
CHAPITRE 4. APPROCHE DE RÉSOLUTION DU PROBLÈME MOIFLP

• Possibilité pour résoudre les problèmes plus rapidement.

• Un moyen amélioré pour résoudre beaucoup de type de problèmes.
• Un moyen de décomposition si un modèle contient des sous-modèles.
LINGO est livré avec un jeu de solveurs pour l’optimisation linéaire, non-linéaire convexe
ou non convexe), quadratique, sous contraintes, et en nombre entier. Nous avons même pas
à nous préoccuper du choix du solveur : en effet, LINGO iterpréte lui-même nos formu-
lations et sélectionne automatiquement le solveur adapté à chaque problème. Un modèle
d’optimisation se compose de trois parties :
– La fonction objective : c’est la formule simple qui décrit exactement ce que le modèle
devrait optimiser.
– Les variables : ce sont les quantités qui peuvent être changés pour déterminer la
valeur optimale de la fonction objective.
– Les contraintes : ce sont les formules qui définissent les limites sur les valeurs des
variables.

Les fonctions utilisées dans un modèle de LINGO sont :

@F OR : utilisée pour produire des contraintes.
@SU M : calcul de la somme.
@M AX : recherche de maximum.
@M IN : recherche de minimum.

Type de variables dans LINGO :

Toutes les variables dans un modèle de LINGO sont considérées non négatives et conti-
nus, les fonctions variables d’un modèle de LINGO sont :
@GIN : toute valeur positive de nombre entiers.
@BIN : une valeur binaire (0 ou 1). @F REE : toute valeur positive ou négative réelle.
@BN D : toute valeur bornée par des limites indiquées.
LA forme générale pour la déclaration d’un variable x, en utilisant les fonctions variables
@GIN, @BIN, @F REE est : @f unction(x).
La fonction @BN D inclut les limites inférieure et supérieure des variables, sa forme géné-
rale est : @BN D (limite inférieure, x, limite supérieure).

4.4.1 Interface de logiciel :

Après,avoir entré le problème de programmation fractionnaire multiobjectifs,avec les
poids ω1 , ω2 tel que ω1 = 0.4, ω2 = 0.6 on aura la fenêtre suivante :

51
CHAPITRE 4. APPROCHE DE RÉSOLUTION DU PROBLÈME MOIFLP

Par conséquence, on obtient une solution non dominée, où x∗ = (x∗1 , x∗2 , x∗3 ) = (26, 0, 0)
avec U (x∗ ) = 4.4 et (Z 1 , Z 2 ) = (2, 6). Cette solution est une solution optimale de (4.3),avec
w1 = 0.4 et w2 = 0.6.

Cette fenêtre nous donne la valeur de l’optimum qui produisent la valeur optimale de
la fonction objectif.

52
CHAPITRE 4. APPROCHE DE RÉSOLUTION DU PROBLÈME MOIFLP

Le tableau(4.1) donne l’ensemble des solutions non dominées et les valeurs optimales cor-
respondantes de la fonction objectif. Ces résultats sont obtenus à partir du logiciel Lingo
en faisant varier les poids w1 et w2 . Les résultats obtenus peuvent donner une certaine
flexibilité au décideur quand au choix des poids de la fonction objectif.

Table 4.1 – Résultats de l’optimisation en faisant varier les poids w1 et w2

w1 w2 x1 x2 x3 U (x) (Z 1 , Z 2)
0 1 26 0 0 6 (2, 6)
0.1 0.9 26 0 0 5.6 (2, 6)
0.2 0.8 26 0 0 5.2 (2, 6)
0.3 0.7 26 0 0 4.8 (2, 6)
0.4 0.6 26 0 0 4.4 (2, 6)
0.5 0.5 26 0 0 4 (2, 6)
0.6 0.4 26 0 0 3.6 (2, 6)
0.7 0.3 0 10 0 3.1 (4, 1)
0.8 0.2 0 10 0 3.4 (3, 0)
0.9 0.1 0 10 0 3.7 (4, 1)
1 0 0 10 0 4 (4, 1)

4.5 Conclusion
Dans ce chapitre, Nous Nous sommes intéressées principalement sur l’approche de ré-
solution du problème d’optimisation fractionnaire multi-objectifsen en nombre entier. En
premier lieu, nous avons convertir le problème fractionnaire multiobjectifs vers un problème
mono-objectif. Ensuite nous avons présenté le logiciel lingo et les interfaces nécessaires pour
exécuté un problème fractionnaire quadratique. En dernier lieu, nous avons présenté un
exemple sur le logiciel lingo.

53
Conclusion générale

Les problèmes de programmation multiobjectifs sont de plus en plus étudiés car ils ont
un grand intérêt dans l’industrie, où plusieurs objectifs concurrents doivent être satisfaits.
Ils sont la plupart du temps NP-difficiles même si leur version mono-objectif ne l’est pas.
Contrairement aux problèmes d’optimisation mono-objectif, il existe généralement plu-
sieurs solutions Pareto optimales ou efficaces en optimisation multi-objectifs, c’est-à-dire
des solutions qu’on ne peut améliorer sur un objectif sans les détériorer sur un autre.Comme
il n’existe aucune solution meilleure en tout point qu’une autre, un compromis différent
selon les personnes doit être choisi. Le choix est donc subjectif, et il est indipensable de
proposer l’ensemble des choix possibles afin de ne pas exclure une possibilité.L’optimisation
multi-objectifs est donc avant tout un outil d’aide à la décision, et c’est une personne qui
prendra la décision finale.

Nous avons présenté dans ce mémoire les travaux de recherche sur les méthodes d’op-
timisation multi-objectifs fractionnaire linéaires.

Dans notre étude, nous nous sommes particulièrement intéressés aux problèmes de pro-
grammation multi-objectifs fractionnaire linéaires en nombres entiers pour lesquels relati-
vement peu de travaux ont été réalisés. Le noyau du thème de notre mémoire est princi-
palement focalisé sur l’optimisation linéaire multi-objectifs en nombres entiers et le travail
présenté s’articule autour de deux volets :

• Le premier volet consiste à rappeler la notion d’optimisation multi-objectifs fraction-

naire linéaire en nombre entier (MOILFP).
• Le deuxième volet consiste à résoudre le problème d’optimisation fractionnaire mul-
tiobjectifs en nombre entier en utilisant la méthode de somme pondérée.

54
Notation

(PLE) :problème linéaire en nombre entier.

(PFE) :problème linéaire fractionnaire en nombre entier.
(PLMO) :problème linéaire multiobjectifs.
(PLMOE) :problème linéaire multiobjectifs en nombre entier.
(PLFMO) :problème linéaire fractionnaire multiobjectifs.
(PLFMOE) :problème linéaire fractionnaire multiobjectifs en nombre entier.
(PLIFMOE) :problème linéaire fractionnaire integer multiobjectifs en nombre entier.
D :l’ensemble des entiers relatifs.
S :l’ensemble des solutions réalisable.
SES :solution efficace supportée.
SENS :solution efficace non supportée.
x∗ :la solution optimale

55
Bibliographie

[1] M.Moulaï. Thèse de doctorat : Optimisation Multicritere Fractionnaire Linéaire en

Nombres entiers 2002.
[2] O.Zerdani. Thèse de doctorat : L’optimisation non linèaire multi objectif 2013,.
[3] E.U. Choo. Proper effciency and the linear fractional vector maximum problem.
Operations Research, 32(1) :216–220, 1984.
[4] V. Pareto. The new theories of economics. Journal of political economy,
5(4) :485–502, 1897.
[5] V.Chankong and Y.Y.Haimes, "Multiobjective Decision Making : Theory and Me-
thodology", North Holland Series in System Science and Engeneering, p.406, 1983.
[6] A.Berro, "Optimisation Multi-objectifs et Stratégie d’Evolution en Environnement
Dynamique", Thèse de doctorat, université des sciences sociale de Toulouse, 2001.
[7] Y.Collette, P.Siarry, "Optimisation Multi-objectifs", édition Eyrolles 61, 2002.
[8] Y.Y.Haimes, "Modeling and Control of the Pollution of Water Resources Systems
via Multilevel Approch", New-York, 1971.
[9] L.ASLI . Approche hybride pour les problèmes d’optimisation combinatoire multiob-
jectif : cas des problèmes de type sac-à-dos 2010.
[10] Y.Y.Haimes, L.S.Lasdon and D.A.Wismer, "Formulation of the Problems of
Integrated System Identification and System Optimization", 1986.
[11] A. Charnes and W.W. Cooper. Management models and industrial applications
of linear programming. Management science,
[12] F.Kebaili, H.Mouloud, "Optimisation de le Gestion de Portefeuille d’Actifs Finan-
ciers, mémoire de fin d’étude", université de USTHB, 2008.
[13] E.Zitzler, L. Thiele : Multiobjective evolutionary algorithms : A comparative case
study and the strength pareto approach. IEEE Transactions on Evolutionary Compu-
tation 3(4), 257–271 (1999)
[14] W.Dinkelbach ,"On nonlinear fractional programming ",Management
Science,1967,vol,13,pp.492-498

56
BIBLIOGRAPHIE

[15] V.Chankong and Y.Y.Haimes, "Multiobjective Decision Making : Theory and Me-
thodology", North Holland Series in System Science and Engeneering, p.406, 1983.
[16] A.M. Geoffrion. Proper effciency and the theory of vector maximization. Journal of
mathematical analysis and applications, 22(3) :618–630, 1968.
[17] J.P. Costa. Computing non-dominated solutions in molfp. European Journal of Ope-
rational Research, 181(3) :1464–1475, 2007.
[18] M.E.A. Chergui and M. Moulaï. An exact method for a discrete multiobjective
linear fractional optimization. Journal of Applied Mathematics et Decision Sciences,
2008(1), 2008.
[19] M.Abbac and M.Moulai Integer linear fractional programming with multiple ob-
jective. Journal of the Italian Operations Research Society, 32(103-104) :15–38, 2002.
[20] M.E.A. Chergui and M. Moulaï. An exact method for a discrete multiobjective
linear fractional optimization. Journal of Applied Mathematics and Decision Sciences,
2008(1), 2008.
[21] F.Y.Edgeworth, "Mathematical Physics", Keagan.P, Londres, Angleterre, 1881.
[22] Pareto Vilfredo,"cours d’économie politique" J.R. Isbell and W.H. Marlow.
Attrition games. Naval Research Logistics Quarterly„Vol.1 et 2, Rouge Lausanne, 1896.
[23] R.E. Steuer. Multiple criteria optimization. Theory, computation and applications,
1986.
[24] A. Cambini and L. Martein. A modified version of martos’ algorithm. Methods of
Operation Research, 53 :33–44, 1986.
[25] 3(1-2) :71–94, 1956.
[26] A. Nagih and G. Plateau. Problèmes fractionnaires : tour d’horizon sur les ap-
plications et méthodes de résolution. RAIRO-Operations Research-Recherche Opéra-
tionnelle, 33(4) :383–419, 1999.
[27] R.E.Gomory, "Outline of an Algorithm for Integer Solutions to Linear Programs",
Bulletin of the AMS 64, p.275-278, 1958.
[28] B. Bereanu. Decision regions and minimum risk solutions in linear programming.
In colloquium on applications of mathematics to economics, Budapest, pages 37–42,
1963.
[29] A.Charnes,W.cooper.programming with linear fractional functionals,naval
ref,logist.quart.9,181-186,1962
[30] A.Merakeb.optimisation multicritères en contrôle optimal :application au véhicule
électrique, thèse de doctorat,université de Tizi-ouzou,2011
[31] K.Miettinen, "non linear multiobjective Optimization", Kluwer, Boston, 1999.

57
Résumé

La résolution des problèmes multi-objectifs, particulièrement les problèmes d’optimisa-

tion fractionnaire multi-objectifs se fait ou bien dans l’espace des critères ou dans l’espaces
des décisions. La notion d’optimalité disparaît pour les problèmes de ce type au profit
de la notion d’efficacité. Une solution efficace est une solution à partir de laquelle, il est
impossible d’augmenter la valeur d’un critère sans diminuer celle d’au moins un autre. La
solution choisie par un décideur sera un compromis dépendant d’un grand nombre de pa-
ramètres variant d’un décideur à un autre et donc difficile à modéliser. Notre objectif vise
la résolution des problèmes multi-objectifs fractionnaires en présence de variables discrètes
et l’approche de résolution est basée sur la méthode de la somme pondérée.

Abstract
The resolution of multi-objective problems, particularly multi-objective fractional opti-
mization problems, is done either in the criterion space or in the decision space. The notion
of optimality disappears for problems of this type in favor of the notion of efficiency. An
effective solution is a solution from which it is impossible to increase the value of one
criterion without decreasing that of at least one other. The solution chosen by a decision
maker will be a compromise depending on a large number of parameters varying from one
decision maker to another and therefore difficult to model. Our goal is to solve fractional
multi-objective problems in the presence of discrete variables and the resolution approach
is based on the weighted sum method.

58