les thèses : ces opinions doivent être considérées comme

Université Paris-Dauphine

Lamsade

N˚ attribué par la bibliothèque

Thèse

présentée en première version en vue d’obtenir le grade deDocteur en Informatique

spécialité Programmation mathématique

par

Nabila REMLI

Robustesse en programmation linéaire

Date de soutenance le 17 Mars 2011 devant le jury composé de :

Mr. P. Michelon Professeur Université d´Avignon (Rapporteur)

Mme A. Thiele Associate Professor Lehigh University (Rapporteur)

Mme V. Gabrel Maître de conférences Université Paris-Dauphine (Directrice)

Mme C. Murat Maître de conférences Université Paris-Dauphine (Co-directrice)

Mr. M. Minoux Professeur Université Paris 6

Mr. A.R. Mahjoub Professeur Université Paris-Dauphine

Mr. J. Figueira Professeur École des mines de Nancy

L’université n’entend donner aucune approbation ni improbation aux opinions émises dans

les thèses : ces opinions doivent être considérées comme propres à leurs auteurs.

Table des matières

Table des matières v

Liste des figures ix

Liste des tableaux xi

Introduction générale 1

1 État de l’art et problématique 7

Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

1.1 Incertitudes sur les coefficients de la fonction objectif . . . . . . . 9

1.1.1 Critère du pire cas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

1.1.2 Critère de regret maximum . . . . . . . . . . . . . . . . . . . . . . . . 13

1.2 Incertitudes portant sur la matrice des contraintes . . . . . . . . . 17

1.2.1 Approche de Soyster . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

1.2.2 Approche de Ben-Tal et Nimerovski . . . . . . . . . . . . . . . . . . . . 23

1.2.3 Approche de Bertsimas et Sim . . . . . . . . . . . . . . . . . . . . . . . 26

1.2.4 Approches multi-étapes . . . . . . . . . . . . . . . . . . . . . . . . . . 29

1.3 Incertitudes sur le second membre des contraintes . . . . . . . . . . 34

Conclusion et problématique . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

2 Programmes linéaires avec seconds membres incertains 43

Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

2.1 Premier contexte décisionnel : des décisions robustes . . . . . . . . . 47

2.1.1 Programmes linéaires avec contraintes d’inégalité . . . . . . . . . . . . 48

2.1.2 Programmes linéaires avec contraintes d’égalité : modèle de pénalités . . 51

2.2 Second contexte décisionnel : pire et meilleur optimaux . . . . . . . 56

2.2.1 Programmes linéaires avec contraintes d’inégalité . . . . . . . . . . . . 56

2.2.2 Programmes linéaires avec contraintes d’égalité . . . . . . . . . . . . . 58

v

2.2.3 Programmes linéaires quelconques . . . . . . . . . . . . . . . . . . . . 64

2.3 Robustesse et dualité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

2.3.1 Critère du meilleur cas . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

2.3.2 Dualité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68

Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

3 Calcul du pire optimum paramétrique 73

Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75

3.1 Programmes linéaires avec contraintes d’inégalité . . . . . . . . . . 76

3.1.1 Définition du pire optimum paramétrique . . . . . . . . . . . . . . . . 76

3.1.2 Reformulation en programme linéaire mixte . . . . . . . . . . . . . . . 79

3.2 Programmes linéaires avec contraintes d’égalité . . . . . . . . . . . 83

3.2.1 Identification du pire optimum paramétrique . . . . . . . . . . . . . . . 83

3.2.2 Reformulation en programme linéaire mixte . . . . . . . . . . . . . . . 85

Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86

4 Problème de localisation et de transport robuste 89

Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91

4.1 Problème de localisation et de transport déterministe . . . . . . . . 92

4.2 Problème de localisation et de transport robuste . . . . . . . . . . . 93

4.2.1 Formulation de la version robuste . . . . . . . . . . . . . . . . . . . . . 93

4.2.2 Résolution du problème de localisation et de transport robuste . . . . . 97

4.2.3 Reformulation du problème de recours . . . . . . . . . . . . . . . . . . 100

4.3 Expérimentations numériques . . . . . . . . . . . . . . . . . . . . . . . . 105

4.3.1 Problème de recours . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106

4.3.2 Problème de localisation et de transport robuste . . . . . . . . . . . . . 109

4.3.3 Autre contexte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111

Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114

5 Problème de gestion des stocks robuste 117

Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119

5.1 Définition du problème de gestion des stocks déterministe . . . . . . 120

5.2 Formulation robuste 1 : solution robuste de pire cas . . . . . . . . . 124

5.2.1 Modèle de pénalités . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124

5.2.2 Solution de pire cas paramétrique : approche de Bertsimas et Thiele . . 129

5.3 Formulation robuste 2 : pire optimum . . . . . . . . . . . . . . . . . . . 135

vi

5.4 Formulation robuste 3 : approche robuste bi-étapes . . . . . . . . . . 139

Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141

Conclusion générale 143

Bibliographie 147

vii

Liste des figures

1.1 Domaine des solutions réalisables du problème (P1c) . . . . . . . . . . . . 13

1.2 Domaine des solutions réalisables du problème (P2A) . . . . . . . . . . . 22

1.3 Domaine des solutions réalisables du problème P2A(Γ)BS . . . . . . . . . 29

2.1 Solution optimale suivant le critère du pire cas pour (P4b≥) . . . . . . . . 50

2.2 Solution optimale suivant le critère du pire cas pour (P5bp) . . . . . . . . . 55

2.3 Solution optimale suivant le critère du meilleur cas pour (P4b) . . . . . . 67

4.1 Résolution du problème de recours pour un exemple m=100 et n=250 :

a- Temps de résolution en fonction de Γ. b- Valeur de l’optimum en

fonction de Γ. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107

4.2 Résolution du problème de recours pour des tests n=500 : a- Temps

d’exécution en fonction de Γ. b- Saut d’intégrité en fonction de Γ. . . . . . 108

4.3 Résolution du problème de recours pour des tests n=1000 : a- Temps

d’exécution en fonction de Γ. b- Saut d’intégrité en fonction de Γ. . . . . . 109

4.4 Résolution du problème Trob(Γ) pour un test n = m = 50 : a- Valeur de

l’optimum en fonction de Γ. b- ∆OptMaxOpt en fonction de Γ . . . . . . . . . . 110

4.5 Variation relative des coûts en fonction de Γ pour un test n =

m = 35 : la courbe A représente la différence en pourcentage dev∗(Trob(Γ))−v∗(T2rob(Γ))

v∗(T2rob(Γ)) × 100 . La courbe B exprime la différence en pour-

centage de v∗(T2rob(n))−v∗(T2rob(Γ))v∗(T2rob(Γ)) × 100 . . . . . . . . . . . . . . . . . . . . . 114

ix

Liste des tableaux

4.1 Résultats des temps d’exécution du problème de recours . . . . . . . . . . 107

4.2 Temps d’exécution de la résolution du problème robuste Trob(Γ) . . . . . 111

4.3 Temps de résolution et nombre d’itérations pour la résolution de

T2rob(n/2) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112

4.4 Test n = m = 35 : résolution de T2rob(Γ) vs Trob(Γ) . . . . . . . . . . . . . . 113

5.1 Les coûts du problème (G1) . . . . . . . . . . . . . . . . . . . . . . . . . . . 125

5.2 Les demandes du problème (G1) . . . . . . . . . . . . . . . . . . . . . . . . 125

5.3 La solution nominale du problème (G1) . . . . . . . . . . . . . . . . . . . . 126

5.4 Les valeurs des pénalités pt et qt relatives au problème (G1) . . . . . . . . 126

5.5 La solution de pire cas (upent , spen

t , xpent ) du problème (G1Rob1). . . . . . . 127

5.6 Les valeurs des pénalités p′t et q′t relatives au problème (G1) . . . . . . . . 127

5.7 La solution de pire cas (upen′t , spen′

t , xpen′t , ypen′

t ) du problème (G1Rob1). . 128

5.8 La valeur du pire optimum de GS1Rob(Γ) et le scénario de demande en

fonction de Γ. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135

5.9 La valeur du pire optimum de G1Rob2(Γ) et le scénario de demande en

fonction de Γ. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138

xi

Introduction générale

L’optimisation mathématique se heurte dans de nombreux cas au caractère incertain

des données du problème qu’elle se propose de résoudre. En effet, les incertitudes

liées aux problèmes vont impliquer des difficultés à établir un modèle exact. Ceci est le

cas, par exemple dans les problèmes d’optimisation de chaînes d’approvisionnement,

où la demande effective de produits et le rendement financier ne sont pas connus

avec précision. Dans cette situation, les valeurs exactes des paramètres du modèle

ne sont pas accessibles, et seules des estimations sont fournies. Plus généralement,

un grand nombre de problèmes d’optimisation, tels que les problèmes de gestion de

production, d’ordonnancement, de transport, d’allocation de ressources, et de gestion

des risques financiers exigent que les décisions soient prises en présence d’incerti-

tudes. L’incertitude dans ces problèmes peut toucher les prix des matières premières,

leur disponibilité et le niveau de la demande des clients. En ingénierie, les données

sont soumises à des erreurs de mesure ou d’arrondi qui constituent aussi des sources

d’incertitude dans les modèles d’optimisation.

Les difficultés à établir des modèles exacts rendent nécessaire l’établissement de

méthodologies qui tiennent compte de ces imprécisions dans le processus d’optimisa-

tion et offrent des solutions acceptables au problème posé. L’optimisation stochastique

s’est intéressée, dès les années 1950, à ce type de problématiques en se basant sur

des modèles probabilistes pour la représentation des imprécisions (une littérature

étendue y est consacrée, dont voici quelques références Birge et Louveaux (1997),

Prékopa (1995), Kall et Wallace (1994)). Cependant, dans de nombreux cas, l’optimi-

sation stochastique n’est pas applicable en raison de l’insuffisance d’information pour

l’élaboration des lois de probabilité. De plus, elle présente un inconvénient majeur,

celui de la taille très importante des problèmes qu’elle génère. On se trouve dès lors

confronté à des problèmes d’espace mémoire et de temps de calcul.

1

2 Introduction générale

L’optimisation robuste est une approche différente qui vise à apporter des solutions

aux problématiques liées à l’incertain, sans avoir recours à l’analyse probabiliste. Le

premier à avoir proposé des méthodes non probabilistes est Dantzig (1955). Depuis,

cette thématique a connu un regain d’intérêt et un développement rapide durant les

deux dernières décennies.

La mise en application des approches robustes nécessite d’identifier trois prin-

cipales composantes. La première est la représentation du modèle d’incertitude ; la

deuxième consiste à identifier les objectifs ainsi que le contexte décisionnel du pro-

blème et la troisième composante vise à déterminer le moyen ou la démarche à suivre

permettant d’atteindre les objectifs fixés.

Parmi les modèles d’incertitude non probabilistes relevés dans la littérature, citons

la modélisation par scénarios discrets, où les paramètres incertains sont représentés

par un ensemble fini de valeurs discrètes (voir par exemple les domaines d’applica-

tions de Yu et Yang (1998) et Deineko et Woeginger (2006)) ; la modélisation par des

intervalles continus, ou plus généralement par des ensembles convexes est, elle aussi,

très utilisée en optimisation robuste (à titre d’exemples, voir les travaux de Kouvelis et

Yu (1997), Bertsimas et Sim (2003) et Averbakh et Lebedev (2005)). La modélisation de

l’incertitude par des intervalles est celle que nous avons retenue tout au long de cette

thèse.

Après avoir établi le modèle d’incertitude, le décideur doit définir quel est l’objectif

visé, en terme de robustesse, compte tenu du contexte décisionnel du problème et

des incertitudes sur les données. Dans la littérature, la notion de solution robuste est

souvent emplyée. Nous observons, toutefois, qu’il n’y a pas de définition unique d’une

solution robuste et que celle-ci diffère selon les auteurs et les contextes de décision.

En effet, selon Roy (2002) la robustesse est une aptitude à résister à des “à peu près” ou

à des “zones d’ignorance” afin de se protéger d’impacts jugés regrettables. Daniel et Salazar

(2006) quant à eux qualifient une solution de robuste si sa valeur ne change pas de

façon “significative” lorsque le vecteur de décision est légèrement perturbé. Par ailleurs, une

solution robuste est définie par Gabrel et Murat (2007) comme étant une solution qui

doit être “acceptable” dans un grand nombre de scénarios et qui ne soit jamais “trop mauvai-

se”. Ces définitions nécessitent d’être adaptées au contexte décisionnel du problème

incertain. Par exemple, une solution robuste peut refléter une notion de stabilité dans


un système (voir Rosenblatt et L. (1987)), ou bien de flexibilité dans un contexte sé-

quentiel (voir Gupta et Rosenhead (1968), Rosenhead (1989) et Rosenhead et al. (1972)).

En dernier lieu, il faut définir les outils et les méthodologies pour répondre à la

préoccupation de la robustesse ainsi que leur mise en œuvre. Les critères issus de la

théorie de la décision ont été les premiers outils utilisés en robustesse, notamment le

critère du pire cas et le critère du regret maximum (voir Averbakh et Lebedev (2005)).

Il est important de noter la différence entre robustesse et analyse de sensibilité. En

effet, dans ce dernier contexte, une solution est déterminée pour un jeu de données

fixe (un scénario unique) et une étude a posteriori est réalisée dans le voisinage de

cette solution. Par contre, l’optimisation robuste conduit à considérer, a priori, plu-

sieurs scénarios et de rechercher des solutions, qui soient bonnes dans la totalité ou

la plupart des scénarios. Dans la construction de modèles robustes, les incertitudes

doivent être intégrées au processus de la décision et ne sont pas le résultat d’une

analyse a posteriori (voir Roy et al. (1982)).

Dans le cadre de ce travail de thèse, nous nous intéressons aux problèmes de

programmation linéaire dans lesquels certains coefficients sont incertains. Plus préci-

sément, notre intérêt se porte sur la prise en compte d’incertitudes affectant exclusi-

vement les coefficients du second membre. Cette problématique n’avait pas, à notre

connaissance, fait l’objet d’étude spécifique antérieure au commencement de cette

thèse. En effet, les problèmes incertains de programmation linéaire étudiés dans la

littérature se concentraient essentiellement autour des problèmes admettant : soient

des coûts incertains, soient des coefficients incertains dans la matrice des contraintes

(ou parfois conjointement avec le second membre).

Les problèmes que nous proposons de traiter se rencontrent dans de nombreuses

applications réelles. Citons, par exemple, les problèmes de transport avec demande

incertaine, des problèmes de flots avec des capacités incertaines, ou encore des pro-

blèmes de gestion de stock avec des demandes incertaines. Dans cette étude, nous

proposons de développer des outils permettant la prise en compte des incertitudes

afin de répondre à la préoccupation de la robustesse selon trois contextes différents.

4 Introduction générale

Dans le premier contexte, une décision doit être prise avant la réalisation de l’in-

certain. Un grand nombre d’applications s’inscrivent dans ce contexte de décision. Le

critère le plus adapté et le plus répandu dans ce contexte est le critère du pire cas. Ce

critère étant largement étudié dans la théorie de la décision, nous nous attacherons

ici à identifier les cas où son application est possible et à étudier la complexité des

problèmes engendrés. Par ailleurs, s’il apparaît des situations où son application est

peu pertinente, nous proposerons des alternatives.

Le deuxième contexte décisionnel développé dans notre étude est celui où le dé-

cideur est en phase de planification. Dans ce cas, l’objectif est l’évaluation des coûts

des solutions optimales selon les réalisations possibles des incertitudes. La prise de

décision se fait, quant à elle, en milieu déterministe, une fois les incertitudes levées.

Nous proposons ici de fournir au décideur des évaluations pertinentes suivant les scé-

narios envisagés et nous étudierons les problèmes engendrés (leur formulation et leur

complexité). Les évaluations recherchées par le décideur peuvent être très différentes

d’une application à l’autre. Nous nous intéresserons entre autre à l’évaluation la plus

favorable et la plus défavorable et proposerons d’autres évaluations plus flexibles.

Le dernier contexte décisionnel abordé dans ce manuscrit a été étudié récemment

dans la littérature et concerne la prise de décisions robustes en plusieurs étapes ; il

s’agit du contexte multi-étapes. Ce contexte a été introduit par Ben-Tal et al. (2004) pour

les programmes linéaires où l’incertitude est située dans la matrice des contraintes et

a été récemment étudié par Thiele et al. (2009) qui l’adoptent sur des problèmes avec

second membre incertain dans une approche robuste bi-étapes. Dans cette dernière,

nous considérons que l’espace de décision est séparé en deux parties : les variables de

la première partie doivent être décidées avant la réalisation des incertitudes, alors que

celles de la seconde partie sont décidées au moment de la divulgation des incertitudes.

Le travail réalisé selon ce contexte consiste à appliquer une approche bi-étapes sur

deux applications réelles : une première application traite d’un problème de localisa-

tion et de transport ; la seconde, concerne un problème de gestion de stock.

Le plan de la thèse est le suivant : au chapitre 1, un état de l’art sera abordé dé-

crivant les principales approches robustes existant dans la littérature et cela en fonc-

tion de l’emplacement de l’incertitude dans le programme linéaire. Tout d’abord, nous

traiterons les problèmes possédant des coûts incertains. Ensuite, nous aborderons les


versions robustes de programmes linéaires admettant une matrice des contraintes in-

certaine. Enfin, nous introduirons notre problématique qui concerne les programmes

linéaires comportant un second membre incertain. Dans le chapitre 2, nous considérons

deux contextes décisionnels distincts pour lesquels nous répondrons à la préoccupa-

tion de la robustesse différemment : dans le premier contexte, il s’agira de calculer une

solution robuste de pire cas, et dans le second contexte nous calculerons l’évaluation

des valeurs du pire et du meilleur optima. En outre, nous montrerons que la nature

des contraintes du problème (que celles-ci soient des inégalités ou des égalités) influe

sur la complexité des versions robustes engendrées. Dans le chapitre 3, nous propose-

rons une généralisation du calcul du pire optimum et cela en étudiant une extension

pertinente de l’approche de Bertsimas et Sim (2004) sur le calcul de pire optimum.

Les problèmes contenant des contraintes d’inégalité ou d’égalité seront abordés sépa-

rément. Dans le chapitre 4, nous nous intéresserons à une approche robuste bi-étapes

pour traiter une première application d’un problème de localisation et de transport

avec demande incertaine. Ce problème est modélisé par un programme linéaire où les

incertitudes affectent certains coefficients du second membre de contraintes d’inégalité

du problème et nous ferons appel au résultats du chapitre 3. Enfin, dans le chapitre 5,

nous étudierons une seconde application d’un problème de gestion de stock avec de-

mande incertaine, que nous traiterons suivant plusieurs contextes de décision. Pour ce

faire, les versions robustes associées à ce problème doivent tenir compte du caractère

dynamique du problème ainsi que des incertitudes présentes dans le second membre

de contraintes d’égalité.

1État de l’art et problématique

Sommaire

Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

1.1 Incertitudes sur les coefficients de la fonction objectif . . . . . . . 9

1.1.1 Critère du pire cas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

1.1.2 Critère de regret maximum . . . . . . . . . . . . . . . . . . . . . . . . . . 13

1.2 Incertitudes portant sur la matrice des contraintes . . . . . . . . . 17

1.2.1 Approche de Soyster . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

1.2.2 Approche de Ben-Tal et Nimerovski . . . . . . . . . . . . . . . . . . . . . 23

1.2.3 Approche de Bertsimas et Sim . . . . . . . . . . . . . . . . . . . . . . . . 26

1.2.4 Approches multi-étapes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

1.3 Incertitudes sur le second membre des contraintes . . . . . . . . . . . 34

Conclusion et problématique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

Dans ce chapitre est présenté un état de l’art des principales approches, dites ro-

bustes, traitant de programmes linéaires contenant des données incertaines ou

imprécises. Ce chapitre est divisé en trois parties : dans la première partie, sont abor-

dés les problèmes dont les coefficients de la fonction objectif sont incertains. Les ré-

sultats concernant l’application de critères issus de la théorie de la décision y seront

détaillés. La deuxième partie est consacrée aux problèmes affectés par des coefficients

incertains situés dans la matrice des contraintes. Nous aborderons quelques approches

robustes utilisées dans la littérature. Les avantages et inconvénients de chacune seront

discutés. Enfin, la dernière partie traite des programmes linéaires contenant un second

membre des contraintes incertain. Nous montrerons que les approches existantes dans

la littérature sont peu pertinentes, ce qui introduira la problématique de notre travail.

7

1.1. Incertitudes sur les coefficients de la fonction objectif 9

Introduction

Ce chapitre fait un état de l’art des principales approches robustes traitant de pro-

grammes linéaires en présence d’incertitude. Nous rappelons qu’il ne sera abordé

ici que le modèle d’incertitude décrit par des intervalles continus. Nous avons choisi

de séparer les résultats bibliographiques en fonction de l’emplacement des incerti-

tudes dans le programme linéaire. Tout d’abord, seront traités dans la section 1.1

les programmes linéaires admettant des coefficients de la fonction objectif incertains.

Les critères classiques du pire cas et du regret maximum y seront appliqués pour

trouver des solutions robustes. Dans la seconde partie de chapitre (section 1.2), notre

intérêt sera porté sur les approches robustes traitant de programmes linéaires où les

coefficients de la matrice des contraintes sont incertains. Nous verrons que pour être

robustes, les solutions recherchées doivent répondre à la préoccupation de réalisabilité

du problème. Enfin, le cas des incertitudes présentes dans le second membre des

contraintes, faisant l’objet de la problématique de cette thèse, sera discuté à la fin du

chapitre.

1.1 Incertitudes sur les coefficients de la fonction objectif

Considérons un programme linéaire avec des coefficients de coûts incertains, écrit sous

la forme générale suivante :

(Pc)

min cx

s.c. Ax ≤ b

où x est une matrice colonne de taille n qui représente les variables du problème.

La matrice des contraintes A est de taille m× n et le second membre des contraintes

b est une matrice colonne de taille m. Notons X = x ∈ Rn|Ax ≤ b le domaine

des solutions réalisables du problème (Pc) que nous supposons non vide et borné.

Le coût c est une matrice ligne de taille n. Elle constitue la part incertaine du problème.

Nous supposons que chaque coefficient incertain de c prend ses valeurs dans

un intervalle fermé, indépendamment des valeurs prises par les autres paramètres.

Formellement, notons Λ l’ensemble d’incertitude représenté par le produit cartésien

10 Chapitre 1. État de l’art et problématique

des intervalles [cj, cj], j = 1 . . . n, où cj ≤ cj.

Nous définissons un scénario comme étant une réalisation de l’incertitude dans le

domaine Λ et notons v∗(Pc) la valeur de l’optimum pour le scénario c fixé.

Dans la plupart des études, l’objectif est de déterminer une solution, qualifiée

de robuste, avant de connaître les vraies valeurs des paramètres incertains, avec la

seule indication que ces derniers varient dans un domaine d’incertitude préalablement

défini. Une solution robuste doit alors présenter une certaine “garantie” sur tous ou la

plupart des scénarios pouvant se réaliser.

Les critères issus de la théorie de la décision sont des mesures couramment em-

ployées pour la détermination de solutions robustes. Les deux principaux critères

rencontrés dans la littérature sont le critère du pire cas (appelé aussi robustesse ab-

solue) et le critère du regret maximum (ou déviation absolue). La définition et l’emploi

de ces deux critères sur le problème incertain (Pc) seront détaillés ci-après dans ce

chapitre. Moins étudié, le critère du regret relatif maximum (ou déviation relative) peut

être appliqué. Ce critère ne sera pas abordé dans ce manuscrit mais nous invitons le

lecteur à se rapporter aux travaux de Mausser et Laguna (1999b) qui l’emploient sur

les programmes linéaires incertains, et Averbakh (2000), Averbakh (2005), Zielinski

(2004) et Assavapokee et al. (2008) sur divers problèmes d’optimisation combinatoire.

D’autres mesures de robustesse ont vu le jour plus récemment, avec la particularité

de faire intervenir des seuils (à fixer par le décideur) et de déterminer un groupe de

solutions robustes (voir Kouvelis et al. (1992), Kalai (2006), Kalai et Lamboray (2007)

et Roy (2010)).

Nous allons, dans ce qui suit, donner le résultat de l’application des critères

classiques du pire cas et du critère du regret maximum sur le problème (Pc). Il en

découlera différents problèmes robustes dont nous donnerons la complexité et la

résolution.

1.1.1 Critère du pire cas

Le critère du pire cas peut être considéré comme étant le critère de référence en op-

timisation robuste, quand il s’agit de déterminer des solution avant la réalisation des


incertitudes. De manière générale, son application sur un problème incertain permet

de déterminer la solution optimale suivant le scénario le plus défavorable. La solution

ainsi obtenue est robuste car elle offre une garantie absolue à toutes les éventualités

pouvant se réaliser.

Parmi les auteurs qui se sont intéressés aux programmes linéaires incertains

s’écrivant sous la forme du problème (Pc) où c ∈ Λ, nous retrouvons les travaux de

Averbakh et Lebedev (2005), où les auteurs présentent -entres autres- le résultat de

l’application du critère du pire cas sur (Pc), qui se décrit comme suit.

Soit x une solution réalisable de (Pc), sa valeur selon le critère du pire cas, notée

vpir(x), se définit comme :

vpir(x) = maxc∈Λ

cx (1.1)

Suivant le critère du pire cas, il s’agit de déterminer, parmi toutes les solutions réali-

sables x ∈ X, celle qui minimise la valeur de vpir(x). Le problème de pire cas, noté

(Pc)pirCas, s’écrit :

(Pc)pirCas

minx∈X

maxc∈Λ

cx

Proposition 1.1 [Averbakh et Lebedev (2005)] L’application du critère du pire cas sur un

programme linéaire, dont les coefficients coûts sont incertains et appartiennent à des intervalles,

est un problème polynomial.

Démonstration. Par hypothèse, le polyèdre des solutions réalisables X est non vide et

borné ; il est donc possible, selon le théorème fort de dualité, de remplacer le pro-

blème de maximisation dans l’écriture de (Pc)pirCas par son dual. Nous obtenons la

formulation en programme linéaire suivante :

(Pc)pirCas

min cu− cv

s.c. u− v− x = 0

Ax ≤ b

u ≥ 0, v ≥ 0

qui est un problème polynomial.


Remarque 1.1 Dans le cas particulier où les variables x sont de signe constant, par exemple

supposons qu’elles soient positives, le problème (Pc)pirCas est équivalent à (Pc) :

(Pc)pirCas

min cx

s.c. Ax ≤ b

x ≥ 0

En effet, si les variables x sont non-négatives, nous remarquons que les pires valeurs des coef-

ficients de la fonction objectif pour le problème de minimisation (Pc) se déduisent directement

en affectant aux coûts les valeurs des bornes supérieures des intervalles auxquels elles appar-

tiennent.

Exemple 1.1 Soit le programme linéaire (P1c) suivant :

(P1c)

min c1x1 + c2x2

s.c. − x1 + 3x2 ≤ 4

3x1 + 2x2 ≥ −4

− 5x1 + 2x2 ≥ −6

(1.2)

(1.3)

(1.4)

Les coefficients (c1, c2) de la fonction objectif sont incertains et peuvent prendre n’importe

quelle valeur dans les intervalles suivants : c1 ∈ [−3, 3] et c2 ∈ [1, 3].

Selon la proposition 1.1, la solution robuste selon le critère du pire cas pour le problème (P1c)

s’obtient par la résolution du programme linéaire (P1c)pirCas s’écrivant :

(P1c)pirCas

min 3u1 + 3u2 + 3v1 − v2

s.c. u1 − v1 − x1 = 0

u2 − v2 − x2 = 0

−x1 + 3x2 ≤ 4

3x1 + 2x2 ≥ −4

−5x1 + 2x2 ≥ −6

u1, u2, v1, v2 ≥ 0

La solution robuste selon le critère du pire cas est x∗pirCas = (0,−2) de valeur égale à −2. Elle

se réalise pour tous les scénarios (c1, 1) où c1 ∈ [−3, 3]. En adoptant la solution x∗pirCas, le

décideur est sûr de garantir un coût égal à −2 dans le pire cas. La figure 1.1 illustre le domaine


des solutions réalisables du problème (P1c). Nous remarquons que x∗pirCas ne se situe pas sur

un point extrême du domaine des solutions réalisables du problème (P1c).

- 3 - 2 - 1 1 2 3

- 2

- 1

1

2

( 1 . 3 )

( 1 . 4 )

( 1 . 2 )

x * p i r C a s = ( 0 , - 2 )

Fig. 1.1 – Domaine des solutions réalisables du problème (P1c)

En optimisation combinatoire, le critère du pire cas est utilisé dans de nombreuses

applications. Nous donnons quelques références de certains problèmes qui ont retenu

notre attention : citons d’abord les travaux de Yaman et al. (2001) qui s’intéressent

au problème de l’arbre couvrant. Citons également le problème de plus court chemin

robuste qui est traité par Yu et Yang (1998) et Gabrel et Murat (2007). Mentionnons

enfin les travaux de Yu (1996) et Taniguchi et al. (2008) sur le problème de sac à dos

robuste.

Le second critère est celui du regrêt maximum, dont nous présentons l’application

dans ce qui suit.

1.1.2 Critère de regret maximum

Le critère de regret maximum a été introduit par Savage (1954) et Luce et Raiffa (1957).

C’est le critère le plus étudié et le plus utilisé en théorie de la décision, lorsque la

fonction objectif d’un programme linéaire est incertaine et la décision doit être prise

avant la réalisation de l’incertain. Par définition, le regret est le sentiment de perte

ressenti par un décideur après avoir appris qu’une autre solution (ou décision) aurait

été préférable à celle sélectionnée. En programmation mathématique, le regret est


souvent associé à la notion de robustesse. En effet, la solution robuste obtenue par

l’application de ce critère est celle dont le plus grand écart par rapport aux valeurs

optimales sur tous les scénarios est le plus faible.

Plusieurs auteurs se sont intéressés à l’application du critère du regret maximum

sur un programme linéaire, dont les coefficients de la fonction objectif sont incertains.

Les premiers travaux sont ceux de Shimizu et Aiyoshi (1980) qui, comme nous le

verrons dans ce qui suit, proposent un algorithme pour résoudre ce problème robuste.

Tout d’abord, formalisons le problème : soit x une solution réalisable du problème

(Pc) pour un scénario fixé c, appartenant à l’ensemble d’incertitude Λ. Le regret, noté

r(x, c), associé à la solution x représente la différence entre la valeur de l’optimum

pour le scénario c et la constante cx, sa valeur est donc :

r(x, c) = (cx− cx∗)

où x∗ représente la solution optimale du problème (Pc) pour le scénario c. Le regret

maximum, noté R(x), associé à la solution x est celui qui réalise le maximum sur tous

les scénarios :

R(x) = maxc∈Λ

r(x, c)

La solution robuste suivant le critère du regret maximum est alors une solution dans

X qui minimise le regret maximum :

minx∈X

R(x)

Le problème du regret maximum, noté (Pc)reg, s’écrit donc :

(Pc)reg

minx∈X

maxc∈Λ

(cx− cx∗)

La solution optimale x∗reg de (Pc)reg est robuste car elle fournit au décideur une ga-

rantie relative dans le sens où, quand celui-ci la choisit, il sait que quel que soit le

scénario incertain qui se réalisera, l’écart maximum sur tous les scénarios par rapport

à la solution optimale sera le plus faible.

Théorème 1.1 [Averbakh et Lebedev (2005)] Le problème du regret maximum, lorsque les

coefficients de la fonction objectif varient dans des intervalles, est NP-difficile au sens fort. De


plus, les auteurs montrent que le calcul du regret maximum R(x), pour une solution réalisable

x, est NP-difficile au sens fort.

Résolution exacte

Shimizu et Aiyoshi (1980) proposent un algorithme de résolution exacte du problème

(Pc)reg. Les auteurs se basent sur le fait que le problème (Pc)reg peut s’écrire de manière

équivalente sous la forme d’un programme linéaire comme suit :

(Pc)reg

min r

s.c. r ≥ cx− cx∗ pour tout c ∈ Λ

x ∈ X

(1.5)

qui inclut une infinité de contraintes (1.5).

Afin de résoudre (Pc)reg de manière optimale, les auteurs considèrent initialement

un sous-ensemble de contraintes (1.5), qui sera augmenté à chaque itération, jusqu’à

l’obtention de la solution optimale. Soit donc C = c1, c2, ..., cl un sous-ensemble de

vecteurs coûts appartenant à Λ, et (Pc)′reg le problème relaxé engendré par C :

(Pc)′reg

min r

s.c. r ≥ ckx− ckxck , k = 1 . . . l

x ∈ X

(1.6)

où xck est la solution optimale pour le scénario ck, avec k = 1 . . . l.

Les contraintes (1.6) sont appelées des coupes de regret. Soit x la solution optimale de

(Pc)′reg et r le regret correspondant. La valeur de r représente une borne inférieure à la

valeur optimale du regret maximum. En effet, (Pc)′reg est le problème relaxé de (Pc)reg,

qui admet un nombre restreint de contraintes. Pour la même raison, notons que la

valeur du regret r est non décroissante au fur et à mesure que les coupes de regret

s’ajoutent au programme (Pc)′reg.

Il est clair que si la solution de regret r satisfait toutes les contraintes (1.5) alors elle est

optimale pour le problème (Pc)reg. Afin de tester cette condition, il suffit de calculer

le regret maximum de x dans l’ensemble Λ. Ceci passe par la résolution du problème


esclave, noté (CMR) (candidate maximum regret), suivant :

(CMR)

Rmax(x) = max cx− cx

s.c. x ∈ X

c ∈ Λ

(1.7)

Par conséquent, si Rmax(x) = r alors x est la solution optimale du problème (Pc)reg,

sinon la solution (c, xc) obtenue par la résolution du problème (CMR) ne vérifie pas

toutes les contraintes (1.5). Dans ce cas, la nouvelle contrainte :

r ≥ cx− cxc

est ajoutée au problème (Pc)′reg. Ainsi, la taille de l’ensemble C croît itérativement

jusqu’à ce que le critère d’arrêt soit vérifié.

En utilisant (Pc)′reg et (CMR) pour générer des solutions candidates et des coupes de

regret, on obtient l’algorithme suivant qui minimise le regret maximum :

Algorithme 1 : Algorithme pour le calcul du regret maximum

Étape 0 : Initialiser : poser r := 0 et choisir un x ∈ XÉtape 1 : Résoudre (CMR) et trouver c et Rmax(x). Si Rmax(x) ≤ r alors fin, xminimise le regret maximum ; sinon aller à l’étape 2

Étape 2 : Ajouter la coupe r ≥ cx− cxc au problème (Pc)′reg

Étape 3 : Résoudre (Pc)′reg et trouver r et x. Actualiser la valeur de r et aller àl’étape 1

Convergence de l’algorithme : [Shimizu et Aiyoshi (1980)] L’algorithme 1 converge

vers la solution qui minimise le regret maximum en un nombre fini d’itérations.

La résolution du problème (CMR) à l’étape 1 est la partie la plus coûteuse en temps

de calcul. En effet, rappelons que ce problème est NP-difficile au sens fort (Averbakh

et Lebedev (2005)). Plusieurs travaux ont été menés pour résoudre le problème (CMR)

de manière efficace (afin d’en réduire les temps de calcul). Dans une première étude,

Inuiguchi et Sakawa (1995) caractérisent les solutions optimales du problème (CMR)

ainsi que des scénarios de pire cas. Puis, en exploitant ces propriétés, ces mêmes

auteurs reformulent et résolvent le problème en utilisant un algorithme de branch and

bound (voir Inuiguchi et Sakawa (1996)). D’autres améliorations sont apportées par

1.2. Incertitudes portant sur la matrice des contraintes 17

Mausser et Laguna (1998; 1999a) qui suggèrent, respectivement, une formulation en

