N0 d’ordre : 22 /2008-M/MT

RÈPUBLIQUE ALGÉRIENNE DÉMOCRATIQUE ET POPULAIRE

MINISTÈRE DE L’ENSEIGNEMENT SUPÉRIEUR
.
ET DE LA
RECHERCHE SCIENTIFIQUE
UNIVERSITÉ DES SCIENCES ET DE LA TECHNOLOGIE HOUARI
BOUMEDIENNE
FACULTÉ DES MATHÉMATIQUES

Mémoire
présenté pour l’obtention du diplôme de Magister
En : MATHEMATIQUES
Spécialité : Recherche Opérationnelle (Mathématiques de Gestion)
Par

RAGGAS Nassima
Thème

OPTIMISATION MULTICRITÈRE APPLIQUÉE

AU PROBLÈME D’AFFECTATION

Soutenu publiquement le 12/03/2008, devant le jury composé de :

Mr. A. BERRACHEDI Professeur U.S.T.H.B Président.
Mr. D. CHAABANE Maître de Conférences U.S.T.H.B. Directeur de mémoire.
Mr. M. MOULAÏ Maître de Conférences U.S.T.H.B. Examinateur.
Mr. M.E-A. CHERGUI Chargé de Recherche U.S.T.H.B. Examinateur.
Table des matières

Introduction générale 4

1 Optimisation linéaire multi-objectifs 7

1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2 Programmation linéaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2.1 Généralités . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2.2 Formulation des problèmes de Programmation linéaire . . . . . . . . 9
1.2.3 Notions fondamentales [12] . . . . . . . . . . . . . . . . . . . . . . . . 10
1.2.4 Résolution d’un problème linéaire . . . . . . . . . . . . . . . . . . . . 12
1.2.5 Méthode du Simplexe . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.2.6 Notion de dualité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.3 Programmation Linéaire multi-objectifs . . . . . . . . . . . . . . . . . . . . . 17
1.3.1 Problèmes de programmation mathématique multi-objectifs . . . . . 18
1.3.2 Notions de dominance et d’e¢ cacité . . . . . . . . . . . . . . . . . . . 19
1.3.3 Caractérisation des solutions e¢ caces continues . . . . . . . . . . . . 21
1.3.4 Points particuliers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
1.3.5 Résolution d’un problème multicritère linéaire. . . . . . . . . . . . . . 22

2 Optimisation multi-objectifs en nombres entiers 26

2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.2 Programmation unicritère en nombres entiers . . . . . . . . . . . . . . . . . 27
2.2.1 Problèmes de programmation linéaire unicritère en nombres entiers . 27
2.2.2 Complexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

1
 TABLE DES MATIÈRES

2.2.3 Optimisation combinatoire . . . . . . . . . . . . . . . . . . . . . . . . 29

2.2.4 Problème d’a¤ectation ([13], [16]) . . . . . . . . . . . . . . . . . . . . 30
2.2.5 Solution de problème d’a¤ectation unicritère . . . . . . . . . . . . . . 31
2.2.6 Méthodes exactes de résolution . . . . . . . . . . . . . . . . . . . . . 35
2.2.7 Procédure par séparation et évaluation (Branch and Bound) . . . . . 37
2.2.8 Les coupes de Gomory [13] . . . . . . . . . . . . . . . . . . . . . . . . 37
2.3 Programmation linéaire multicritère en nombres entiers . . . . . . . . . . . . 40
2.3.1 Problèmes de programmation mathématique multicritère en nombres
entiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
2.3.2 Solutions supportées / non supportées . . . . . . . . . . . . . . . . . 40
2.3.3 Revue des méthodes exactes existantes (voir [4], [6], [10]) . . . . . . . 41
2.3.4 Abécédaire de méthodes d’optimisation multi-objectifs [1] . . . . . . . 45
2.3.5 Problèmes à variables binaires [1] . . . . . . . . . . . . . . . . . . . . 50
2.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

3 Problème Bicritère d’a¤ectation 55

3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
3.2 Problème multicritère d’a¤ectation . . . . . . . . . . . . . . . . . . . . . . . 55
3.2.1 Formulation du Problème. . . . . . . . . . . . . . . . . . . . . . . . . 55
3.2.2 Positionnement du problème . . . . . . . . . . . . . . . . . . . . . . . 56
3.2.3 Importance du problème . . . . . . . . . . . . . . . . . . . . . . . . . 57
3.3 Solution du problème bicritère d’a¤ectation . . . . . . . . . . . . . . . . . . 57
3.3.1 La méthode de Malhotra et al ([9]). . . . . . . . . . . . . . . . . . . . 57
3.3.2 Exemple illustratif de Malhotra et al [9] . . . . . . . . . . . . . . . . 61
3.3.3 Adaptation de la méthode hongroise [19] . . . . . . . . . . . . . . . . 62
3.3.4 Application du principe de Malhotra et al [9] . . . . . . . . . . . . . . 72
3.3.5 Contre exemple [19] . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
3.3.6 Alternative proposée par Ulungu [19] . . . . . . . . . . . . . . . . . . 74
3.3.7 Méthode de deux phases [19], [21] . . . . . . . . . . . . . . . . . . . . 90

2
 TABLE DES MATIÈRES

4 Conclusion générale et perspectives 96

3
Dédicases

F A mes très chers parents, pour les sacri…ces qu’ils ont fait pour nous.

F A la mémoire de mes grands parents Slimane et Djilali.

F A la mémoire de ma grand mère Yasmine.

F A la mémoire de mon oncle Mohamed, puisse Dieu le tout puissant leurs accorder sa
Miséricorde et les accueillir dans son vaste paradis.

4
Remerciements

F Je remercie d’abord le BON DIEU le tout puissant de m’avoir accordé la santé; et le

courage d’arriver au terme de ce travail.

F Je tient à exprimer mes vifs remerciements à mon promoteur Monsieur CHAABANE

Djamel qui a été pour moi un guide bien quali…é, ainsi que pour ses précieux conseils
et ses orientations au long de ce travail de mémoire.

F Je remercie également mon enseignant Monsieur le Professeur BERRACHEDI Abdel-

ha…d qui m’a fait l’honneur d’accepter d’être président du jury de mon mémoire.

F C’est un grand honneur pour moi que d’avoir Messieurs MOULAÏ Mustapha, CHERGUI
Mohamed el amine comme membres de mon jury; Je les remercie ici très vivement.

F En…n j’adresse une pensée toute particulière à ma famille –mes chers parents, mes frères
Réda, Sid Ali, Lamine et Salim, mes sœurs Amina et Imène, ma tente Saïda – pour
leur présence et leurs encouragements. Merci à madame Nadia pour son aide précieuse
et aux amis pour tous les bons moments passés ensemble. Merci à tous et à toutes qui
ont contribué de près ou de loin à la réalisation de ce travail.

5
Introduction générale

L’objet de la recherche opérationnelle est l’amélioration du fonctionnement des entreprises et

des organismes publics par l’application de l’approche scienti…que. Reposant sur l’utilisation
de méthodes scienti…ques et de techniques spécialisées, elle permet d’obtenir une évalu-
ation quantitative des politiques, stratégies et actions possibles dans le cours des opéra-
tions d’une organisation ou d’un système. Elle est apparue en tant que telle en Grande-
Bretagne durant la seconde guerre mondiale, lorsqu’on décida d’employer des méthodes
scienti…ques pour étudier divers aspects des opérations militaires (d’ou son nom). Depuis
lors, la recherche opérationnelle est devenue un élément important du processus de prise
de décision dans de nombreux contextes commerciaux, industriels et gouvernementaux, car
elle permet d’appréhender de façon systématique la complexité toujours grandissante des
problèmes de gestion auxquels sont confrontés les décideurs.
De nombreux secteurs (télécommunications, transport, etc...) sont concernés par des
problèmes complexes de grandes dimensions et multi-critères (qualité de service, etc...) met-
tant en jeu des coûts très importants et pour lesquels les décisions doivent être prises de
façon optimale. Les problèmes d’optimisation rencontrès en pratique sont rarement mono-
critère. Il y a généralement plusieurs critères contradictoires à satisfaire simultanément.
L’optimisation multi-critères s’intéresse à la résolution de ce type de problèmes, elle pos-
sède ses racines au 19ième siècle dans les travaux en économie de Edgeworth et Pareto [6].
Elle a ainsi été initialement utilisée en économie et dans les sciences du management, puis
graduellement dans les sciences pour l’ingénieur.
Dans les 30 dernières années, la plupart des travaux ont portés sur la programmation
multi-objectifs linéaire en variables continues. Les raisons principales de cet intérêt sont

6
 Introduction générale

d’une part le développement de la programmation linéaire mono-objectif en recherche opéra-

tionnelle, et la facilité relative de traiter de tels problèmes, et d’autre part l’abondance des
cas pratiques qui peuvent être formulés sous forme linéaire. Ainsi, un certain nombre de
logiciels ont vu le jour depuis le développement de la méthode du simplexe multi-objectifs
(Zeleny, 1982 [22]). Le livre de Steuer [15] ainsi que celui de Ehrgott o¤re une solide introduc-
tion aux problèmes d’optimisation multicritère. Concernant l’optimisation multi-objectifs
linéaire en variables discrètes et l’optimisation combinatoire multi-objectifs, peu de travaux
ont été réalisés avant les années 80-90. Mais depuis, un fort intérêt a été montré pour ce
genre de problèmes [20], [7].
Dans la littérature, une attention particulière a portés sur les problèmes à deux critères
en utilisant les méthodes exactes telles que le "branch and bound" (Sen et al, 1988 ),
l’algorithme A* (Stewart and White, 1991).
Dans le cadre de ce travail, nous nous somme intéressée à l’étude du problème multi-
critères d’a¤ectation et spécialement à la détermination des solutions e¢ caces dans le cas
de deux fonctions objectifs d’où l’appellation problème bicritère d’a¤ectation ( Bi-critaria
Assignment Problem (BAP)). Notons que Charnes et al [20] ont été les premiers a portés
attention sur l’extension multi-objectifs du problème d’a¤ectation et depuis plusieurs méth-
odes ont été établie [18].
Ce mémoire comporte trois chapitres :
Le premier chapitre fournit les éléments de la recherche opérationnelle nécessaires à la
compréhension de la suite du mémoire, tels que la notion de base, de dualité...etc. De
plus, les caractéristiques principales des problèmes multi-objectifs et de leurs méthodes de
résolution sont indiquées.
Le deuxième chapitre est une introduction aux problèmes de la programmation linéaire en
nombres entiers. Nous présenterons la structure générale des problèmes (ILP) et (MOILP)
et les principales méthodes de résolution existantes dans la littérature, en précisant où réside
la di¢ culté de la résolution de ce type de problèmes.
Le troisième chapitre est consacré au problème bicritère d’a¤ectation, nous formulerons
le problème et nous exposerons quelques méthodes existantes dans la littérature notamment

7
 Introduction générale

celles établie par Malhotra et al [9], et par Ulungu [19], nous présenterons également des
exemples illustratifs pour chaque méthode.
En…n, nous terminerons ce travail par une conclusion générale et perspectives.

8
Chapitre 1

Optimisation linéaire multi-objectifs

1.1 Introduction
La programmation linéaire, une des branches de la recherche opérationnelle, consiste à
établir la théorie et les méthodes de résolution des problèmes d’optimisation sur des ensem-
bles dé…nies par des contraintes (égalités ou inégalités) qui consiste soit à minimiser les coûts
ou les dégâts soit à maximiser les gains ou les béné…ces. Dans ce chapitre, nous rappelons
les principaux résultats de la programmation linéaire, et les principales méthodes utilisées
pour résoudre ces problèmes de manière exacte, ainsi que les notions de bases nécessaires
pour l’étude de notre problème.

1.2 Programmation linéaire

1.2.1 Généralités

Notions d’algèbre linéaire

Un ensemble de vecteurs V = fvi =vi 2 Rn ; i = 1; 2; :::; ng est linéairement indépen-

P
k
n
dant si et seulement si i vi = 0 2 R ) 1 = 2 = ::: = n = 0 2 R: Sinon
i=1
l’ensemble des vecteurs V est linéairement dépendant.

La dimension de l’ensemble V est le nombre maximum de vecteurs linéairement in-

9
 1.2. Programmation linéaire

dépendants.

Une matrice est dite totalement unimodulaire si et seulement si, tous les déterminants
de ses sous-matrices carrées soient égaux à 1, 0 ou 1.

Voisinage

Un voisinage V est une fonction V : C ! P (C) qui associe pour chaque x 2 C un

sous-ensemble V (x) de C des voisins de x

Ensembles convexes et points extrêmes

Soient v1 ; v2 ; :::; vn des éléments dans un espace vectoriel. On appelle combinaison

linéaire convexe de ces vecteurs le vecteur :

V = 1 v1 ; 2 v2 ; :::; n vn où les i ; (i = 1; 2; :::; n) sont des scalaires tels que : i 0

P
n
et i = 1:
i=1

Un ensemble S Rn est convexe si et seulement si pour tous x1 ; x2 2 S, le point

( x1 + (1 ) x2 ) 2 S pour tout 2 [0; 1]. En d’autres termes, un ensemble est dit
convexe si pour toutes paires de points (x; y) de cet ensemble, le segment [xy] qui les
joints est entièrement inclu dans cet ensemble.

Soit S Rn , un point x 2 S est un point extrême (sommet) de S si et seulement s’il

n’existe pas deux points x1 ; x2 2 S, x1 6= x2 , tel que x = x1 + (1 ) x2 , 2 ]0; 1[. Ou
encore, un point x 2 S est dé…ni comme un point extrême s’il ne peut pas être exprimé
comme une combinaison linéaire convexe des points de S. Un ensemble convexe peut avoir
un nombre …ni de points extrêmes, en avoir un nombre in…ni, ou ne pas avoir de points
extrêmes du tout.

L’ensemble constitué par les combinaisons linéaires convexes d’un ensemble …ni de
points extrêmes de S est un polyèdre convexe. Un polyèdre convexe est un ensemble
convexe borné. Un polyèdre convexe a un nombre …ni de points extrêmes.

10
 1.2. Programmation linéaire

Soient x1 ; x2 ; :::; xp ; p points de Rn : On appelle enveloppe convexe de ces points l’ensemble

Pn P n
x 2 Rn = i xi ; 0 i 18i; i = 1 :
i=1 i=1

Face

Dé…nition 1.2.1 Soit S Rn convexe. Un sous ensemble F de S est dit une face de
dimension p si la plus petite variété linéaire L véri…e L \ S = F:

Les Cônes

Dé…nition 1.2.2 Soit v 2 V Rn ; V 6= ?; alors V est un cône si et seulement si v 2 V

pour tout scalaire 0:

1.2.2 Formulation des problèmes de Programmation linéaire

On dé…nit un problème linéaire en variables continues comme un problème d’optimisation

d’une fonction linéaire (appelée “fonction objectif”) en variables (dites “de décision”) satis-
faisant un ensemble d’équations et/ou d’inéquations linéaires (dites “contraintes”).
D’une façon générale, un programme mathématique est un problème d’optimisation dans
Rn de la forme :

8
>
> M inimiser (ou M aximiser) f (x)
>
>
>
>
< sous les conditions :
(P )
>
> gi (x) 0; i = 1; 2; :::; n
>
>
>
>
: x 2 S et S Rn

Tels que

- La fonction f (x) est appelée fonction objectif ou critère.

- L’ensembles des conditions gi (x) 0, x 2 Rn sont les contraintes (égalités ou inégalités)

du problème.

11
 1.2. Programmation linéaire

- Le vecteur x 2 Rn a pour composantes (x1 ; x2;:::; xn )T qui sont les inconnues du problème;
appeler variables de décision.

- S et la région réalisable (possible) du problème.

Si les fonctions f et gi sont linéaires en x, on obtient un problème de programmation

linéaire (noté (P L)) généralement écrit sous la forme suivante :
8
< min ou (max) Z = cx
(P L)
: x2S

avec S = fx 2 Rn : Ax b; x 0g ; A (matrice des contraintes); c; x et b sont des

matrices de dimensions respectives (m n) ; (1 n) ; (n 1) et (m 1) ; n est le nombre
de variables, m est le nombre de contraintes du système, et Z est la fonction objectif.

1.2.3 Notions fondamentales [12]

Base, solution de base.

Dé…nition 1.2.3 Un point x 2 S est appelé solution réalisable ou admissible ou possible:

Toute combinaison linéaire convexe de deux solutions possibles quelconques est aussi une
solution possible.

L’ensemble des solutions possibles ou admissibles est un polyèdre convexe.

Dé…nition 1.2.4 Une solution de (P L) est appelée solution optimale.

Optimum global On appelle optimum global (solution optimale) de (P L) une solution

qui minimise Z sur l’ensemble de toute les solutions.

Optimum local On dit qu’un vecteur x0 est un optimum local de (P L) si et seulement

s’il existe un voisinage v(x0 ) de x0 tel que x0 soit un optimum global du problème

12
 1.2. Programmation linéaire

8
>
> min Z = Cx
>
>
>
>
< s:c
(P L)
>
> x 2 S \ v(x0 )
>
>
>
>
: S Rn

Dé…nition 1.2.5 On appelle base de (P L) un ensemble B de m indices pris dans f1; 2; :::; ng
tel que la sous- matrice AB formée des m colonnes correspondantes à A soit carrée non sin-
gulière (inversible).

À une base B on associée l’ensemble d’indices complémentaire N = f1; 2; :::; ng n B:

Après une permutation de colonnes on peut écrire :

A = A B AN

On désigne par I l’ensemble des indices de colonnes correspondantes à la base et J

l’ensemble des indices de colonnes hors base.
Soit B une base de (P L) :

- AB est dite matrice de base associe à B:

- Si x 2 Rn , les composantes xi avec i 2 B sont alors dites de base et notées xB ; celles avec
= B sont dites hors base et notées xN , donc à tout élément x 2 Rn on associée la
i2
partition (xB ; xN ) :
8
< x = AB 1
b
B
Dé…nition 1.2.6 La solution est appelée solution de base associée à B.
: x =0
N

Une base est dite réalisable si la solution de base associée véri…e xB 0.

Une solution de base associée à une base réalisable est dite solution de base réalisable.

Remarque 1.2.1 Tout programme linéaire peut s’écrire AB xB + AN xN = b: Où AB est la

sous matrice des colonnes de base, AN la sous matrice des colonnes hors base, xB sont les
variables de base, xN les variables hors base.

13
 1.2. Programmation linéaire

Remarque 1.2.2 À une base correspond une et une seule solution de base; par contre, il
peut exister plusieurs bases pour lesquelles une solution donnée est solution de base associée.
1
On dit alors qu’il y a dégénérescence c’est à dire xB = AB b; a des composantes nulles .

1.2.4 Résolution d’un problème linéaire

Bien évidemment, une fois le problème modélisé, se pose la question de la détermination de

sa (ou ses) solution(s) optimale(s) et donc de sa résolution. Nous parlerons de résolution
exacte d’un problème lorsque l’algorithme utilisé permettra de trouver au moins une solution
optimale et de démontrer son optimalité.
Pour les problèmes en variables continues, le nombre de solutions admissibles est in…ni
lorsque leur domaine n’est pas vide. Le domaine des solutions admissibles (ou espace de
recherche) d’un programme linéaire en variables continues est soit un polytope convexe (cas
d’un domaine non borné), soit un polyèdre convexe (cas d’un domaine borné). De plus, si
le domaine est borné et non vide, la solution optimale est un sommet du domaine (ou une
face s’il y a plusieurs solutions optimales).
Ainsi, l’algorithme du simplexe permet d’obtenir la solution optimale d’un problème
en parcourant la fermeture convexe de l’espace de recherche et ce en passant de sommet
en sommet. Malgré une complexité théorique exponentielle, la méthode du simplexe reste
largement utilisée dans la pratique.

1.2.5 Méthode du Simplexe

La méthode du simplexe a été développée par [Link] (1947) (voir [3]). C’est une
procédure itérative qui à travers des opérations répétées permet d’atteindre progressivement
la solution optimale.

Forme standard d’un programme linéaire

On dit qu’un programme linéaire est mis sous forme standard si toutes les contraintes sont
des égalités.

14
 1.2. Programmation linéaire

On peut toujours mettre un programme linéaire quelconque sous forme standard en

introduisant des variables supplémentaires appelées variables d’écarts.

Forme canonique d’un programme linéaire

On dit qu’un programme linéaire est mis sous forme canonique relativement à la base des
variables (xi1 ; xi2 ; :::; xim ) si :

1. Z est exprimé en fonction des variables hors base (cB = 0) :

2. Les colonnes de la matrice des contraintes correspondantes aux variables de base AB

forment une matrice unité à une permutation près.

Tableau simplexe

L’intérêt du tableau simplexe est de rassembler de façon condensée tous les éléments néces-
saires au déroulement de l’algorithme du simplexe.
Considérons le programme linéaire (écrit sous forme standard) suivant :
8
>
> min Z = c1 x1 + c2 x2 + ::: + cn xn
>
>
>
>
< s:c
(P L)
>
> ai1 x1 + ai2 x2 + ::: + ain xn = bi ; i = 1; 2; :::; m
>
>
>
>
: (x ; x ; :::; x ) 0
1 2 n

On peut le représenter par le tableau suivant, appelé tableau simplexe :

x1 x2 ::: xn b
a11 a12 a1n b1
a21 a22 a2n b2
... ... ... ... ...
am1 am2 ... amn bm
c1 c2 ... cn Z (x)

Tableau simplexe

15
 1.2. Programmation linéaire

On obtient la forme canonique relative à la base des variables (x1 ; :::; xm )

1 0
1
fN = AB
A
1
AN eb = AB 1
b

0 1
1
0 0 0 cf
N = cN cB B 1 N Z(x) c B AB b

Algorithme de simplexe.

Le principe de l’algorithme consiste à e¤ectuer une série d’opération de pivotage sur la

matrice des coe¢ cients de manière à écrire le programme linéaire sous forme canonique par
rapport aux bases courantes.
La mise en œuvre de la méthode simplexe peut être divisée en trois (3) étapes.

Étape1(Initialisation) Transformer le programme linéaire sous la forme standard en y

introduisant les variables d’écarts, et en suite sous forme canonique par rapport à une base
B de façon à avoir une solution de base admissible.

Étape2 Établir le premier tableau du simplexe.

Étape3 Procéder à une série d’itérations.

3.1 Déterminer la colonne pivot.

3.1.1 Si les di¤érentes coe¢ cients canonique cf

N 0: Terminer, la solution de base admis-
sible actuelle est optimale.
n o
3.1.2 Choisir s tel que (f cN )j j (f
cN )s = min (f cN )j < 0 :
j2J

3.2 Déterminer la ligne pivot.

n s o
Soit L = l e
A >0 .
l

16
 1.2. Programmation linéaire

3.2.1 Si L = ?: Terminer, (P L) n’admet pas de solution optimale.

s h si
3.2.2 Sinon, soit K = k eb e
= A = min eb = A
e ;choisir r 2 K:
k k l2L l l

3.3 Établir le nouveau tableau simplexe.

s
e , et établir le nouveau tableau simplexe tel que :
3.3.1 Pivoter sur l’élément A
r

l’ensemble des indices de la nouvelle base J = J [ fsg n frg :

arj
ars = 1; arj = ars
avec j 6= s
arj
aij = aij ais ars avec j 6= s; i 6= r
ebi := ebi ais ebr =ars i 6= r; cf f
N = c N cN )s (arj =ars ) :Si la solution est non optimale,
(f
répéter l’étape 3. Sinon donner la solution optimale.
Pour résoudre un programme linéaire avec une fonction objectif à maximiser, il su¢ t de
changer, dans l’algorithme :
n o
Trouver s tel que (f cN )j j (f
cN )s = min (f cN )j < 0
j2J

Par
n o
Trouver s tel que(f cN )j j (f
cN )s = max (f cN )j > 0
j2J

Et

le critère d’arrêt : de cf
N 0 en cf
N 0:

Finitude de l’algorithme du simplexe.

Théorème 1.2.1 Si à chaque base rencontrée dans la résolution de (P L) la solution de base

est non dégénérée l’algorithme se termine en un nombre …ni d’itérations.

1.2.6 Notion de dualité

Les problèmes de la programmation linéaire existent toujours sous forme de paires, car il est
possible de dériver d’un programme linéaire donné son programme dual, selon des relations

17
 1.2. Programmation linéaire

bien dé…nies. Le programme original est appelé programme primal (P ) et le programme

obtenu dual (D). Ainsi, est associé à chaque problème de minimisation, un problème de
maximisation et inversement.
La notion de dualité est cruciale pour di¤érentes raisons, dans certains cas, résoudre
le programme dual s’avère être plus facile que de solutionner le programme primal. Cette
alternative permet une économie appréciable de temps de calcul.
Considérons le problème linéaire suivant :
8
>
> CX = Z (M in)
>
<
(P ) AX b
>
>
>
: x 0

Ecrit sous forme canonique

Dé…nition 1.2.7 On appelle dual8de programme linéaire (P ), le programme linéaire (D)

>
> Y b = W (M ax)
>
<
écrit sous la forme suivante : (D) Y A C
>
>
>
: Y 0

Le programme dual (D) est obtenu du programme primal (P ) on opérant comme suit:

a). Il y’a autant de variables duales Y = (y1 ; y2 ; :::; ym ) que de contraintes dans le pro-
gramme primal.

b). Les coe¢ cients du second membre b = (b1 ; b2 :::; bm )T de (P ) …gurent dans la fonction
objectif du (D) comme coe¢ cients.

