[PDF] [PDF] Cours Optimisationpdf Département de Génie

View - Download [PDF] Cours Optimisationpdf

Previous PDF

Next PDF

SommaireI.1IntroductionI.2DéfinitionI.3Exemple de problème de programmation linéaireI.3.1Problème de productionI.3.2Problème de MélangeI.3.3Problème dedécoupeI.3.4Problème de transportI.4Résolution du problème par la méthode SimplexeI.4.1Bases et solutions de base des programmes linéairesI.4.2Recherche d"une solution optimaleI.5Tableaux du simplexe et procédure de calculI.6Recherche d"une solution réalisable de base initialeI.7Initialisation de l"algorithme du simplexe (la méthode à deux phases)Chapitre 2:Optimisation non-linéaireII.1IntroductionII.2Le GradientII.3Le HessienII.4Condition nécessaire pour l"existence d"un minimum localII.5Conditions suffisantes pour l"existence d"un minimum localII.6Fonctions convexesII.6.1Fonctions convexesII.6.2Minimum de fonctions convexesII.7Méthodes de rechercheunidimensionnelleII.7.1Méthodes du premier ordre (dichotomie)II.7.2Méthodes du second ordre (Méthode de Newton)II.8Méthodes du gradientII.9Méthodes des directions conjuguéesII.9Méthode de NewtonII.10Méthodes quasi-NewtonChapitre III:Optimisation avec contraintesIII.1IntroductionIII.2Problème avec contraintes d"égalitéIII.2.1Le théorème de LagrangeIII.2.2Définition du lagrangienIII.2.3Condition nécessaire du secondordreIII.2.4Condition nécessaire du second ordreIII.3Problème avec contraintes d"inégalité (conditions de KKT)III.4Conditions de KKT pour un problème avec limitations d"égalité et d"inégalitéIII.5Méthodes de pénalitéIII.5.1PrincipeIII.5.2Pénalité extérieureIII.5.3Pénalité intérieureIII.6Programmation quadratique séquentielleMéthodes d"optimisation stochastiquesIV.1L"algorithme génétiqueIV.1.1Le codageIV.1.2L'opérateur desélectionIV.1.3L'opérateur de croisement ou crossover

IV.1.4L'opérateur de mutationIV.1.5L'opérateur de remplacementIV.2La méthode d"essaim particulaireIV.2.1Configuration de la méthodeIV.2.1.1Nombre de particulesIV.2.1.2Topologie du voisinageIV.2.1.3Coefficients de confianceIV.2.1.4Vitesse maximale et coefficient de constrictionIV.2.1.5Facteur d"inertieIV.2.1.6Initialisation de l"essaimIV.2.1.7Critères d"arrêtIV.2.2Algorithme de synthèse

I-1 IntroductionL"optimisation(programmation)linéaireest une technique mathématique permettant dedéterminerla meilleure solution d"un problème dont les données etles inconnues satisfont à uneséried"équations et d"inéquations linéaires. La programmation linéaire a été formuléeparGeorge BernardDantzigen 1947 et connaît un développement rapide par suite de son applicationdirecte à la gestionscientifiquedes entreprises. Le facteur expliquant l"essor de laprogrammation linéaireest laconstruction d"ordinateurs puissants qui ont permis de traiter les problèmesconcrets de taille trèsgrande. On l"applique surtout en gestion et en économieappliquée. On peut citer les domainesd"application de laprogrammation linéaire quisont : les transports, les banques, les industries lourdesetlégères, l"agriculture, leschaînes commerciales, la sidérurgie, et même le domaine des applicationsmilitaires.Les méthodes de résolution sont la méthodedu simplexe, méthode duale du simplexe,méthodesdes potentiels, méthode lexicographique et des méthodes récentes appeléesméthodes des pointsintérieurs.I.2DéfinitionUn programme linéaire (PL) est un modèle mathématiquequ"onpeut écrire sous la forme :Maximiser ou minimiser la fonction objectif :(I.1)Sous les contraintes(I.2)Et(I.3)oùaij, biet cisont des constantes connues.Les contraintessont appelées contraintes de non-négativité.Définition1.On appellesolutiond"un problème de programmation linéaire tout vecteurxqui satisfaitles contraintes(I.2).Une solution est appeléesolution réalisablesi elle vérifie les contraintes de non-négativité(I.3).Dansle cascontraire, on dit que la solution n"estpas réalisable.Définition2.Une solution réalisable est unesolution optimales"il n"existe pas d"autressolutionsréalisables qui fournissentune plus grande valeur de la fonctionobjectif. À noter que dans un problèmepossédant des solutions réalisables,il se peut que la valeur optimale de la fonction objectif soit infinie.Dans cecas, on parle de solutionoptimale infinie.I-3 Exemple de problème de programmation linéaireI-3-1Problème de production

Une entreprisefabrique des chaises et des tables à l"aide de deux machines A et B. Chaqueproduit passe obligatoirement par les deux machines. Pour produire unechaise, il faut 2 heures demachine A et1heure de machine B. Pour produireune table, il faut1heure de machine A et 2 heuresde machine B.L"entreprise réalise un bénéfice de 3DZD.-sur chaque chaise et de 4DZD.-surchaque table. Les deuxmachines A et B sont disponibles12 heures par jourau maximum.Le problème consiste à savoir combien de chaises et de tables il fautfabriquer pour maximiser lebénéfice. Le tableau suivant montre :1. le nombre d"heures nécessairespour produire chaque table et chaquechaise par machine ;2. le nombre total des heures disponibles ;3. le profit pour chaque unité de chaise et de table produite.MachineProduitDisponibilitéChaiseTableA2112B1212Bénéfice parunité34Il s"agit à présent de formuler mathématiquement le problème.Notons respectivement parx1etx2le nombre de chaises et de tables quidoit être produit par jour.Lebénéfice pour une chaise étant de3DZD.-et celui pour une table de4DZD, le bénéficejournalier estdonc donné par la fonction objectif :Il faut formulermaintenant lescontraintes. Puisquele temps où les machines peuvent fonctionnerest limité, on ne peut pasaccroître la production indéfiniment. Les machines A et B ne peuvent pasfonctionner plus de 12 heures par jour. On sait que pour produire une chaise,il faut 2 heures demachine A alors que pour une table il n"en faut qu"une.La contrainte concernant la machine A est donc :De même, une chaise requiert 1heure de machine B, tandis qu"une tableen demande 2. Lacontrainte concernant la machine B, avec la même duréemaximale de 12 heures par jour, est donnéepar :De plus, comme on ne peut pas produire de quantités négatives, il fautajouterencore deuxcontraintes de non-négativité :Le problème consiste donc à trouver les valeurs des variablesx1etx2qui maximisent le bénéficejournalier (fonction objectif) tout en satisfaisant les contraintes.En résumé, le problème s"écrit sousla forme :MaximiserSouscontraintes

EtReprésentation graphique du problèmeL"exemple décrit ci-dessus peut être représenté graphiquementpuisqu"il ne contient que deuxvariables. Avant de rechercher lasolution du problème, représentons sur la figureI.1 larégion despoints(x1; x2) qui satisfont les quatre contraintes simultanément. Les deuxcontraintes de non-négativitéindiquent que cette région setrouve dans le premier quadrant. En ce qui concerne les deuxautresinégalités, on étudie les équations de droite :La première est une droite passant par les points (6 ;0) et (0 ;12), tandisque la deuxième passepar ( 12 ;0 ) e t (0 ;6). L"i nte rsect ion de ces deuxdroites est le point ( 4 ; 4) . La r égi on des pointssatisfaisant les quatreinégalités est la région hachurée sur la figureI.1. Elle a pour sommetsles points(0 ;0), (0 ;6), (4 ;4) et (6 ;0).Pour résoudre le problème de programmation linéaire, nous devonstrouver le ou les points appartenantà ce polyèdre convexe et maximisantla fonction objectif :. Pour une valeur donnéedez, il s"agit d"une droite. En attribuant différentes valeurs àzonobtient autant de droites parallèles(quelle que soit la valeur dez, lapente reste inchangée et vaut-3/4).Puisque le but est de maximiser la fonction objectif, la recherche dela solution optimale se fait entranslatant la droitedemanière à ce que l"ordonnée à l"origine soit la plus grande. Deplus,poursatisfaire les contraintes, l"intersection de cette droite avec la régionhachurée doit être nonvide.Sur la figureI.1, la fonction objectif est tracée pour trois valeurs dez.La première valeur estz1= 18.Cette valeur n"est pas optimale puisquel"onpeut encore déplacer la fonction objectif en gardant despoints communsavec la région hachurée. La deuxième valeurz2= 28. Il s"agit dela valeur optimalepuisque l"ordonnée à l"origine est la plus grande possibletout en gardant un point d"intersectionavec larégion hachurée.La troisième valeurz3= 38ne peut pas être optimale puisqu"il n"y aplus de point en commun entre ladroite et la région hachurée.Ainsi dans cet exemple, la solution optimale se situe à l"intersection desdeux droiteset. Il s"agit d"une solutionunique donnée parx1= 4etx2= 4. Celasignifie que le bénéfice estmaximal lorsqu"on produit 4 chaises et 4 tables par jour. Ce bénéfices"élèveàz = 3(4) + 4(4) = 28par jour.À noter que la solutionoptimale est l"un des sommets du polyèdre(point extrême).

