Optimisation.docx

Optimisation Cours n°1 : Domaine de classification des problèmes d'optimisation La recherche opérationnelle Historique: Outils de calcul informatisés (milieu du 20e siècle) répondre à des problèmes de planification de manière rationnelle (et non de manière intuitive seulement) outils d'aide à la décision Définition: Technique de calcul de décisions optimales (optimisation) au sens d'un critère (évaluation) qui mesure l'efficacité des décisions. Autant de décision optimale que de critères possibles une seule politique optimale Rôle de l'optimisation dans les systèmes de production Classification hiérarchique: Niveau 3: gestion Niveau 2: produit Niveau 1: machine Niveau 0: asservissements Optimiser le temps de réponse (seconde) Optimiser la fiabilité de conception (heure) Optimiser les performances du produit (mois) Optimiser l'entreprise pour son profit (années) Classification des problèmes Univers certain ou incertain (déterministe ou aléatoire) 2743200280670Perturbations Sortie s Entrée e 00Perturbations Sortie s Entrée e Si certain alors on peut modéliser le problème de décision et appliquer une théorie mathématique rigoureuse Système complètement prédictible : univers hostile (théorie des jeux) processus statique ou dynamique (le temps intervient ou non) état continu ou état discret variable de décision, nombres relationnels temps continu ou échantillonné techniques de recherche d'optimum programmation mathématique : base théorique de l'optimisation recherche de maximum (ou minimum) d'une fonction de plusieurs variables (f(x1, x2, …)) programmation linéaire : cas particuliers de la programmation mathématique théorie des graphes : modélisation particulière qui n'est du type ordinaire de la théorie des fonctions, mais très intuitives programmation dynamique (temps): décisions séquentielles Exemple de classes de problème allocation de ressources - planification gestion de stock - théorie des jeux réseau - file d'attente ordonnancement - commande optimale Cours n°2 : La programmation mathématique Les étapes de formulation d'un problème d'optimisation choix des variables de décision en programmation mathématique, les variables de décision sont des nombres réels en nombre n x1, x2, …, xn ou le vecteur de décision X={x1, x2, …, xn} => X, espace à n dimensions 1714500114300Processus X Résultats 00Processus X Résultats validité a priori des variables de décision c'est définir un domaine de ou les xi Exemple : xi 0, le domaine admissible : On dit que les décisions sont contraintes si elles ne peuvent pas prendre toutes les valeurs de. quantification d'une décision c'est la définition d'une fonction d'évaluation une fonction de n variables, F(xi, …, xn). X=> un nombre F(X) ou bien critères de décision optimisation dans l'ensemble des décisions admissibles, il y en a une (ou plusieurs) qui conduit à une valeur du critère (F) plus grande (ou plus petite) que toutes les autres. pour cet ensemble de décisions ={, …,} et l'optimum est =F(, …,), c'est un maximum ou minimum absolu. Résoudre un problème d'optimisation, c'est trouver et. Les théorèmes généraux de la programmation mathématique recherche locale du maximum on part d'une décision quelconque admissible (décision initiale X0). on calcule F0=F(X0) => Une première valeur du critère. => MAIS ce n'est pas forcément l'optimum On teste X0 en effectuant une variation de décision autour de X0, on calcule la nouvelle valeur de F1(X0+?X). F1= F1(X0+?X) si X, F1?F0, F0 est peut-être un maximum, on dit que c'est un maximum local si pour tous ?X, F1?F0, F0 est alors un minimum calcul de la variation ?F=F1- F0 pour une variation ?X petite (autour de ?X=0) par la formule de Taylor F1(X0+?X)=F(X0) + forme linéaire des dérivées partielles successives de F. Ex : n=2 : F1(,) = Th: si ne sont pas toutes les deux nulles, alors la décision X0 n'est pas un extremum (ni un max ni un min). Pourquoi : la variation ?F va dépendre du signe de ?x1 ou ?x2 et donc ?F peut être supérieur ou inférieur à zéro. On en déduit qu'on peut calculer les extrêmes éventuels en résolvant le système de n équations (pas forcément linéaire). Le vecteur de composanteest le vecteur gradient de la fonction F. exemple : fonction d'une variable F(X) max ou min pour, une équation ou une inconnue 02540a b x1 x2 x3 F1 F2 F3 x F(x) 00a b x1 x2 x3 F1 F2 F3 x F(x) - F1 est le maximum absolu sur le domaine de validité - F2 est le maximum local sur le domaine de validité - F3 est le minimum absolu sur le domaine de validité Domaine admissible de la décision pour a, < ou =0 Exemple : variables de décisions x1>0 -> il peut y avoir plusieurs contraintes gi(x1,...,xn)>, < ou =0, i variant de un à un nombre (nombre quelconque entier) contrainte égalité les variables de décision sont liées par une équation g(x1,...,xn)=0 et ne sont pas indépendantes Combien de contraintes égalité? Système de m équations à n inconnues Si m=n résolution du système d'équations une ou quelques solutions possibles décisions admissibles Dans le cas où m=n : on choisit la solution qui amène le plus grand (petit) F. Si m>n plus de contraintes que de variables de décision 0 solution admissible Si m, < ou =0, qui sont des surfaces dans , par exemple, un plan ax1+bx2+cx3+d=0 Recherche optimum dans le cas de contraintes égalité Th (Lagrangien) : L (x1, …, xn, …, ?1, …, ?m)=F(x1, …, xn)+ ?1g1(x1,...,xn)+…+ ?mgm(x1,...,xn) Un point stationnaire est solution du système d'équations L'optimum, le point stationnaire éventuel, ne correspond pas à Grad. F=0. L'optimum avec contraintes égalité est différent de l'optimum sans contraintes. Interprétation géométrique d'un : 34290076200x2 x1 00x2 x1 - g(x1, x2)=0, courbe de contraintes égalité - le point de décision doit appartenir à la courbe de contraintes - l'optimum est le point où une courbe ISO-F est tangente à la courbe de contraintes Court n°4 : Programmation Linéaire Forme de la fonction d'évaluation Hypothèse de la P.L. : la fonction d'évaluation est une combinaison linéaire de variables de décision : F(x1, x2, …, xn)= a1x1+a2x2+…+ anxn Conséquence : Grad. mais les ai ne sont pas tous nuls Donc l'optimum est situé sur les frontières du domaine d'admissibilité. Le problème de P.L. n'a pas de sens s'il n'y a pas de contraintes. Les contraintes En P.L., il y a m contraintes inégalités qui sont de la forme h(x1, …, xn)?0 où h est une forme linéaire b1x1+b2x2+…+bmxm ?B Conséquence : les frontières du domaine d'admissibilité sont constituées de m hyperplans d'équation bi1x1+bi2x2+…+bimxm=Bi On définit un polyèdre, qui est le polyèdre des contraintes. Exemple : n=2 F= a1x1+a2x2 3 contraintes Contraintes : - b11v1+b12v2?b1 - b21v2+b22v2?b2 - b31v1+b32v2?b3 3429004826000 Polyèdre des contraintes (triangle) Analyse de l'existence de l'optimum Les hyperplans ISO-F, soit d'équation : a1x1+a2x2+…+ anxn=F? constant, c'est l'ensemble des points (x1, x2, …, xn) qui vérifient l'équation a1x1+a2x2+…+ anxn=F? C'est une famille d'hyperplans parallèles. Donc, il va y avoir un hyperplan de la famille qui va "toucher" le polyèdre des contraintes en un point. 34290010985500 Point de contact Frouge En laissant tout le polyèdre d'un même côté. 159829516764000 au maximum non au minimum La recherche de l'optimum se réduit à trouver les coordonnées des sommets du polyèdre, en résolvant le système d'équations linéaires deux à deux. 1028700000 S1=D2? D3 D1 S1=D1? D2 D2 S3=D1? D3 D3 Court n°5 : Algorithme du simplexe Propriétés fondamentales L'optimum étant sur un sommet du polyèdre, il faut calculer les coordonnées des sommets admissibles. La difficulté, c'est l'explosion combinatoire du nombre de sommets possibles : = Exemple : n=6 et m=10 =8008 sommets =8008 systèmes linéaires Forme canonique d'un problème de P.L. Maximum de F=C1x1+…+ Cmxm=CX avec C=et sous n+m contraintes inégalités. n contraintes de positivité m contraintes ordinaires Ou minimum de F sous contrainte : - Ax?B - X?0 Variables d'écart Une contrainte inégalité a1x1+…+ anxn?b, se transforme en une égalité a1x1+…+ anxn+e=b avec e?0, e variable d'écart associée à la contrainte. Forme standard , n+m variables Forme canonique système d'équations avec n+m variables - avec : ,, Transformation linéaire équivalente On obtient une forme standard équivalente en transformant les différentes équations par des combinaisons linéaires des m+1 équations entre elles. Exemple : - 6x1+5x2+6x3+e1=30 - 8x1+6x2+3x3+e2=24 - F= x1+ x2+ x3 -10x1-7x2+e1-2e2=-18 8 x1+6 x2+3x3+ e2=24 6F-0 x1+ x2+0 x3- e1+0F=6F-30 Principe de recherche de l'optimum initialisation On prend pour première solution admissible x1=0, xn=0, n+m inconnues pour m équations. n inconnues de trop, qu'on peut fixer à n'importe quelle valeur et trouver les valeurs des m restantes. On fait le choix le plus simple x1=0, xn=0 : il reste à trouver e1, …, em. Exemple : - 6x1+5x2+6x3+e1=30 - 8x1+6x2+3x3+e2=24 - F= x1+x2+x3 x1=x2=x3=0 - e1=30 - e2=24 F=0 les x1, x2 et x3 sont les variables hors base, celles que l'on met à zéro. les e1, e2 sont les variables de base. amélioration de la solution initiale autre choix de variables nulles : Conclusion Il reste à déterminer les critères de choix d'un ensemble admissible de variable hors base (=0). Il faut trouver un critère qui indique si la solution est optimum ou pas. 297180016764000Initialisation choix d'une nouvelle solution 33147003810000optimum fin Cours n°6 : Algorithme du simplexe, méthode du tableau Représentation de la forme standard par un tableau Exemple : - 6x1+5x2+6x3+e1=30 - 8x1+6x2+3x3+e2=24 - F= x1+x2+x3 - n=3 et m=2 x1 x2 x3 e1 e2 b ratios L1 6 5 6 1 0 30 12496808636000L2 8 6 3 0 1 24 L3 1 1 1 0 0 F Pivot interprétation du tableau d'une ligne Li, on revient à l'équation classes Première solution évidente On fait x1=x2=x3=0 Choix du pivot : intersection d'une colonne q et d'une ligne p Nouveau tableau équivalent choix de la colonne q règle n°1 : on choisit la colonne dont l'élément de la ligne Cq (L3) est positif. ici q=2 (au hasard dans ce cas, vu que les trois coefficients sont positifs) Choix de la ligne p règle des ratios : on forme les m ratios on choisit la ligne p correspondant au plus petit ratio positif on en déduit l'élément pivot (situé en {2,2} dans l'exemple) pivotage vers un nouveau tableau On transforme chaque ligne par combinaison linéaire avec la ligne du pivot (ici, c'est la ligne 2, L2) de manière à n'obtenir que des 0 pour la colonne q. la ligne 1 devient : la ligne 2 du pivot devient : L3=L3-L2 x1 x2 x3 e1 e2 b ratios L1 0 1 10 L2 1 0 4 L3 0 0 F-4 On dit que la variable x2 est rentrée dans la base et la variable e2 est sortie de la base. Solution à la deuxième itération : x1=0 x2=4 x3=0 e1=10 e2=0 Test d'optimalité Si les coefficients c correspondant aux variables hors base sont tous négatifs, alors le F obtenu est le maximumc'est le pivot x1 x2 x3 e1 e2 b ratios L1 … … … … … … … L2 … … … … … … … L3 0 0 F- tous les c correspondants aux variables hors base sont négatifs. Cours n°7 : Complément de l'algorithme du simplexe Analyse du tableau final Test de l'optimalité sur la dernière ligne du tableau x1 x2 … xn e1 em F c1 c2 … cn cn+1 cn+m F-nombre qui représente la valeur optimale de F. c1x1+ c2x2+ …+cnxn+ cn+1e1+ …+cn+mem= F- Il y a n valeurs nulles parmi les Ci et m valeurs restantes (en général, ?0) cpour l'indice k correspondant aux variables hors base. Il y a n variables xk dont les valeurs sont les coefficients e(m). F-=0 Foptimal= F=c1x1+ c2x2+ …+cnxn+ cn+1e1+ …+cn+mem+ Tests d'arrêt : variation des variables xi et ej autour des valeurs Optimales : Variations admissibles : lorsque xi=0 ou ej=0, Les autres variables ne sont pas nulles mais elles sont positives ou =0. Si les ci non nuls sont négatifs alors <0 avec toute variation admissible. Conséquence : si on cherche un minimumle test devient : les ci doivent être positifs (>0) Variables duales Optimum de F=cTx avec AX?B et X?0. La variation de la valeur optimale, lorsque B varie , on montre que :?=y1 ?b1+…+ ym ?bm Les m yi sont appelés les variables de sensibilité par rapport à B. Par définition, elles sont les variables duales. Problème dual Var X : au pb primal : Max. de F=cx et AX?B, on associe un nouveau pb, le pb dual Var Y : au pb dual : Min. de G=BY avec ATY?C Propriété : A l'optimum =. D'autre part, les sont les variables duales du problème primal. La dimension de Y est m (le nombre de contraintes inégalités). Application numérique x1 x2 x3 e1 e2 b L1 5 1 L2 1 0 L3 0 0 F- x1=0 e1=0 x2= e2=0 x3= , ?= ?b1+ ?b2 Exceptions il y a à la fois des contraintes de type ? et ?. il y a aussi des contraintes = x1+2x2?3, x1 et x2?0 Variable d'écart : x1+2x2-e1=3 Cela pose un problème dans le démarrage de l'algorithme car la matrice des variables ei n'est plus unité. Solution : on introduit une variable supplémentaire dans l'équation des contraintes : x1+x2-e1+?1=3 et on modifie la relation : F=>c1x1+…+cn+mxm+M?n=F avec M grand. Si : M grand : petit M?? : =0 Court n°8 : Optimisation dans les graphes Définition et représentation d'un graphe rappel : ensemble d'éléments Xi (sommets) avec une application qui à l'élément Xi fait correspondre d'autres éléments Xj (application non univoque). On représente graphiquement par : 14859009144000 Xj 148590014478000148590014478000Xi Xk Xl propriétés - arc XiXj orienté on non : peut être valué : 320040016764000- chemin : suite d'arcs adjacents : X1 X2 X3 20574004572000- circuit : X1 X2 42291003810000 X4 X3 - arbre : graphe dans lequel il n'y a pas de circuit Différents types de problèmes de R.O. s'exprimant par des graphes 1257300122555xA1 x12 xA3 x13 x3B x2B 00xA1 x12 xA3 x13 x3B x2B problème du plus court chemin X1 X2 On cherche à minimiser le coût pour aller de A en B, c'est-à-dire trouver le chemin optimum. A B Départ Fin X3 Aide à la décision où l'inconnue est le chemin : plusieurs chemins possibles : AX1X2B, AX1X3B, en nombre fini. Le coût = xA1+x13+x3B problème de flot maximum 114300015875?A1 ?12 ?A2 ?13 ?2B ?4B ?32 ?43 00?A1 ?12 ?A2 ?13 ?2B ?4B ?32 ?43 X1 X4 On veut écouler un flot de A en B en maximisant ?A1+?A2=?4B+?2B A B X3 X2 Contraintes : - en un sommet, ? flot entrant = ? flot sortant conservation des flux - canalisation 0