c). Les coe¢ cients de la fonction objectif du (P ) deviennent les coe¢ cients du second
membre du programme dual (D).

d). La matrice transposée des coe¢ cients des contraintes de (P ) devient la matrice des
coe¢ cients des contraintes de (D).

e). Lorsque, dans le programme primal la fonction objectif est de minimiser, dans le pro-
gramme dual il s’agit de maximiser.

18
 1.3. Programmation Linéaire multi-objectifs

f). En…n, pour déterminer le sens des contraintes ( ; ; =), il faut se référer au diagramme
de la dualité dans le tableau suivant :

Primal (dual) Dual (primal)

Fonction objectif (minimisation) Fonction objectif (maximisation)

0
ieme contrainte = ieme variable quelconque( 0)
0

0
j eme variable quelconque( 0) j eme contrainte =
0

Si (D) est le dual de (P ): (P ) sera dit primal de (D):

Relations entre les valeurs de fonctions objectifs des deux problèmes duaux

Soit (P ) un programme linéaire écrit sous forme canonique et soit (D) son dual.

1. Si (x; y) constitue un couple de solutions réalisables de (P; D) alors Cx yb:

2. Si (x; y) constitue un couple de solutions réalisables de (P; D) et si de plus Cx = yb

alors (x; y) constitue un couple de solutions optimales pour (P; D) :

1.3 Programmation Linéaire multi-objectifs

Les problèmes d’optimisation sont généralement optimisés en ne considérant qu’un seul ob-
jectif, alors que plusieurs critères contradictoires existent. L’optimisation multi-objectifs
s’intéresse à la résolution de ce type de problèmes. Elle cherche à optimiser (maximiser
ou minimiser) plusieurs composants d’un vecteur de fonctions coûts. Contrairement à
l’optimisation unicritère, la solution d’un problème multicritère n’est pas une solution unique,
mais un ensemble de solutions, connu comme l’ensemble des solutions Pareto optimales et
c’est au décideur de choisir une parmi elles, selon l’ordre de préférences des critères, et

19
 1.3. Programmation Linéaire multi-objectifs

celle qui convient le mieux à son problème. Toute solution de cet ensemble est optimale
dans le sens qu’aucune amélioration ne peut être faite sur un composant du vecteur sans
dégradation d’au moins un autre composant du vecteur.

1.3.1 Problèmes de programmation mathématique multi-objectifs

Nous dé…nissons un problème multi-objectifs (noté par (M O)) comme un problème de dé-
cision qui consiste à optimiser (maximiser ou minimiser) simultanément p (p 2) fonctions
objectifs notées fk , k = 1; :::; p, sur un ensemble d’actions S:
Ce problème peut être formulé mathématiquement comme suit :
8
< “opt”ff (x) ; f (x); :::; f (x) g
1 2 p
(M O)
: x2S
où S = fx 2 Rn jgj (x) 0 ; j = 1; 2; :::; mg et ffk gk=1;2;:::;p et gj sont des fonctions à
valeurs réelles.
Le symbole “ ” signi…e qu’il n’est généralement pas possible de trouver dans S une
action qui optimise simultanément les p objectifs.

Dé…nition 1.3.1 L’espace Rn dans lequel se situe l’ensemble des actions S (S Rn ) est
appelé espace des décisions.

Si les objectifs fp et les fonctions gj sont linéaires en x, on obtient un problème de

programmation linéaire multicritère écrit sous la forme suivante :

8
< “ min ”z = ck x k = 1; 2; :::; p
k
(M OLP )
: x2S
avec S = fx 2 Rn : Ax b; x 0g ; A; ck ; x et b sont des matrices des dimensions
respectives (m n) ; (1 n) ; (n 1) et (m 1) ; où n est le nombre de variables, m est le
nombre de contraintes du système, et k est le nombre de fonctions objectifs.

20
 1.3. Programmation Linéaire multi-objectifs

1.3.2 Notions de dominance et d’e¢ cacité

Dominance

Dé…nition 1.3.2 Soient deux vecteurs critères Z1 ; Z2 2 Rk . On dit que Z1 domine Z2

si et seulement si zk1 zk2 pour tout k 2 f1; :::; pg et zk1 < zk2 pour au moins un indice
k 2 f1; :::; pg.

Autrement dit, Z1 est au moins aussi bon que Z2 sur tous les critères, et meilleur que
lui sur au moins un critère.

Dé…nition 1.3.3 Soit x 2 S et C le cône semi-positive généré par les gradients des p
fonctions objectifs où :

C = fy 2 Rn =Cy 0; Cy 6= 0g [ f0 de Rn g

L’ensemble de dominance sur x est donné par Dx^ = fxg C . L’ensemble de dominance
contient tous les points dont les vecteurs critères dominent le vecteur critère de x 2 S: Une
autre façon de décrire l’ensemble de dominance est Dx^ = fx 2 Rn =x = x + y; Cy 0; Cy 6= 0g.

Remarque 1.3.1 L’ensemble addition de deux ensembles X et Y dans Rn (noté X Y ),

est donné par : X Y = fz 2 Rn = z = x + y; x 2 X; y 2 Y g :

On générale, il existe deux formes de dominance :

Dominance forte

Dé…nition 1.3.4 Soient deux vecteurs critères Z1 ; Z2 2 Rp . On dit que Z1 domine forte-
ment Z2 si et seulement si zk1 < zk2 pour tout k 2 f1; :::; pg. Si Z1 domine fortement Z2 ,
alors Z1 est meilleur que Z2 sur tous les objectifs.

Dominance faible

Dé…nition 1.3.5 Soient deux vecteurs critères Z1 ; Z2 2 Rp . Alors Z1 domine faiblement

Z2 si et seulement si zk1 zk2 et zk1 6= zk2 ( i:e:zk1 zk2 pour tout k 2 f1; 2; :::; pg et zk1 < zk2
pour au moins un k).

21
 1.3. Programmation Linéaire multi-objectifs

E¢ cacité

Dé…nition 1.3.6 Une solution x^ 2 S est e¢ cace si et seulement s’il existe pas une autre
solution x 2 S et x 6= x^ tel que zk (x) x) et zk (x) 6= zk (^
zk (^ x):

Remarque 1.3.2 Une solution e¢ cace est l’image réciproque d’un vecteur critère non dom-
iné.

Théorème 1.3.1 [15] Soit Dx^ l’ensemble de dominance sur x 2 S. Alors, x est e¢ cace si
et seulement si Dx^ \ S = fxg.

E¢ cacité faible

Dé…nition 1.3.7 Une solution x^ 2 S est une solution faiblement e¢ cace s’il n’existe pas
une autre solution x 2 S et x 6= x^ tel que zk (x) < zk (^
x) pour tout k 2 f1; 2; :::; pg .

Une solution est faiblement e¢ cace si son vecteur objectif n’est pas fortement dominé.

E¢ cacité forte

Dé…nition 1.3.8 Une solution x^ 2 S est une solution fortement e¢ cace s’il n’existe pas de
solution x 2 S telle que x 6= x^ et zk (x) zk (^
x).

Une solution x^ est fortement e¢ cace s’il n’existe pas de solution x telle que le vecteur
objectif, qui lui est associé, soit aussi bon que celui de x^. Remarquons que l’e¢ cacité forte
implique l’e¢ cacité qui implique à son tour l’e¢ cacité faible
Une solution e¢ cace est aussi appelée solution Pareto optimale ou encore solution non-
dominée. Nous ne parlerons donc plus de solution optimale, mais d’un ensemble de solutions
Pareto optimales. L’ensemble des solutions e¢ caces d’un problème est noté E (:). La pro-
jection dans l’espace des objectifs de cet ensemble E (:) décrit une frontière communément
appelée frontière e¢ cace.

22
 1.3. Programmation Linéaire multi-objectifs

1.3.3 Caractérisation des solutions e¢ caces continues

Théorème de Geo¤rion
Ce théorème concerne la minimisation d’une combinaison convexe des critères. Il s’agit
d’une condition nécessaire et su¢ sante pour la détermination des solutions e¢ caces dans le
cas continu. Soit l’ensemble de tous les vecteurs = ( k ) ; k = 1; :::; p dé…nis par :
P
p
= 2 Rp j k = 1; k 0; k = 1; :::; p :
k=1

Pour 2 ; on dé…nit le problème paramétrique (P ) par :

8
> Pp
< min k zk (x)
x2S k=1
(P ) =
>
: t:q zk (x) = (z1 (x); z2 (x); :::; zp (x))

alors z est une solution e¢ cace si et seulement si z est une solution optimale du
problème paramétrique (P ).
Ce principe n’est cependant plus valable lorsque le domaine des solutions admissibles
n’est pas convexe (qui est le cas pour les problèmes en variables discrètes).

1.3.4 Points particuliers

En vue d’avoir certains points de références, des points particuliers ont été dé…nis dans
l’espace des objectifs. Ces points peuvent représenter des solutions réalisables ou non.

1. Le point xI idéal est le point qui a comme valeur pour chaque objectif la valeur optimale
de l’objectif considéré ou encore c’est le point qui optimise tous les critères en même
temps :

z I tel que 8i 2 f1; 2; :::; ng, z I = Optzi (x) = min fz1 (x)g ; min fz2 (x)g ; :::; min fzn (x)g
x2S x2S x2S

2. De ce point idéal peut être dé…ni le point utopique de la façon suivante :

zU = zI U

où > 0 et U est le vecteur unitaire (U = (1; :::; 1) 2 <n ). Il est clair, de par sa
dé…nition, que ce point n’est pas réalisable.

23
 1.3. Programmation Linéaire multi-objectifs

3. En…n le point Nadir qui est dé…ni par :

z N tel que 8i 2 f1; 2; :::; ng ; z N = Optzi (x) = max fz1 (x)g ; max fz2 (x)g ; :::; max fzn (x)g :
x2S x2S x2S
Ce point est aussi appelé point anti-idéal

1.3.5 Résolution d’un problème multicritère linéaire.

Choix de la méthode d’aide à la décision

La résolution d’un problème multicritère menant à la détermination d’un ensemble de so-

lutions e¢ caces. Ainsi, avant de se lancer dans la résolution d’un problème multicritère, il
faut se poser la question du type de méthode d’optimisation à utiliser. En e¤et, on peut
répartir les méthodes de résolution des problèmes multicritères en trois familles, en fonction
du moment où intervient le décideur. Ainsi nous pouvons trouver les familles suivantes :

Les méthodes d’optimisation a priori Dans ce cas, le compromis que l’on désire faire
entre les critères (objectifs) a été dé…ni avant l’exécution de la méthode. Ainsi une seule
exécution permettra d’obtenir la solution recherchée. Cette approche est donc rapide, mais
il faut cependant prendre en compte le temps de modélisation du compromis et la possibilité
pour le décideur de ne pas être satisfait de la solution trouvée et de relancer la recherche
avec un autre compromis. Généralement dans ce type de méthodes le problème est remplacé
par un problème unicritère.

Les méthodes d’optimisation progressives ou interactives Dans ce cas, le décideur

intervient dans le processus de recherche de solutions en répondant à di¤érentes questions
a…n d’orienter la recherche. Cette approche permet donc de bien prendre en compte les
préférences du décideur, mais nécessite sa présence tout au long du processus de recherche.

Les méthodes d’optimisation a posteriori Dans cette troisième famille de méthodes,

on cherche à fournir au décideur un ensemble de bonnes solutions bien réparties. Il peut
ensuite, au regard de l’ensemble des solutions, sélectionner celle qui lui semble la plus ap-
propriée. Ainsi, il n’est plus nécessaire de modéliser les préférences du décideur (ce qui peut

24
 1.3. Programmation Linéaire multi-objectifs

s’avérer être très di¢ cile), mais il faut en contre-partie fournir un ensemble de solutions
bien réparties, ce qui peut également être di¢ cile et requérir un temps de calcul important
(mais ne nécessite pas la présence du décideur).
Dans ce type de méthode, deux phases importantes sont à considérer : la phase de
recherche de l’ensemble des solutions e¢ caces, que nous appellerons, résolution du problème
d’optimisation et la phase de choix parmi ces solutions, qui relève de l’aide à la décision.
Les travaux portés dans ce mémoire, appartiennent à cette dernière catégorie, mais
seulement la première phase sera traitée.

Méthodes d’optimisation multicritère [5]

De nombreuses méthodes d’optimisation existent pour les problèmes multicritères linéaire.

Elles correspondent à des situations et des problématiques di¤érentes. Toutes ces méthodes
peuvent être classées en deux grandes catégories suivant le but recherché :

- Celles visant à obtenir une (ou plusieurs) solution(s) représentant un bon compromis entre
les di¤érents critères.

- Celles visant à déterminer l’ensemble de la frontière e¢ cace.

Recherche d’un compromis La première catégorie regroupe des méthodes ramenant

la résolution d’un problème multicritère à la résolution d’un (ou de plusieurs) problème(s)
unicritère(s). Leur but est de trouver une (ou plusieurs) solution(s) qui correspondra(ont)
à un bon compromis entre les di¤érents critères en fonction des préférences exprimées par
le décideur à l’aide des paramètres. Ces méthodes peuvent être utilisées soit avec des
paramètres …xés a priori, soit de manière interactive en modi…ant les paramètres durant la
recherche. De nombreuses méthodes peuvent entrer dans cette catégorie, nous en présentons
ci-dessous trois couramment utilisées :

Méthode lexicographique Elle consiste à considérer un ordre de priorité (dit lex-

icographique) entre chacun des objectifs. Le problème sera alors formulé avec l’objectif
suivant :

25
 1.3. Programmation Linéaire multi-objectifs

lexOpt(z 1 ; z 2 ; :::; z p )

Dans ce cas, la résolution pourra s’e¤ectuer en résolvant le problème successivement sur

chacun des critères pris par ordre de priorité décroissante. Les valeurs obtenues sur un
objectif sont ensuite intégrées comme contraintes pour la résolution sur des objectifs moins
prioritaires (cet ajout de contraintes peut casser la structure de la matrice des contraintes).
La solution obtenue par une résolution exacte successive de ces problèmes unicritères sera
l’une des solutions extrémales de E (une solution située sur l’enveloppe convexe).

Goal programming (programmation par buts). Dans ce type d’approche, le décideur

indique une valeur cible (but) et l’objectif est de minimiser l’écart avec cette cible.(c-à-d
s’approcher au maximum de valeurs cibles appelées aussi niveaux d’aspiration et notées z^k ;
8k = 1; 2; :::; p) sur chacun des objectifs. Pour cela, des poids sont a¤ectés à chaque objectif
(notés k; 8k = 1; 2; :::; p), et la somme pondérée des écarts en excès(notés d+
k ) comme en

défaut (notés dk ) par rapport aux valeurs cibles doit être minimisée. Le problème sera
alors formulé de la manière suivante :
8
> P k +
>
> min zgoal programming = dk + dk
>
>
>
>
< sc X2S
P
>
> ci xi + d+ ^k ; 8k = 1; 2; :::; p
k + dk = z
>
>
>
> i2I
>
: d+k ; dk 0 ; 8k = 1; 2; :::; p

La structure de la matrice des contraintes est alors cassée. La solution obtenue par une
résolution exacte de ce problème unicritère ne sera pas obligatoirement l’une des solutions
de E:

Méthode “Max-ordering” Une troisième méthode correspond au cas où il faut opti-

miser non pas tous les objectifs, mais uniquement le moins bon. Dans ce cas, le problème
reviendra à optimiser l’objectif suivant pour un problème de maximisation (resp. minimi-
sation) :
M ax zmax Ordering = min z k (resp M in zmin Ordering = max z k )
k k

26
 1.3. Programmation Linéaire multi-objectifs

La structure de la matrice des contraintes est alors cassée. La solution obtenue par une
résolution exacte de ce problème unicritère ne sera pas obligatoirement l’une des solutions
de E.

Détermination de la frontière e¢ cace

La deuxième catégorie rassemble les méthodes déterminant l’ensemble complet des solutions
e¢ caces du problème. Ces méthodes permettent au décideur de sélectionner a posteriori
la (ou les) solution(s) qui l’intéresse parmi l’ensemble des solutions e¢ caces. Di¤érentes
méthodes peuvent être utilisées, nous présentons ci-dessous deux méthodes courantes :

La méthode du ranking Elle est applicable uniquement aux problèmes bi-critères. Elle
consiste à rechercher l’ensemble des solutions situées entre le point Nadir et le point Idéal.
Ceux-ci sont obtenus en calculant les points extrêmes de la frontière e¢ cace (par deux
résolutions lexicographiques successivement sur chaque critère). Ensuite, en partant de
l’une des solutions extrêmes, la deuxième meilleure est cherchée, puis la troisième, . . ., puis
la k ieme jusqu’à atteindre la valeur du point Nadir.

La méthode de la somme pondérée Une autre méthode parfois utilisée, consiste à faire
une recherche paramétrique sur la somme pondérée des critères (la structure de la matrice
des contraintes est donc conservée). Cependant, cette technique présente l’inconvénient
de ne permettre de trouver que les solutions e¢ caces situées sur l’enveloppe convexe de
l’ensemble des solutions e¢ caces; cette méthode n’est donc valide que pour les problèmes
dont toutes les solutions e¢ caces sont situées sur l’enveloppe convexe de E. Pour les autres
problèmes, cette méthode peut cependant être utilisée pour obtenir un sous-ensemble de la
frontière e¢ cace.

27
Chapitre 2

Optimisation multi-objectifs en
nombres entiers

2.1 Introduction
De nombreux problèmes d’optimisation se formulent par l’intermédiaire de variables entières,
la résolution de ces problèmes est généralement di¢ cile. En e¤et, le domaine des solutions
admissibles n’est plus convexe, ainsi la solution optimale n’est en générale plus un sommet
et peut donc être un point quelconque de ce domaine. Toute caractérisation particulière
de la solution optimale est perdue, la résolution s’en trouve donc plus di¢ cile. Dans ce
chapitre, nous rappelons les principaux résultats de la programmation linéaire unicritère et
multicritère en variables entières. Nous abordons les résultats nécessaires pour l’étude et
la résolution du problème bicritère d’a¤ectation (BAP ) dans le prochain chapitre. Nous
formulons les problèmes (ILP ) et (M OILP ), nous décrivons les méthodes les plus souvent
utilisées pour les résoudre. Nous terminons par quelques méthodes de résolutions pour des
problèmes qui appartiennent à la même classe que notre problème.

28
 2.2. Programmation unicritère en nombres entiers

2.2 Programmation unicritère en nombres entiers

2.2.1 Problèmes de programmation linéaire unicritère en nom-

bres entiers

Considérons le problème de programmation linéaire unicritère suivant :

8
< min z = cx
(P L)
: x2S

où S = fx 2 Rn : Ax b; x 0g ; A 2 Rm n
; x 2 R n ; b 2 Rm ; c 2 R1 n

Si toutes les variables sont entières, on a un problème de programmation linéaire en

nombres entiers écrit sous la forme suivante :
8
< min cx
(ILP )
: t:q x 2 D

où D = S \ Zn ; Z est l’ensemble des entiers relatifs.

Dans le cas où seulement quelques variables sont entières, on obtient un problème de
programmation linéaire mixte donné par :
8
>
> min (cx + hy)
>
<
(LP M IX) t:q Ax + Gy = b
>
>
>
: x 0; y 0 et entier
Si toutes les variables sont restreintes à 0 et 1, on a un problème de programmation en
variables binaires écrit comme suit :
8
>
> min cx
>
<
(LP BIN ) t:q Ax = b
>
>
>
: x 2 f0; 1gn

29
 2.2. Programmation unicritère en nombres entiers

2.2.2 Complexité

Comme pour tout algorithme, une manière de comparer les méthodes de résolutions est de
considérer leur complexité mathématique. Ainsi, on parlera d’un algorithme de complexité:

- Polynomiale lorsque son temps de calcul est borné par un polynôme de la taille du prob-
lème (c-à-d que la complexité de l’algorithme est en O(np mq ) avec p et q constants).

- Exponentielle lorsque son temps de calcul ne peut pas être borné par un polynôme de la
taille du problème (c-à-d que la complexité de l’algorithme est par exemple en O(pn )
ou en O(pm ) avec p constant). Par extension, la théorie de la complexité s’intéresse à la
complexité des modèles de programmation linéaire. Celle-ci se détermine en fonction
de la complexité des algorithmes susceptibles de le résoudre exactement. Ces modèles
peuvent ainsi être classés en deux catégories :

–Ceux pour lesquels un algorithme de résolution exacte en temps polynomial est connu.
On parlera alors de problèmes faciles ou encore de problèmes de classe P.
– Ceux pour lesquels on ne connait pas d’algorithme de résolution exacte en temps
polynomial. On parlera alors de problèmes di¢ ciles. Parmi cette deuxième catégorie, les
problèmes pour lesquels il ne peut pas exister d’algorithme de résolution exacte en temps
polynomial, à moins que la conjecture P =
6 N P ne soit fausse, sont appelés N P-di¢ ciles.
En…n, le choix de la méthode de résolution à mettre en œuvre dépendra souvent de la
complexité du problème. En e¤et, suivant sa complexité, le problème pourra ou non être
résolu de façon optimale. Dans le cas de problèmes classés dans la classeP, un algorithme
polynomial a été mis en évidence. Il su¢ t donc de l’utiliser. Dans le cas de problèmes
N P-di¢ ciles, si le problème est de petite taille, alors un algorithme exact permettant de
trouver la solution optimale peut être utilisé (procédure de séparation et évaluation (Branch
& Bound), programmation dynamique...). Malheureusement, ces algorithmes par nature
énumératifs, sou¤rent de l’explosion combinatoire et ne peuvent s’appliquer à des problèmes
de grandes tailles (même si en pratique la taille n’est pas le seul critère limitant).

30
 2.2. Programmation unicritère en nombres entiers

2.2.3 Optimisation combinatoire

L’optimisation combinatoire regroupe une large classe de problèmes ayant des applications
dans de nombreux domaines applicatifs. Un problème d’optimisation combinatoire est dé…ni
par un ensemble …ni de solutions discrètes D et une fonction objectif f associant à chaque so-
lution une valeur (la plupart du temps, une valeur réelle). Ainsi, un problème d’optimisation
combinatoire consiste en l’optimisation (minimisation ou maximisation) d’un certain critère
sous di¤érentes contraintes permettant de délimiter l’ensemble des solutions réalisables (ou
solutions admissibles). La variété des problèmes d’optimisation combinatoire est en par-
ticulier due au large spectre de ses applications. Notons que la plupart des problèmes
d’optimisation combinatoire sont N P-di¢ ciles; sauf quelques problèmes qui ont une struc-
ture particulière.

Quelques problèmes d’optimisation combinatoire [13]

Problème de sac à dos On dispose de n objets ayant chacun un poids aj et une valeur
cj (j = 1; 2; :::; n) : Il faut sélectionner un sous ensemble de ces n objets dont le poids total
soit inférieur ou égal à un nombre donné et dont la valeur somme des valeurs des objets
sélectionnés, soit maximum.
Le problème doit son nom au scénario qui est souvent utilisé pour l’introduire : un
campeur prépare une randonné, les n objets sont ceux qu’il envisage d’emporter. L’objet
j ayant un poids aj et une utilité cj , le campeur cherche à maximiser l’utilité totale de
son chargement tout en limitant son poids (ou son encombrement si les aj représentent des
volumes)

Problème de voyageur de commerce Soient G = (X; E) un graphe complet à n

sommets numérotés de 0 à n 1 et P une matrice n n des poids de chaque arc. Le
problème du voyageur de commerce (travelling salesman problem), consiste à trouver dans
G un plus court cycle hamiltonien (un sommet représente une ville et le voyageur doit passer
une et une seule fois par chaque ville, à partir de la ville 0 pour …nalement revenir à son
point de départ).

31
 2.2. Programmation unicritère en nombres entiers

Une manière équivalente de formuler ce problème est de considérer la matrice P dont

l’élément pji de la ieme ligne et de la j eme colonne est dé…nie comme suit :

8
>
> la distance de la ville i à la ville j s’il existe un moyen d’aller directement
>
<
j
pi = de i à j ((i; j) 2 E)
>
>
>
: 1 si non

Le problème consiste alors à :

(
X d(i)
min pi ; i = 1; 2; :::; n
i

2.2.4 Problème d’a¤ectation ([13], [16])

C’est le problème qui consiste à a¤ecter un nombre n 2 N de sources (ou origines) au même
nombre de destinations à un coût minimum. Ainsi, chaque source est associée à une et une
seule destination. Cette spéci…cité implique deux particularités à ce programme linéaire :

La fonction objectif C = (cij )(i;j=1;:::;n) (où (cij )(i;j=1;:::;n) est le coût d’a¤ectation de
ieme source au j eme destination) correspond à une matrice carrée.

La solution optimale (ou n’importe quelle solution admissible) est telle qu’il y a une
seule a¤ectation dans chaque colonne et chaque ligne.

La formulation mathématique de problème d’a¤ectation unicritère (AP )

Soit un atelier où il y’à n opérations à exécuter par n machines, chacune de ces ma-
chines n’e¤ectuant qu’une et une seule tâche. En connaissant les coûts associés à chaque
opération e¤ectuée par chaque machine (qui peut être le temps mis par la machine i a
l’accomplissement de la tâche j) l’objectif est de déterminer les a¤ectations opération/machine
qui minimise le critère. C’est un problème combinatoire avec :
- Choix
8 de variables :
< 1 si l’opération i est exécutée par la machine j
xij = i = 1; 2; :::; n j = 1; 2; :::; n
: 0 sinon

32
 2.2. Programmation unicritère en nombres entiers

- Une opération est exécutée par une et une seule machine :

Pn
xij = 1 j = 1; 2; :::; n
i=1
- Une machine exécute une et une seule opération :
Pn
xij = 1 i = 1; 2; :::; n
j=1
Ce qui revient au modèle complet :
8
> Pn P n
>
> min Z (x) = cij xij
>
>
>
> i=1 j=1
>
> Pn
< xij = 1 j = 1; 2; :::; n
(AP ) i=1
>
> P
n
>
> xij = 1 i = 1; 2; :::; n
>
>
>
>
j=1
>
: xij 2 f0; 1g 8 (i; j)

2.2.5 Solution de problème d’a¤ectation unicritère

Dégénérescence

Vu le caractère fortement dégénéré du problème d’a¤ectation; l’application des méthodes

classiques de résolution des problèmes linéaire à ce dernier tel que le simplexe, engendre des
calculs très dur et de plus en plus long car au bout de quelques itérations, on retrouve une
solution déjà trouver, c’est à dire le problème de cyclage.
Une façon de résoudre le problème d’a¤ectation est d’énumérer les solutions et de choisir
celle qui fournit le coût le plus faible. En générale pour une matrice coût a n lignes et n
colonnes, il y a n! possibilités d’a¤ectations qui veut dire n! solutions admissibles. Puisque
n! s’accroît très vite avec n, l’énumération totale est une tâche presque impossible.

La méthode hongroise

Le mathématicien hongrois Egerváry [12] était le premier à proposer un algorithme (im-

plicite) pour le problème d’a¤ectation, ce que inspire Kuhn pour développer la méthode
hongroise (Hungarian method, en hommage), qui est une procédure polynomiale de complex-
ité O(n4 ). Plus tard, avec l’introduction des procédures de plus court chemin la complexité
a été réduite à O(n3 ). Et depuis plusieurs algorithmes pour le (AP ) ont été développés.

33
 2.2. Programmation unicritère en nombres entiers

Dans un survey (bibliographie) présenté par Dell’Amico et Martello [11], plus de 100 papiers
sur le problème sont mentionnés.

Principe de la méthode

Soit la matrice coût C = (cij )i;j=1;2;:::;n

0 1
c11 :: :: c1n
B C
B C
B : C
C=B
B
C
C
B : C
@ A
cn1 cnn
Phase1.
1)- Choisir le minimum de chaque ligne : mi = min fcij g; i = 1; : : : ; n:
1 j n
X
n
2)- Pour chaque ligne, on retranche le minimum correspondant et on a Z mi .
i=1
0
3)- Choisir le minimum de chaque colonne : lj = min fcij = cij mi g; j = 1; : : : ; n:
1 i n
4)- Pour chaque colonne, on retranche le minimum correspondant et on a:

X
n X
n
Z mi + lj :
i=1 j=1

5)- Trouver une solution réalisable en a¤ectant un seul zéro par ligne et par colonne, on
obtient le tableau (I).
Si cette solution existe alors c’est la solution optimale du tableau initiale (tableau (0)).
Si on a pas (5), aller à la deuxième phase :
Phase2.
a)- Marquer les lignes ayant un zéro non a¤ecté.
b)- Marquer les colonnes ayant un zéro non a¤ecté sur une ligne marquée.
c)- Marquer les lignes non encore marquées ayant un zéro a¤ecté dans une colonne
marquée.
d)- Barrer les lignes non marquées et les colonnes marquées.
e)- Choisir le minimum des éléments non barrés, le retrancher des éléments non barrés
et le rajouter aux éléments doublement barrés. On obtient le tableau (II):

34
 2.2. Programmation unicritère en nombres entiers

Trouver une solution réalisable on a¤ectant un seul zéro par ligne et par colonne en cas
d’échec, reprendre la procédure à partir de la deuxième étape. Si une telle solution existe,
c’est une solution optimale du (AP ).

Justi…cation de la méthode

1. Montrons que si X est une solution optimale du problème d’a¤ectation (P A) dans le

tableau (I) alors X est une solution optimale dans le tableau (0).

1.1. Tableau (0) : cij ; i; j = 1; 2; :::; n

Soit
mi = min fcij g; i = 1; : : : ; n:
1 j n
0
cij = cij mi ; i; j = 1; : : : ; n
0
lj = min fcij g; j = 1; : : : ; n
1 i n
0
c"ij = cij lj ; i; j = 1; : : : ; n:

1.2. Tableau (I) : c"ij ; i; j = 1; 2; :::; n

Soit X une a¤ectation, on note par Z0 (X) : la valeur de la fonction objectif dans le
tableau (0) et Z1 (X) la valeur de la fonction objectif dans le tableau (I).
On a :
P P
Z1 (X) = c"ij xij
1 i n1 j n
P P 0
= cij lj xij
1 i n1 j n
P P 0 P P
= cij xij lj xij
1 i n1 j n 1 i n1 j n
D’autre part :
P P P P P P
lj xij = lj xij = lj xij = 1 (constante)
1 i n1 j n 1 j n1 i n 1 j n 1 i n
D’où !
P P
Z1 (X) = (cij mi ) xij 1
1 i n1 j n
! !
P P P P
= cij xij mi xij 1
1 i n1 j n 1 i n1 j n
De même:

35
 2.2. Programmation unicritère en nombres entiers

P P P P
mi xij = mi xij = 2
1 i n1 j n 1 i n 1 j n
D’où !
P P
Z1 (X) = cij xij 1 2 = Z0 (X) ( 1 + 2)
1 i n1 j n
Posons : 1 + 2 = M:
D’où :Z1 (X) = Z0 (X) M:
Si X est une solution optimale pour le tableau (I) alors Z1 (X ) = 0:
Supposons que X ne soit pas optimale pour le tableau (0), donc il existe une autre
solution optimale et soit X cette solution .
Donc Z0 (X) Z0 (X ) ) Z1 (X) + M Z1 (X ) + M ) Z1 (X) Z1 (X ) absurde car
X est solution optimale pour le tableau (I).
D’où X est optimale pour le tableau (0); avec Z0 (X ) = M:

2. Montrons que si on obtient une solution réalisable on a¤ectant les zéros du tableau (II)
alors c’est une solution optimale de (AP ) dans le tableau (0): Après application de la
deuxième étape, on obtient le tableau (II) sous la forme suivante :

J J
dij = c"ij + dij = c"ij
I
les elements doublement barres + les elements barres
dij = c"ij dij = c"ij
I
les elements barres les elements non barres

Où : dij : les éléments du tableau (II); = min c"ij

i2I
j2J
Soit X une a¤ectation :
PP
Z2 (X) = dij xij
i2I P
P j2J PP PP PP
= dij xij + dij xij + dij xij + dij xij
J I J I J
PI P J P
I P
Posons: dij xij + dij xij = A
I J I J
D’où

36
 2.2. Programmation unicritère en nombres entiers

PP PP
Z2 (X) = dij xij + A + dij xij
I J
I J !
PP PP "
= c"ij + xij + A + cij xij
I J I J
! !
PP " PP PP " PP
= cij xij + xij + A + cij xij xij
I J I J I J I J
! !
PP " PP " PP PP
= cij xij + cij xij + A + xij xij
I J I J I J I J
!
PP PP
= Z1 (X) + xij xij
I PJ P I J
PP PP PP PP PP
xij xij = xij + xij xij xij
I J I J I! J I J
I J I J !
PP PP PP PP
= xij + xij xij + xij
I J I J I J I J
! !
P P P P P P
= xij + xij xij + xij
I J J J I I

= I + J
D’ou :
Z2 (X) = Z1 (X) + I + J = Z1 (X) + (constante)
Si X est solution optimale pour le tableau (II); alors Z2 (X ) = 0:
Supposons que X ne soit pas optimale pour (P A) dans le tableau (0); et soit X une
solution optimale pour (P A).
Donc : Z0 (X) Z0 (X ) ) Z2 (X) + M Z2 (X ) + M ) Z2 (X) Z2 (X )
impossible.
D’où X est optimale pour le tableau (0):

Remarque 2.2.1 La solution optimale donnée par la méthode hongroise n’est pas unique.

2.2.6 Méthodes exactes de résolution

Pour les problèmes en variables discrètes, le nombre de solutions admissibles est …ni lorsque
leur domaine est borné. Pourtant, le nombre de ces solutions grandissant généralement de
manière exponentielle (on parle d’explosion combinatoire), et la propriété de convexité du
domaine des solutions n’étant en général plus valable, la résolution de ces problèmes n’est

37
 2.2. Programmation unicritère en nombres entiers

souvent pas aisée. Une exception existe lorsque la matrice des contraintes A est totalement
unimodulaire. Tous les sommets du domaine des solutions admissibles de la relaxation
linéaire du problème sont alors entiers. Le problème peut donc être résolu comme un
problème en variables continues (et donc en temps polynomial). D’une manière générale,
la résolution de ces problèmes n’est cependant pas aisée. Beaucoup de ces problèmes sont
ainsi N P di¢ ciles.
Les méthodes de résolution exactes pour les problèmes en variables discrètes ou mixtes
sont nombreuses, cependant trois familles principales peuvent être distinguées :

La programmation dynamique

Consiste à placer le problème dans une famille de problèmes de même nature mais de
di¢ culté décroissante, puis à trouver une relation de récurrence liant les solutions optimales
de ces problèmes,

Les méthodes dites par séparation et évaluation (Branch & Bound par exemple)

Consistent à faire une énumération implicite fondée sur un principe de décomposition

du problème en sous-problèmes (branchements) [13], et pour chaque sous problème crée,
l’évaluation de ceux-ci permet d’avoir une idée de la valeur des solutions qu’il contient, ap-
préciant par défaut la meilleur solution lui appartenant. Ainsi de suite jusqu’à ne plus avoir
que des problèmes faciles à résoudre ou qui ne peuvent pas contenir de solutions optimales
ou réalisables,

Les méthodes polyhédrales (méthode des coupes)

Consistent à ajouter progressivement des contraintes supplémentaires (ou coupes) a…n de

ramener la résolution d’un problème linéaire en nombres entiers à celle d’un problème
linéaire, et ça en ramenant le domaine des solutions admissibles à un domaine convexe
(sans en enlever la ou les solutions optimales bien évidemment). Ces coupes sont appelées
inégalités valides lorsqu’elles ne suppriment aucune solution admissible du problème.
De plus, certaines méthodes essayent de combiner les avantages de di¤érentes familles.

38
 2.2. Programmation unicritère en nombres entiers

Ainsi par exemple, la méthode du Branch & Cut, dérivée du Branch & Bound, intègre une
recherche de coupes dans les nœuds de l’arbre de recherche a…n d’améliorer la valeur de la
relaxation linéaire guidant le processus.
Nous en présentons ci-dessous deux méthodes couramment utilisées :

2.2.7 Procédure par séparation et évaluation (Branch and Bound)

La méthode de Branch and Bound repose essentiellement sur trois notions clés :

Procédure de séparation

L’ensemble des solutions est séparé (décomposé) successivement en des sous ensembles de
tailles de plus en plus réduite en vue d’aboutir à un sous ensemble ne contenant qu’une
seule solution ou à un sous ensemble vide ou encore appelé stérile.

Procédure d’évaluation

Pour chaque sous ensemble crée par séparation, l’évaluation permet d’analyser ce sous prob-
lème ou encore d’avoir une idée de la valeur des solutions qu’il contient, appréciant par défaut
la meilleur solution lui appartenant.

Procédure de cheminement

C’est la règle de sélection du sous ensemble que l’on va séparer à la prochaine itération. Elle
indique quels sous-ensembles analysés et dans quel ordre.
Les stratégies classiques de sélection sont : meilleur d’abords, profondeur d’abords et
largeur d’abords.

2.2.8 Les coupes de Gomory [13]

Considérons le (ILP ) sous forme standard :

8
< min z = cx
(ILP ) ((1:1))
: t:q x 2 D

39
 2.2. Programmation unicritère en nombres entiers

La relaxation continue de (1:1) est :

8
< min z = cx
(LP )
: t:q x 2 S

L’idée principale de cette méthode est d’ajouter des contraintes qui n’excluent aucun
point entier admissible. La méthode consistera à ajouter de telles contraintes linéaires une
par une, jusqu’à ce que la solution optimale de le relaxation soit entière. Les contraintes
ajoutées sont appelées troncatures ou coupes.

Description de la méthode

Commençons par résoudre la relaxation linéaire du problème par l’algorithme (primal) du

e = eb : parmi les variables de
simplexe et considérons le tableau obtenu à l’optimum Ax
base, choisissons une variable xi ; i 2 J, fractionnaire (s’il n’y en a pas, on est à l’optimum
en entier). La contrainte correspondante à xi se lit directement sur le tableau optimal :

X
xi + af e
ij xj = b ((1:2))
J2J

Puisque toutes les variables sont positives ou nulles dans (2:1), on a :

X X
bf
aij c xj af
ij xj
J2J J2J

Donc on a

X
xi + bf
aij c xj bei
J2J

La patrie gauche de cette inéquation est entière. Le second membre peut donc être
j k
remplacé par bei :

X j k
xi + bf
aij c xj bei ((1:3))
J2J

(1:2) (1:3) donne :

40
 2.2. Programmation unicritère en nombres entiers

X j k
(f
aij bf
aij c) xj bei bei
J2J

Posons :

fij = af
ij aij c (partie fractionnaire de af
bf ij , 0 < fij < 1)

j k
fi = bei bei ( partie fractionnaire def
bi , 0 < fi < 1)

Finalement, nous obtenons la contrainte :

X
fij xj fi
J2J

C’est la coupe de Gomory

Nous voulons ajouter cette coupe au problème initial. Pour garder un problème écrit
sous forme canonique, nous multiplions cette dernière inéquation par ( 1) et ajoutons une
variable d’écart s. On obtient :

X
fij xj + s = fi ((1:4))
J2J

Si la coupe (1:4) est ajoutée au tableau optimal du simplexe d’un programme linéaire, aucun
point admissible entier n’est exclu, et le nouveau tableau est écrit sous forme canonique par
rapport à la nouvelle base formée de la base optimale précédente à laquelle on ajoute s.
Cette nouvelle base n’est pas réalisable.

Remarque 2.2.2 La base ainsi obtenue véri…e les conditions d’optimalité (coûts réduits
positifs ou nuls) et n’est pas primal-admissible : on peut appliquer l’algorithme dual du
simplexe pour résoudre le nouveau programme linéaire formé.

Remarque 2.2.3 La nouvelle variable s doit être entière comme toutes les autres variables
du problème pour pouvoir itérer le processus.