Figure I.1:Région réalisable et fonction objectif pourz1= 18, z2= 28etz3= 38I-3-2Problème de Mélange. Il faut mélanger trois gaz de telle manière que le gaz mixte soit le plusbonmarché que possède un pouvoir calorifique entre plus de 1700 et 2000 k. cal/ m3et un taux desulfure au plus de 2,8 g/ m3. Indications sur les trois gaz :GazPouvoir calorifiquek. cal/ m3Taux de sulfureg/ m3Prix en DA110006100220002250315003200Ecrire le modèle mathématique de ce problème.Formulation du problèmeVariables :x1, x2et x3sont lesnombres en m3du 1er,2èmeet3èmegaz à fabriquerrespectivement.Fonction objectif à maximiser :La fonction objectiveZcorrespond au profit total:On cherche doncContraintes :iPouvoir calorifiqueiTaux de sulfureiPositivité des variablesI-3-3Problème de découpe. Une usine a reçu des plaques de métal d"une largeur de 200 cm et d"unelongueur de 500 cm. Il faut en fabriquer au moins 30 plaques de largeur de 110 cm , 40 plaques delargeur de 75 cm et 15 plaques de largeur de 60 cm. Donner le modèle mathématique pour que lesdéchets soient les plus petits possibles .Formulation du problèmeUne plaque de 200 cm de largeur peut être découpée de cinq façons :1. une plaque de 75 cm et deux plaques de 60 cm. Les déchets seront de 05 cm.

2. une plaque de 110 cm et une plaque de 75 cm. Les déchets seront de 15 cm.3. une plaque de 110 cm et une plaque de 60 cm. Les déchets seront de 30 cm.4.trois plaques de 60 cm. Les déchets seront de 20 cm.5.deux plaques de 75 cm. Les déchets seront de 50 cm.Variables :x1,x2,x3,x4etx5sont lesnombresde plaques a découper parla1ere,2ème,3ème,4èmeetla 5èmefaçonsrespectivement.Fonction objectif àminimiser :La fonction objectiveZcorresponddéchettotal:On cherche doncContraintes :iPlaques de largeur 110cmiPlaques de largeur 75cmiPlaques de largeur 60cmiPositivité des variablesI-3-4Problème de transport.Il s"agit ici d"un problème que l"on peut résoudre par la programmationlinéaire, c"est-à-dire unproblème de transport. Cetype de problèmese définit comme suit.Connaissant les quantités disponibles de chacune des unités de production,les quantités requisesaux points de distribution et le coût de transport d"unbien d"une usine vers un point de vente, il s"agitde déterminer le plan detransport optimal, c"est-à-dire de déterminer les quantités de biens que chaqueusine va envoyer vers chacun des points de vente afin que le coût de transporttotal soit minimum. Onsuppose qu"il est possible d"expédier des produits den"importe quelle origine vers n"importe quelledestination.L"exemple ci-dessous est le cas d"une fabrique de conserves qui expédiedes caisses vers sesdépôts. Nous voulons que le plan d"expédition des caissesminimise le coût total de transport des usinesauxdépôts. Pour simplifier,supposons qu"il y a deux usines et trois dépôts. L"offre des usines et lesdemandes des dépôts sont les suivantes (en nombre de caisses) :Usine 1: 350dépôt 1: 200Usine 2: 450dépôt 2: 300dépot 3: 50Les coûts de transport de chaque origine vers chaque destination sontdonnés dans le tableau ci-dessous(enDApar caisse) :UsinesDépôts12312517162241814

Ainsi, le coût pour transporter une caisse de l"usine 1 au dépôt 1 est de25, le coût pour transporter unecaisse de l"usine 2 vers le dépôt 1 est de 24,et ainsi de suite.Ce problème peut se formuler sous laforme d"un problème de programmationlinéaire. Notons parcijle coût de transport d"une caisse del"origineivers la destinationj. Nous avons donc, d"après le tableau précédent :Soitaila quantité de caisses disponibles à l"origineietbjcelle requise àla destinationj.Nous pouvons représenter le problème sous forme d"un diagramme (figureI.2). Les lignes qui relientles usines aux dépôts peuvent être considéréescomme des routes. Ony indique leur coût de transportunitaire respectif.À noter que le nombre de caisses disponibles doit être supérieur ou égalau nombre de caisses requises :Dans le cas contraire, le problème n"a pas de solutions réalisables.Sixijreprésente le nombre de caisses expédiées de l"origineivers ladestinationj, le coût total del"expédition se traduit alors par l"équation :C"est la fonction objectif à minimiser.

Figure I.2 :Coût de transport unitaire des usines aux dépôtsComme il est impossible d"expédier plus de caisses d"une origine donnéequ"il n"y en a de disponibles,nous sommes confrontés auxdeux contraintes :

De plus, il faut approvisionner chacun des trois dépôts avec la quantitérequise, ce qui nous donne troisnouvelles contraintes :Comme il n"est pas possible d"expédier des quantités négatives, nous avonsencore les six contraintesdenon-négativité suivantes :Finalement, le programme linéaire à résoudre est :Comme ce problème présente plus de deux variables, nous ne pouvonspas le résoudregéométriquement.I.4Résolution du problème par la méthode Simplexe:La méthode de simplexeest l"outil principal de résolution des problèmes de programmation linéaire.Elle consisteà suivre un certain nombre d"étapes avant d"obtenir la solutiond"un problème donné. Ils"agit d"une méthode algébrique itérative qui permetde trouver la solution exacte d"un problème deprogrammation linéaire en unnombre fini d"étapes.La forme matricielle permet de représenter un problème de programmationlinéaire sous une formeplus concise.(I.4)(I.5)

Oùcest un vecteur-ligne de dimension (1 × n),xun vecteur-colonne dedimension (n×1),Aunematrice de dimension (m×n),bun vecteur-colonnede dimension (m× 1) e t 0 l e vecte ur nul àncomposantes.Un problème de programmation linéairepeut se présenter sous différentesformes. En voici laterminologie.Forme canoniqueSi la fonction objectif doit être maximisée et si toutes les contraintes sont des inéquations dutype,on dit que le programme linéaire se présente sous une formecanonique. Matriciellement, un problèmede programmationlinéaire se présente sous sa forme canonique de la manière suivante :(I.6)(I.7)(I.8)À noter que toute contrainte peut être transformé sous forme canonique.Forme standardUn problèmede programmation linéaire se présente sous sa forme standard sitoutes les contraintessont des équations. La fonction objectif doit égalementêtre maximisée. Sous forme matricielle, laforme standard s"écrit :(I.9)(I.10)(I.11)Transformation minimisation-maximisationTout problème de minimisation peut être transformé en un problème équivalentde maximisation. Eneffet, le problème :est équivalent à :Variablesd"écartLa procédure que nous allons développer pour trouver la solution d"un problèmede programmationlinéaire s"appelle la méthode du simplexe. Cette méthodeexige que le programme linéaire soit sousforme standard. Pourcette raison, il faut transformer les inégalités rencontrées en égalités. Cettetransformation se fait simplement en introduisant des variables non-négatives( qui vérifie nt lescontraintes de non-négativité) appelées variables d"écart.Si les contraintes sont du type :Nous introduisons une nouvelle variableet écrivons :De même, nous pouvons être contraints de transformer les contraintes dela forme :en uneégalité en soustrayant cette fois une variable d"écart. Nous écrivons alors :

