Modélisation et résolution de problèmes de décision et d PDF

11 mai 2005 1 Problèmes d'optimisation combinatoire dans les applications spatiales ... Un problème d'optimisation consiste à chercher une instanciation ...

OPTIMISATION À LAIDE DEXCEL

Optimisation sans contraintes avec le Solveur d'Excel . problèmes d'optimisation de tous genres (une ou plusieurs variables avec ou sans contraintes).

Chapitre 7: Optimisation

Plan de résolution Voici la marche à suivre pour résoudre un problème d'optimisation: Calcul de la dérivée de Q fonction à optimiser.

Modélisation et résolution de problèmes de décision et d

26 mai 2010 d'optimisation hiérarchiques en utilisant des contraintes ... blème de décision à un problème d'optimisation ce qui permet de modéliser ...

Résolution de problèmes combinatoires et optimisation par colonies

Cette méta-heuristique a permis de résoudre différents problèmes d'optimisation combinatoire comme par exemple le problème du voyageur de commerce [DG97]

NOUVELLES APPROCHES DE MODÉLISATION ET D

Dans ce problème la difficulté est de modéliser la capacité gastrique de l'animal Wmoi(t) qui peut limiter la consommation d'aliment à basse densité

OPTIMISATION SOUS CONTRAINTES

Optimisation sous contrainte à variables multiples . Contrairement au problème sans contraintes il n'y a pas lieu de déterminer la.

Quelques problèmes doptimisation

23 mai 2013 Ce problème peut se formuler comme un problème d'optimisation c'est-à-dire un problème de minimisation d'une fonction bien choisie.

Perturbation des méthodes doptimisation. Applications

d'optimisation convexe avec contraintes. 1. INTRODUCTION. 1.1. La plupart des algorithmes pour résoudre un problème d'optimisation :.

Formulations de problèmes doptimisation multiniveaux pour la

15 oct. 2016 Formulation de Problèmes d'Optimisation Avion plus électrique

>G A/, ?H@yy3k88y3 ?iiTb,ffBM`BX?HXb+B2M+2f?H@yy3k88y3 am#KBii2/ QM kj Jv kyRj >GBb KmHiB@/Bb+BTHBM`v QT2M ++2bb `+?Bp2 7Q` i?2 /2TQbBi M/ /Bbb2KBMiBQM Q7 b+B@

2MiB}+ `2b2`+? /Q+mK2Mib- r?2i?2` i?2v `2 Tm#@

HBb?2/ Q` MQiX h?2 /Q+mK2Mib Kv +QK2 7`QK

i2+?BM; M/ `2b2`+? BMbiBimiBQMb BM 6`M+2 Q` #`Q/- Q` 7`QK Tm#HB+ Q` T`Bpi2 `2b2`+? +2Mi2`bX

Gˆ`+?Bp2 Qmp2`i2 THm`B/Bb+BTHBMB`2>G- 2bi

