Remerciez-le!

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

Introduction ` a la Programmation Math´ ematique Programmation Lin´ eaire et Op

Introduction ` a la Programmation Math´ ematique Programmation Lin´ eaire et Optimisation Combinatoire Y. Hamam & H. Talbot Groupe E.S.I.E.E. Cit´ e Descartes, BP 99 93162 Noisy-le-Grand CEDEX 7 avril 2009– version 0.2 2 Table des mati` eres Introduction 5 I Th´ eorie, formulation et algorithmes de r´ esolution 9 1 Mod´ elisation pour la programmation math´ ematique 11 2 Programmation lin´ eaire 19 2.1 Un exemple : formulation, repr´ esentation et r´ esolution . . . . . . . . . . . . . . . 19 2.1.1 Le probl` eme de la nourriture pour chiens . . . . . . . . . . . . . . . . . . 19 2.1.2 Cas de ﬁgure des solutions possibles . . . . . . . . . . . . . . . . . . . . . 21 2.1.3 Recherche d’optimum . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 2.1.4 Un algorithme ´ el´ ementaire du simplexe . . . . . . . . . . . . . . . . . . . 22 2.1.5 R´ esum´ e . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 2.2 Cas limites, par l’exemple et approche g´ eom´ etrique . . . . . . . . . . . . . . . . 25 2.3 Algorithme du simplexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 2.3.1 Forme standard . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 2.3.2 Solutions de Base . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 2.3.3 Caract´ eristiques d’une solution de base r´ ealisable . . . . . . . . . . . . . 32 2.3.4 Solution Optimale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 2.3.5 Coˆ uts r´ eduits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 2.3.6 Am´ elioration d’une solution de base . . . . . . . . . . . . . . . . . . . . . 36 2.3.7 Algorithme du simplexe . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 2.3.8 Illustration de l’algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . 37 3 Le simplexe en pratique 43 3.1 Cas limites . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 3.1.1 Solution unique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 3.1.2 Solutions multiples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 3.1.3 Solution non born´ ee . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 3.1.4 Solution d´ eg´ en´ er´ ee . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 3.1.5 Pas de solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 3.2 Initialisation de l’algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 3.2.1 M´ ethode avec les grands M dans la fonction de coˆ ut . . . . . . . . . . . 50 3.2.2 M´ ethode en deux temps en minimisant d’abord les variables auxiliaires . 50 3.3 Dualit´ e . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 3.3.1 Probl` eme primal/probl` eme dual . . . . . . . . . . . . . . . . . . . . . . . 50 3 4 TABLE DES MATI` ERES 3.3.2 Probl` eme vendeur-consommateur . . . . . . . . . . . . . . . . . . . . . . 50 3.3.3 Interpr´ etation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 3.3.4 Utilit´ e de la dualit´ e . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 3.3.5 Passer de la solution du primal au dual et vice-versa . . . . . . . . . . . 50 3.3.6 Algorithme primal-dual ? . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 3.4 Eﬃcacit´ e de l’algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 II Exemples 51 Introduction Cette introduction reprend quasi ”in extenso” l’introduction au m´ emoire HDR (Habilitation ` a Diriger des Recherches) de Y. Hamam[?], d’ailleurs, dans la suite de cet ouvrage nous nous servirons abondemment de ce m´ emoire sans y faire explicitement r´ ef´ erence. Les premiers travaux importants sur les techniques d’optimisation datent des ann´ ees cinquante avec le d´ eveloppement de la programmation math´ ematique lin´ eaire et non-lin´ eaire. Depuis d’in- nombrables travaux ont ´ et´ e publi´ es traitant de probl` emes tr` es vari´ es : continus et combinatoires, lin´ eaires et non-lin´ eaires, alg´ ebriques ou dans les graphes, d´ eterministes ou stochastiques. Travailler dans ce domaine n´ ecessite une maˆ ıtrise de toute la chaˆ ıne : de la mod´ elisation ` a l’op- timisation en passant par l’analyse num´ erique. Sans un de ces ´ el´ ements, il est diﬃcile de traiter des probl` emes r´ eels. Avant d’entamer la pr´ esentation de ces travaux il me semble n´ ecessaire de commencer par quelques remarques d’ordre g´ en´ eral pouvant expliquer ma d´ emarche en ce qui concerne la recherche et d´ eveloppement dans ce domaine. Pour r´ esoudre ce type de probl` eme, le chercheur va ˆ etre confront´ e d` es l’amorce ` a une s´ erie de choix d´ eterminant pour la suite des op´ erations. En eﬀet, il lui faut tout d’abord choisir un mod` ele. Cette op´ eration est des plus d´ elicates dans la mesure ou ce choix va d´ eterminer pour le moins le domaine de validit´ e de la (des) solution(s) obtenue(s). Si le choix se porte sur un mod` ele complexe (plus pr´ ecis au sens de la r´ ealit´ e physique) la manipulation risque d’ˆ etre coˆ uteuse (en temps de calcul) voire hasardeuse. Dans le cas ou un mod` ele plus simple est utilis´ e, le risque alors est grand d’obtenir des r´ esultats peu ou pas utilisables. De plus, le choix du mod` ele peut avoir une inﬂuence d´ eterminante sur la pertinence des m´ ethodes de r´ esolutions utilis´ uploads/Science et Technologie/ poly-optim-2009.pdf