Dans la fonction objectif le réelcjest souvent appelé le "prix" associé à la variablexj. En assignantunprix nul àchaque variable d"écart, la transformation des contraintesen un système d"équationslinéaires nechange pas la fonction objectif.Exemple I.1Résoudre le programme linéaire suivant à l"aide de la méthode algébrique:Maximiser la fonction objectif:2147xxZSoumise aux contraintes linéaires suivantes:360351041402212121xxxxxxEt0,021mmxxEn introduisant les variables d"écart dans chaque contrainte, on obtient la forme standard du modèle:360351041402521421321xxxxxxxxx0,0,0,0,054321mmmmmxxxxx5432100047maxxxxxxZFonction objectif reste inchangéeI.4.1Bases et solutions de base des programmes linéairesPour développer la méthode du simplexe, nous avancerons les hypothèsessuivantes :1.,c"est-à-dire que le système d"équations est compatible,2., où m est le nombre de contraintes.La seconde hypothèse permet de former, à partir deA, une (m×m) sousmatriceBnon-singulière. CettematriceBpeut être formée par n"importequel ensemble demcolonnes linéairement indépendantes deA. Les colonnesdeBseront notéesb1, b2, . . ., bm(à ne pas confondre avec le second membreb). LamatriceBest appelée matrice de base puisqu"elle est formée demvecteurs linéairement indépendants.Sans restreindre la généralité, on peut supposer que les colonnes deAontété ordonnées de manière àpouvoir écrireAsous la forme, avecBde dimension (m×m) la matrice de base etNdedimensioncontenant les colonnes deAqui n"appartiennent pas àB. Le vecteurxpeutêtre partitionné de façon analogue en posant. Les variablesxBsont appelés variables de base etles variablesxNles variables horsbase.Finalement le vecteurcpeut lui aussi être partitionné de la même manièreenc = (cB, cN).Le programme linéaire (I.9)-(I.11) peut donc être reformulé de la manièresuivante :(I.12)(I.13)

(I.14)La contrainte (I.13) peut s"écrire de manière équivalente :et puisqueBest non-singulière (inversible) :(I.15)Lorsque toutes les variables hors base sont nulles,, (I.15) devientOn appelle solution de base la solution :Lorsqueet, on parle desolution réalisable de base.Exemple I.2Soit le problème de programmation linéaire suivant :MaximiserSous contraintesEtCe problème peut se mettre sous forme standard enintroduisant lesvariables d"écartx4etx5:MaximiserSous contraintesEtSous forme matricielle, on obtient donc :,,,Formons à partir deAune matrice de baseBen prenant parexemple les colonnes 2 et 4, dans cet ordre:Il s"agit bien d"une base puisqueBest non-singulière ().À noter que dans notre cas, on a :b1= a2(2ecolonne deA)b2= a4(4ecolonne deA).Acette matrice de base correspond une solution de base donnée par :Dansnotre cas :

Les autres variables étant nulles,x1= x3= x5= 0.Cette solution de base n"est pas réalisable pour lasimple raison quexB1= x2=-5viole la contrainte de non-négativité.Dans cet exemple, il est trèsfacile de trouver une base qui fournisse unesolution réalisable de base. Eneffetles colonnesa4eta5forment une basequi est l"identité :Ici,b1= a4etb2= a5.La solution de base est le vecteurbpuisque :Commebdoit être non-négatif lorsque le problème est présenté sous saforme standard, la solution estune solution réalisable de base.Z a pour valeur: z = 0· 16 + 0 · 20 = 0I.4.2 Recherche d"une solution optimaleRésultat4.1Tout point extrême est unesolution réalisable de base.Ainsi pour trouver la solution optimale, il suffit d"examiner les points extrêmes ou de manièreéquivalente les solutions réalisables de base.À la solution réalisable de base initiale correspond une valeur de la fonction objectifz. Le but estd"améliorer la valeur de la fonction objectif en l"évaluant en un point extrême adjacent. Pour cela, étantdonné une baseB, on trouve un point extrême adjacent (nouvell e solut ion réalisabl e de base ) enéchangeant l"une des colonnes de labase (bi) contr e une colonneajqui n"est pas dans la base.Cependant, en faisant cet échange, il faut s"assurer que la solution de base reste réalisable et que lavaleur de la fonction objectif augmente (ou du moins ne diminue pas).Il y a donc deux règles à suivre pour cet échange. La première consiste à déterminer quelle colonneajdeA(à laquelle correspond une variablexj) doit entrer dans la base pour améliorer la fonction objectif.La seconde consiste à sélectionner l"une des colonnesbiqui doit quitter la base de manière à ce que lanouvelle solution de base reste réalisable.Nous développons ici les critères d"entrée et de sortie de la base pourobtenir une nouvelle solutionréalisable de base qui améliore la valeur dela fonction objectif. Il restera ensuite à déterminer si lanouvelle solutionréalisable de base est optimale ou non.Pour développer ces deux critères, nous reformulons le programme linéaire(I.12)-(I.14) sous la forme suivante :(I.16)(I.17)(I.18)oùJest l"ensemble des indices des variables hors base.CommeBest une base formée de m colonnes linéairement indépendantes,toute colonneajde lamatriceApeut s"écrire comme une combinaisonlinéaire des colonnes de la matriceB. On peut doncécrire :On peut également écrire (puisqueBest inversible) :(I.19)

AvecDéfinissons encore une nouvelle variablezjpar :(I.20)En utilisant (I.19), les contraintes (I.17) s"écrivent :(I.21)Introduisons (I.21) dans la fonction objectif (I.16) :Finalement, en utilisant (I.20), la fonction objectif s"écrit :D"où(I.22)Lorsqu"on obtient une solution réalisable de base, les valeurs des variablesxjsont nulles pour toutindice. Dans ce cas, la valeur de la fonctionobjectif est.Le but est d"améliorer au maximum cette valeur dez. Dans l"équation(I.22), les variablesxjsont non-négatives et la sommation est précédée dusigne négatif. C"est donc la variablexj, au plus petit, quiaméliorera le plus la valeur de la fonction objectif. Le critère d"entrée dansla baseest donc le suivant.• Critère d"entrée dans la baseLe vecteurakqui doit entrer dans la base correspond à la variable horsbasexkpour laquelle(zj-cj) a laplus petite valeur négative :Ilreste encore à déterminer quel vecteur de base doit quitter la base.Pour cela, reprenons lasolution debase (I.21) :

Toutes les variables hors base sont nulles saufxkqui devient une variablede base. Commexkest unenouvelle variable de base, elle sera notée.Ainsi la nouvelle solution de base, notées"écrit :La ièmecomposante de cette solution de base est :(I.23)Pour que cette solution de base soit réalisable, il faut que les variables debase soient non-négatives,c"est-à-dire :(I.24)Les contraintes de non-négativité (I.24) sont évidemment satisfaites pourles variables qui ont unyiknégatif ou nul. En revanche, en ce qui concerneles variables qui ontyikpositif, il faut que :Pour ne pas violer lescontraintes de non-négativité. Cette dernière inégalitédevant être valable pourtout i tel queyik> 0,doit être égale au pluspetit rapportxBi/yik. Supposons que ce plus petit rapportsoit associé à larèmevariable de basexBr.Alors en posant :Toutes les contraintes de non-négativité dans (I.24) sont satisfaites et par(I.23) :ce qui permet de sortirxBrde la base. Nous avons ainsi obtenu le critèrepour sortir une colonnebrde labase.•Critère de sortie de la baseSoit le vecteurakqui doit entrer dans la base. Le vecteurbrassocié à lavariablexBrqui doit sortir de labase est celui qui satisfait :Résultat 4.2La solution réalisable de base associée à la baseBest optimale si :pour chaque colonne ajdeAqui n"est pas dans la base.Remarque 4.1Il se peut que la solution optimale d"un problème de programmation linéaire possédantune solutionréalisable de base soit infinie.• Étapes de la méthode du simplexeEtape 1:Rechercher la solution optimale à partir d"une solution réalisablede base :Etape 2:Examiner les (zj-cj) pour toutes les colonnesajqui ne sontpas dans la base. Si tous les, passer à l"étape 6, sinon passerà l"étape 3.

Etape 3:S"il existe un (zj-cj) négatif pour lequel il n"y a pas d"élémentspositifs dansyj, arrêter larecherche puisque la solution optimale est infinie.Sinon, choisir le vecteur (et donc la variable) associée à la valeur la plusnégative des (zj-cj) pourentrer dans la base :Etape 4:Déterminer le vecteur (et donc la variable) qui sort de la base àl"aide du critère :Etape 5:Établir la nouvelle base, calculer la nouvelle solution réalisablede base et la nouvelle valeurde la fonctionobjectif.Retourner à l"étape 2.Etape 6:La solution réalisable de base courante est la solution optimale.La solution optimale n"estpas unique s"il existe un (zj-cj) nul pour unvecteurajqui ne se trouve pas dans la base.I.5 Tableaux du simplexeet procédure de calculLorsque l"on calcule la méthode du simplexe à la main, il est préférable detravailler avec un tableauqui contient toutes les données nécessaires. Àchaque itération correspond un nouveau tableau prenantla forme suivante :