programme linéaire mixte et une heuristique pour la résolution du problème (CRM),

réduisant ainsi les temps de calcul.

En optimisation combinatoire, le critère du regret maximum a largement été utilisé

pour répondre à la préoccupation de la robustesse. Tout d’abord, nous citons le pro-

blème de l’arbre couvrant qui a été traité par Yaman et al. (2001), Averbakh et Lebedev

(2004), Montemanni et Gambardella (2005) et Montemanni (2006). La complexité de

ce problème est donnée par Aron et Van Hentenryck (2004), et une formulation en

nombres entiers est proposée par Yaman et al. (2001). Ensuite, concernant le problème

de plus court chemin robuste suivant le même critère, nous pouvons noter les travaux

d’Averbakh et Lebedev (2004), Karasan et al. (2001), Kasperski et Zielinski (2006), Mon-

temanni et Gambardella (2004) et Montemanni et al. (2004). Dans Averbakh (2004),

il est question du problème d’allocation de ressources robuste, et dans Deineko et

Woeginger (2006) est traité le problème d’affectation robuste. De plus, Montemanni

et al. (2005) s’intéressent au problème de voyageur de commerce robuste. D’autres

versions robustes selon le critère du regret maximum de divers problèmes d’optimisa-

tion combinatoire ont été étudiés, comme par exemple : Aissi (2005), Aissi et al. (2007),

Assavapokee et al. (2008), Averbakh (2000), Averbakh (2001) et Escoffier et al. (2008).

Dans la première partie de cet état de l’art, nous avons traité des programmes li-

néaires dont les coefficients de la fonction objectif sont incertains. Nous avons présenté

les résultats de complexité et approches de résolution des versions robustes obtenues

par l’application des critères classiques de la théorie de la décision. Dans la partie sui-

vante seront exposées les principales approches utilisées pour déterminer des solutions

robustes lorsque les coefficients de la matrice des contraintes sont incertains.

1.2 Incertitudes portant sur la matrice des contraintes

Dans un programme linéaire, considérer que les incertitudes portent sur les coeffi-

cients de la matrice des contraintes revient à considérer que le domaine des solutions

réalisables est incertain. La préoccupation de la réalisabilité est donc une considération

centrale lors de la recherche de solutions robustes pour ce problème incertain. Nous

verrons dans ce qui suit, comment chacune des approches présentées définit une


solution robuste et de quelle manière la réalisabilité du problème est prise en compte.

Commençons, tout d’abord, par formaliser le problème. Soit le programme linéaire

(PA) s’écrivant sous la forme suivante :

(PA)

min cx

s.c. Ax ≤ b

x ≥ 0

où x est une matrice colonne de taille n qui représente les variables du problème. Le

coût c est une matrice ligne de taille n, la matrice A des contraintes de taille m× n et

le second membre b est une matrice colonne de taille m. Supposons que l’incertitude

porte uniquement sur les coefficients de la matrice des contraintes A et que le domaine

réalisable est non vide, quelle que soit la réalisation de l’incertitude.

L’ensemble d’incertitude adopté pour modéliser les coefficients de la matrice A

est un modèle par intervalles, que nous définissons de la manière suivante : pour tout

i = 1 . . . m et j = 1 . . . n, le paramètre aij appartient à [aij− aij, aij + aij], où aij représente

la valeur nominale du coefficient aij et aij (avec aij ≥ 0) sa déviation maximale. En

d’autres termes,

aij = aij + aijξij (1.8)

avec

ξij ∈ [−1, 1] (1.9)

Dans la littérature, il est possible de séparer les approches robustes en deux familles

selon le contexte décisionnel auquel appartient le problème (PA) :

1. Contexte statique : il s’agit de prendre une décision (une solution robuste) avant

toute réalisation de l’incertitude de façon irrémédiable. Dans ce contexte, nous

présenterons trois approches robustes : l’approche de Soyster (1973), l’approche

de Ben-Tal et Nimerovski (1999) et l’approche de Bertsimas et Sim (2004) ;

2. Contexte multi-étapes : ici l’espace de décision est divisé en plusieurs groupes,

de telle sorte que les décisions de chaque groupe peuvent être prises au fur


et à mesure que l’incertitude est levée. Nous présenterons l’approche bi-étapes

introduite par Ben-Tal et Nimerovski (1999).

Commençons donc par formaliser les trois approches utilisables dans le contexte sta-

tique.

1.2.1 Approche de Soyster

L’approche de Soyster (1973) (voir aussi les développements de Soyster (1979), Falk

(1976) et Singh (1982)) est l’une des premières approches référencées dans la littérature

pour la détermination de solutions robustes au problème (PA). Son principe rejoint

celui du critère du pire cas décrit précédemment, où la solution doit, pour être quali-

fiée de robuste, être acceptable (réalisable) quel que soit le scénario qui se réalise.

La version robuste, notée (PA)Soyster, associée au problème (PA) selon cette approche

où les incertitudes sont définis par (1.8) et (1.9) s’écrit alors :

(PA)Soyster

min

n∑

j=1cjxj

s.c.n∑

j=1(aij + aijξij)xj ≤ bi ∀ ξij ∈ [−1, 1] i = 1 . . . m

xj ≥ 0 j = 1 . . . n

qui revient à résoudre :

(PA)Soyster

min

n∑

j=1cjxj

s.c.n∑

j=1aijxj + max

ξij∈[−1,1]aijξijxj ≤ bi i = 1 . . . m

xj ≥ 0 j = 1 . . . n

Dans notre cas, puisque les variables xj, j = 1 . . . n sont non négatives, et que les

coefficients sont indépendants, la version robuste de (PA) selon l’approche de Soyster

correspond au programme linéaire suivant :

(PA)Soyster

min

n∑

j=1cjxj

s.c.n∑

j=1(aij + aij)xj ≤ bi i = 1 . . . m

xj ≥ 0 j = 1 . . . n


Remarque 1.2 Notons que nous n’avons présenté ici qu’une adaptation des travaux de Soyster

à la modélisation des incertitudes par des intervalles. En effet, dans la version d’origine présentée

par Soyster (1973), les incertitudes sont modélisées par des ensembles convexes définis sur les

colonnes de la matrice A. C’est à dire que chaque colonne Aj appartient à un ensemble convexe

Kj, le but étant de calculer des solutions robustes de pire cas.

Remarque 1.3 La complexité des versions robustes associées au problème (PA) selon l’ap-

proche de Soyster (1973), dépend de la difficulté de calculer un maximum sur le domaine d’in-

certitude. Dans le cas d’incertitudes modélisées par des intervalles continus ou des polyèdres le

problème est polynomial (voir Ben-Tal et Nimerovski (2002)).

Exemple 1.2 Considérons le programme linéaire incertain (P2A) suivant :

(P2A)

max −2x1 + 3x2

s.c. a11x1 + a12x2 ≤ 120 (a)

a21x1 + a22x2 ≥ 30 (b)

x1 ≤ 8 (c)

x1, x2 ≥ 0

où les coefficients de la matrice des contraintes sont décrits par les intervalles continus suivants :

a11 ∈ [−15,−3], a12 ∈ [15, 25], a21 ∈ [1, 3] et a22 ∈ [5, 6]. Les valeurs nominales de ces coef-

ficients ainsi que les déviations sont respectivement : a11 = −9, a12 = 20, a21 = 2, a22 = 5.5

et a11 = 6, a12 = 5, a21 = 1, a22 = 0.5.

La version robuste selon l’approche de Soyster, notée (P2A)Soyster, associée au problème (P2A)

s’écrit :

(P2A)Soyster

max −2x1 + 3x2

s.c. −3x1 + 25x2 ≤ 120 (a)pir

x1 + 5x2 ≥ 30 (b)pir

x1 ≤ 8 (c)

x1, x2 ≥ 0

La solution optimale de (P2A)Soyster est égale à x∗pir = (3.75, 5.25). Sa valeur est égale à 8.25.

Elle correspond à la solution robuste de pire cas pour le problème incertain (PA).

Sur la figure 1.2 est illustrée la variation du domaine des solutions réalisables du problème

(P2A) en fonction des valeurs prises par les coefficients de la matrice A. Il y est notamment


illustré les domaines des solutions réalisables de trois valeurs de scénarios différents, définis

comme suit :

– le scénario de pire cas : relatif aux contraintes du problème (P2A)Soyster. Le domaine

réalisable suivant ce scénario est délimité par les droites (a)pir et (b)pir et (c) de la figure

1.2.

– le scénario nominal : correspondant au programme linéaire où tous les coefficients sont

égaux aux valeurs nominales. Le domaine réalisable suivant ce scénario est donné par les

droites (a)nom et (b)nom, (c) et x1 ≥ 0 de la figure 1.2.

– un troisième scénario, qu’on appellera scénario de meilleur cas : (par opposition au

scénario de pire cas), celui où les coefficients prennent les valeurs des intervalles qui

forment le plus grand domaine de solutions réalisables possible. Le domaine réalisable

suivant ce scénario est donné par les droites (a)mei et (b)mei, (c) et x1 ≥ 0 de la figure

1.2. Ce scénario est peu pertinent en robustesse mais il est considéré ici afin de comparer

les différentes solutions.

Les solutions optimales suivant ces trois scénarios sont très différentes (puisqu’elles résultent

de domaines réalisables différents) et sont -pris dans cet ordre- de valeurs croissantes. En effet,

x∗pir = (3.75, 5.25) est de valeur 8.25, x∗nom = (0, 6) est de valeur 18 et x∗mei = (8, 16) de

valeur 32.

L’approche robuste de Soyster (1973) est une approche de pire cas destinée à la

détermination d’une solution robuste avant la réalisation de l’incertain. Cette solution

est une garantie absolue contre tout scénario pouvant se réaliser, et va être décidée

sur la base du scénario le plus défavorable, celui définissant le plus petit domaine

réalisable.

Cependant, ces solutions robustes peuvent être jugées trop pessimistes et sont sou-

vent qualifiées de solutions “conservatives” dans la littérature. En effet, ne disposant

d’aucune information sur la probabilité d’occurrence des scénarios (nous supposons

seulement qu’ils sont tous équiprobables), il est clair pour certains décideurs que la

décision basée sur le cas le plus défavorable ne sera pas toujours satisfaisante. Son

coût peut être inutilement élevée alors qu’il n’y a que peu de chance qu’elle se réalise.

Pour pallier les inconvénients de l’approche de Soyster, de nouvelles approches ont


- 3 3 6 9

3

6

9

1 2

1 5

( c )( b ) m e i

( b ) n o m

( b ) p i r

( a ) p i r

( a ) n o mx *n o m

x *p i r

x *m e i

( a ) m e i

Fig. 1.2 – Domaine des solutions réalisables du problème (P2A)

émergé au cours de la dernière décennie. Elles ont permis des avancées importantes en

optimisation robuste tant sur le plan théorique que sur le plan pratique. Les versions

robustes selon ces approches font intervenir un paramètre qui permet de contrôler

le degré de “conservatisme” de la solution robuste tout en garantissant une forte

probabilité de satisfaction des contraintes. La solution robuste recherchée n’est plus

réalisable quel que soit le scénario qui se produit, mais le degré de non satisfaction des

contraintes est fixé par ce paramètre. S’autorisant cette faible violation des contraintes

on s’éloigne des scénarios extrêmes de pire cas, et on fournit au décideur des solutions

robustes de meilleure qualité.

Parmi les approches paramétriques existant dans la littérature, deux principales

approches peuvent être distinguées : l’approche de Ben-Tal et Nimerovski (que nous

présenterons dans la section 1.2.2) et l’approche de Bertismas et Sim (présentée à la

section 1.2.3).


1.2.2 Approche de Ben-Tal et Nimerovski

L’approche de Ben-Tal et Nimerovski (1999; 2000) (parallèlement introduite par

El Ghaoui et Lebret (1997) et El Ghaoui et al. (1998)) consiste à chercher des solutions

robustes moins conservatives que les solutions de pire cas, et cela en utilisant un

domaine d’incertitude qui exclut les valeurs extrêmes des intervalles en autorisant une

faible violation des contraintess.

En effet, la modélisation proposée ne situe plus les scénarios sur les extrémités des

intervalles, mais sur les bords d’ellipsoïdes inscrits dans les intervalles de variation.

Pour ce faire, les auteurs imposent, pour toute contrainte i, i = 1 . . . m du programme

linéaire incertain (PA), que les déviations maximales sur une même contrainte i appar-

tiennent à un ellipsoïde défini par :

Ξi(Ωi) = ξij ∈ Rn|

√√√√ n

∑j=1

ξ2ij ≤ Ωi; ξij ∈ [−1, 1] (1.10)

avec Ωi ≥ 0, pour tout i = 1 . . . m.

Ce modèle d’incertitude est souvent nommé dans littérature par modèle en ligne, du fait

qu’un paramètre Ωi soit défini pour chaque contrainte i.

Selon l’approche de Ben-Tal et Nimerovski (1999), la version robuste du problème (PA)

consiste à se placer dans le pire cas dans le domaine s’écrit Ξi(Ωi) et s’écrit :

PA(Ω)BenTal

min

n∑

j=1cjxj

s.c.n∑

j=1aijxj + max

ξ∈Ξi(Ωi)

n∑

j=1aijξijxj ≤ bi i = 1 . . . m

xj ≥ 0 j = 1 . . . n

où Ω représente le vecteur des paramètres (Ω1, . . . , Ωm). Il est possible de simplifier le

problème en employant le lemme suivant.

Lemme 1.1 [Babonneau et al. (2010)] Soit p un réel (avec p > 1), et soit q tel que 1p + 1

q = 1.


Pour tout vecteur d ∈ Rn et un réel positif k, nous avons :

max||ξ||p≤k

dTξ = k||d||q

Il découle du Lemme 1.1 que le problème PA(Ω)BenTal est équivalent à :

PA(Ω)BenTal

minn∑

j=1cjxj

s.c.n∑

j=1aijxj + Ωi

√n∑

j=1a2

ijx2j ≤ bi i = 1 . . . m

xj ≥ 0 j = 1 . . . n

qui revient au problème quadratique suivant :

PA(Ω)BenTal

minn∑

j=1cjxj

s.c.n∑

j=1aijxj + Ωizi ≤ bi i = 1 . . . m

n∑

j=1a2

ijx2j ≤ z2

i i = 1 . . . m

zi ≥ 0 i = 1 . . . m

xj ≥ 0 j = 1 . . . n

Le problème robuste PA(Ω)BenTal est non linéaire mais de type conique quadratique.

Il existe diverses méthodes pour le résoudre que nous ne développerons pas dans ce

manuscrit (le lecteur peut se rapporter aux travaux de Ben-Tal et Zibulevsky (1995)

par exemple).

La solution du problème PA(Ω)BenTal est robuste tout en étant moins conservative

que la solution de pire cas de Soyster. En effet, il est possible de contrôler le risque de

non satisfaction des contraintes en modifiant la valeur des paramètres Ωi qui condi-

tionnent le degré de conservatisme des contraintes i. Plus sa valeur est grande, plus

la solution est robuste (proche du pire cas). En supposant que les variables aléatoires

ξij sont uniformément distribuées dans [−1, 1], Ben-Tal et al. (2009) montrent que

la probabilité de violation de la contrainte i ne dépasse pas exp(−Ω2i

2 ). Les auteurs

fournissent ainsi un outil fort (qui ne dépend pas de la taille du problème) pour fixer

la valeur du paramètre de robustesse Ωi avec peu d’hypothèses sur les incertitudes.

Il existe donc un compromis entre la robustesse de la solution, à décider avant la


connaissance des incertitudes, et le risque que celle-ci n’appartienne pas au domaine

réalisable prévu par le modèle.

Exemple 1.3 Reprenons l’exemple précédent du problème (P2A). En posant Ω1 = Ω2 = 0.8,

la version robuste selon le modèle de BenTal s’écrit sous la forme du programme quadratique :

P2A(Ω)BenTal

max −2x1 + 3x2

s.c. −9x1 + 20x2 + 0.8z1 ≤ 120

2x1 + 5.5x2 − 0.8z2 ≥ 30

36x21 + 25x2

2 − z21 ≤ 0

x21 + 0.25x2

2 − z22 ≤ 0

x1 ≤ 8

x1, x2, z1, z2 ≥ 0

La solution robuste est x∗BenTal = (1.25, 5.43) et est de valeur égale à 13.80, qui est meilleure

que la valeur de la solution de pire cas de Soyster (qui vaut 8.25).

Il est à noter que, pour les valeurs de Ω1 = Ω2 = 0.8 choisies dans cet exemple, la probabilité de

violation des contraintes est très élevée (autour de 0,77). Dans cet exemple, la taille de l’instance

permet une représentation du domaine des solutions réalisables dans le plan mais est trop faible

pour être pertinente en robustesse.

Dans la littérature, plusieurs applications de problèmes réels empruntent la for-

mulation robuste de Ben-Tal et Nimerovski. Citons, à titre d’exemple, Ben-Tal et

Nimerovski (2002) qui traitent du problème robuste de conception d’antennes, Gold-

farb et Iyengar (2003) qui s’intéressent à la selection de portefeuilles robuste, et

Babonneau et al. (2010) à la planification énergétique et environnementale.

En parallèle, des études théoriques ont été menées pour améliorer le calcul de la

probabilité de non satisfaction des contraintes en fonction des paramètres Ω. Ainsi,

Babonneau et al. (2010) réduisent cette probabilité à exp(−Ω2i

1.5 ). Par ailleurs, ces mêmes

auteurs proposent un autre modèle paramétrique, qui a l’avantage de rester linéaire

dans sa version robuste en approximant l’éllipsoïde par l’intersection d’une boule de

norme infinie et d’une autre boule de norme 1 (modèle non détaillé ici). Enfin, Bertsi-

mas et al. (2004) généralisent l’approche de Ben-Tal et Nimerovski à une modélisation


paramétrique suivant une norme quelconque.

1.2.3 Approche de Bertsimas et Sim

La troisième approche présentée dans ce manuscrit pour le calcul des solutions ro-

bustes au problème (PA) est l’approche paramétrique de Bertsimas et Sim (2004).

Cette approche permet aussi de chercher des solutions robustes en évitant le scéna-

rio extrêmes de pire cas. Son principe est le suivant : les auteurs stipulent que dans la

réalité les paramètres incertains n’atteignent jamais -ou très exceptionnellement- leurs

pires valeurs simultanément, et que seule une partie d’entre eux dévie des valeurs

nominales. Les auteurs traduisent cette idée par l’introduction de paramètres Γi pour

chacune des contraintes i, i = 1 . . . m, qui représentent la somme des déviations to-

tales par rapport aux valeurs nominales de tous les coefficients incertains de la même

contrainte i. L’ensemble d’incertitude noté Φi(Γi) est alors :

Φi(Γi) = ξij ∈ Rn|n

∑j=1|ξij| ≤ Γi ; −1 ≤ ξij ≤ 1 (1.11)

Tout comme dans l’approche de Ben-Tal et Nimerovski, le modèle d’incertitude utilisé

dans cette approche est aussi un modèle en ligne.

La version robuste associée à (PA) selon cette approche s’écrit :

PA(Γ)BS

min

n∑

j=1cjxj

s.c.n∑

j=1aijxj + max

ξ∈Φi(Γi)

n∑

j=1aijξijxj ≤ bi i = 1 . . . m

xj ≥ 0 j = 1 . . . n

Ainsi, pour une contrainte i, la valeur de Γi permet de contrôler la déviation totale

des paramètres incertains de leur valeur nominale. Notons que Γi n’est pas nécessai-

rement un entier mais prend des valeurs dans l’intervalle [0, n]. Par exemple, si Γi = 0

aucune déviation n’est autorisée sur les coefficients de la ieme contrainte et celle-ci est

équivalente à la contrainte nominale. Par contre, si Γi = n tous les paramètres sont

susceptibles de dévier, et l’on revient à la formulation pire cas de Soyster 1.2.1.

Attachons-nous à résoudre le problème PA(Γ)BS. Il est possible de simplifier ce dernier


en le linéarisant. Il suffit pour cela de remarquer que les variables xj, ainsi que les va-

leurs de aij sont non négatives. Ceci nous permet dans un premier temps de remarquer

que la valeur du

maxξ∈Φi(Γi)

n

∑j=1

aijξijxj (1.12)

pour un vecteur x fixé est atteinte pour des valeurs non négatives des variables ξij.

Ceci a pour conséquence la suppression des valeurs absolues dans la formulation du

domaine d’incertitude, qui devient alors :

Φi(Γi) = ξij ∈ Rn|n

∑j=1

ξij ≤ Γi ; 0 ≤ ξij ≤ 1 (1.13)

Dans un second temps, en rappelant que le problème incertain admet une solution

optimale finie quelles que soient les valeurs des incertitudes sur A, nous pouvons

remplacer le sous-problème de maximisation (1.12) par son dual dans l’écriture de

PA(Γ)BS, selon le théorème fort de dualité. Le problème robuste est alors équivalent au

programme linéaire suivant :

PA(Γ)BS

minn∑

j=1cjxj

s.c.n∑

j=1aijxj + πiΓi +

n∑

j=1λij ≤ bi i = 1 . . . m

πi + λij ≥ aijxj i = 1 . . . m, j = 1 . . . n

xj ≥ 0 j = 1 . . . n

πi ≥ 0 i = 1 . . . m

λij ≥ 0 i = 1 . . . m, j = 1 . . . n

où πi, λij correspondent aux variables du problème dual de (1.12).

Les auteurs évaluent le degré de non satisfaction des contraintes à exp(− Γ2i

2n ) (en

supposant que les variables aléatoires ξ sont uniformément distribuées dans [−1, 1]).

Nous remarquons qu’étant donné que cette probabilité dépend de la taille du problème

(plus précisément, du nombre de coefficients incertains dans une même contrainte),

cette approche devient pertinente (apporte un gain significatif par rapport à l’approche

de Soyster) quand la valeur de n est élevée. Par exemple, pour garantir une satisfaction

des contraintes avec une probabilité égale à 99%, si n = 100 alors Γ doit être supérieur


ou égal à 30. Enfin, l’approche de Bertsimas et Sim (2004) a l’avantage de garder la

linéarité du problème dans sa version robuste.

En optimisation combinatoire, Bertsimas et Sim (2003) donnent, selon la même ap-

proche, les versions robustes de plusieurs problèmes d’optimisation dans les réseaux.

Ces versions étant de même complexité que les problèmes associés.

Exemple 1.4 Revenons à l’exemple précédent. Suivant le modèle de Bertsimas et Sim la ver-

sion robuste associée au problème (P2A), notée P2A(Γ)BS, est la suivante :

P2A(Γ)BS

max −2x1 + 3x2

s.c. −9x1 + 20x2 + π1 + λ11 + λ12 ≤ 120

2x1 + 5.5x2 − π2 − λ21 − λ22 ≥ 30

π1 + λ11 − 6x1 ≥ 0

π1 + λ12 − 5x2 ≥ 0

π2 + λ21 − x1 ≥ 0

π2 + λ22 − 0.5x2 ≥ 0

x1 ≤ 8

x1, x2, π1, π2, λ11, λ12, λ21, λ22 ≥ 0

En choisissant les valeurs de Γ1 = Γ2 = 1, la solution robuste est x∗BS = (1.58, 5.37) et

est de valeur égale à 12.95, avec π∗1 = 1.59, π∗2 = 9.47, λ∗11 = 0, λ∗12 = 1.10, λ∗21 = 0,

λ∗22 = 17.37. Il est possible de retrouver le scénario qui correspond à cette solution. En effet,

en remarquant que λ∗12 > 0 et λ∗22 > 0, nous déduisons que les contraintes correspondantes

dans le problème dual sont saturées (d’après le théorème des écarts complémentaires). Ceci nous

permet d’identifier le scénario comme étant égal à a11 = −9, a12 = 25, a21 = 2 et a22 = 5. Le

domaine de solutions réalisables lui correspondant est représenté sur la figure 1.3.

Tout comme l’approche (1.2.2) de Ben-Tal et Nimerovski, la solution robuste x∗BS possède une

meilleure évaluation que celle obtenue par l’approche pire cas de Soyster 1.2.1. Elle est aussi,

pour cet exemple, moins bonne que la solution robuste x∗BenTal .

Notons enfin que la probabilité de violation des contraintes pour les valeurs de Γ1 = Γ2 = 1

est assez élevée (elle approche 0.78). Tout comme l’exemple 1.3, la taille du problème est ici trop


- 3 3 6 9

3

6

9

1 2

1 5

( a ) B S

( c )( b ) m e i

( b ) B S

( b ) p i r

( a ) p i r

x *B S

( a ) m e i

Fig. 1.3 – Domaine des solutions réalisables du problème P2A(Γ)BS

petite pour qu’une étude de robustesse soit pertinente.

Après avoir présenté trois approches définies sur un contexte statique, intéressons

nous dans ce qui suit au contexte multi-étapes.

1.2.4 Approches multi-étapes

Dans le contexte multi-étapes, les décisions du problème sont fractionnées en plusieurs

groupes, chacun étant déterminé à une étape donnée. Citons, à titre d’exemple, des

problèmes de gestion d’une chaîne de production, des problèmes de flots dans un

réseau, ou encore des problèmes de gestion de stock où dans chacun de ces problèmes

les quantités produites, achetées, acheminées ou stockées doivent être calculées sur

plusieurs périodes d’un horizon temporel de manière dynamique.

Dans la réalité, ces problèmes sont souvent touchés par des aléas ; cela peut

concerner par exemple, les prix des produits ou bien la demande à satisfaire. Ainsi,

des approches robustes prenant en compte ces incertitudes ont été développées très


récemment ; elles proposent des solutions robustes adaptées au contexte multi-étapes

de ces problématiques.

En optimisation robuste, les approches multi-étapes ont été introduites de manière

générales par Ben-Tal et al. (2004) et Minoux (2009b). Les auteurs s’intéressent à la prise

de décision en deux étapes sur des programmes linéaires admettant des domaines

réalisables incertains. Il s’agit dans cette approche de distinguer deux groupes disjoints

de variables, tels que les valeurs des variables du premier groupe sont déterminées

avant que l’incertitude ne soit levée, alors que les valeurs des variables du second

groupe, nommées variables de recours ou d’ajustement, sont calculées après connaissance

des incertitudes.

Les approches robustes bi-étapes sont fortement inspirées de l’optimisation sto-

chastique. En effet, en optimisation stochastique les incertitudes sont décrites par

des lois de probabilités, et l’objectif est de décider des variables “here and now”

(ou de première étape) en utilisant l’espérance mathématique de toutes les décisions

de recours. Les variables “wait and see” (ou de seconde étape) sont, quant à elles,

déterminées après la réalisation des incertitudes. Ce raisonnement est étendu à l’opti-

misation robuste où, bien qu’aucune probabilité ne soit disponible sur les coefficients

incertains, les décisions de la première étape sont définies telles qu’il existe toujours

un recours à la seconde étape. Le problème de recours est dans ce cas basé sur la pire

évaluation du problème compte tenu des incertitudes.

Intéressons nous à la formulation mathématique d’un modèle robuste à deux

étapes. Considérons un programme linéaire (PR) dont les variables sont séparées en

deux groupes distincts x et y. Les variables du premier groupe x sont décidées en pré-

sence d’incertitude, et celles du second groupe y le sont, une fois l’incetitude levée (il

s’agit des variables de recours). Appliquons dans ce qui suit l’approche bi-étapes au

programme linéaire (PR) qui s’écrit :

(PR)

min cx

s.c. Ax + Ry ≤ b

x, y ≥ 0

où x est une matrice colonne de dimension n1 et y est une matrice colonne de dimen-

sion n2. La matrice A est de taille m× n1, et la matrice R, nommée matrice de recours,


est de taille m× n2. Les coûts c et le second membre des contraintes b sont respecti-

vement une matrice ligne de taille n1 et une matrice colonne de taille m. Ces derniers

sont supposés certains, l’incertitude ne portant que sur les coefficients des matrices

A et R. Afin de simplifier l’écriture du problème robuste, la notation matricielle est

employée.

L’incertitude sur les matrices A et R est décrite comme suit :

A = A + Aξ (1.14)

et

R = R + Rξ (1.15)

où A, A et R, R sont des matrices de taille respectivement m × n1 et m × n2. Elles

contiennent les valeurs nominales et les déviations associées aux coefficients des

matrices A et R respectivement. Les incertitudes ξ appartiennent à un ensemble

d’incertitude Ψ quelconque (fixe ou paramétrique). Le problème (PR) est supposé

réalisable pour tout (A, R) incertain dans Ψ.

La version robuste bi-étapes associée à (PR), notée (PR)BiE, consiste à déterminer la

solution de première étape x telle que pour toute réalisation du couple (A, R), il existe

un recours y ≥ 0 (à la seconde étape) gardant le problème réalisable. Le problème

robuste est alors le suivant :

(PR)BiE

min cx

s.c. ∀(A, R) ∈ Ψ , ∃y ≥ 0 : Ax + Ry ≤ b

x ≥ 0

D’un point de vue de complexité, Guslitser (2002) démontre que le problème

(PR)BiE est NP-difficile dans le cas d’incertitudes décrites par un polytope. Il devient

facile (polynomial) dans deux cas :

– quand dans leur modélisation, les incertitudes dans chaque contrainte sont in-

dépendantes (modèle d’incertitude en lignes). Dans ce cas, Ben-Tal et al. (2004)

montrent que le problème (PR)BiE est équivalent à la version robuste mono-étape

de Soyster.

– quand le recours est fixe (la matrice R est certaine, ie R ≡ R) et que l’incertitude


est décrite par l’enveloppe convexe de scénarios discrets (résultat prouvé par

Guslitser (2002) pour des problèmes linéaires, et Takeda et al. (2004) généralisent

ce résultat pour des problèmes non linéaires).

Revenons à la formulation du problème (PR)BiE. Afin de simplifier et résoudre ce

problème, Ben-Tal et al. (2004) proposent la relaxation suivante.

Règle de décision linéaire

Dans l’écriture du problème (PR)BiE, on remarque que les variables de recours y dé-

pendent non seulement des variables de décision x mais aussi des incertitudes. Ben-Tal

et al. (2004) choisissent de se restreindre à une relation linéaire entre la réalisation des

incertitudes et les variables de recours. En imposant cette règle de décision linéaire,

les auteurs s’assurent de l’existence d’un recours quelle que soit l’incertitude, et donc

de résoudre une relaxation du problème robuste.

Formellement, suivant cette règle de décision, les variables y s’écrivent :

y = y + Dξ (1.16)

où ξ appartiennent au domaine d’incertitude Ψ. La matrice colonne y et la matrice

D, de taille respectivement n2 et n2 × n1, représentent les nouvelles variables du

problème de recours.

De plus, les auteurs considèrent un recours fixe, c’est-à-dire un recours qui ne dépend

pas des incertitudes. Dans ce cas, la matrice R = R et R ≡ 0 dans l’expression 1.15.

Suivant les hypothèses décrites ci-avant, le problème robuste bi-étapes suivant la règle

de décision linéaire , noté (PR)BiEA, se formule comme suit :

(PR)BiEA

min cx

s.c. Ax + Aξx + RDξ + Ry ≤ b ∀ξ ∈ Ψ

x, y, D ≥ 0

Dans ce cas, toutes les variables du problème sont à déterminer en même temps et le

problème (PR)BiEA est équivalent à une formulation de pire cas de Soyster (voir 1.2.1)


qui s’écrit :

(PR)BiEA

min cx

s.c. maxξ∈ΨAξx + RDξ+ Ry + Ax ≤ b

x, y, D ≥ 0

Il est possible de modéliser les incertitudes dans Ψ par n’importe quel ensemble d’in-

certitude (fixe ou paramétrique). On rappelle néanmoins que cette approche est plus

pertinente que l’approche de Soyster si cet ensemble permet une dépendance en co-

lonnes des incertitudes (Ben-Tal et al. (2004)).

Remarque 1.4 Dans le cas où le recours est variable, la règle de décision linéaire ne garantit

pas la polynomialité du problème robuste. En effet, il a été montré que le problème est dans le

cas général NP-difficile (voir Ben-Tal et al. (2004)).

Se plaçant dans un contexte bi-étapes, l’approche robuste présentée dans cette

section a été utilisée dans de nombreuses applications de problèmes réels. La règle de

décision linéaire est souvent utilisée dans les formulations robustes de ces problèmes.

Citons par exemple, Ben-Tal et al. (2000; 2003) qui l’appliquent respectivement à un

problème de gestion de portefeuilles multi-étapes et un problème de gestion de pro-

duction multi-étapes. Par ailleurs, Babonneau et al. (2010) s’intéressent au problème de

la planification énergétique et environnementale dans un contexte bi-étapes et Erera

et al. (2009) suivent cette approche pour un problème de disponibilité de véhicules

partagés robuste. Chen et al. (2008) tentent de leur côté d’étendre la règle de décision

linéaire, en définissant d’autres règles de décision (comme la règle de décision linéaire

déviée). D’autres références d’applications sont regroupées dans les résumés de Bert-

simas et Thiele et Bertsimas et al. (2007).

Dans la dernière partie de ce chapitre, nous nous intéressons aux problèmes se

modélisant sous forme de programmes linéaires dans lesquels l’incertitudes portent

exclusivement sur le second membre des contraintes. Nous présenterons quelques

résultats de la littérature et exposerons la problématique étudiée dans cette thèse.


1.3 Incertitudes sur le second membre des contraintes

Quand ces travaux de thèse ont débuté, les problèmes linéaires traités dans le cadre de

l’optimisation robuste étaient des problèmes contenant de l’incertitude sur les coeffi-

cients de la fonction objectif, la matrice des contraintes ou la matrice des contraintes et

le second membre. Dans ce dernier cas, les incertitudes portant sur les coefficients du

second membre étaient conjointement traitées avec celles portant sur les coefficients de

la matrice des contraintes, en suivant les approches présentées dans les sections pré-

cédentes de ce chapitre (par exemple l’approche (1.2.3) de Bertsimas et Sim). Si l’on se

propose de traiter un programme linéaire avec des incertitudes portant exclusivement

sur le second membre, il est nécessaire de savoir si ces méthodes sont pertinentes pour

la détermination de solutions robustes.

Afin de traiter ces problèmes, une première approche assez naturelle concerne l’uti-

lisation de la dualité pour transférer l’incertitude se situant dans le second membre

des contraintes aux coefficients de la fonction objectif. Comme cela sera développé ci-

après, nous montrerons que cette possibilité se révèle inadaptée pour la détermination

de solutions robustes au problème incertain en question. De plus, nous allons montrer

que l’utilisation des approches paramétriques dans un contexte statique, comme par

exemple l’approche de Bertsimas et Sim (voir section 1.2) est tout aussi insatisfaisant.

Avant d’aborder ces approches, formulons le problème incertain. Soit (Pb) le pro-

gramme linéaire suivant :

(Pb)

min cx

s.c. Ax ≥ b

x ≥ 0

où x est une matrice colonne de taille n représentant les variables du problème, c est

une matrice ligne de taille n, A est une matrice de taille m× n et le second membre

b est une matrice colonne de taille m. Les coefficients de b sont incertains. Le modèle

d’incertitude est le modèle par intervalles.

Utilisation de la dualité

Le dual d’un programme linéaire (primal) dont le second membre des contraintes est

incertain est un programme linéaire où seuls les coefficients de la fonction objectif sont

1.3. Incertitudes sur le second membre des contraintes 35

incertains. Il semblerait alors pertinent, via la théorie de la dualité, d’exploiter le résul-

tat obtenu pour le cas d’incertitudes sur les coefficients de la fonction objectif. En effet,

afin de déterminer des solutions robustes au problème primal, une approche serait

dans un premier temps d’appliquer un des critères de la décision, comme par exemple

le critère du pire cas (voir section (1.1)), au problème dual. Puis dans un second temps,

retrouver les solutions robustes du problème primal, et cela en exploitant de nouveau