Par ce procédé, on ajoute ainsi, une par une des coupes jusqu’à obtention d’une solution
de base entière.

41
 2.3. Programmation linéaire multicritère en nombres entiers

2.3 Programmation linéaire multicritère en nombres

entiers
Un programme linéaire multicritère en nombres entiers est constitué d’un système de con-
traintes linéaires dé…nissant un domaine discret de solutions réalisables, et d’un ensemble
de fonctions linéaires à maximiser ou à minimiser dé…nissant des objectifs con‡ictuels. Le
problème consiste à déterminer toute solution réalisable entière telle qu’il n’existe aucune
autre solution réalisable entière qui fournisse des valeurs au moins aussi bonnes que celles
sur chaque objectif et même meilleure sur au moins un objectif.

2.3.1 Problèmes de programmation mathématique multicritère

en nombres entiers

Considérons le problème de programmation linéaire multicritère suivant :

8
< “ min ”z = ck x k = 1; 2; :::; p
k
(M OLP )
: x2S

avec S = fx 2 Rn : Ax b; x 0g ; A 2 R(m n)
; ck 2 R(1 n)
; x 2 Rn et b 2 Rm
k = 1; 2; :::; p
Si toutes les variables sont des entiers, nous obtenons un problème de programmation
linéaire multicritère en variables entières :
8
< “ min ”z = ck x k = 1; 2; :::; p
k
(M OILP )
: x2D
où D = S \ Zn ; Z est l’ensemble des entiers relatifs.

2.3.2 Solutions supportées / non supportées

Dé…nition 2.3.1 Une solution x^ de D est e¢ cace pour le problème (M OILP ), s’il n’existe
pas une autre solution x 2 D telle que zk (x) x), k = 1; 2; :::; p avec au moins une
zk (^
inégalité stricte.

42
 2.3. Programmation linéaire multicritère en nombres entiers

Pour les problèmes en nombres entiers, deux types de solutions e¢ caces peuvent être
di¤érenciées : les solutions e¢ caces supportées et les solutions e¢ caces non supportées. Les
premières sont celles situées sur l’enveloppe convexe de l’ensemble des solutions e¢ caces et
peuvent donc être trouvées à l’aide d’une agrégation linéaire des objectifs. Elles sont donc
plus simples à obtenir que les solutions non supportées. D’ailleurs, les premiers travaux en
optimisation multi-objectifs se sont pour la plupart focalisés sur la recherche de ces solutions
supportées en optimisant des combinaisons linéaires des objectifs utilisant di¤érents vecteurs
de poids. Alors pourquoi ne pas se satisfaire des solutions supportées?. Tout d’abord parce
que ces solutions peuvent ne représenter qu’un petit sous-ensemble des solutions e¢ caces.
De plus, ces solutions supportées ne sont pas forcément bien réparties et ne représentent
pas toujours un bon compromis. Donc, si l’on veut obtenir des solutions de bon compromis
entre les objectifs, il est nécessaire de considérer les solutions e¢ caces non supportées.
Notons par SE(:) l’ensemble des solutions e¢ caces supportées, et par N SE(:) l’ensemble
des solutions e¢ caces non supportées.

2.3.3 Revue des méthodes exactes existantes (voir [4], [6], [10])

Dans la littérature, une attention particulière a portés sur les problèmes à deux critères en
utilisant les méthodes exactes. Ces méthodes sont e¢ caces pour des problèmes de petites
tailles. Pour des problèmes à plus de deux critères ou de grandes tailles, il n’existe pas de
procédures exactes e¢ caces, étant donné les di¢ cultés simultanées de la complexité N P-
complet, et le cadre multi-critères des problèmes.
Nous présentons ici les principales méthodes exactes développées de façon à obtenir
l’ensemble ou une partie de l’ensemble des solutions e¢ caces.

L’agrégation linéaire

Cette méthode populaire transforme le problème multi-objectifs en un problème mono-

objectif en combinant linéairement les di¤érents objectifs. Ainsi, le nouveau problème
obtenu, car il s’agit alors d’un problème di¤érent (le problème obtenu conserve la struc-
ture de la matrice des contraintes ce qui peut être intéressant lorsque cette structure cor-

43
 2.3. Programmation linéaire multicritère en nombres entiers
X
respond à un problème caractéristique facile à résoudre), consiste à optimiser i zi : Le
i
théorème de Geo¤rion indique qu’en utilisant di¤érentes valeurs pour le vecteur , il est
possible d’obtenir toutes les solutions supportées du problème multi-objectifs initial. Par
contre, aucune solution non supportées ne peut être trouvée par cette méthode. La méthode
d’agrégation linéaire a donc ses limites. Toutefois, elle est intéressante pour des problèmes
ayant de nombreux objectifs et/ou un grand nombre de solutions supportées bien réparties.
Dans ce contexte, il peut être su¢ sant de générer les solutions supportées.
Notons, en…n que les résultats obtenus dans la résolution du problème unicritère obtenu
dépendent fortement des paramètres choisis pour le vecteur poids . Les poids i doivent
aussi être choisis en fonction des préférences associées aux critères, ce qui est une tâche déli-
cate. Ainsi, une approche généralement utilisée est de résoudre le problème avec di¤érentes
valeurs de ; d’où le coût associé à cette classe de méthodes.

La recherche dichotomique

La recherche dichotomique o¤re un schéma d’application de l’agrégation linéaire permet-

tant d’obtenir les solutions non supportées. Cette méthode consiste à explorer de façon
dichotomique des intervalles de recherche de plus en plus petits. Tout d’abord les solutions
extrêmes sont recherchées. Puis une recherche est menée entre ces solutions r et s suivant
une direction perpendiculaire à la droite (r; s). En interdisant de réobtenir les solutions r et
s et en éliminant les solutions dominées par ces solutions, cette recherche trouve la meilleure
solution e¢ cace relativement à cette direction de recherche, solution qui peut alors être non
supportées. Cette nouvelle solution crée deux nouveaux intervalles qu’il faut explorer de la
même façon. Cette méthode, très utilisée au bi-objectifs, est intéressante mais nécessite de
l’ordre de 2n recherches, si n est le nombre de solutions e¢ caces. La recherche dichotomique
est, là encore, applicable aux problèmes bi-objectifs.

Méthode -contrainte

Le principe de la méthode -contrainte qui consiste, dans le cas bi-objectifs, à borner l’un
des objectifs (en général le plus di¢ cile à résoudre) et à optimiser l’autre objectif (optimi-

44
 2.3. Programmation linéaire multicritère en nombres entiers

sation mono-objectif) en tenant compte de cette borne, est intéressant lorsque l’on cherche
à énumérer toutes les solutions e¢ caces. En e¤et, en utilisant cette méthode itérativement,
en repartant à chaque fois de la solution trouvée pour dé…nir la borne suivante, il est pos-
sible en utilisant une méthode exacte mono-objectif de générer, l’ensemble des solutions
e¢ cace. Par exemple pour le cas bi-objectifs, la solution e¢ cace optimale pour l’objectif z1
est d’abord recherchée (solution Optz1 ). Cette solution détermine la borne B1 sur l’objectif
z2 en dessous de laquelle l’objectif z2 va devoir être optimisée. Cela nous donne la solution
Opt z2 qui elle-même détermine la borne B2 , etc. L’inconvénient principal de cette méthode
est qu’elle nécessite une résolution mono-objectif pour chacune des solutions. Lorsque ce
nombre est élevé, cela peut être vu comme une limite, d’autant plus lorsque la méthode
de résolution mono-objectif est coûteuse. De plus, lorsqu’il n’existe pas de méthode mono-
objectif e¢ cace, rechercher une solution particulière (respectant une borne, par exemple)
est souvent synonyme d’énumération de nombreuses autres solutions dont certaines peuvent
être e¢ caces optimales. Ainsi certaines solutions seront énumérées plusieurs fois sans que
la méthode les repère.

Méthode de deux-phases

La méthode de deux phases a initialement été proposée par Gonzalez et al (voir [19]), et par
la suite, adaptée par Ulungu et Teghem au problème d’a¤ectation et sac à dos bi-objectifs.
Pendant la dernière décennie, cette méthode s’est avérée très e¢ cace pour résoudre même
des problèmes qui sont très di¢ ciles, (voir par exemple ( [21])).
Comme son nom l’indique, cette méthode est décomposée en deux étapes : la première
consiste à trouver toutes les solutions supportées, puis la deuxième phase cherche entre ces
solutions les solutions non supportées. Cette méthode travaille donc essentiellement dans
l’espace des objectifs et elle est souvent utilisée dans le cas bi-critères.

Première phase L’objectif de la première phase est d’obtenir l’ensemble des solutions
e¢ caces supportées. Comme nous l’avons vu précédemment, ces solutions ont l’avantage
d’être relativement faciles à trouver puisqu’elles optimisent une certaine combinaison linéaire
des objectifs. Ainsi, durant la première phase de la méthode, les deux solutions extrêmes

45
 2.3. Programmation linéaire multicritère en nombres entiers

(solutions optimisant chacun des deux objectifs) sont recherchées. Puis, de façon récursive,
dès que deux solutions supportées r et s sont trouvées, la méthode recherche d’éventuelles
autres solutions supportées entre r et s, à l’aide de combinaisons linéaires bien choisies des
objectifs. A la …n de la première phase l’ensemble des solutions supportées est donc trouvé.
Cette première phase rappelle la méthode dichotomique, mais ici seules les solutions sup-
portées sont recherchées. Pour cela, lors de l’exploration entre deux solutions, on s’autorise
à retrouver l’une de ces deux solutions, lorsqu’il n’existe pas d’autres solutions supportées
dans l’intervalle.

Deuxième phase La deuxième phase consiste alors en la recherche des solutions non
supportées. Ces solutions ne peuvent être obtenues par combinaisons d’objectifs. Ulungu et
Teghem proposent alors d’utiliser les solutions supportées trouvées pour réduire l’espace de
recherche en argumentant que les solutions Pareto non supportées restantes sont forcément
dans les triangles basés sur deux solutions supportées consécutives. Ainsi, une recherche de
type deuxième phase est exécutée entre chaque couple de solutions supportées adjacentes.
La méthode de recherche au sein de ces triangles dépend du problème étudié. A la …n de la
deuxième phase, toutes les solutions Pareto sont trouvées.
La méthode en deux-phases présente un schéma de résolution exacte très intéressant car
très général et qui ne dépend pas du problème. Son intérêt réside dans une décomposition
de l’espace de recherche et l’utilisation de méthodes mono-objectifs pour les di¤érentes
résolutions successives (recherche des extrêmes, résolution des agrégations...). Appliquer la
méthode en deux-phases pour la résolution d’un problème bi-objectifs nécessite donc d’avoir
une méthode mono-objectif e¢ cace, ce qui rend la méthode performante pour ces problèmes
là. Cependant, la non existence de méthode exacte e¢ cace pour d’autres problèmes pouvant
optimiser chaque objectif séparément peut compromettre l’intérêt de la méthode.

PPM : Parallel Partitionning Method [6]

Cette méthode est décomposée en trois phases :

46
 2.3. Programmation linéaire multicritère en nombres entiers

Phase1 : Recherche des extrêmes et partitionnement de l’espace de recherche.

Les deux solutions extrêmes sont recherchées. Ces deux solutions indiquent donc les valeurs
minimales et maximales des solutions e¢ caces pour chacun des objectifs. L’espace contenu
entre ces deux solutions est ensuite découpé de façon uniforme suivant l’objectif le plus
di¢ cile à résoudre (supposons un découpage suivant z2 ).

Phase2 : Recherche d’une solution par partition. À la manière de la méthode

-contrainte, la solution optimisant le second objectif (z1 ) est recherchée pour chacune des
partitions. À la …n de cette deuxième phase, des solutions, les mieux réparties possible,
sont trouvées. Les solutions obtenues sont toutes Pareto optimales (e¢ caces) mais pas
nécessairement supportées.

Phase3 : Recherche des solutions e¢ caces dans les sous-espaces. Cette dernière
phase consiste à rechercher dans chacun des sous-espaces délimités par deux solutions adja-
centes obtenues lors de la phase précédente, toutes les solutions e¢ caces (supportées et non
supportées) existantes. Cette méthode a donc l’avantage de découper l’espace de recherche
tout en restant plus indépendante de la structure des solutions e¢ caces. En e¤et, aucune
hypothèse n’est prise concernant la répartition des solutions supportées, puisque la deuxième
phase recherche des solutions qui ne sont pas forcément supportées (mais qui sont e¢ caces).
Remarquons, que pour cette méthode, suivant le type de méthode utilisée pour la
troisième phase, il peut être possible de trouver toutes les solutions d’une même partition
en une seule exécution.

2.3.4 Abécédaire de méthodes d’optimisation multi-objectifs [1]

Désignons par :
Z : Un vecteur objectif avec Z = (Z1 ; Z2 ; :::; Zk )T
Supposons que l’ensemble des solutions réalisables entières est …ni.

47
 2.3. Programmation linéaire multicritère en nombres entiers

Méthode de MOMIX( Multi-objectif à variables Mixte)[1]

C’est une méthode introduite par Teghem et Kunch, elle utilise le concept de Branch and
Bound interactive. La méthode comporte principalement deux phases.

Phase1 : Initialisation

Déterminer le premier point e¢ cace x0 en résolvant le problème suivant pour m = 0:

8
>
> min
>
<
(P (m) ) t:q m;k (Mm;k ck x) k = 1; [Link]; p
>
>
>
: x2S
m

où S0 = S ; Mm;k la valeur optimale de la k ieme fonction objectif sur Sm et

m;k = p
P
m;k
le poids de la k ieme fonction objectif .
m;i
i=1

Phase2.

La méthode Branch and Bound interactive est utilisée en deux étapes:

Première étape : Procédure descendante. Soit la mieme itération.

(m 1)
- Soit xm 1
le mieme compromis (solution e¢ cace) et zk = ck xm 1
la valeur corre-
spondante pour la meme fonction objectif.
- Le DM (decision maker) indique le critère lm (1) 2 f1; 2; :::; pg à améliorer en priorité.
- Un nouveau compromis est obtenu en résolvant le problème (P(m) ) avec Sm = Sm 1 \
n o
xjzlm(1) (x) > zlm(1) : (xm 1 ) de façon que le critère lm (1) sera ainsi amélioré :

Tests d’arrêt. Plusieurs tests d’arrêts ont été dé…nit, on cite parmi :
- Sm = ?:
- Mm;k mm;k "k pour toutes les valeurs k ("k >0; f ixe).
- z^; le vecteur des meilleurs valeurs trouvées précédemment, est préféré au vecteur idéal
Mm relatif à DM:

48
 2.3. Programmation linéaire multicritère en nombres entiers

- Aucune amélioration n’a été apportée à z^ après un nombre d’itération …xé par le
décideur DM:

Deuxième étape : Procédure remontante Le but de cette étape est de scanner la ré-
gion d’admissibilité négligée à chaque itération de la procédure descendante pour un éventuel
meilleur compromis que z^ dans cette région.
- Le nœud correspondant au compromis xm 1
est séparé en p branches.
- Soit lm (k); k = 1; 2; :::; p l’ordre de priorité dans lequel le décideur veut voir améliorer
les p critères par rapport à ce compromis.
- Les p nœuds sont obtenus par l’adjonction respective des contraintes suivantes :
zlm (1) >zlmm (1)1
zlm (2) >zlmm (2)1 et
zlm (1) zlmm (1)1
...
zlm (p) >zlmm (p)1 et
zlm (k) >zlmm (k)
1
; k = 1; 2; :::; p:
L’ensemble de solutions admissibles est partitionné et à chaque sous nœud on résous le
problème (P(m) ):

Tests d’arrêt. Les mêmes tests d’arrêts que l’étape précédente sont utilisés

Méthode de [Link] et [Link]. [2]

C’est une méthode développée récemment, elle a été implémentée pour le problème de sac
à dos avec trois fonctions objectifs, dix contraintes et jusqu’a 30 variables et aussi pour le
problème d’a¤ectation généralisée.
Les auteurs ont considérés le problème M OILP avec paramètre coût entiers i.e.
8
< “ max ”Z = Cx
(P )
: x 2 D = fAx = b; x 0; x 2 Zn g
où C 2 Zp n
; A 2 Rm n
et b 2 Rm :

49
 2.3. Programmation linéaire multicritère en nombres entiers

Pour justi…er la méthode les auteurs ont utilisé la proposition suivante :

Proposition 2.3.1 Soient x1 ; x2 ; :::; xl des solutions e¢ caces du problème (P ) et

s = fx 2 Zn jCx Cxs g ((s = 1; :::; l))

Soit x une solution e¢ cace du problème

8
>
< “ max ”Z = Cx
l
(P ) Sl
>
: x2 D s
s=1
Alors x une solution e¢ cace du problème (P ). En plus, si le problème (P l ) devient
impossible (non réalisable) alors fCxs ; s = 1; :::; lg est l’ensemble de tous les points non
dominées dans l’espace des critères pour le problème (P ).

La méthode est basée sur le corollaire suivant :

Corollaire 2.3.1 Soient x1 ; x2 ; :::; xl des solutions e¢ caces du problème (P ) et

s = fx 2 Zn jCx Cxs g

Si x est une solution optimale pour le problème unicritère :

S
l
(P l ) : maxf t Cxjx 2 D sg
s=1
pour quelques valeurs de 2 Rp ; >0: Alors x est une solution optimale pour le problème
(P ):

La méthode

Étape1. Après avoir choisi le paramètre >0; on résout en première étape le problème de
programmation linéaire unicritère suivant :

t
(P0 ) max Cxj Ax = b; x 0; x 2 Zn

Si le problème n’admet pas de solution optimale, alors le problème (P ) n’a pas de solution
e¢ caces aussi. Sinon, une solution optimale x1 trouvée est e¢ cace pour le problème (P )
(par le corollaire):

50
 2.3. Programmation linéaire multicritère en nombres entiers

Puis, une suite de problèmes unicritères (où à chaque itération on ajoute des contraintes
éliminant les solutions déjà trouvées précédemment) est résolue séquentiellement.
après l itérations, si le problème (P(l 1) ) est irréalisable, alors l’algorithme prend …n.
Sinon, une nouvelle solution e¢ cace xl est générée et un nouveau problème (P(l) ) est dé…ni
en éliminant de l’ensemble d’admissibilité de (P(l 1) ) toutes les solutions véri…ant Cx Cxl :
Mathématiquement, ceci peut être traduit par les contraintes additionnelles suivantes :
P
p
(Cx)k ((Cxl )k + 1)ysl Mk (1 ykl ): pour k = 1; 2; :::; p et ykl 1; ykl 2 f0; 1g ; pour
k=1
k = 1; 2; :::; p:
où Mk est la borne inférieure pour toute valeur réalisable de la k ieme fonction objectif.

Étapes l. résoudre le problème :

8
>
> max t
Cx
>
>
>
>
>
> t:q
>
>
>
>
>
> Ax = b
>
>
>
>
>
< (Cx)k ((Cxs )k + 1)yks Mk (1 yks )
(Pl )
>
> pour s = 1; 2; :::; l; k = 1; 2; :::; p
>
>
>
> Pp
>
> yks 1; yks 2 f0; 1g
>
>
>
> k=1
>
>
>
> pour s = 1; 2; :::; l; k = 1; 2; :::; p
>
>
>
: x 0; x 2 Zn
Pour des problèmes à grandes tailles, l’énumération de toutes les solutions e¢ caces n’est
pas une tache facile, seulement un sous ensemble peut être généré on changeant le problème
(Pl ) en :

51
 2.3. Programmation linéaire multicritère en nombres entiers

8
>
> max t
Cx
>
>
>
>
>
> t:q
>
>
>
>
>
> Ax = b
>
>
>
>
>
< (Cx)k ((Cxs )k + fk )yks Mk (1 yks )
(Pl )
>
> pour s = 1; 2; :::; l; k = 1; 2; :::; p
>
>
>
> Pp
>
> yks 1; yks 2 f0; 1g
>
>
>
> k=1
>
>
>
> pour s = 1; 2; :::; l; k = 1; 2; :::; p
>
>
>
: x 0; x 2 Zn
où fk (fk 1; entier) représente l’amélioration minimale dans la k ieme fonction objectif.
La procédure s’arrête lorsque le problème (Ps ) devient impossible à résoudre. À la …n on
obtient l’ensemble des solutions e¢ caces entièrement ou une partie seulement qui intéresse
le décideur (selon la valeur de fk ).

2.3.5 Problèmes à variables binaires [1]

Un nombre considérable de problèmes en nombres entiers est formulé comme problèmes à

variables qui ne peuvent prendre que deux valeurs 0 et 1 (variables bivalentes), ce type
de problèmes est notès (M OBLP ) (Multiple Objective Binary Lineair Programming). En
plus des di¢ cultés liées aux problèmes en variables entières ou mixtes; dans le cas des
problèmes en variables binaires, la principale di¢ culté provient du grand nombre de variables
nécessaires pour modéliser des situations réelles. Cependant certains problèmes présentent
des structures particulières. Ils font partie de l’Optimisation Combinatoire. Il est alors
possible de tirer pro…t de l’information liée à cette structure pour faciliter leur résolution.
Ces problèmes sont très intéressants et souvent rencontrés dans l’industrie. La formulation
de tels problèmes est donné par :

(M OBLP ) “ max0 ”zk = ck x ; k = 1; 2; :::; p

x2S
n
où S 0 = fx 2 f0; 1g j Ax b g il est clair que le nombre de solutions peut croître
exponentiellement en fonctions de n:

52
 2.3. Programmation linéaire multicritère en nombres entiers

Méthode de Bitran[1]

Cette méthode est spéci…que aux problèmes à variables binaires et elle engendre toutes les
solutions e¢ caces.

L’auteur a considéré d’abord le problème suivant :