Tableau 1:Tableau initial du simplexeLa première colonne indique les prixcBcorrespondant aux vecteurs debase. La deuxième colonneindique quels vecteurs se trouvent dans la base.Les vecteursbi, i = 1, . . .,mreprésentent les mcolonnes de la matrice de baseB. Si la matrice de base est formée des colonnesa1,a3eta4par exemple,on écriraa1à la place deb1,a3à la place deb2eta4à la place deb3.Latroisième colonne du tableaufournit la solution réalisable de basexBsaufà la dernière ligne où l"on trouve la valeur dezpour lasolution réalisablede base. Les colonnes suivantes indiquent les valeurs desyjpour tous lesvecteurs deA. La première ligne donne les prix associés aux variables et ladernière ligne donne les (zj-cj).Voyons comment utiliser les informations données par le tableau poureffectuer les différentes étapesde la méthode du simplexe.En premier lieu, examinons les éléments de la dernière ligne(zj-cj)correspondant aux vecteurs horsbaseaj. Si tous les, la solutionest optimale. S"il existe unpour lequel iln"existe pas d"élémentspositifs dansyj(la colonne au-dessus de (zjcj)), la solution est infinie. Sitel n"est pas le cas, nous choisissons le plus petit. Appelons lacolonne correspondantek.Ainsiakentre dans la base. Le vecteur qui doitsortir de la base est choisi par le critère :Cela signifie que le vecteur de larèmeligne dans la colonne "vecteurs debase" est remplacé parak. Lesvaleurs nécessaires au calcul de ce critère sontfaciles à trouver, puisque les valeursxBise trouvent en

regard des valeursyik.Il faut à présent tracer un nouveau tableau.Al"intersection de la colonneakquientre dans la base et du vecteurbrqui en sort, se trouve le termeyrkqui est appelé lepivotde latransformation. La colonneakest appeléecolonne-pivotet le vecteurbrligne-pivot. Ilest utiled"encercler dansle tableau le pivot ainsi que la colonne-pivot et la ligne-pivot. Établissonsles formulesde transformation en ajoutant le symbole(ˆ)au-dessus desnouvelles valeurs afin de les distinguer desanciennes. Les nouvelles valeursdes variables de base se calculent facilement à partir des anciennes.En effet, nous avons vu que la nouvelle variable qui entre dans la base est(I.25)En substituant(I.25) dans (I.23), nous obtenons :(I.26)Développons à présent les formules de transformation afin de calculer lestermes. Toute colonneajdeApeut s"exprimer comme une combinaisonlinéaire des anciens vecteurs de base :(I.27)Or le vecteuraka remplacé le vecteurbrdans la base. De (I.27), enposantj = k, on déduit que :(I.28)Substituons (I.28) dans (I.27) :(I.29)où. Si l"on compare les deux égalités dans (I.29),on trouve :(I.30)(I.31)Calculons les nouvelles valeursen utilisant la définition :(I.32)avec,et. En utilisant lesrésultats (I.30) et (I.31),l"équation (I.32) devient :(I.33)À noter que la sommation peut se faire sans la restrictionpuisquele terme correspondant à cetindice est nul :Ainsi, l"équation (I.33) peut s"écrire :ou de manière équivalente :(I.34)Enfin,déterminons, la nouvelle valeur de la fonction objectif :(I.35)Avec (I.25), (I.26) et le fait que,,, on obtient :

Dans la sommation, le terme pourétant nul on peut omettre larestriction. On obtient alors:Puisqueetz, on a finalement :(I.36)Exemple I.3Soitl"exemple suivantTout d"abord, passons ce programme linéaire sous forme standard.Appliquons les différentes étapes de la méthode du simplexeEtape 1:Le tableau initial du simplexe est donné dans le tableau1.

Tableau 2 : Tableau initial du simplexeLa base B est formée par les vecteursa3eta4et correspond à la matriceidentité. La solution réalisablede base correspondante est donnée parLes termes (zj-cj) correspondant aux vecteursde base sont nuls et ceux correspondant aux vecteurshors base s"obtiennentencalculant :Enfin, la fonction objectif a pour valeur :Etape 2:Dans le tableau 2, nous voyons qu"il reste des (zj-cj) négatifs. Nous passons donc à l"étape3.Etape 3:Les vecteursyjsitués au-dessus des (zj-cj) négatifs n"ont que deséléments positifs. Uneamélioration de la fonction objectif est donc possibleet nous cherchons le vecteur qui doit entrer dansla base.La plus petite valeur négative des (zj-cj) est(-4)obtenue pour (z2-c2).Ainsi,k = 2et le vecteura2entre dans la base. La colonne correspondanteest la colonne-pivot qui a été encadrée dansle tableau 2.Pour connaître levecteur qui sort de la base, nous passons à l"étape 4.Etape 4:Examinons les rapportsavec:

etLe plus petit rapport est 6 et correspond à. Ainsi,et levecteura4(correspondant à lavariable) sort de la base. La lignecorrespondante est laligne-pivotqui a été encadrée dansle tableau 2. Ilreste à établir le nouveautableau à l"étape 5.Etape 5:Puisquea2remplacea4dans la base, on remplacepardans lacolonnecB. Tous les autres éléments du nouveautableau se calculent à partir des formules (I.30) et(I.31). Commençonspar calculer leséléments de la ligne-pivot à l"aide de (I.31)Calculons à présent la première ligne à l"aide de (5.30) :. À noter queest une constante pourcette ligne.Il ne reste plus qu"à calculer les éléments de la dernière ligne :Le tableau 3 représente le nouveau tableau du simplexe.Avant de retourner à l"étape 2, mentionnonsque certains calculseffectuéslors de l"étape 5 ne sont pas nécessaires. Eneffet les (zj-cj)correspondantaux vecteurs dans la base sont forcément nuls. Le vecteur qui entre dansla base devientun vecteur unitaire avec pour composantes : 1 à la placede l"élément pivot et0ailleurs. Le vecteur qui

reste dans la base n"est pasmodifié. De plus, la ligne-pivot est très facilement calculée puisque chaqueélément de cette ligne est divisé par l"élément pivot. Nous appliquerons cesremarques dans les calculssuivants.

Tableau 3 : Tableau du simplexe obtenu après une itérationEtape 2:Dans le tableau3, il reste un (zj-cj) négatif. Par conséquent,nous passons à l"étape 3.Etape 3:Seulz1-c1=-1est négatif et tous les éléments dey1sont positifs.Par conséquentk = 1etle vecteura1entre dans la base ; passons à,l"étape 4.Etape 4:Calculons les rapports:Le plus petit rapport correspond à, d"où. Le vecteura3sort donc de la base.Calculons le nouveau tableau à l"étape 5.Etape 5:Puisquea1entre dans la base pour se substituer àa3, on remplacepar.L"élément pivot étant, tous les éléments de laligne-pivot sont divisés par 3/2. Le vecteura1qui entre dans la base devientle vecteur unitaire avec pour composantes : 1 à la place de l"élémentpivotet 0 ailleurs. Le vecteura2qui reste dans la base n"est pas modifié. De pluset, puisquea1eta2se trouvent dans la base. Lesautres éléments se calculent à l"aide de(I.30) comme suit :

Tableau 4 : Tableau du simplexe obtenu après deux itérations

