Optimisation Linéaire 2 eme Année Licence RO (Section B) (2017/2018) Plan du C

Optimisation Linéaire 2 eme Année Licence RO (Section B) (2017/2018) Plan du Cours. Introduction générale. Chapitre 1. Notions fondamentales de la programmation linéaire. Chapitre 2. Méthode du Simplexe. Chapitre 3. Dualité en programmation linéaire. Chapitre 4. Analyse post-optimal. Chapitre 5: Quelques algorithmes en programmation linéaire : Dual du Simplexe, Méthode révisée du Simplexe, Méthode big M. Références [1] V. Chvatal, Linear Programming, Freeman, 1983. [2] R. Faure, B. Lemaire et C. Picouleau, Précis de recherche opérationnelle – Méthodes et exercices d’application, Dunod, 2008. [3] M. Gondran, M. Minoux, Graphes et Algorithmes, Eyrolles, 1995. [4] Roseaux, Exercices et problèmes résolus de recherche opérationnelle : Tome 3 (Programmation linéaire et extensions, problèmes classiques), Dunod, 1985. [5] D. Maquin, Eléments de Théorie des Graphes et Programmation Linéaire, Ecole Nationale Supérieure d’Electricité et de Mécanique, Institut National Polytechnique de LORRAINE, mai 2008. [6] M. Minoux, Programmation Mathématiques : Théorie et Algorithmes, Tec & Doc Lavoisier ; Édition : 2e édition, 14 décembre 2007. [7] M. Sakarovitch, Optimisation combinatoire - Graphes et programmation linéaire, Hermann, 1984. 1 Introduction générale. Une première tentative, nous mène à dé…nir la recherche opérationnelle comme ensemble de méthodes (algorithmiques et mathématiques, après passage par la modélisation) a…n de prendre des décisions optimales ou proches de l’optimum pour des problèmes complexes, qui traitent de la maximisation d’un pro…t ou la minimisation d’un coût, à titre d’exemples : - Comment ordonnancer les tâches d’un projet, tout en minimisant sa durée ? - Comment investir ses millions de dinars de sorte à maximiser le pro…t obtenu après deux ans ? - Trouver un (plus court) chemin entre deux villes ... . La programmation linéaire est un domaine de la recherche opérationnelle qui a été développée la …n des années 1940, pour résoudre un certain nombre de problèmes d’allocation de ressources pour le gouvernement fédéral des États Unis d’Amérique et dont le développement peut se situer aux environs des années cinquantes, particulièrement à partir de 1951, l’année où G. Dantzig (1914-2005) découvrit l’algorithme du Simplexe, principal outil de résolution des programmes linéaires. L’importance de la programmation linéaire est liée aux deux facteurs suivants : : De nombreux problèmes de la vie économique (et même courante) peuvent se formuler comme des programmes linéaires. Ceci est d’autant plus vrai que depuis la deuxième guerre mondiale, les organisations économiques et sociales en grandissant en taille ont également grandi en complexité quant à leur fonctionnement. De nombreux problèmes nouveaux et complexes sont posés, qui ne peuvent se résoudre que par l’utilisation de techniques mathématiques adaptées. La programmation en est une de ces techniques. . Une autre raison est le développement des outils de calcul. En e¤et, il ne fait nul doute que le développement de la recherche opérationnelle et en particulier de la programmation est lié au développement des ordinateurs, particulièrement leurs fantastiques moyens de calcul permettant ainsi de résoudre des problèmes dont l’étude était impossible avant l’apparition de ces outils de calcul. De ce fait, résoudre un programme linéaire est un problème qui relève des mathématiques appliquées et l’algorithme du simplexe n’est qu’une méthode de calcul destinée à être programmée et utilisée sur un ordinateur. Notons que le terme de programmtion linéaire ne provient pas de l’expression "programmation" telle qu’elle est conçue par les informaticiens. A ce titre, l’expression programmation n’est pas la heureuse, mais cette terminologie est désormais classique. L’essentiel de ce cours présente les idées de base et les techniques de la programmation linéaire. En premier lieu, nous présentons d’abord le problème de programmation linéaire à travers quelques problèmes simples et didactiques. Une résolution géométrique est suggérée suivie par la méthode du Simplexe, qui est une méthode numérique de résolution de programmes linéaires. D’autres techniques de résolution et résultats sont proposés par la suite, après avoir introduit la notion de dualité et son intérêt pratique. 2 Chapitre 1. Notions Fondamentales de la Programmation Linéaire. 1.1 Dé…nitions. Soient D un domaine de Rn et une fonction f : D ! R. Dé…nition 1 Un programme mathématique, noté (P), est le problème qui consiste à chercher un élément x de D tel que f(x) soit le plus grand possible en cas de maximisation (resp. le plus petit possible en cas de minimisation). C’est-à-dire 8x 2 D : f(x)  f(x) en cas de maximisation (resp. 8x 2 D : f(x)  f(x) en cas de minimisation) Notation: Un programme mathématiques (P) est représenté par : Max x2D f(x) Problème de Maximisation min x2D f(x) Problème de minimisation Dé…nition 2 Soit (P) un programme mathématique.  Un point x 2 D est appelé "solution réalisable" de (P).  Le domaine D est appelé "domaine des solutions réalisables" de (P).  Une solution x de (P), lorsqu’elle existe, est appelée "solution optimale" de (P).  La fonction f est appelée "fonction objectif" de (P).  f(x), si x existe, est appelée "valeur du programme mathématique" (P). Remarque. Considérons le programme mathématique (P) min x2D f(x) Ceci revient à chercher x 2 D, tel que f(x) = min x2D f(x). On a : 8x 2 D : f(x)  f(x) ) 8x 2 D : f(x)  f(x) ) 8x 2 D : g(x)  g(x) (où g(x) = f(x); 8x 2 D) ) g(x) = Max x2D g(x) ) f(x) = Max x2D (f(x)) ) f(x) = Max x2D (f(x)) Ainsi, résoudre le programme mathématique min x2D f(x), revient à résoudre le programme mathéma- tique Max x2D (f(x)). Dans toute la suite, on considérera le problème de maximisation, sauf spéci…cations contraires. 3 1.2 Exemples. On se propose de trouver le modèle mathématique des deux problèmes proposés ci-dessous : 1.2.1 Un problème de production. Dans une usine, deux produits (A) et (B) sont fabriqués à partir de trois matières premières (I), (II) et (III). Le tableau ci-dessous résume la politique de production dans l’usine. (A) (B) (I) 6 5 (II) 10 20 (III) 1 0 Sachant que le fonctionnement de l’usine est linéaire, la direction dispose des matières premières (I), (II) et (III) en quantités respectives 6, 15 et 0:8. Le pro…t dû à la vente d’une unité du produit (A) (resp. (B)) est de 50 DA (resp. 45 DA) (les pro…ts sont proportionnels aux quantités produites). En quelles quantités, doit être produit (A) (resp. (B)), a…n de maximiser le pro…t net de l’usine ? Modélisation. Choix des ............................ Posons x1 : Quantité du produit (A) à confectionner. x2 : Quantité du produit (B) à confectionner. Formulation ............................................................. On constate (après simpli…cations) que x1  0; x2  0g ........................................................... ::::::::::::::::::::::::::::::::: ::::::::::::::::::::::::::::::::: ::::::::::::::::::::::::::::::::: 9 = ; ................................................... Détermination ........................................................ Posons z le pro…t net. On a :::::::::::::::::::::::::::::::::::::::::::::::::::::::: Donc on est amené à résoudre le problème (programme) suivant : (P) 8 < : Solution graphique d’un programme linéaire à deux variables. On constate que l’ensemble des points du plan P rapporté à un repère (orthonormé pour la beauté de la forme mais pas nécessaire !) fO; ! i ; ! j g véri…ant les contraintes est un polygone (pentagone) qu’on appellera polygone (ou région) admissible (ou réalisable). 4 La famille de droites d’isovaleur (dz)z2R données par dz : z =    x1 +    x2 représente une famille de droites parallèles. Elles ont toutes le même coe¢cient directeur et les points qui se trouvent sur une droite …xée dz0 représentent les points qui correspondent à la même valeurs du béné…ce z = z0. Dans la …gure ci-dessous, on a représenté les droites correspondant à z = 0 et z = 40 et à la plus grande valeur de z pour laquelle la droite dz à une intersection non vide avec le domaine des solutions réalisables (appelé aussi domaine ou ensemble de réalisabilité). Autrement dit, la plus grande valeur de z pour laquelle il existe une décision réalisable (admissible) qui assure cette performance. Donc la valeur optimale zmax = 360 7 , ce qui correspond à la solution optimale x ( ; )t. Notons qu’en déplaçant la droite dz vers la gauche la valeur de z diminue, contrairement à son déplacement vers la droite, où la valeur de z augmente. On remarquera que : (a) La solution optimale est un sommet du polygone réalisable, et dans cet exemple elle est unique. (b) Si la droite dz était parallèle au côté où l’optimum est atteint, alors l’optimum correspond à tous les points du côté (particulièrement la (ou les) extrémité(s)). Donc, dans tous les cas où existe une valeur optimale de z, il existe toujours au moins un sommet correspondant à une solution optimale. (c) Le long d’un côté du polygone, la valeur de l’objectif peut être soit constante ; soit strictement croissante, soit strictement décroissante. On peut donc suggérer l’algorithme suivant : (i) Choisir comme point de départ un sommet x du polygone admissible. (ii) Déterminer les côtés passant par ce sommet x. Trouver un côté le long duquel z croît. S’il n’y a pas, STOP : le x courant est optimal. (iii) Déterminer le sommet y à l’autre bout du côté et poser x = y. Retour en uploads/Industriel/ cours-opt-lin-chapitre1chapitre-2annexe1annexe-2chapitre-3-pdf.pdf

Tags
Industrielsolution programme linéaire réalisable optimale
Documents similaires
  • 24
  • 0
  • 0
Afficher les détails des licences
Licence et utilisation
Gratuit pour un usage personnel Attribution requise
Partager