la dualité. Toutefois, cette approche n’est pas concluante comme le montre l’exemple

suivant.

Exemple 1.5 Soit le programme linéaire incertain (P3b) :

(P3b)

min 3x1 + x2

s.c. x1 + x2 ≥ b1

x1 − x2 ≥ b2

x1 ≥ 0, x2 ≥ 0

où les coefficients du second membre varient dans les intervalles suivants b1 ∈ [4, 5] et

b2 ∈ [1, 3].

Tout d’abord, notons que, pour toute valeur de second membre b dans les intervalles correspon-

dant, le problème (P3b) est réalisable, et son optimum est fini. Par conséquent, et d’après le

théorème fort de la dualité, le problème dual admet lui aussi un optimum fini. Il s’écrit :

(D)

max b1y1 + b2y2

s.c. y1 + y2 ≤ 3

y1 − y2 ≤ 1

y1 ≥ 0, y2 ≥ 0

où les coefficients de la fonction objectif b1 et b2 sont incertains, appartenant respectivement

aux intervalles [4, 5] et [1, 3].

Le problème résultant de l’application du critère du pire cas au problème (D) est un problème

facile (voir la proposition (1.1)). Étant donné que les variables du problème sont non négatives,

il suffit d’associer aux paramètres incertains les plus petites valeurs des intervalles. La solution

robuste de pire cas est alors y∗pirCas = (2, 1). Elle est de valeur égale à 9 et est réalisée sous le

scénario bpirCas = (4, 1).


Remplaçons ce scénario dans le problème primal :

(P3b)pirCas

min 3x1 + x2

s.c. x1 + x2 ≥ 4

x1 − x2 ≥ 1

x1 ≥ 0, x2 ≥ 0

La solution optimale x∗ = (5/2, 3/2) est de valeur égale à 9.

Nous observons que la solution x∗ associée au scénario bpirCas = (4, 1) ne correspond pas à la

solution du pire cas pour (P3b). En effet, cette solution n’est réalisable que sur le seul scénario

bpirCas, et il est clair que si elle est choisie avant de connaître la réalisation de l’incertitude, elle

sera non réalisable sur la quasi totalité des scénarios (sauf un seul, égal à bpirCas). Elle ne peut

donc être qualifiée de robuste.

Comme on le voit sur cet exemple, la dualité ne peut être exploitée de cette manière

pour déterminer des solutions robustes au problème incertain. Plus généralement, Mi-

noux (2007a; 2009b) a montré que le problème issu de l’application du critère du

pire cas sur le problème primal était différent de celui obtenu par l’application du

même critère sur le problème dual. Nous reviendrons sur ces problématiques et nous

développerons cette relation de dualité plus en détails au chapitre 2 de ce manuscrit.

Utilisation de l’approche paramétrique de Bertsimas et Sim

La deuxième alternative pour traiter le problème (Pb) est d’utiliser les approches

présentées à la section 1.2 du chapitre courant. Intéressons-nous à l’approche paramé-

trique de Bertsimas et Sim (voir section (1.2.3)) appliquée au problème (Pb).

Rappelons que selon cette approche, les coefficients du second membre sont modélisés

par des intervalles composés d’une valeur nominale autour de laquelle une déviation

est permise. Dans ce cas, tout bi, i = 1 . . . m appartient à l’intervalle [bi − bi, bi + bi], où

bi représente la valeur nominale du coefficient bi et bi sa déviation. Le décideur doit

fixer un budget d’incertitude pour chaque contrainte, l’objectif étant de déterminer des

solutions robustes dans ce budget, autorisant ainsi une faible violation des contraintes.

Construisons la version robuste du problème (Pb) selon cette approche. Nous intro-


duisons pour ce faire un vecteur Γ de taille m où chaque composante représente le

budget d’incertitude de la ieme contrainte, pour i = 1 . . . m. Nous remarquons que, ne

disposant que d’un seul coefficient incertain par contrainte, le budget d’incertitude Γi

(i = 1 . . . m) n’excède pas 1, et donc Γi ∈ [0, 1]. Ceci implique que la version robuste de

(Pb) se déduit aisément et s’écrit :

Pb(Γ)BS

min cx

s.c. Ax ≥ b + Γb

x ≥ 0

Nous observons que cette approche conduit à décider sur la base d’un scénario unique

induit par les valeurs de Γi. Par conséquent, l’application directe de cette approche sur

le problème incertain (Pb) est peu pertinente.

Nous nous proposons dans le chapitre 3 d’adapter l’approche de Bertsimas et Sim

au problème incertain (Pb) en considérant non plus un budget d’incertitude par

contrainte (modèle d’incertitude en ligne), mais un budget commun à l’ensemble des

coefficients incertains du second membre (modèle d’incertitude colonne).

Approches multi-étapes

Nous nous intéressons dans cette dernière section aux approches robustes pour le trai-

tement de (Pb) placé dans un contexte multi-étapes. Durant ces dernières années les

approches robustes multi-étapes, et notamment des approches bi-étapes, ont suscité

un fort engouement pour la résolution d’applications réelles. Citons à titre d’exemple

les travaux de Minoux (2007a;b; 2009b) pour des problèmes d’ordonnancement et Mi-

noux (2008) pour un problème de gestion de stock. Atamtürk et Zhang (2007) traitent

quant à eux d’un problème de dimensionnement de réseaux et Solyali et al. (2010)

s’intéressant à un problème de tournées de véhicules.

Nous présentons brièvement l’approche robuste bi-étapes, suivie par Thiele et al.

(2009), qui vise à calculer des solutions robustes d’un programme linéaire incertain

particulier, où une partie des coefficients du second membre des contraintes sont

incertains.


Définissons le problème. Soit un programme linéaire (H) suivant :

(H)

min cx

s.c. Ax = b

A′x ≥ b′

où x est une matrice colonne de taille n représentant les variables du problème, c est

une matrice ligne de taille n, les matrices A et A′ de taille respectivement m × n et

m′ × n, et b et b′ sont des matrices colonnes de taille respectivement m et m′. Nous

supposons que le domaine des solutions réalisables de (H) est non vide, et que l’opti-

mum est atteint en une valeur finie.

Les auteurs s’intéressent à la prise de décision robuste quand les coefficients du second

membre b sont incertains. Pour ce faire, ils adoptent une approche bi-étapes et cela en

ajoutant de nouvelles variables : les variables de recours y. Celles-ci ont pour rôle de

mesurer le degré de violation des contraintes d’égalité à l’aide de pénalités reportées

dans la fonction objectif. Le problème qu’ils proposent de résoudre est le suivant :

(H′)

min cx + py

s.c. Ax + Ry = b

A′x ≥ b′

y ≥ 0

où y est une matrice colonne de taille l, p est une matrice ligne de pénalités de taille l

et R représente la matrice de recours, de taille m× l. Ici, le recours est supposé fixe (R

ne dépend pas des incertitudes).

Soit le domaine d’incertitude Ψ dans lequel varient les valeurs des coefficients incer-

tains de b. La version robuste bi-étapes (H′)BiE consiste à déterminer les décisions de

première étape x telles que quelle que soit l’incertitude dans le domaine Ψ, un recours

y est possible à la seconde étape. Il s’écrit alors :

(H′)BiE

min cx + maxb∈Ψ

minRy=b−Ax, y≥0

py

s.c. A′x ≥ b′

Le problème (H′)BiE est un problème de type min-max-min, qui est dans le cas général


difficile à résoudre. Afin de le simplifier, les auteurs supposent l’existence d’un recours

complet, où pour tout vecteur x réalisable (de première étape) le problème de recours

admet une solution finie. En d’autres termes, le problème de minimisation suivant :

minRy=b−Ax, y≥0

py (1.17)

est réalisable et admet un optimum fini pour tout b ∈ Ψ. Sa valeur peut donc être

substituée par la valeur du problème dual (selon le théorème fort de la dualité). Par

conséquent, le problème (H′)BiE est équivalent à : min cx + maxb∈Ψ, Rtu≤pt

(b− Ax)tu

s.c. A′x ≥ b′

où u sont les variables du problème dual de (1.17).

Dans le cas où le domaine incertain Ψ est un polyèdre, les auteurs montrent que le

problème (H′)BiE est un problème d’optimisation convexe, et emploient l’algorithme

proposé par Kelley (1960) pour le résoudre. Cet algorithme se base sur une procédure

de génération de contraintes dont nous verrons le détail au chapitre 4.

Conclusion et problématique

Nous avons présenté dans ce chapitre les principaux résultats bibliographiques relatifs

à la prise en compte d’incertitude affectant les coefficients de programmes linéaires.

Nous nous sommes limités à la modélisation de ces incertitudes par des intervalles

continus. Trois cas ont été distingués : un premier cas où les incertitudes portent sur la

fonction objectif, un deuxième cas où elles portent sur la matrice des contraintes, et en-

fin le cas où les incertitudes concernent uniquement le second membre des contraintes.

Dans le premier cas de figure, nous avons détaillé les résultats de l’application des

critères issus de la théorie de la décision, et dressé un panorama non exhaustif des

travaux qui ont été menés sur le sujet. Le contexte de décision dans lequel s’inscrivent

la plupart des approches existantes est celui où la décision doit être prise en présence

d’incertitude. Le premier critère que nous avons abordé est le critère du pire cas qui

vise à se prémunir contre la pire éventualité. Pour la modélisation des incertitudes par


intervalles, ce problème est facile. Le critère du pire cas est particulièrement adapté

lorsque le décideur est averse au risque, notamment dans les domaines d’application

touchant par exemple au nucléaire, à la santé ou à l’environnement. Cependant, la

solution robuste de pire cas peut être jugée trop conservative (car ne prend aucun

risque) et peut se révéler trop coûteuse.

Parmi les autres critères pouvant être appliqués lorsque l’incertitude porte sur

les coefficients de la fonction objectif, le critère du regret maximum propose une

solution robuste moins conservative que la solution de pire cas. Ce critère est utile

lorsqu’une prise de risque est acceptable par le décideur et est souvent employé dans

le domaine de la finance où les investisseurs souhaitent avoir le moins de regret quand

ils prennent leurs décisions.

Dans le deuxième cas de figure (incertitude portant sur la matrice des contraintes),

le domaine réalisable est affecté par l’incertitude. Ainsi, la détermination de solutions

robustes sera étroitement liée à la réalisabilité du problème. Nous avons séparé les

approches de la littérature en deux familles, selon le contexte décisionnel. Dans le

contexte statique, il s’agit de prendre une décision avant que l’incertitude ne se réalise.

Le second contexte, quant à lui, englobe les approches multi-étapes, où la solution

robuste se construit en plusieurs étapes, et ceci au fur et à mesure que l’incertitude est

levée.

Trois approches ont été exposées dans le contexte statique. La première approche,

celle de Soyster, est une approche de pire cas. La solution robuste recherchée est réali-

sable pour tous les scénarios pouvant se réaliser. Les deux approches de Ben-Tal et al.

et celle de Bertsimas et Sim visent à accepter une part de risque, et cela en autorisant

une faible violation des contraintes, dans le but de déterminer des solutions robustes

moins conservatives que la solution de Soyster.

Dans un contexte multi-étapes, de nouvelles approches robustes ont vu le jour au

cours de ces quelques dernières années, qui s’inspirent de l’optimisation stochastique.

Elles sont employées lorsque l’information sur les coefficients incertains peut être

révélée sur plusieurs étapes. Ces approches possèdent l’avantage d’être flexibles, mais

l’inconvénient d’engendrer des modèles souvent difficiles à résoudre.


Enfin, dans le dernier cas de figure (incertitudes portant exclusivement sur le se-

cond membre des contraintes), peu de travaux avaient été réalisés au moment où cette

thèse a débuté. Nous avons mis en évidence la nécessité d’adapter et de développer

des méthodologies propres pour répondre à la préoccupation de la robustesse pour ce

type de problème, et cela en distinguant les contextes de décision.

Le contexte général de ce travail de thèse est le traitement robuste des programmes

linéaires où les coefficients du second membre des contraintes sont incertains (que

nous modéliserons à l’aide d’intervalles continus). Dans le chapitre suivant, nous dis-

tinguerons deux contextes décisionnels pour lesquels nous construirons les versions

robustes aux problèmes incertains.

2Programmes linéaires avec

incertitudes sur le second membre

des contraintes

Sommaire

Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

2.1 Premier contexte décisionnel : des décisions robustes . . . . . . . . . 47

2.1.1 Programmes linéaires avec contraintes d’inégalité . . . . . . . . . . . . . 48

2.1.2 Programmes linéaires avec contraintes d’égalité : modèle de pénalités . 51

2.2 Second contexte décisionnel : pire et meilleur optimaux . . . . . . . 56

2.2.1 Programmes linéaires avec contraintes d’inégalité . . . . . . . . . . . . . 56

2.2.2 Programmes linéaires avec contraintes d’égalité . . . . . . . . . . . . . . 58

2.2.3 Programmes linéaires quelconques . . . . . . . . . . . . . . . . . . . . . . 64

2.3 Robustesse et dualité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

2.3.1 Critère du meilleur cas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

2.3.2 Dualité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68

Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

Dans ce chapitre, il sera question de programmes linéaires dans lesquels l’incerti-

tude porte exclusivement sur les coefficients du second membre des contraintes.

Nous séparons notre étude selon le contexte décisionnel du problème. Dans le premier

contexte, une décision doit être prise avant la réalisation de l’incertain. Nous cher-

chons alors une solution dont la réalisabilité ne sera pas perturbée par la réalisation

43

44 Chapitre 2. Programmes linéaires avec seconds membres incertains

de l’incertain. Dans le second contexte, nous considérons que l’incertitude sera levée

au moment de la prise de décision. Dans un cadre prévisionnel, notre intérêt est alors

porté sur l’évaluation d’une solution optimale selon les différentes réalisations pos-

sibles de l’incertitude. Par ailleurs, nous nous attachons à l’emploi de la dualité en

robustesse pour ces mêmes problèmes, avec une approche pire cas.

45

Introduction

Dans ce chapitre, nous nous intéressons à la prise en compte d’incertitudes affectant

exclusivement les coefficients du second membre des contraintes d’un programme li-

néaire. Se plaçant dans un contexte statique, il s’agit de définir des méthodologies

spécifiques qui répondent à la préoccupation de la robustesse pour ces problèmes.

Pour ce faire, nous distinguerons deux contextes décisionnels différents.

– Dans le premier contexte, nous considérons qu’une décision doit être prise avant

la réalisation de l’incertain. Pour illustrer cela, prenons l’exemple d’un problème

de gestion de stockage de marchandises où le décideur doit approvisionner ses

centres de stockage une seule fois dans une période donnée, dans le but de

satisfaire toutes les demandes à venir tout au long de cette période. Au moment

de la prise de décision des quantités à stocker, les demandes des clients ne sont

pas connues. Le décideur souhaite alors adopter une politique (ou solution) qui

permettrait de satisfaire toutes les demandes, quel que soit le scénario qui se

réalisera.

– Nous définissons un second contexte où l’incertitude est levée avant la prise de

décision. Ainsi, pour une réalisation donnée, le décideur sait calculer la solu-

tion optimale du problème, qui serait alors déterministe. La préoccupation de

la robustesse est alors différente. En effet, dans une phase de planification, le

décideur peut s’intéresser au coût engendré par les différentes décisions qu’il

pourrait prendre selon les scénarios qui se réalisent. Par exemple, considérons

un centre de production de marchandises, où les produits sont manufacturés

à la demande. Ici, tant que les clients n’effectuent pas de commande, aucune

marchandise n’est produite. Dans ce cas, le décideur attend la réalisation de la

demande pour prendre sa décision (achat de matières premières, transport, . . . ).

En revanche, dans une phase de planification, pour des considérations budgé-

taires par exemple, le décideur peut s’intéresser à la fourchette de variation de

ses coûts en fonction des scénarios éventuels de la demande à venir, notamment

le pire scénario, celui engendrant le coût le plus élevé, et le meilleur scénario,

celui engendrant le coût le plus faible (correspondant respectivement à la plus

forte demande et la plus faible demande).

Dans la première section de ce chapitre, nous traiterons du premier contexte de

décision. Dans ce contexte, l’objectif est de décider avant la réalisation de l’incertain


tout en se prémunissant contre tout scénario pouvant se réaliser, et donc le pire d’entre

eux. Nous nous attacherons alors au calcul de solutions robustes de pire cas. Selon la

définition de Soyster (1973) (voir la section 1.2.1 du chapitre 1), ces solutions doivent

être réalisables quel que soit le scénario qui se produit.

Nous montrerons dans la section 2.1.1 que le calcul de ces solutions, associé à un

problème admettant des contraintes d’inégalité exclusivement, est un problème facile.

En revanche, quand le problème incertain contient des contraintes d’égalité, ce calcul

n’est plus pertinent. En effet, chaque scénario définissant un ensemble unique de

solutions réalisables, il s’en suit que pour toute solution, il existe au moins un scénario

pour lequel cette solution n’est pas réalisable, et il n’existe pas de solution réalisable

sur tous les scénarios. Il n’y a donc pas de décision de pire cas, puisqu’il n’est pas

possible de discriminer une solution d’une autre. Dans ce cas, le décideur est obligé

de choisir une solution puis de constater la violation des contraintes.

Néanmoins, dans certains contextes décisionnels, il est possible de mesurer le

coût engendré par la non réalisabilité d’une solution sur un scénario donné. C’est le

cas dans l’exemple du problème de gestion de stock, où l’équilibrage entre offre et

demande est souvent exprimé par des égalités. Lorsque la demande des clients est

incertaine (affectant ainsi le second membre des contraintes du modèle), le décideur

ne peut pas choisir, avant la réalisation de la demande, une solution de pire cas lui

garantissant de satisfaire la demande quelle qu’elle soit. Il est alors courant pour

ce type de problème, face à une situation de rupture de stocks, que le décideur ait

recours à un marché extérieur pour se procurer des marchandises et ceci en payant

des pénalités conséquentes. Le cas contraire peut aussi se dérouler, le décideur se

retrouvant avec un surplus de marchandises à stocker au prix fort chez un concurrent.

Ici, la non réalisation des contraintes d’égalité est aussi quantifiée par des pénalités.

Dans la section 2.1.2, nous faisons appel à ce type de modèle, nommé modèle de

pénalités, qui permet de mesurer par des pénalités le coût de la non satisfaction d’une

contrainte d’égalité. Il devient alors possible de discriminer chaque solution sur n’im-

porte quel scénario. Dans ce cas, la détermination d’une solution robuste de pire cas

est possible. Elle correspondra à la solution qui minimise le coût total plus les pénalités.

Dans le second contexte de décision, abordé dans la deuxième section du chapitre,

2.1. Premier contexte décisionnel : des décisions robustes 47

nous nous intéressons aux valeurs de l’optimum du problème incertain en fonction

des scénarios qui se présentent. Ici, l’objectif est de fournir au décideur des indicateurs

concernant l’intervalle de variation de la valeur de l’optimum. Cet intervalle s’obtient

par le calcul de deux valeurs extrêmes : la valeur du meilleur optimum et celle du

pire optimum. Les deux scénarios extrêmes qui leurs sont associés sont aussi source

d’information pour le décideur. Par ailleurs, l’évaluation du pire optimum sera d’une

importance primordiale, comme nous le verrons par la suite, lors de la détermination

d’une solution robuste dans un contexte multi-étapes. Nous reviendrons plus en dé-

tails, au chapitre 4 de ce manuscrit, sur le calcul de cette solution, notamment pour le

problème de localisation et de transport robuste.

Enfin, dans la dernière section, nous reviendrons sur les relations de dualité abor-

dées à la section 1.3 du chapitre précèdent. Nous ferons le lien entre l’emploi du critère

du pire cas appliqué à des problèmes contenant des incertitudes sur les coefficients du

second membre des contraintes d’une part, et leurs problèmes duaux qui contiennent

des incertitudes sur la fonction objectif d’autre part. Pour ce faire, nous utiliserons un

autre critère, le critère du meilleur cas. Une partie de ces travaux ont été publiés dans

Gabrel et al. (2008) et Gabrel et al. (2010a).

2.1 Premier contexte décisionnel : des décisions robustes

Dans cette section, il est question de la détermination de décisions robustes pour des

programmes linéaires dont le second membre des contraintes est incertain. Nous nous

situons dans un contexte décisionnel où la décision doit être prise avant la réalisation

de l’incertain. Dans ce cas, nous cherchons des solutions robustes qui, selon l’approche

de Soyster (1973) (voir la section 1.2.1), doivent être des solutions réalisables quel que

soit le scénario qui se produit.

La détermination de telles solutions dépend de la nature des contraintes du

problème. En effet, nous rappelons que lorsque le problème admet des contraintes

d’égalité, il n’existe pas de solution réalisable sur tous les scénarios. Nous séparons

alors notre étude en deux parties : nous traiterons en premier les programmes linéaires

contenant des contraintes d’inégalité, puis nous emploierons un modèle de pénalités


pour traiter les programmes linéaires avec contraintes d’égalité.

2.1.1 Programmes linéaires avec contraintes d’inégalité

Soit le problème linéaire (Pb≥) suivant :

(Pb≥)

min cx

s.c. Ax ≥ b(2.1)

où x une matrice colonne de taille n représentant les variables du problème, c est une

matrice ligne de taille n, la matrice des contraintes A est de dimension m × n et de

rang égal à m, et le second membre b est une matrice colonne de taille m.

Nous supposons que pour toute contrainte i, i = 1 . . . m, le coefficient incertain

bi appartient à l’intervalle [bi, bi] (avec bi ≤ bi). Notons B le produit cartésien des

intervalles [bi, bi], pour i = 1 . . . m.

Tout d’abord, énonçons quelques définitions. Pour tout scénario b dans B nous défi-

nissons l’ensemble :

Xb≥ = x ∈ Rn : Ax ≥ b (2.2)

comme étant le domaine des solutions réalisables de (Pb≥). Nous supposerons que le

polyèdre Xb≥ est non vide pour tout b.

Par ailleurs, pour tout vecteur x de Rn, nous définissons la valeur de x pour le pro-

blème Pb≥(x), notée v≥(b, x), comme suit :

v≥(b, x) =

cx si x ∈ Xb

≥

+∞ sinon(2.3)

De plus, nous faisons l’hypothèse que la solution optimale de (Pb≥) pour un scénario b

fixé dans B est de valeur finie. Cette valeur est notée v∗(Pb≥).

Enfin, soit X≥ l’ensemble des solutions réalisables résultant de l’intersection des do-

maines réalisables sur tous les scénarios b et X≥ l’ensemble des solutions réalisables


de (Pb≥) pour au moins un scénario b. Formellement, ces ensembles correspondent à :

X≥ =⋂

b∈BXb≥ (2.4)

et

X≥ =⋃

b∈BXb≥ (2.5)

Il est clair que l’ensemble X≥ est non vide. En effet, pour tout vecteur b fixé dans B, le

domaine des solutions Xb≥ est par hypothèse non vide. L’union de tous les domaines

est par conséquent non vide. Plus précisément, X≥ représente le plus grand domaine

de solutions réalisables et coïncide avec Xb≥.

Par ailleurs, l’ensemble X≥ est lui aussi non vide. En effet, étant donné les contraintes

d’inégalité de (Pb≥), il est clair que le polyèdre Xb

≥ est inclus dans tout autre polyèdre

Xb≥ où b ∈ B. Puisque Xb

≥ est non vide, il s’en suit que X≥ est aussi non vide. Les deux

domaines se confondent et représentent le plus petit domaine de solutions réalisables

associé au problème (Pb≥).

Après avoir défini le domaine d’incertitude du problème, calculons une solution

robuste de pire cas associée au problème (Pb≥). Il s’agit de déterminer la solution qui

possède la meilleure évaluation dans le scénario de pire cas. Le problème robuste, noté

(Pb≥)pirCas, s’écrit :

(Pb≥)pirCas

minx∈X≥

maxb∈B

v≥(b, x) (2.6)

où v≥(b, x) est défini par (2.3).

Soit x une solution appartenant à X≥. Nous observons que l’évaluation de x est

constante quel que soit le scénario b ∈ B. Par conséquent, la pire évaluation de x

est égale à :

maxb∈B

v≥(b, x) = cx (2.7)

Par ailleurs, la pire évaluation de toute autre solution qui n’appartient pas à X≥ est


égale à +∞ (car elle est non réalisable sur le scénario b). Par conséquent, la solution

robuste selon le critère du pire cas (qui minimise (2.7)) appartient nécessairement à

X≥.

En rappelant que X≥ n’est autre que Xb≥, nous déduisons que la solution robuste de

pire cas de (Pb≥) s’obtient par la résolution du programme linéaire admettant le plus

petit domaine réalisable :

(Pb≥)pirCas ≡ (Pb

≥)

min cx

s.c. Ax ≥ b

Exemple 2.1 Soit le programme linéaire suivant :

(P4b≥)

min 5x1 − 5x2

s.c. 2x1 + x2 ≥ b1

x1 − 2x2 ≥ −b2

x1 ≤ 6

x1 ≥ 0 ; x2 ≥ 0

où les coefficients b1 et b2 du second membre des contraintes sont incertains et appartiennent

aux intervalles suivants : b1 ∈ [6, 10] et b2 ∈ [4, 8].

2 4 6

2

4

6 b 1 = 6

b 1 = 1 0b 2 = 8

x p i r C a s

b 2 = 4

Fig. 2.1 – Solution optimale suivant le critère du pire cas pour (P4b≥)


La solution robuste de pire cas est égale à x∗pirCas = (16/5, 18/5) et sa valeur est égale à

−2. Elle est obtenue pour le scénario b1 = 10 et b2 = 4 définissant le plus petit domaine de

solutions réalisables, comme illustré dans figure (2.1)).

2.1.2 Programmes linéaires avec contraintes d’égalité : modèle de pénalités

Dans cette section, nous nous intéressons aux programmes linéaires dans lesquels les

contraintes sont exclusivement des égalités. En premier, nous montrerons (à l’aide d’un

exemple) que la détermination d’une solution robuste réalisable sur tous les scénarios

est non pertinente. Puis, nous proposerons un modèle, dit modèle de pénalités, pour

lequel il sera possible de décider de solutions robustes de pire cas.

Soit un programme linéaire de minimisation contenant exclusivement des

contraintes d’égalité, qu’on notera (Pb=) :

(Pb=)

min cx

s.c. Ax = b

x ≥ 0

sachant que x est une matrice colonne de taille n des variables du problème, la matrice

ligne c est de taille n, la matrice des contraintes A est de dimension m× n et le second

membre b est une matrice colonne de taille m. Cette dernière est incertaine : chaque

coefficient bi de la ieme contrainte varie dans l’intervalle [bi, bi] (avec bi ≤ bi), i = 1 . . . m.

Notons B le produit cartésien des intervalles [bi, bi], pour i = 1 . . . m.

Pour tout scénario b dans B, notons :

Xb= = x ∈ Rn : Ax = b, x ≥ 0 (2.8)

comme étant le domaine des solutions réalisables de (Pb=). Le polyèdre Xb

= est supposé

non vide pour tout vecteur b. De plus, notons v∗(Pb=) la valeur (que nous supposons

finie) de l’optimum du problème (Pb=) pour un scénario b fixé dans B.

Par ailleurs, pour tout vecteur x de Rn, nous définissons la valeur de x pour le pro-


blème Pb=(x), notée v=(b, x), comme suit :

v=(b, x) =

cx si x ∈ Xb

=

+∞ sinon(2.9)

Enfin, nous définissons X= l’ensemble des solutions réalisables de (Pb=) pour au moins

un scénario b :

X= =⋃

b∈BXb

= (2.10)

Remarque 2.1 Il est clair que X= est non vide. En revanche, l’ensemble défini par l’intersec-

tion des domaines de solutions réalisables sur tous les scénarios est quant à lui vide.

Afin d’illustrer la spécificité de (Pb=) par rapport à (Pb

≥) considérons l’exemple

suivant. Soit le problème incertain (P5b) :

(P5b)

min 5x1 − 10x2

s.c. x1 + 2x2 = b1

−x1 + 2x2 = b2

x1 ≥ 0 ; x2 ≥ 0

où les contraintes sont des égalités et le second membre est incertain avec b1 ∈ [9, 14]

et b2 ∈ [2, 8].

L’ensemble, noté X(P5b), représentant l’union de toutes les solutions réalisables,

s’écrit :

X(P5b) = (x1, x2) ∈ R+ ×R+ : 9 ≤ x1 + 2x2 ≤ 14, 2 ≤ −x1 + 2x2 ≤ 8

Soit x′ = (x′1, x′2) = (2, 4) une solution réalisable de X(P5b). Nous remarquons que

cette solution est réalisable sur un seul scénario : b′1 = 10 et b′2 = 6. Il s’en suit que la

pire évaluation de x′ sur tous les scénarios possibles est :

maxb∈B

v=(b, x′) = +∞

Cette observation étant valide pour toute solution dans X(P5b), il n’est plus possible

de discriminer une solution d’une autre solution. La décision de pire cas qu’on choi-


sirait, avant la réalisation des incertitudes, pour se prémunir contre tous les scénarios

possibles n’existe pas.

Dans ce qui suit, nous proposons une alternative qu’il est possible d’employer dans

certains contextes de décisions. Dans cette approche l’objectif est de limiter la distance

à la réalisabilité d’une solution et cela en intégrant dans le modèle des pénalités de

violation des contraintes. Supposons, en effet, que la non satisfaction d’une contrainte

d’égalité puisse être traduite par un surcoût connu, que le décideur accepte de payer.

Il est alors possible d’évaluer le coût d’une solution (son coût réel auquel s’ajoutent

des pénalités) sur tous les scénarios et par conséquent il devient envisageable de

déterminer la décision la “moins irréalisable”.

Formellement, nous employons un modèle, dit de pénalités, où la non satisfaction

de toute contrainte i, i = 1 . . . m du problème initial (Pb=) est mesurée par une nouvelle

variable ei, i = 1 . . . m telle que :

ei = (n

∑j=1

aijxj − bi) (2.11)

et l’évaluation d’une solution x ∈ X= pour le scénario b est définie par :

vbp(x) =

n

∑j=1

cjxj +m

∑i=1

max(piei , −qiei) (2.12)

où pi et qi sont des pénalités positives relatives à ei ≥ 0 et ei ≤ 0 respectivement.

La pire évaluation de la solution x sur tous les scénarios n’est plus infinie mais se

calcule comme suit :


maxb∈B

vbp(x) = max

b∈B

n

∑j=1

cjxj +m

∑i=1

max (piei , −qiei) (2.13)

=n

∑j=1

cjxj + maxb∈B

m

∑i=1

max(pi(n

∑j=1

aijxj − bi) , qi(bi −n

∑j=1

aijxj)) (2.14)

=n

∑j=1

cjxj +m

∑i=1

maxbi∈[bi ,bi ]

max(pi(n

∑j=1


∑j=1

aijxj)) (2.15)

=n

∑j=1

cjxj +m

∑i=1

max (pi(n

∑j=1


∑j=1

aijxj)) (2.16)

L’égalité (2.14) est vérifiée car les coûts du vecteur c sont certains, l’incertitude ne

portant que sur les coefficients du second membre b. L’égalité (2.15) est due au fait

que toutes les contraintes soient indépendantes (par hypothèse). Enfin, l’égalité (2.16)

est obtenue en rappelant que chaque coefficient du vecteur b appartient à un intervalle

unique, et que par conséquent le maximum pour chacun est atteint en une de ses

bornes.

Sachant évaluer toute solution sur n’importe quel scénario, nous pouvons calculer

la solution robuste de pire cas. Celle-ci s’obtient par la résolution du problème noté

(Pbp)pirCas qui s’écrit :

(Pbp)pirCas

minx≥0

maxb∈B

vbp(x)

Ce problème se simplifie en un programme linéaire comme suit :

(Pbp)pirCas

minn∑

j=1cjxj +

m∑

i=1yi

s.c. yi − pin∑

j=1aijxj ≥ −pibi i = 1 . . . m

yi + qin∑

j=1aijxj ≥ qibi i = 1 . . . m

xj ≥ 0 j = 1 . . . n

yi ≥ 0 i = 1 . . . m

Exemple 2.2 Reprenons maintenant le programme linéaire incertain (P5b=) que nous ne

pouvions traiter au préalable.

Nous considérons que la non satisfaction de chacune des contraintes d’égalité engendre les


pénalités suivantes : p1 = p2 = q1 = q2 = 100, alors suivant le modèle de pénalités présenté ci-

dessus, la solution robuste de pire cas s’obtient par la résolution du problème, noté (P5bp)pirCas,

qui s’écrit :

(P5bp)pirCas

min 5x1 − 10x2 + y1 + y2

s.c. y1 − 100x1 − 200x2 ≥ −900

y1 + 100x1 + 200x2 ≥ 1400

y2 + 100x1 − 200x2 ≥ −200

y2 − 100x1 + 200x2 ≥ 800

x1, x2, y1, y2 ≥ 0

La solution optimale est x∗pirCas = (3.25, 4.125, 250, 300) de valeur égale à 525.

La figure (2.2) illustre la projection de la solution x∗pirCas sur l’espace à deux dimensions formé

par les variables x1 et x2. Nous remarquons que cette solution correspond à la solution du

problème selon le scénario correspondant à b1 = 11.5 et b2 = 5, qui n’est autre que bi+bi2

pour les contrainte i = 1, 2. Nous observons, qu’étant donné des pénalités égales et de valeurs

bien plus élevées que les coûts du vecteur c, le scénario de pire cas est constitué des valeurs

du second membre qui se situent au milieu des intervalles. En effet, ce scénario est celui qui

engendre le plus faible coût de pénalités de non satisfaction des contraintes d’égalité.

2 4 6

2

4

6

b 1 = 1 4

b 1 = 1 1 . 5

b 1 = 9

b 2 = 8

b 2 = 5

x p i r C a s

b 2 = 2

Fig. 2.2 – Solution optimale suivant le critère du pire cas pour (P5bp)


2.2 Second contexte décisionnel : pire et meilleur optimaux

Nous considérons à présent des problèmes incertains s’inscrivant dans un autre

contexte de décision, où l’incertitude est levée au moment de la prise de décision.

Dans ce cas, le décideur est capable de choisir la meilleure solution étant donnée la

réalisation de l’aléa. Il n’y a pas lieu de déterminer de décision robuste de pire cas.

Cependant, afin de préparer la prise de décision à venir, notamment pour des besoins

de planification, il peut être profitable au décideur de calculer les coûts des différentes

solutions qu’il pourrait être amené à choisir. Nous proposons alors de calculer deux

valeurs extrêmes de l’optimum : la plus grande valeur, nommée pire optimum et la

plus petite, nommée meilleur optimum. Ainsi, nous exhiberons d’une part l’intervalle

de variation des valeurs des solutions optimales, et d’autre part les scénarios extrêmes

pouvant se réaliser.

Le calcul du pire et du meilleur optimum sont des notions relativement récentes

dans la littérature (voir Alefeld et Herzberger (1983), Mráz (1998), Chinneck et Rama-

dan (2000), Fiedler et al. (2006), Hladìk). Dans ces travaux, sont traités des programmes

linéaires dans lesquels tous les coefficients du problème sont potentiellement incer-

tains et représentés par des intervalles. Compte tenu de ces incertitudes, il s’agit de

calculer les deux valeurs extrêmes de l’optimum : la plus grande valeur et la plus pe-

tite valeur. Dans la section suivante, nous calculerons ces deux valeurs dans le cas de

programmes linéaires où seuls les coefficients du second membre sont incertains. Nous

étudierons également la complexité des problèmes engendrés. Nous commencerons

par traiter des problèmes contenant des contraintes d’inégalité, puis ceux contenant

des contraintes d’égalité et enfin nous généraliserons nos résultats à des problèmes

quelconques.

2.2.1 Programmes linéaires avec contraintes d’inégalité

Calcul du pire optimum

La valeur du pire optimum dans le cas du problème (Pb≥) est la plus grande évaluation

