28
Introduction Exemples Probl` eme d’optimisation Plan Informatique & Math´ ematiques Appliqu´ ees Programmation Math´ ematique et Application Introduction J. Gergaud & D. Ruiz 17 avril 2008 1/ 28

Informatique & Mathématiques Appliquées Programmation

  • Upload
    others

  • View
    6

  • Download
    0

Embed Size (px)

Citation preview

Page 1: Informatique & Mathématiques Appliquées Programmation

Introduction Exemples Probleme d’optimisation Plan

Informatique & Mathematiques AppliqueesProgrammation Mathematique et

ApplicationIntroduction

J. Gergaud & D. Ruiz

17 avril 2008

1/ 28

Page 2: Informatique & Mathématiques Appliquées Programmation

Introduction Exemples Probleme d’optimisation Plan

Introduction

ExemplesCas Continu et de dimension finieProblemes en nombres entiers

Probleme d’optimisationDefinitionClassification

Plan

2/ 28

Page 3: Informatique & Mathématiques Appliquées Programmation

Introduction Exemples Probleme d’optimisation Plan

Introduction

Soit f une application d’un ensemble E dans un ensemble F . Unprobleme d’optimisation consiste a rechercher le meilleur elementde l’ensemble E , c’est-a-dire celui qui rend la valeur de f la pluspetite possible.

(P)

{min f (x)x ∈ C ⊂ E .

I Il faut donc avoir une structure d’ordre sur E (= R)

I E s’appelle l’ensemble des strategies, des etats, desparametres, l’espace

I C est l’ensemble des contraintes

I f est la fonction cout, economique ou le critere, l’objectif

3/ 28

Page 4: Informatique & Mathématiques Appliquées Programmation

Introduction Exemples Probleme d’optimisation Plan

Introduction

Deux questionsI Question 1 : Existence de solution

I Si C est fini, c’est evidentI Si C est infini, c’est moins trivial

I Question 2 : Calcul de la solutionI Si C est fini mais grand, c’est ”difficile”I Si C ⊂ Rn et que les fonctions sont derivables, c’est plus facile

4/ 28

Page 5: Informatique & Mathématiques Appliquées Programmation

Introduction Exemples Probleme d’optimisation Plan

Cas Continu et de dimension finie

Principe de Fermat

I Pierre de Fermat, 1601(Beaumont-de-Lomagne, pres deMontauban) – 1665 (Castres)

I Principe de Fermat : la lumierese propage d’un point a un autresur des trajectoires telles que laduree du parcours soit minimale

I methode, dite de maximis etminimis

I precurseur du calcul differentiel

5/ 28

Page 6: Informatique & Mathématiques Appliquées Programmation

Introduction Exemples Probleme d’optimisation Plan

Cas Continu et de dimension finie

Probleme

−1 0 1 2 3 4 5 6 7−3

−2

−1

0

1

2

3

A(0,a)

B(k,b)

P(x,0)

air

eau

α1

α2

Fig.: Principe de Fermat.6/ 28

Page 7: Informatique & Mathématiques Appliquées Programmation

Introduction Exemples Probleme d’optimisation Plan

Cas Continu et de dimension finie

Exemple 2 : Condensateur

Un condensateur charge a une tension de U0 volts se decharge surune resistance. On mesure la tension U entre les armatures ducondensateur toutes les secondes pendant un intervalle de temps de10 secondes. Les resultats des mesures sont donnees dans la table

ti Ui ti Ui

0 100 6 151 75 7 102 55 8 103 40 9 54 30 10 55 20

7/ 28

Page 8: Informatique & Mathématiques Appliquées Programmation

Introduction Exemples Probleme d’optimisation Plan

Cas Continu et de dimension finie

Residus

−2 0 2 4 6 8 10 120

10

20

30

40

50

60

70

80

90

100

110

← r1

← r2

← r3

← r4

← r5

← r6

← r7

← r8 ← r

9← r

10 ← r11

Fig.: Criteres des moindres carres8/ 28

Page 9: Informatique & Mathématiques Appliquées Programmation

Introduction Exemples Probleme d’optimisation Plan

Cas Continu et de dimension finie

Exemple 3 : modele de Kaplan

On desire etudier la diffusion d’une drogue dans un organe d’uncorps donne. La drogue est injectee par intraveineuse dans le sanga l’instant t0 = 0. On modelise le systeme par un modele acompartiments (cf.la figure 3).

Sang y1(t) Organe y2(t)-

?

k1

k3

k2

Fig.: Modele par compartiments.

9/ 28

Page 10: Informatique & Mathématiques Appliquées Programmation

Introduction Exemples Probleme d’optimisation Plan

Cas Continu et de dimension finie

Donnees

Les concentrations dans le sang, mesurees a differents instants,sont donnees a la table 1.

ti yi1 ti yi1

0.25 215.6 3.00 101.20.50 189.2 4.00 88.00.75 176.0 6.00 61.61.00 162.8 12.00 22.01.50 138.6 24.00 4.42.00 121.0 48.00 0.0

Tab.: Donnees pour l’exemple de Kaplan.

Le systeme d’equations differentielles decrivant le modele est alors10/ 28

Page 11: Informatique & Mathématiques Appliquées Programmation

Introduction Exemples Probleme d’optimisation Plan

Cas Continu et de dimension finie

Modele

Le systeme d’equations differentielles decrivant le modele est alors

(EDO)

dy1

dt= y1(t) = −(k1 + k2)y1(t) + k3y2(t)

dy2

dt= y2(t) = k1y1(t)− k3y2(t)

y1(0) = c0

y2(0) = 0.

11/ 28

Page 12: Informatique & Mathématiques Appliquées Programmation

Introduction Exemples Probleme d’optimisation Plan

Cas Continu et de dimension finie

Residus

0 5 10 15 20 25 30 35 40 45 50

0

50

100

150

200

250

t

y 1(t)

← r1

← r2← r3← r4

← r5← r6← r

7← r8← r

9← r

10 ← r11 ← r

12

0 5 10 15 20 25 30 35 40 45 500

20

40

60

80

t

y 2(t)

Fig.: Critere des moindres carres pour le modele de Kaplan.12/ 28

Page 13: Informatique & Mathématiques Appliquées Programmation

Introduction Exemples Probleme d’optimisation Plan

Cas Continu et de dimension finie

Exemple 4 : Fisher

On veut mesurer la liaison entre 2 genes dominants, l’un controlantla couleur d’une fleur, rouge (R) est dominant sur blanc (b), etl’autre la taille, grand (G ) est dominant sur petit (p). Dans ladescendance F2, issu de deux populations homozygotes dephenotype [RG ] et [bp], on a etudie n = 3839 plantes. On aobtenu les resultats de la table 2.

Phenotypes [RG ] [Rp] [bG ] [bp]

Effectifs observes 1997 906 904 32

Tab.: Donnees de Sir R.A. Fisher.

13/ 28

Page 14: Informatique & Mathématiques Appliquées Programmation

Introduction Exemples Probleme d’optimisation Plan

Cas Continu et de dimension finie

Probabilites

Le probleme est d’estimer, a partir de ces donnees le taux derecombinaison r .Ici la population F1 est heterozygote de genotype Rb,Gp. Nousavons donc les probabilites de la table 3 pour les differents gametespossibles et les differents croisements possibles.

♀ : ♂ RG bp Rp bG12(1 − r) 1

2(1 − r) 1

2r 1

2r

RG [RG ] [RG ] [RG ] [RG ]12(1 − r) 1

4(1 − r)2 1

4(1 − r)2 1

4r(1 − r) 1

4r(1 − r)

bp [RG ] [bp] [Rp] [bG ]12(1 − r) 1

4(1 − r)2 1

4(1 − r)2 1

4r(1 − r) 1

4r(1 − r)

Rp [RG ] [Rp] [Rp] [RG ]12r 1

4r(1 − r) 1

4r(1 − r) 1

4r2 1

4r2

bG [RG ] [bG ] [RG ] [bG ]12r 1

4r(1 − r) 1

4r(1 − r) 1

4r2 1

4r2

Tab.: Probabilites pour la descendance F2

14/ 28

Page 15: Informatique & Mathématiques Appliquées Programmation

Introduction Exemples Probleme d’optimisation Plan

Cas Continu et de dimension finie

Modele

Par suite nous avons dans la population F2 la loi suivante pour lavariable aleatoire phenotype X

X : F2 −→ {[RG ], [Rp], [bG ], [bp]}1 plante 7−→ son phenotype,

P(X = [RG ]) =1

4(3− 2r + r2) =

2 + θ

4

P(X = [Rp]) =1

4(2r − r2) =

1− θ

4

P(X = [bG ]) =1

4(2r − r2) =

1− θ

4

P(X = [bp]) =1

4(1− r)2 =

θ

4

15/ 28

Page 16: Informatique & Mathématiques Appliquées Programmation

Introduction Exemples Probleme d’optimisation Plan

Cas Continu et de dimension finie

Exemple 4 : probleme lineaire

Un fermier desire determiner les quantites de lisier de porc etd’engrais compose a etendre sur 20 ha de prairie de facon aoptimiser le cout total de la fertilisation. Le cout et la compositiondu lisier et de l’engrais sont donnes a la table 4.

cout (par tonne) composition chimique (kgt−1)azote phosphate potasse

lisier 25 francs 6 1.5 4engrais 1300 francs 250 100 100

Tab.: Couts et compositions des engrais

Le fermier veut appliquer au moins 75 kgha−1 d’azote, 25 kgha−1

de phosphate et 35 kgha−1 de potasse. Il ne peut appliquer le lisierqu’a un taux maximum de 8 t/heure et l’engrais qu’a un tauxmaximum de 0.4 t/heure. Il ne peut de plus consacrer pour cetravail qu’un maximum de 25 heures.

16/ 28

Page 17: Informatique & Mathématiques Appliquées Programmation

Introduction Exemples Probleme d’optimisation Plan

Cas Continu et de dimension finie

Gestion de portefeuille I

I Harry Markowitz, prix Nobel d’economie en 1990I On a :

I une quantite fixe d’argentI n actifs differentes (actions, stocks, ...)

I On connaıt :I Pour tout actif i son esperance mathematique µi et sa variance

σ2i

I Pour tout actifs i et j leur coefficient de correlation lineaire ρij

I On note x = (x1, . . . , xn) ou xi represente la proportioninvestie dans l’actif i

17/ 28

Page 18: Informatique & Mathématiques Appliquées Programmation

Introduction Exemples Probleme d’optimisation Plan

Cas Continu et de dimension finie

Gestion de portefeuille II

I Le portefeuille sera dit efficient si, pour une variance fixee, il ala plus grande esperance mathematique

(P)

Max E (x)Var(x) = V∑n

i=1 xi = 1x ≥ 0.

I On peut aussi s’interesser au probleme (MV 0)(Mean-Variance 0ptimization) de Markowitz.

(MVO)

Min Var(x)E (x) ≥ R∑n

i=1 xi = 1x ≥ 0.

18/ 28

Page 19: Informatique & Mathématiques Appliquées Programmation

Introduction Exemples Probleme d’optimisation Plan

Problemes en nombres entiers

Probleme du sac a dos de Knapsack

Un alpiniste veut mettre dans son sac a dos un maximum de 16 kgde ravitaillement. Il peut choisir un certain nombre d’unites de troisproduits differents. Le poids unitaire en kilogrammes et la valeurenergetique unitaire des ces produits sont connus et donnes dans latable (5).

Produits I II III

Poids 2 5 7Valeurs 4 10 15

Tab.: Poids unitaires et valeurs energetiques unitaires.

Le probleme pour l’alpiniste est de savoir ce qu’il doit emporterpour avoir une valeur totale en calories maximale sans depasser les16 kg.

19/ 28

Page 20: Informatique & Mathématiques Appliquées Programmation

Introduction Exemples Probleme d’optimisation Plan

Problemes en nombres entiers

probleme d’affectation de ressources

Dans un service hospitalier, les malades i attendent d’etre operes.Le malade i a besoin d’une duree d’operation Di . D’autre part,compte tenu des disponibilites des chirurgiens, la somme desdurees des operations possibles chaque jours j de la periode etudieeest connue et egale a Tj . On veut minimiser la somme despenalites d’attente pour les differents malades. On note :

I xij = 1 si le malade i est opere le jour j ;

I xij = 0 si le malade i n’est pas opere le jour j ;

I cij la penalite du malade i s’il est opere le jour j . cij est unefonction croissante de j .

20/ 28

Page 21: Informatique & Mathématiques Appliquées Programmation

Introduction Exemples Probleme d’optimisation Plan

Problemes en nombres entiers

Alignement de sequences

Soit 2 sequences CTGTATC et CTATAATCCC . On desire trouverle ”meilleur” alignement possible. A chaque alignement, est associeun score (simple ici) suivant : pour chaque position on associe 0 siles 2 bases sont identiques, +1 si les deux bases sont differentes et+3 s’il y a un ”trou”. On effectue ensuite la somme. La figure (5)donne un exemple de la fonction score S .

C T A T − A A − T C C C− − C T G T A T C − − −3 3 1 0 3 1 0 3 1 3 3 3 = 24

Fig.: Exemple de calcul d’un score.

21/ 28

Page 22: Informatique & Mathématiques Appliquées Programmation

Introduction Exemples Probleme d’optimisation Plan

Problemes en nombres entiers

Probleme de la brachistochrone I

Jean Bernoulli 27 juillet 1667 – 1erjanvier 1748.Ce probleme consiste en la recherchedans un plan vertical du cheminreliant 2 points P0 et Pf de ce plan,suivant lequel un corps M entrainepar son propre poids effectuera letrajet de P0 a Pf en un tempsminimum. On suppose qu’il n’y a pasde frottement

22/ 28

Page 23: Informatique & Mathématiques Appliquées Programmation

Introduction Exemples Probleme d’optimisation Plan

Problemes en nombres entiers

Probleme de la brachistochrone I

I v =√

2g(−y(x))

I ds =√

dx2 + dy2 ett = ds/

√2g(−y(x))

I

T : C 1([0, xf ],R) → R

T (y(.)) =

∫ xf

0

√1 + y ′(x)2√2g(−y(x))

dx

I

(P)

Min T (y(.))y(0) = 0y(xf ) = yf .

0 5 10 15 20 25

−20

−18

−16

−14

−12

−10

−8

−6

−4

−2

0

23/ 28

Page 24: Informatique & Mathématiques Appliquées Programmation

Introduction Exemples Probleme d’optimisation Plan

Problemes en nombres entiers

Transfert orbital

−40

−20

0

20

40

−40

−20

0

20

40

−505

r1

ORBITE INITIALE

ORBITE FINALE

r2

r 3

−50 0 50−40

−20

0

20

40

r1

r 2

−50 0 50−5

0

5

r2

r 3

I Orbite de depart LEO :P = 11.625 Mm, e = 0.75 andi = 7◦

I Orbite finale : orbitegeostationnaire

I Masse initiale : m0 = 1500 kg

I Poussee : Tmax = 0.1 N

24/ 28

Page 25: Informatique & Mathématiques Appliquées Programmation

Introduction Exemples Probleme d’optimisation Plan

Problemes en nombres entiers

tf min, m(tf ) max

(P)

Min tf =∫ tf0 dt tf libre

r(t) = v(t) pp.

v(t) = − µr(t)

|r(t)|3+

Tmax

m(t)u(t)

m(t) = −βTmax|u(t)|(r(t), v(t),m(t)) ∈ A|u(t)| ≤ 1r(0), v(0),m(0) fixer(tf ), v(tf ) fixe,

(P)

Min∫ tf0 |u(t)|dt tf fixe

r(t) = v(t) pp.

v(t) = − µr(t)

|r(t)|3+

Tmax

m(t)u(t)

m(t) = −βTmax|u(t)|(r(t), v(t),m(t)) ∈ A|u(t)| ≤ 1r(0), v(0),m(0) fixer(tf ), v(tf ) fixe,

Probleme de controle optimal

25/ 28

Page 26: Informatique & Mathématiques Appliquées Programmation

Introduction Exemples Probleme d’optimisation Plan

Classification

Classification optimisation differentiable

(P )

Min f(x)x ∈ C ⊂ E

E = Rn

C = Rn

Sans contraintes

f(x) = (1/2)||r(β)||2

Moindres carres

r(β) = Xβ − y

Moindres carres

lineaires

gj (x) ≤ 0

hl = 0

Avec contraintes

NLP

f, gj(x) convexes

hl = 0 affines

Problemes convexes

f, gi, hl affines

Problemes lineaires

LP

E = Rn × N

m

MINLP

f, gi, hl affines

MILP

E = Nn

INLP

f, gi, hl affines

ILP

dimE = +∞

26/ 28

Page 27: Informatique & Mathématiques Appliquées Programmation

Introduction Exemples Probleme d’optimisation Plan

l’Optimisation en Informatique et mathematiquesappliquees

I 1ere anneeI ConvexiteI Existence de solutionI Condition necessaire, condition suffisanteI Notion de dualiteI Problemes aux moindres carres (y compris algorithmique)

I 2ieme anneeI Optimisation numeriqueI Recherche operationnelle (Programmation Lineaire)I Controle optimal (majeure mathematique)

I 3ieme anneeI Optimisation discreteI Controle optimal

27/ 28

Page 28: Informatique & Mathématiques Appliquées Programmation

Introduction Exemples Probleme d’optimisation Plan

Evaluation

I Examen ecrit Calcul differentiel : 2 ECTS (1 page A4recto-verso)

I Projet : 2 ECTS (Calcul differentiel et Optimisation)

I Examen ecrit Optimisation : 2 ECTS (1 page A4 recto-verso)

28/ 28