Retournons à l"étape 2.Etape 2:Tous les (zj-cj) correspondant aux vecteurs hors base sont strictementpositifs, nous passonsdonc à l"étape 6.Etape 6:Puisque,, la solution optimale est donnée par :Les variables hors basesont nulles :.La valeur de la fonction objectif est.Observons les solutionsx1etx2obtenues à chaque itération. Dans letableau initial,x1= 0etx2= 0.Après la première itération,x1= 0etx2= 6. Finalement, à la seconde et dernière itération,x1= 4etx2= 4.Jusqu"à présent, nous avons toujours étudié des cas où une solution réalisablede base initiale étaitconnue. Cependant, cette situation (idéale ) ne serencontre pas dans tous les problèmes deprogrammation linéaire. Nous verronsdonc dans leparagraphesuivant comment trouver une solutionréalisablede base initiale.I.6Recherche d"une solution réalisable de baseinitialeJusqu"ici nous avons vu comment trouver une solution réalisablede baseinitiale lorsque toutes lescontraintes sont sous forme d"inégalités du type"". Dans ce cas, en ajoutant une variable d"écart àchaque contrainte pourla transformer en une égalité, la matriceAqui correspond à l"ensemble descontraintesprend la forme :oùIest la matrice identité d"ordre (m × m), puisqu"il y a m contraintes.L"intérêt d"obtenir au départ une matrice identité comme sous-matrice deAest évident. En effet,commeB = Iest une matrice de base, une solutionréalisable de base est immédiatement trouvée sousla forme :.De plus,etpuisque les prix associésaux variables d"écart sont nuls.À noter que cettematrice identité peut apparaître sans que les variablesd"écart aient été rajoutées. Dansce cas, la méthode du simplexe s"appliqueégalement, à la différence près que les prix associés auxvariables de base nesont pas nuls.Cependant, il n"existe pas, leplus souvent, de sous-matrice identité dansla matriceA. C"est le cas parexemple lorsque des contraintes n"ont pasbesoin de l"adjonction de variables d"écart (contraintes déjàsous forme d"égalités).On peut néanmoins obtenir une matrice identité commematrice debase initiale en considérant lenouveau système de contraintes :(I.37)dans lequel nous avons ajouté m variables xai, i = 1, . . . ,m, dont les colonnescorrespondantes sont lesvecteursei(vecteurs unitaires). Ces nouvelles variablessont appeléesvariables artificiellescar ellesn"ont aucune significationpour le système original de contraintes. Les vecteurs artificielseiquicorrespondent aux variables artificielles seront désignés parqide manière àles distinguer des vecteursajde la matriceA. Nous avons fait apparaîtreune matrice identité comme matrice de base initiale. Nousdisposons doncimmédiatement d"une solution réalisable de base pour (I.37) qui estet.Nous noterons toutefois qu"il ne s"agit pas d"une solution réalisabledu système original. Pour qu"unesolution de (I.37) soit aussi une solutiondu système original, il faut que,c"est-à-dire que toutesles variablesartificielles sortent de la base. Nous allons donc donner à ces variables artificiellesdes

prix très défavorables, de façon à ce que la fonction objectifpuisse être améliorée tant qu"une de cesvariables reste dans la base. Si lafonction objectifzdoit être maximisée, en donnant un prix négatif trèsgrandà chaque variable artificielle, on peut s"attendre à ce quezs"améliore aussilongtemps qu"unevariable artificielle se trouve dans la base avec une valeurpositive.I.7Initialisation de l"algorithme du simplexe (la méthode à deux phases).Comme son nom l"indique, cette méthode consiste à résoudre un problème de programmation linéaireen deux parties. La première partie, appelée phase 1, consiste à annulertoutes les variables artificiellesen utilisant une fonction objectif artificielle. Si l"on ne peut pas annuler toutes les variables, alors leproblème n"est pas réalisable.La phase II consiste à remplacer la fonction objectif artificielle de la phase 1 par la vraie fonctionobjectif à maximiser. On utilise alors la solution réalisable de base obtenue à la fin de la phase 1. Deuxcas peuvent se présenter en ce qui concerne cette solution réalisable de base.Premier cas La solution réalisable de base obtenue à la fin de la phase 1 ne contient plus de variablesartificielles. Dans ce cas, on utilise simplement l"algorithme du simplexe décrit précédemment pourobtenir la solution optimale.Deuxième cas Une ou plusieurs variables artificielles (nulles) font partie de cette solution réalisable debase. L"algorithme du simplexe peut également être utilisé mais il faut s"assurer que ces variablesartificielles ne deviennent jamais positives. Pour éviter ce problème, le critère de sortie de la base doitêtre modifiéen conséquence. Après avoir déterminé le vecteurakà faire entrer dans la base, il fautexaminer les valeursyikqui correspondent aux vecteurs artificiels.Sipour tous les indices icorrespondant aux vecteurs artificielsetpour au moins unindicei, lecritèreusuel desortiedelabasene sélectionnerait aucun vecteur artificiel. Ce serait donc unvrai vecteurbrqui serait éliminé. SixBr>0, alors les valeurs des variables artificielles avecdeviendraient positives puisque:Dans une situation de ce type, au lieu d"utiliser le critère usuel de sortiede la base, on fait sortir unvecteur artificiel avec unyik<0. Dans ce cas, lesnouvelles valeurs de la solution réalisable de baserestent inchangées puisquexBr=0. La nouvelle valeur de la fonction objectif n"est pas strictementaméliorée mais reste constante,, pour cette itération.La méthode des deux phases et les étapes de chaque phase sont décritesci-dessous.Phase ICette phase consiste à construire une fonction objectif artificielle en attribuant à chaque variableartificielle un prix de-1etun prix nul à toutes les autres variables. Il s"agit donc de maximiser lafonction objectif suivante :

où l"indicesindiquelenombredevariablesartificielles qui ont été rajoutéesdans les contraintes.Puisque les variables artificiellesxaisont non-négatives,la fonction objectif artificielle est toujoursnon-positive et atteint son maximum0lorsque chaque variable artificielle est nulle.LesétapesdelaphaseIsontlessuivantes:Etape 1:Transformer au besoin le problème de programmation linéaire sousforme standard enajoutant les variables d"écart etles variables artificiellesnécessaires.Etape 2:Construire la fonction objectif artificiellezaen changeant les coefficients de la fonctionobjectif originale de la manière suivante :(a)les coefficients des variables artificielles valent-1(b)les coefficients des autres variables sont nuls.Etape 3:Résoudre le problème établi dans les deux étapes précédentes avecla méthode usuelle dusimplexe.On s"arrête àla phase Idans deux cas :(a) La valeur dezavaut 0 (même s"il reste certains(zj-cj)négatifs).On passe alors àl"étape 1dela phase II.( b) Le crit ère d"optimalité,est satisfait mais ilreste dans la base desvariables artificielles avec des valeurs positives (ainsiza<0). Dans ce cas, le problème originaln"a pas desolution réalisable et l"on s"arrête.Voyons à présent les étapes de laphase IIdont le but est de trouver unesolution optimale au problèmeoriginal.Phase IIEtape 1:Remplacer la fonction objectif artificielle par la fonction objectiforiginale, ycompris lesvariables d"écart en donnant leur prix réel aux vraiesvariables et un prix zéro à toute variableartificielle qui peut apparaître dansla base à un niveau zéro. Les colonnes des vecteurs artificiels qui nesontpas dans la base peuvent être éliminées du tableau car elles ne seront pluscandidates pour y entrer.Etape 2:Le premier tableau de la phase II et le derniertableau de la phaseI sont identiques àl"exception des coefficients de la fonction objectif et desvaleurs(zj-cj)qui doiventêtre recalculées.Etape 3:S"il n"y a plus de variables artificielles dans la base à lafinde laphase I, on applique laméthode usuelle du simplexe. Sinon, on passe àl"étape 4.Etape 4:Pour éviter que les variables artificielles de la base nedeviennentpositives, il faut examinerles valeursyik(la colonne correspondant au vecteurakqui entre dans la base) pour chaque variableartificielle. Si ces valeurssont telles quepour tous les indicesicorrespondant aux vecteursartificielsetyik>0pour au moins un indicei, on fait sortir de la base unvecteur artificiel avec unyik<0.Sinon on utilise le critère usuel de sortie.Les exemples suivants illustrent respectivement les trois cas qui peuventse présenter à lafin de laphase I,c"est-à-dire :1.za=0et il ne reste plus de vecteurs artificiels dans la base.2.za=0et il reste un ou plusieurs vecteurs artificielsdanslabase.

3.za<0; dans ce cas, il n"existe pas de solution réalisable.Exemple:Soit le problème suivant à résoudre avecla méthode des deuxphases :• Phase IEtape 1:Comme il s"agit d"un problème de minimisation, il faut le transformeren un problème demaximisation en inversant le signe descoefficientsde la fonction objectif. Cette opération n"intervientque dans la phase II. Enrevanche, il faut introduire une variable d"écart dans la quatrième contrainteetajouter trois variables artificielles pour qu"une matrice identité apparaissedans le tableau 1 de la phaseI. Les contraintes s"écrivent alors :Etape 2:La fonction objectif artificielle s"écrit :Etape 3:Nous construisons le tableau 1 de la phase I et appliquons l"algorithmeusuel dusimplexe.