d’une solution optimale (dans le cas d’un problème de minimisation) parmi toutes les

solutions optimales selon les différents scénarios possibles. Son calcul s’obtient par la

2.2. Second contexte décisionnel : pire et meilleur optimaux 57

résolution du problème :

(Pb≥)pirOpt

maxb∈B

v∗(Pb≥)

où v∗(Pb≥) est la valeur de la solution optimale du problème (Pb

≥) lorsque le scénario b

est réalisé.

Proposition 2.1 Le calcul du pire optimum d’un programme linéaire avec des contraintes

d’inégalité, où le second membre des contraintes est incertain et appartenant à des intervalles

est un problème polynomial. Il est donné par la valeur de la solution optimale du programme

linéaire suivant :

(Pb≥)pirOpt ≡ (Pb

≥)

min cx

s.c. Ax ≥ b

Démonstration. Compte tenu du sens des contraintes dans (Pb≥), il est clair que le do-

maine réalisable Xb≥ pour le scénario b est inclus dans tout autre domaine réalisable Xb

≥,

où b est un scénario quelconque dans B. Par conséquent, la relation v∗(Pb≥) ≤ v∗(Pb

≥)

est vérifiée pour tout b ∈ B. Ceci implique que la valeur du pire optimum pour le

problème (Pb≥) est la valeur de la solution optimale du programme linéaire (Pb

≥).

Nous pouvons retrouver ce résultat en adoptant le raisonnement suivant. Rappe-

lons que, pour tout scénario b dans B, le problème (Pb≥) est réalisable, et son optimum

est atteint en une valeur finie. Selon le théorème fort de la dualité, il est possible de

remplacer le problème de minimisation dans l’écriture de (Pb≥)pirOpt par son dual. Nous

obtenons : maxb∈B

maxAty=ct, y≥0

bty

Ce problème se simplifie en remarquant que les variables y sont non négatives, et

revient à résoudre le programme linéaire suivant :max b

ty

s.c. Aty = ct

y ≥ 0

qui, en appliquant de nouveau le théorème fort de la dualité, est équivalent à :

(Pb≥)

min cx

s.c. Ax ≥ b


Remarque 2.2 Le calcul d’une solution de pire cas pour (Pb≥) (voir section 2.1.1) coïncide

avec le calcul d’un pire optimum pour le même problème. En effet, pour le problème linéaire

incertain (Pb≥), la valeur de la solution robustes de pire cas est le pire optimum. Ces deux

problèmes sont équivalents au programme linéaire défini selon le scénario qui décrit le plus

petit domaine réalisable Xb≥.

Calcul du meilleur optimum

La valeur du meilleur optimum associé au problème (Pb≥) représente la valeur la plus

favorable (dans le cas d’une minimisation, c’est la plus faible) d’une solution opti-

male sur tous les scénarios b dans B. Cette valeur, associée à celle d’un pire optimum,

forment les bornes de l’intervalle de variation de l’optimum du problème incertain

(Pb≥). Le meilleur optimum se calcule comme suit :

(Pb≥)meiOpt

minb∈B

v∗(Pb≥)

Proposition 2.2 Le meilleur optimum pour le programme linéaire (Pb≥) correspond à la valeur

de la solution optimale du problème selon le scénario qui décrit le plus grand domaine réalisable.

Cette valeur s’obtient en résolvant le programme linéaire suivant :

(Pb≥)meiOpt

min cx

s.c. Ax ≥ b

Démonstration. Rappelons que le domaine réalisable Xb≥ pour tout scénario b ∈ B vé-

rifie Xb≥ ⊆ Xb

≥. Par conséquent, la relation v∗(Pb≥) ≥ v∗(Pb

≥) est vraie pour tout b ∈ B.

Il en résulte que la valeur du meilleur optimum s’obtient en résolvant le programme

linéaire (Pb≥).

2.2.2 Programmes linéaires avec contraintes d’égalité

Nous nous intéressons à présent aux programmes linéaires incertains dont les

contraintes sont des égalité. Notons tout d’abord que, pour le calcul du pire opti-

mum, la simple réécriture du problème en substituant les contraintes d’égalité par des

contraintes d’inégalité n’est pas satisfaisante. Illustrons cela par un exemple. Soit le


programme linéaire incertain (P6b) suivant :

(P6b)

min x1 + 2x2

s.c x1 + x2 = b1

x1 − x2 ≥ b2

x1, x2 ≥ 0

où les coefficients b1 et b2 sont incertains et appartiennent respectivement aux inter-

valles [4, 6] et [0, 4].

Le problème (P6b) peut s’écrire de manière équivalente en un programme linéaire où

toutes les contraintes sont des inégalités, comme suit :

(P6′b)

min x1 + 2x2

s.c. x1 + x2 ≥ b1

x1 + x2 ≤ b1

x1 − x2 ≥ b2

x1, x2 ≥ 0

(2.17)

(2.18)

(2.19)

Les valeurs du second membre dans les deux contraintes (2.17) et (2.18) dans le

problème (P6′b) sont dépendantes. Si nous appliquons les résultats de la section (2.2.1),

alors le pire optimum se calcule selon le scénario décrivant le plus petit domaine de

solutions réalisables, à savoir :

(P6′b)pirOpt

min x1 + 2x2

s.c. x1 + x2 ≥ 6

x1 + x2 ≤ 4

x1 − x2 ≥ 4

x1, x2 ≥ 0

(2.20)

(2.21)

(2.22)

Or, le problème (P6′b)pirOpt admet un domaine de solutions réalisables vide, et ceci

à cause des contraintes (2.20) et (2.21) qui ne varient pas dans le même sens. En fait,

cette transformation n’est pas possible, car elle contredit les hypothèses de départ

sur l’indépendance des coefficients incertains. Il apparaît alors que la substitution des

contraintes d’égalité par des contraintes d’inégalité n’est pas pertinente quand il s’agit


de calculer un pire optimum pour ce problème incertain.

Afin d’étudier la complexité des problèmes associés au calcul des valeurs du pire

optimum et du meilleur optimum pour (Pb=), nous distinguons deux cas :

– le cas où n = m et le rang de la matrice A est égal à n. Dans ce cas, le problème

(Pb=) admet une solution réalisable unique ;

– le cas où n > m avec le rang de la matrice A étant égal à m. Dans ce cas, le

domaine réalisable de (Pb=) est non borné. Nous supposons néanmoins que la

solution optimale est de valeur finie.

Examinons la valeur du pire optimum associé au problème (Pb=) selon ces deux

cas.


La valeur d’un pire optimum pour le problème (Pb=) s’obtient par la résolution du

problème suivant :

(Pb=)pirOpt

maxb∈B

v∗(Pb=)

Cas 1 : Existence d’une solution réalisable unique

Proposition 2.3 Dans le cas où n = m et Rg(A) = n, le problème (Pb=)pirOpt peut être résolu

en temps polynomial.

Démonstration. Pour tout b ∈ B, le domaine Xb= étant non vide et ne contenant qu’une

seule solution réalisable x = A−1b, il suffit de remarquer que le problème (Pb=)pirOpt

est équivalent au programme linéaire :

(Pb=)pirOpt

max cA−1b

s.c. A−1b ≥ 0

b ≤ b ≤ b

qui est un problème polynomial.

Cas 2 : Existence de solutions optimales finies

Afin d’étudier la complexité de (Pb=)pirOpt dans le cas où le rang de la matrice A est

égal à m avec m < n, nous allons procéder de la manière suivante. Tout d’abord, le

lemme 2.1 ci-dessous établit la complexité du problème (QX) dans le cas où X est


un domaine borné. Ensuite, le lemme 2.2 étend ce résultat au cas de domaine X′ non

borné. Enfin, le théorème 2.1 conclut sur la complexité du problème (Pb=)pirOpt.

Lemme 2.1 Le problème quadratique suivant est NP-difficile au sens fort :

(QX)

max cx

s.c. x ∈ X

c ≤ c ≤ c

(2.23)

où X ⊆ Rn est un polyèdre non vide et borné.

Démonstration. Soit le programme linéaire (Pc) où les coefficients de la fonction objectif

sont incertains et varient dans des intervalles :

(Pc)

max cu

s.c. ∆u ≤ β

où u est une matrice colonne de taille n représentant les variables, c est une matrice

ligne de taille n, ∆ est une matrice de taille m× n et b est une matrice colonne de taille

m. Pour tout j = 1 . . . n, le coefficient cj est incertain et appartient à l’intervalle [cj, cj].

Le domaine des solutions réalisables de (Pc) est supposé non vide et borné.

Soit u une solution réalisable du problème (Pc). La valeur du regret maximum associé

à cette solution, notée Rmax(u), est un problème NP-difficile (Théorème 1.1). Celui-ci

s’écrit :

Rmax(u) =

max c(v− u)

s.c. ∆v ≤ β

c ≤ c ≤ c

Posons x = v− u. Le problème devient :

Rmax(u) =

max cx

s.c. ∆x ≤ β− ∆u

c ≤ c ≤ c

Par ce changement de variables, nous avons construit à partir d’une instance du pro-

blème du regrêt maximum, une instance du problème (QX). En effet, définissons le


polyèdre X comme étant :

X = x ∈ Rn : ∆x ≤ β− ∆u (2.24)

Nous obtenons :

Rmax(u) =

max cx

s.c. x ∈ X

c ≤ c ≤ c

Par conséquent, le problème (QX) est de même complexité que le calcul de la valeur

Rmax(u), qui est NP-difficile au sens fort.

Dans le lemme 2.2, nous étendons ce résultat au problème (QX′), où le domaine de

solutions réalisables X′ est non borné.

Lemme 2.2 Le problème quadratique suivant est NP-difficile au sens fort :

(QX′)

max cx

s.c. x ∈ X′

c ≤ c ≤ c

avec X′ ⊆ Rn est un polyèdre non vide et non borné.

Démonstration. A partir d’une instance du problème (QX), où X ⊆ Rn−1 construisons

l’instance suivante du problème (QX′) :

(IX′)

maxn−1∑

j=1cjxj − cnxn

s.c. (x1, . . . xn−1) ∈ X

xn ≥ 0

cj ≤ cj ≤ cj j = 1 . . . n− 1

0 ≤ cn ≤ M

où M > 0 est une constante positive.

Remarquons que, dans cette instance (IX′), le polyèdre X′ = (x1, . . . xn−1) ∈ X, x′n ≥0 est non vide (car X est non vide) et non borné.

Par ailleurs, si on note (x∗1 , . . . , x∗n−1) la solution optimale de (QX) alors la solution

optimale de (QX′) sera égale à (x∗1 , . . . , x∗n−1, 0). Par conséquent, le problème (QX′) est

au moins aussi difficile que le problème (QX).


En utilisant les deux lemmes précédents, le théorème (2.1) donne la complexité du

problème (Pb=)pirOpt dans le cas général.

Théorème 2.1 Dans le cas où n > m et Rg(A) = m le calcul du pire optimum pour le

problème (Pb=) est un problème NP-difficile.

Démonstration. Le problème (Pb=)pirOpt s’écrit :

(Pb=)pirOpt

maxb∈B

v∗(Pb=)

Selon le théorème fort de la dualité, on peut réécrire le problème (Pb=)pirOpt comme

suit : maxb∈B

maxAty≤ct

bty

Ce dernier est équivalent au problème quadratique suivant :

(Q)

max bty

s.c. Aty ≤ ct

b ≤ b ≤ b

Dans les deux cas de figure où le domaine des solutions réalisables du problème

(Q) est borné ou non borné, nous déduisons des lemmes 2.1 et 2.2 que le problème

(Pb=)pirOpt est NP-difficile.


La valeur du meilleur optimum pour le problème (Pb=) se calcule en résolvant le pro-

blème :

(Pb=)meiOpt

minb∈B

v∗(Pb=)

Proposition 2.4 Le problème (Pb=)meiOpt est polynomial.

En effet, la valeur du meilleur optimum est la valeur de la solution optimale du pro-

gramme linéaire :

(Pb=)meiOpt

min cx

s.c. Ax− b = 0

b ≤ b ≤ b

x ≥ 0

La preuve étant équivalente à celle de la recherche du meilleur optimum d’un pro-


blème contenant des contraintes d’inégalité (voir la proposition (2.2)).

2.2.3 Programmes linéaires quelconques

Dans cette section, nous aborderons le calcul du pire optimum ainsi que celui du

meilleur optimum pour le cas général de programmes linéaires quelconques (admet-

tant des contraintes d’inégalité et d’égalité), dont le second membre des contraintes

est incertain.

Considérons les programmes linéaires suivants :

(Pb,b′)

min cx

s.c. Ax = b

A′x ≥ b′

où x une est matrice colonne des variables de taille n, c est une matrice ligne de Rn,

A et A′ sont des matrices respectivement de taille m1 × n et m2 × n, et b et b′ sont des

matrices colonnes de taille respectivement m1 et m2.

Supposons que pour toute contrainte i, i = 1 . . . m1 + m2 les coefficients bi (resp. b′i)

varient dans l’intervalle [bi, bi] (resp. [b′i, b′i]), avec bi ≤ bi (resp. b′i ≤ b

′i). Notons le

produit cartésien des intervalles [bi, bi] pour i = 1 . . . m1 (respectivement [b′i, b′i]) par B

(respectivement B′ pour i = m1 + 1 . . . m1 + m2).

Pour les vecteurs b et b′ fixés dans B et B′ respectivement, notons Xb,b′ le polyèdre des

solutions réalisables défini par :

Xb,b′ = x ∈ Rn : Ax = b, A′x ≥ b′ (2.25)

que nous supposons non vide. Enfin, nous supposons de plus que le problème (Pb,b′)

admet un optimum fini pour tout couple (b, b′) incertain, sa valeur est notée v∗(Pb,b′).



Le calcul du pire optimum s’écrit de la manière suivante :

(Pb,b′)pirOpt

max

b∈B, b′∈B′v∗(Pb,b′)

Pour les deux cas de figure présentés dans la section 2.2.2, étudions la complexité du

problème (Pb,b′)pirOpt.

Existence d’une solution réalisable unique

Proposition 2.5 Dans le cas où n = m1 et Rg(A) = n, le problème (Pb,b′)pirOpt est polyno-

mial.

Démonstration. Dans ce cas, le problème (Pb,b′)pirOpt est équivalent au programme li-

néaire suivant : max cA−1b

s.c. A′A−1b ≥ b′

b ≤ b ≤ b

Existence d’une solution optimale finie

Proposition 2.6 Dans le cas où n > m1 et Rg(A) = m1, le problème (Pb,b′)pirOpt est NP-

difficile au sens fort.

Démonstration. Il suffit de remarquer que dans le cas particulier où m2 = 0, le pro-

blème (Pb,b′)pirOpt revient à résoudre (Pb=)pirOpt qui est NP-difficile au sens fort (voir le

théorème (2.1)).


Le problème du calcul de la meilleure solution optimale se formule comme suit :

(Pb,b′)pirOpt

min

b∈B, b′∈B′v∗(Pb,b′)

Proposition 2.7 Le problème (Pb,b′)meiOpt peut être résolu en un temps polynomial.

Démonstration. Le problème (Pb,b′)meiOpt se ramène au programme linéaire :


(Pb,b′)meiOpt

min cx

s.c. Ax− b = 0

A′x ≥ b′

b ≤ b ≤ b

2.3 Robustesse et dualité

Après avoir étudié la résolution des programmes linéaires dans lesquels l’incertitude

porte sur le second membre des contraintes, nous revenons sur la réflexion initiée

par les travaux de Minoux (2007a; 2009b) concernant l’emploi de la dualité pour

traiter le problème incertain (Pb), avec une approche pire cas. Nous avons montré

dans le chapitre précédent (voir la section 1.3) que le problème qui consiste à dé-

terminer des solutions robustes de pire cas au problème (Pb) d’une part, et à son

problème dual d’autre part, n’étaient pas équivalents. Nous proposons dans ce qui

suit une alternative dans laquelle nous définirons un autre critère, nommé critère du

meilleur cas. Ce critère va nous servir à déterminer la relation existant entre une version

robuste de pire cas de (Pb) et la version équivalente associée au problème dual de (Pb).

Définissons tout d’abord ce critère, en étudiant le résultat de son application sur

les programmes linéaires incertains (Pb≥) (où les contraintes sont des inégalités). Nous

donnerons, à titre indicatif, le résultat de l’application de ce même critère sur (Pb=).

2.3.1 Critère du meilleur cas

Une solution selon le critère du meilleur cas correspond à la solution optimale selon

le scénario le plus favorable. Nous emploierons ensuite ce critère pour déterminer les

relations de dualité pour traiter le problème incertain (Pb).

Programmes linéaires avec contraintes d’inégalité

Soit le problème (Pb≥). La solution obtenue selon le critère du meilleur cas est définie

comme étant la solution possédant la plus petite évaluation sur tous les scénarios. Le

2.3. Robustesse et dualité 67

problème, noté (Pb≥)meiCas, s’écrit :

(Pb≥)meiCas

minx∈X≥

minb∈B

v≥(b, x)

Étant donné que pour toute solution réalisable x dans X≥, la meilleure évaluation de

x sur tous les scénarios est constante et est égale à :

minb∈B

v≥(b, x) = cx (2.26)

Il s’en suit que la solution de (Pb≥)meiCas est la solution optimale du programme linéaire

défini par le scénario décrivant le plus grand domaine de solutions réalisables :

(Pb≥)meiCas

min cx

s.c. Ax ≥ b

Exemple 2.3 La solution suivant le critère du meilleur cas appliqué sur le problème (P4b) de

l’exemple 2.1, est xmeiCas = (4/5, 22/5) (voir figure (2.3)). Sa valeur est égale à = −18, et le

scénario correspondant est b1 = 6 et b2 = 8.

2 4 6

2

4

6b 1 = 6

b 1 = 1 0b 2 = 8

x m e i C a sb 2 = 4

Fig. 2.3 – Solution optimale suivant le critère du meilleur cas pour (P4b)


Programmes linéaires avec contraintes d’égalité

La solution optimale selon le critère du meilleur cas appliqué au problème (Pb=) est la

solution du problème, noté (Pb=)meiCas, suivant :

(Pb=)meiCas

minx∈X=

minb∈B

v=(b, x)

La meilleure évaluation d’une solution x ∈ X= étant égale à cx, le problème (Pb=)meiCas

est équivalent au programme :

(Pb=)meiCas

min cx

s.c. Ax− b = 0

b ≤ b ≤ b

x ≥ 0

Remarque 2.3 Le calcul de la solution selon le critère du meilleur cas associé au problème

(Pb) (de formulation générale quelconque) est un problème polynomial. Il revient à calculer le

meilleur optimum pour ce même programme.

2.3.2 Dualité

Nous avons vu que que la solution de pire cas du problème primal (Pb≥) ne correspond

pas à la solution de pire cas du problème dual. Nous allons montrer que cette dernière

correspond plutôt à la solution de meilleur cas. Pour ce faire, comparons le problème

dual de (Pb≥)meiCas obtenu ci-dessus avec le problème dual de la version de pire cas.

Soit (F) le problème dual de (Pb≥)meiCas, qui s’écrit :

(F)

max bty

s.c. Aty = ct

y ≥ 0

D’après le théorème fort de la dualité, nous avons :

v∗((Pb≥)meiCas) = v∗(F) (2.27)

où v∗((Pb≥)meiCas) (respectivement v∗(F)) représente la valeur de la solution optimale


du problème (Pb≥)meiCas (respectivement (F)).

Considérons à présent le problème, noté (Db), dual du problème (Pb≥). Il s’écrit :

(Db)

max bty

s.c. Aty = ct

y ≥ 0

Notons que l’incertitude concerne les coefficients de la fonction objectif de (Db).

Nous avons montré à la section 1.1.1 que calculer la solution robuste suivant le critère

du pire cas sur le problème (Db) est équivalent au programme linéaire où les coef-

ficients de la fonction objectif correspondent aux valeurs b (puisque le problème est

un problème de maximisation et que les variables sont non négatives). Le problème

(Db)pirCas s’écrit donc :

(Db)pirCas

max bty

s.c. Aty = ct

y ≥ 0

Or, ce dernier coïncide avec le problème (F). Nous déduisons alors que :

v∗((Pb≥)meiCas) = v∗((Db)pirCas) (2.28)

D’où la proposition suivante :

Proposition 2.8 Quand le second membre des contraintes est incertain, l’application du critère

du meilleur cas sur le problème primal revient à appliquer le critère du pire cas sur le problème

dual, et réciproquement.

En robustesse, appliquer un critère sur un problème primal ne revient donc pas

à appliquer ce même critère sur le problème dual, mais plutôt à appliquer le cri-

tère “dual”. Cette relation reste valable quand il s’agit de calculer la valeur d’un

pire optimum ou d’un meilleur optimum. Très récemment, quelques extensions ont

été réalisées dans le cadre de l’utilisation de la dualité en robustesse. Citons à titre

d’exemple, les travaux de Beck et Ben-Tal (2009) qui étendent ces résultats aux pro-

blèmes admettant des coefficients incertains situés dans la matrice des contraintes, ou

encore les travaux de Gabrel et Murat (2010) qui, en définissant des extensions des


critères du pire cas et du meilleur cas, généralisent le résultat de la proposition 2.8.

La proposition (2.8) nous permet aussi de déterminer la complexité du problème

du calcul du meilleur optimum d’un programme linéaire où les coefficients de la

fonction objectif sont incertains.

Théorème 2.2 Soit le problème incertain suivant :

(Pc)

min cx

s.c. Ax ≥ b

où c est une matrice ligne de Rn, x est une matrice colonne de taille n, A est une matrice de

Rm×Rn et b une matrice colonne de Rm. Les coefficients de la fonction objectif sont incertains

et appartiennent, pour tout j = 1 . . . n, à un intervalle [cj, cj].

Le calcul du meilleur optimum associé au programme linéaire (Pc) est un problème NP-

difficile.

Démonstration. Afin de prouver le théorème (2.2), il suffit de construire le dual du

problème (Pc), noté (Dc=), et qui s’écrit :

(Dc=)

max bty

s.c. Aty = c

y ≥ 0

D’après le résultat de la section (2.2.2), le calcul de pire optimum associé au pro-

blème (Dc=), qui admet des contraintes d’égalité et un second membre incertain, est

un problème NP-difficile (hormis, dans le cas spécial d’existence d’une solution réa-

lisable unique, où ce problème est polynomial). Par conséquent, le calcul du meilleur

optimum associé au problème (Pc) est lui aussi un problème NP-difficile, les deux

problèmes étant équivalents d’après la proposition (2.8).

De manière générale, tout programme linéaire dont le second membre des

contraintes serait incertain et contenant des contraintes d’inégalité verra les variables

correspondantes dans le problème dual, restreintes en signe. Dans ce cas, les deux

problèmes (primal et dual) sont polynômiaux. Par contre, quand les contraintes dans


le primal sont des égalités, les variables correspondantes dans le problème dual sont

quelconques, et la recherche du pire optimum pour le primal et du meilleur optimum

pour son dual sont des problèmes NP-difficiles.

Conclusion

Dans ce chapitre, nous nous sommes intéressés aux programmes linéaires dans les-

quels les coefficients du second membre des contraintes sont incertains. Nous avons

considéré deux contextes décisionnels distincts, pour lesquels nous nous sommes

attachés à apporter au décideur des réponses adéquates et une information utile et

pertinente, pour réagir au mieux face aux aléas.

Dans le premier contexte, nous avons supposé qu’une décision doit être prise avant

toute réalisation de l’incertain. Les solutions recherchées doivent être réalisables quelle

que soit la réalisation de l’aléa, y compris dans le pire cas.

Le second contexte regroupe des problèmes pour lesquels aucune décision ne doit

être prise avant la réalisation de l’incertain. Nous nous sommes alors intéressés aux

valeurs du pire optimum et du meilleur optimum. Ces valeurs fournissent au déciceur

l’intervalle de variation de l’optimum, une indication intéressante dans une phase de

planification.

Par ailleurs, nous avons montré la nécessité de distinguer les approches en fonction

de la nature des contraintes. En effet, cette étude a montré que les problèmes contenant

exclusivement des contraintes d’inégalité sont des problèmes faciles, pour les deux

contextes de décision. En revanche, quand le problème admet des contraintes d’éga-

lité, se plaçant dans le premier contexte, il est impossible de déterminer une solution

réalisable pour tout scénario qui se présente. Le décideur est contraint de choisir une

solution puis de mesurer la violation des contraintes. Néanmoins, quand celui-ci sait

mesurer la non satisfaction des contraintes, il peut envisager de suivre un modèle de

pénalités permettant de prendre la décision la moins pénalisante. Enfin, concernant le

second contexte décisionnel, nous avons établi que le calcul du pire optimum est un

problème NP-difficile quand celui-ci contenait les contraintes d’égalité.


Dans ce qui a été traité jusqu’à présent, nous avons admis que tous les coefficients

incertains pouvaient atteindre leur pire valeur simultanément. Or, ce scénario extrême

de pire cas est peu vraisemblable dans la réalité. Quand cela est envisageable par le

décideur, nous voulons exhiber un autre scénario, moins conservateur que le scénario

de pire cas. Inspirée de l’approche de Bertsimas et Sim (2004) (présentée à la section

1.2.3), nous proposons dans le prochain chapitre, une extension de cette approche

pour le calcul du pire optimum, nommé pire optimum paramétrique. Il s’agit dans cette

approche de fournir au décideur la valeur de l’optimum pour un scénario dans lequel

tous les coefficients ne sont pas à leur pire valeur. Dans la suite de ce travail, se

positionnant dans le second contexte décisionnel, nous nous attachons à raffiner le

calcul du pire optimum de (Pb) et cela en introduisant une paramétrisation appropriée.

3Calcul du pire optimum

paramétrique

Sommaire

Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75

3.1 Programmes linéaires avec contraintes d’inégalité . . . . . . . . . . 76

3.1.1 Définition du pire optimum paramétrique . . . . . . . . . . . . . . . . . 76

3.1.2 Reformulation en programme linéaire mixte . . . . . . . . . . . . . . . . 79

3.2 Programmes linéaires avec contraintes d’égalité . . . . . . . . . . . . 83

3.2.1 Identification du pire optimum paramétrique . . . . . . . . . . . . . . . 83

3.2.2 Reformulation en programme linéaire mixte . . . . . . . . . . . . . . . . 85

Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86

Dans ce chapitre, nous présentons une extension de l’approche paramétrique ro-

buste de Bertsimas et Sim (2004) au calcul de la valeur du pire optimum d’un

programme linéaire comprenant un second membre des contraintes incertain. En re-

prenant le modèle d’incertitude proposé par ces auteurs, nous introduisons un para-

mètre qui contrôlera la déviation totale des valeurs nominales de tous les coefficients

incertains. Nous étudierons le problème résultant et nous proposerons une formulation

par programmation linéaire mixte.

73

75

Introduction

Dans ce chapitre nous nous plaçons dans le contexte décisionnel introduit au chapitre

précédent, dans lequel nous supposons que le décideur aura connaissance des incerti-

tudes au moment de prendre sa décision et souhaite, dans une phase de planification,

évaluer les coûts des solutions optimales selon les scénarios pouvant se réaliser.

Nous nous intéressons plus précisément à l’évaluation de l’optimum selon des

scénarios différents du scénario extrême de pire cas, jugé parfois trop conservateur

et peu réaliste. Nous supposons ici que le décideur accepte une part de risque en ne

considérant pas la totalité des scénarios pouvant se réaliser mais seulement une partie

d’entre eux.

Nous proposons alors une extension de l’approche de Bertsimas et Sim (2004) (voir

section 1.2.3) au calcul du pire optimum, qu’on nommera pire optimum paramétrique.

Modélisant les incertitudes par des intervalles dont la valeur médiane est la valeur

nominale, il s’agit dans cette approche de déterminer la valeur de l’optimum em-

ployant un modèle d’incertitude en colonne en non pas en ligne comme cela a été étudié

dans l’approche de Bertsimas et Sim (2004) (voir la section 1.3 du premier chapitre).

Nous considérons pour ce faire un budget d’incertitude unique et commun à tous les

coefficients du second membre des contraintes qui représente la déviation totale des

coefficients incertains de leurs valeurs nominales.

Ce chapitre est séparé en deux parties : nous traiterons dans la première partie

les problèmes dont les contraintes sont exclusivement des inégalités. Puis, dans la

seconde partie, nous aborderons les problèmes contenant des contraintes d’égalité.

Nous montrerons que dans les deux cas, le calcul du pire optimum paramétrique

n’est pas un problème facile et nous proposerons une reformulation du problème en

programme linéaire mixte.

76 Chapitre 3. Calcul du pire optimum paramétrique

3.1 Programmes linéaires avec contraintes d’inégalité

3.1.1 Définition du pire optimum paramétrique

Rappelons que le programme linéaire incertain (Pb≥) s’écrit (voir le problème (2.1) au

chapitre 2) :

(Pb≥)

min cx

s.c. Ax ≥ b

Nous considérons que tout coefficient incertain bi, i = 1 . . . m appartient à l’inter-

valle [bi − bi, bi + bi] où bi représente la valeur nominale et bi une déviation positive.

Notons U le produit cartésien des intervalles [bi − bi, bi + bi], i = 1 . . . m et supposons

que pour tout b ∈ U le problème (Pb≥) est réalisable et la valeur de l’optimum, notée

v∗(Pb≥), est finie.

Comme nous l’avons vu au chapitre précédent, le calcul d’un pire optimum pour

le problème (Pb≥) est un problème polynomial. Il s’obtient par la résolution du pro-

gramme linéaire selon le scénario qui décrit le plus petit domaine réalisable. Cepen-

dant, ce scénario extrême peut paraître trop conservateur et peu représentatif de ce

qui pourrait réellement se réaliser. Le décideur aimerait connaître la valeur de l’opti-

mum selon un autre scénario, moins conservateur que le scénario de pire cas. Nous

proposons alors une extension de l’approche de Bertsimas et Sim (2004) au calcul du

pire optimum qui suppose que tous les paramètres incertains n’atteignent pas simul-

tanément leur pire valeur. Pour ce faire, nous introduisons le budget d’incertitude Γ

représentant la déviation totale sur toutes les contraintes des paramètres incertains par

rapport aux valeurs nominales. Le modèle d’incertitude employé, noté U (Γ), est un

modèle en colonne et le calcul du pire optimum paramétrique s’obtient par la résolu-

tion du problème, noté Pb≥(Γ), suivant :

Pb≥(Γ)

max

b∈U (Γ)minAx≥b

cx

où

U (Γ) = b ∈ Rm : bi = bi + zi bi, zi ∈ Z(Γ) (3.1)

3.1. Programmes linéaires avec contraintes d’inégalité 77

et

Z(Γ) = z ∈ Rm :m

∑i=1|zi| ≤ Γ, |zi| ≤ 1 (3.2)

Étant donné que le problème (Pb≥) comprend m contraintes, le paramètre Γ appartient

à l’intervalle [0, m]. Quand Γ vaut l’une des deux valeurs extrêmes 0 ou m, le problème

correspond respectivement au problème nominal et au problème du pire optimum.

Simplifions le problème Pb≥(Γ) en remarquant tout d’abord que les valeurs absolues

peuvent être supprimées du modèle d’incertitude (??). En effet, étant donné le sens des

contraintes d’inégalité, les valeurs du second membre qui ont un impact défavorable

sur le domaine réalisable sont supérieures ou égales aux valeurs nominales. Il s’en

suit qu’à l’optimum, les variables zi, i = 1, . . . , m sont nécessairement non négatives et

appartiennent donc à [0, 1].

Par ailleurs, en rappelant que le problème Pb≥(Γ) possède une solution finie pour tout

vecteur b ∈ U (Γ), il est possible, en utilisant le théorème fort de la dualité, de l’écrire

de la manière suivante :

Q(Γ)

max

m∑

i=1zi ≤ Γ

zi ∈ [0, 1] i = 1 . . . m

maxm∑

i=1aijyi = cj j = 1 . . . n

yi ≥ 0 i = 1 . . . m

m∑

i=1biyi +

m∑

i=1biyizi

qui revient au problème de maximisation suivant :

Q(Γ)

maxm∑

i=1biyi +

m∑

i=1biyizi

s.c.m∑

i=1aijyi = cj j = 1 . . . n

m∑

i=1zi ≤ Γ

0 ≤ zi ≤ 1 i = 1 . . . m

yi ≥ 0 i = 1 . . . m

où les variables y sont les variables du problème dual de (Pb≥).

Nous constatons que le calcul du pire optimum paramétrique Q(Γ) est un pro-

blème quadratique. Plus précisément, il s’identifie comme étant un problème bilinéaire


avec des contraintes linéaires. En effet, la fonction objectif est de forme quadratique

et se décrit sur deux groupes disjoints de variables (les variables y d’une part, et les

variables z d’autre part). Le problème est linéaire pour chacun des deux groupes de

variables quand l’autre est fixé. Ce problème a été prouvé NP-difficile (voir Floudas et

Parlados (1995) et Vavasis (1991)).

Par conséquent, le calcul du pire optimum paramétrique, où un budget d’incer-

titude unique et en colonne lie les coefficients du second membre est un problème

difficile (ce qui diffère du modèle d’incertitude d’origine de Bertismas et Sim qui est

en ligne et qui garde la complexité polynomial du programme linéaire incertain dans

sa version robuste).

Le problème Q(Γ) peut être résolu de façon exacte soit à l’aide de méthodes de

résolution exactes de problèmes bilinéaires, soit par la résolution d’une reformulation

en programme linéaire mixte. Intéressons nous, tout d’abord, à la résolution directe

du problème Q(Γ). Les premiers travaux de résolution exacte de problèmes bilinéaires

sont de Falk (1973) et Konno (1976) qui ont proposé un algorithme de coupe. Les

travaux de Sherali et Shetty (1980) apportent des améliorations à ces méthodes. Plus

récemment, Meyer (1997), Meyer et Jaumard (1998), Meyer (2000) proposent d’autres

développements pour ces mêmes méthodes. Bloemhof-Ruwaard et Hendrix (1996)

quant à eux s’intéressent à une application à un système de production.

Afin de résoudre le problème bilinéaire Q(Γ) nous avons adapté et implémenté

l’algorithme de minimisation concave donné par Gallo et Ülkücü (1977). Brièvement,

l’idée générale de cet algorithme est de plonger dans un cône l’un des deux domaines

de solutions réalisables (celui associé aux variables y ou celui associé aux variables z ;

nous avons choisi ce dernier), puis de réaliser des subdivisions successives sur ce cône

et de tester si la solution optimale s’y trouve. Ce processus est réitéré jusqu’à ce que

tout le domaine soit parcouru, déterminant ainsi la solution optimale. Nous n’allons

pas présenter en détails ce travail dans ce manuscrit pour les raisons suivantes :

– en dépit de l’existence d’une preuve de convergence de cet algorithme (voir Flou-

das et Parlados (1995), Meyer et Jaumard (1998)) nous avons été confronté au

cyclage dans la majorité des instances traitées. Nous n’avons, pour le moment,

pu trouver une autre alternative que de garder en mémoire toutes les solutions

visitées et de comparer à chaque itération la nouvelle solution avec toutes les


précédentes. Bien sûr, cette manière de faire consomme du temps et de l’espace

mémoire, et est peu satisfaisante.

– même pour les instances pour lesquelles l’algorithme ne rencontre pas de cy-

clage, les instances pouvant être résolues sont relativement de petite taille (ne

dépassant pas une dizaine de variables), alors que notre intérêt porte sur la réso-

lution d’instances de taille plus importante.

Nous n’avons donc pas poursuivi notre étude dans ce sens, ouvrant ainsi des perspec-

tives d’un travail futur dans le sujet.

Nous nous sommes alors tournés vers une autre alternative pour résoudre le pro-

blème Q(Γ) qui consiste en une reformulation en programme linéaire mixte. Cela sera

développé dans la section suivante.

3.1.2 Reformulation en programme linéaire mixte

