Remerciez-le!

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

PROGRAMMATION LINÉAIRE Chapitre 1: Formulation d’un programme linéaire (1/2) fa

PROGRAMMATION LINÉAIRE Chapitre 1: Formulation d’un programme linéaire (1/2) faycel.mtar@esprit.tn Euler: « Il n’y a rien dans le monde qui ne se réalise sans la volonté de minimiser ou Citation 2 PL : Modélisation se réalise sans la volonté de minimiser ou maximiser quelque chose » Processus d’optimisation Modélisation Problème Modèle Mise en œuvre Résolution 3 Mise en œuvre Résolution Décision Solution Interprétation PL : Modélisation Objectifs du chapitre 1 À la fin de ce chapitre, l’étudiant sera capable de : Formuler un programme linéaire modélisant un problème d’optimisation: (définir les3 composantes principales) 1. Les variables de décisions: les variables dont les valeurs sont sous notre contrôle et influencent le système 4 PL : Modélisation sous notre contrôle et influencent le système « ce que vous pouvez contrôler » 2. La fonction-objectif: expression mathématique qui utilise les variables de décisions pour exprimer l'objectif . « Que cherche-t-on à optimiser ? » 3. Les contraintes liés au PL: expressions mathématiques qui utilise les variables de décisions pour décrire les limites . « Quelles sont les contraintes du problème ? »  Classifier le type du problème: selon la nature des variables de décision (PLNE: PL en nombres entiers, PL pour les autres) Modèles linéaires et non linéaires 5 Supposons que chaque fois que des variables de décision apparaissent dans la fonction objective et dans les contraintes d’un modèle d’optimisation, les variables de décision sont toujours multipliées par des constantes PL : Modélisation toujours multipliées par des constantes et additionnés. Un tel modèle est un modèle linéaire. Si un modèle d’optimisation n’est pas linéaire, alors c’est un modèle non linéaire. Modèles en nombre entiers et modèles continus 6 Si une ou plusieurs variables de décision doivent être entières, alors nous disons qu’un modèle d’optimisation est un modèle entier. PL : Modélisation Si toutes les variables de décision sont libres d’assumer des valeurs fractionnaires, alors le modèle d’optimisation est un modèle non entier. Les modèles entiers sont beaucoup plus difficiles à résoudre que les modèles non linéaires. Modèles statiques et modèles dynamiques 7 Un modèle statique est un modèle dans lequel les variables de décision n’impliquent pas de séquences de décisions sur plusieurs périodes. PL : Modélisation Un modèle dynamique est un modèle dans lequel les variables de décision impliquent des séquences de décisions sur plusieurs périodes. Modèles déterministes et modèles stochastiques 8 Supposons que pour toute valeur des variables de décision, la valeur de la fonction objective et si oui ou non les contraintes sont satisfaites est connu avec certitude. Nous avons alors un modèle déterministe. PL : Modélisation Si ce n’est pas le cas, nous avons un modèle stochastique. Plan du cours Chapitre 1 : Formulation d’un programme linéaire Chapitre 2 : Résolution graphique Chapitre 3 : Résolution algébrique 9 PL : Modélisation Chapitre 3 : Résolution algébrique Chapitre 4 : La Méthode de Simplexe Chapitre 5 : Dualité Chapitre 6 : Analyse de sensibilité Modélisation: exemple1 (introductif) Après avoir chômé pendant quelques années, un jeune homme a eu l’opportunité de se transformer en fleuriste dans un hôtel à Djerba. Pour démarrer son commerce, il dispose d’un stock de 50 lys, 80 roses et 80 jonquilles. Il décide de suivre le conseil qui lui a été donné par un fleuriste espagnol qui visite notre pays : « La vente des bouquets est plus 10 PL : Modélisation qui visite notre pays : « La vente des bouquets est plus bénéfique que la vente des fleurs en vrac. Pour débuter faites les compositions suivantes : 10 lys, 10 roses, 20 jonquilles à 4 euros 10 lys, 20 roses, 10 jonquilles à 5 euros » Formulez le modèle adéquat qui décrit l’activité du jeune fleuriste. Les roses 11 PL : Modélisation Lys et jonquille 12 PL : Modélisation Les étapes de formulation du PL (Trois composantes principales) Identifier les variables du problème à valeurs non connues (variable de décision) et les représenter sous forme symbolique (exp. x1, x2 , …). Identifier les contraintes (les limites de la solution) du problème et les exprimer par un système d’équations 13 PL : Modélisation problème et les exprimer par un système d’équations linéaires. Identifier l’objectif ou le critère de sélection et le représenter sous la forme, d’une fonction linéaire des variables de décision, avec la mention maximiser ou minimiser. La modélisation: (art/expertise/ingénierie) Pour un problème donné, plusieurs formulations équivalentes Pas de méthode universelle 14 Pas de méthode universelle Apprentissage par pratique et réflexion Procéder méthodiquement, systématiquement, par simulation… PL : Modélisation Programmation linéaire c’est quoi ? Les problèmes de programmations linéaires sont généralement liés à des problèmes d’allocations de ressources limitées, de la meilleure façon possible, afin de maximiser un profit (fonction-objectif linéaire) ou de minimiser un coût. Le terme meilleur fait référence à la possibilité d’avoir un ensemble de 15 PL : Modélisation Le terme meilleur fait référence à la possibilité d’avoir un ensemble de décisions possibles qui réalisent le même objectif ou le même profit. Ces décisions sont en général le résultat d’un problème mathématique. Le terme " Programmation" signifie essentiellement planification. L'adjectif "linéaire" indique que toutes les fonctions mathématiques de ce modèle sont linéaires. . Domaines d’application (liste non exhaustive) Planification de production, Choix de produits à fabriquer Répartition des ressources Logistique Transport 16 PL : Modélisation Transport Affectation et gestion du personnel pour un projet Economie-finance: planification des investissements , gestion du portefeuille,… Ingénierie : Robotique, intelligence artificielle,… Modélisation: exemple 2 Diet problem Une personne doit décider de son régime alimentaire. – Elle a le choix entre deux types d’aliments (maïs, fèves) à mélanger pour un repas. – La quantité nécessaire par jour est de 400g. 17 PL : Modélisation – La quantité nécessaire par jour est de 400g. – Le régime stipule que la personne doit manger au moins 30% de protéines et au plus 5% de fibres. Données: Modélisation: Exemple 3 18 Un ébéniste fabrique des bureaux sous forme standard ou luxe. Des études de marché ont montré que pour l’année à venir, les possibilités de vente s’élèvent à 300 unités pour le modèle luxe et à 400 unités pour le modèle standard. L’approvisionnement en bois est suffisant pour fabriquer annuellement 500 bureaux quel que soit le type. Par ailleurs, le temps de fabrication d’un modèle luxe est le PL : Modélisation double de celui d’un bureau de modèle standard. La capacité annuelle de fabrication est telle que, si tous les bureaux fabriqués étaient de type standard, on pourrait en fabriquer 700 au maximum. La vente d’un bureau sous le modèle luxe conduit à une marge unitaire sur coût variable égale à 700, celle d’un bureau de type standard égale à 500. On se propose de rechercher le programme annuel de fabrication conduisant au profit global maximum. Forme canonique d’un programme linéaire 19 PL : Modélisation Ecriture matricielle d’un PL 20 PL : Modélisation RO (PL) = modélisation et optimisation (linéaire) (1/2 ) La recherche opérationnelle (RO) est la discipline des méthodes scientifiques utilisables pour faciliter la prise de décisions face à des problématiques. 21 Grâce à elle, les décideurs peuvent analyser et mieux comprendre des situations complexes ou de grande dimension, aux interactions nombreuses et donc, faire des choix pertinents en toute connaissance de cause. Elle participe à l’aide à la décision. PL : Modélisation RO (PL) = modélisation et optimisation (linéaire) (2/2 ) 22 Discipline transverse associant les mathématiques appliquées, les statistiques et l’informatique, elle s’applique à des problèmes usuels et joue un rôle-clé PL : Modélisation dans la recherche de l’efficience. La recherche opérationnelle permet notamment d’optimiser l’architecture et le fonctionnement des organisations, qu’elles soient du ressort de la chaîne opérationnelle ou de la chaîne organique Problème 1: Service d’employés On considère un lieu de travail où il existe des besoins quotidiens en ouvriers. Les besoins en nombre d’ouvriers par jour sont donnés par le tableau suivant: Le salaire par jour s’élève Lundi Mardi Mercredi Jeudi Vendredi Samedi Dimanche 18 13 16 19 12 16 11 23 PL : Modélisation Quelques restrictions : Il faut que tout ouvrier soit engagé à plein temps. Chaque ouvrier travaille cinq jours consécutif et il se repose deux jours. Le travail durant les samedis et les dimanches doit être payé deux fois plus que le travail durant le reste des jours. Le salaire par jour s’élève à 100 DT. Déterminer le programme linéaire qui aidera le DRH à prendre les bonnes décisions. Problème 2: Investissements Un financier dispose de 5000MD à investir dans trois alternatives : actions, obligations et bon de trésor. Chaque dinar investi en actions rapporte 1,2 dinars après un an. Chaque dinar investi en obligations rapporte 1,5 dinars après deux ans. 24 PL : Modélisation ans. Chaque dinar investi en bon de trésor rapporte 1,8 dinars après quatre ans an. L’investissement en action et obligations est possible au début de chaque année. L’investissement en bon de trésor est possible à partir de la deuxième année. Formuler un programme linéaire qui maximise le capital du financier à la fin de la cinquième année Problème 3 : Livraison Quatre produits uploads/Management/ pl-modelisation1-sept21 1 .pdf