Tableau 1Le critère d"entrée indique que le vecteura3entre dans la base. Le critèrede sortie indique deuxpossibilités pour sortir un vecteur de la base :q2oua4puisqu"ils ont tous deux le plus petit rapport (4/2= 2/1 = 2).Le but de laphase I étant de faire sortir les vecteurs artificiels de la base,notre choixportera surq2. Nous construisons le tableau 2 de la phase I.

Tableau 2Le tableau 2 de la phase I indique queza=-8. On peut faire entrera1dans la base. Le vecteura4sort dela base puisqu"il correspond au plus petitrapport, c"est-à-dire.À noter que puisque, la valeur de la fonction objectif dansle tableau suivant resteconstante, comme l"indique le tableau 3 de laphase I.

Tableau 3Dans le tableau 3 de la phase I, nous avonsza=-8. Le vecteur qui entredans la base est le vecteura2. Ily a deux vecteurs candidats pour sortir dela base :q1etq3. Nous choisissons arbitrairement de sortirq1de la base etcalculons un nouveau tableau.

Tableau 4Puisque dans le tableau 4 de la phase I.za=0, la phase I est terminée.Notons qu"il reste un vecteurartificiel(q3) dans la base à un niveau 0. Ilfaudra donc s"assurer dans la phase II que la variablecorrespondante nedevienne pas positive. Nous pouvons passer à l"étape 1 de la phase II.Phase II

Etape 1:Puisqu"il s"agit d"un problème de minimisation, il faut le transformer en un problème demaximisation. La fonction objectif à maximiserest donc :Les coefficients de la variable d"écartx4et de la variable artificiellexa3dans la base sont nuls. De plus,nous pouvons éliminer du tableau les vecteursartificielsq1etq2qui nesontplusdanslabase.Etape2:Établissons le tableau 1 de la phase II.

Tableau 1Le tableau 1 de la phase II fournit la solution optimale puisque la seulevaleur de(zj-cj)pour unvecteur hors base est strictement positive. À noterque dans ce cas, à lafin de la phase II, ilreste unvecteur artificiel dans labase àunniveauzéro.La solution optimale est donnée parx1=2,x2=2etx3=2.Lavaleurde la fonction objectif vautz=-8(car il s"agit d"une minimisation).

Chapitre 2:Optimisation non-linéaire sanscontraintesII.1IntroductionNous allonsétudier le problème d"optimisation sans contraintes ouon effectue la minimisation de lafonctionsur tout l"espace. Nous considérons donc le problèmeformuléde la façonsuivante:Oufest une fonction de???+∞II.2LeGradientLadérivéepartielle au premier ordre dela fonctionfenadans la directionu:lim→+-Dans le cas particulier ouudécrit une base,...,de?, on note,...,,...,Les dérivées partielles dans ces directions.Définition1:Soit:?→?admettant des dérivées partielles d"ordre 1 en a; on appelle gradient defenale vecteur?=,...,,...,Lorsque=,...,:?→?, le gradient est une matrice×dont les colonnes sont lesvecteurs?Fonction de classeDéfinition2:fest continument différentiable si et seulementsitoutes ces dérivées partielles d"ordre1existent et sont continues.II.3Le HessienSi les dérivées partielles defpossèdent à leur tour des dérivées partielles: on dit quefpossède desdérivées d"ordre 2. La dérivée partielle dans la directionde la dérivée partielleest notée:()Définition1:Soit:?→?admettant des dérivées partielles d"ordre 2 en a; on appelle gradient defenaon appelle Hessien defen a la matrice×donnée par

?=()...()...()...()...()=??()ExempleII.1:soit,,=+-L"hessienne defest donné par=+2-2--0-2--0Fonction de classeDéfinition2:fest deux fois différentiable siet si seulement toutes ces dérivées partielles d"ordre deuxexistent et sont continues.Hessien de fonctionsProposition:Lorsquefest,=: le Hessien est unematrice symétriqueToute matrice symétriqueréelleHest diagonalisable dans le groupe orthogonal: il existeΔdiagonal,Uorthogonale telle que=Δ;Δ↔i?est positive si et seulementsiΔ≥0?≥0,???i?est définie positive si et seulement siΔ≥0?≥0,??0?Définition3:(minimum global).Soit:?→?une fonction.(?)est le minimumglobal defsi etseulement si :???,()≥(?)?est un minimiseur global def.Définition4:(minimum local).Soit:?→?une fonction.(?)est le minimumlocal defsi etseulement si :?,??]?-;?+[,()≥(?)?est un minimiseur local def.Définition 5:x0est un point stationnaire si et seulement si?=0.Dans les points stationnaires, il y a les minima et les maxima (locaux et globaux) et il y a aussi d"autrespoints.Définition 6:Un point stationnaire qui n"est ni un minimum ni un maximum est un point singulier.II.4Condition nécessaire pour l"existence d"un minimum local

k=0: choix de??dans un voisinage de?.2-Itération k=-()()3-Critère d"arrêtSi?-?<,Si non, On pose k=k+1 et on retourne à 2.D'un point de vue pratique, cette méthode souffre de nombreux inconvénients :la méthode peut diverger si le point de départ est tropéloignéde la solution.la méthode n'est pas définie si=0.la méthode peut converger indifféremment vers un minimum, un maximum ou unpoint de selle.Cette méthode est donc peu utilisée. Son intérêt majeur est d'illustrer dans?lefonctionnement desalgorithmes de minimisation multidimensionnelle du second ordreII.8Méthodes du gradientIl s"agit d"une famille de méthodes itératives qui s"appliquent à des fonctionsdérivables et qui utilisentl"idée ci-dessous.On veut minimiser une fonctionf. Pour cela on se donne un point de départ arbitrairex0. Pourconstruire l"itéré suivantx1il faut penser qu"on veut se rapprocher du minimum def; on veut donc que()<(). On cherche alorsx1sous la forme=+oùd1est un vecteur non nul de?etestun réel strictement positif. En pratique donc, on cherched1etpour que(+)<(). On ne peut pas toujours trouverd1. Quand d1existe on dit que c"est unedirection de descenteetestle pasde descente. La direction et le pas de descente peuvent être fixes ou changer à chaqueitération. Le schéma général d"une méthode de descente est le suivant :??é=+,??-0,???Ouetsont choisis de telle sorte que(+)<()De tels algorithmes sont souvent appelés méthodes de descente. Essentiellement, la différence entre cesalgorithmes réside dans le choix de la direction de descentedk.Une idée naturelle pour trouver une direction de descente est de faire un développement de Taylor àl"ordre 2 de la fonctionfentre deux itérationsxket=++=+?(,)+Comme on veut+<, on peut choisir en première approximation=-?(). La méthode ainsi obtenue s"appelle l"algorithme du Gradient. Le pasest choisiconstant ou variable.Alghorithme 3:Algorithme du Gradient1-Initialisationk=0 choix de x0et de>02-Itération k=+()3-Critère d"arrêt

Si?-?<,Si non, On pose k=k+1 et on retourne à 2.est un réelpositif (petit) donnéqui représente laprécision désirée.Cette méthode a pour avantage d"êtretrèsfacileàmettre enœuvre. Malheureusement, les conditions deconvergence sont assez lourdes (c"est essentiellement de la stricteconvexité) et la méthode est engénéral assez lente.Méthode du gradient à pas constantOn utilise le plus souvent laméthode du gradient à pas constant (=constant).Toutefois, on peut fairevarier le pas à chaque itération : on obtient alors la méthode dugradient à pasvariable.ExempleII.2Soit la fonction=+-3(+)trouver le minimum de cette fonction en partant dupoint de cordonnée=(-2,1.5); critère d"arrêt est?-?<10Solution1-=(-2,1.5)=0.452-Calcul de la dérivée par rapport àx1=2-3-Calcul de la dérivée par rapport àx2=-3-1èreitération=+()=+()3-Test d"arrêtSi-<10,-<10,Si non on pose k=2 et on retourne à 2

Les itérationsItérationsx1x2f(x)1-21,50006,625021,15002,17506,6250