Rappelons que dans la formulation du problème Pb≥(Γ), le paramètre Γ est un réel

appartenant à l’intervalle [0, m]. Cependant, il s’avère qu’en se restreignant aux va-

leurs entières dans [0, m], il est possible de linéariser le problème bilinéaire Q(Γ) en

un programme linéaire mixte, comme le montre la proposition 3.1.

Proposition 3.1 Si la valeur du paramètre Γ est entière alors il existe une solution optimale

(y∗, z∗) de Q(Γ) telle que z∗i ∈ 0, 1, i = 1, . . . , m.

Démonstration. Définissons les deux polyèdres suivants :

Y = y ∈ Rm :m

∑i=1

aijyi = cj, j = 1 . . . n, y ≥ 0 (3.3)

et

Z ′(Γ) = z ∈ Rm :m

∑i=1

zi ≤ Γ, 0 ≤ zi ≤ 1, i = 1 . . . m (3.4)

Le problème Q(Γ) étant un problème bilinéaire alors s’il existe une solution optimale

finie pour le problème (ce qui est assuré ici, par hypothèse), alors il existe au moins

une solution optimale (y∗, z∗) telle que y∗ est un point extrême de Y et z∗ un point


extrême de Z ′(Γ) (voir Horst et Tuy (1996)). Ceci implique que si Γ est entier alors les

variables z∗ sont 0− 1.

D’après la proposition 3.1, il est clair que si Γ ∈N (Γ ≤ m), alors à l’optimum tout

coefficient du second membre bi, i = 1 . . . m, sera égal soit à la valeur nominale bi, soit

à la plus grande valeur bi + bi. Spécifiquement, Γ représente le nombre de coefficients

du second membre qui sont égaux à bi + bi.

Dans de nombreuses applications, cette contrainte d’intégrité n’est pas gênante.

Considérons l’exemple d’un problème de gestion de stocks sur un horizon temporel T

où il s’agit de définir les quantités à acheter et à stocker à chaque période t = 1 . . . T,

avec une demande à satisfaire qui serait incertaine. Il est naturel pour le décideur

d’attribuer une valeur entière à Γ, puisqu’elle représente ici le nombre de périodes où

les demandes dévient des valeurs nominales et sont égales aux pires valeurs.

Nous pouvons à présent linéariser le problème Q(Γ). En effet, étant donné que les

variables z sont binaires et apparaissent dans les produits yizi, i = 1 . . . m, de la fonction

objectif, alors suivant les techniques de linéarisation de Glover et Woolsey (1974) et

Glover (1975), chaque produit yizi peut être remplacé par une nouvelle variable ωi

telle que :

ωi =

yi si zi = 1

0 sinon(3.5)

Ajoutant les contraintes nécessaires pour garantir l’égalité (3.5), le problème Q(Γ) se

linéarise et devient le programme linéaire mixte, noté Q′(Γ), suivant :

Q′(Γ)

maxm∑

i=1biyi +

m∑

i=1biωi

s.c.m∑

i=1aijyi = cj j = 1 . . . n

m∑

i=1zi ≤ Γ

ωi ≤ yi i = 1 . . . m

ωi ≤ Mzi i = 1 . . . m

zi ∈ 0, 1 i = 1 . . . m

yi, ωi ≥ 0 i = 1 . . . m


où M est une constante positive très grande.

Remarque 3.1 Dans le cas où Γ = m, le problème Q′(m) se simplifie en un programme

linéaire. En effet, on remarque qu’à l’optimum, toutes les variables z∗i = 1 et donc que bi =

bi + bi, i = 1 . . . m. Ceci rejoint le résultat du chapitre précédent (voir la section 2.2.1) du

calcul d’un pire optimum pour (Pb≥), qui est un problème polynomial.

En prenant un Γ entier nous passons d’un problème bilinéaire à un programme

linéaire mixte. Ce dernier, même s’il reste difficile dans le cas général, peut être résolu

de manière rapide à l’aide de solvers performants. L’efficacité des algorithmes utilisés

dépend de la valeur de M.

Afin de réduire le saut d’intégrité et d’accélérer la vitesse de résolution du pro-

blème, la constante M doit être la plus petite possible. Nous devons alors définir

des bornes pour les variables y. La formulation du problème Q′(Γ) présentée ici

est une formulation générique et les bornes que nous allons présenter le sont aussi.

Cependant, il est préférable de déterminer des bornes spécifiques à chaque type de

problème (ainsi, nous donnerons au chapitre 4 une borne spécifique pour le problème

de transport). Dans le cas général, nous pouvons poser les deux bornes suivantes (va-

lables uniquement si les valeurs de tous les coefficients bi, i = 1 . . . m sont strictement

positives).

Bornes pour M

Nous proposons de calculer deux bornes pour les variables y.

La première s’obtient comme suit : étant donné que les variables z sont des variables

binaires, alors pour toute solution réalisable (y, z, ω) du problème Q′(Γ) l’inégalité

suivante est vérifiée :

m

∑i=1

biyi +m

∑i=1

biyizi ≤m

∑i=1

biyi +m

∑i=1

biyi (3.6)

Par ailleurs, nous remarquons que la solution (y, 1l, ω) est réalisable pour Q′(m). Nous

avons donc :

m

∑i=1

biyi +m

∑i=1

biyi ≤m

∑i=1

biy∗i +m

∑i=1

biy∗i ≡ v∗(Q′(m)) (3.7)


où (y∗, 1l, ω∗) est la solution optimale du problème Q′(m) et v∗(Q′(m)) sa valeur à

l’optimum.

De (3.6) et (3.7) nous déduisons que :

m

∑i=1

(bi + bi)yi ≤ v∗(Q′(m)) (3.8)

Par conséquent, si les valeurs de bi + bi sont strictement positives pour tout i = 1 . . . m,

alors, nous déduisons de (3.8) que pour tout i = 1 . . . m les variables yi sont bornées

par les valeurs :

v∗(Q′(m))(bi + bi)

(3.9)

Examinons maintenant la seconde borne.

Pour toute solution réalisable (y, z, ω) de Q′(Γ), nous avons :

m

∑i=1

biyi +m

∑i=1

biyizi ≤ v∗(Q′(Γ)) (3.10)

où v∗(Q′(Γ)) représente la valeur de la solution optimale de Q′(Γ).

Par ailleurs, étant donné que les valeurs bi, yi, zi sont toutes non négatives pour i =

1, . . . , m, alors nous avons :

m

∑i=1

biyi ≤m

∑i=1

biyi +m

∑i=1

biyizi (3.11)

Nous déduisons de (3.10) et (3.11) que :

m

∑i=1

biyi ≤ v∗(Q′(Γ)) (3.12)

De plus, il est clair que v∗(Q′(Γ)) ≤ v∗(Q′(Γ + k)) pour tout k entier dans [1, m− Γ]

(la valeur de v∗(Q′(Γ)) est non décroissante quand la valeur de Γ augmente). Par

3.2. Programmes linéaires avec contraintes d’égalité 83

conséquent nous avons :

m

∑i=1

biyi ≤ v∗(Q′(Γ + k)) (3.13)

Si bi > 0 pour tout i = 1 . . . m, alors nous déduisons de (3.13) la borne suivante pour

les variables yi :

v∗(Q′(Γ + k))bi

(3.14)

Cette borne est la plus serrée quand k vaut 1.

Remarque 3.2 Ces deux bornes ne sont valables que si bi > 0 pour tout i = 1 . . . m, une

condition assez restrictive en général.

Nous passons à présent aux programmes linéaires admettant des contraintes

d’égalité exclusivement, pour lesquels nous allons proposer un moyen d’identifier le

scénario et de calculer la valeur du pire optimum paramétrique.

3.2 Programmes linéaires avec contraintes d’égalité

3.2.1 Identification du pire optimum paramétrique

Rappelons l’écriture du problème (Pb=) qui est un programme linéaire admettant des

contraintes d’égalité et dont le second membre des contraintes est incertain :

(Pb=)

min cx

s.c. Ax = b

x ≥ 0

Supposons que tout coefficient bi, pour i = 1 . . . m, appartient à l’intervalle

[bi − bi, bi + bi].

Selon la même approche, le calcul de la valeur du pire optimum paramétrique


s’obtient en résolvant le problème d’optimisation suivant :

Pb=(Γ)

max

b∈U (Γ)min

Ax=b, x≥0cx

où U (Γ) est défini par (3.1) et (3.2).

Puisque les contraintes de (Pb=) sont des égalités, le sens de déviation des seconds

membres qui détériore la valeur de l’optimum n’est pas connu a priori. La suppres-

sion des valeurs absolues n’est donc pas immédiate (comme cela fut le cas pour les

contraintes d’inégalité).

Afin de contourner cette difficulté, nous choisissons de remplacer les variables zi

pour tout i = 1 . . . m, par l’introduction de deux variables binaires z+i et z−i qui repré-

sentent un sens de déviation de la ieme contrainte. Selon cette formulation, le budget

d’incertitude Γ est un entier dans [0, m]. Le domaine d’incertitude est alors le suivant :

U ′(Γ) = b ∈ Rm : bi = bi + biz+i − biz−i ; z+

i , z−i ∈ Z′′(Γ) (3.15)

et

Z ′′(Γ) = z ∈ R2m :m

∑i=1

(z+i + z−i ) ≤ Γ; z+

i + z−i ≤ 1; z+i , z−i ∈ 0, 1 (3.16)

La valeur du pire optimum paramétrique s’obtient alors en résolvant le problème d’op-

timisation suivant :

Pb=(Γ)

max

m∑

i=1(z+

i + z−i ) ≤ Γ

z+i + z−i ≤ 1 i = 1 . . . m

z+i , z−i ∈ 0, 1 i = 1 . . . m

minn∑

j=1aijxj = bi + biz+

i − biz−i i = 1 . . . m

xj ≥ 0 j = 1 . . . n

n∑

j=1cjxj

En employant le théorème fort de dualité, nous retrouvons le problème de maximisa-


tion suivant :

W(Γ)

maxm∑

i=1biyi +

m∑

i=1biyiz+

i −m∑

i=1biyiz−i

s.c.m∑

i=1aijyi ≤ cj j = 1 . . . n

m∑

i=1(z+

i + z−i ) ≤ Γ

z+i + z−i ≤ 1 i = 1 . . . m

z+i , z−i ∈ 0, 1 i = 1 . . . m

où les variables y sont les variables du problème dual du problème de minimisation

dans (Pb=).

Nous proposons dans ce qui suit une formulation de W(Γ) en programme linéaire

mixte.

3.2.2 Reformulation en programme linéaire mixte

Dans le problème W(Γ), les termes quadratiques apparaissant dans la fonction ob-

jectif sont formés d’une variable binaire et d’une variable continue (non restreinte en

signe). Selon Glover (1975) et Torres (1990), il est possible de linéariser le problème en

effectuant le changement de variables suivant :

– pour i = 1 . . . m, tout produit yiz+i est remplacé par la variable ω+

i telle que :

ω+i =

yi si z+

i = 1

0 sinon(3.17)

– de la même manière, pour tout i = 1 . . . m, le produit yiz−i est remplacé par la

variable ω−i telle que :

ω−i =

yi si z−i = 1

0 sinon(3.18)

Ce changement de variables est accompagné par les contraintes suivantes :


– pour tout i = 1 . . . m nous avons :

Lz+i ≤ ω+

i ≤ Uz+i

yi −U(1− z+i ) ≤ ω+

i ≤ yi − L(1− z+i )

(3.19)

– pour tout i = 1 . . . m nous avons :

Lz−i ≤ ω−i ≤ Uz−iyi −U(1− z−i ) ≤ ω−i ≤ yi − L(1− z−i )

(3.20)

où L et U avec L ≤ U représentent des bornes inférieure et supérieure pour les

variables y qui sont à définir.

Le problème quadratique W(Γ) devient alors le programme linéaire mixte W ′(Γ)

suivant :

W ′(Γ)

maxm∑

i=1biyi +

m∑

i=1biω

+i −

m∑

i=1biω

−i

s.c.m∑

i=1aijyi ≤ cj j = 1 . . . n

m∑

i=1(z+

i + z−i ) ≤ Γ

z+i + z−i ≤ 1 i = 1 . . . m

Lz+i ≤ ω+

i ≤ Uz+i i = 1 . . . m

yi −U(1− z+i ) ≤ ω+

i ≤ yi − L(1− z+i ) i = 1 . . . m

Lz−i ≤ ω−i ≤ Uz−i i = 1 . . . m

yi −U(1− z−i ) ≤ ω−i ≤ yi − L(1− z−i ) i = 1 . . . m

z+i , z−i ∈ 0, 1 i = 1 . . . m

Le calcul de la valeur du pire optimum paramétrique, valeur de la solution opti-

male de W ′(Γ), (Γ ∈ N) est un problème difficile. Ceci est valable même dans le cas

où Γ = m, rejoignant ainsi le résultat du calcul du pire optimum de (Pb=), dont nous

avons prouvé la NP-difficulté à la section 2.2.2.

Conclusion

Dans ce chapitre nous avons proposé une extension de l’approche de Bertsimas et

Sim (2004) au calcul du pire optimum d’un programme linéaire où les incertitudes


affectent exclusivement le second membre des contraintes. Nous avons pour ce faire

paramétré le calcul du pire optimum par un budget d’incertitude unique commun à

toutes les contraintes.

De cette étude, nous avons établi que ce problème est dans le cas général un pro-

blème difficile et nous avons proposé une relaxation en programme linéaire mixte. Ceci

montre qu’en robustesse la prise en compte d’un budget d’incertitudes en colonnes

conduit à des problèmes plus difficiles que ceux issus de modèles d’incertitudes en

lignes. Très récemment, plusieurs auteurs emploient ce modèle d’incertitude pour

représenter les incertitudes sur des coefficients du second membre dans diverses

applications : Minoux (2007b;a) étudie un problème d’ordonnancement PERT robuste,

Atamtürk et Zhang (2007) et Minoux (2010) s’intéressent à des problèmes de dimen-

sionnement de réseaux et Minoux (2009a) traite d’un problème de flot dans un réseau.

Dans la suite de ce travail, nous changeons de contexte de décision et nous nous

plaçons dans un contexte bi-étapes dans lequel nous abordons une application du

problème de localisation et de transport robuste avec une demande incertaine. Comme

nous le détaillerons dans le chapitre suivant, le calcul du pire optimum paramétrique

sera d’une importance centrale dans la recherche des solutions robustes à ce problème.

En effet, adoptant un modèle d’incertitude paramétré par le budget d’incertitude décrit

dans le chapitre 3, nous montrerons que le problème de recours n’est autre que le

problème du pire optimum paramétrique.

4Application : Problème de

localisation et de transport

robuste bi-étapes

Sommaire

Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91

4.1 Problème de localisation et de transport déterministe . . . . . . . . 92

4.2 Problème de localisation et de transport robuste . . . . . . . . . . . 93

4.2.1 Formulation de la version robuste . . . . . . . . . . . . . . . . . . . . . . 93

4.2.2 Résolution du problème de localisation et de transport robuste . . . . . 97

4.2.3 Reformulation du problème de recours . . . . . . . . . . . . . . . . . . . 100

4.3 Expérimentations numériques . . . . . . . . . . . . . . . . . . . . . . . . . . 105

4.3.1 Problème de recours . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106

4.3.2 Problème de localisation et de transport robuste . . . . . . . . . . . . . . 109

4.3.3 Autre contexte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111

Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114

Dans ce chapitre, nous présentons une application du problème de localisation et

transport, où les demandes des clients sont incertaines. Afin de déterminer des

solutions robustes à ce problème, nous empruntons une approche robuste bi-étapes,

adaptée au contexte décisionnel du problème. Grâce à une borne très serrée établie

pour le problème de transport, nous exposerons les résultats de tests numériques réa-

lisés sur des instances de grande taille du problème.

89

91

Introduction

Ce chapitre traite du problème de localisation et de transport comportant des de-

mandes incertaines.

Le problème que nous abordons s’inscrit dans un contexte bi-étapes, et com-

prend des incertitudes modélisées dans le second membre des contraintes. Afin de

déterminer des solutions robustes, nous emploierons l’approche robuste bi-étapes

de Thiele et al. (2009) (présentée à la section 1.3). Pour rappel, selon cette approche,

les variables sont divisées en deux groupes distincts tels qu’une partie des variables

doit être décidée avant la réalisation de l’aléa, alors que la seconde partie est décidée

après divulgation des demandes. Étant données les incertitudes sur les demandes, il

s’agit de calculer une décision robuste de première étape, qui pour notre problème

correspond à la localisation, tout en garantissant l’existence d’un recours à la seconde

étape, représenté par le transport.

Selon cette approche, notre objectif est de construire la version robuste du pro-

blème de localisation et de transport puis de la résoudre de manière exacte. Nous

utiliserons, pour ce faire, un algorithme qui se base sur une procédure de génération

de contraintes (Kelley (1960)). Nous montrerons qu’une étape clé de cet algorithme

réside dans le calcul d’un pire optimum paramétrique (présenté au chapitre 3) associé

au problème de transport. De plus, ce calcul faisant intervenir une constante de grande

valeur, notre contribution sera de déterminer une borne serrée à cette constante. Ceci

nous permettra de résoudre des instances de grande taille du problème. Une version

synthétique de ce travail est présenté dans Gabrel et al. (2010b).

Le chapitre est structuré comme suit : dans la section 4.1, le problème de loca-

lisation et de transport déterministe sera décrit. Puis, une formulation robuste du

problème comportant une demande incertaine sera abordée à la section 4.2. Tout

d’abord, le contexte décisionnel du problème sera donné à la section 4.2.1 et la for-

mulation mathématique de la version robuste sera construite. Ensuite, un algorithme

de résolution de ce problème sera présenté dans la section 4.2.2. Enfin, dans la section

4.3, les résultats des tests expérimentaux qui ont été menés seront exposés.

92 Chapitre 4. Problème de localisation et de transport robuste

4.1 Problème de localisation et de transport déterministe

Considérons le problème de localisation et de transport suivant : une marchandise doit

être transportée de m entrepôts (ou sources) potentiels vers n clients. Les entrepôts

sont de capacités maximales égales à Ci pour tout i = 1, . . . , m. Les demandes des

clients sont notées β j, j = 1, . . . , n. Nous supposons que le problème est réalisable,

dans le sens où la somme totale des capacités est supérieure ou égale à la somme des

demandes. Divers coûts sont considérés : en premier lieu, les coûts fixes de construc-

tion des entrepôts sont notés par fi, i = 1 . . . m. Ensuite, les coûts variables de stockage

dans une source i, i = 1 . . . m, sont notés di. Enfin, les coûts unitaires d’acheminement

de marchandise d’une source i vers un client j sont notés µij. L’objectif visé est de

déterminer les entrepôts à construire (modélisés par les variables binaires ri), ainsi que

les quantités stockées dans chacun (modélisées par les variables yi) et les quantités à

acheminer des sources vers les clients (représentées par les variables tij) tels que les

coûts totaux soient minimum.

Le problème de localisation et de transport déterministe, noté (T), se formule alors

comme le programme linéaire mixte suivant :

(T)

minm

∑i=1

diyi +m

∑i=1

firi +m

∑i=1

n

∑j=1

µijtij

s.c.n

∑j=1

tij ≤ yi i = 1 . . . m

m

∑i=1

tij ≥ β j j = 1 . . . n

yi ≤ Ciri i = 1 . . . m

ri ∈ 0, 1, yi, tij ≥ 0 i = 1 . . . m, j = 1 . . . n

(4.1)

(4.2)

(4.3)

Les contraintes (4.1) et (4.2) sont les contraintes classiques relatives au transport, à

savoir que les quantités soustraites d’une source n’excèdent pas le niveau de stock

existant, et les quantités acheminées vers les clients sont suffisantes pour satisfaire les

demandes de ces derniers. Enfin, les contraintes (4.3) expriment, quant à elles, le fait

que pour une source ouverte, les quantités à stocker ne dépassent pas la capacité de la

source.

4.2. Problème de localisation et de transport robuste 93

4.2 Problème de localisation et de transport robuste

4.2.1 Formulation de la version robuste

Considérons le cas où le décideur souhaite construire des entrepôts de stockage sur

un certain nombre de sites, y stocker des marchandises, puis déterminer le routage de

celles-ci vers les clients. Il est rare qu’au moment de la construction des entrepôts, le

décideur connaisse les valeurs effectives des demandes ; il ne dispose en général que

d’estimations. Nous désirons prendre en compte cette incertitude sur les demandes

lors de la prise de décision sur le choix de la construction des entrepôts.

Dans ce qui suit, nous définirons précisément le contexte décisionnel du problème,

ainsi que le modèle d’incertitude associé aux demandes, puis nous exposerons la

formulation mathématique du problème robuste.

Contexte de décision

Le décideur procède en deux étapes : dans la première étape, les emplacements doivent

être choisis et les marchandises doivent être disposées dans les entrepôts correspon-

dant ; puis, dans la seconde étape, le routage de ces marchandises doit être décidé, et

ceci une fois que la demande des clients est connue. Ce problème de localisation et de

transport incertain s’inscrit donc dans un contexte bi-étapes.

De plus, nous admettrons une contrainte supplémentaire à la description du pro-

blème : à savoir que le décideur est dans l’obligation de satisfaire toutes les demandes

des clients quand elles se présentent. Il doit par conséquent garantir une quantité

suffisante de marchandises en stock prêtes à être acheminées.

Afin de formuler le problème, attachons-nous à décrire le domaine d’incertitude

qui modélisera les demandes des clients.

Modèle d’incertitude

La demande de chaque client est modélisée par un intervalle construit à partir d’une

valeur nominale autour de laquelle nous autorisons une déviation. Formellement,


suivant les notations du chapitre précédent, la demande β j du jeme client, pour tout

j = 1 . . . n, appartient à l’intervalle [βj − β j, βj + β j], où βj ≥ 0 représente la valeur

nominale de la demande et β j ≥ 0 sa déviation maximale.

Notons le problème (Tβ) correspondant à une instance du problème de localisa-

tion et de transport pour un vecteur β donné. Nous supposons que le domaine des

solutions réalisables pour tout problème (Tβ) est non vide. De plus, notons v∗(Tβ) la

valeur de la solution optimale du problème, que nous supposons finie.

Si le décideur voulait se prémunir du pire scénario de la demande, il lui suffirait de

résoudre la version déterministe du problème en prenant les plus grandes demandes.

Par conséquent, d’après le résultat de la section 2.1.1, le problème (Tβ)pirCas s’écrit :

(Tβ)pirCas

minm∑

i=1diyi +

m∑

i=1firi +

m∑

i=1

n∑

j=1µijtij

s.c.n∑

j=1tij ≤ yi i = 1 . . . m

m∑

i=1tij ≥ βj + β j j = 1 . . . n

yi ≤ Ciri i = 1 . . . m

ri ∈ 0, 1, yi, tij ≥ 0 i = 1 . . . m, j = 1 . . . n

La solution obtenue est robuste, car le décideur s’assure de satisfaire la demande

quand elle se présente, puisqu’il décide sur la base du scénario définissant les plus

fortes demandes.

Cependant, le décideur souhaite dimensionner ses entrepôts selon un scénario

moins conservateur que le scénario de pire cas (qui reste peu vraisemblable dans la

réalité) et cela en supposant que certaines demandes ne soient pas toutes les pires.

Rappelons cependant que le décideur doit impérativement prévoir assez de capacité

de stockage pour satisfaire toutes les demandes quand elles se présentent, y compris

les pires. Ces problèmes sont souvent rencontrés par des fournisseurs d’énergie qui

doivent installer des entrepôts de capacités capables de supporter une forte demande

mais désirent construire et stocker l’énergie selon un scénario plus réaliste et moins

extrême que celui du pire cas.

Nous proposons pour ce faire une modélisation des incertitudes selon le modèle


paramétrique décrit au chapitre 3, à savoir qu’un budget d’incertitude Γ est considéré

pour représenter le nombre de demandes déviant des valeurs nominales. Ici, la valeur

de Γ est comprise entre 0 et n. Ces deux valeurs décrivent les scénarios extrêmes

suivants : dans le cas où Γ = 0 toutes les demandes sont égales aux valeurs nominales,

et dans le cas où Γ = n toutes les demandes sont à leur maximum. Le décideur peut

ainsi modifier la valeur de Γ selon ses prévisions et déterminer une solution robuste

dans le budget d’incertitude qu’il s’autorise.

Formulation mathématique du problème robuste

Appliquons au problème incertain (Tβ) l’approche robuste bi-étapes, présentée dans la

section 1.3. En rappelant que le décideur doit définir les emplacements des entrepôts

ainsi que leur dimensionnement avant que les demandes ne soient connues, nous

définissons les variables ri et yi, i = 1 . . . m comme étant les variables de première

étape. L’acheminement des marchandises se faisant après divulgation des demandes,

les variables tij représentent alors les variables de recours ou de seconde étape.

Le problème de localisation et de transport robuste bi-étapes consiste à détermi-

ner le coût minimum de la localisation et du dimensionnement des entrepôts de telle

sorte que quelles que soient les demandes formulées, il existe un routage de coût mi-

nimum assurant la satisfaction de ces demandes. La formulation du problème robuste

bi-étapes, notée TRob(Γ), est la suivante :

TRob(Γ)

min

yi≤Ciri , i=1...mm∑

i=1yi≥B

yi≥0, ri∈0,1

(m∑

i=1diyi +

m∑

i=1firi+ max

β∈UT (Γ)min

n∑

j=1tij≤yi , i=1...m

m∑

i=1tij≥β j , j=1...n

tij≥0, i=1...m, j=1...n

m∑

i=1

n∑

j=1µijtij)

où

B =n

∑j=1

(βj + β j) (4.4)

et le domaine d’incertitude paramétrique UT (Γ) est défini par :

UT (Γ) = β ∈ Rn : β j = βj + zj β j, j = 1 . . . n, z ∈ Z(Γ) (4.5)


avec

ZT (Γ) = z ∈ Rn :n

∑j=1

zj ≤ Γ, 0 ≤ zj ≤ 1, j = 1 . . . n (4.6)

La contraintem∑

i=1yi ≥ B, où B est donné par (4.4), exprime le fait que le décideur,

une fois les demandes connues, doit pouvoir satisfaire ses clients. Le recours est ainsi

considéré complet, dans le sens où pour toute solution (y, r), le problème de transport

possède une solution finie, quelles que soient les demandes qui se réalisent, même

dans les cas où elles excèdent les prévisions et atteignent leur maximum.

Avantages d’une telle approche

Comme nous l’avons souligné auparavant, dans une approche classique de pire cas

toutes les décisions relatives à la localisation, au dimensionnement et au routage sont

prises sur la base des plus fortes demandes. Ainsi, la quantité de marchandises stockée

dans tous les entrepôts sera égale à la quantité nécessaire pour satisfaire ces demandes

maximales. La localisation et l’acheminement seront également optimisés de manière

à satisfaire cette pire demande.

Dans le cas de l’approche bi-étapes que nous traitons ici, la satisfaction de la

demande reste une condition qui doit être remplie dans tous les cas. Aussi, la somme

des quantités stockées sera la même que dans l’approche pire cas. Cependant, la locali-

sation et le dimensionnement des entrepôts seront optimisés en fonction des scénarios

de la demande. La valeur de cette demande est pilotée par le budget d’incertitude Γ

fixé par le décideur.

Il est alors clair que les solutions apportées par cette approche sont différentes de

celles apportées par une approche pire cas classique. Nous montrerons dans la section

4.3.2 qu’un gain important est réalisé avec cette approche bi-étapes comparativement

à une approche pire cas.


4.2.2 Résolution du problème de localisation et de transport robuste

Nous proposons à présent une résolution exacte du problème robuste TRob(Γ). Tout

d’abord, identifions le problème de recours comme étant le problème d’optimisation,

noté R(y, Γ), suivant :

R(y, Γ)

maxn∑

j=1zj≤Γ

0≤zj≤1, j=1...n

minn∑

j=1tij≤yi , i=1...m

m∑

i=1tij≥βj+β jzj, j=1...n

tij≥0, i=1...m, j=1...n

m∑

i=1

n∑

j=1µijtij

Nous remarquons qu’il s’agit du problème de recherche du pire optimum paramé-

trique (étudié au chapitre 3) associé au problème classique de transport avec les

capacités y fixées et une déviation totale égale à Γ. La résolution du problème robuste

TRob(Γ) va être intimement liée à la résolution de ce problème de recours.

Par hypothèse, le problème de transport est réalisable, et l’optimum est atteint en une

valeur finie, quelles que soient les capacités y (satisfaisant les contraintes du problème)

et quel que soit le budget d’incertitude Γ. Par conséquent, d’après le théorème fort de

la dualité, le problème de recours est équivalent au problème suivant :

Q(y, Γ)

max −m∑

i=1yiui +

n∑

j=1βjvj +

n∑

j=1β jvjzj

s.c. vj − ui ≤ µij i = 1 . . . m, j = 1 . . . nn∑

j=1zj ≤ Γ

0 ≤ zj ≤ 1 j = 1 . . . n

ui, vj ≥ 0 i = 1 . . . m, j = 1 . . . n

où ui, vj pour tout i = 1 . . . m, j = 1 . . . n représentent les variables du problème dual

du problème de transport. Le problème Q(y, Γ) est un problème quadratique. Il est

possible de le linéariser en un programme linéaire mixte, comme cela a été montré au

chapitre 3. Nous proposons par la suite de détailler le calcul d’une borne très serrée

permettant une résolution rapide de ce problème.

Revenons au problème de localisation et de transport robuste Trob(Γ). Ce problème


peut s’écrire de manière équivalent comme suit :

Trob(Γ)

minm∑

i=1diyi +

m∑

i=1firi + v∗(Q(y, Γ))

s.c. yi ≤ Ciri i = 1 . . . mm∑

i=1yi ≥ B

yi ≥ 0, ri ∈ 0, 1 i = 1 . . . m

où v∗(Q(y, Γ)) est égale à la valeur d’une solution optimale de Q(y, Γ).

Comme suggéré par Thiele et al. (2009) dans le cas général, nous adaptons dans ce

qui suit, l’algorithme de génération de contraintes proposé par Kelley (1960) pour

résoudre le problème Trob(Γ).

Remarquons, tout d’abord, que l’optimum du problème Q(y, Γ) se réalise en un

point extrême du domaine des solutions réalisables. Par conséquent, il est possible de

reformuler le problème robuste Trob(Γ) comme suit :

Trob(Γ)

minm∑

i=1diyi +

m∑

i=1firi + α

s.c. α ≥ −m∑

i=1yius

i +n∑

j=1βjv

sj +

n∑

j=1β jvs

j zsj s = 1 . . . S

m∑

i=1yi ≥ B

yi ≤ Ciri i = 1 . . . m

α, yi ≥ 0, ri ∈ 0, 1 i = 1 . . . m

où S représente l’ensemble des points extrêmes du problème de recours Q(y, Γ), pour

un vecteur y fixé et un budget d’incertitude Γ.

L’idée générale de l’algorithme est la suivante : initialement, un sous-ensemble de

points extrêmes de S est considéré et une version relaxée du problème Trob(Γ), nommée

problème maître, est résolue. La solution optimale est notée (y∗, r∗). Il s’agit du problème

de première étape, relatif à la localisation. Les valeurs de y∗ sont ensuite fixées dans

le problème de recours correspondant au transport et nommé problème esclave, afin de

vérifier son optimalité. Si tel n’est pas le cas, une contrainte est ajoutée au problème

maître. Cette procédure est réitérée jusqu’à vérification du critère d’arrêt et obtention

de la solution optimale. Le critère d’arrêt étant défini par l’égalité de deux bornes


(une borne supérieure U et une borne inférieure L). Formellement l’algorithme est le

suivant :

Algorithme 2 : Algorithme de Kelley pour la résolution de Trob(Γ)

Étape 0 : Initialisation :Définir T1

rob(Γ) contenant un seul point extrême (u0, v0, z0) avec u0 = v0 = z0 = 0.Poser L← −∞, U ← +∞ et k← 1. Aller à l’Étape 1.Étape 1 :Résoudre le problème maître

Tkrob(Γ)

minm∑

i=1diyi +

m∑

i=1firi + α

s.c. α ≥ −m∑

i=1yiul

i +n∑

j=1βjv

lj +

n∑

j=1β jvl

jzlj l = 0 . . . k− 1

m∑

i=1yi ≥ B

yi ≤ Ciri i = 1 . . . myi ≥ 0, ri ∈ 0, 1 i = 1 . . . m

Noter par (yk, rk, αk) sa solution optimale.

Mettre à jour la valeur de la borne L←m∑

i=1diyk

i +m∑

i=1firk

i + αk, et aller à l’Étape 2.

Étape 2 :Pour les capacités fixées à yk, résoudre le problème de recours Q(yk, Γ) et noter sasolution (uk, vk, zk).

Poser U ← minU,m∑

i=1diyk

i +m∑

i=1firk

i −m∑

i=1yk

i uki +

n∑

j=1βjv

kj +

n∑

j=1β jvk

j zkj .

Si U = L AlorsRetourner (yk, rk, αk), qui représente la solution robuste de Trob(Γ)

Sinonaller à l’Étape 3

Fin SiÉtape 3 :Ajouter la contrainte

α ≥ −m

∑i=1

yiuki +

n

∑j=1

βjvkj +

n

∑j=1

β jvkj zk

j

au problème maître Tkrob(Γ), k← k + 1 et aller à l’Étape 1.


Convergence de l’algorithme : [Kelley (1960)] il est clair que la valeur d’une solution

de (Tkrob(Γ)) à l’itération k, notée L, représente une borne inférieure à la valeur d’une

solution du problème robuste. En effet, Tkrob(Γ) ne contient qu’un sous-ensemble de

contraintes de Trob(Γ). À chaque itération, des contraintes sont ajoutées à Tkrob(Γ),

et ainsi la valeur de L est non décroissante. Par ailleurs, étant donné qu’à chaque

itération k, la solution (yk, rk, uk, vk, zk) est une solution réalisable de Trob(Γ), la borne

supérieure U consiste à prendre la valeur minimale de toutes les solutions réalisables

générées. De plus, le nombre de points extrêmes de S étant fini, nous déduisons de ce

qui précède que l’algorithme converge vers la solution optimale du problème.

Comme nous le voyons, cet algorithme se base sur l’optimisation itérative de deux

problèmes : d’une part, la résolution d’une version relaxée du problème, modélisée

par un programme linéaire mixte, et d’autre part, le problème de recours Q(yk, Γ), qui

est un problème quadratique. Il s’en suit que la résolution du problème robuste Trob(Γ)

dépend fortement de la résolution du problème de recours, bien plus difficile. Nous

utiliserons, dans ce qui suit, la reformulation présentée au chapitre 3 pour linéariser

ce dernier.

4.2.3 Reformulation du problème de recours

Il est naturel de supposer que le paramètre Γ prenne des valeurs entières dans l’inter-

valle [0, n]. Il représente ainsi le nombre de demandes que le décideur autorise à dévier

des valeurs nominales. Dans ce cas, le problème Q(y, Γ) est linéarisable (d’après la pro-

position 3.1 du chapitre 3), et peut se formuler comme un programme linéaire mixte

comme suit :

Q′(y, Γ)

max −m∑

i=1yiui +

n∑

j=1βjvj +

n∑

j=1β jωj

s.c. vj − ui ≤ µij i = 1 . . . m, j = 1 . . . nn∑

j=1zj ≤ Γ

ωj ≤ vj j = 1 . . . n

ωj ≤ Mzj j = 1 . . . n

zj ∈ 0, 1 j = 1 . . . n

ui, vj, ωj ≥ 0 j = 1 . . . n, i = 1 . . . m


où M est une constante positive de grande valeur.

Afin de réduire le saut d’intégrité lors de la résolution du problème Q′(y, Γ), la valeur

de M doit être la plus serrée possible. Étant donné que les constantes du problème