(PB1 ) “ max ”Zk = ck x ; k = 1; 2; :::; p ; avec S1 = B n (f(0; 1)n g) l’ensemble des som-
x2S1
mets de l’hypercube unité dans Rn : On a :

x 2 E(PB1 ) \ S 0 =) x 2 E(M OBLP )

Ceci veut dire qu’une solution e¢ cace pour le problème (PB1 ) et réalisable pour le prob-
lème (M OBLP ) est aussi e¢ cace pour ce dernier par contre une solution qui n’est pas
e¢ cace pour le problème (PB1 ) peut l’être pour le problème (M OBLP ):

i:e x 2
= E(PB1 ) ; x 2
= E(M OBLP )

L’algorithme proposé comporte trois étapes :

Étape1 : Caractériser l’ensemble des solutions e¢ caces du problème (PB1 ):
Étape2 : Parmi toutes ces solutions engendrées, déterminer celles qui sont réalisables
pour le problème (M OBLP ):
Étape3 : Adjoindre ensuite les autres solutions e¢ caces de (M OBLP ) non engendrées
dans l’etape1.
Algorithme
Étape1 : Caractérisation de E(PB1 )
Considérons l’ensemble V = v t 2 Rn ; t 2 T jCv t 0; vjt = 0; 1 ou 1 8j dit ensem-
ble de directions de préférence, où T est un ensemble d’indices.
On dit alors que x domine x0 dans la direction v t si et seulement si x0 = x + v t : Donc
Cx0 Cx:
Soit M (v t ) l’ensemble des points de S1 dominés dans la direction v t par un autre point
de S1 :
M (v t ) = xt;r j r = 1; 2; :::; R

53
 2.3. Programmation linéaire multicritère en nombres entiers

avec : 8
>
> 0 si vjt = 1
>
<
xt;r = 1 si vjt = 1
>
>
>
: 0 ou 1 si v t = 0
j

L’auteur a montré que cet ensemble peut être déterminé par l’ensemble des solutions
optimales du problème min0 v t x où S10 = fx 2 Rn j0 xj 1; 8j g est la relaxation linéaire
x2S1
S1 : L’ensemble E(PB1 ) est déterminé à partir de la résolution successive des problème relaxé,
noté (RPB1 ) pour di¤érentes directions v t ; t 2 T: Ce dernier permet de trouver des ensembles
S
M (v t ) puis E(PB1 ) = M (v t ):
t2T
Notons que quelques directions seulement sont examinées.

Remarque 2.3.1 A veut dire le complémentaire de l’ensemble A:

Étape2 : Détermination de l’ensemble E1 = E(PB1 ) \ S:

Pour cela il su¢ t de tester l’admissibilité des solutions de E(PB1 ):
Étape3 : Caractérisation de l’ensemble E(M OBLP ):
Pour déterminer l’ensemble des solutions non e¢ caces dans (PB1 ) et e¢ caces dans
(M OBLP ) noté par E2 on utilise la propriété suivante :

x 2 E2 ) s + v t 2
= S, 8v t ; t 2 T : x 2 M (v t ):

D’où
E(M OBLP ) = E1 [ E2

Méthode de Deckro et Winkofsky[1]

C’est une méthode spéci…que aux problèmes à variables binaires et elle est basée sur le
concept d’énumération implicite. La procédure est constituée de deux parties.
Première partie : Elle consiste à résoudre successivement et par énumération implicite
les p problèmes unicritères suivants :

max ck x 8k 2 f1; 2; :::; pg

x2S

54
 2.4. Conclusion

L’ensemble de toutes les solutions réalisables obtenues au cours de la résolution de ces

p problèmes sont considérées. Par une comparaison deux à deux, les solutions dominées
sont écartées et le reste des solutions forment un ensemble de solutions candidates pour
l’e¢ cacité, soit E1 :
Deuxième partie : Dans cette partie on applique simultanément à tous les critères
une énumération implicite qui ressemble à la précédente sauf qu’ici le processus de recherche
utilise deux concepts : évaluation et direction de préférence.

- Évaluation : Une solution réalisable x est éliminée si elle est dominée par une solution de
E1 : Un processus remontant est appliqué dès que toutes les complétions d’une solution
partielle non réalisable sont dominées par une solution de E1 .

- Direction de préférence : Considérons une solution partielle x, v est une direction de

préférence sur les variables libres de x si et seulement si :

ck (x + v) ck x; k = 1; 2; :::; p et
ck (x + v)>ck x
pour au moins un k; k 2 f1; 2; :::; pg

- S’il n’existe aucune direction de préférence on commence à remonter. Si non, la solution

partielle x est complétée dans la direction de v:

- On actualise l’ensemble E1 après chaque étape et à la …n on obtient E1 = E(M OBLP ):

2.4 Conclusion
Ces deux premiers chapitres avaient pour objectif de présenter dans un premier temps
les principales dé…nitions nécessaires à la présentation des problèmes d’optimisation mono-
objectif et multi-objectifs en variables continues et discrètes. Puis di¤érentes problématiques
liées aux spéci…cités du multi-objectifs, comme l’intervention du décideur dans le processus
de décision, le choix des méthodes d’optimisation à utiliser ou encore la complexité. De
même, les principales méthodes utilisées pour résoudre ces problèmes, de manière exacte,

55
 2.4. Conclusion

ont été indiquées. En particulier les di¤érences, en terme de di¢ culté de résolution et
de technique employée, découlant du type de variables (continues et discrets), du nombre
d’objectifs ou encore de la structure des problèmes, ont été mises en évidence a…n de montrer
l’importance et la di¢ culté de la recherche dans le domaine.
Nous nous sommes également astreints à cerner le cadre des études qui seront présentées
ci-après, à savoir l’optimisation “A posteriori”(cherchant à générer l’ensemble des solutions
e¢ caces) à l’aide des méthodes exactes.

56
Chapitre 3

Problème Bicritère d’a¤ectation

3.1 Introduction
Dans certains problèmes d’a¤ectations, plusieurs paramètres et critères sont impliqués dans
l’évaluation des divers aspects du problème; par exemple quand il s’agit d’a¤ecter des ou-
vriers à leurs postes de travail, il est important de considérer la compatibilité et la non
compatibilité de l’ouvrier pour un travail, ainsi que la priorité de chaque ouvrier et de
chaque poste de travail dans la chaîne de la production; donc plus de critères à gérer et
plus de paramètres à prendre en considération, d’où l’extension multi-critères du problème
d’a¤ectation. Dans ce chapitre nous formulerons le problème bicritère d’a¤ectation, et nous
présenterons quelques méthodes de résolutions existantes dans la littérature.

3.2 Problème multicritère d’a¤ectation

3.2.1 Formulation du Problème.

Soit le problème d’a¤ectation unicritère suivant :

57
 3.2. Problème multicritère d’a¤ectation
8
> Pn P n
>
> min z (x) = cij xij
>
>
>
> i=1 j=1
>
> P
n
< xij = 1 j = 1; 2; :::; n
(AP ) i=1
>
> Pn
>
> xij = 1 i = 1; 2; :::; n
>
>
>
>
j=1
>
: xij 2 f0; 1g 8 (i; j)

Quand il s’agit d’optimiser plusieurs fonctions objectifs en même temps, nous obtenons
le problème multicritère d’a¤ectation (note (M OAP )) :
8
> Pn P n
>
> “ min ”z (x) = ckij xij k = 1; 2; :::; n
>
>
k
>
> i=1 j=1
>
> P
n
< xij = 1 j = 1; 2; :::; n
(M OAP ) i=1
>
> P
n
>
> xij = 1 i = 1; 2; :::; n
>
>
>
>
j=1
>
: xij 2 f0; 1g 8 (i; j)

Pour k = 2; nous obtenons le problème bicritère d’a¤ectation.

8
> Pn P n
>
> “ min ”z (x) = ckij xij k = 1; 2
>
>
k
>
> i=1 j=1
>
> Pn
< xij = 1 i = 1; 2; :::; n
(BAP ) i=1
>
> Pn
>
> xij = 1 j = 1; 2; :::; n
>
>
>
>
j=1
>
: xij 2 f0; 1g 8 (i; j)

3.2.2 Positionnement du problème

Le problème d’a¤ectation unicritère (AP ) est un problème de la programmation linéaire en

nombre entier qui peut être résolu comme un programme linéaire dû à l’unimodularité total
de la matrice des contraintes; il est considéré comme un problème facile (de la classe P)
car des algorithmes permettant de le résoudre de manière exacte en temps polynomial sont
connus. Dell’Amico et al [11], donnent des tests comparatifs des di¤érentes implémentations
des ces algorithmes. Par contre le problème bicritère ou multicritère d’a¤ectation, comme
beaucoup de problème important est un problème N P-di¢ cile (voir [8]). Les premiers
papiers sur le problème traitent seulement les solutions e¢ caces supportées, en utilisant des
combinaisons convexes des fonctions objectifs, ou de la programmation par but.

58
 3.3. Solution du problème bicritère d’a¤ectation

3.2.3 Importance du problème

L’importance du problème d’a¤ectation peut être résumée en deux points essentiels :

- Les applications pratiques du problème d’a¤ectation qui sont nombreuses et inclurent

a¤ecter les professeurs aux classes d’école, les locataires aux appartements, les travaux
aux machines, etc....

- Le problème d’a¤ectation (AP ) surgit comme un sous-problème dans des systèmes de

décision, plus complexes (transport, voyageur de commerce, etc...).

3.3 Solution du problème bicritère d’a¤ectation

Contrairement au problème d’a¤ectation unicritère, qui est un problème facile (de la classe
P) car on connait un algorithme polynomial pour le résoudre, à savoir la méthode hongroise,
pour le problème multicritère d’a¤ectation, comme beaucoup de problèmes de même natures
(N P-di¢ cile), il n’existe pas d’algorithmes e¢ caces pour le résoudre de manière exacte.
Résoudre le problème bicritère d’a¤ectation revient à trouver un ensemble de solutions
e¢ caces. Dans la littérature, on trouve quelques algorithmes pour déterminer l’ensemble
de toutes les solutions e¢ caces [19], [21] ou une partie de cet ensemble [9]. Notons que la
plupart de méthodes sont de type “primal-dual”.

3.3.1 La méthode de Malhotra et al ([9]).

C’est une méthode de type “primal-dual”, basée sur le principe d’énumération dans l’espace
des critères pour générer l’ensemble des paires non dominées (z1 ; z2 ) dans l’ordre croissant
du premier critère z1 , et décroissant du deuxième z2 , on partant de la solution optimale
du premier critère z1 : Pour cela ils proposent de diviser le problème bi-critère en deux
problèmes unicritères (P1 ) et (P2 ) de matrices coûts C 1 ; C 2 respectivement et de travailler
simultanément sur les deux problèmes duaux (D1 ); (D2 ). À chaque itération la réalisabilité
et la non réalisabilité des contraintes duales est utilisée pour déterminer l’arête admissible

59
 3.3. Solution du problème bicritère d’a¤ectation

incidente à la base courante et parmi ces nouvelles bases celle qui fournit la plus petite
valeur de z1 est retenue pour l’itération suivantes.

Notation :

Soit le problème (BAP ) suivant :

8
> Pn P n
>
> “ min ”z (X) = ckij xij k = 1; 2
>
>
k
>
> i=1 j=1
>
> Pn
< xij = 1 i = 1; 2; :::; n
(BAP ) i=1
>
> Pn
>
> xij = 1 j = 1; 2; :::; n
>
>
>
>
j=1
>
: xij = 0; 1 i; j = 1; 2; :::; n
Et les deux problèmes unicritères (P1 ), (P2 ):

8 8
> Pn P n
> Pn P n
>
> “ min ”z (X) = c1ij xij >
> “ min ”z (X) = c2ij xij
>
>
1 >
>
2
>
> i=1 j=1 >
> i=1 j=1
>
> Pn >
> Pn
< xij = 1 i = 1; 2; :::; n < xij = 1 i = 1; 2; :::; n
(P1 ) i=1 et (P2 ) i=1
>
> Pn >
> Pn
>
> xij = 1 j = 1; 2; :::; n >
> xij = 1 j = 1; 2; :::; n
>
> >
>
>
>
j=1 >
>
j=1
>
: xij = 0; 1 >
: xij = 0; 1
i; j = 1; 2; :::; n i; j = 1; 2; :::; n

Et qu’on associée a leurs relaxations linéaires les deux problèmes duaux (D1); (D2)
respectivement suivants :

8
> Pn Pn
>
> “ max ” u 1
+ vj1
>
>
i
>
>
i=1 j=1
<
(D1 ) sous les contraintes
>
>
> u1i + vj1 c1ij i; j = 1; 2; :::; n
>
>
>
>
: avec u1 ; v 1 sans restriction de signes8i; 8j
i j

60
 3.3. Solution du problème bicritère d’a¤ectation

8
> Pn Pn
>
> “ max ” u 2
+ vj2
>
>
i
>
>
i=1 j=1
<
(D2 ) sous les contraintes
>
> u2 + v 2 c2 i; j = 1; 2; :::; n
>
>
>
>
i j ij
>
: avec u2 ; v 2 sans restriction de signes8i; 8j
i j

Notations
On note par Dij ( i; j = 1; 2; :::; n) les contraintes de (D1 ) tels que :

Dij = 0 si la contrainte Dij est satisfaite comme égalité.

Dij = 1 si la contrainte Dij est satisfaite comme inégalité.

Dij = 1 si la contrainte Dij est violée (non satisfaite).

0
De même on note Dij ( i; j = 1; 2; :::; n) les contraintes de (D2 ) tels que :

0 0
Dij =0 si la contrainte Dij est satisfaite comme égalité.

0 0
Dij = 1 si la contrainte Dij est satisfaite comme inégalité.

0 0
Dij =1 si la contrainte Dij est violée.

(p)
Soit Xl (p 2 N; p 1) une a¤ectation. On note par :

(p) (p)
- Bl les bases de l’a¤ectation Xl :

(p) 0
- Sl l’ensemble des indices (i; j) hors base tel que Dij = 1 et Dij =1:

n o
(p) (p) 0
Sl = (i; j) 2
= Bl j Dij = 1 et Dij =1

(p) (p) (p) (p)

Dé…nition 3.3.1 Soit Xl une a¤ectation, et Bl une base de Xl tel que 8 (i; j) 2
= Bl ;
(p) ^ (p) où
Dij 6= 1:On appelle arête admissible incidente à Xl , l’ensemble des solution Xl(ij)
(p) 0
(i; j) 2
= Bl tel que Dij = 1 et Dij 6= 1:

61
 3.3. Solution du problème bicritère d’a¤ectation

(p) P
n P
n
(p) P
n P
n
(p) (p)
- F = (z1 ; z2 ) z1 = c1ij x^l(ij) ; z2 = c2ij x^l(ij) ; (i; j) 2 Sl ; l = 1; 2; :::; qp ; où
i=1 i=1 i=1 i=1
^ (p) = (^
X
(p) (p)
xl(ij) ) les a¤ectations appartenant à l’arête admissible incidente à Xl :
l

(p)
n o
(p) (p)
- F^ (p) = F [ F (p 1)
(z1 ; z2 ) (avec p 2 N; p 2):
n o
- F (p) = (z1 ; z2 ) (z1 ; z2 ) est non dominees dans F^ (p)

La procédure

Initialisation Déterminer la solution optimale du premier critère, en cas de non unicité

de la solution (c-à-d il existe plusieurs solutions optimales pour (P1 )) ; celle qui fournit la
plus petite valeur de z2 est prise.
(1)
Soit Xl cette solution.
(1) (1) (1)
Xl est la première solution e¢ cace générée, et soit (z1 ; z2 ) les valeurs prise par cette
solution.

Itération1

(1) (1)
Déterminer Bl la base correspondante à Xl :

(1) (1)
Déterminer l’ensemble Sl ; F ; F (1) :

(2) (2)
Identi…er la deuxième paire e¢ cace (z1 ; z2 ) parmi les éléments de F (1) , celle cor-
(2)
respondante à la plus petite valeur de z1 et l’a¤ectation correspondante Xl ; l =
1; 2; :::; qp . Cette solution est retenue pour l’itération suivante.

(p-1)ieme Itération

(p 1) (p 1)
Déterminer Bl la base correspondante à l’a¤ectation Xl ; p 2 sélectionnée
l’itération précédente (i.e. l’a¤ectation qui fournit la plus petite valeur de z1 et en cas
de non unicité celle qui donne la plus petite valeur de z2 ).

(p 1) (p 1)
Déterminer l’ensemble Sl ;F ; F (p 1)
:

62
 3.3. Solution du problème bicritère d’a¤ectation

(p) (p)
Identi…er la pieme paire e¢ cace (z1 ; z2 ) parmi les éléments de F (p 1)
(celle correspon-
dante à la plus petite valeur de z1 ) et l’a¤ectation correspondante Xlp ; l = 1; 2; :::; qp .
Cette solution est retenue pour l’itération suivante.

pieme Itération

(p) (p)
Déterminer Bl la base correspondante à Xl ; p 2:

(p) (p)
Déterminer l’ensemble Sl ; F ; F (p) :

(p+1) (p+1)
Identi…er la (p + 1)ieme paire e¢ cace (z1 ; z2 ) parmi les éléments de F (p) (celle
(p+1)
correspondante à la plus petite valeur de z1 ) et l’a¤ectation correspondante Xl ;
l = 1; 2; :::; qp .

Test d’arrêt Le processus d’énumération s’arrête dès que F (N ) = ? ( N 2 N).

L’ensemble constitué par les paires engendrées à chaque itération, est l’ensemble des
solutions e¢ caces du problème bi-critères d’a¤ectation E(BAP ).
Notons en…n, que les auteurs ne précisent pas quelle méthode ont utilisé pour déterminer
les variables duales (ui ; vj ) ; i; j = 1; :::; n:

3.3.2 Exemple illustratif de Malhotra et al [9]

Soit le problème bi-critères d’a¤ectation dé…nit par les matrices coûts suivantes :
0 1 0 1
5 2 6 3 4 2 3 1
B C B C
B C B C
B2 4 3 1C B2 5 3 4C
C1 B
B
C et C 2 B
C B
C
C
B3 5 4 8C B5 3 4 5C
@ A @ A
6 7 4 5 3 4 2 3
(1) (1) (1)
z1 ; z2 = (10; 13) ; X1 fx12 = x24 = x31 = x43 = 1; les autres xij = 0g :
(1)
F = f(13; 11)g :
(1)
F (1) = F = f(13; 11)g :
(2) (2) (2)
z1 ; z2 = (13; 11) et X1 fx12 = x21 = x33 = x44 = 1; les autres xij = 0g

63
 3.3. Solution du problème bicritère d’a¤ectation

(2)
B1 = f(1; 2) ; (1; 4) ; (2; 1) ; (2; 4) ; (3; 3) ; (4; 3) ; (4; 4)g :
(2)
S1 = f(3; 2)g :
(2)
F = f(14; 8)g :
(2)
n n oo (2)
(2) (2)
F^ (2) = F [ F (1) z1 ; z2 =F [ ?:
(2)
=F :
F (2) = f(14; 8)g :
(3) (3) (3)
z1 ; z2 = (14; 8) ; et X1 fx14 = x21 = x32 = x43 = 1; les autres xij = 0g :
(3)
B1 = f(1; 2) ; (1; 4) ; (2; 1) ; (2; 4) ; (3; 2) ; (4; 3) ; (4; 4)g :
(3)
S1 = ?:
(3)
F = ?:
(3)
n n oo (3)
(3) (3)
F^ (3) = F [ F (2) z1 ; z2 =F [ ? = ?:
F (3) = ?
Fin de procédure.

A = f(10; 13) ; (13; 11) ; (14; 8)g

3.3.3 Adaptation de la méthode hongroise [19]

Cette méthode est une concrétisation du principe décrit par Malhotra et al [9] à l’aide
de la méthode hongroise pour le problème d’a¤ectation unicritère. Cette adaptation a
permis aux auteurs dans [19] de montrer que la méthode de Malhotra donne e¤ectivement
l’ensemble complet des solutions e¢ caces pour quelques exemples, mais elle échoue pour
d’autres exemples. Ils donneront un contre exemple.
Comme vu ci-dessus, la méthode [9], propose de déterminer à chaque itération la base
admissible correspondante à la solution optimale courante. L’adaptation de la méthode
hongroise, nécessite donc, une procédure pour déterminer une base duale admissible cor-
respondante à la solution optimale déterminée par la méthode hongroise, pour cela, [19]
propose une procédure pour construire une telle base.

64
 3.3. Solution du problème bicritère d’a¤ectation

Construction d’une base duale admissible correspondante à une solution opti-

male obtenue par la méthode hongroise [19].

Initialisation ~ la solution optimale obtenue par la méthode hongroise et soit :

Soit X

I1 = f(ip ; p)j p = 1; :::; ng les a¤ectations correspondantes:

Rappelons que dans un problème d’a¤ectation, il y’a :

- 2n contraintes; (2n 1) contraintes linéairement indépendantes et donc (2n 1) variables

de base.
8
< (2n 1) variables de base
- n2 variables :
: n2 (2n 1) variables hors base:
8
>
> n variables (celles correspondantes aux n a¤ectations) sont
>
<
- (2n 1) variables de base : strictement positives et égales à 1
>
>
>
: n 1 variables égale à 0

~ revient à …xer (n
Déterminer ces (2n 1) variables de base pour la solution optimale X
1) variables supplémentaires d’indices (i; j) qui seront de base, en plus des n paires d’indices
correspondantes aux n a¤ectations de I1 : Ces de (2n 1) variables doivent déterminées, en
plus une base duale admissible étant donné que la solution est optimale, c’est à dire une
solution duale fui ; vj ; i; j = 1; 2; :::; ng et donc 2n variables duales (ui ; vj ); i; j = 1; 2; :::; n,
véri…ants
8 (par le théorème des écarts complémentaires) :
>
> (2n 1) égalités ui + vj = cij 8(i; j) 2 IB (1; 1)
>
>
>
>
< avec jIB j = 2n 1 et I1 IB
(1)
>
> n2 (2n 1) inégalités ui + vj cij 8(i; j) 2 IHB (2; 2)
>
>
>
>
: avec IHB complémentaire de IB par rapport aux n2 paires (i; j)

La méthode hongroise fournit les n paires d’indices I1 ; et une solution duale admissible
(non nécessairement
8 de base) véri…ant :
< n egalites u + v = c 8(i; j) 2 I1 (2:1)
i j ij
(2)
: n2 n inegalites u + v cij 8(i; j) 2 I2 = f(i; j)j x~ij = 0g (2:2)
i j

65
 3.3. Solution du problème bicritère d’a¤ectation

Procédure de construction

Itération 1 Fixons une variable duale arbitrairement choisit soit vn à une valeur
arbitraire soit 0:
Pour le couple (in ; n) 2 I1 (i:e uin + vn = cin n )

(2:1)
vn = 0 ) uin = cin n vn

(vn ; uin ) étant …xées, portées dans les contraintes (2; 2) où …gurent ces deux variables,
on déduit des bornes supérieurs pour les (2n 1) variables restantes (car on a …xée deux
variables parmi 2n variables) .
D’où les bornes supérieures suivantes :
8
< v f ixee ! u ui 8i 6= in (3:1)
n i
: u f ixee ! v v 8j 6= n (3:2)
in j j

Pour déterminer les 2(n 1) variables restantes, on procède comme suit :

- Fixer une variable parmi ces 2(n 1) variables arbitrairement, soit v(n 1) ; et soit l’écart
type positif par rapport à sa borne supérieure, telle que :
8
< v
(n 1) = v (n 1) (4:1)
: avec 0 (6:0)

La contrainte (2:1) dans laquelle cette variable intervienne fournit la valeur de l’autre
variable présente dans cette contrainte :
soit :
ui(n 1)
+ v(n 1) = ci(n 1) (n 1) ) ui(n 1)
= ci(n 1) (n 1) v(n 1) ; avec v(n 1) = v (n 1) .
D’où
ui(n 1)
= ci(n 1) (n 1) v (n 1) + ((4,2))

- Pour que la contrainte (3:1) soit véri…ée par cette variable : ui(n 1)
ui(n 1)
; il faut que

ci(n 1) (n 1) v (n 1) + ui(n 1)
((5,1))

66
 3.3. Solution du problème bicritère d’a¤ectation

Ce qui nous fournit une borne supérieur pour le paramètre :

ui(n 1)
ci(n 1) (n 1) v (n 1) ((6,1))

En portant la valeur (4:1) dans les (n 2) contraintes (2:2) faisant intervenir simultané-
ment les (n 2) variables ui (i 6= in ; i(n 1) ) et la variable v(n 1) ,

on obtient :

ui ci(n 1) v (n 1) + ((5,2))

Ces conditions (5:2) portées dans les (n 2) contraintes (2:1) faisant intervenir simul-
tanément uiJ (ij 6= in ; i(n 1) ) et vj (j 6= n; n 1) : uij + vj = cij j fournissent une condition
sur les variables vj :

vj cij j cij (n 1) + v (n 1) ((5:3))

Pour que la contrainte (3:2) soit véri…ée par cette variable il faut que : cij j cij (n 1) +
v (n 1) v j ; j 6= n; n 1; ce qui nous fournit des bornes inférieures sur la valeur du
paramètre

cij j cij (n 1) + v (n 1) vj ((6; 2))

De même pour la valeur (4:2) :

En portant cette valeur dans les (n 2) contraintes (2:2) faisant intervenir la variable
ui(n 1)
et les (n 2) variables vj (j 6= n; n 1); on aura :

vj ci(n 1) j
ci(n 1) (n 1) + v (n 1) ((5; 4))

67
 3.3. Solution du problème bicritère d’a¤ectation

Ces conditions (5; 4) portées dans les (n 2) contraintes (2:1) fournissent une condition
sur les variables uij (j 6= n; n 1) :

uij cij j ci(n 1) j

+ ci(n 1) (n 1) v (n 1) + ((5; 5))

Le respect de la contrainte (3:1) :

uij uij ) cij j ci(n 1) j
+ ci(n 1) (n 1) v (n 1) + uij , fournit une borne supérieur de
la valeur du paramètre :

uij cij j + ci(n 1) j

ci(n 1) (n 1) + v (n 1) ((6; 3))

En regroupant
8 les 2(n 1) conditions (6) sur :
< 0 (6:0)
: cij j cij (n + v (n vj (6:2)
1) 1)
et 8
< ui(n ci(n v (n (6:1)
1) 1) (n 1) 1)
: uij cij j + ci(n ci(n v (n (6:3)
1) j 1) (n 1) 1)
On aura

Avec
8
< = max(0; c cij (n + v (n vj ) ou j 6= n; n + 1 dans les deux cas
ij j 1) 1)
(8:2)
: = min(ui(n ci(n v (n
1) 1) (n 1) 1) ; uij cij j + ci(n 1) j
ci(n 1) (n 1) + v (n 1) )

La …xation du paramètre à une de ces bornes et entraînera deux conséquences :

1. Les variables ui(n 1)

et v(n 1) sont …xées par les relations (4:1); (4:2):

2.

a) Soit une contrainte (2.2) sera …xée à l’égalité. C’est le cas dans les deux situations
suivantes :

68
 3.3. Solution du problème bicritère d’a¤ectation

= =0:

Par la relation (4:1) : v(n 1) = v (n 1) ce qui entraine par la relation (3:2) :

v (n 1) = cin (n 1) uin que v(n 1) = cin (n 1) uin :

D’où une contrainte (2:2) serrée : uin + v(n 1) = cin (n 1) .

= = ui(n 1)
ci(n 1) (n 1) v (n 1) :

Par la relation (4:2) ui(n 1)

= ci(n 1) (n 1) v (n 1) + ! = ui(n 1)
ci(n 1) (n 1) +
v (n 1) ! ui(n 1)
ci(n 1) (n 1) v (n 1) = ui(n 1)
ci(n 1) (n 1) + v (n 1)

D’où ui(n 1)
= ui(n 1)
:

Ce qui entraine par la relation (3:1) ui(n 1)

= ci(n 1) n
vn que ui(n 1)
= ci(n 1) n
vn ;
d’où une contrainte(2:2) serrée : ui(n 1)
+ vn = ci(n 1) n
:

b) Soit deux autres variables seront …xées et deux contraintes de (2:2) seront serrées. C’est
le cas dans les deux situations suivantes :

= = cij j cij (n 1) + v (n 1) vj :

Par la relation (5; 3) on a que vj cij j cij (n 1) + v (n 1) ce qui implique vj vj

alors que par (3:2) on a vj v j ; d0 ou vj = v j :

vj = v j entraine par la relation (3:2)( vj = cin j uin ): vj = cin j uin ; d’où une
contrainte (2:2) serrée : uin + vj = cin j :

Mais par (2:1) on a que uij + vj = cij j ! uij + v j = cij j ! uij = cij j v j ; et par
(4:1) : v(n 1) = v (n 1) ! v(n 1) = v (n 1) cij j + cij (n 1) v (n 1) + v j ! v(n 1) =
cij j + cij (n 1) + v j et dés lors uij + v(n 1) = (cij j v j ) + ( cij j + cij (n 1) + vj ) !
0
uij + v(n 1) = cij (n 1) :d où une contrainte (2:2) serrée : uij + v(n 1) = cij (n 1) :

= = uij cij j + ci(n 1) j

ci(n 1) (n 1) + v (n 1) :

69
 3.3. Solution du problème bicritère d’a¤ectation

Par la relation (5:5) on a que uij cij j ci(n 1) j

+ ci(n 1) (n 1) v (n 1) + ! uij uij
alors que par (3:1) on a uij uij ; d0 ou uij = uij :

uij = uij entraine par la relation (3:1) (uij = cij n vn ) : uij = cij n vn ; d’où une
contrainte (2:2) serrée : uij + vn = cij n :

Mais par (2:1) on a que uij + vj = cij j ! vj = cij j uij ! vj = cij j uij ; et par
(4:1) : ui(n 1)
= ci(n 1) (n 1) v (n 1) + ! ui(n 1)
= uij cij j + ci(n 1) j
, et dés lors
ui(n 1)
+ vj = (uij cij j + ci(n 1) j
) + (cij j uij ) ! ui(n 1)
+ vj = ci(n 1) j
; d’où une
contrainte (2:2) serrée : ui(n 1)
+ vj = ci(n 1) j
:

Notons à la …n que la base obtenue par cette méthode n’est pas unique, à chaque fois
qu’on change le choix des variables vj et des paramètres , on trouve une base di¤érente mais
toujours duale admissible étant donné que le problème d’a¤ectation est fortement dégénéré.
Soit le problème d’a¤ectation unicritère dé…nit par la matrice coût suivante :
0 1
5 1 4 7
B C
B C
B6 2 2 6C
C=B B
C
C
B2 8 4 4C
@ A
3 5 7 1

Initialisation Par application de la méthode hongroise, nous obtenons le tableau op-

timal suivant :
0 1
4 (0) 3 6
B C
B C
B4 0 (0) 4 C
C=B
B
C
C
B(0) 6 2 2C
@ A
2 4 6 (0)

e
Telle que X x12 = x23 = x31 = x44 = 1: Avec I1 = f(1; 2) ; (2; 3) ; (3; 1) ; (4; 4)g ;
I2 = f(1; 1) ; (1; 3) ; (1; 4) ; (2; 1) ; (2; 2) ; (2; 4) ; (3; 2) ; (3; 3) ; (3; 4) ; (4; 1) ; (4; 2) ; (4; 3)g :
D’où le système suivant :

70
 3.3. Solution du problème bicritère d’a¤ectation

8
>
> u1 + v2 =1
>
>
>
>
< u +v =2
2 3
(2:1)
>
> u3 + v1 =2
>
>
>
>
: u +v =1
4 4

8
>
> u1 + v 1 5
>
>
>
>
>
> u1 + v 3 4
>
>
>
>
>
> u1 + v 4 7
>
>
>
>
>
> u2 + v 1 6
>
>
>
>
>
> u2 + v 2 2
>
>
>
>
< u2 + v 4 6
(2:2)
>
> u3 + v 2 8
>
>
>
>
>
> u3 + v 3 4
>
>
>
>
>
> u3 + v 4 4
>
>
>
>
>
> u4 + v 1 3
>
>
>
>
>
> u4 + v 2 5
>
>
>
>
: u4 + v 3 7

Construction d’une base primale duale admissible:

Fixons v4 = 0 ) u4 = 1

