Programmation Linéaire PDF

Preview

Summary

Download Programmation Linéaire PDF

Description

PROGRAMMATION LINÉAIRE I/ Méthodes et algorithmes de la recherche opérationnelle La recherche opérationnelle (RO) c’est : - Structurer - Coordonner - Modéliser - Raisonner logiquement - Trouver une solution appropriée aux problèmes organisationnels  Technique récente datant de la seconde guerre mondiale appliquée dans le cadre des opérations militaires de logistique 17ème : décision dans l’incertain, dans les jeux de hasard 1917 : théories des files d’attente qui étudie les solutions optimales de gestion de files d’attente 1921-1925 : théorie mathématique des jeux qui étudie les problèmes pour lesquels les choix des joueurs ont des conséquences pour l’adversaire.  Depuis, la recherche opérationnelle est utilisée pour les problèmes d’optimisation dans différents domaines : logistique, transport, production, informatique, télécommunication etc. II/ Programmation linéaire Programmation linéaire (PL) : méthode permettant d’obtenir le meilleur résultat d’un modèle mathématique dont les besoins sont représentés par des équations linéaires. Le meilleur résultat conduira 9 la minimisation des co:ts ou 9 la maximisation des profits.  La PL est une technique mathématique largement utilisée pour aider les responsables des opérations 9 planifier et 9 prendre les décisions nécessaires 9 l'allocation des ressources. Les modles de la PL visent 9 maximiser ou minimiser certaines quantités  cette propriété correspond 9 la fonction objectif d'un problème PL. ATTENTION : des valeurs optimales n’existent pas 9 tous les coups Méthode et étapes de la modélisation : 1) Objectif 2) Définir les variables et leurs significations 3) Écrire la fonction objectif 4) Contraintes ATTENTION : la fonction objectif et les contraintes doivent être exprimés sous formes d’équations ou inéquations linéaires. Exercice : Une entreprise propose trois types de produits : A, B and C . Les co:ts de production sont : 11, 12 et 8 pour A, B et C respectivement. La demande est, au moins, 25 pour A, 13 pour B et 30 pour C. Toutes les commandes devraient être satisfaites. Étant donné que les produits A, B et C sont complémentaires, il existe certaines réglementations du marché : - La production de A ne peut pas dépasser le double de B. - La production de A doit être supérieure d'au moins 5 unités 9 celle de C. Quel est le plan de production qui minimise le co:t de production de cette entreprise ? Solution :

1) 2) 3) 4)

Objectif = minimiser le co:t de production Variables : xi : quantité de production du produit i avec i = A, B, C Fonction objectif : Min Z = 11 xA + 12 xB + 8 xC Contraintes : o xA ≥ 25 o xB ≥ 13 o xC ≥ 30 o La production de A ne peut pas dépasser le double de B : xA ≤ 2 xB o La production de A doit être supérieur d’au moins 5 unités 9 celle de C : xA ≥ 5 + xC o xA, xB et xC ≥ 0

Le programme linéaire est donc : Min 11xA + 12xB + 8xC xA ≥ 25 xB ≥ 13 xC ≥ 30 xA ≤ 2 xB xA ≥ 5 + xC xA, xB et xC ≥ 0 Exercice : SEC est une entreprise qui produit deux appareils électroniques: Xpod et Sbluberry. Chaque Xpod nécessite 4 heures de travail électronique et 2 heures dans l’atelier de montage. Chaque Sblueberry nécessite 3 heures en électronique et 1 heure en assemblage. Pour une semaine, 240 heures de temps électronique sont disponibles et 100 heures d'heure de département d'assemblage sont disponibles. Chaque Xpod vendu rapporte 7 $; chaque Sblueberry produit peut être vendu pour un bénéfice de 5 $. Quel est le plan de production que la SEC devrait suivre afin de maximiser son profit ? Solution : 1) 2) 3) 4)

Objectif = maximiser le profit Variables : x = quantité de Xpod fabriqué et y = quantité de Sbluberry fabriqué Fonction objecitf = Max (Z) = 7x + 5y Contraintes : o 4x + 3y ≤ 240 o 2x + y ≤ 100 o x et y ≥ 0

Remarque : si le modèle PL ne comprend que 2 variables, nous pouvons utiliser la méthode graphique pour optenir des solutions optimales. Le programme linéaire est donc : Max (Z) = 7x + 5y 4x + 3y ≤ 240 2x + y ≤ 100 x et y ≥ 0 Méthode : 1) Construire un repère orthonormé (O, x, y) 2) Convertir les inégalités des contraintes en égalités 3) Tracer les droites représentant les différentes contraintes 4) Définir la région des solutions réalisables

L’intersection des deux courbes nous donne la solution : x =30 et y = 40 d’où Z = 410 Exercice : Une entreprise fabrique 2 objets (de type A et B) en matière plastique obtenue par mélange de 2 produits de base(PX et PY). - Pour obtenir une unité de A, il faut 3 unités de PX et 1 de PY. - Pour obtenir une unité de B, il faut 1 unité de PX et 2 de PY. - La marge bénéficiaire est de 2 sur A et de 1 sur B. - On dispose en stock de 15 unités de PX et de 10 unités de PY. Quel est le plan de production qui donne le meilleur profit ? Solution : 1) Objectif = maximiser le profit 2) Variables : x = le nb d’objets A 9 fabriquer, y = le nb d’objets B 9 fabriquer 3) Les contraintes peuvent être résumé dans la matrice suivante : A B max dispo PX 3 1 15 PY 1 2 10 D’où : 3x+ y ≤ 15 x + 2y ≤ 10 où x et y ≥ 0

Exercice : Fabrication de 2 produits P1 et P2 sur trois ateliers A1, A2 et A3. P1 nécessite le passage dans A1 et A3. P2 nécessite le passage dans A2 et A3. Les temps de fabrication de chacun des produits dans chacun des ateliers ainsi que les capacités hebdomadaire résiduelles de ces ateliers sont donnés par :

Combien faut-il produire en P1 et P2 par semaine pour maximiser le profit net de l’entreprise. Solution : 1) 2) 3) 4)

Objectif = maximiser le profit Variables : x1 et x2 la quantité de biens 9 produire par semaine Fonction objectif : Max Z = 3x1 + 5x2 Contraintes : o x1 ≤ 4 o 2x2 ≤ 12 o 3x1 + 2x2 ≤ 18 o x1, x2 ≥ 0

Remarque : dans les cas où nous avons plus que 2 variables, il faut utiliser un tableur Excel...