ne sont pas toutes strictement positives, il n’est pas possible d’utiliser les deux bornes

définies à la section 3.1.2 du chapitre 3 (voir la remarque 3.2). Une borne spécifique

pour les variables v du problème doit être calculée. La proposition 4.1 fournit une

borne serrée pour les constantes M pour ce problème de transport.

Proposition 4.1 Dans le problème Q′(y, Γ) les valeurs de M peuvent être fixées spécifique-

ment pour chacune des variables vj comme suit :

Mj = v∗j (n)

où v∗j (n), j = 1, . . . , n, est la valeur dans la solution optimale des variables v du problème

Q′(y, n).

Afin de montrer cette proposition, montrons tout d’abord le théorème 4.1.

Théorème 4.1 Soit (D∗) le dual du problème classique de transport :

(D∗)

max −

m∑

i=1yiui +

n∑

j=1β jvj

s.c. −ui + vj ≤ µij i = 1 . . . m, j = 1 . . . n

ui, vj ≥ 0 i = 1 . . . m, j = 1 . . . n

Notons (u∗, v∗) la solution optimale de (D∗) et Z∗(u∗, v∗) sa valeur à l’optimum.

Considérons par ailleurs, une instance du problème de transport, telle que la demande du pre-

mier client soit égale à β1 − β1 avec β1 > 0. Le problème dual, noté (D′), d’une telle instance

est le programme linéaire :

(D′)

max −

m∑

i=1yiui + (β1 − β1)v1 +

n∑

j=2β jvj

s.c. −ui + vj ≤ µij i = 1 . . . m, j = 1 . . . n

ui, vj ≥ 0 i = 1 . . . m, j = 1 . . . n


Alors, il existe au moins une solution optimale (u′, v′) de (D′) telle que u′ ≤ u∗ et v′ ≤ v∗.

Démonstration. Dans le cas trivial où (u∗, v∗) est optimale pour (D′), le théorème 4.1

est vérifié. Nous nous intéressons au cas contraire. Soit (u′, v′) une solution optimale

du problème (D′) qui ne satisfait pas le théorème 4.1, et définissons la solution (u′′, v′′)

comme suit :

u′′i = minu∗i , u′i pour tout i = 1 . . . m

v′′j = minv∗j , v′j pour tout j = 1 . . . n

Montrons que (u′′, v′′) est une solution optimale de (D′).

Tout d’abord, montrons que (u′′, v′′) est une solution réalisable. Par l’absurde, suppo-

sons qu’il existe un indice i1 et un indice j1 pour lesquels −u′′i1 + v′′j1 > µi1 j1 . Deux cas

de figure se distinguent :

– Si u′′i1 = u∗i1 alors

u∗i1 < −µi1 j1 + v′′j1 (4.7)

Par ailleurs, par définition on a v′′j1 ≤ v∗j1 , ce qui implique que :

− µi1 j1 + v′′j1 < −µi1 j1 + v∗j1 (4.8)

De (4.7) et (4.8) nous déduisons que u∗i1 < −µi1 j1 + v∗j1 , ce qui contredit la réalisa-

bilité de la solution (u∗, v∗).

– Si u′′i1 = u′i1 alors

u′i1 < −µi1 j1 + v′′j1 (4.9)

Par définition v′′j1 ≤ v′j1 et donc

− µi1 j1 + v′′j1 < −µi1 j1 + v′j1 (4.10)

De (4.9) et (4.10) nous déduisons que u′i1 < −µi1 j1 + v′j1 , ce qui contredit la réali-

sabilité de la solution (u′, v′).

Par conséquent, la solution (u′′, v′′) est réalisable.

Avant de prouver que (u′′, v′′) est optimale pour (D′), montrons que v′′1 = v′1. Par


l’absurde, supposons que v′′1 = v∗1 (impliquant que v∗1 ≤ v′1). Étant donné que (u∗, v∗)

n’est pas optimale pour (D′) par hypothèse, alors :

Z′(u∗, v∗) < Z′(u′, v′) (4.11)

où Z′(u∗, v∗) (respectivement Z′(u′, v′)) est la valeur de la solution (u∗, v∗) (respecti-

vement (u′, v′)) pour le problème (D′). De plus, pour toute solution réalisable (u, v)

nous avons :Z′(u, v) = −

m∑

i=1yiui +

n∑

j=1β jvj − β1v1

Z∗(u, v) = −m∑

i=1yiui +

n∑

j=1β jvj

ce qui implique que :

Z′(u, v) = Z∗(u, v)− β1v1 (4.12)

De (4.11) et (4.12) on obtient

Z∗(u∗, v∗)− β1v∗1 < Z∗(u′, v′)− β1v′1 (4.13)

Z∗(u∗, v∗)− Z∗(u′, v′) < β1v∗1 − β1v′1 (4.14)

Si nous supposons que v∗1 ≤ v′1, alors β1v∗1 − β1v′1 ≤ 0. Par conséquent, (4.14) implique

que :

Z∗(u∗, v∗)− Z∗(u′, v′) < 0 (4.15)

ce qui contredit le fait que (u∗, v∗) soit optimale pour (D∗). Il est alors clair que v∗1 ≥ v′1et donc que

v′′1 = v′1 (4.16)

Montrons à présent que (u′′, v′′) est une solution optimale de (D′). Le coût de cette

solution est égal à :

Z′(u′′, v′′) = −m

∑i=1

yiu′′i + (β1 − β1)v′′1 +n

∑j=2

β jv′′j (4.17)


Soit I ⊆ I le sous-ensemble d’indices de I = 1 . . . m tel que i ∈ I si u′′i = u′i, et donc

u′i ≤ u∗i . On définit J ⊆ J comme étant le sous-ensemble d’indices de J = 1 . . . n tel

que j ∈ J si v′′j = v′j, et donc v′j ≤ v∗j . La valeur de la solution (u′′, v′′) est égale à :

Z′(u′′, v′′) = − ∑i∈I

yiu′i + ∑j∈J\1

β jv′j + (β1 − β1)v′′1 − ∑i∈I\I

yiu∗i + ∑j∈J\J

β jv∗j

De (4.16), remplaçons v′′1 par v′1. Nous obtenons :

Z′(u′′, v′′) = − ∑i∈I

yiu′i + (β1 − β1)v′1 + ∑j∈J\1

β jv′j + ∑i∈I\I

yi(u′i − u∗i )− ∑j∈J\J

β j(v′j − v∗j )

= Z′(u′, v′) + ∑i∈I\I

yi(u′i − u∗)− ∑j∈J\J


Si (u′′, v′′) n’est pas optimale pour (D′), alors la quantité :

A = ∑i∈I\I

yi(u′i − u∗i )− ∑j∈J\J

β j(v′j − v∗j ) (4.18)

doit être strictement négative. Montrons que cela conduit à une contradiction.

Pour ce faire, définissons une autre solution notée (u, v) comme suit :

ui = maxu∗i , u′i pour tout i = 1 . . . m

vj = maxv∗j , v′j pour tout j = 1 . . . n

Suivant le même raisonnement que celui employé pour la solution (u′′, v′′), il est facile

de montrer que la solution (u, v) est réalisable. La valeur de cette dernière pour le

problème (D∗) est égale à :

Z∗(u, v) = −m∑

i=1yiui +

n∑

j=1β jvj

= − ∑i∈I

yiu∗i − ∑i∈I\I

yiu′i + ∑j∈J

β jv∗j + ∑j∈J\J

β jv′j

= − ∑i∈I

yiu∗i + ∑j∈J

β jv∗j − ∑i∈I\I

yi(u′i − u∗i ) + ∑j∈J\J


= Z∗(u∗, v∗)− ∑i∈I\I

yi(u′i − u∗i ) + ∑j∈J\J


= Z∗(u∗, v∗)− A

Supposer que A < 0 contredit l’optimalité de la solution (u∗, v∗) pour (D∗). Par consé-

4.3. Expérimentations numériques 105

quent, A ≥ 0 et Z′(u′′, v′′) ≥ Z′(u′, v′). Plus précisément, A = 0 et la solution (u, v)

est optimale pour (D∗). En conclusion, nous avons construit la solution (u′′, v′′) qui est

réalisable et optimale pour (D′) et vérifie le théorème 4.1.

La proposition 4.1 se déduit directement du théorème 4.1. En premier lieu, nous re-

marquons qu’à l’optimum, les valeurs des variables u∗i et v∗j pour i = 1 . . . m, j = 1 . . . n

représentent des bornes supérieures pour les variables u et v respectivement dans

toutes les instances du problème de transport où une ou plusieurs demandes dé-

croissent. En second lieu, nous rappelons que pour la valeur de Γ = n, toutes les

demandes sont égales aux plus grandes valeurs βj + β j. Par conséquent, quand Γ

décroît, certaines d’entre elles vont aussi diminuer. Nous en déduisons que les valeurs

de v∗j (n), solution du problème Q′(y, n), représentent des bornes supérieures pour les

valeurs des variables v dans le problème Q′(y, Γ) où Γ ≤ n et Γ ∈N.

Remarque 4.1 Dans l’algorithme 2, les valeurs des bornes v∗(n) doivent être recalculées à

chaque itération. En effet, un nouveau vecteur yk est généré à chaque itération. Il s’en suit qu’à

l’étape 2 de l’algorithme, le problème de recours est résolu deux fois :

– une première fois, en posant Γ = n, afin d’obtenir les valeurs de v∗(n). Ce calcul se fait

rapidement, étant donné que Q′(yk, n) est un programme linéaire.

– en utilisant les valeurs de v∗(n), le problème Q′(yk, Γ) est résolu.

4.3 Expérimentations numériques

Nous exposons dans cette section les résultats expérimentaux réalisés sur la version

robuste du problème de localisation et de transport. L’objectif est de tester la vitesse

de convergence de l’algorithme de Kelley et la capacité d’un solver à résoudre le

problème de recours. Notre étude est séparée en deux parties : tout d’abord, en posant

les conditions adéquates de réalisabilité, nous traiterons uniquement le problème de

recours, en comparant la borne définie à la section 4.2.3 avec une borne de valeur

arbitrairement grande. La seconde partie est consacrée à la résolution du problème

robuste dans sa globalité.


4.3.1 Problème de recours

Les données du problème

Les premières séries de tests ont été réalisées sur le problème de recours Q′(y, Γ), pour

des valeurs fixées de sources m et de demandes n, et différentes valeurs de Γ. Afin de se

rapprocher de la réalité, le nombre de clients est choisi plus grand que le nombre d’en-

trepôts. Toutes les autres données du problème sont générées aléatoirement comme

suit :

– les demandes : pour tout j = 1, . . . , n , la demande nominale βj est générée aléa-

toirement dans l’intervalle [10, 500], et les déviation β j = pjβj, où pj représente

le pourcentage de déviation maximale pour chaque demande j. Les valeurs de pj

sont générées dans [0.1, 0.5], ce qui assure des déviations strictement positives.

– Les capacités : les valeurs de capacités yi, i = 1 . . . m, sont obtenues en répar-

tissant équitablement la valeur totale des demandes maximales sur le nombre

d’entrepôts. Ainsi, le problème est réalisable.

– Les coûts de transport µij sont générés uniformément dans [1, 1000].

Résolution du problème de recours

Le problème Q′(y, Γ) est résolu à l’aide du solver CPLEX 11.2. Pour tout couple (n, m)

fixé, 10 instances ont été générées et résolues. En fixant le temps de résolution maximal

à 35 mn, nous montrons dans le tableau 4.1 les résultats regroupant le temps moyen

d’exécution, ainsi que le pourcentage des instances résolues dans le temps imparti, et

cela en comparant deux bornes de M différentes : la borne v∗(n) décrite à la section

4.2.3, et une borne de valeur arbitre grande. Pour les instances non résolues au bout

de 35 mn, nous considérons un temps d’exécution égal à 2100 s.

Les résultats reportés dans le tableau 4.1 montrent que les temps de résolution relatifs

à la résolution du problème de recours où M = v∗(n) sont nettement plus courts que

ceux obtenus par une borne arbitrairement grande, et cela pour toutes les instances

testées. De plus, nous remarquons que ce temps s’allonge quand Γ est compris entre

n/2 et 2n/3, comme le montre la figure 4.1.a. Ceci s’explique par la combinatoire

élevée autour des valeurs de n/2. Par ailleurs, la figure 4.1.b montre l’évolution de la

valeur de la fonction objectif en fonction de Γ pour un échantillon m = 100 et n = 250.

Nous obtenons une courbe concave où v∗(Q′(y, Γ)) augmente rapidement pour des

petites valeurs de Γ et qui s’aplatie quand Γ s’approche de n. En effet, pour des petites


Tab. 4.1 – Résultats des temps d’exécution du problème de recours

Temps (s) Inst. résolues

n×m Γ (%) M v∗(n) M v∗(n)

25% 2.63 0.76 10/10 10/10

250× 10 50% 1178.14 14.05 5/10 10/10

75% 215.24 0.97 9/10 10/10

25% 14.86 2.09 10/10 10/10

250× 50 50% 434.85 4.94 9/10 10/10

75% 645.52 6.80 7/10 10/10

25% 8.57 1.82 10/10 10/10

250× 100 50% 18.93 2.69 10/10 10/10

75% 46.05 12.66 10/10 10/10

25% 4.99 1.00 10/10 10/10

500× 10 50% 1051.82 1050.25 5/10 5/10

75% 843.92 2.29 6/10 10/10

25% 10.49 1.60 10/10 10/10

500× 50 50% 223.63 5.52 9/10 10/10

75% 612.10 11.94 8/10 10/10

25% 12.03 1.90 10/10 10/10

500× 100 50% 10.98 2.26 10/10 10/10

75% 170.57 21.34 10/10 10/10

25% 35.59 3.26 10/10 10/10

1000× 10 50% 1472.13 1260.21 3/10 4/10

75% 1530.47 10.42 3/10 10/10

valeurs de Γ la valeur du pire optimum paramétrique se fonde sur les demandes les

plus contraignantes, puis au fur et à mesure que Γ augmente, les demandes moins

contraignantes sont intégrées.

0 5 0 1 0 0 1 5 0 2 0 0 2 5 0

0

2 0

4 0

6 0

8 0

1 0 0

1 2 0

0 5 0 1 0 0 1 5 0 2 0 0 2 5 08 0 0 0

9 0 0 0

1 0 0 0 0

1 1 0 0 0

1 2 0 0 0

1 3 0 0 0

1 4 0 0 0

Temp

s d’ex

ecus

sion (

s)

G a m m a( a )

M v * ( n )

Valeu

r de l

’optim

um

G a m m a( b )

Fig. 4.1 – Résolution du problème de recours pour un exemple m=100 et n=250 : a- Temps de résolutionen fonction de Γ. b- Valeur de l’optimum en fonction de Γ.


Des tests supplémentaires ont été réalisés sur le problème de transport, utilisant les

bornes v∗(n), et cela dans le but de déterminer les tailles d’instances qu’il est possible

de résoudre dans un temps limité à une heure d’exécution. La figure 4.2 montre les

résultats obtenus pour un nombre de clients fixé à n = 500. Nous observons que

le temps de calcul augmente avec le nombre de sources m considéré. En effet, pour

m = 10, le problème est résolu en quelques secondes seulement. Une moyenne de 20

minutes est nécessaire pour résoudre les instances admettant m = 80 entrepôts et une

déviation totale égale à Γ = 60%, alors que le temps d’exécution approche une heure

quand m ∈ [300, 500] et Γ = 50%.

0 1 0 0 2 0 0 3 0 0 4 0 0 5 0 0 6 0 0

0

5 0 0

1 0 0 0

1 5 0 0

2 0 0 0

2 5 0 0

3 0 0 0

0 1 0 0 2 0 0 3 0 0 4 0 0 5 0 00 , 0 00 , 0 10 , 0 20 , 0 30 , 0 40 , 0 50 , 0 60 , 0 70 , 0 80 , 0 90 , 1 00 , 1 10 , 1 20 , 1 30 , 1 40 , 1 5

G a m m a( a )

m = 1 0 m = 2 0 m = 3 0 m = 4 0 m = 5 0 m = 6 0 m = 7 0 m = 8 0 m = 9 0 m = 1 0 0 m = 2 0 0 m = 3 0 0 m = 4 0 0

G a m m a( b )

m = 1 0 m = 2 0 m = 3 0 m = 4 0 m = 5 0 m = 6 0 m = 7 0 m = 8 0 m = 9 0 m = 1 0 0 m = 2 0 0 m = 3 0 0 m = 4 0 0

Fig. 4.2 – Résolution du problème de recours pour des tests n=500 : a- Temps d’exécution en fonctionde Γ. b- Saut d’intégrité en fonction de Γ.

La figure 4.3.a illustre quant à elle les résultats relatifs à n = 1000 demandes incer-

taines. Nous observons que toutes les instances où m = 10 sont résolues en moins

d’une heure, quelle que soit la valeur de Γ entre 10% et 100%. Quand 100 ≤ m ≤ 500

le solver ne résout aucune instance en moins d’une heure pour Γ = 50%. Au delà de

m = 600 entrepôts, l’espace mémoire devient insuffisant.

De plus, nous avons calculé le saut d’intégrité entre la valeur de la solution exacte et la

valeur de la solution de la relaxation linéaire du problème de recours. Les figures 4.2.b

et 4.3.b illustrent ce rapport pour des instances correspondant à n = 500 et n = 1000

demandes respectivement. Nous remarquons que pour les deux séries de tests, le

saut d’intégrité est plus faible pour des petites valeurs de m, et atteint son maximum

quand Γ est autour de 20% de déviation totale. Par ailleurs, le coût supplémentaire


0 1 0 0 2 0 0 3 0 0 4 0 0 5 0 0 6 0 0 7 0 0 8 0 0 9 0 0 1 0 0 0

0

5 0 0

1 0 0 0

1 5 0 0

2 0 0 0

2 5 0 0

3 0 0 0

3 5 0 0

4 0 0 0

0 1 0 0 2 0 0 3 0 0 4 0 0 5 0 0 6 0 0 7 0 0 8 0 0 9 0 0 1 0 0 00 , 0 0

0 , 0 1

0 , 0 2

0 , 0 3

0 , 0 4

0 , 0 5

0 , 0 6

0 , 0 7

0 , 0 8

0 , 0 9

0 , 1 0

0 , 1 1

G a m m a( a )

m = 1 0 m = 1 0 0 m = 2 0 0 m = 3 0 0 m = 4 0 0 m = 5 0 0 m = 6 0 0

G a m m a( b )

m = 1 0 m = 1 0 0 m = 2 0 0 m = 3 0 0 m = 4 0 0

Fig. 4.3 – Résolution du problème de recours pour des tests n=1000 : a- Temps d’exécution en fonctionde Γ. b- Saut d’intégrité en fonction de Γ.

(par rapport à la solution optimale) engendré par la relaxation linéaire ne dépasse pas

13%. Par exemple, si l’on s’autorise Γ = 70% de déviation, la différence de coût entre

la résolution exacte et sa relaxation linéaire ne dépasse pas 3%. Ceci confirme que la

borne utilisée est très serrée.

4.3.2 Problème de localisation et de transport robuste

Dans cette section, nous présentons les résultats de calcul concernant la résolution

du problème de localisation et de transport robuste bi-étapes Trob(Γ). En plus des

données précédemment générées sur la partie du transport, nous incluons la partie

localisation du problème, à savoir : pour toute source i, i = 1 . . . m, les capacités Ci

sont générées uniformément dans [200, 700]. Les coûts fixes et variables appartiennent

respectivement aux intervalles [100, 1000] et [10, 100]. Nous montrons les résultats

numériques issus de l’application de l’algorithme de Kelley (décrit à la section 4.2.2)

sur le problème Trob(Γ), tel que le temps d’exécution est limité à deux heures.

Dans la figure 4.4.a est reportée la valeur de l’optimum du problème robuste en

fonction de Γ pour un échantillon m = 50 et n = 50. L’allure de la courbe de la

fonction objectif est similaire à celle du problème de recours (voir la figure 4.1.b). En

effet, quand la valeur de Γ augmente, le coût augmente, rapidement pour des petites

valeurs de Γ, et plus lentement quand Γ s’approche de n. La figure 4.4.b illustre pour

le même exemple, l’écart -en pourcentage- entre la valeur de l’optimum de Trob(Γ)


0 10 20 30 40 50 60 70 80 90 1000

2

4

6

8

10

12

14

16

18

20

Delta

opt /

Max o

pt

Gamma(%)(b)

0 10 20 30 40 50 60 70 80 90 100

23

24

25

26

27

28

29

Valeu

r de l

'optim

um (

x 105 )

Gamma(%)(a)

Fig. 4.4 – Résolution du problème Trob(Γ) pour un test n = m = 50 : a- Valeur de l’optimum enfonction de Γ. b- ∆Opt

MaxOpt en fonction de Γ

et la solution de pire cas (pour le problème mono-étape où Γ = n) en fonction de Γ.

Nous remarquons que le décideur peut réaliser un gain significatif, jusqu’à 18% de

bénéfices, sur les coûts de transport par rapport à une approche classique de pire cas,

et cela tout en garantissant la réalisabilité du problème et la satisfaction des demandes

des clients, même les plus élevées. Ce gain est d’autant plus grand que Γ est petit. Ceci

montre la pertinence de notre approche.

Nous nous intéressons à présent au temps de résolution du problème robuste. Le

tableau 4.2 résume les résultats de plusieurs séries de tests, où le nombre de sources

et de clients ont été fixés respectivement à n = m = 10, 70, 100 et 150. Les résultats

montrent que pour n = m = 10, 50 ou 70, l’algorithme nécessite jusqu’à 20mn de

temps d’exécution. Pour des tailles d’instances n = m = 100 ce temps est plus long,

et dépasse les deux heures pour certaines valeurs de Γ. À partir de n = m = 150, ce

temps limite est atteint presque pour toutes les instances pour Γ ∈ [30%, 80%].

Par ailleurs, les colonnes 5 et 6 du tableau 4.2 montrent la proportion de temps

passé dans la résolution du problème maître et le problème esclave respectivement.

Les résultats confirment que la partie la plus coûteuse en temps dans l’algorithme

de Kelley est la résolution du problème de recours, notamment quand Γ est autour

de n/2. Enfin, nous remarquons que pour Γ = 100%, le problème de recours devient

un problème facile (en fait, équivalent à un programme linéaire), ce qui explique les


résultats en ces lignes.

Tab. 4.2 – Temps d’exécution de la résolution du problème robuste Trob(Γ)

n×m Γ(%) # iter. Temps (s) Pb. Maître(%) Pb. Recours(%) Inst. Resolues

10× 10 10% 8.6 0.05 10 90 10/10

20% 9.2 0.06 8.8 91.2 10/10

30% 10 0.06 8.8 91.2 10/10

40% 10.1 0.06 7.0 93.0 10/10

50% 10 0.05 5.0 95.0 10/10

60% 10 0.06 4.2 95.8 10/10

70% 10.3 0.04 6.0 94.0 10/10

80% 9.4 0.04 7.1 92.9 10/10

90% 9.9 0.03 10.1 89.9 10/10

100% 8.8 0.02 50.0 50.0 10/10

70× 70 10% 117.9 124.14 28.9 71.1 10/10

20% 130.3 263.14 19.6 80.4 10/10

30% 124.4 570.62 6.3 93.7 10/10

40% 141.7 804.67 7.1 92.9 10/10

50% 153.9 964.01 6.0 94.0 10/10

60% 159.3 1085.50 7.1 92.9 10/10

70% 170.4 702.98 10.3 89.7 10/10

80% 184 351.58 26.3 73.7 10/10

90% 163.5 141.07 49.6 50.4 10/10

100% 146.4 57.67 84.1 15.9 10/10

100× 100 10% 194.4 760.07 40.7 59.3 10/10

20% 180.2 1359.50 37.1 62.9 10/10

30% 208.1 1842.72 30.3 69.7 9/10

40% 231.1 2837.36 23.0 77.0 9/10

50% 235.9 4087.44 13.1 86.9 8/10

60% 237.7 4285.29 6.6 93.4 7/10

70% 228.1 3261.86 13.5 86.5 8/10

80% 245.2 2890.07 27.0 73.0 7/10

90% 265.6 1292.35 70.8 29.2 10/10

100% 242.2 633.17 93.6 6.4 10/10

150× 150 10% 261,7 2647 19.4 80.6 10/10

20% 302,4 5499.08 12.8 87.2 8/10

30% 298,4 6316.47 6.4 93.6 6/10

40% 231 6375.56 3.6 96.4 6/10

50% 181 6677.38 1.5 98.5 4/10

60% 242 7042.79 2.5 97.5 3/10

70% - 7200 10.1 89.9 0/10

80% 222,6 6216.67 22.6 77.4 5/10

90% 286,1 3723.10 56.9 43.1 7/10

100% 306,5 2374.98 93.4 6.6 7/10

4.3.3 Autre contexte

Clôturons cette partie expérimentale en exposant quelques résultats expérimentaux

sur la résolution du problème de localisation et de transport dans un contexte bi-étapes

différent. En effet, considérons une autre version du problème de localisation et de

transport, où le décideur tolère que le stockage ne garantisse pas de satisfaire les pires


demandes et désire dimensionner les entrepôts tout comme l’acheminement selon la

valeur du paramètre Γ qu’il se fixe.

Dans ce cas, la formulation mathématique de la version robuste associée à ce pro-

blème, noté T2rob(Γ), reste inchangée, à l’exception de la contraintem∑

i=1yi ≥ B qui doit

être remplacée par la contrainte :

m

∑i=1

yi ≥ B (4.19)

où B =n∑

j=1βj + ∑

j∈ Jβ j avec J l’ensemble d’indices des Γ plus grandes déviations.

Nous observons que dans ce cas, les valeurs de v∗(n), données par la proposition

4.1, ne peuvent plus être utilisées comme bornes pour les variables v dans la formu-

lation du problème de recours. En effet, à cause de la contrainte (4.19), la résolution

du problème Q′(yk, n), nécessaire à la détermination de ces bornes à l’étape 2 de

l’algorithme (voir la remarque 4.1), ne peut se faire, le problème étant désormais non

réalisable.

Nous pouvons néanmoins énoncer quelques résultats de tests expérimentaux réa-

lisés sur des petites tailles d’instances et cela en choisissant une valeur arbitrairement

grande pour M. Les résultats de l’algorithme de Kelley sont les suivants :

Tab. 4.3 – Temps de résolution et nombre d’itérations pour la résolution de T2rob(n/2)

n×m # iter. Temps (s)

20× 20 5.2 1.40

30× 30 14 134

35× 35 17.1 1363

40× 40 19 4215

Le tableau 4.3 montre les résultats d’exécution de l’algorithme de Kelley sur le

problème T2rob(n/2), où Γ = n/2 (représentant les instances les plus difficiles), et où

la borne M associée au problème de recours est de valeur arbitrairement grande. Nous

constatons que les temps de calcul explosent rapidement dès lors qu’on dépasse le

nombre de 30 demandes incertaines. Ce temps atteint plus d’une heure de calcul pour


une taille relativement faible de 40 demandes incertaines. Notons que des instances du

problème Trob(Γ) de taille similaire sont résolues en quelques secondes (voir le tableau

4.4 sur une instance où n = m = 35). Ces résultats montrent clairement la nécessité

de définir une borne adéquate et serrée pour améliorer les temps de résolution de

T2rob(Γ).

Tab. 4.4 – Test n = m = 35 : résolution de T2rob(Γ) vs Trob(Γ)

T2rob(Γ) Trob(Γ)Γ(%) # iter. Temps (s) # iter. Temps (s)

10 40 76.90 22 1.79

20 43 1606.34 14 1.27

30 30 8010.29 9 1.26

40 22 7703.9 12 1.63

50 34 4216.17 12 1.44

60 25 777.14 25 3.52

70 22 186.52 26 3.36

80 31 32.96 25 2.51

90 35 12.16 31 2.23

100 23 0.46 16 0.43

Enfin, la figure 4.5 illustre pour le test précédent deux courbes qui, en fonction de

Γ, représentent :

– la courbe A : l’écart en pourcentage entre l’optimum de T2rob(Γ) et celui de

Trob(Γ) (du premier contexte de décision),

– la courbe B : l’écart en pourcentage entre l’optimum de T2rob(Γ) et celui du

scénario de pire cas T2rob(n).

Nous observons tout d’abord que pour les deux courbes, cette différence est d’autant

plus grande que Γ est faible. Elle se situe pour la première courbe entre 0% et 10%, et est

environ 3 fois plus grande pour la seconde courbe. Il s’en suit qu’à défaut de pouvoir

résoudre T2rob(Γ) de manière rapide, nous pouvons résoudre Trob(Γ) qui fournit dans

tous les cas de meilleurs résultats que le scénario de pire cas.


0 1 0 2 0 3 0 4 0 5 0 6 0 7 0 8 0 9 0 1 0 00

5

1 0

1 5

2 0

2 5

3 0

Varia

tion r

elative

des c

outs

(%)

G a m m a ( % )

A B

Fig. 4.5 – Variation relative des coûts en fonction de Γ pour un test n = m = 35 : la courbe A représentela différence en pourcentage de v∗(Trob(Γ))−v∗(T2rob(Γ))

v∗(T2rob(Γ)) × 100 . La courbe B exprime la différence en

pourcentage de v∗(T2rob(n))−v∗(T2rob(Γ))v∗(T2rob(Γ)) × 100 .

Conclusion

Dans ce chapitre nous nous sommes intéressés à la résolution d’un problème de

localisation et de transport comprenant des demandes incertaines. Nous avons intégré

ces incertitudes dans une formulation robuste du problème.

Nous avons construit puis résolu la version robuste avec une approche bi-étapes

adaptée. Grâce à une propriété du problème de transport que nous avons démontrée,

nous avons pu définir des bornes serrées pour les constantes de la formulation en

programme linéaire mixte du problème de recours, qui représente l’étape la plus

difficile de l’algorithme de résolution.

À notre connaissance, nous proposons ici la première étude approfondie traitant de

la détermination de ces bornes, et nous montrons par de multiples tests expérimentaux

l’importance de telles bornes dans le calcul des solutions optimales, notamment pour

la résolution d’instances de grande taille. En effet, dans les travaux antérieurs (voir

par exemple Atamtürk et Zhang (2007), Thiele et al. (2009)) les instances résolues par

des approches similaires sont de plus faibles tailles, s’arrêtant à quelques dizaines de

coefficients incertains seulement.

Aussi, nous avons présenté un second contexte de décision pour le problème de

localisation et de transport à la fin de ce chapitre, pour lequel nous n’avons pu pour


le moment déterminer une borne spécifique. Cette étude restant une perspective d’un

travail futur.

Dans le dernier chapitre de cette thèse, nous nous intéressons à une autre applica-

tion qui concerne un problème de gestion de stock robuste admettant des demandes

incertaines, que nous traiterons selon plusieurs contextes de décision.

5Application : Problème de gestion

des stocks robuste

Sommaire

Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119

5.1 Définition du problème de gestion des stocks déterministe . . . . . 120

5.2 Formulation robuste 1 : solution robuste de pire cas . . . . . . . . . . 124

5.2.1 Modèle de pénalités . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124

5.2.2 Solution de pire cas paramétrique : approche de Bertsimas et Thiele . . 129

5.3 Formulation robuste 2 : pire optimum . . . . . . . . . . . . . . . . . . . . 135

5.4 Formulation robuste 3 : approche robuste bi-étapes . . . . . . . . . . . 139

Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141

Dans ce chapitre, nous présentons une seconde application de l’optimisation ro-

buste concernant un problème de gestion de stock avec demande incertaine. Ce

problème a été introduit lors de mon stage de Master. Les résultats que nous avions

obtenus n’avaient pas été concluants pour deux raisons principales : le manque de

résultats théoriques (que notre travail de thèse a maintenant comblé) et la mauvaise

identification de la préoccupation de robustesse vis-à-vis du contexte décisionnel. En

s’appuyant sur les résultats présentés dans les chapitres précédents, nous proposons

dans ce chapitre quatre formulations robustes pour ce problème, et cela suivant le

contexte de décision envisagé.

117

119

Introduction

Nous abordons dans le dernier chapitre de cette thèse une application d’un problème

de gestion de stock avec des demandes incertaines. Ce problème a été étudié lors de

mon stage de Master (voir Remli (2006)). Cependant, les résultats n’avaient été satis-

faisants. La mauvaise identification de la préoccupation de la robustesse du problème

(notamment le contexte de décision) en a été la cause principale. À ce jour, le contexte

décisionnel dans lequel s’inscrit ce problème incertain n’est pas clairement désigné et

c’est pour cette raison que nous allons envisager de le traiter selon trois contextes de

décision distincts. Chacun de ces contextes va mener à la formulation d’une version

robuste particulière du problème de gestion de stock.

Les travaux réalisés durant le stage de master ont constitué un point de départ à

nos recherches de thèse. En effet, les demandes incertaines du problème de gestion

de stock traité ici, apparaissent dans le second membre des contraintes d’égalité du

programme linéaire modélisant le problème. Ces recherches ont donc initié la réflexion

sur l’établissement d’approches robustes propres à des problèmes admettant des co-

efficients incertains, situés exclusivement sur le second membre des contraintes. Nous

allons, dans ce chapitre, exploiter les résultats des chapitres précédents pour prendre

en compte les incertitudes sur la demande du problème de gestion de stock considéré.

Nous proposons pour ce faire diverses versions robustes à adopter selon le contexte de

décision. Nous présenterons leurs différentes formulations ainsi que des extensions,

pouvant être menées dans des travaux futurs.

Ce chapitre se divise en quatre sections. Nous commencerons à la section 5.1 par

décrire le problème dans sa forme déterministe. Puis nous supposerons, à la section

5.2, que la demande est incertaine et nous nous attacherons à la détermination de

solutions robustes de pire cas. Le contexte de décision est alors celui d’un décideur

cherchant à définir un plan d’achat et de stockage sans connaître le niveau effectif de

la demande. Nous emploierons pour ce faire un modèle de pénalités adapté. Nous

calculerons, d’une part, les solutions robustes de pire cas, et d’autre part, les solutions

robustes selon l’approche de Bertsimas et Thiele (2006). À la section 5.3, nous nous

placerons dans un contexte décisionnel différent : le décideur définit un plan d’achat

et de stockage après que le niveau de la demande lui soit révélé. La politique optimale

est alors calculée en conséquence. Néanmoins, dans une phase de planification, nous

120 Chapitre 5. Problème de gestion des stocks robuste

proposerons d’évaluer les coûts engendrés par les différents scénarios de la demande

(notamment le pire scénario). Nous calculerons alors les valeurs du pire optimum et

le pire optimum paramétrique. Enfin, à la section 5.4, nous proposerons une version

robuste bi-étapes, dans un contexte se situant à mi-chemin entre les deux premiers,

où nous supposerons que le décideur connaît les demandes effectives sur un horizon

temporel proche et désire anticiper les décisions sur les demandes à venir, qu’il ne

connaît pas avec certitude.

5.1 Définition du problème de gestion des stocks déterministe

Pour des raisons de confidentialité, nous ne présentons ici qu’une version simplifiée

du problème abordé lors du stage de Master. Une version qui garde néanmoins toute

la complexité du problème, notamment pour les considérations de robustesse que

nous voulons aborder.

Soit le problème de gestion des stocks suivant : un plan d’achat et de stockage d’un

produit doit être décidé sur un horizon T. Les quantités achetées à chaque période t où

t = 1 . . . T, représentées par les variables ut, sont bornées par une quantité minimale à

acheter, notée U, et une quantité maximale U, avec 0 ≤ U < U. Ici, un contrat liant le

décideur à un fournisseur l’oblige à s’approvisionner dans une fourchette donnée. Le

niveau de stock à la fin de chaque période t, représenté par les variables xt, est aussi

borné par une quantité minimale X et une capacité maximale X, avec 0 ≤ X < X. Le

niveau de stock initial est connu et est égal à x0. Les demandes du client, notées dt,