8
>
> u 7 ) u1 = 7
>
< 1
v4 = 0 ) u2 6 ) u2 = 6 (3:1)
>
>
>
: u
3 4 ) u3 = 4

8
>
> v 2 ) v1 = 2
>
< 1
u4 = 1 ) v2 4 ) v2 = 4 (3:2)
>
>
>
: v
3 6 ) v3 = 6

71
 3.3. Solution du problème bicritère d’a¤ectation

Il reste 6 variables à déterminer avec le système suivant :

8
>
> u + v2 = 1
>
< 1
u2 + v3 = 2 (2:1)
>
>
>
: u +v =2
3 1

8
>
> u1 + v1 5
>
>
>
>
>
> u1 + v3 4
>
>
>
>
< u +v 6
2 1
(2:2)
>
> u2 + v2 2
>
>
>
>
>
> u3 + v2 8
>
>
>
>
: u +v 4
3 3

Soit v3 = v3 =6 ! v3 = 6 (4:1), avec 0 (6:0)

u2 + v 3 = 2 ) u2 = 2 v3 ) u2 = 2 (6 ); d’où u2 = 4+ (4:2)
u2 6) 4+ 6) 6+4! 10 (6:1)
v3 = 6 8: 8 8
< u +v 4 < u 4 (6 ) < u 2+
1 3 1 1
de (2:2) : ) ) (5:2)
: u +v 4 : u 4 (6 ) : u 2+
8 3 3
8 3 8 3
< u =1 v2 < 1 v 2+ < v 3
1 2 2
de (2:1) : ) ) (5:3)
: u =2 v1 : 2 v 2+ : v 4
83 8 1
8 1

< v 4 < 4 3 < 1

2
) ) (6:2)
: v 2 : 2 4 : 2
1
u2 = 4 +8 : 8
< v 6 ( 4+ ) < v 10
1 1
De (2:2) : ) (5:4)
: v 2 ( 4 + ) : v 6
8 2 8 2
8
< v =2 u < 2 u 10 < u 8+
1 3 3 3
De (2:1) : ) ) (5:5)
: v =1 u : 1 u 6 : u 5+
2 1
8 8 8 1 1

< u 4 < 4 8+ < 12

3
) ) (6:3)
: u 7 : 7 5 + : 12
1

72
 3.3. Solution du problème bicritère d’a¤ectation

On
28 obtient les systèmes
8 suivants
3 :
>
> 10 >
> 0 8
6>
< >
< 7 < = max(0; 1; 2) = 2
6 7
6 12 et 1 7) )2 10
4>
> >
> 5 : = min(10; 12; 12) = 10
>
: >
:
12 2
(4:1)
Posons = 10 ) v3 =8 4 et u2 = 6;8et la contrainte u2 + v4 6 serrée:
< u 7 < v 0
1 1
Les borne actualisées : et
: u 4 : v 4
3 2
Il reste quatre(4) variables à déterminer avec le système suivant :

8
< u +v =1
1 2
(2:1)
: u +v =2
3 1

8
< u +v 5
1 1
(2:2)
: u +v 8
3 2

Posons v1 = ; avec 0
v1 = ) u3 = 2 + ) 2:
v1 = ) u1 5+ ) v2 4 ) 0:
u3 = 2 + ) v2 6 ) u1 5+ ) 12:
D’où :

0 2

Soit = 2 ) v1 = 2 et u3 = 4 et la contrainte u3 + v4 4 serrée:

Il reste, v2 et u1 avec les bornes actualisées u1 7 et v2 4: Fixons v2 à sa borne
(2:1)
supérieure: i:e v2 = 4: ) u1 = 5; d’où la contrainte u2 + v2 2 serrée.
Nous avons déterminé la solution duale admissible de base suivante :
0 1
u1 = 5 ; u2 = 6 ; u3 = 4 ; u4 = 1
@ A
v1 = 2 ; v2 = 4 ; v3 = 4 ; v4 = 0
Telle que IB = I1 [ f(2; 2) ; (2; 4) ; (3; 4)g :

73
 3.3. Solution du problème bicritère d’a¤ectation

3.3.4 Application du principe de Malhotra et al [9]

Une itération consiste à déterminer la solution e¢ cace correspondante à la plus faible aug-
mentation de z1 alors que z2 doit diminuer, et cela en partant de la solution optimale de
premier critère.
Etant donné la dégénérescence de la base, on doit distinguer entre deux types de change-
ments de base classiques :

a) Ceux dégénérés, ne modi…ant pas la solution, appelés de type(a):

b) Ceux non dégénérés, produisent une nouvelle solution, appelés de type(b):

Procédure

Initialisation

f1 du premier critère z1 par la méthode hongroise tel

1- Déterminer la solution optimale X
~1
que X f~
xij = 1 si (i; j) 2 I; x~ij = 0 si nong ; où I est l’ensemble des a¤ectations
(1) (1)
correspondantes. Et soit (~
z1 = z1 ; z~2 = z2 ) les valeurs correspondantes des critères.

Remarque 3.3.1 Si la solution optimale du premier critère n’est pas unique, celle qui four-
nit la plus petite valeur de z2 est choisit.

2- Déterminer l’ensemble des (2n 1) indices de base optimale associée, ainsi que la solution
n o
(1) (1)
optimale duale correspondante ui ; vj ; i; j = 1; 2; :::; n .

(1)
3- Construire la matrice des coûts réduits C = (cij (1) )i;j=1;2;:::;n :
8
< c(1) = c(1) u(1) v (1) = 0 8(i; j) 2 I
ij ij i j B
Où
: c =c
(1) (1)
u
(1)
v
(1)
0 8(i; j) 2 I
ij ij i j HB
Où IB est l’ensemble des (2n 1) indices de base, et IHB l’ensemble des n2 (2n 1)
indices hors base.

4- Pour la même base, on détermine la solution optimale duale correspondante au deuxième

n o
(2) (2)
critère ui ; vj ; i; j = 1; 2; :::; n , et on construit la matrice des coûts réduits

74
 3.3. Solution du problème bicritère d’a¤ectation

(2)
n
(2) (2) (2) (2) (2)
C = (cij )i;j=1;2;:::;n : cij = cij ui vj = 0 8(i; j) 2 IB :
(2)
Pour les indices (i; j) 2 IHB ; il existe des indices pour lesquels cij 0, étant donné que
la solution de base n’est pas duale admissible pour le deuxième critère.
Á chaque itération
(P )
Déterminer l’ensemble suivant : (I S1 )

(1) (2)
I = f(i; j) 2 IHB jcij > 0; cij < 0g

Tester tous les changements de base possibles. Ne garder que les changements de base
de type (b):
Parmi toutes les solutions engendrées, seules les solutions non dominées sont retenues.
Celle correspondante à la plus petite valeur de z1 est prise pour l’itération suivante.
Le même principe et réappliqué à partir de cette nouvelle solution e¢ cace, et ainsi de
suite jusqu’aucune autre solution ne puisse être générée.
Cette adaptation, a permis de montrer que le principe, tel qu’il est présenté dans [9] ne
fonctionne pas toujours, et de le recti…er par la suite.
Un contre exemple a été construit pour montrer la défaillance du principe.

3.3.5 Contre exemple [19]

0 1 0 1
5 1 4 7 3 6 4 2
B C B C
B C B C
B6
(1) B
2 2 6C B1 3 8 3C
C B C et C (2) B C
C B C
B2 8 4 4C B5 2 2 3C
@ A @ A
3 5 7 1 4 2 3 5
(1) (1) (1)
z1 ; z2 = (6; 24) ; X1 = fx12 = x23 = x31 = x44 = 1; les autres xij = 0g :
Les tableaux des coûts réduits :
0 1 0 1
2 (0) 3 2 5 (0) 4 7
B C B C
B C B C
(1) B2 0 (0) 0 C B 4 0 (0) 0 C
C =B C ; C (2) = B C
B C B C
B(0) 8 4 0C B(0) 1 6 0C
@ A @ A
4 8 10 (0) 3 3 7 (0)

75
 3.3. Solution du problème bicritère d’a¤ectation

IB = f(1; 2) ; (2; 2) ; (2; 3) ; (2; 4) ; (3; 1) ; (3; 4) ; (4; 4)g :

IHB = f(1; 1) (1; 3) ; (1; 4) ; (2; 1) ; (3; 2) ; (3; 3) ; (4; 1) ; (4; 2) ; (4; 3)g :
I = f(1; 1) ; (1; 3) ; (1; 4) ; (2; 1) ; (3; 2) ; (3; 3) ; (4; 1) ; (4; 2) ; (4; 3)g :
Seules les a¤ectations (1; 3) ; (4; 1) ; (4; 3) permettent des changements de base de type
(b); elles conduisent respectivement aux solutions
X3 : x13 = x22 = x31 = x44 = 1 de valeur (9; 17) :
X4 : x12 = x23 = x34 = x41 = 1 de valeur (10; 21) :
X6 : x12 = x24 = x31 = x43 = 1 de valeur (16; 17) :
Seule la0solution X3 de valeur 1 (9; 17) est 0 non dominée. 1
1 3 (0) 1 2 7 (0) 3
B C B C
B C B C
(1) B 2 (0) 0 0 C (2) B 4 (0) 0 0C
C =B B C B C
C; C = B C
B(0) 8 4 0C B(0) 1 6 0C
@ A @ A
4 8 10 (0) 3 3 7 (0)
IB = f(1; 3) ; (2; 2) ; (2; 3) ; (2; 4) ; (3; 1) ; (3; 4) ; (4; 4)g :
IHB = f(1; 1) (1; 2) ; (1; 4) ; (2; 1) ; (3; 2) ; (3; 3) ; (4; 1) ; (4; 2) ; (4; 3)g :
I = f(2; 1) ; (3; 2) ; (3; 3) ; (4; 1) ; (4; 2) ; (4; 3)g
Seules les a¤ectations (4; 1) ; (4; 2) permettent des changements de base de type (b); elles
conduisent respectivement aux solutions
X5 : x13 = x22 = x34 = x41 = 1 de valeur (13; 14) :
X7 : x13 = x24 = x31 = x42 = 1 de valeur (17; 14) :
Ces deux solutions ne sont retenues puisqu’elles sont dominées.

3.3.6 Alternative proposée par Ulungu [19]

Contrairement à ce qui est fait par Malhotra et al [9], cette méthode propose de tester tous
les changements de bases même ceux avec des variables hors base qui, si elles rentrent dans
la base ne modi…e pas la solution; en faisant rentrer deux variables simultanément dans la
base y compris celles qui diminuent la valeur de z1 et augmente la valeur de z2 .
Une liste L conservera les solutions engendrées et à chaque itération seuls les changements
de base qui conduisent à des solutions non dominées par les solutions de L sont acceptés et

76
 3.3. Solution du problème bicritère d’a¤ectation

garder pour l’itération suivante.

La procédure

Soit le problème (BAP ).

8
> Pn P n
>
> \ min ”z (X) = ckij xij k = 1; 2
>
>
k
>
> i=1 j=1
>
> Pn
< xij = 1 i = 1; 2; :::; n
(BAP ) i=1
>
> Pn
>
> xij = 1 j = 1; 2; :::; n
>
>
>
>
j=1
>
: xij = 0; 1 i; j = 1; 2; :::; n
qu’on associée à sa relaxation linéaire les deux problèmes duaux suivants :
08 1
> P
n Pn
>
> \ max ” ( u k
+ vjk )
B> i C
B< i=1 j=1 C
B C k = 1; 2
B> u i + v j
k k k
cij C
@>> A
>
: uk ; v k sans restriction de signe8i et 8j
i j

