Remerciez-le!

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

1 OPTIMISATION LINÉAIRE Madani BEZOUI madani.bezoui@gmail.com http://mbezoui.we

1 OPTIMISATION LINÉAIRE Madani BEZOUI madani.bezoui@gmail.com http://mbezoui.webs.com Année Universitaire 2014-2015 M. BEZOUI *** UMB.Boumerdes 2 Ceci est un manuscrit établit pour permettre aux étudiants de deuxième année Recherche Opérationnelle, de l’Université de Boumerdes, une bonne assimilation et une bonne révision des cours de ce module. Veuillez me signaler d’éventuelles erreurs de frappe de saisie,... à l’adresse mail suivante : "madani.bezoui@gmail.com". Merci. Ceci est un manuscrit établit pour permettre aux étudiants de deuxième année Recherche Opérationnelle, de l’Université de Boumerdes, une bonne assimilation et une bonne révision des cours de ce module. Veuillez me signaler les éventuelles erreurs de frappe de saisie,... à l’adresse mail suivante : madani.bezoui@gmail.com, Merci. Ceci est un manuscrit établit pour permettre aux étudiants de deuxième année Recherche Opérationnelle, de l’Université de Boumerdes, une bonne assimilation et une bonne révision des cours de ce module. Veuillez me signaler les éventuelles erreurs de frappe de saisie,... à l’adresse mail suivante : madani.bezoui@gmail.com, Merci. Ceci est un manuscrit établit pour permettre aux étudiants de deuxième année Recherche Opérationnelle, de l’Université de Boumerdes, une bonne assimilation et une bonne révision des cours de ce module. Veuillez me signaler les éventuelles erreurs de frappe de saisie,... à l’adresse mail suivante : madani.bezoui@gmail.com, Merci. Ceci est un manuscrit établit pour permettre aux étudiants de deuxième année Recherche Opérationnelle, de l’Université de Boumerdes, une bonne assimilation et une bonne révision des cours de ce module. Veuillez me signaler d’éventuelles erreurs de frappe de saisie,... à l’adresse mail suivante : madani.bezoui@gmail.com, Merci. c ⃝. M. BEZOUI. UMBB. Mai 2015. M. BEZOUI *** UMB.Boumerdes Table des matières 1 Introduction et Notions de bases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.1 Notions de modèle mathématique 5 1.1.1 La modélisation Mathématique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.1.2 Les modèles de la RO sont classes en deux grands groupes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.2 Programme Linéaire 5 1.3 Formulation d’un programme linéaire 6 1.4 Forme d’un Programme Linéaire (PL) 7 1.4.1 Forme canonique d’un PL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.4.2 Écriture matricielle d’un PL sous forme canonique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.4.3 Règles de passage vers une écriture sous une forme canonique . . . . . . . . . . . . . . . . . . . . . . . . 8 1.5 Forme standard d’un programme linéaire 8 1.6 Convexité et ensemble convexe 9 2 Méthode du simplexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.1 Base et solution de base 11 2.2 Optimalité en un point extrême 13 2.3 Critère d’optimalité 13 2.3.1 Formule d’accroissement de la fonction objectif . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.4 Critère d’optimalité 14 2.5 Algorithme du simplexe 15 3 Dualité en Programmation Linéaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 4 4 Notion de dualité en Programmation Linéaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 4.1 Problème dual d’un problème de programmation linéaire 21 4.2 Méthode de construction du dual 22 4.3 Propriétés de la dualité 23 4.4 Correspondance entre Primal et Dual 25 4.5 Interprétation économiques des variables duales 25 5 Compléments sur l’algorithme du simplexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 5.1 Modeles non bornes, non realisables et degeneres 27 5.2 Absence de solution de base réalisable de départ 27 6 Algorithme dual du simplexe Relations entre Primal et Dual . . . . . . . . . . . . . . . . . 29 M. BEZOUI *** UMB.Boumerdes Notions de modèle mathématique La modélisation Mathématique Les modèles de la RO sont classes en deux grands groupes Programme Linéaire Formulation d’un programme linéaire Forme d’un Programme Linéaire (PL) Forme canonique d’un PL Écriture matricielle d’un PL sous forme canonique Règles de passage vers une écriture sous une forme canonique Forme standard d’un programme linéaire Convexité et ensemble convexe 1. Introduction et Notions de bases Un modèle est forcément une description limitée et orientée de la réalité. Il est impossible de décrire de manière absolue la réalité à des ﬁns descriptives ou prédictives, sans même parler de l’intérêt d’une telle démarche (c’était l’utopie de Laplace et du déterminisme associé au paradigme mécaniste du XIXéme siècle). 1.1 Notions de modèle mathématique 1.1.1 La modélisation Mathématique Un modèle mathématique est un outil et un moyen qui permet a simuler un problème, situation ou un phénomène réel pour mieux le comprendre et de le résoudre. En vue de l’optimisation, résoudre un modèle par une méthode consiste à chercher des solutions concrètes dites décisions optimales. 1.1.2 Les modèles de la RO sont classes en deux grands groupes Modèles déterministes Système philosophique selon lequel les événements sont déterminés par des précédents, suivent une loi de causes à effets, donc ne fait pas appel au calcul de probabilité, on trouve ici deux grandes familles : Optimisation linéaire transport et d’affectation, programmation en nombres entiers(PLNE), graphes et réseaux..... Optimisation non-linéaire quadratique, fractionnaire, la programmation dynamique Modèles stochastiques : Se dit de phénomènes qui, partiellement, relèvent du hasard et qui font l’objet d’une analyse statistique, on peut citer les problèmes suivants : probabilistes, processus aléatoires, les ﬁles d’attentes, modèles de prévision et la théorie des jeux... 1.2 Programme Linéaire La programmation linéaire (PL) est un outil mathématique d’aide a la décision, elle consiste a optimiser (Minimiser ou maximiser) une fonction linéaire dite fonction économique ou fonction objectif exprimée en fonction d’un nombre de variables appelées variables de décisions sur un espace (ensemble) non vide obtenu à partir des contraintes du problème. 6 Chapitre 1. Introduction et Notions de bases 1.3 Formulation d’un programme linéaire Etant donné un problème d’ordre économique, en vue de l’optimisation, pour modéliser ce problème sous forme d’un PL, il faut identiﬁer soigneusement les trois éléments suivants : Ce sont les facteurs que l’on peut modiﬁer dans le système, elles décrivent les inconnus du problème et représentent des quantités utiles sur lesquelles des décisions seront prisent. Déﬁnition 1 (Variables de décisions). Ce sont les paramètres du système étudié et sur lesquels on ne peut apporter aucune modiﬁcation. Elles regroupent toutes les restrictions et conditions imposées au problème posé sous forme d’inégalités ou d’égalités (≤;≥;=). Déﬁnition 2 (Contraintes). Constitue la fonction a optimiser ou bien l’objectif à atteindre. Déﬁnition 3 (Fonction objectif). Une usine sis à Boumerdes, fabrique 2 produits P1 et P2 nécessitant des ressources d’équipement, de main d’oeuvre et de matières premières disponibles en quantité limitée. P1 et P2 rapportent à la vente 6$ et 4$ euros par unité. Quelles quantités (non entières) de produits P1 et P2 doit produire l’usine pour maximiser le bénéﬁce total venant de la vente des 2 produits ? Exemple 1 (Problème de Planiﬁcation de Production). M. BEZOUI *** UMB.Boumerdes 1.4 Forme d’un Programme Linéaire (PL) 7 Variables de décisions xi : quantité de produit i fabriqué. Fonction objectif à maximiser La fonction objectif f correspond au bénéﬁce total : f(x1,x2) = 6x1 + 4x2. On cherche donc : max x1,x2 [f(x1,x2) = uploads/Litterature/ poly-pl.pdf