doivent être satisfaites à chaque t, t = 1 . . . T. Pour ce faire, il est possible de réaliser un

achat, stocker ou déstocker du produit à tout instant t. Différents coûts sont considérés :

– les coûts d’achat du produit à chaque période t sont notés ct,

– les coûts relatifs au stockage ou au remplissage du stock à la période t, nommés

coût de stockage, sont notés cst,

– les coûts relatifs au déstockage ou au soutirage du stock à la période t, nommés

coût de déstockage, sont notés cdt. Notons que le maintien du produit en stock

n’engendre pas de coût.

L’objectif est de déterminer les quantités à acheter ut, à stocker st et à déstocker dst à

chaque période t dans l’horizon T tels que les coûts totaux soient minimum.

5.1. Définition du problème de gestion des stocks déterministe 121

Le problème de gestion de stock déterministe, noté (G), se formule comme le pro-

gramme linéaire suivant :

(G)

minT

∑t=1

ctut +T

∑t=1

cstst +T

∑t=1

cdtdst

s.c. ut + dst − st = dt t = 1 . . . T

xt = xt−1 + st − dst t = 1 . . . T

X ≤ xt ≤ X t = 1 . . . T

U ≤ ut ≤ U t = 1 . . . T

st, dst ≥ 0 t = 1 . . . T

(5.1)

(5.2)

(5.3)

(5.4)

où x0 ≥ X est fixé.

Les égalités (5.1) décrivent les contraintes de satisfaction des demandes à chaque

période t, pour t = 1 . . . T. Ces contraintes sont des égalités strictes et expriment le fait

que les situations de surplus de produit ou de rupture de stock ne sont pas tolérées.

Les contraintes (5.2) expriment quant à elles le niveau de stock de chaque période t.

Ce dernier est égal au niveau de stock de la période précédente (soit à t− 1) auquel

s’ajoute ou se retranche la quantité stockée ou déstockée à la période t (il est clair qu’à

l’optimum et pour chaque t, les deux variables st et dst ne peuvent être strictement

positives en même temps). De plus, le niveau de stock est contraint par les contraintes

(5.3) qui représentent les bornes de niveau à respecter. Enfin, les contraintes (5.4) sont

des bornes sur les quantités d’approvisionnement à chaque période t.

Nous nous intéressons, dans ce qui suit, à la prise en compte d’incertitudes sur

les demandes du problème (G). En effet, considérons que les demandes dt à chaque

période t = 1 . . . T soient incertaines et appartiennent respectivement aux intervalles

[dt − dt, dt + dt], où dt représente la valeur nominale de la demande et dt la déviation


maximale. Notons alors le problème incertain par (Gd) qui s’écrit comme suit :

(Gd)

minT

∑t=1

ctut +T

∑t=1

cstst +T

∑t=1

cdtdst

s.c. ut + dst − st = dt t = 1 . . . T

xt = xt−1 + st − dst t = 1 . . . T

X ≤ xt ≤ X t = 1 . . . T

U ≤ ut ≤ U t = 1 . . . T

st, dst ≥ 0 t = 1 . . . T

(5.5)

(5.6)

(5.7)

(5.8)

où dt appartient à [dt − dt, dt + dt], pour tout t = 1 . . . T.

Avant de construire les différentes versions robustes associées au problème (Gd),

simplifions ce dernier. Nous remarquons que ce problème admet 2T contraintes d’éga-

lité, dont T avec un second membre incertain. Étant donné que les contraintes (5.6)

ne contiennent aucun élément incertain, nous pouvons par exemple supprimer les va-

riables dst du problème (Gd). Nous obtenons alors le problème équivalent suivant :

(G′d)

minT

∑t=1

ctut +T

∑t=1

(cst + cdt)st + cd1x0+

T−1

∑t=1

(cdt+1 − cdt)xt − cdTxT

s.c. ut + xt−1 − xt = dt t = 1 . . . T

xt−1 − xt + st ≥ 0 t = 1 . . . T

X ≤ xt ≤ X t = 1 . . . T

U ≤ ut ≤ U t = 1 . . . T

st ≥ 0 t = 1 . . . T

(5.9)

Remarque 5.1 Il n’est pas pertinent de supprimer d’autres variables du problème (G′d) sur

la base des contraintes d’égalité (5.9) et cela car ces dernières admettent un second membre

incertain. En effet, si nous choisissons par exemple d’exprimer les variables ut de (G′d) en

5.1. Définition du problème de gestion des stocks déterministe 123

fonction des variables xt nous obtenons le problème suivant :

(G′′d)

min (cd1 − c1)x0 +T

∑t=1

(cst + cdt)st +T

∑t=1

cdtdt+

T−1

∑t=1

(cdt+1 − ct+1 − cdt + ct)xt + (cT − cdT)xT

s.c. xt−1 − xt + U ≥ dt t = 1 . . . T

xt−1 − xt + U ≤ dt t = 1 . . . T

xt−1 − xt + st ≥ 0 t = 1 . . . T

X ≤ xt ≤ X t = 1 . . . T

st ≥ 0 t = 1 . . . T

(5.10)

(5.11)

(5.12)

Or, étant donné que les demandes dt sont incertaines et interviennent dans la fonction objectif

(5.10) ainsi que dans les contraintes (5.11) et (5.12), alors dans toute version robuste du pro-

blème (G′′d) l’hypothèse selon laquelle tous les coefficients incertains doivent être indépendants

n’est plus respectée. Le problème (G′′d) n’est pas pertinent pour l’application de modèles de

robustesse présentés dans les chapitres précédents.

Dans ce qui suit, les versions robustes seront formulées à partir du problème (G′d).

Notons que la particularité de ce problème réside, d’une part, dans la définition des

incertitudes qui affectent une partie du second membre de contraintes d’égalité, et

d’autre part, dans le caractère dynamique de dépendance entre périodes dont il faut

tenir compte.

Nous considérons successivement trois contextes décisionnels :

– dans le premier contexte, qui est traité dans la section 5.2, il s’agit de définir un

plan d’achat et de stockage sans connaître le niveau réel de la demande. Des

solutions robustes dans un contexte statique sont recherchées.

– puis, dans la section 5.3, nous nous intéressons au contexte “opposé” dans lequel

la demande de chaque période est connue au moment de la prise de décision

concernant l’achat et le stockage. Nous cherchons alors à évaluer les coûts selon

différents scénarios en calculant la valeur du pire optimum,

– dans la dernière section, nous envisageons un contexte intermédiaire et plus

réaliste, où la demande est connue sur un horizon proche mais devient incertaine


au-delà. Notre objectif est alors de construire une version robuste bi-étapes qui

permet de répondre à cette problématique.

5.2 Formulation robuste 1 : solution robuste de pire cas

Nous considérons le contexte décisionnel suivant : le décideur ne connaît pas les

demandes effectives des clients et doit décider d’un plan d’achat et de stockage sur

“toutes” les périodes t = 1 . . . T. La décision doit être prise en présence d’incertitudes.

5.2.1 Modèle de pénalités

Dans ce contexte, la solution de pire cas s’impose comme une décision robuste qui,

adoptée par le décideur avant la réalisation des demandes, lui permet de se prémunir

contre tous les scénarios possibles, y compris le pire d’entre eux.

En rappelant que le problème (G′d) admet des incertitudes situées dans le second

membre des contraintes d’égalité (5.9), nous constatons que la solution de pire cas

n’existe pas (d’après le résultat de la section 2.1.2 du chapitre 2).

Or, dans le problème considéré, le décideur connaît les coûts de la violation des

contraintes d’égalité (5.9), et par conséquent, il devient possible de déterminer des

solutions de pire cas en employant un modèle de pénalités (comme cela a été présenté

dans la section 2.1.2). En effet, dans le cas de rupture de stock, l’achat de marchandise

supplémentaire peut se faire sur un marché extérieur, et dans le cas où le stock est

saturé, le stockage du surplus de marchandise est possible chez un concurrent. La

solution de pire cas est alors celle dont le coût total minimise les coûts d’achat, de

stockage et des différentes pénalités (correspondant à des surcoûts.)

Notons pt le coût unitaire de la pénalité engendrée par le surplus de marchandises

à la période t et qt le coût unitaire de la pénalité de rupture de stock. Ces pénalités sont

effectives sur les quantités en surplus ou en déficit à chaque période t, représentées par

les variables suivantes :

et = ut + xt−1 − xt − dt (5.13)

5.2. Formulation robuste 1 : solution robuste de pire cas 125

avec et ≥ 0 correspondant à un surstockage, et et ≤ 0 correspondant à une rupture de

stock.

Selon les résultats de la section 2.1.2, la solution robuste de pire cas s’obtient en résol-

vant le programme linéaire, noté (GRob1). En effet, il suffit de construire le problème

(Pbp)pirCas donné dans la section 2.1.2 dans lequel nous considérons bt = dt + dt et

bt = dt − dt. Le problème (GRob1) s’écrit alors :

(GRob1)

minT∑

t=1ctut +

T∑

t=1(cst + cdt)st + cd1x0+

T−1∑

t=1(cdt+1 − cdt)xt − cdTxT +

T∑

t=1yt

s.c. yt − ptut − ptxt−1 + ptxt ≥ −ptdt + ptdt t = 1 . . . T

yt + qtut + qtxt−1 − qtxt ≥ qtdt + qtdt t = 1 . . . T

xt−1 − xt + st ≥ 0 t = 1 . . . T

X ≤ xt ≤ X t = 1 . . . T

U ≤ ut ≤ U t = 1 . . . T

st, yt ≥ 0 t = 1 . . . T

avec x0 ≥ X donné.

Exemple 5.1 Soit (G1) le problème de gestion de stock défini sur un horizon T = 4. Les

différentes constantes du problème relatives aux coûts et aux demandes sont données par le

tableau 5.1 et le tableau 5.2 respectivement.

Tab. 5.1 – Les coûts du problème (G1)

t = 1 t = 2 t = 3 t = 4

ct 10 21 40 30

cst 5 6 7 8

cdt 4 3 2 1

Tab. 5.2 – Les demandes du problème (G1)

t = 1 t = 2 t = 3 t = 4

dt 30 40 35 20

dt 10 10 5 10


Les bornes sur les achats et le stockage sont les suivantes : U = 30, U = 100, X = 0, et

X = 180, et le stock initial est égal à x0 = 10.

Examinons tout d’abord la solution optimale du problème nominal où toutes les demandes sont

fixées aux valeurs nominales. Pour ce scénario la politique optimale d’achat et de stockage, notée

(unomt , snom

t , xnomt ), est reportée dans le tableau 5.3. Il s’agit d’acheter 35 unités à la première

période et de stocker 5 unités ; à la deuxième et troisième période, d’approvisionner 30 unités

aux deux périodes, et de déstocker 10 unités et 5 unités respectivement ; enfin, à la dernière

période d’acheter 30 unités et d’en stocker 10. Nous remarquons que pour cette solution un

stockage est réalisé à la première période (où le prix de stockage est le plus faible), alors que

la marchandise est déstockée sur les périodes 2 et 3. Par ailleurs, l’approvisionnement est au

minimum égal à 30 unités à chaque période, d’où le stock final égale à 10 unités. Enfin, le coût

total de cette politique est égal à 3225.

Tab. 5.3 – La solution nominale du problème (G1)

t = 1 t = 2 t = 3 t = 4

unomt 35 30 30 30

snomt 5 0 0 10

xnomt 15 5 0 10

Supposons à présent que les situations de rupture de stock ou de surplus soient envisageables

et cherchons la solution robuste de pire cas selon le modèle de pénalités. Nous considérons alors

que le décideur peut stocker l’excédent de produit au prix unitaire pt et acheter la quantité de

produit manquante au prix unitaire qt à chaque période t = 1 . . . 4. Ces pénalités sont reportées

dans le tableau 5.4.

Tab. 5.4 – Les valeurs des pénalités pt et qt relatives au problème (G1)

t = 1 t = 2 t = 3 t = 4

pt 200 100 50 70

qt 75 35 550 10

La politique optimale d’approvisionnement et de stockage selon le modèle de pénalités, notée

(upent , spen

t , xpent ), est reportée sur le tableau 5.5. Le décideur doit acheter 30 unités à toutes les


périodes. Il doit stocker 4.54 unités à la première période. À la deuxième et troisième période,

il doit déstocker 5.18 unités et 9.17 unités respectivement. À la dernière période, le stockage

est de 17.69 unités. Le coût de cette solution est nettement supérieur au coût de la solution

nominale (sans les pénalités) et est égal à 5469.38. En revanche, le coût de la solution nominale

suivant ce modèle de pénalités est de 9675 qui est largement supérieur à celui de la solution

(upent , spen

t , xpent ). Nous remarquons aussi que ces deux solutions sont très différentes. Ceci

s’explique par la disparité des coûts de surstockage ou de déficit de chaque période. En effet,

soit un second jeu de pénalités donné par des coûts de surplus p′t et des coûts de déficit q′t assez

proches pour t = 1 . . . T, comme reporté dans le tableau 5.6.

Tab. 5.5 – La solution de pire cas (upent , spen

t , xpent ) du problème (G1Rob1).

t = 1 t = 2 t = 3 t = 4

upent 30 30 30 30

spent 4.54 0 0 17.50

xpent 14.54 9.36 0.19 17.69

ypent 1100.91 518.52 458.33 175

Tab. 5.6 – Les valeurs des pénalités p′t et q′t relatives au problème (G1)

t = 1 t = 2 t = 3 t = 4

p′t 20 40 50 60

q′t 25 35 55 70

La politique optimale d’approvisionnement et de stockage pour ce second jeu de pénalités est

notée (upen′t , spen′

t , xpen′t ) et est reportée dans le tableau 5.7. Le décideur doit dans ce cas acheter

35.68 unités à la première période, et stocker 4.57 unités. À la deuxième et troisième période, la

quantité à acheter est de 30 unités chacune, et celle déstockée est de 9.33 unités et 5.24 unités

respectivement. À la dernière période, l’approvisionnement est de 30 unités et le stockage de

9.23 unités. Le coût de cette solution est égal à 4725.62.

Nous observons que la solution de pire cas (upen′t , spen′

t , xpen′t ) ne diffère que légèrement de

la solution nominale (unomt , snom

t , xnomt ) (le coût de la solution nominale pour ce modèle de

pénalités est proche de celui de la solution de pire cas et est ici égal à 4850). Ceci rejoint la

remarque faite dans l’exemple 2.2 du chapitre 2, dans laquelle nous avions observé que pour des


Tab. 5.7 – La solution de pire cas (upen′t , spen′

t , xpen′t , ypen′

t ) du problème (G1Rob1).

t = 1 t = 2 t = 3 t = 4

upen′t 35.68 30 30 30

spen′t 4.57 0 0 9.23

xpen′t 14.57 5.24 0 9.23

ypen′t 222.22 373.33 261.90 646.15

valeurs de pénalités proches et élevées (par rapport aux autres coûts du problème), la solution de

pire cas selon le modèle de pénalités se rapprochait de la solution optimale selon le scénario no-

minal. Ceci s’explique par le modèle même de pénalités, où les coûts des pénalités imposées pour

limiter la non satisfaction de contraintes d’égalité sont les plus faibles quand les coûts de sursto-

ckage et de déficit s’équilibrent, donnant lieu à un scénario médian, proche du scénario nominal.

De plus, nous remarquons que les valeurs des variables ypent , tout comme celles de ypen′

t ,

sont strictement positives pour tout t. En effet, selon le contexte de décision considéré ici, où

le décideur souhaite adopter une politique d’achat et de stockage avant la connaissance des

demandes, les situations de rupture de stock ou de surplus de produit ne peuvent être évitées.

Enfin, il est possible à partir de la solution (upent , spen

t , xpent ) (respectivement

(upen′t , spen′

t , xpen′t )) et en utilisant les contraintes (5.1), de calculer le scénario de de-

mande correspondant à ces deux solutions de pire cas. Le scénario, noté dpen (respectivement

dpen′), correspond aux demandes dpen = (25.45, 35.18, 39.17, 12.50) (respectivement

dpen′ = (33.11, 39.33, 35.24, 20.77)). Nous observons qu’étant donné les pénalités appliquées

dans les deux situations de surplus de produit et de rupture de stock et pour la même raison

évoquée auparavant, alors le scénario de demande engendré n’est pas un scénario extrême.

Dans la section suivante, nous restons dans le même contexte décisionnel, dans

lequel la décision doit être prise avant la réalisation de l’incertitude, et nous voulons

construire une version robuste au problème de gestion de stock selon une approche

qui permet de nuancer le caractère extrême de la solution de pire cas. Pour ce faire,

nous suivrons l’approche de Bertsimas et Thiele (2006) qui n’est autre que l’adaptation

de l’approche de Bertsimas et Sim (2004) (présentée à la section 1.2.3) au problème de


gestion de stock. Nous présenterons dans ce qui suit la formulation robuste qui intègre

des pénalités adéquates ainsi que les budgets d’incertitudes sur la demande.

5.2.2 Solution de pire cas paramétrique : approche de Bertsimas et Thiele

Afin de décider d’une solution robuste, non plus sur un scénario unique, celui de

pire cas, mais sur un ensemble de scénarios délimité par un budget d’incertitude,

Bertsimas et Thiele (2006) ont proposé une approche dérivée de celle de Bertsimas

et Sim (présentée à la section 1.2.3 du premier chapitre) pour traiter un problème

similaire de gestion de stock.

Pour rappel, cette approche vise la détermination de solutions robustes moins

conservatives que la solution de pire cas et ceci en autorisant une faible violation des

contraintes. Elle est appliquée sur des programmes linéaires admettant une matrice

des contraintes incertaine et nécessite la définition d’un budget d’incertitude pour

chacune des contraintes.

Afin de construire la version robuste du problème incertain (G′d) selon cette ap-

proche, nous réécrivons ce dernier de manière appropriée. Pour ce faire, nous expri-

mons tout d’abord les contraintes (5.9) de manière équivalente comme suit :

x0 − xt +t

∑i=1

ui =t

∑i=1

di, t = 1 . . . T (5.14)

Ensuite, nous appliquons le modèle de pénalités présenté à la section précédente

avec :

et = x0 − xt +t

∑i=1

ui −t

∑i=1

di, t = 1 . . . T (5.15)

où et ≥ 0 correspondant à un surstockage, et et ≤ 0 correspondant à une rupture de

stock.


Le nouveau problème incertain, noté (GSd), s’écrit alors :

(GSd)

minT

∑t=1

ctut +T

∑t=1


T−1

∑t=1

(cdt+1 − cdt)xt − cdTxT +T

∑t=1

yt

s.c. yt ≥ pt(x0 − xt +t

∑i=1

ui −t

∑i=1

di) t = 1 . . . T

yt ≥ qt(xt − x0 −t

∑i=1

ui +t

∑i=1

di) t = 1 . . . T

xt−1 − xt + st ≥ 0 t = 1 . . . T

X ≤ xt ≤ X t = 1 . . . T

U ≤ ut ≤ U t = 1 . . . T

st, yt ≥ 0 t = 1 . . . T

(5.16)

(5.17)

Le problème (GSd) est un programme linéaire dans lequel les éléments incertains

sont situés dans les contraintes (5.16) et (5.17). Afin d’en tenir compte et de formuler la

version robuste selon l’approche de Bertsimas et Thiele (2006), nous introduisons les

paramètres Γt (non nécessairement entiers) qui représentent le budget d’incertitude

autorisé à la teme période. Le modèle d’incertitude considéré ici est un modèle en ligne,

où pour chacune des 2T contraintes incertaines (5.16) et (5.17), un vecteur Γt de taille t

est fixé par le décideur.


La formulation robuste, notée GSRob(Γ), s’écrit alors :

GSRob(Γ)

minT∑

t=1ctut +

T∑

t=1(cst + cdt)st + cd1x0 +

T−1∑

t=1(cdt+1 − cdt)xt−

cdTxT +T∑

t=1yt

s.c. yt − pt(x0 − xt +t

∑i=1

ui −t

∑i=1

di + maxt

∑i=1

zi≤Γt

0≤zi≤1, i=1...t

t

∑i=1

dizi) ≥ 0 t = 1 . . . T

yt − qt(−x0 + xt −t

∑i=1

ui +t

∑i=1

di + maxt

∑i=1

zi≤Γt

0≤zi≤1, i=1...t

t

∑i=1

dizi) ≥ 0 t = 1 . . . T

xt−1 − xt + st ≥ 0 t = 1 . . . T

X ≤ xt ≤ X t = 1 . . . T

U ≤ ut ≤ U t = 1 . . . T

st, yt ≥ 0 t = 1 . . . T

Linéarisons le problème GSRob(Γ). Notons (At) les problèmes auxiliaires qui

s’écrivent :

(At)

max

t∑

i=1dizi

s.c.t

∑i=1

zi ≤ Γt

0 ≤ zi ≤ 1 i = 1 . . . t

En utilisant le théorème fort de dualité, les problèmes (At) sont alors remplacés par

leurs duaux :

(DAt)

min Γtgt +

t∑

i=1rit

s.c. gt + rit ≥ di i = 1 . . . t

gt, rit ≥ 0 i = 1 . . . t


Nous obtenons le programme linéaire suivant :

GSRob(Γ)

minT∑

t=1ctut +

T∑

t=1(cst + cdt)st + cd1x0+

T−1∑

t=1(cdt+1 − cdt)xt − cdTxT +

T∑

t=1yt

s.c. yt − pt(t

∑i=1

ui + Γtgt +t

∑i=1

rit − xt) ≥ pt(x0 −t

∑i=1

di) t = 1 . . . T

yt − qt(xt −t

∑i=1

ui + Γtgt +t

∑i=1

rit) ≥ qt(t

∑i=1

di − x0) t = 1 . . . T

xt−1 − xt + st ≥ 0 t = 1 . . . T

gt + rit ≥ di i = 1 . . . t, t = 1 . . . T

X ≤ xt ≤ X t = 1 . . . T

U ≤ ut ≤ U t = 1 . . . T

st, yt, gt, rit ≥ 0 i = 1 . . . t, t = 1 . . . T

Nous pointons, dans ce qui suit, les avantages et les limites de cette formulation

pour répondre à la préoccupation de la robustesse du problème posé :

1. Tout d’abord, le point fort de cette approche est qu’elle garde la linéarité du

problème dans cette version robuste. De plus, sa valeur représente une ap-

proximation linéaire par excès de la valeur du pire cas pour différents budgets

d’incertitudes.

2. Par contre, se pose le problème de la définition du budget d’incertitude pour

chacune des périodes t, t = 1 . . . t. En effet, si la définition du budget total

ΓT sur tout l’horizon T est facilement appréhendé par le décideur, la question

du choix des valeurs intermédiaires Γt pour chacune des périodes t reste pro-

blématique ? Il est clair que pour tout t, t = 1 . . . T nous avons les inégalités

Γt ≤ Γt+1 ≤ Γt + 1. Le décideur peut alors choisir le scénario (valeurs de Γt)

qui lui convient en respectant ces inégalités. Par exemple, soit un problème de

gestion de stock incertain défini sur un horizon T = 4. Si ΓT = 3, alors les

vecteurs suivants de Γ sont possibles : (1, 2, 3, 3), (0, 1, 2, 3), (0.5, 1.5, 2, 3),. . ..

Notons alors qu’en fixant les valeurs de Γt pour tout t, la flexibilité et la liberté

qu’offre l’approche de Bertsimas et Sim se verra lésée par la définition même

de ce scénario. En effet, l’attrait principal de cette approche est de permettre

aux coefficients de chaque contrainte de dévier des valeurs nominales, tant que

cela reste dans le budget considéré pour cette contrainte. Cette latitude n’est


plus effective dans GSRob(Γ) si l’on doit fixer pour chaque période t un budget

d’incertitude. Une façon de contourner cette restriction est de poser une valeur

unique de budget ΓT = Γt = Γ pour toutes les périodes (voir Solyali et al. (2010)).

Nous rappelons par ailleurs, que dans les travaux de Bertsimas et Thiele (2006),

les budgets d’incertitude ne sont pas fournis par le décideur mais sont calculés

en fonction de la probabilité de violation des contraintes autorisée (voir la section

1.2.3).

3. Par ailleurs, nous constatons que les budgets d’incertitude sont surévalués. Illus-

trons cela par l’exemple suivant : reprenons l’exemple précédent défini sur un

horizon T = 4 et examinons les problèmes auxiliaires engendrés par les dévia-

tions suivantes : d1 = 1, d2 = 3, d3 = 2, d4 = 2 où les budgets d’incertitude sont

fixés à Γ1 = Γ2 = Γ3 = Γ4 = 2. Les problèmes auxiliaires (A2) et (A3) associés

respectivement aux périodes t = 2 et t = 3 s’écrivent alors :

(A2)

max d1z1 + d2z2

s.c. z1 + z2 ≤ Γ2

z1 ≤ 1

z2 ≤ 1

z1, z2 ≥ 0

et

(A3)

max d1z1 + d2z2 + d3z3

s.c. z1 + z2 + z3 ≤ Γ3

z1 ≤ 1

z2 ≤ 1

z3 ≤ 1

z1, z2, z3 ≥ 0

À l’optimum, les solutions optimales des problèmes (A2) et (A3) sont respec-

tivement (1, 1) et (0, 1, 1). Nous constatons que la valeur de z∗1 diffère dans

les deux problèmes ! L’un considère que la demande à la première période est

à son maximum, et l’autre considère qu’elle reste égale à la valeur nominale.

Quelle valeur de z∗1 doit-on considérer ? En fait, la formulation robuste GSRob(Γ)

considère les deux cas de figure et est par conséquent sur-conservative.


4. Le dernier point que nous voulons montrer réside dans l’emploi de la dualité

dans cette formulation. En effet, reprenons l’exemple précédent et écrivons les

problèmes duaux associés à (A2) et (A3) comme suit :

(DA2)

min Γ2g2 + r12 + r22

s.c. g2 + r12 ≥ d1

g2 + r22 ≥ d2

g2, r12, r22 ≥ 0

et

(DA3)

min Γ3g3 + r13 + r23 + r33

s.c. g3 + r13 ≥ d1

g3 + r23 ≥ d2

g3 + r33 ≥ d3

g3, r13, r23, r33 ≥ 0

Nous remarquons que les variables z1 et z2 sont présentes dans les deux pro-

blèmes (A2) et (A3), alors que les deux problèmes duaux (DA2) et (DA3) sont

sous cette formulation complètement indépendants ! La version robuste GSRob(Γ)

ne correspond pas au problème recherché, elle surévalue et contraint le problème.

En fait, les problèmes (DAt) sont plutôt les duaux des problèmes auxiliaires où

les variables de chaque période t sont indépendantes. Ils s’écrivent :

(A′t)

max

t∑

i=1dizt

i

s.c.t

∑i=1

zti ≤ Γt

0 ≤ zti ≤ 1 i = 1 . . . t

Dans ce cas, nous rejoignons la remarque précédente et constatons que les bud-

gets d’incertitude sur-évaluent le pire cas et cumulent les déviations de toutes les

périodes.

La version robuste GSRob(Γ) du problème de gestion de stock est par conséquent

trop conservative. La raison principale réside dans le caractère dynamique du pro-

blème (G′d), pour lequel le modèle d’incertitude considérant un budget en ligne n’est

pas adapté et cache implicitement une dépendance entre les contraintes. Un modèle

en colonne serait plus adapté, comme nous le montrerons dans les sections suivantes.

5.3. Formulation robuste 2 : pire optimum 135

Exemple 5.2 Reprenons l’exemple 5.1 et calculons les solutions robustes suivant le mo-

dèle employé ci-avant. Nous prenons des valeurs de Γt toutes égales pour les périodes t, que

nous faisons varier entre 0 et 4. Nous utilisons par ailleurs les pénalités du tableau 5.6. Le

tableau 5.8 présente les valeurs de l’optimum du problème robuste GS1Rob(Γ) en fonction de Γt.

Tab. 5.8 – La valeur du pire optimum de GS1Rob(Γ) et le scénario de demande en fonction de Γ.

Γt = 0 Γt = 1 Γt = 2 Γt = 3 Γt = 4

v∗(GS1Rob(Γ)) 3225 4986.71 6535.09 7442.95 7762.95

Nous remarquons que pour Γt = 0 pour tout t = 1 . . . 4, la valeur de l’optimum de GS1Rob(Γ)

correspond à la valeur de l’optimum du problème nominal (voir l’exemple 5.1). Nous observons

cependant que pour les autres valeurs de Γt le coût est croissant quand Γt augmente et dépasse

largement le coût engendré par la solution de pire cas selon le modèle de pénalités (G1Rob1)

(voir l’exemple 5.1). Ceci confirme que ce modèle est très conservateur. Les pénalités sont

cumulées plusieurs fois.

Nous avons montré dans cette section que selon ce contexte, le décideur peut

envisager un plan d’achat et de stockage avant la divulgation des demandes et cela en

rendant possible (et moyennant de fortes pénalités) les situations de rupture de stock

ou de surplus de produit. Nous envisageons dans la section suivante, un contexte

décisionnel totalement opposé : le décideur attend que la demande soit révélée pour

décider des quantités à acheter et à stocker.

5.3 Formulation robuste 2 : pire optimum

Dans cette section, nous considérons le contexte décisionnel suivant : nous supposons

que le décideur connaît la demande au début de chaque période t et peut décider

en conséquence de la politique optimale d’achat et de stockage. Toutes les données

du problème sont alors certaines au moment de la prise de décision. La recherche

d’une solution robuste de pire cas n’a pas lieu d’être. Néanmoins, dans une phase

de planification, le décideur peut vouloir anticiper les coûts d’achat et de stockage et

identifier les scénarios de la demande les plus défavorables dans un horizon T qu’il


se fixe. Pour cela, nous proposons de calculer la valeur d’un pire optimum ou plus

généralement le pire optimum paramétrique.

Pour ce faire, nous considérons un budget d’incertitude Γ représentant le nombre de

périodes où la demande dévie des valeurs nominales sur l’horizon T. Ce paramètre est

défini sur le second membre des contraintes d’égalité (5.9) et est unique et commun à

toutes les demandes (il s’agit d’un modèle en colonne).

Selon la formulation de la section 3.2 du chapitre 3, nous calculons la valeur d’un pire

optimum du problème (G′d) que nous paramétrisons par la valeur de Γ. Ce dernier

est un entier appartenant à l’intervalle [0, T]. Pour les valeurs extrêmes de Γ = 0

(respectivement Γ = T), le problème correspond au problème nominal (respectivement

au pire optimum).

Le problème de pire optimum paramétrique, noté GRob2(Γ), se formule de la manière

suivante :

GRob2(Γ)

maxd∈UG(Γ)

min v∗(G′d)

où

UG(Γ) = d ∈ RT : dt = dt + dtz+t − dtz−t ; z+

t , z−t ∈ ZG(Γ) (5.18)

et

ZG(Γ) = z ∈ R2T :T

∑t=1

(z+t + z−t ) ≤ Γ, z+

t + z−t ≤ 1, z+t , z−t ∈ 0, 1 (5.19)

Ce qui revient à résoudre :

GRob2(Γ)

maxT∑

t=1(z+

t +z−t )≤Γ

z+t +z−t ≤1, t=1...T

z+t , z−t ∈0,1, t=1...T

minut+xt−1−xt=dt+z+

t dt−z−t dt , t=1...T

xt−1−xt+st≥0, t=1...T

X≤xt≤X, t=1...T

U≤ut≤U, t=1...T

st≥0, t=1...T

T∑

t=1ctut +

T∑

t=1(cst + cdt)st+

cd1x0 +T−1∑

t=1(cdt+1−

cdt)xt − cdTxT

Simplifions et linéarisons le problème GRob2(Γ). Tout d’abord, nous employons le théo-

5.3. Formulation robuste 2 : pire optimum 137

rème fort de dualité et nous obtenons le problème quadratique, noté GD(Γ), qui s’écrit :

GD(Γ)

cd1x0 + max (d1 − x0)α1 +T∑

t=2dtαt − x0µ1 − X

T∑

t=1βt + X

T∑

t=1γt−

UT∑

t=1δt + U

T∑

t=1θt +

T∑

t=1dtαtz+

t −T∑

t=1dtαtz−t

s.c. αt − δt + θt = ct t = 1 . . . T

µt ≤ cst + cdt t = 1 . . . T

αt+1 − αt − βt + µt+1 − µt + γt = cdt+1 − cdt t = 1 . . . T − 1

−αT − βT − µT + γT = −cdTT∑

t=1(z+

t + z−t ) ≤ Γ

z+t + z−t ≤ 1 t = 1 . . . T

z+t , z−t ∈ 0, 1 t = 1 . . . T

βt, δt, γt, θt, µt ≥ 0 t = 1 . . . T

Ensuite, le problème GD(Γ) peut être linéarisé (comme montré dans la section 3.2)

en remplaçant les produits de variables αtz+t (respectivement αtz−t ) par les variables

ω+t (respectivement ω−t ) et en ajoutant les contraintes adéquates. Le problème robuste

devient le programme linéaire mixte suivant :

GD′(Γ)

cd1x0 + max (d1 − x0)α1 +T∑

t=2dtαt − x0µ1 − X

T∑

t=1βt + X

T∑

t=1γt−

UT∑

t=1δt + U

T∑

t=1θt +

T∑

t=1dtω

+t −

T∑

t=1dtω

−t

s.c. αt − δt + θt = ct t = 1 . . . T

µt ≤ cst + cdt t = 1 . . . T

αt+1 − αt − βt + µt+1 − µt + γt = cdt+1 − cdt t = 1 . . . T − 1

−αT − βT − µT + γT = −cdTT∑

t=1(z+

t + z−t ) ≤ Γ

z+t + z−t ≤ 1 t = 1 . . . T

−Mz+t ≤ ω+

t ≤ Mz+t t = 1 . . . T

αt −M(1− z+t ) ≤ ω+

t ≤ αt + M(1− z+t ) t = 1 . . . T

−Mz−t ≤ ω−t ≤ Mz−t t = 1 . . . T

αt −M(1− z−t ) ≤ ω−t ≤ αt + M(1− z−t ) t = 1 . . . T

z+t , z−t ∈ 0, 1 t = 1 . . . T

βt, δt, γt, θt, µt ≥ 0 t = 1 . . . T


où M est une constante de grande taille représentant des bornes pour les variables αt

qui sont à définir. Notons que pour pouvoir résoudre des instances de taille même

raisonnable, il faut déterminer des bornes serrées pour ces variables.

Remarque 5.2 Il est possible d’apporter quelques améliorations au calcul du pire optimum

paramétrique. En effet, selon la formulation de GD′(Γ), rien n’exclut qu’un pire scénario soit

donné, par exemple, par une demande très faible à la période t, une demande très élevée à t + 1,

puis de nouveau une demande très faible à période t + 2. Cette situation est peu vraisemblable

dans la réalité, où nous pouvons supposer que pour des périodes proches la demande va évoluer

dans la même sens. Cette considération peut alors être modélisée dans GD′(Γ), en posant les

dépendances adéquates entre les variables z+t et z−t .

Exemple 5.3 Reprenons le problème (G1) de l’exemple 5.1 et calculons le pire optimum para-

métrique en fonction des valeurs de Γ. Pour ce faire, nous résolvons le programme linéaire mixte

dans lequel nous avons posé une valeur arbitrairement grande pour la constante M. Le tableau

5.9 fournit les valeurs du pire optimum ainsi que le scénario de demande correspondant, noté

dt, et cela en fonction du budget d’incertitude Γ.

Tab. 5.9 – La valeur du pire optimum de G1Rob2(Γ) et le scénario de demande en fonction de Γ.

Γ = 0 Γ = 1 Γ = 2 Γ = 3 Γ = 4

v∗(G1Rob2(Γ)) 3225 3405 3505 3590 3670

d1 30 = d1 30 40 40 40d2 40 = d2 50 50 50 50d3 35 = d3 35 35 40 40d4 20 = d4 20 20 20 10

