Algorithme d'optimisation
Les algorithmes d’optimisation cherchent à déterminer le jeu de paramètres d’entrée d’une
fonction donnant à cette fonction la valeur maximale ou minimale. On cherchera par exemple
la découpe optimale d’une tôle pour en fabriquer le plus grand nombre de boîtes de conserve
possible (ou d’un tissu pour en faire le plus grand nombre de chemises possibles, etc.). Cette
optimisation peut se faire sans contrainte ou sous contrainte, le second cas se ramenant au
premier dans le cas des fonctions dérivables par la méthode du multiplicateur de Lagrange
(et des fonctions non-dérivables par l’algorithme d’Everett).
Le problème est bien entendu insoluble en tant que tel si l’on ne connaît rien de la fonction (il
existe peut-être une combinaison très particulière de valeurs d’entrées lui donnant
ponctuellement une valeur extrêmement haute ou basse, qui pourrait échapper à l’algorithme.
Aussi existe-t-il plusieurs classes d’algorithmes liés aux différentes connaissances qu’on peut
avoir sur la fonction. Si celle-ci est dérivable, l’une des plus performantes est celle du gradient
conjugué.
Aucune méthode connue en 2004 (à part bien entendu l’énumération exhaustive ou l’analyse
algébrique) ne permet de trouver avec certitude un extremum global d’une fonction. Les
extrema déterminables sont toujours locaux à un domaine, et demandent souvent même en
ce cas quelques caractéristiques à la fonction, par exemple dans certains cas la continuité.
Les métaheuristiques sont une classe d’algorithmes d’optimisation qui tentent d’obtenir une
valeur approchée de l’optimum global dans le cas de problèmes d’optimisation difficile. Elles
ne donnent cependant aucunes garanties sur la fiabilité du résultat.
Bonjour, j'ai un exo dans un dm a faire , j'ai réussi a faire la figure a l'aide de geoplan mais
après pour démontrer, je bloque donc de l'aide serait la bienvenue merci d'avance.
Voici l'énoncé:
Dans le plan muni d'un repere orthonormal(O, i, j) , C désigne le cercle de centre O et de
rayon 1.
On note A et A' les points de coordonnées respectives (1;0) et (-1;0). La droite d coupe le
cercle C en M et M'.
On note x l'abscisse du point H, comment choisir x pour que l'aire du triangle AMM' soit
maximale.
I/
1.a/ Quelles sont les valeurs possibles de x?
b/ Démontrer que l'aire AMM' est égale à (1-x)Racine1-x²
2. On note f la fonction définie sur l'intervalle [-1;1] par f(x)= (1-x)racine de1-x².
a/ Démontrer que f est dérivable sur ]-1;1[ et que pour tout x de cet intervalle, f'(x)=(f(-
1+h)-f(-1))/h.
b/ Calculer la limite de (f(-1+h)-f(-1))/h lorsque h tend vers 0 à droite.
c/ Démontrer que f est dérivable en 1, préciser f'(1).
d/ Dresser le tableau de variation de la fonction f.
Voila, la première question je l'ai faite, les valeurs de x possible sont dans [-1;1].
Pour la b/ je crois qu'il faut s'aider du théorème de Pythagore mais je bloque, je tombe sur
de drole de résultat.
En ésparant avec de l'aide et non les réponses merci d'avance.
1/ Cliquer sur l'icone repere puis creer successivement;
-Les points A(1;0), A'(-1;0) et le cercle C de centre O passant par A;
-H point libre sur le segment [AA'];
-le droite d perpendiculaire à (AA') passant par H;
-les points M et M' intersection de d et C et le triangle AAM'.
Masquer le droite puis créer:
-l'abscisse x du point H et l'aire a du triangle AMM'.
Enfin, créer l'affichage avec deux décimales des variables x et a.
2/ Sans fermer les figure:
-cliquer sur fichier, nouvelle figure, créer numérique, variable réelle x, puis variable réelle
libre a.
-Créer le point S(x;a) dans le repère Roxy.
CLiquer sur l'icone repère, puis piloter, importer, fenetre, mosaique, afficher, selection
trace, enfin sur l'icone T. Rendre le point M mobile.
Problème des seaux
3 litres 5 litres 8 litres
On dispose de trois seaux de respectivement 3, 5 et 8 litres. Initialement, le seau de 8
litres est complètement rempli et les deux autres sont vides.
Transvaser x litres de A dans B de contenance y litres correspond à verser le contenu
de A dans B :
- si x>y on rempli B à ras bord et on laisse le reste x-y dans A ; on ne peut pas verser
moins de x litres dans B.
- si x<y on vide totalement A dans B et B n’est pas totalement rempli.
- si x=y on vide totalement A dans B et B est totalement rempli.
Un transvasement ne peut mettre en jeu que 2 seaux. (Si l’on doit vider un seau dans 2
autres, cela correspond à 2 transvasements).
Objectif :
On cherche à trouver le nombre minimum X de transvasements à effectuer pour
arriver à la configuration suivante :
- seau de 3 litres vide
- 4 litres dans le seau de 5 litres
- 4 litres dans le seau de 8 litres
Question : Trouver X en utilisant l’algorithme de Dikjstra (la méthode doit
pouvoir s’adapter à un nombre n de seaux…)
Corrigés : PROBLEME DES SEAUX
Modélisation:
On modélise ce problème par un graphe arborescent dont chaque arc est de longueur
1.
On note les sommets avec 3 chiffres correspondant au nombre de litres contenus dans
les seaux de respectivement 8, 5 et 3 litres. On cherche donc la manière d’arriver au
nombre 440 avec le nombre minimal d’étapes.
Pour cela on remplit en parallèle un tableau de marques provisoires et définitives. On
attribue 3 chiffres (a, b, c) à chaque sommet :
a=numéro du sommet représentant le nombre de litres dans chaque seau.
b=marque.
c=dernier sommet par lequel on est passé pour arriver à a.
Voici le début du tableau jusqu’à l’étape 4. Dans le cas des trois seaux, la résolution
complète de l’algorithme comporte 7 étapes mais la méthode est exactement la même
que pour les 4 premières étapes.
Numéro d’étape Liste proviso ire Liste définitive
0 - (800, 0, -)
1 (350, 1, 800) (503, 1, 800) (503, 1, 800)
2 (350, 1, 800) (530, 2, 503) (053, 2, 503) (350, 1, 800)
3 (530, 2, 503) (053, 2, 503) (323, 2, 350) (530, 2, 503)
4 (053, 2, 503) (323, 2, 350) (233, 3, 530) (053, 2, 503)
Et ainsi de suite jusqu’à ce que l’on arrive au point 440 dans la liste définitive.
Au fur et à mesure que l’on avance dans le remplissage du tableau, on peut construire
le graphe ; pour éviter d’avoir à dessiner un arbre trop lourd, on choisit de ne
représenter que les étapes de la liste définitive :