Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

MINISTERE DE L’ENSEIGNEMENT SUPERIEUR ET DE LA RECHERCHE SCIENTIFIQUE UNIVERSIT

MINISTERE DE L’ENSEIGNEMENT SUPERIEUR ET DE LA RECHERCHE SCIENTIFIQUE UNIVERSITÉ MOULOUD MAMMERI DE TIZI-OUZOU FACULTÉ DES SCIENCES DÉPARTEMENT DE MATHÉMATIQUES MÉMOIRE DE FIN D’ÉTUDES EN VUE DE L’OBTENTION DU DIPLÔME DE MASTER EN MATHÉMATIQUES SPECIALITE : RECHERCHE OPERATIONNELLE OPTION : AIDE A LA DECISION THÈME : La programmation mathématique Avec les méthodes des points intérieurs. Présenté Par : Mr AREZKI RAFIK Devant le jury composé de : Mr M. MORSLI Professeur UMMTO President Mr M. CHEBAH M.A.A UMMTO promoteur Mr K. KASDI M.A.A UMMTO Examinateur Mr M. OUANES M.C.A UMMTO Examinateur Mr M. AOUANE M.A.A UMMTO Examinateur Sutenue le 08 .07.2013 à 11h00 Je Je Je Je remercie remercie remercie remercie tout d’abor tout d’abor tout d’abor tout d’abord « d « d « d « DIEU DIEU DIEU DIEU » tout puissant de m’ » tout puissant de m’ » tout puissant de m’ » tout puissant de m’ avoir avoir avoir avoir donné la santé et le courage pour donné la santé et le courage pour donné la santé et le courage pour donné la santé et le courage pour effectuer effectuer effectuer effectuer ce ce ce ce projet de fin d’étude, dans les meilleur projet de fin d’étude, dans les meilleur projet de fin d’étude, dans les meilleur projet de fin d’étude, dans les meilleures conditions es conditions es conditions es conditions Comme je Comme je Comme je Comme je tiens tiens tiens tiens à adresser à adresser à adresser à adresser toute la reconnaissance toute la reconnaissance toute la reconnaissance toute la reconnaissance et ma et ma et ma et ma gratitude à gratitude à gratitude à gratitude à : : : : Mon p Mon p Mon p Mon promoteur romoteur romoteur romoteur : Mr. : Mr. : Mr. : Mr. M. M. M. M. CHEBBAH CHEBBAH CHEBBAH CHEBBAH pour ses pour ses pour ses pour ses précieux conseil et précieux conseil et précieux conseil et précieux conseil et son son son son suivi suivi suivi suivi. . . . Je Je Je Je remercie remercie remercie remercie les membres du les membres du les membres du les membres du jury d’ jury d’ jury d’ jury d’avoir avoir avoir avoir accepter accepter accepter accepter d’examiner mon d’examiner mon d’examiner mon d’examiner mon travail. travail. travail. travail. Enfin, Enfin, Enfin, Enfin, je je je je tiens tiens tiens tiens à remer à remer à remer à remercier tous ce cier tous ce cier tous ce cier tous ceux qui ont contribués ux qui ont contribués ux qui ont contribués ux qui ont contribués de prés et de prés et de prés et de prés et de loin à la réalisation de ce travail de loin à la réalisation de ce travail de loin à la réalisation de ce travail de loin à la réalisation de ce travail Rafik Rafik Rafik Rafik AREZKI AREZKI AREZKI AREZKI Remerciements Remerciements Remerciements Remerciements J’ai l’immense plaisir de dédier ce modeste travail à : Mes très chers parents :HACENE ET BAYA. Mes frère :MOULOUD,TOUFIK et MOUNIR. Mes sœurs :mon oiseau KAHINA,KATIA et NADIA. MA CHERIE KAHINA A tous les membres de ma grande famille,oncles, tantes, cousins et cousines. Mes amis(es) Dédicaces Dédicaces Dédicaces Dédicaces Table de matière Table de matière Introduction générale…………………………………………1 Chapitre 01 : Notions de bases : 1.1. Introduction : 1.2. Ensembles et fonctions : 1.2.1. Ensembles convexes ………………………………………….3 1.2.2. Fonctions convexes:…………………………………………...5 1.2.3. Matrices et vecteurs ………………………….………………6 1.2.4. Convergence des suites dans ℝ et dans ℝ……………………9 Chapitre 02: Programmation mathématique : 2.1. Introduction …………………………………………….………10 2.2. Notions de base …………………………………………………10 2.3. Classification d’un programme mathématique : …………..…….11 2.4. Qualification des contraintes ……………………………………12 2.5. Existence et unicité de la solution ……………………………....12 2.6. Conditions d’optimalité (sans contraintes) …………………….12 2.7. Conditions d’optimalité : (avec contraintes)…………………….13 Table de matière Chapitre 03 : Programmation linéaire : 3.1. Introduction ……………..…………………………..……..16 3.2. Dualité…………………………..………………………….16 3.3. Autres définitions …………………………………..…..…..17 3.4. La résolution d’un programme linéaire (PL)..………….…..17 3.4.1. La résolution des programmes linéaires par la méthode du simplexe …………………………………………..……………………………… ….18 3.4.1.1. Algorithme du simplexe ……………………….18 3.4.1.2. Critère d’optimalité ……………………………19 3.4.1.3. Exemple numérique :……………...…………….19 3.4.2. La résolution des programmes linéaires par les méthodes des points intérieurs………………………………...………………22 3.4.3. Méthode de Karmarkar (présentation de la méthode)…....22 3.4.3.2. Le calcul de direction et de pas ……….….……...24 3.5. Algorithme de base………………………………….………25 3.5.1. Convergence de l’algorithme………………….26 3.6. Généralisation de l’algorithme de Karmarkar sur la programmation linéaire………………………. ……………………………….25 3.7. Tests numériques……………………………………..……..28 Chapitre 04 : programmation quadratique : 4.1. Introduction……………………………………….31 4.2. Méthodes de résolution d’un problème quadratique ……………………………………………………………………...31 Table de matière 4.3. Complémentarité linéaire monotone…………..32 4.4. Transformation d’un programme quadratique convexe en un programme complémentaire linéaire…………….32 4.5. Transformation d’un programme complémentaire linéaire monotone en un programme quadratique convexe……….34 4.6. La résolution d’un problème de complémentarité linéaire avec les méthodes des trajectoires centrales …………….35 4.6.1. Présentation de la méthode……………………….35 4.6.1.3. Facteur de centralité…………………39 4.6.1.4. Concept de proximité………………..39 4.6.1.5. Algorithme de la trajectoire centrale pour la programmation quadratique……………………….………………………………....39 4.6.1.6. La convergence de la méthode……………………..40 4.6.2. Méthode de trajectoire centrale avec poids 4 .6.2.1. Présentation de la méthode ……………………….40 4.6.2.2. Facteur de centralité ………………………………42 4.6.2.3. Concept de proximité…………………………….42 4.6.2.4. Calcul du pas de déplacement ……………………42 4.6.2.5. Algorithme de la trajectoire centrale avec poids pour la programmation quadratique …………………………………………………….…43 4.6.2.6. Convergence de l’algorithme …………………….44 4.6.2.7. Le calcul d’une solution initiale strictement réalisable ………………………………………………………………………….…44 4.7. Tests numériques …………………………….....45 Table de matière Chapitre 05 : la programmation non linéaire convexe avec les méthodes des points intérieurs sous contraintes linéaires : 5.1. Introduction ……………………………………………..50 5.2. Méthode de Karmarkar pour la résolution du programme non linéaire convexe sur un polyèdre 5.2.1. Présentation de la méthode…………………………………….50 5.2.2. Algorithme de Karmarkar pour la programmation non linéaire convexe …………………………………………………………………………….55 5.2.3. Convergence de l’algorithme …………………………………….55 5.2.4. Test numériques ………………………………………………….56 5.3. la méthode de trajectoire centrale : 5.3.1. présentation de la méthode …………………………………...58 5.3.2. Algorithme de trajectoire centrale pour la programmation convexe……………………………………………………………………………...61 5.3.3. Méthode de trajectoire centrale avec poids…………………... 62 5.3.3.1. Présentation de la méthode………………………………..…62 5.3.3.2. Le calcul de la direction de descente…………………………63 5.3.3.4. Calcul d’une solution initiale strictement réalisable …………65 5.3.3.5. Calcul du pas de déplacement ................…………………….66 5.3.3.6. Algorithme de trajectoire centrale avec poids pour la programmation convexe sur un polyèdre…………………………………………….67 5.3.3.7. Convergence de l’algorithme………………………………..67 5.3.4. Tests numériques……………………………………......69 Table de matière Chapitre 06 : définition et implémentation de logiciel MATLAB 6.1. Définition de logiciel MATLAB…………………..….74 6.2. Description de la fenêtre MATLAB ……..…….….….74 6.2.1. La barre de titre ………………………………..……74 6.2.2. La barre de menu ………………………….…..……75 6.2.3. La barre d’outils ……...…………….…………….…..76 6.2.4. La fenêtre de commande …………………………..….76 6.3. Méthode de travail ………..…………………………….76 6.3.1. Edition et sauvegarde des fichiers MATLAB …...76 6.3.2. Aide en ligne ………………………………………76 6.3.4. Création de fichiers de commandes et de fonctions utilisateur ……………………………………………………………………….77 6.3.4.1. Fichiers de commande (”script files”) …………...77 6.3.4.2. Fonctions ……………………...………………….77 6.4. Exemples d’illustration ………………………..78 Conclusion générale …………………………………………….93 Annexe……………………………………………………..……..94 Bibliographies……………………………………………..……..95 Introduction générale 1 Introduction générale: La recherche opérationnelle peut être définie comme l'ensemble des méthodes et techniques rationnelles orientées vers la recherche de la meilleure façon d'opérer des choix en vue d'aboutir au résultat visé ou au meilleur résultat possible. Dès le XVIIe siècle, des mathématiciens comme Blaise Pascal tentent de résoudre des problèmes de décision dans l'incertain avec l'espérance mathématique. D'autres, au XVIIIe et XIXe siècle, résolvent des problèmes combinatoires. Au début du XXe siècle, l'étude de la gestion de stock peut être considérée comme étant à l'origine de la recherche opérationnelle moderne avec la formule du lot économique (dite formule de Wilson) proposée par Harris en 1913. Mais ce n'est qu'avec la Seconde Guerre mondiale que la pratique va s'organiser pour la première fois et acquérir son nom. En 1940, Patrick Blackett est appelé par l'état-major anglais à diriger la première équipe de recherche opérationnelle, pour résoudre certains problèmes tels que l'implantation optimale de radars de surveillance ou la gestion des convois d'approvisionnement. Le qualificatif « opérationnelle » vient du fait que la première application d'un groupe de travail organisé dans cette discipline avait trait aux opérations militaires. La dénomination est restée par la suite, même si le domaine militaire n'est plus le principal champ d'application de cette discipline. Après la deuxième guerre mondiale, la méthode du simplexe s’est imposée comme la seule méthode efficace pour la résolution des programmes linéaires (PL). EN 1979, Kachian a découvert le premier algorithme de type point intérieur projectif de complexité polynomiale, pour des instances des grandes dimensions l’algorithme s’avéra inefficace. En 1984 Karmarkar a crée un algorithme qui révolutionna toutes les recherches dans les domaines des algorithmes de complexité polynomiale, grâce à son algorithme Karmarkar a palie aux insuffisances de l’algorithme de Kachian. L’apparition de l’algorithme de Karmarkar a permis le développement des méthodes de points intérieurs qui se sont révélées comme une véritable alternative à la méthode du simplexe.sur tout après la découverte par Klee & Minty en 1972 d’un exemple prouvant que le simplexe peut aller jusqu’à une complexité exponentielle. Les méthodes de points intérieurs partent d’un point intérieur au domaine des solutions réalisables, puis au moyen d’une stratégie fixée (trajectoire centrale,...) déterminent une valeur approchée de la solution optimale. Parmi les avantages de ces méthodes par rapport à la méthode du simplexe, on peut uploads/Geographie/ arezki-rafik.pdf