Calcul deCommeminimiseqdans la directiondk; on a,?:=?=0?=+=0Soit++=0D"oùl"on tire:=()Comment construire les directions A-conjuguées ?Des directions A-conjuguées,,...,peuvent être générées à partir d"unensemblede vecteurslinéairement indépendants,,...,en utilisant la procédure dite de GramSchmidt, de telle sorte quepour toutientre0etk, le sous-espace généré par,,...,soitégale au sous-espace généré par,,...,.Alorsdi+1est construite comme suit :=+Nous pouvons noter que sidi+1est construite d"une telle manière, elle est effectivementlinéairementindépendante avec,,...,.En effet, le sous-espace généré par les directions,,...,est le même que le sous-espacegénérépar lesdirections,,...,, etest linéairement indépendant de,,...,:ne fait donc pas partie du sous-espace généré par les combinaisons linéaires delaforme∑,de sorte quedi+1n"en faitpas partie non plus et est donc linéairementindépendante des,,...,.Les coefficients, eux sont choisis de manière à assurer la A-conjugaison des,,...,.Méthode de gradient conjugué dans le casquadratiqueLa méthode du gradient conjugué quadratique est obtenue en appliquant la procédure de Gram-Schmidtaux gradients?,...,?()c"est-à-dire en posant=?,...,=?()En outre, nous avons :?=+Et?=Notons que la méthode se termine si?=0.La particularité intéressante de la méthode du gradient conjugué est que le membre dedroite del"équation donnant la valeur dedk+1dans la procédure de Gram-Schmidt peutêtre grandementsimplifié.Algorithme de La méthode du gradient conjugué pour les fonctions quadratiquesOn suppose ici que la fonction à minimiser est quadratique sous la forme :=12++Si l"onnote=?(), l"algorithme prend la forme suivante.Cet algorithme consiste à générer une suite d"itéréssous la forme :=+

L"idée de la méthode est :1-construire itérativement des directions,,...,mutuellementconjuguées :A chaque étapekla directiondkest obtenue comme combinaison linéaire du gradientEnxket de la direction précédentedk-1c"est-à-dire=-?+les coefficientsétant choisis de telle manière quedksoit conjuguée avec toutes lesdirectionsprécédentes.Autrementdit :=0=0?-?+=0?-+=0?==2-déterminer le pas:En particulier, une façon de choisirconsiste à résoudre le problème d"optimisationunidimensionnelle suivant :=+,>0On en deduit=Le pasobtenu ainsi s"appelle le pas optimal.Algorithme 3.1Algorithme du gradient conjugué "quadratique"Etape 0 :(initialisation)Soit x0le point de départ,=?=+, poserd0=-g0;Poserk = 0et aller à l"étape 1:Etape 1 :sigk= 0: STOP (x* = xk)."Test d"arrêt"si non aller à l"étape 2.Etape 2 :Prendre=+avec=-=-?+=Poserk=k+1et aller a l"étape 1.ExempleII.4:Même exempleII.2SolutionEtape 0 :(initialisation)Soit x0(-2.1.5)le point de départ,===2-3=-7=-3=-1.5

Sous la formesuivante?=+,Matrice=2001et=-3-3onposed0=-=71.5Poserk = 0et aller à l"étape 1:Etape 1 :sig0= 0: STOP (x* = xk)."Test d"arrêt"Test non vérifier donc aller a l"étape suivante.Etape 2=+=+=-=-71.5×-7-1.571.5×200171.5=0.5112=-2+0.5112?7=1.5786=1.5+0.5112?1.5=2.2668Test d"arrêt===2-3=0.1571=-3=-0.7332≠0on pose k=k+1=+=+=-?+===0.1571-0.7332=0.1571-0.7332×2001×71.571.5×200171.5=0.0110=-?+=0.1571+0.0110?7=-0.0803=-?+=-0.7332+0.0110?1.5=0.7496=-=--0.0803-0.7496×0.1571-0.7332-0.08030.7496×2001-0.08030.7496=0.9780=1.5786+0.9780?(-0.0803)=1.5000=2.2668+0.9780?(0.7496)=3.0000Test d"arrêt==0.888×100?0arrêt.

Méthode du gradient conjugué dans le cas non quadratiqueOn s"intéresse dans cette section à la minimisation d"une fonction:?→?, nonnécessairementquadratique :min,??Les méthodes du gradient conjugué génèrent des suites,,..,de la forme suivante :=+Le pas??étant déterminé par une recherche linéaire.Ladirectiondkest définiepar la formulede récurrence suivante(??)=-=1-+≥2Ces méthodes sont des extensions de la méthode du gradient conjugué linéaire du casquadratique, siprend l"une des valeurs=??=????=??-Ou=-Algorithme 3.2Algorithme de La méthode du gradient conjugué pour les fonctions quelconquesEtape0 :(initialisation)Soit x0 le point de départ ,=?, poserd0=-g0Poserk=0et aller à l"étape 1.Etape1:sigk= 0: STOP (x* = xk)."Test d"arrêt"si non aller à l"étape 2.Etape 2 :Définir=+avec:calculer par la recherche linéaire=-+Ou:ééPoserk=k+1et aller a l"étape 1.II.9Méthode de NewtonLa méthode de Newton pour les fonctions multivariables est identique à celle des fonctions univariées.Comme précédemment, une estimationdefau pointxkestdonnée par le développement deTaylor dusecond ordre, qui s'écrit pour une fonctionmultivariée :=+-?+12(-)?(-)Si la matrice Hessienne est inversible, on choisitqui minimise, soit :=-??()En pratique, la direction de descente=-??()est calculée sans inverser?mais en résolvant:

?=-?()L'intérêt de cette suite est sa convergence quadratique vers un minimiseur localàlacondition quex0soit assez proche d'un minimiseur. Néanmoins d'un point de vue pratique,cetteMéthode comporte lesmêmes inconvénients que dans le cas monovariable :la méthode peut diverger si le point de départ est tropéloignéde la solution,la méthode n'est pasdéfinie si la matriceHessienne n'est pas inversible,la méthode peut converger indifféremment vers un minimum, un maximum ou unpoint de selle.Algorithme4.Algorithmede la méthode de Newton Dans?Données :fune fonction différentiable et x0un point initial1-Initialisationk=0: choix de??dans un voisinage de?.2-Itérationk=+3-Critère d"arrêtSi?-?<,Si non, On posek=k+1et on retourne à 2.L"étape 2. de la méthode revient à résoudre lesystème linéaire suivant:?=-?()Puis à poser=+Actuellement on développe surtout des méthodes dites quasi-Newton qui gardent la rapidité de laméthode de Newton, et sont plus robustes par rapport au du point de départ.ExempleII.5:Même exemple II.2Solution1-=(-2,1.5)2-Calcul de la dérivée par rapport àx1=2-3=-7-Calcul de la dérivée par rapport àx2=-3=-1.5-Calcul de la dérivéedeuxièmepar rapport àx1=2-Calcul de la dérivéedeuxièmepar rapport àx2=1-Calcule deDau pointx0=-??=2-32=3.5é,=-??=-31=5é,-1èreitération=+=1.5000=+=33-Test d"arrêtSi-<10,-<10,

Si non on pose k=2 et on retourne à 2

Les itérationsItérationsx1x2f(x)1-21,500000000000006,6250000000000021,50000000000003-6.7500II.11.Méthodes quasi-NewtonPour des problèmes de grandes dimensions, le calcul duHessien est trop couteux. Onpeut alors utiliserdes algorithmes, dits quasi-Newton, qui calculentdonc une approximationde?()enfonction de,?,?,.On trouve notamment deux méthodes de calcul :la formule deDavidon-Fletcher-Powell(DFP) :=-+la formule de Broyden-Fletcher-Goldfarb-Shanno (BFGS):=+1+-+Avec=?-?()Ces formules donnent toujours desmatrices définies positives. A l'aide de ces estimations,onétablit unalgorithmeàconvergencetrèsefficace et particulièrement robuste.Son uniqueinconvénientest la nécessitédu stockage en mémoire d'une matrice de taillen×n. Dans lapratique, on utilise engénéralla méthode BFGS qui est plus efficace.Algorithme5Algorithme de quasi-Newton avec mise à jour BFGSou DFPDonnées :fune fonction différentiable et x0un point initialEtape 1:soit>0critère d"arrêt, choisirdéfini positive quelconque (par exemple=)Poser k=1 et aller à l"étape suivanteEtape 2:Si???

par exemple dichotomie ou Wolfe)et poser=+Etape 3:construirecomme suit:=-+SelonDFPOu=+1+-SelonBFGSAvec=?-?()=Remplacerkpark+1et aller à l"étape 1Exemple II.6:Même exemple II.2SolutionEtape 1:soit=0.001critère d"arrêt, choisirdéfini positive quelconque (par exemple=)Poser k=0et aller à l"étape suivanteEtape 2:Si???