Initialisation

~ 1 du premier critère z1 par la méthode hongroise tel

1- Déterminer la solution optimale X
~1
que X f~
xij = 1 si (i; j) 2 I; x~ij = 0 si nong ; où I est l’ensemble des a¤ectations
(1) (1)
correspondantes. Et soit (~
z1 = z1 ; z~2 = z2 ) les valeurs correspondantes des critères.

Remarque 3.3.2 Si la solution optimale du premier critère n’est pas unique, celle qui four-
nit la plus petite valeur de z2 est choisit.

2- Déterminer l’ensemble des (2n 1) indices de base optimale associée, ainsi que la solution
n o
(1) (1)
optimale duale correspondante ui ; vj ; i; j = 1; 2; :::; n .
(1)
3- Construire la matrice des coûts réduits C = (cij (1) )i;j=1;2;:::;n :
8
< c (1) = c(1) u(1) v (1) = 0 8(i; j) 2 I
ij ij i j B
Où
: c (1) = c (1)
ui
(1) (1)
vj 0 8(i; j) 2 IHB
ij ij
Où IB est l’ensemble des (2n 1) indices de base, et IHB l’ensemble des n2 (2n 1)
indices hors base.

77
 3.3. Solution du problème bicritère d’a¤ectation

4- Pour la même base, on détermine la solution optimale duale correspondante au deuxième

n o
(2) (2)
critère ui ; vj ; i; j = 1; 2; :::; n , et on construit la matrice des coûts réduits

(2)
n
(2) (2) (2)
C = (cij (2) )i;j=1;2;:::;n : cij (2) = cij ui vj = 0 8(i; j) 2 IB . Pour les indices
(i; j) 2 IHB ; il existe des indices pour lesquels cij (2) 0, étant donné que la solution de base
n’est pas duale admissible pour le deuxième critère.

Itération1 Soit (~ f1 ):
z1 ; z~2 ) les valeurs prises par la solution courante (X

Étape1. Déterminer les deux ensembles suivants :

I = f(i; j) 2 IHB jcij (1) > 0; cij (2) < 0g:

I = f(i; j) 2 IHB jcij (1) < 0; cij (2) > 0g:

Étape2. Tester tous les changements de base possibles. Pour cela appelons :
8
>
> I (I ) les a¤ectations deI(I ) qui conduisent à un changement de base de type(a):
>
< a a
et
>
>
>
: I (I ) celles de qui produisent un changement de type(b):
b b

a) Pour les changements de base de (i; j) 2 Ib [ Ib , les valeurs des critères deviennent :

8
< z = z~ + c (1)
1 1 ij
si(i; j) 2 Ib [ Ib
: z = z~ + c (2)
2 2 ij

Et soit (ib ; jb ) l’a¤ectation de Ib [ Ib fournissant le couple (z1 ; z2 ) non dominée par les
solution de L:

b) Pour les changements de base de (i; j) 2 Ia [ Ia , on distingue deux cas :

b.1) (i; j) 2 Ia :

78
 3.3. Solution du problème bicritère d’a¤ectation

L’imposition de (i; j) 2 Ia ne modi…e pas la valeur de (~

z1 ; z~2 ); pour cela, on est obligé
de faire rentrer une deuxième variable permettant d’e¤ectuer en rentrant dans la base avec
(i; j) un changement de type(b): Mais on peut pas tester toutes les variables, pour cela on
applique la procédure du choix suivante :

Procédure du choix. Appelons (l(i; j); p(i; j)) la variable candidate à rentrer simul-
tanément dans la base avec (i; j) :
Choix de (l(i; j); p(i; j))
On note par :

Iij le sous ensemble d’a¤ectation de IHB nf(i; j)g permettant d’e¤ectuer, en rentrant
dans la base avec (i; j) un changement de type(b):
0 1
n o (1) (1)
z1 = z~1 + cij + clp
(1) (1) (2) (2)
Iij = (l; p) 2 Iij cij + clp 0; cij + clp 0 , avec @ A:
(2) (2)
z2 = z~2 + cij + clp
(1) (1)
Parmi toutes les a¤ectations (l; p) 2 Iij , celle qui réalise le min (cij + clp ) est
(l;p)2Iij
0 1
(1) (1)
z1 = z~1 + cij + clp
choisit pour rentrer dans la base avec (i; j); avec @ A : En cas
(2) (2)
z2 = z~2 + cij + clp
(2) (2)
d’ex aequo(égalité), sélectionner celle de plus petite valeur de (cij + clp ):

L’introduction du couple de variables ((i; j); (l(i; j); p(i; j))) induit les valeurs :
0 1
(1) (1)
z1 = z~1 + cij + cl(i;j);p(i;j)
@ A:
(2) (2)
z2 = z~2 + cij + cl(i;j);p(i;j)

b.2) (i; j) 2 Ia : le même raisonnement

Procédure du choix Appelons (l (i; j); p (i; j)) la variable candidate à rentrer simul-
tanément dans la base avec (i; j):
Choix de (l (i; j); p (i; j))
On note par :

79
 3.3. Solution du problème bicritère d’a¤ectation

Iij le sous ensemble d’a¤ectations de IHB nf(i; j)g permettant d’e¤ectuer, en rentrant
dans la base avec (i; j) un changement de type(b):
0 1
n o (1) (1)
z1 = z~1 + cij + cl p
(1) (1) (2) (2)
Iij = (l ; p ) 2 Iij jcij + cl p 0; cij + cl p 0 , avec @ A:
(2) (2)
z2 = z~2 + cij + cl p

Parmi toutes les a¤ectations (l ; p ) 2 Iij , celle qui réalise le min (cij (1) + c(1)
l p
) est
(l ;p )2Iij
0 1
(1) (1)
z1 = z~1 + cij + cl p
choisit pour rentrer dans la base avec (i; j), avec @ A : En cas
(2) (2)
z2 = z~2 + cij + cl p
(2) (2)
d’ex aequo, sélectionner celle de plus petite valeur de (cij + cl p ):

L’introduction du couple de variables ((i; j); (l (i; j); p (i; j))) induit les valeurs :
0 1
(1) (1)
z = z~1 + cij + cl (i;j);p (i;j)
@ 1 A:
(2) (2)
z2 = z~2 + cij + cl (i;j);p (i;j)

Parmi toutes les nouvelles valeurs de (z1 ; z2 ) engendrées, soit par a), soit par b), est
sélectionné la paire correspondante à la plus petite valeur de z1 : Le changement de base
correspondant conduit à une nouvelle solution introduite dans L. Cette même solution est
retenue pour l’itération suivante.
Et ainsi de suite à chaque itération on détermine les ensembles I; I ; et les a¤ectations Ia
(Ia ); Ib (Ib ): Déterminer l’a¤ectation (ib ; jb ), les sous ensembles Iij ; (Iij ); Iij (Iij ) et choisir
les a¤ectations (l(i; j); p(i; j)); ((l (i; j); p (i; j))); et parmi toutes les nouvelles valeurs en-
gendrées, choisir celle qui corresponde à la plus faible valeur de z1 :

Test d’arrêt Le processus s’arrête pour l’une des possibilités suivantes :

Soit on trouve une solution dominée par les solutions de L.

Soit l’ensemble Ib (Ib ) est vide et pour toutes les a¤ectations (i; j) 2 Ia [ Ia , les sous
ensembles Iij et Iij sont vides.

La liste L ainsi construite, constitue l’ensemble des solutions e¢ caces du problème bi-
critères d’a¤ectation E(BAP ):

80
 3.3. Solution du problème bicritère d’a¤ectation

Exemple 3.3.1 0 1 0 1
5 1 4 7 3 6 4 2
B C B C
B C B C
B6 2 2 6C B1 3 8 3C
C (1) B
B
C et C (2) B
C B
C
C
B2 8 4 4C B5 2 2 3C
@ A @ A
3 5 7 1 4 2 3 5

Initialisation
0 1
u = 5; v1 = 2
B 1 C
B C
B u2 = 6; v2 = 4 C
B C
B C
B u3 = 4; v3 = 4 C
@ A
u4 = 1; v4 =0

~1
X x12 = x23 = x31 = x44 = 1; avec (z1 = 6; z2 = 24) :
IB = f(1; 2) ; (2; 2) ; (2; 3) ; (2; 4) ; (3; 1) ; (3; 4) ; (4; 4)g :
IHB = f(1; 1) (1; 3) ; (1; 4) ; (2; 1) ; (3; 2) ; (3; 3) ; (4; 1) ; (4; 2) ; (4; 3)g :
Tableaux des coûts réduits:
(1)
C :
(1) (1) (1) (1) (1) (1) (1)
c12 = c22 = c23 = c24 = c31 = c34 = c44 = 0
(1) (1) (1) (1) (1) (1) (1) (1)
c11 = c11 u1 v1 = 5 5 + 2 = 2; c13 = c13 u1 v3 = 4 5+4=3
(1) (1) (1) (1) (1) (1) (1) (1)
c14 = c14 u1 v4 = 7 5 0 = 2; c21 = c21 u2 v1 = 6 6+2=2
(1) (1) (1) (1) (1) (1) (1) (1)
c32 = c32 u3 v2 = 8 4 + 4 = 8; c33 = c33 u3 v3 = 4 4+4=4
(1) (1) (1) (1) (1) (1) (1) (1)
c41 = c41 u4 v1 = 3 1 + 2 = 4; c42 = c42 u4 v2 = 5 1+4=8
(1) (1) (1) (1)
c43 = c43 u4 v3 =7 1 + 4 = 10
(2)
C :
(2) (2) (2) (2) (2) (2) (2)
c12 = c22 = c23 = c24 = c31 = c34 = c44 = 0
(2) (2) (2) (2) (2) (2) (2) (2)
c11 = c11 u1 v1 = 3 6 2= 5; c13 = c13 u1 v3 = 4 6 5= 7
(2) (2) (2) (2) (2) (2) (2) (2)
c14 = c14 u1 v4 = 2 6 0= 4; c21 = c21 u2 v1 = 1 3 2= 4
(2) (2) (2) (2) (2) (2) (2) (2)
c32 = c32 u3 v2 = 2 3 0= 1; c33 = c33 u3 v3 = 2 3 5= 6
(2) (2) (2) (2) (2) (2) (2) (2)
c41 = c41 u4 v1 = 4 5 2= 3; c42 = c42 u4 v2 = 2 5 0= 3
(2) (2) (2) (2)
c43 = c43 u4 v3 =3 5 5= 7
D’où

81
 3.3. Solution du problème bicritère d’a¤ectation

~1
X x12 = x23 = x31 = x44 = 1; avec (z1 = 6; z2 = 24) :
0 1 0 1
2 (0) 3 2 5 (0) 4 7
B C B C
B C B C
(1) B2 0 (0) 0 C B 4 0 (0) 0 C
C =B C ; C (2) = B C
B C B C
B(0) 8 4 0C B(0) 1 6 0C
@ A @ A
4 8 10 (0) 3 3 7 (0)

Itération 1.

I = f(1; 1) ; (1; 3) ; (1; 4) ; (2; 1) ; (3; 2) ; (3; 3) ; (4; 1) ; (4; 2) ; (4; 3)g :

I = ? ) Ib = Ia = ?:

Ia = f(1; 1) ; (1; 4) ; (2; 1) ; (3; 2) ; (3; 3) ; (4; 2)g :

Ib = f(1; 3) ; (4; 1) ; (4; 3)g :

1.a) (i; j) 2 Ib [ Ib :
8 9
< z1 =6+3=9 >
>
>
>
(i; j) (1; 3) ) >
>
: z2 = 24 7 = 17 > >
8 >
>
>
>
< z1 = 6 + 4 = 10 =
(i; j) (4; 1) ) ) (ib ; jb ) (1; 3) avec (z1 ; z2 ) = (9; 17) :
: z2 = 24 3 = 21 > >
8 >
>
>
>
< z1 = 6 + 10 = 16 >
>
>
(i; j) (4; 3) ) >
>
>
: z2 = 24 7 = 17 ;

1.b) (i; j) 2 Ia (Ia = ?)

(i; j) (1; 1) ) Iij = f(2; 3) ; (3; 3)g Iij

8
< z = 6 + 2 + 4 = 12
1
(l (i; j) ; p (i; j)) (3; 3) )
: z = 24 5 6 = 13
2

(i; j) (1; 4) ) Iij = f(4; 2) ; (4; 3)g Iij

82
 3.3. Solution du problème bicritère d’a¤ectation

8
< z = 6 + 2 + 8 = 16
1
(l (i; j) ; p (i; j)) (4; 2) )
: z = 24 4 3 = 17
2

(i; j) (2; 1) ) Iij = f(2; 3) ; (4; 3)g Iij

8
< z = 6 + 2 + 4 = 12
1
(l (i; j) ; p (i; j)) (2; 3) )
: z = 24 4 6 = 14
2

(i; j) (3; 2) ) Iij = f(1; 1)g Iij

8
< z = 6 + 8 + 2 = 16
1
(l (i; j) ; p (i; j)) (1; 1) )
: z = 24 1 5 = 18
2

(i; j) (3; 3) ) Iij = f(1; 1) ; (2; 1)g Iij

8
< z = 6 + 4 + 2 = 12
1
(l (i; j) ; p (i; j)) (1; 1) )
: z = 24 6 5 = 13
2

(i; j) (4; 2) ) Iij = f(1; 1) ; (1; 3) ; (1; 4)g Iij

8
< z = 6 + 8 + 2 = 16
1
(l (i; j) ; p (i; j)) (1; 1) )
: z = 24 3 5 = 16
2

Par comparaison des valeurs de (z1 ; z2 ) ; la variable x13 rentre seule dans la base.
X3 x13 = x22 = x31 = x44 = 1; (z1 ; z2 ) = (9; 17) :

L = f(6; 24) ; (9; 17)g

83
 3.3. Solution du problème bicritère d’a¤ectation

Itération 2.
0 1 0 1
1 3 (0) 1 2 7 (0) 3
B C B C
B C B C
(1) B2 0 (0) 0 C B 4 0 (0) 0C
C =B C ; C (2) = B C
B C B C
B(0) 8 4 0C B(0) 1 6 0C
@ A @ A
4 8 10 (0) 3 3 7 (0)

I = f(2; 1) ; (3; 2) ; (3; 3) ; (4; 1) ; (4; 2) ; (4; 3)g :

I = f(1; 1) ; (1; 2) ; (1; 4)g

Ia = f(2; 1) ; (3; 2) ; (3; 3) ; (4; 3)g :

Ib = f(4; 1) ; (4; 2)g :

Ia = f(1; 1) ; (1; 4)g

Ib = f(1; 2)g

2.a) (i; j) 2 Ib [ Ib :
8 9
< z1 = 9 + 4 = 13 >>
>
>
(i; j) (4; 1) ) >
>
: z2 = 17 3 = 14 > >
8 >
>
>
>
< z1 = 9 + 8 = 17 =
(i; j) (4; 2) ) ) (ib ; jb ) (4; 1) avec (z1 ; z2 ) = (13; 14) :
: z2 = 17 3 = 14 > >
8 >
>
>
>
< z1 =9 3=6 >
>
>
>
(i; j) (1; 2) ) >
>
: z2 = 17 + 7 = 24 ;

2.b) (i; j) 2 Ia [ Ia :

2.b.1. (i; j) 2 Ia

(i; j) (2; 1) ) Iij = f(3; 2)g Iij

8
< z = 9 + 2 + 8 = 19
1
(l (i; j) ; p (i; j)) (3; 2) )
: z = 17 4 1 = 12
2

84
 3.3. Solution du problème bicritère d’a¤ectation

(i; j) (3; 2) ) Iij = f(2; 1)g Iij

8
< z = 9 + 8 + 2 = 19
1
(l (i; j) ; p (i; j)) (2; 1) )
: z = 17 4 1 = 12
2

(i; j) (3; 3) ) Iij = f(1; 1)g Iij

8
< z = 9 + 4 1 = 12
1
(l (i; j) ; p (i; j)) (1; 1) )
: z = 17 6 + 2 = 13
2

(i; j) (4; 3) ) Iij = f(1; 1) ; (1; 2) ; (1; 4)g Iij

8
< z = 9 + 10 3 = 16
1
(l (i; j) ; p (i; j)) (1; 2) )
: z = 17 7 + 7 = 17
2

2.b.2. (i; j) 2 Ia

(i; j) (1; 1) ) Iij = f(3; 2) ; (3; 3)g ) Iij = ?:

(i; j) = (1; 4) ) Iij = f(4; 2) ; (4; 3)g ) Iij = ?:

Par comparaison des valeurs de (z1 ; z2 ) ; les variables x33 et x11 rentrent simultanément
dans la base.
X4 x11 = x22 = x33 = x44 = 1; (z1 ; z2 ) = (12; 13) :

L = f(6; 24) ; (9; 17) ; (12; 13)g

Itération 3.
0 1 0 1
(0) 3 0 1 (0) 7 0 3
B C B C
B C B C
(1) B 3 (0) 0 0C (2) B 6 (0) 0 0C
C =B
B
C; C = B
C B
C
C
B 3 4 (0) 4C B4 5 (0) 6 C
@ A @ A
5 8 10 (0) 5 3 7 (0)

85
 3.3. Solution du problème bicritère d’a¤ectation

I = f(2; 1) ; (4; 1) ; (4; 2) ; (4; 3)g :

I = f(1; 2) ; (1; 4) ; (3; 1) ; (3; 4)g :

Ia = f(2; 1) ; (4; 1) ; (4; 3)g :

Ib = f(4; 2)g :

Ia = f(1; 2) ; (1; 4) ; (4; 3)g :

Ib = f(3; 1)g :

3.a) (i; j) 2 Ib [ Ib :
8 9
< z1 = 12 + 8 = 20 >
>
>
>
(i; j) (4; 2) ) >
>
: z2 = 13 3 = 10 =
8 ) (ib ; jb ) (3; 1) solution dominée
< z1 = 12 4 = 9 > >
>
(i; j) (3; 1) ) >
>
>
: z2 = 13 + 3 = 17 ;

3.b) (i; j) 2 Ia [ Ia :

3.b.1. (i; j) 2 Ia

(i; j) (2; 1) ) Iij = f(1; 2) ; (3; 2)g ) Iij = ?:

(i; j) (4; 1) ) Iij = f(1; 2) ; (1; 4)g ) Iij = f(1; 4)g :

8
< z = 12 + 5 1 = 16
1
(l (i; j) ; p (i; j)) (1; 4) )
: z = 13 5 + 3 = 11
2

(i; j) (4; 3) ) Iij = f(3; 1) ; (3; 4)g Iij

8
< z = 12 + 10 4 = 18
1
(l (i; j) ; p (i; j)) (3; 4) )
: z = 13 7 + 6 = 12
2

3.b.2 (i; j) 2 Ia

86
 3.3. Solution du problème bicritère d’a¤ectation

(i; j) (1; 2) ) Iij = f(2; 1) ; (3; 1) ; (4; 1)g ) Iij = f(2; 1) ; (3; 1)g :

8
< z = 12 + 3 3 = 6
1
(l (i; j) ; p (i; j)) (3; 1) )
: z = 13 + 7 + 4 = 24
2

(i; j) (1; 4) ) Iij = f(4; 1)g ) Iij = ?:

(i; j) (3; 4) ) Iij = f(4; 1) ; (4; 2) ; (4; 3)g ) Iij = ?:

Par comparaison des valeurs de (z1 ; z2 ) ; x41 et x14 rentrent simultanément dans la base.
X4 x14 = x22 = x33 = x41 = 1; (z1 ; z2 ) = (16; 11) :

L = f(6; 24) ; (9; 17) ; (12; 13) ; (16; 11)g

Itération 4.
0 1 0 1
0 3 0 (0) 0 7 0 (0)
B C B C
B C B C
(1) B 3 (0) 0 1C B 6 (0) 0 3C
C =B C ; C (2) = B C
B C B C
B 3 4 (0) 3C B4 5 (0) 3C
@ A @ A
(0) 3 5 4 (0) 2 2 2

I = f(2; 1) ; (2; 4) ; (4; 3)g :

I = f(1; 2) ; (3; 1) ; (3; 4) ; (4; 4)g :

Ia = f(2; 1) ; (2; 4) ; (4; 3)g :

Ib = ?:

Ia = f(1; 2) ; (3; 1)g :

Ib = f(3; 4) ; (4; 4)g :

4.a) (i; j) 2 Ib [ Ib :

87
 3.3. Solution du problème bicritère d’a¤ectation
8
< z = 16 3 = 13
1
(i; j) (3; 4) ) Solution dominée
: z = 11 + 3 = 14
8 2
< z = 16 4 = 12
1
(i; j) (4; 4) ) Solution dominée
: z = 11 + 2 = 13
2

4.b) (i; j) 2 Ia [ Ia :

4.b.1. (i; j) 2 Ia :

(i; j) (2; 1) ) Iij = f(4; 2)g Iij

8
< z = 16 + 3 + 3 = 22
1
(l (i; j) ; p (i; j)) (4; 2) )
: z = 11 6 + 2 = 7
2

(i; j) (2; 4) ) Iij = f(1; 2)g ) Iij = ?:

(i; j) (4; 3) ) Iij = f(3; 1) ; (3; 4)g Iij

8
< z = 12 + 10 4 = 18
1
(l (i; j) ; p (i; j)) (3; 4) )
: z = 13 7 + 6 = 12
2

4.b2. (i; j) 2 Ia :

(i; j) (1; 2) ) Iij = f(2; 4)g Iij

8
< z = 16 3 + 1 = 14
1
(l (i; j) ; p (i; j)) (2; 4) ) Solution dominée
: z = 11 + 7 3 = 15
2

(i; j) (3; 1) ) Iij = f(4; 2) ; (4; 3); (4; 4)g ) Iij = f(4; 2) ; (4; 4)g

