×îÓÅ»¯ÀíÂÛºÍËã·¨(·¨ÎÄ°æ)

1 Introduction de l'optimisation 1 1.1 Br¨¨ve histoire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2 1.2 D¨¦finition du probl¨¨me d'optimisation . . . . . . . . . . . . . . . . .3 1.3 Classes des probl¨¨mes d'optimisation . . . . . . . . . . . . . . . . . .4 1.4 Rappels math¨¦matiques pour l'optimisation . . . . . . . . . . . . . .5 1.4.1 Normes vectorielles et matricielles . . . . . . . . . . . . . . .5 1.4.2 Suite num¨¦rique dans Rn. . . . . . . . . . . . . . . . . . . . 12 1.4.3 Topologie dans Rn. . . . . . . . . . . . . . . . . . . . . . . . 13 1.4.4 Fonctions de plusieurs variables et calcul diff¨¦rentiel . . . . . 17 2 Analyse convexe 25 2.1 Ensemble convexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.1.1 Ensemble convexe . . . . . . . . . . . . . . . . . . . . . . . . 25 2.1.2 Combinaison lin¨¦aire, convexe, affffine et positive . . . . . . . . 30 2.1.3 Th¨¦or¨¨me de Carath¨¦odory . . . . . . . . . . . . . . . . . . . 36 2.1.4 Projection et S¨¦paration . . . . . . . . . . . . . . . . . . . . . 38 2.1.5 Point extr¨¦mal et Direction extr¨¦male . . . . . . . . . . . . . 44 2.1.6 Th¨¦or¨¨me de repr¨¦sentation . . . . . . . . . . . . . . . . . . . 47 2.1.7 Lemme de Farkas et de Gordan . . . . . . . . . . . . . . . . . 49 2.2 Fonction convexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 2.2.1 Fonction convexe . . . . . . . . . . . . . . . . . . . . . . . . . 52 2.2.2 Fonction D.C. . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 3 Optimisation Lin¨¦aire 65 3.1 Probl¨¨me d'optimisation lin¨¦aire . . . . . . . . . . . . . . . . . . . . 65 3.2 Solution d'optimisation lin¨¦aire . . . . . . . . . . . . . . . . . . . . . 67 3.2.1 Th¨¦or¨¨me d'existence de solution optimale d'optimisation lin¨¦aire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 3.2.2 Solution de base . . . . . . . . . . . . . . . . . . . . . . . . . 69 3.3 M¨¦thodes de r¨¦solution du probl¨¨me (OL) . . . . . . . . . . . . . . . 75 3.3.1 M¨¦thode graphique . . . . . . . . . . . . . . . . . . . . . . . . 75 3.3.2 Algorithme du simplexe . . . . . . . . . . . . . . . . . . . . . 76 3.3.3 Tableau du simplexe . . . . . . . . . . . . . . . . . . . . . . . 85 3.3.4 M¨¦thode des deux phases . . . . . . . . . . . . . . . . . . . . 89 3.3.5 R¨¨gles d'anti-cyclage . . . . . . . . . . . . . . . . . . . . . . . 93 3.3.6 Logiciels pour l'optimisation lin¨¦aire . . . . . . . . . . . . . . 97 4 Th¨¦orie de dualit¨¦ 104 4.1 Probl¨¨me dual et point-selle . . . . . . . . . . . . . . . . . . . . . . . 104 4.2 Dualit¨¦ de Lagrange . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 5 Conditions d'optimalit¨¦ 114 5.1 Direction r¨¦alisable et Direction de descente . . . . . . . . . . . . . . 114 5.2 Conditions d'optimalit¨¦ du probl¨¨me d'optimisation sans contrainte . 116 5.3 Conditions d'optimalit¨¦ du probl¨¨me d'optimisation sous contraintesd'in¨¦galit¨¦s et d'¨¦galit¨¦s . . . . . . . . . . . . . . . . . . . . . . . . . 118 5.3.1 Contrainte active et qualification de contrainte . . . . . . . . 118 5.3.2 Qualifications des contraintes usuelles . . . . . . . . . . . . . 120 5.3.3 Conditions de Karush-Kuhn-Tucker . . . . . . . . . . . . . . 123 Bibliographie 134 Index des d¨¦finitions 135 Index des th¨¦or¨¨mes 139