Zm2H[m2b T`Q#HK2b /ˆQTiBKBbiBQM

JHH2 LQ/2i

hQ +Bi2 i?Bb p2`bBQM, JHH2 LQ/2iX Zm2H[m2b T`Q#HK2b /ˆQTiBKBbiBQMX G2 "mHH2iBM o2`i 4 "mHH2iBM /2 HˆSJ1S- kyyd-

9eN- TTXkjN@k89X ?H@yy3k88y3

Quelques problèmes d"optimisation

Malle Nodet

1. Présentation du problème des flotteurs dérivants

Les physiciens océanographes qui désirent étudier les courants en profondeur

dans l"océan utilisent des flotteurs lestés. Ces flotteurs dérivent au gré du flot : leurs

trajectoires permettent de mieux connaître les courants profonds. Pour suivre les flotteurs au cours de leur déplacement, les physiciens utilisent un système de positionnement acoustique : plusieurs sources acoustiques émettrices sont fixées au fond de l"eau et envoient des signaux au flotteur (qui est équipé d"un récepteur). Sans entrer dans les détails, on peut énoncer le problème de positionnement des flotteurs comme suit :

On se donne

1. la position des sources,

2. les distances entre le flotteur et chacune des sources (avec une marge d"erreur

connue), on veut pouvoir calculer (avec la plus petite erreur possible) la position du flotteur. Ce problème peut se formuler comme un problème d"optimisation, c"est-à-dire un problème de minimisation d"une fonction bien choisie. On étudiera le problème en dimension 1, lorsque l"on peut faire explicitement tous les calculs. On commencera par formaliser le problème et on illustrera, sur des exemples, l"approche naÔve et l"approche par optimisation. Ensuite on regardera le problème en dimension 2, et c"est celui des physiciens. On ne pourra pas faire explicitement les calculs, mais on pourra faire des dessins, et éventuellement utiliser l"ordinateur pour calculer/dessiner et comparer là aussi l"approche naÔve avec l"optimisation. Enfin, on terminera en évoquant d"autres applications de l"optimisation, en particulier la prévision météorologique.Prérequis Pour étudier le problème en dimension 1, il suffit de savoir calculer le minimum d"un trinôme (avec ou sans dérivation), et de connaître la notion de distance entre deux points réels (valeur absolue). En dimension 2 les calculs ne sont plus faisables

et on se borne à illustrer, par des dessins et des calculs par ordinateur, les avantagesPour chercher et approfondir

(*) d"après l"AMIREM du 25 janvier 2006 (IREM de Nice). (**) Laboratoire J.-A. Dieudonné, Université de Nice. Laboratoire de Modélisation et de Calcul, Université de Grenoble 1. nodet@imag.fr http://www-lmc.imag.fr/lmc-edp/Maelle.NodetNodet-Texte 22/03/07 8:23 Page 239

de l"optimisation par rapport à la méthode naÔve. La programmation par ordinateurest très simple et nécessite simplement la notion de distance dans le plan. Pour lesautres applications (météo), les notions utilisées ne sont plus élémentaires, on se

limitera donc à donner les grandes idées des problèmes étudiés.

Illustration pardes programmes en Scilab

Le logiciel Scilab est gratuit et peut être téléchargé sur la page suivante : (il existe pour toutes les plates-formes : Linux, Windows et Mac OSX) Le programme Scilab pour la dimension 2 est disponible sur Internet à l"adresse

2. Étude du problème en dimension 1

2.1. Position du problème

Le problème peut se formuler ainsi : sur une ligne droite sont placées deux sources acoustiques (ou bien deux radars). Un objet est situé sur cette droite, sa position est inconnue. L"acoustique (ou bien les radars) nous donne les distances, entachées d"erreurs, entre chaque source et l"objet. L"ordre de grandeur des erreurs est connu. L"objectif est d"obtenir une estimation, la plus précise possible, de la position de l"objet.

Notations.On note S

1 et S 2 les sources, s 1 et s 2 leurs abscisses sur la droite (on aura pris soin de choisir un zéro, une unité et un sens à la droite...). On note Al"objet et ason abscisse. Les sources mesurent approximativement les distances AS 1 et AS 2

Les erreurs sont respectivement

e 1 et e 2 (nombres réels positifs) pour les sources S 1 et S 2 . Cela signifie que l"écart entre AS 1 et d 1 est au plus e 1 (de même pour e 2 (1)

2.2. Méthode nave

La méthode naÔve consiste tout simplement à chercher l"intervalle dans lequel se trouve l"objet. Avec (1) on obtient asde asde --£-- £

111222

ASAS.

111222

=-=-asdas d;;, 240

Nodet-Texte 22/03/07 8:23 Page 240

Ce qui donne graphiquement

(2) De la même façon on obtient le même type d"inégalités relatives à S 2 . La résolution, graphique ou non, nécessite alors de comparer les extrémités des intervalles ainsi construits.

On va donc poursuivre sur des exemples.

Exemple 1.On donne

(3)

Au vu des distances

d 1 et d 2 on peut dire que l"objet est entre les deux sources :

Ceci permet d"écrire

Le système d"inéquations (1) se réécrit donc ainsi : (4 )

Ce système s"interprète ainsi :

avaut s 1 +d 1

à e

1 près et avaut s 2 -d 2

à e

2 près. On appelle estimations de adonnées par S 1 et S 2 les valeurs s 1 +d 1 et s 2 -d 2 . Ici les estimations de avalent 5.3 et 6.7.

En utilisant (3) et (4) on obtient

ce qui donne

4363 ..££a

4363 5777..,.. ££££aa

asde sad e easdee--£- -£

1112 22

11112
,ssade sdeasdesdea 222

1111112 22

€+-££++--£,££-+sde 222
asasassa -=--= - 1122
sde sde 111
222
0531

1033 1======,.,,

asde easde deasde--£ 111
1111
1 1111
d deasdedesade sd

11111 111 11

1 1 €+ ou --££++--££-+easdesdeasde

1111111111

Quelques problèmes d'optimisation

Nodet-Texte 22/03/07 8:23 Page 241

Remarque.La méthode nave nous donne comme résultat un intervalle. L'objet peut se trouver n'importe où dans cet intervalle.

Exemple 2.On donne maintenant

Comme précédemment, l'objet est entre les deux sources et de la même façon on obtient

Exemple 3.Soit

Cette fois, l'objet n'est plus entre les deux sources, il est à l'extérieur, côté S 1 Les estimations de avalent cette fois s 1 -d 1 =-5.5 et s 2 -d 2 =-4.8, et on obtient

Remarques.

1.Les estimations de avalent s

1 +d 1 (si l'objet est à droite de la source S 1 ) ou s 1 -d 1 (s'il est à gauche) et s 2 +d 2 ou squotesdbs_dbs20.pdfusesText_26

[PDF] Modélisation et résolution de problèmes de décision et d

2MiB}+ `2b2`+? /Q+mK2Mib- r?2i?2` i?2v `2 Tm#@

HBb?2/ Q` MQiX h?2 /Q+mK2Mib Kv +QK2 7`QK

Gˆ`+?Bp2 Qmp2`i2 THm`B/Bb+BTHBMB`2>G- 2bi

Zm2H[m2b T`Q#HK2b /ˆQTiBKBbiBQM

JHH2 LQ/2i

9eN- TTXkjN@k89X ?H@yy3k88y3

Quelques problèmes d"optimisation

Malle Nodet

1. Présentation du problème des flotteurs dérivants

On se donne

1. la position des sources,

2. les distances entre le flotteur et chacune des sources (avec une marge d"erreur

Illustration pardes programmes en Scilab

2. Étude du problème en dimension 1

2.1. Position du problème

Notations.On note S

Les erreurs sont respectivement

2.2. Méthode nave

111222

111222

Nodet-Texte 22/03/07 8:23 Page 240

Ce qui donne graphiquement

On va donc poursuivre sur des exemples.

Exemple 1.On donne

Au vu des distances

Ceci permet d"écrire

Ce système s"interprète ainsi :

à e

à e

En utilisant (3) et (4) on obtient

4363 ..££a

4363 5777..,.. ££££aa

1112 22

1111112 22

1033 1======,.,,

11111 111 11

1111111111

Quelques problèmes d'optimisation

Nodet-Texte 22/03/07 8:23 Page 241

Exemple 2.On donne maintenant

Exemple 3.Soit

Remarques.

1.Les estimations de avalent s

Malle Nodet

2.2. Méthode nave