Optimisation dans l'incertain
2017-2018

Master EDDEE-EEET
(Économie du développement durable,
de l'environnement et de l'énergie)
(mention Économie de l'environnement,
de l'énergie et des transports)

Michel De Lara (CERMICS-ENPC)

Version pdf de ce document


Contenu du cours. Dans un problème d'optimisation déterministe, les valeurs de tous les paramètres sont supposées connues. Comment formuler un problème d'optimisation dans lequel les données sont incertaines (par exemple, les prix des énergies) ? Et quand certaines valeurs des données sont révélées au cours des étapes de décision (par exemple, des valeurs de demande d'énergie) ? L'optimisation stochastique est un cadre pour répondre à de telles questions et pour formuler des problèmes sous incertitude. C'est également un ensemble de méthodes de résolution.

Dans ce cours, nous présentons la programmation stochastique à deux étapes (et la résolution sur arbre de scénarios ou par scénarios) et le contrôle stochastique à temps discret (et la résolution par programmation dynamique stochastique). Nous illustrons ces approches sur des problèmes de gestion de stocks pour l'énergie [LCCL14].

Des séances de travaux pratiques informatiques -- avec le logiciel scientifique Scicoslab et [CCN10] -- complètent les séances de cours.


Prérequis souhaités.


Apprentissage. À l'issue du cours l'étudiant devrait pouvoir concevoir des modèles mathématiques pour l'optimisation sous incertitude et utiliser le logiciel scientifique Scicoslab pour résoudre numériquement des problèmes de petite taille.


Matériel informatique. Ordinateur portable personnel aux séances de travaux pratiques. Logiciel (gratuit) Scicoslab.


Langue. Les transparents de cours et les travaux pratiques informatiques sont en anglais. Le cours oral est assuré en français.


Validation. Notation des travaux pratiques. Examens.


Équipe enseignante. Michel De Lara (ENPC)      Michel De Lara professional webpage


Lien cours http://cermics.enpc.fr/~delara/TEACHING/Master_EDDEE/Master_EDDEE.html      course webpage


Lien master EDDEE-EEET http://www.master-eddee.fr/      course webpage


Lieu. AgroParisTech - Engref, 19 avenue du Maine, 75732 PARIS CEDEX 15      Engref webpage


Programme

1 /     Mercredi 22 novembre 2017, 13h-15h30, salle Amphi 7

Exercice

Nous commençons par formuler un problème de commande optimale d'un produit pour satisfaire une demande, avec des coûts d'achat, de backorder et de holding. Nous montrons comment parvenir à un programme linéaire, d'abord en déterministe puis avec un nombre fini de scénarios de demande.      slides

2 /     Mercredi 22 novembre 2017, 16h-18h30, salle informatique CRM 2

Travaux pratiques informatiques

Introduction au logiciel de calcul scientifique Scicoslab.      Travaux pratiques Scicoslab

3 /     Mercredi 6 décembre 2017, 13h-15h30, salle Amphi 7

Travaux pratiques informatiques

The newsvendor problem Vous enverrez les résultats du TP The newsvendor problem sous forme d'un fichier pdf
NOM_TP1_EDDEE_2017.pdf à delara@cermics.enpc.fr avant le XXX.

4 /     Mercredi 6 décembre 2017, 16h-18h30, salle Amphi 7

Exercice de modélisation

Nous continuons par un exercice de modélisation. Comment formuler mathématiquement un problème d'allocation optimale de sources de production d'énergie (à coûts minimaux), avec production minimale garantie et pollution maximale garantie ? On obtient naturellement un programme linéaire. Nous verrons comment l'introduction d'incertitudes (coûts, production d'énergie renouvelable) modifie la formulation du problème. C'est l'occasion d'appréhender les notions de risque et de non-anticipativité.

Cours

Dans le cas d'un espace de probabilité fini, nous présentons la programmation stochastique à deux étapes, avec variables de recours [SDR09,KW12]. Nous montrons comment la contrainte de non-anticipativité peut être prise en compte en indiçant les solutions par un arbre de scénarios.      slides

5 /     Mercredi 10 janvier 2018, 13h-15h30, salle B 208

Travaux pratiques informatiques

Dimensionnement de réserves pour l'équilibrage sur un marché électrique.      travaux pratiques Scicoslab

6 /     Mercredi 10 janvier 2018, 16h-18h30, salle Amphi 7

Cours

Rappels et exercices sur l'optimisation continue [Ber96].     slides

Cours

Nous poursuivons la programmation stochastique à deux étapes et montrons comment la contrainte de non-anticipativité peut être prise en compte

Avec cette deuxième façon de faire, nous introduisons la décomposition par scénarios, puis le Progressive Hedging [RW91].      slides      slides      slides      slides

7 /     Mercredi 17 janvier 2018, 13h-15h30, salle B 208

Travaux pratiques informatiques

Dimensionnement de réserves pour l'équilibrage sur un marché électrique.      Two Stage Stochastic Optimization for Fixing Energy Reserves Vous enverrez les résultats du TP Two Stage Stochastic Optimization for Fixing Energy Reserves sous forme d'un fichier pdf
NOM_TP2_EDDEE_2017.pdf à delara@cermics.enpc.fr avant le XXX.

8 /     Mercredi 17 janvier 2018, 16h-18h30, salle Amphi 7

Cours

Contrôle optimal stochastique de systèmes dynamiques avec incertitudes. Programmation dynamique stochastique. Exercices : problème du sac à dos, gestion de stock. [Bel57,Put94,Ber00,Whi82,DD08,CCCD15]      slides


Malédiction de la dimension. Contrôle optimal stochastique avec coûts convexes et dynamique linéaire.      slides     Exercices.      slides


Bibliographie

Bel57
R. E. Bellman.
Dynamic Programming.
Princeton University Press, Princeton, N.J., 1957.

Ber96
D. P. Bertsekas.
Constrained Optimization and Lagrange Multiplier Methods.
Athena Scientific, Belmont, Massachusets, 1996.

Ber00
D. P. Bertsekas.
Dynamic Programming and Optimal Control.
Athena Scientific, Belmont, Massachusets, second edition, 2000.
Volumes 1 and 2.

Bre93
L. Breiman.
Probability.
Classics in applied mathematics. SIAM, Philadelphia, second edition, 1993.

CCCD15
P. Carpentier, J.-P. Chancelier, G. Cohen, and M. De Lara.
Stochastic Multi-Stage Optimization. At the Crossroads between Discrete Time Stochastic Control and Stochastic Programming.
Springer-Verlag, Berlin, 2015.

CCN10
Stephen Campbell, Jean-Philippe Chancelier, and Ramine Nikoukhah.
Modeling and Simulation in Scilab/Scicos with ScicosLab 4.4.
Springer-Verlag, New York, 2 edition, 2010.

DD08
Michel De Lara and Luc Doyen.
Sustainable Management of Natural Resources. Mathematical Models and Methods.
Springer-Verlag, Berlin, 2008.

Fel68
W. Feller.
An Introduction to Probability Theory and its Applications, volume 1.
Wiley, New York, third edition, 1968.

KW12
Alan J. King and Stein W. Wallace.
Modeling with Stochastic Programming.
Springer Series in Operations Research and Financial Engineering. Springer New York, 2012.

LCCL14
M. De Lara, P. Carpentier, J.-P. Chancelier, and V. Leclère.
Optimization methods for the smart grid.
Report commissioned by the Conseil Français de l'Énergie, École des Ponts ParisTech, October 2014.

Pit93
J. Pitman.
Probability.
Springer-Verlag, New-York, 1993.

Put94
M. L. Puterman.
Markov Decision Processes.
Wiley, New York, 1994.

RW91
R.T. Rockafellar and R. J-B. Wets.
Scenarios and policy aggregation in optimization under uncertainty.
Mathematics of operations research, 16(1):119-147, 1991.

SDR09
A. Shapiro, D. Dentcheva, and A. Ruszczynski.
Lectures on stochastic programming: modeling and theory.
The society for industrial and applied mathematics and the mathematical programming society, Philadelphia, USA, 2009.

Whi82
P. Whittle.
Optimization over Time: Dynamic Programming and Stochastic Control, volume 1 and 2.
John Wiley & Sons, New York, 1982.