Avech(x) = x12+ x22-1 = 0Le Lagrangien estL(x, λ) = 2x1+ x2+ λ(x12+ x22-1 )=0ce qui donne+=0+=0?2+2=01+2=0??=?==0?1+12=0??=?⎷522 points vérifient les conditions de Lagrange, mais un seul est minimum : cesconditions sontnécessaires, mais pas suffisantespour qu"un point soit optimum.

♦facile à implanter, mais pas très performant (conditionnement),solution toujourslégèrement nonadmissible.Remarque :Dans le cas de contraintesd"égalité=0=1,...,), la fonctionpénalisée àconsidérer est :,=+()III.5.3 Pénalité intérieureMême principe que la pénalité extérieure,mais pour obtenir un minimum approché par l"intérieur dudomaine (donc toujours admissible). On définit :,=-1()Ou bien,=-log(-())Ou le facteur de pénalité r doit cette fois tendre vers 0 pour que x s"approche de lafrontière dudomaine admissible. On résout donc une succession de problèmes sans contraintes :,=-1()=1,...Avec=×(0.1<<1)

par les différentes méthodes de pénalité.1. Pénalités extérieures.La fonction pénalisée s"écrit :,=0.5+?4-?Sa minimisationinduit les solutions approchées dépendant de:=4-0.522. Pénalités intérieuresLa fonctionpénalisée s"écrit :,=0.5-4-La solution approchée associée est :=4+0.5III.6Programmation quadratique séquentielleNous allons nous attaquer maintenant à une dernière classe de méthodes appelées SQP pour SequentialQuadraticProgramming.Intéressons-nous dans un premier temps au cas de contraintes en égalité. Considérons le problèmemin()?=??,=0,=1,...,L"idée essentielle consisteàrésoudre unesuccession de problèmes quadratiques avec contrainteslinéaires (c es problèmes sont relativement simplesàrésoudre) qui sont des approximat ions duproblème de départ.Etant donné, on cherche=+ou??est une direction de descente etle pas.Effectuons une approximation des contrainteshàl"aide de la formule de Taylor du premier ordre :+=+?.+(??)Si on néglige les termes d"ordre supérieur ou égal à 2, on définit la directionavec la directionpermettantd"assumer(+)?0On pose donc+?.=0,?=1,...,?.=-

Ou?est la matrice jacobienne deen. Cette relation correspondàune linéarisation descontraintes au voisinage de: c"est un système linéaire.Par ailleurs, il faudrait quediminue la valeur du Lagrangien (puisque c"est le Lagrangien qui jouelerôlede la fonction objectif quand on a des contraintes) . On va fair e une approximati on duLagrangien.+,=,+?,,+12?,,+(??)Si on néglige les termes d"ordre supérieur ou égal à3, on voit qu"il faut minimiser?,,+12?,,Pourespérer minimiser le Lagrangien. On cherche donc, en fin de comptesolution du problèmemin?,+(?,.,)?+=0En effet, nous avons :(?,,)=?+?()=?,+()Le dernier termeétant constant. Il reste ensuiteàdéterminer le paset le multiplicateuràchaqueitération. Il y a bien sur, beaucoup de possibilités qui génèrent autant de variantes de la méthode.Nous présentons ici, la méthode qui est basée sur le choix :=1Algorithme:Méthode SQP pour des contraintes enégalitéInitialisationK=1, choix de??,??Itération k: tant que le critère d"arrêtn"est pas satisfait1-Résoudre le sous problème quadratiquemin?,+(?,.,)?+=0(1)2-On pose alors??le multiplicateur associe a la contrainte (en égalité)de (1) et=+K=k+1Intéressons-nous maintenant au cas de contraintes générales en égalité et inégalité; globalement, leprincipeest le même, seule la fonction Lagrangienne est modifiée.

Méthodes d"optimisation stochastiquesIV.1L"algorithme génétiqueLes algorithmes génétiques sont des algorithmes d'optimisation s'appuyant sur des techniques dérivéesde la génétique et des mécanismes d'évolution de la nature: croisements, mutations, sélections, etc....Ils appartiennent àla classe des algorithmes évolutionnaires.IV.1.1Le codageChaque paramètre d'une solution est assimilé à un gène, toutes les valeurs qu'il peut prendre sont lesallèles de ce gène, on doit trouver une manière de coder chaque allèle différent de façonunique(établirune bijection entre l'allèle "réel" et sa représentation codée).Un chromosome est une suite de gène, on peut par exemple choisir de regrouper les paramètressimilaires dans un même chromosome (chromosome à un seul brin) et chaque gène serarepérableparsa position : son locus sur le chromosome en question.Chaque individu est représenté par un ensemble de chromosomes, et une population est unensembled'individus.

Figure1: les cinq niveaux d'organisation d'un algorithme génétiqueIl ya trois principaux types de codage utilisables, et on peut passer de l'un à l'autre relativementfacilement :•le codage binaire :c'est le plus utilisé.Chaque gène dispose du même alphabet binaire {0, 1}.Un gène est alors représenté par un entier long(32 bits), les chromosomes qui sont dessuites de gènes sont représentés par des tableaux de gènes et lesindividus de notre espacede recherche sont représentés par des tableaux de chromosomes.Ce cas peut être généralisé à tout alphabet allélique n-airepermettant un codage plus intuitif,parexemple pour le problème du voyageur de commerce on peut préférer utiliser l'alphabet

allélique {c1, c2, c3, ..., cn} où cireprésente la ville de numéro i.•le codage réel :cela peut-être utile notamment dans le cas où l'on recherche le maximum d'unefonction réelle.

Figure2: illustration schématique du codage des variables réelles•le codage de Gray :dans le cas d'un codage binaire on utilise souvent la "distance de Hamming"comme mesure de la dissimilaritéentre deux éléments de population, cette mesure compte lesdifférences de bits de même rang de ces deux séquences.Et c'est la que le codage binaire commence à montrer ses limites. En effet, deux éléments voisinsenterme de distance de Hamming ne codentpas nécessairement deux éléments proches dansl'espace derecherche. Cet inconvénient peut être évité en utilisant un "codage de Gray" : lecodage de Gray est uncodage qui a comme propriété que:entre un élément n et un élément n + 1,donc voisin dansl'espacede recherche, un seul bit diffère.IV.1.2L'opérateur de sélectionCet opérateur est chargé de définir quels seront les individus de P qui vont être dupliqués dans lanouvelle population P' et vont servir de parents (application de l'opérateur decroisement).Soitnle nombre d'individus de P, on doit ensélectionnern/2(l'opérateur de croisement nouspermet derepasser ànindividus).Cet opérateur est peut-être le plus important puisqu"il permet aux individus d"une population desurvivre, de se reproduire ou de mourir. En règlegénérale, la probabilité de survie d"un individu seradirectement reliée à son efficacité relative au sein de la population.On trouve essentiellement quatre types de méthodes de sélection différentes :•La méthode de la "loterie biaisée" (roulette wheel) de GoldBerg,•La méthode "élitiste",•La sélection par tournois,•La sélection universelle stochastique.a) La loterie biaisée ou roulette wheel :Cette méthode est la plus connue et la plus utilisée.

Avec cette méthode chaque individu a une chance d'êtresélectionnéproportionnelle à saperformance,donc plus les individus sont adaptés au problème, plus ils ont de chances d'êtresélectionnés.Pour utiliser l'image de la "roue du forain", chaque individu se voit attribué un secteur dontl'angle estproportionnel à son adaptation, sa "fitness".On fait tourner la roue et quand elle cesse de tourner onsélectionnel'individu correspondant ausecteurdésigné par une sorte de "curseur", curseur qui pointe sur un secteur particulier de celle-ciaprès qu'ellese soit arrêté de tourner.

Figure3: la méthode de sélectioquotesdbs_dbs32.pdfusesText_38

[PDF] exercices corrigés de convexité et optimisation

[PDF] exercices corrigés doptimisation pdf

[PDF] cours doptimisation pour économistes

[PDF] cours optimisation sans contrainte

[PDF] resume cours optique geometrique

[PDF] cours de physique optique cours et exercices corrigés pdf

[PDF] examen corrigé optique ondulatoire

[PDF] résumé cours optique ondulatoire

[PDF] physique optique cours complet

[PDF] controle optique 1ere s

[PDF] orientation scolaire et professionnelle définition

[PDF] oxydoréduction cours bac pro

[PDF] programme daeu b physique

[PDF] programme daeu a

[PDF] cours physique daeu b pdf