8
< z = 16 3 4 = 9
1
(l (i; j) ; p (i; j)) (4; 4) ) Solution dominée
: z = 11 + 4 + 2 = 17
2

Par comparaison des valeurs de (z1 ; z2 ) ; x21 et x42 rentrent simultanément dans la base.
X5 x14 = x21 = x33 = x42 = 1; (z1 ; z2 ) = (22; 7) :

L = f(6; 24) ; (9; 17) ; (12; 13) ; (16; 11) ; (22; 7)g

88
 3.3. Solution du problème bicritère d’a¤ectation

Itération 5.
0 1 0 1
0 6 0 (0) 0 5 0 (0)
B C B C
B C B C
(1) B(0) 6 3 2C (2) B (0) 4 6 3 C
C =B
B
C; C = B
C B
C
C
B 3 1 (0) 3C B4 3 (0) 3 C
@ A @ A
0 (0) 5 4 0 (0) 2 2

I = f(4; 3)g :

I = f(1; 2) ; (2; 2) ; (2; 3) ; (2; 4) ; (3; 1) ; (3; 4) ; (4; 4)g :

Ia = f(4; 3)g :

Ib = ?:

Ia = f(1; 2) ; (2; 3) ; (3; 1) ; (4; 4)g :

Ib = f(2; 2) ; (2; 4) ; (3; 4)g :

5.a) (i; j) 2 Ib [ Ib :
8 9
< z = 22 6 = 16 >
>
1 >
(i; j) (2; 2) ) Solution dominee >
>
>
: z = 7 + 4 = 11 >
>
8 2 >
>
>
>
< z = 22 2 = 20 =
1
(i; j) (2; 4) ) ) (ib ; jb ) (3; 4)avec
: z = 7 + 3 = 10 >
>
8 2 >
>
>
>
< z = 22 3 = 19 >
>
1 >
>
(i; j) (3; 4) ) >
>
: z = 7 + 3 = 10 ;
2

(z1 ; z2 ) = (19; 10)

5.b) (i; j) 2 Ia [ Ia :

5.b.1. (i; j) 2 Ia :

(i; j) (4; 3) ) Iij = f(3; 2)g ) Iij = ?:

89
 3.3. Solution du problème bicritère d’a¤ectation

5.b.2. (i; j) 2 Ia :

(i; j) (1; 2) ) Iij = f(4; 4)g Iij

8
< z = 22 6 4 = 12
1
(l (i; j) ; p (i; j)) (4; 4) ) Solution dominée
: z = 7 + 5 + 2 = 14
2

(i; j) (2; 3) ) Iij = f(3; 1) ; (3; 2); (3; 4)g Iij

8
< z = 22 3 3 = 16
1
(l (i; j) ; p (i; j)) (3; 4) ) Solution dominée
: z = 7 + 6 + 3 = 16
2

(i; j) (3; 1) ) Iij = f(2; 4) ; (2; 3)g Iij

8
< z = 22 3 3 = 16
1
(l (i; j) ; p (i; j)) (2; 3) ) Solution dominée
: z = 7 + 4 + 6 = 17
2

(i; j) (4; 4) ) Iij = f(1; 2)g Iij

8
< z = 22 4 6 = 12
1
(l (i; j) ; p (i; j)) (1; 2) ) Solution dominée
: z = 7 + 2 + 5 = 14
2

Par comparaison des valeurs de (z1 ; z2 ) ; x34 rentre seule dans la base.
X6 x13 = x21 = x34 = x42 = 1; (z1 ; z2 ) = (19; 10) :

L = f(6; 24) ; (9; 17) ; (12; 13) ; (16; 11) ; (22; 7) ; (19; 10)g

Itération 6.
0 1 0 1
0 6 (0) 0 0 5 (0) 0
B C B C
B C B C
(1) B(0) 6 3 2C (2) B(0) 4 6 3C
C =B
B
C; C = B
C B
C
C
B0 4 3 (0) C B 1 0 3 (0)C
@ A @ A
0 (0) 5 4 0 (0) 2 2

I = f(3; 3) ; (4; 3)g :

I = f(1; 2) ; (2; 2) ; (2; 3) ; (2; 4) ; ; (4; 4)g :

90
 3.3. Solution du problème bicritère d’a¤ectation

Ia = f(4; 3)g :

Ib = f(3; 3)g :

Ia = f(1; 2) ; (4; 4)g :

Ib = f(2; 2) ; (2; 3) ; (2; 4)g :

6.a) (i; j) 2 Ib [ Ib :
8
< z = 19 + 3 = 22
1
(i; j) = (3; 3) ) Solution dominee
: z = 10 3=7
8 2
< z = 19 3 = 16
1
(i; j) = (2; 3) ) Solution dominee
: z = 10 + 6 = 16
8 2
< z = 19 2 = 17
1
(i; j) = (2; 4) ) Solution dominee
: z = 10 + 3 = 13
8 2
< z = 19 6 = 13
1
(i; j) = (2; 2) ) Solution dominee
: z = 10 + 4 = 14
2

6.b) (i; j) 2 Ia [ Ia :

6.b.1. (i; j) 2 Ia :

(i; j) (4; 3) ) Iij = f(1; 2)g ) Iij = ?:

6.b.2. (i; j) 2 Ia :

(i; j) (1; 2) ) Iij = f(3; 4)g Iij

8
< z = 19 6 + 5 = 18
1
(l (i; j) ; p (i; j)) (3; 4) ) Solution dominée
: z = 10 + 5 2 = 13
2

(i; j) (4; 4) ) Iij = f(3; 2)g Iij

8
< z = 19 4 + 4 = 19
1
(l (i; j) ; p (i; j)) (3; 2) ) Solution dominée
: z = 10 + 2 0 = 12
2

91
 3.3. Solution du problème bicritère d’a¤ectation

Aucune nouvelle solution. Toutes les solutions engendrées sont dominées. Fin d’itération.

L = f(6; 24) ; (9; 17) ; (12; 13) ; (16; 11) ; (22; 7) ; (19; 10)g = E (BAP ) :

La méthode décrite ci-dessus a été programmée à l’aide du logiciel Delphi 5. Ce pro-

gramme peut déterminer l’ensemble de toutes les solutions e¢ caces du problème bi-critères
d’a¤ectation (s’il en existent), ou alors un sous-ensemble de solutions e¢ caces .
Les tests e¤ectués sur une variété de problèmes (BAP ) ont révélé que l’e¢ cacité de la
méthode dépend de la base duale admissible trouvée, car pour certaines bases, le programme
donne l’ensemble de toutes les solutions e¢ caces, pour d’autres bases correspondantes à
la même solution, seulement un sous ensemble est trouvé. Par exemple pour l’exemple
illustratif, il su¢ t de prendre pour la dernière itération v2 = v2 au lieu de v1 = v1
pour que la méthode ne donne pas toutes les solutions e¢ caces malgré que la base obtenue
est duale admissible.
Nous avons aussi remarquer que, pour d’autres bases des solutions qui ne sont pas
e¢ caces ont été engendrées.

3.3.7 Méthode de deux phases [19], [21]

Contrairement à la méthode précédente, celle-ci travaille sur un problème d’a¤ectation uni-

critère dont la fonction objectif est une agrégation linéaire des deux autres. Comme vu
ci-dessous, la première phase va déterminer toutes les solutions e¢ caces supportées, tandis
que la seconde détermine les solutions e¢ caces non supportées.

Phase (I) : détermination de SE(P )

Cette phase est identique à celle de Aneja et nair [19] pour le problème de transport.
Soit S la liste des solution e¢ caces supportées; cette liste est initialisée par les deux so-
~ 1 et X
~ 2 de valeurs respectives (~(1) (1)
lutions optimales et e¢ caces en cas de non unicité X z1 ; z~2 )
(2) (2)
et (~
z1 ; z~2 ) des deux critères. Les solutions de S sont rangées dans l’ordre croissant de
premier critère z1 :

92
 3.3. Solution du problème bicritère d’a¤ectation

Une agrégation est réalisée à l’aide des poids :

(t) (r) (s) (t) (s) (r)

a1 = z2 z2 et a2 = z1 z1

(r) (1) (r) (1) (s) (2) (s) (2)

Où (z1 = z~1 ; z2 = z~2 ) et (z1 = z~1 ; z2 = z~2 ) sont les valeurs données par les
deux premières solutions e¢ caces et supportées consécutives X r ; X s de S.
On obtient le problème d’a¤ectation unicritère P (t) de matrice coût C (t)

(t) (1) (t) (2)

C (t) = (a1 cij + a2 cij )

Soit fX (t) ; t 2 T g l’ensemble des solutions optimales de ce critère obtenues par la méth-
ode hongroise.
Deux cas se manifestes :

Premier cas : fX r ; X s g \ X (t) ; t 2 T = ?: Alors les solutions X (t) t 2 T sont des

nouvelles solutions e¢ caces supportées inclues dans S.

Deuxième cas : fX r ; X s g X (t) ; t 2 T :

Si X r et X s sont les deux seules solutions X (t) fX r ; X s g \ X (t) ; t 2 T = fX r ; X s g ,

donc il n’y a pas d’autres solutions supportées entre X r et X s

Dans le cas contraire, c.à.d qu’il existe d’autres solutions X (t) , alors ces dernières sont
de nouvelles solutions supportées. Ces nouvelles solutions, si elles existent, elles sont
placées dans un ensembles particulier note S 0 .

On continu la procédure tant que les autres paires n’ont pas été examinées, en particulier
les paires (X r ; X t ) et (X t ; X s ) .
À la …n de cette phase, on obtient :

0
SE(BAP ) = S [ S

93
 3.3. Solution du problème bicritère d’a¤ectation

Phase (II) : Détermination de E(P )nSE(P )

L’objectif de cette phase est de rechercher, pour chaque paire de solution (X r ; X s ) de SE(P ),
(u) (u)
s’il existe des solutions e¢ caces non supportées X u : (z1 ; z2 ) véri…ant :
0 1
(r) (u) (s)
z < z 1 < z1
@ 1 A
(r) (u) (s)
z1 > z2 > z2

La procédure

Soit P (t) le problème associé au couple (X r ; X s ) est optimisé.

n o
(t)
Soit L = (i; j) cij > 0

(t)
Les a¤ectations étant classées dans l’ordre croissant des valeurs cij .
Les a¤ectations de L ne sont pas toutes candidate à être imposées, certaines d’elles
peuvent être éliminées de L; se sont celles qui conduisent à des solutions dominées. Pour se
faire cette phase propose de calculer une borne inférieure de l’augmentation pour les trois
cas suivants :

Du critère correspondant à la matrice C (t) par rapport à la valeur prise par Z r ; Z s .

Du critère z1 par rapport à la valeur z1r :

Du critère z2 par rapport à la valeur z2s :

Test1 : test sur le problème P (t) Soit (i ; j ) une a¤ectation de L.

Et soit ir ; is ; jr ; js des indices tel que : xir j = xi jr = xis j = xi js = 1:
1.a) Par rapport à X r
L’imposition de (i ; j ) impose au minimum de créer un nouveau zéro dans la ligne ir et
dans la colonne jr .

Si ce nouveau zéro est créé en (ir ; jr ) la borne inférieur de l’augmentation de z (t) sera
(t)
cir jr .

Si deux nouveaux zéros sont créés, la borne inférieure de l’augmentation z (t) sera :

94
 3.3. Solution du problème bicritère d’a¤ectation

(t) (t) (t)

s = min cis j + min cijs
j6=j i6=i

Alors la borne inférieur de l’augmentation de z (t) pour ce test sera :

(t) (t) (t) (t) (t)

lt = ci j + min cir jr ; cis js ; r ; s

Une a¤ectation peut être éliminée de la liste L si :

(t) (t)
lt a1 a2

(r)
Test2 : test d’augmentation de z1

~1
a) X r = X

L’a¤ectation (i ; j ) peut être éliminée de la liste L si :

(t)
l1 a2

(r)
Où l1 est la borne inférieur de l’augmentation de z1 engendrée par l’imposition de
l’a¤ectation (i ; j ) qui vaut :

(1) (1) (1) (1)

l1 = ci j + min ci1 j1 ; min ci1 j ; min cij1
j6=j i6=i

Avec i1 ; j1 ; des indices tel que: xi1 j =.xi j1 =1

~1
b) X r 6= X

L’a¤ectation (i ; j ) peut être éliminée de la liste L si :

!
(1) P (1) P (1) (t)
l10 = ci j + max min cij ; min cij a2
i6=i j6=j j6=j i6=i

95
 3.3. Solution du problème bicritère d’a¤ectation

(s)
Test3 : test d’augmentation de z2

~2
a) X s = X

L’a¤ectation (i ; j ) peut être éliminée de la liste L si :

(2) (2) (2) (2) (t)

l2 = ci j + min ci2 j2 ; min ci2 j ; min cij2 a1
j6=j i6=i

Avec i2 ; j2 indices tel quexi2 j =.xi j2 = 1. Les coûts réduits cij (2) sont ceux du critère
z2 relative à la solution X s :

~2
b) X s 6= X

L’a¤ectation (i ; j ) peut être éliminée de la liste L si :

!
(2) P (2) P (2) (t)
l20 = ci j + max min cij ; min cij a1
i6=i j6=j j6=j i6=i

Pour le reste (i.e. les a¤ectations qui ne sont éliminées par aucun des trois tests) deux
variantes existent pour la procédure :

les a¤ectations restantes de L sont imposées tour à tour et le même problème est
ré-optimisé; les solutions obtenues sont triées a…n de ne conserver que les solutions
e¢ caces et les a¤ectations sont considérées dans l’ordre de bornes d’augmentation
croissante. Dès qu’une nouvelle solution e¢ caces X u est trouvée, le test1 peut être
réappliqué est la borne inférieur de l’augmentation de z (t) sera :

(t) (u) (r) (t) (u) (s)

lt0 = max(a1 (z1 z1 ); a2 (z1 z1 ))

Pour chaque paire (X r ; X s ), il faut poursuivre l’optimisation de P (t) , en imposant en

plus de (i; j) 2 L, d’autres a¤ectations de L, jusqu’à ce que :

a) Soit on trouve une solution X u telle que :

0 1
(r) (u) (s)
z1 < z1 < z1
@ A
(r) (u) (s)
z2 > z2 > z2

96
 3.3. Solution du problème bicritère d’a¤ectation

(t) (t)
b)Soit z (u) z (t) + a1 a2
Cette méthode a été implémentée a…n d’engendrer des exemples numériques pour tester
son e¢ cacité. Cependant, ce procédé prend beaucoup du temps (voir [17]). En conséquence,
des méthodes d’approximation ont été proposées pour calculer les solutions e¢ caces avec
une durée de calcul raisonnable ( voir [14], [8]), ces mèthodes combinent entre méthodes
exactes et méthodes approchées.

97
Chapitre 4

Conclusion générale et perspectives

L’optimisation multi-objectifs (multicritère) est sans doute un axe de recherche primordial

pour les scienti…ques et les ingénieurs, non seulement à cause de la nature multi-critères
de la plupart des problèmes réels, mais aussi parce que de nombreuses questions restent
ouvertes dans ce domaine. Elle a pour caractéristique principale de fournir un ensemble
de solutions qui représentent l’ensemble des solutions e¢ caces. Dans le cas continu (où
l’ensemble d’admissibilité est convexe), cette tache est relativement facile car l’ensemble des
solutions e¢ caces peut être trouvé par combinaison convexe des critères ce qui est impossible
dans le cas entier (la propriété de convexité n’est pas conservée) où seulement un sous
ensemble est généré sauf pour quelques problèmes représentant une structure particulière.
Dans le cadre de ce travail nous avons réalisé une synthèse sur les méthodes de résolution
des problèmes unicritères et multicritères dans le cas continu et discret en précisant la
di¢ culté relative à la résolution de chaque type de problème. Ces méthodes ont été classées
selon l’intervention du décideur dans le processus de résolution et le but recherché.
Pour les méthodes exactes pour l’optimisation multi-objectifs, di¤érentes perspectives
sont envisageables. Tout d’abord, l’amélioration des performances de ces méthodes notam-
ment l’implémentation de ces dernières ce qui permettrait de résoudre des problèmes de
tailles plus grandes. Une autre perspective concerne le développement de nouvelles méth-
odes exactes ou l’adaptation des méthodes existantes pour des problèmes à plus de deux
objectifs ou encore la coopération entre méthodes exactes et approchées a…n de réduire le

98
 4. Conclusion générale et perspectives

temps de calcul.
Dans la classe des problèmes à variables binaires, en plus des di¢ cultés liées aux prob-
lèmes en variables discrètes, ces problèmes sou¤rent de l’explosion combinatoire ce qui rend
nécessaire pour toute méthode de résolution de considérer le temps de calcul. L’implémentation
de la méthode de l’adaptation de la méthode hongroise pour le problème bi-critères d’a¤ectation
proposée par Ulungu dans [19] présenté dans ce mémoire, nous a permis de constater que
pour des instances de moyennes tailles la méthode ne donne pas toutes les solutions e¢ caces
et que pour des bases correspondantes à la même solution optimale, elle donne toutes les
solutions e¢ caces et pour d’autres bases seulement un sous ensemble est généré et pour
d’autres bases elle génère des solutions qui ne sont pas e¢ caces.
Pour le problème d’a¤ectation nos perspectives sont nombreuses on site parmi :

L’amélioration des méthodes déjà existantes en diminuant le nombre d’itérations et

par conséquent le temps de calcul.

L’adaptation des méthodes existantes pour des problèmes à plus de deux objectifs.

L’adaptation de nouvelles méthodes pour le problème d’a¤ectation tel que PPM.

Ce qui est sûr qu’il reste beaucoup à faire pour le problème d’a¤ectation multicritère.

99
Bibliographie

[1] Dj. Chaabane. Optimisation Multicritère en nombres entiers. Thèse de doctorat d’état,
Faculté de Mathématique, U.S.T.H.B, 16-05-2005.

[2] [Link], [Link]. A method for …nding the set of non- dominated vectors of Multiple
Objective Integer Linear Programs, European Journal of Operational Research, in press
2003.

[3] G. B. Dantzig, Linear Programming and Extensions. Princeton university press, 1963.

[4] F. Degoutin, Problèmes bi-objectifs en optimisation combinatoire et capacité

d’infrastructures ferroviaires. Mémoire de recherche préparé dans le cadre du DEA
AISIH, Université de Valenciennes, 2002.

[5] X. Delorme. Modélisation et résolution de problèmes liés à l’exploitation

d’infrastructures ferroviaires. Thèse de doctorat, université de Valenciennes et du
Hainaut-Cambrésis, Discipline : Informatique, 2003.

[6] C. Dhaenens-Flipo“Optimisation Combinatoire Multi-Objectif : Apport des Méthodes

Coopératives et Contribution à l’Extraction de Connaissances. Habilitation de diriger
des Recherches de l’U.S.T.L. Discipline : Informatique, 2005.

[7] M. Ehrgott and X. Gandibleux. A survey and Annotated Bibliography of Multiobjective

combinatorial optimization. OR. Spektrum, Springer-Verlag, 22: 425-460, 2000.

[8] X. Gandibleux. École d’Automne de Recherche Opérationnelle. LAMIH - Recherche

Opérationnelle et Informatique, université de Valenciennes et du Hainaut-Cambrésis
2003.

100
 BIBLIOGRAPHIE

[9] R. Malhotra, H.L. Bhatia, and M.C. Puri. Bi-criteria assignment problem. Opsearch.
Journal of the Operational Research Society of India, 19(2): 84–96, 1982.

[10] H. Meunier. Algorithmes évolutionnaire paralléles pour l’optimisation multi-objectif

de réseaux de télécommunication mobiles. Thèse de doctorat, de l’U.S.T.L, dicipline :
Informatique, 2002.

[11] C.R. Pedersen, Multicritaria descrete optimization-and related topics. Phd thesis, De-
partment of Operations Research, University of Aarhus, 2006.

[12] M. Sakarovitch. Graphe et programmation linéaire. Tome1; Paris.

[13] M. Sakarovitch, 1983. ‘Techniques mathématique de la recherche opérationnelle, tome

IV Optimisation combinatoire’, ENSIMAG, Université Scienti…que et Médicale, Institut
National Polytechnique de Grenoble.

[14] A. Przybylski, X. Gandibleux, and M. Ehrgott. Seek and cut algorithm comput-
ing minimal and maximal complete e¢ cient solution sets for the biobjective assign-
ment problem. In 6th Int. Multi-Objective Programming and Goal Programming conf
(MOPGP’04), 2004.

[15] R.E. Steuer. Multiple Criteria Optimization: Theory, Computation, and Applica-
[Link] séries in Probability and Mathematical Statistics: Applied Probability and
Statistics. John Wiley & Sons, New York, 1986.

[16] J. Teghem. Programmation linéaire Ellipses, 1996.

[17] D. Tuyttens, J. Teghem, Ph. Fortemps, and K. Van Nieuwenhuyse. Performance of the
mosa method for the bicriteria assignment problem. Journal of Heuristics, 6:295–310,
2000.).

[18] [Link]. [Link]. Multicritaria assignment problem: a new method, Technical

report,.Faculté Polytechnique de Monis (1992).

101
 BIBLIOGRAPHIE

[19] E.L. Ulungu. Optimisation Combinatoire multicritère: Détermination de l’ensemble

des solutions e¢ caces et mèthodes intéractives. thèse de doctorat, Université de Mons-
Hainault, Faculté des Sciences, 1993.

[20] E.L. Ulungu and J. Teghem. Multi-objective combinatorial optimization problems: A

survey. Journal of Multi-Criteria Decision Analysis, 3:83–104,1994.

[21] E.L. Ulungu and J. Teghem. The two phases method : An e¢ cient procedure to solve
bi-objective combinatorial optimization problems. Foundations of Computing and De-
cision Sciences, 20:149–165, 1995.

[22] [Link], Multiple criteria problem solving. McGraw-Hill, New York, (1982).

102