[PDF] Thèse Mr. A.R. Mahjoub Professeur

View - Download Thèse

Previous PDF

Next PDF

UniversitéParis-Dauphine

Lamsade

N° attribué par la bibliothèqueThèse

présentée en première version en vue d"obtenir le grade de

Docteur enInformatique

spécialité Programmation mathématique par

Nabila REMLI

Robustesse en programmation linéaire

Date de soutenance le17Mars2011devant le jury composé de : Mr. P. MichelonProfesseur Université d´Avignon (Rapporteur) M meA. ThieleAssociate Professor Lehigh University (Rapporteur) M meV. GabrelMaître de conférences Université Paris-Dauphine (Directrice) M meC. MuratMaître de conférences Université Paris-Dauphine (Co-directrice)

Mr. M. MinouxProfesseur Université Paris6

Mr. A.R. MahjoubProfesseur Université Paris-Dauphine Mr. J. FigueiraProfesseur É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èresv

Liste des figuresix

Liste des tableauxxi

Introduction générale1

1État de l"art et problématique7

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

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

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

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

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

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

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

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

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

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

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

2Programmes linéaires avec seconds membres incertains43

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

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

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

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

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

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

2.2.2Programmes linéaires avec contraintes d"égalité. . . . . . . . . . . . .58v

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

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

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

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

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

3Calcul du pire optimum paramétrique73

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

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

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

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

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

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

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

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

4Problème de localisation et de transport robuste89

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

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

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

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

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

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

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

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

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

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

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

5Problème de gestion des stocks robuste117

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

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

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

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

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

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

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

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

Conclusion générale143

Bibliographie147vii

Liste des figures

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

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

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

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

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

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

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

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

4.2Ré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.3Ré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.4Résolution du problèmeTrob(Γ)pour un testn=m=50 :a-Valeur de

l"optimum en fonction deΓ.b-ΔOptMaxOpt en fonction deΓ. . . . . . . . . .110

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

m=35 : la courbeAreprésente la différence en pourcentage de v ?(Trob(Γ))-v?(T2rob(Γ))v ?(T2rob(Γ))×100 . La courbeBexprime la différence en pour- centage de v?(T2rob(n))-v?(T2rob(Γ))v ?(T2rob(Γ))×100 . . . . . . . . . . . . . . . . . . . . .114ix

Liste des tableaux

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

4.2Temps d"exécution de la résolution du problème robusteTrob(Γ). . . . .111

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

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

4.4Testn=m=35 : résolution deT2rob(Γ)vsTrob(Γ). . . . . . . . . . . . . .113

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

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

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

5.4Les valeurs des pénalitésptetqtrelatives au problème(G1). . . . . . . .126

5.5La solution de pire cas(upen

t,spen t,xpen t)du problème(G1Rob1). . . . . . .127

5.6Les valeurs des pénalitésp?tetq?trelatives au problème(G1). . . . . . . .127

5.7La solution de pire cas(upen?

t,spen? t,xpen? t,ypen? t)du problème(G1Rob1). .128

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

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

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

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

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ées1950, à 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

2Introduction généraleL"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 desolution robusteest 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 estune 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 robustesi 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

Introduction générale3un 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 oeuvre. 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 caset lecritè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.

4Introduction généraleDans 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 ducontexte 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 chapitre1, 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

Introduction générale5versions 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 chapitre2, 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 chapitre3, 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 chapitre4, 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 chapitre3. Enfin, dans le chapitre5, 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

SommaireIntroduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .9

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

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

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

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

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

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

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

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

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

Conclusion et problématique. . . . . . . . . . . . . . . . . . . . . . . . . . . . .39Dansce 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 objectif9Introduction

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 section1.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 (section1.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.1Incertitudes 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)?mincx oùxest une matrice colonne de taillenqui représente les variables du problème. La matrice des contraintesAest de taillem×net le second membre des contraintes des solutions réalisables du problème(Pc)que nous supposons non vide et borné. Le coûtcest une matrice ligne de taillen. Elle constitue la part incertaine du problème. Nous supposons que chaque coefficient incertain decprend 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

10Chapitre1. État de l"art et problématiquedes intervalles[cj

,c j],j=1...n, oùcj j. Nous définissons unscénariocomme étant une réalisation de l"incertitude dans le domaineΛet notonsv?(Pc)la valeur de l"optimum pour le scénariocfixé. 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 dupire cas(appelé aussirobustesse ab- solue) et le critère duregret maximum(oudé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 duregret relatif maximum(oudé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.1Critè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

1.1. Incertitudes sur les coefficients de la fonction objectif11incertitudes. 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 ˆxune solution réalisable de(Pc), sa valeur selon le critère du pire cas, notée v pir(ˆx), se définit comme : v

pir(ˆx) =maxc?Λcˆx(1.1)Suivant le critère du pire cas, il s"agit de déterminer, parmi toutes les solutions réali-

sablesx?X, celle qui minimise la valeur devpir(x). Le problème de pire cas, noté (Pc)pirCas, s"écrit : (Pc)pirCas? min

x?Xmaxc?ΛcxProposition1.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éalisablesXest 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)pirCaspar son dual. Nous obtenons la formulation en programme linéaire suivante : (Pc)pirCas? ?????mincu-cv s.c.u-v-x=0 u≥0,v≥0 qui est un problème polynomial.

12Chapitre1. État de l"art et problématiqueRemarque1.1Dans le cas particulier où les variables x sont de signe constant, par exemple

supposons qu"elles soient positives, le problème(Pc)pirCasest équivalent à(Pc (Pc)pirCas? ??mincx 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.Exemple1.1Soit le programme linéaire(P1c)suivant :(P1c)? ?????minc1x1+c2x2

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 : c

1?[-3,3]et c2?[1,3].

Selon la proposition1.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)pirCass"écrivant : (P1c)pirCas? s.c. u

1-v1-x1=0

u

2-v2-x2=0

3x1+2x2≥ -4

-5x1+2x2≥ -6 u

1,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 à-2dans le pire cas. La figure1.1illustre le domaine

1.1. Incertitudes sur les coefficients de la fonction objectif13des solutions réalisables du problème(P1c). Nous remarquons que x?pirCasne se situe pas sur

un point extrême du domaine des solutions réalisables du problème(P1c).-3-2-1123-2-112(1.3)(1.4)(1.2)x*pirCas=(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.2Critè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

14Chapitre1. État de l"art et problématiquesouvent 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

ˆxune solution réalisable du problème

quotesdbs_dbs20.pdfusesText_26

[PDF] Initiation à l'économie - ENSAE, 1A Maths - CREST

[PDF] 1 Tube cylindrique sous pression (12 points) - ENSTA ParisTech

[PDF] Economie de l'Incertain et des Incitations CHAPITRE 4 0pt40pt

[PDF] Science économique - mediaeduscoleducationfr - Ministère de l

[PDF] Applications  Problème du voyageur de commerce (TSP) - GERAD

[PDF] Gestion de projet - contraintes, chevauchement, attente - AUNEGE

[PDF] Définition - Irisa

[PDF] Contraintes et déformations (1)

[PDF] Le diagnostic dentreprise et lenvironnement (an sens - Aderse

[PDF] Mécanique des Structures et Approximations Numériques

[PDF] Les contraintes sociales et institutionnelles du développement de l

[PDF] La pression temporelle dans les environnements dynamiques : le

[PDF] Limites et responsabilités des ATSEM

[PDF] Les contraintes d'antériorités

[PDF] INTRODUCTION L'environnement est une contrainte - cloudfrontnet