Quand Γ = 0, le scénario de la demande correspond au scénario nominal, dont la solution est

donnée dans le tableau 5.3 (voir l’exemple 5.1).

Nous déterminons pour Γ = 4 le pire scénario de la demande. La valeur de l’optimum pour le

problème (G1) est égale à 3670.

Nous remarquons que ce scénario ne correspond pas au scénario où les demandes sont toutes les

5.4. Formulation robuste 3 : approche robuste bi-étapes 139

plus grandes. Ceci s’explique par le fait que les incertitudes sont situées dans le second membre

des contraintes d’égalité du problème. Le pire optimum est alors engendré par le scénario

constitué, soit par de fortes demandes et donc par des quantités achetées et stockées élevées, ou

bien par de faibles demandes où le décideur est contraint d’acheter des quantités minimales à

chaque période.

Selon l’approche présentée dans cette section, le décideur est capable d’identifer,

dans une phase de planification, les scénarios de demandes les plus défavorables et

leur coût. Ainsi, il peut prévoir son budget en conséquence. Cependant, il ne peut

décider avant la réalisation des demandes. Dans ce sens, la solution calculée n’est pas

robuste puisque non réalisable pour d’autres valeurs de Γ. Dans la section suivante,

nous exposons une approche qui se situe dans un contexte à mi chemin entre les deux

contextes précédemment présentés : nous supposons qu’au moment de la prise de

décision, les demandes sur de proches périodes sont connues et deviennent incertaines

au-delà.

5.4 Formulation robuste 3 : approche robuste bi-étapes

Dans cette dernière section, nous exposons une formulation robuste bi-étapes pour

traiter le problème incertain (G′d) que nous plaçons dans le contexte (plus proche de

la réalité) qui suit : nous supposons que les demandes effectives qui s’exercent sur

un horizon proche sont connues et qu’elles deviennent incertaines sur les périodes

suivantes. Le décideur souhaite dans ce contexte emprunter un plan d’achat et de

stockage durant les périodes où les demandes sont connues, tel qu’il s’assure de

l’existence d’un recours sur les périodes restantes quand la demande se réalisera.

Dans ce cas, nous séparons l’horizon T en deux parties telles que :

– les demandes entre 1 et t sont connues et sont égales aux valeurs nominales dt,

– les demandes entre t + 1 et T sont incertaines et varient dans les intervalles [dt −dt, dt + dt].

La version robuste bi-étapes consiste à décider des variables de première étape qui

sont les achats et le stockage entre la période 1 et t (avant la réalisation des demandes)

tel qu’il existe un recours à adopter à la seconde étape (quand les demandes seront


connues) d’approvisionnement et de stockage entre les périodes t + 1 et T.

Le problème bi-étapes s’écrit comme suit :

GRob3(Γ)

mint

∑t=1

ctut +t

∑t=1


t−1∑

t=1(cdt+1 − cdt)xt − cdtxt + v∗(R(x, Γ))

s.c. ut + xt−1 − xt = dt t = 1 . . . t

xt−1 − xt + st ≥ 0 t = 1 . . . t

X ≤ xt ≤ X t = 1 . . . t

U ≤ ut ≤ U t = 1 . . . t

st ≥ 0 t = 1 . . . t

où v∗(R(x, Γ)) représente la valeur du problème de recours, noté R(x, Γ), suivant :

R(x, Γ)

maxT∑

t=t+1(z+

t +z−t )≤Γ

z+t +z−t ≤1, t=t+1...T

z+t , z−t ∈0,1, t=t+1...T

minut+xt−1−xt=dt+dtz+

t −dtz−t , t=1+t...T

xt−1−xt+st≥0, t=t+1...T

X≤xt≤X, t=t+1...T

U≤ut≤U, t=t+1...T

st≥0, t=t+1...T

cdt+1xt +T−1∑

t=t+1(cdt+1−

cdt)xt +T∑

t=t+1ctut+

T∑

t=t+1(cst + cdt)st − cdTxT

Pour un vecteur de stock x donné sur les périodes t ∈ [1, t] et une valeur du budget

d’incertitude Γ fixé dans [0, T − t], le problème R(x, Γ) correspond au calcul d’un pire

optimum sur les périodes entre t + 1 et T.

Nous laissons la résolution du problème GRob3(Γ) comme perspective. Dans un

premier temps, une étape de réécriture et de simplification du problème est nécessaire.

Dans un second temps, un algorithme de résolution efficace doit être développé,

passant notamment par la définition de bornes appropriées pour la résolution exacte

du problème de recours.

Il serait par ailleurs intéressant d’étudier une version robuste non pas bi-étapes

mais multi-étapes de notre problème (de manière dynamique pour chaque période

t = 1 . . . T) et cela en s’appuyant sur les travaux de Minoux (2008). L’auteur propose

en effet dans cette étude une version robuste multi-étapes d’un problème de gestion

de stock particulier où la demande ainsi que les prix de vente du produit de chaque

période sont sujets à incertitude. L’originalité de cette étude est, d’une part, la prise

5.4. Formulation robuste 3 : approche robuste bi-étapes 141

en compte dans le modèle d’incertitude de la corrélation qui peut exister entre ces

deux type d’incertitude et construisant ainsi un modèle plus riche et plus proche de

la réalité et, d’autre part, la formulation robuste multi-étapes du problème qui repose

sur la résolution d’un système récursif explorant un arbre de scénarios.

Conclusion

Dans ce dernier chapitre, nous nous sommes intéressés à un problème de gestion de

stock admettant des demandes incertaines, pour lequel nous avons exploré quatre

versions robustes, à adopter selon le contexte de décision.

Nous avons ainsi donné les différentes formulations robustes et ouvert plusieurs

perspectives de développement notamment pour la résolution efficace de ces pro-

blèmes. Citons par exemple, le calcul de bornes serrées pour les constantes du

problème du calcul du pire optimum, ou encore, un algorithme de résolution de

la formulation robuste bi-étapes. Des tests numériques restent aussi à mener pour

étudier les tailles d’instances des problèmes pouvant être résolues.

Par ailleurs, nous avons montré que le caractère dynamique du problème jouait

un rôle important lors de la construction des problèmes robustes et qu’un modèle

d’incertitude en ligne n’était pas pertinent pour le problème de gestion de stock.

Il apparaît enfin que l’identification du contexte de décision constitue une compo-

sante importante de la problématique de la robustesse. En effet, nous observons que

les formulations robustes diffèrent selon le contexte décisionnel. Ce dernier n’est pas

toujours aisément identifié. À titre d’exemple, nous rappelons que le contexte réel dans

lequel se situait le problème de gestion de stock traité dans Remli (2006) n’a pas été

clairement identifié. De plus, des trois contextes de décision présentés dans ce cha-

pitre, un autre contexte de décision pourrait être envisagé, dans lequel une seconde

approche bi-étapes serait employée. Elle consisterait à déterminer les bornes sur les

achats et le stockage dans une première étape, tel qu’il existe un recours sur l’ap-

provisionnement et le stockage à la seconde étape. Cette formulation robuste est une

perspective intéressante d’un travail futur.

Conclusion générale

De manière générale, l’étude de la robustesse pour des problèmes d’optimisation

permet la prise en compte d’incertitudes affectant certains de leurs coefficients. Elle

est employée pour décider en milieu incertain de manière statique ou en multi-étapes,

ou encore en phase de planification.

Tout au long de ce travail de thèse, nous nous sommes intéressés aux programmes

linéaires contenant des incertitudes situées dans le second membre des contraintes.

Après avoir fait, au premier chapitre, un tour d’horizon des principales études biblio-

graphiques concernant les versions robustes de problèmes de programmation linéaire

incertains, nous avons dans le deuxième chapitre introduit notre problématique et

réalisé notre étude selon deux contextes décisionnels différents :

– le premier contexte est le contexte classique de décision, où l’on doit décider

avant la réalisation des incertitudes. Nous avons dans ce cas cherché à détermi-

ner des solutions robustes de pire cas au problème incertain considéré. Nous

avons montré que si ce dernier comportait des contraintes d’inégalité seulement,

alors la solution robuste s’obtenait par la résolution du programme linéaire avec

le plus petit domaine de solutions réalisables (le problème est de complexité po-

lynomiale). En revanche, lorsque le problème contient des contraintes d’égalité,

la recherche d’une solution qui permet de se prémunir contre toute éventualité

n’a plus de sens. Nous avons alors proposé pour ces problèmes un modèle de

pénalités permettant de mesurer la non satisfaction des contraintes d’égalité.

De cette manière, une décision de pire cas peut être envisagée, minimisant les

surcoûts engendrés.

– le second contexte est un contexte de planification, où l’objectif est l’évaluation

des solutions optimales suivant les scénarios possibles. Nous avons alors cherché

à déterminer l’intervalle de variation de l’optimum en fonction des incertitudes

143

144 Conclusion générale

et cela en calculant les deux valeurs extrêmes du pire optimum et du meilleur

optimum. Ici aussi, quand le problème incertain comporte des contraintes d’in-

égalité, le pire et le meilleur optima sont des problèmes polynomiaux (corres-

pondant respectivement aux programmes linéaires définis sur le plus petit et le

plus grand domaine de solutions réalisables). Quand le problème contient des

contraintes d’égalité, le calcul du meilleur optimum reste un problème polyno-

mial, alors que nous avons montré que le calcul du pire optimum est un problème

NP-difficile.

L’évaluation du pire optimum étant réalisée suivant le pire scénario (un scénario

peu réaliste et trop conservateur pour certaines situations), nous nous sommes attelé,

au troisième chapitre, à proposer un calcul de la valeur de l’optimum en se basant sur

d’autres scénarios. Pour cela, nous avons étendu l’approche de Bertsimas et Sim (2004)

en paramétrisant le calcul du pire optimum par un budget d’incertitude commun à

tous les coefficients du second membre. Nous avons montré dans cette étude que les

problèmes engendrés par la considération de budgets d’incertitude en colonne était

bien plus difficiles que ceux engendrés par des budgets d’incertitude en ligne. En effet,

le problème du calcul du pire optimum paramétrique est un problème bilinéaire dans

sa forme générale. Nous avons en outre proposé une linéarisation en un programme

linéaire mixte.

Au chapitre 4, nous avons considéré un troisième contexte décisionnel : le contexte

multi-étapes, et nous nous sommes intéressés à une application du problème de lo-

calisation et de transport avec demandes incertaines. Nous avons formulé puis résolu

la version robuste bi-étapes associée à ces applications en utilisant un algorithme de

génération de contraintes adapté. De plus, les résultats expérimentaux réalisés sur ce

problème montrent que la borne que nous avons établie au problème de transport

permet la résolution d’instances de grande taille.

Le dernier chapitre de cette thèse traite d’une autre application, celle d’un pro-

blème de gestion de stock avec demande incertaine. Nous avons construit plusieurs

versions robustes à ce problème et cela suivant les trois contextes de décision définis

précédemment. Nous avons montré qu’elle a été l’influence sur les versions robustes

du caractère dynamique du problème et expliqué en quoi le modèle d’incertitude en

colonne était mieux adapté que le modèle d’incertitude en ligne.

Conclusion générale 145

Dans la continuité directe de notre travail de thèse, nous envisageons de :

– définir un algorithme de résolution adapté au problème bilinéaire engendré par

le calcul du pire optimum paramétrique pour le problème incertain (Pb) (pour

les deux cas de figure où le problème contient des contraintes d’inégalité ou

d’égalité).

– déterminer une borne serrée et spécifique au problème de localisation et de trans-

port, dans le cas où le dimensionnement, le stockage ainsi que le transport sont

conditionnés par le budget d’incertitude fixé par le décideur.

– réaliser une étude approfondie du problème de gestion de stock incertain, en

définissant des bornes serrées aux constantes du problème de recours, puis ef-

fectuer des tests numériques afin de comparer les solutions obtenues dans les

différents contextes de décisions.

– formuler et résoudre la version robuste bi-étapes du problème de gestion de stock

incertain dans lequel il s’agit de dimensionner les bornes des contrats d’approvi-

sionnement et de stockage.

– formuler et résoudre la version robuste multi-étapes du problème de gestion de

stock incertain où l’on doit décider de manière dynamique à chaque période

d’une décision robuste pour la période suivante.

De ce travail de thèse il ressort que l’identification du contexte décisionnel du pro-

blème reste une étape clé pour l’établissement d’une version robuste adéquate. Ainsi,

le décideur doit définir de manière précise les objectifs visés et les garanties désirées.

À ce stade, la modélisation des incertitudes doit traduire le plus fidèlement possible

ces aléas afin de se rapprocher de la réalité. Une tâche qui n’est pas aisée à cause

du peu d’information disponible. Des développements et raffinements des modèles

d’incertitudes existants sont encore nécessaires pour mieux traduire ces incertitudes et

répondre à la préoccupation de robustesse. Enfin, l’utilisation de modèles robustes in-

duit souvent des formulations de plus grande complexité que les problèmes d’origine.

Ceci implique le développement de méthodologies et d’approches spécifiques pour la

résolution de ces problèmes.

Bibliographie

H. Aissi. Approximation et résolution des versions min-max et min-max regret de pro-

blèmes d´optimisation combinatoire. PhD thesis, Université Paris-Dauphine, 2005. (Cité

page 17.)

H. Aissi, Bazgan C., et D. Vanderpooten. Min-max and min-max regret versions of

some combinatorial optimization problems : a survey. Univesité Paris Dauphine, An-

nales du LAMSADE, (7) :1–32, 2007. (Cité page 17.)

G. Alefeld et J. Herzberger. Introduction to Interval Computation. Academic Press Inc,

1983. (Cité page 56.)

I. D. Aron et P. Van Hentenryck. On the complexity of the robust spanning tree problem

with interval data. Operations Research Letters, 32(1) :36 – 40, 2004. (Cité page 17.)

T. Assavapokee, M. J. Realff, J. C. Ammons, et I-H. Hong. Scenario relaxation algo-

rithm for finite scenario-based min-max regret and min-max relative regret robust

optimization. Computers and Operations Research, 35(6) :2093 – 2102, 2008. Part Spe-

cial Issue : OR Applications in the Military and in Counter-Terrorism. (Cité pages 10

et 17.)

A. Atamtürk et M. Zhang. Two-stage robust network flow and design under demand

uncertainty. Operations Research, 55(4) :662 – 673, 2007. (Cité pages 37, 87 et 114.)

I. Averbakh. Minmax regret solutions for minimax optimization problems with uncer-

tainty. Operations Research Letters, 27(2) :57 – 65, 2000. (Cité pages 10 et 17.)

I. Averbakh. On the complexity of a class of combinatorial optimization problems with

uncertainty. Mathematical Programming, 90(3) :263–272, 2001. (Cité page 17.)

I. Averbakh. Minmax regret linear resource allocation problems. Operations Research

Letters, 32(2) :174–180, 2004. (Cité page 17.)

I. Averbakh. The minmax relative regret median problem on networks. INFORMS J.

on Computing, 17(4), 2005. (Cité page 10.)

147

148 Bibliographie

I. Averbakh et V. Lebedev. Interval data minmax regret network optimization problems.

Discrete Applied Mathematics, 138 :289–301, 2004. (Cité page 17.)

I. Averbakh et V. Lebedev. On the complexity of minmax regret linear programming.

European Journal of Operational Research, 160(1) :227–231, 2005. (Cité pages 2, 3, 11, 14

et 16.)

F. Babonneau, J.-P. Vial, et R. Apparigliato. Uncertainty and environmental deci-

sion making. volume 138 de International Series in Operations Research and Manage-

ment Science, Chapitre Robust Optimization for Environmental and Energy Planning,

pages 79–126. 2010. (Cité pages 23, 25 et 33.)

A. Beck et A Ben-Tal. Duality in robust optimization : Primal worst equals dual best.

Operation Rsearch Letters, 37(1) :1–6, 2009. (Cité page 69.)

A. Ben-Tal, L. El Ghaoui, et A. Nemirovski. Robust Optimization. Princeton Series in

Applied Mathematics. Princeton University Press, October 2009. (Cité page 24.)

A. Ben-Tal, B. Golany, A. Nemirovski, et J.-P. Vial. Supplier-retailer flexible commit-

ments contracts : A robust optimization approach. Rapport technique, Dept. of Ma-

nagement Studies, University of Geneva, 2003. (Cité page 33.)

A. Ben-Tal, A. Goryashko, E. Guslitzer, et A. Nimerovski. Adjustable robust solutions

of uncertain linear programs. Mathematical Programming, 99 :351–376, August 2004.

(Cité pages 4, 30, 31, 32 et 33.)

A. Ben-Tal, T. Margalit, et A. Nemirovski. Robust modeling of multi-stage portfolio

problems. Dans T. Terlsky H. Frenk, K. Roos et S. Zhang edition, éditeurs, High Per-

formance Optimization, pages 303–328. Kluwer Academic Publisher, Dordrecht, The

Netherlands, 2000. (Cité page 33.)

A. Ben-Tal et A. Nimerovski. Robust solutions of uncertain linear programs. Operations

Research Letters, 25 :1–13, 1999. (Cité pages 18, 19 et 23.)

A. Ben-Tal et A. Nimerovski. Robust solutions of linear programming problems conta-

minated with uncertain data. Mathematical Programming, 88 :411–224, 2000. (Cité

page 23.)

A. Ben-Tal et A. Nimerovski. Robust optimization - methodology and applications.

Mathematical Programming Series, February 2002. (Cité pages 20 et 25.)

Bibliographie 149

A. Ben-Tal et M. Zibulevsky. Penalty/barrier multiplier methods for convex program-

ming problems. SIAM Journal on Optimization, 7 :347–366, 1995. (Cité page 24.)

D. Bertsimas, D.B. Brown, et C. Caramanis. Theory and applications of robust optimi-

zation. 2007. (Cité page 33.)

D. Bertsimas, D. Pachamanova, et M. Sim. Robust linear optimization under general

norms. Operations Research Letters, 32 :510–516, 2004. (Cité page 25.)

D. Bertsimas et M. Sim. Robust discrete optimization and network flows. Mathematical

Programming Series B., 98 :49–71, 2003. (Cité pages 2 et 28.)

D. Bertsimas et M. Sim. The price of robustness. Operations Research, 52(1) :35–53, 2004.

(Cité pages 5, 18, 26, 28, 72, 75, 76, 86, 128 et 144.)

D. Bertsimas et A. Thiele. Robust and data-driven optimization : Modern decision-

making under uncertainty. Rapport technique. (Cité page 33.)

D. Bertsimas et A. Thiele. A Robust Optimization Approach to Inventory Theory.

Operations Research, 54(1) :150–168, 2006. (Cité pages 119, 128, 129, 130 et 133.)

J.R. Birge et F. Louveaux. Introduction to Stochastic Programming. Springer-Verlag, 1997.

(Cité page 1.)

J. M. Bloemhof-Ruwaard et E. M. T. Hendrix. Generalized bilinear programming :

An application in farm management. European Journal Of Operational Research, 90 :

102–114, 1996. (Cité page 78.)

X. Chen, M. Sim, P. Sun, et J. Zhang. A linear decision-based approximation approach

to stochastic programming. Operations Research, 56(2) :344–357, 2008. (Cité page 33.)

J.W. Chinneck et K. Ramadan. Linear programming with interval coefficients. The

Journal of the Operational Research Society, 51(2) :209–220, Feb. 2000. (Cité page 56.)

E. Daniel et A. Salazar. Robustness analysis : An information-based perspective. Euro-

pean Working Group : Multiple Criteria Decision Aiding, 3(14), 2006. (Cité page 2.)

G.B. Dantzig. Linear programming under uncertainty. Management Science, 1 :179–206,

1955. (Cité page 2.)

V. G. Deineko et G. J. Woeginger. On the robust assignment problem under a fixed

number of cost scenarios. Operations Research Letters, 34(2) :175 – 179, 2006. (Cité

pages 2 et 17.)

150 Bibliographie

L. El Ghaoui et H. Lebret. Robust solutions to least-squares problems with uncertain

data. SIAM Journal on Matrix Analysis and Applications, 18(4) :1035–1064, 1997. (Cité

page 23.)

L. El Ghaoui, F. Oustry, et H. Lebret. Robust solutions to uncertain semidefinite pro-

grams. SIAM Journal on Optimization, 9(1) :33–52, 1998. (Cité page 23.)

A. L. Erera, J. C. Morales, et M. Savelsbergh. Robust optimization for empty repositio-

ning problems. Operations Research, 57(2) :468–483, 2009. (Cité page 33.)

B. Escoffier, J. Monnot, et O. Spanjaard. Some tractable instances of interval data min-

max regret problems. Operations Research Letters, 36(4) :424 – 429, 2008. (Cité page 17.)

J. E. Falk. A linear max-min problem. Mathematical Programming, 5 :169–188, 1973. (Cité

page 78.)

J.E. Falk. Exact solutions to inexact linear programs. Operations Research, pages 783–787,

1976. (Cité page 19.)

M. Fiedler, J. Nedoma, J. Ramik, J. Rohn, et K. Zimmermann. Linear optimization

problems with inexact data. Chapitre Interval linear programming. New York :

Springer-Verlag, 2006. (Cité page 56.)

C. Floudas et P.M. Parlados. State of the art in global optimization. Chapitre Global

Optimization of separable concave functions under Linear Constraints with Totally

Unimodular Matices. Kluwer, Dordrecht- Boston- London, 1995. (Cité page 78.)

V. Gabrel et C. Murat. Robust shortest path problems. Annales du LAMSADE, Robust-

ness in OR-DA, (7) :71–94, 2007. (Cité pages 2 et 13.)

V. Gabrel et C. Murat. Robustness and duality in linear programming. Journal of the

Operational Research Society, 61 :1288–1296, 2010. (Cité page 69.)

V. Gabrel, C. Murat, et N. Remli. Best and worst optimum for linear programs with

interval right hand sides. Dans Le Thi Hoai An, Pascal Bouvry, et Pham Dinh Tao,

éditeurs, MCO, volume 14 de Communications in Computer and Information Science,

pages 126–134. Springer, 2008. ISBN 978-3-540-87476-8. (Cité page 47.)

V. Gabrel, C. Murat, et N. Remli. Linear programming with interval right hand sides.

International Transactions in Operational Research, 17(3) :397–408, 2010a. (Cité page 47.)

Bibliographie 151

V. Gabrel, C. Murat, N. Remli, et M. Lacroix. Recourse problem of the 2-stage robust

location transportation problem. Electronic Notes in Discrete Mathematics, 36 :167 –

174, 2010b. ISCO 2010 - International Symposium on Combinatorial Optimization.

(Cité page 91.)

G. Gallo et A. Ülkücü. Bilinear programming : an exact algorithm. Mathematical Pro-

gramming, 12 :173–194, 1977. (Cité page 78.)

F. Glover. Improved linear integer programming formulations of nonlinear integer

problems. Management Science, 22(4) :455–460, 1975. (Cité pages 80 et 85.)

F. Glover et E. Woolsey. Converting the 0-1 polynomial programming problem to a 0-1

linear program. Opererations Research, 22 :180–182, 1974. (Cité page 80.)

D. Goldfarb et G. Iyengar. Robust portfolio selection problems. Mathematics of Opera-

tions Research, 28(1) :1–38, 2003. (Cité page 25.)

S.K. Gupta et J. Rosenhead. Robustness in sequential investment decisions. Management

Science, 15(2) :18–29, 1968. (Cité page 3.)

E. Guslitser. Uncertainty-immunized solutions in linear programming. Rapport de

Master, The Technion-Israel Institute of Technology, 2002. (Cité pages 31 et 32.)

M. Hladìk. Optimal value range in interval linear programming. Fuzzy Optimization

and Decision Making. (Cité page 56.)

R. Horst et H. Tuy. Global optimization : deterministic approaches. Chapitre Special

Problems of Concave Minimization. Springer-Verlag Berlin Heidelberg New York,

1996. (Cité page 80.)

M. Inuiguchi et M. Sakawa. Minmax regret solution to linear programming problems

with an interval objective function. European Journal Of Operational Research, 86 :

526–536, 1995. (Cité page 16.)

M. Inuiguchi et M. Sakawa. Maximum regret analysis in linear programs with an

interval objective function. Dans Proceedings of IWSCI’96, pages 308–317, 1996. (Cité

page 16.)

R. Kalai. Une nouvelle approche de robustesse : application à quelques problèmes d optimisa-

tion. PhD thesis, LAMSADE, Université Paris-Dauphine, 2006. (Cité page 10.)

152 Bibliographie

R. Kalai et C. Lamboray. alpha-robustesse lexicographique : une relaxation de la beta-

robustesse. Annales du LAMSADE, Robustness in OR-DA, (7) :129–144, 2007. (Cité

page 10.)

P. Kall et S. Wallace. Stochastic Programming. John Wiley and Sons, 1994. (Cité page 1.)

O. E. Karasan, M. C. Pinar, et H. Yaman. The robust shortest path problem with interval

data. Rapport technique, Bilkent Univ., Dpt. of Industrial Engineering, 2001. (Cité

page 17.)

A. Kasperski et P. Zielinski. The robust shortest path problem in series-parallel mul-

tidigraphs with interval data. Operations Research Letters, 34(1) :69 – 76, 2006. (Cité

page 17.)

J. E. Kelley. The cutting-plane method for solving convex programs. Society for Industrial

and Applied Mathematics, 8(4) :703–712, 1960. (Cité pages 39, 91, 98 et 100.)

H. Konno. A cutting plane algorithm solving bilinear programs. Mathematical Program-

ming, 11 :14–27, 1976. (Cité page 78.)

P. Kouvelis, A. A. Kurawarwala, et G. J. Gutierrez. Algorithms for robust single and

multiple period layout planning for manufacturing systems. European Journal of Ope-

rational Research, 63(2) :287 – 303, 1992. (Cité page 10.)

P. Kouvelis et G. Yu. Robust discrete optimization and its applications. Kluwer Academic

Publishers, 1997. (Cité page 2.)

R.D. Luce et H. Raiffa. Games and decisions : Intoduction and critical survey. New

York : Wiley, 1957. (Cité page 13.)

HE. Mausser et M. Laguna. A new mixed integer formulation for the maximum regret

problem. International Transactions in Operational Research, 5(5) :398–403, 1998. (Cité

page 17.)

HE. Mausser et M. Laguna. A heuristic to minmax absolute regret for linear programs

with interval objective function coefficents. European Journal of Operational Research,

117 :157–174, 1999a. (Cité page 17.)

HE. Mausser et M. Laguna. Minimizing the maximum relative regret for linear pro-

grams with interval objective function coefficents. European Journal of Operational

Research, 50(10) :1063–1070, Oct. 1999b. (Cité page 10.)

Bibliographie 153

C. Meyer. On tuy’s 1964 cone splitting algorithm for concave minimization. Rapport

Technique G-97-48, Les Cahiers Du Gerad, 1997. (Cité page 78.)

C. Meyer. A simple finite cone covering algorithm for concave minimization. Journal of

Global Optimization, 18(4), 2000. (Cité page 78.)

C. Meyer et B. Jaumard. A new finite cone covering algorithm for concave minimiza-

tion. Rapport Technique G-98-70, Les Cahiers Du Gerad, 1998. (Cité page 78.)

M. Minoux. Duality, robustness, and 2-stage robust lp decision models. application to

robust pert scheduling. Annales du LAMSADE, Robustness in OR-DA, (7) :173–190,

2007a. (Cité pages 36, 37, 66 et 87.)

M. Minoux. Models and algorithms for robust pert scheduling with time-dependent

task durations. Vietnam Journal of Mathematics, 35(4) :387–398, 2007b. (Cité pages 37

et 87.)

M. Minoux. Solving some multistage robust decision problems with huge implicitly

defined scenario trees. Algorithmic Operations Research, 4(1) :1–18, 2008. (Cité pages 37

et 140.)

M. Minoux. On robust maximum flow with polyhedral uncertainty sets. Optimization

Letters, 3 :367–376, 2009a. (Cité page 87.)

M. Minoux. Robust linear programming with right hand side uncertainty, duality and

application. Encyclopedia of Optimization, pages 3317–3327, 2009b. (Cité pages 30, 36,

37 et 66.)

M. Minoux. Robust network optimization under polyhedral demand uncertainty is

np-hard. Discrete Applied Mathematics, 158(5) :597–603, 2010. (Cité page 87.)

R. Montemanni. A benders decomposition approach for the robust spanning tree pro-

blem with interval data. European Journal of Operational Research, 174(3) :1479–1490,

2006. (Cité page 17.)

R. Montemanni, J. Barta, et L.M . Gambardella. The robust traveling salesman pro-

blem with interval data. Rapport technique, Istituto Dalle Molle di Studi sull’Intel-

ligenza Artificiale (IDSIA-20-05), Galleria 2, CH-6928 Lugano-Manno, Switzerland,

2005. (Cité page 17.)

154 Bibliographie

R. Montemanni et L. Gambardella. An exact algorithm for the robust shortest path

problem with interval data. Computers and Operations Research, 31 :1667–1680, 2004.

(Cité page 17.)

R. Montemanni, L. Gambardella, et A.V. Donati. A branch and bound algorithm for

the robust shortest path problem with interval data. Operations Research Letters, 32 :

225–232, 2004. (Cité page 17.)

R. Montemanni et L. M. Gambardella. A branch and bound algorithm for the robust

spanning tree problem with interval data. European Journal of Operational Research,

161(3) :771 – 779, 2005. (Cité page 17.)

F. Mráz. Calculating the exact bounds of optimal values in lp with interval coefficients.

Annals of Operations Research, 81 :51–62, 1998. (Cité page 56.)

A. Prékopa. Stochastic Programming. Kluwer, 1995. (Cité page 1.)

N. Remli. Gestion des stockages gaziers. Rapport de Master, Université Paris-

Dauphine, 2006. (Cité pages 119 et 141.)

M. J. Rosenblatt et Lee H. L. A robustness approach to facilities design. International

Journal of Production Research, 25 :479–486, 1987. (Cité page 3.)

J. Rosenhead, M. Elton, et S. K. Gupta. Robustness and optimality as criteria for stra-

tegic decisions. Operational Research Quarterly (1970-1977), 23(4) :413–431, 1972. (Cité

page 3.)

M. J. Rosenhead. Rational analysis for a problematic world. Wiley, New York, 1989.

(Cité page 3.)

B. Roy. Robustesse de quoi, vis-à-vis de quoi, mais aussi robustesse pourquoi en aide

à la décision ? In Newsletters of the European Working Group «Multicriteria Aid for

Decisions», (6) :1–6, 2002. (Cité page 2.)

B. Roy. Robustness in operational research and decision aiding : A multi-faceted issue.

European Journal of Operational Research, 200(3) :629–638, 2010. (Cité page 10.)

B. Roy, M. Elton, et S. K. Gupta. A missing link in operational research decision aiding :

robustness analysis. Foundations of Computing and Decision Sciences, 23(3) :141–160,

1982. (Cité page 3.)

Bibliographie 155

L.J. Savage. The foundation of statistics. New York : Wiley, 1954. (Cité page 13.)

H. D. Sherali et C.M. Shetty. A finitely convergent algorithm for bilinear programming

problems using polar cuts and disjunctive face cuts. Mathematical Programming, 19 :

14–31, 1980. (Cité page 78.)

K. Shimizu et E. Aiyoshi. Necessary conditions for min-max problems and algorithm

by relaxation procedure. IEEE Transaction on Automatic control, Ac-25 :62–66, 1980.

(Cité pages 14, 15 et 16.)

C. Singh. Convex programming with set-inclusive constraints and its applications to

generalized linear and fractional programming. Journal of Optimization Theory and

Applications, 38(1) :33–42, 1982. (Cité page 19.)

O. Solyali, J.F. Cordeau, et G. Laporte. Robust inventory routing under demand uncer-

tainty. Rapport Technique 17, CIRRELT, 2010. (Cité pages 37 et 133.)

A. L. Soyster. Convex programming with set-inclusive constraints and applications

to inexact linear programming. Operations Research, 21(5) :1154–1157, October 1973.

(Cité pages 18, 19, 20, 21, 46 et 47.)

A. L. Soyster. Inexact linear programming with generalized resource sets. European

Journal of Operational Research, 3(4) :316–321, 1979. (Cité page 19.)

A. Takeda, S. Taguchi, et R. H. Tütüncü. Adjustable robust optimization models for

nonlinear multi-period optimization. Rapport Technique 04-CNA-013, Department

of Mathematical Sciences, Carnegie Mellon University, Pittsburgh, PA 15213, USA,

2004. (Cité page 32.)

F. Taniguchi, T. Yamada, et S. Kataoka. Heuristic and exact algorithms for the max-

min optimization of the multi-scenario knapsack problem. Computers and Operations

Research, 35(6), 2008. (Cité page 13.)

A. Thiele, T. Terry, et M. Epelman. Robust linear optimization with recourse. Rapport

technique, 2009. (Cité pages 4, 37, 91, 98 et 114.)

F. E. Torres. Linearization of mixed-integer products. Mathematical Programming, 49 :

427–428, 1990. (Cité page 85.)

Stephen A. Vavasis. Nonlinear optimization : complexity issues. Oxford University Press,

Inc., New York, NY, USA, 1991. (Cité page 78.)

H. Yaman, O. E. Karasan, et M. C. Pinar. The robust spanning tree problem with

interval data. Operations Research Letters, 29 :31–40, 2001. (Cité pages 13 et 17.)

G. Yu. On the max-min 0-1 knapsack problem with robust optimization applications.

Operations Research, 44(2) :407–415, 1996. (Cité page 13.)

G. Yu et J. Yang. On the robust shortest path problem. Computers and Operations

Research, 25(6) :457 – 468, 1998. (Cité pages 2 et 13.)

P. Zielinski. The computational complexity of the relative robust shortest path problem

with interval data. European Journal of Operational Research, 158(3) :570 – 576, 2004.

(Cité page 10.)

Résumé Dans cette thèse nous nous intéressons à la prise en compte d’incertitudesaffectant les coefficients de programmes linéaires. Plus précisément, nous traitonsles problèmes admettant un second membre des contraintes incertain. Notre étudevise à répondre à la préoccupation de robustesse pour ces problèmes et cela suivantleur contexte décisionnel. Nous considérons trois contextes de décision : le premierconcerne la prise de décision en présence d’incertitudes, le deuxième traite de l’éva-luation des coûts en fonction des aléas et cela dans une phase de planification et le troi-sième comporte des problématiques multi-étapes, où la décision robuste doit prendreen compte le caractère dynamique de ces problèmes. Pour chacun de ses contextes nousprésentons la formulation mathématique des problèmes engendrés, leur complexité etune approche de résolution. Nous nous intéressons également à deux applicationsréelles : le problème de localisation et de transport robuste comportant des demandesincertaines que nous traitons dans un contexte bi-étapes et, un problème de gestion destock admettant une demande incertaine abordé selon les trois contextes décisionnelsprécédents.

Mots-clés Robustesse, programmation linéaire, second membre incertain, optimisa-tion multi-étapes robuste, problème de localisation et de transport, problème de ges-tion de stock

Abstract In this thesis, we are interested in handling uncertainty in linear program-ming. Specifically, we address problems affected with uncertain right hand side. Ourstudy addresses the concern of robustness depending on the context of the decisionmaking. We consider three contexts : the first context concerns the decision makingunder uncertainty, the second context deals with cost estimates depending on un-certainties, to compute in a planning step, and the third context involves multi-stepproblems, where the robust decision must take into account the dynamic nature ofthese problems. For each one of the contexts we present the mathematical formulationof the problems, the complexity and an approach to resolution. We are also interestedin two real applications : the robust location transportation problem with uncertaindemands, a problem that we treat with a two-stage robust approach, and the inven-tory management problem with uncertain demands explored under the previous threecontexts.

Keywords Robustness, linear programming, uncertain right hand side, multi-stagerobust optimization, location transportation problem, inventory management problem

Documents

les thèses : ces opinions doivent être considérées comme