Remerciez-le!

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

2-656 MDRO - SÉANCE 3 INTRODUCTION À LA PROGRAMMATION LINÉAIRE Dans cette séanc

2-656 MDRO - SÉANCE 3 INTRODUCTION À LA PROGRAMMATION LINÉAIRE Dans cette séance nous introduirons un des outils les plus puissants et les plus utilisés de la recherche opérationnelle: la programmation linéaire. À l'aide de deux exemples nous verrons:  Comment modéliser un programme linéaire dans Excel  Les principes de base de la programmation linéaire et comment écrire le modèle mathématique correspondant à un programme linéaire  Comment résoudre graphiquement un programme linéaire à 2 variables  Comment résoudre un programme linéaire à l'aide du Solveur d'Excel 1 - INTRODUCTION À LA MODÉLISATION D'UN PROGRAMME LINÉAIRE À L'AIDE D'EXCEL (cf. Exemple 3.1 – Choix de production chez Monet’s, W&A Sec. 3.3, pp.69-78)  Cie Monet produit 4 types de cadres (pour photos ou posters) codés 1, 2, 3 et 4  Les 4 modèles diffèrent en taille, forme et types de matériaux utilisés  Chaque modèle requiert pour sa fabrication certaines quantités des 3 types de ressources suivantes :  Main d’œuvre  Métal  Verre Types de cadres 1 2 3 4 Heures de main d'œuvre 2 1 3 2 Qté de métal (oz/ cadre) 4 2 1 2 Qté de verre (oz/cadre) 6 2 1 2 Prix de vente unitaire $28,50 $12,50 $29,25 $21,50  La consommation de chacune de ces ressources implique des coûts Salaire horaire $8,00 Coût du métal ($/oz) $0,50 Coût du verre ($/oz) $0,75  Prix de vente pour chaque type de cadre Profit unitaire pour chacun P.ex. Cadre type 1 Profit unitaire = prix – coût des ressources = 28,50 – ( 2h * 8 $/h + 4 oz * 0,50 $/oz + 6 oz * 0,75 $/oz) = 6 $  La demande pour chacun des types de cadres est limitée Ventes maximales 1000 2000 500 1000 Question : Quelle quantité de chaque type de cadre devrait-on produire afin de maximiser les profits ? Construisons le modèle Excel de Monet Conseil : Pour faciliter la construction, l’interprétation et le « débuggage » d’un modèle Excel suivre une convention de présentation cohérente et systématique, par exemple :  Colonnes  décisions (variables) ex. : quantités à produire de chaque type de cadre  Lignes  activités de production ou ressources consommées (c.f. fig. 3.1, p.73, et fichier Monet.xls sur le site) Pour construire le modèle Excel de Monet on procèdera comme suit: 1. Définir les variables du modèle (les décisions sur lesquelles on peut agir !) Qté produite de chaque type de cadre  Plan de production 2. Calculer les conséquences physiques: Utilisation des ressources = Somme ( Qtés produites  Besoins unitaires du produit) Truc Excel : Fonction SOMMEPROD  produit scalaire pour matrices/vecteurs de tailles compatibles  multiplie entre eux les éléments correspondants des vecteurs puis additionne ces produits !  renvoie un nombre Rem : Faire référence globale pour cellules des Qtés ( en utilisant la fonction F4)  Copier et coller plus facile pour chaque type de pièces 3. Calculer les conséquences économiques pour obtenir les Profits Revenus = Somme ( Qtés  Prix de vente unitaire ) Coûts main d’œuvre, métal, verre Profits = Revenus – Somme (Coûts) Question : Quelle sera la 1ère ressource à manquer ? Truc : Utiliser l’outil Valeur Cible (Goal Seek en anglais) Rem : tester par essai et erreur tous les plans de productions possibles ne serai vraiment pas efficace … mieux vaut utiliser la puissance de calcul de l’ordinateur pour effectuer ces essais … bref, utiliser le SOLVEUR d’Excel … du coup on aura la GARANTIE d’avoir obtenu la solution OPTIMALE au problème. 2 – PROGRAMMATION LINÉAIRE Dans l’exemple de Monet on a vu que certains plans de production n’avaient aucun sens, par exemple ceux qui utilisaient plus de ressources que disponible. Pour éviter ça on va formuler des Programmes Linéaires avec nos variables de décisions  (Modèles mathématiques) Qu’est-ce que la programmation linéaire ? • Outil mathématique qui sert à trouver la solution optimale d’un problème compte tenu d’un ensemble de conditions contraignantes. • Applications: – déterminer le nombre optimal de machines. – établir l’horaire de départ des avions, trains,… – développer des plans financiers – trouver la meilleure combinaison de matières premières afin de respecter des exigences sur le produit fini. Programme linéaire (PL) comprend :  Variables de décision : représentent les décisions à prendre, ce sont les aspects du problème réel sur lesquelles on peut agir directement (ex. qtés à produire, etc…)  Contraintes Relations liant les variables de décision entre elles Elles restreignent les V.Décision à prendre uniquement des valeurs qui ont du sens par rapport au problème réel étudié Elles peuvent être nombreuses Elles doivent être linéaires Ex : Utilisation/consommation de Métal  Quantité disponible Si on avait eu un contrat avec un distributeur pour lui fournir au moins 1000 cadres du type 2 alors on aurait eu la contrainte suivante Qté type 2  1000  Fonction objectif (c’est une fonction des variables de décision) Mesure de performance choisie pour déterminer la meilleure solution On va maximiser ou minimiser cette fonction (selon ce qu’elle mesure) 1 seule dans un modèle PL Ex : Max Profits ou Min Coûts PL  allouer des ressources limitées (c-à-d. en respectant des ``contraintes’’) afin d’optimiser une certaine fonction objectif. Pourquoi les modèles linéaires sont ils importants? • Une grande variété de problèmes sont naturellement modélisés avec la formulation linéaire et d’autres peuvent facilement être approximés par cette structure. • Il existe des techniques très efficaces de résolution pour ces modèles (algorithme du simplexe) • Les résultats obtenus après résolution du modèle fournissent des informations sur la sensibilité de la solution optimale par rapport à des changements dans les paramètres ou les coefficients du problème. Conditions pour avoir un Programme Linéaire (PL) : 1) Une fonction objectif à Maximiser ou à Minimiser 2) La fonction objectif et les contraintes sont des sommes de termes linéaires: i) pas de produits ou divisions entre variables ii) pas de fonctions mathématiques, c-à-d. exposants, valeurs absolues, logarithmes, etc…) iii) pas de conditions logiques, fonctions SI … 3) Contraintes de Non Négativité pour chaque variable de décision 4) Il n’y a aucune inégalité stricte (pas de < ou de > ) Remarque : s’il y a des coûts fixes mais qu’ils ne sont pas influencés par les décisions alors il ne sert à rien de les inclure dans le modèle en tenir compte uniquement pour le calcul final de la valeur de la fonction objectif 2.1 Formulons le PL de Monet (W&A p.70) 1. Définir les variables de décision : X1, X2, X3, X4 : quantité produite de cadres de type 1, 2, 3 et 4 respectivement 2. Contraintes : Ressources Main d’œuvre 2 X1 + X2 + 3 X3 + 2 X4  4000 Métal 4 X1 + 2 X2 + X3 + 2 X4  6000 Verre 6 X1 + 2 X2 + X3 + 2 X4  10000 Demande Nb Max cadres type 1 X1  1000 Nb Max cadres type 2 X2  2000 Nb Max cadres type 3 X3  500 Nb Max cadres type 4 X4  1000 Rem. : A. Dans une contrainte toutes les variables sont placées du côté GAUCHE de la relation (convention d’écriture) B. Le côté DROIT est souvent appelé Membre de droite ou ``Right Hand Side’’ (RHS) en anglais. Il contient  un nombre qui est un paramètre du modèle (connu à l’avance et sur lequel on n’a pas vraiment de contrôle direct)  représente la limite de la ressource correspondant à cette contrainte  ne pas y inscrire une formule utilisant les variables de décision car alors il y aura des problèmes d'interprétation avec les rapports que fournit le Solveur ET si nécessaire 3. Contraintes de non négativité X1  0, X2  0, X3  0, X4  0 4. Contraintes d’intégralité (si besoin – pour forcer les variables à ne prendre que des valeurs entières !) 5. Fonction objectif : Max Z = Profits = 6 X1 + 2 X2 + 4 X3 + 3 X4 Note : les coefficients correspondent au profit unitaire de chaque type de cadre Cadre 1  Prix de vente = 28,50$ Coût de MO = 2h x 8$/h = 16$ Coût du Métal = 4oz x 0,50$/oz = 2$ Coût du Verre = 6oz x 0,75$/oz = 4,50$ Profit unitaire = Prix de vente – Somme des coûts = 28,50 – ( 16 + 2 + 4,50) = 6 $ Etc. 2.2 Autre exemple – le cas de PROTRAC (EGSMW pp.69-72) Contexte :  Fabricant de machinerie lourde  Usine produit 2 modèles de « tracteurs » E9  travaux de construction F9  exploitation forestière  Profits unitaires E9  5000$ F9  4000$  Fabrication comporte 2 étapes E9 F9 Total Disponible Atelier A 10h 15h 150h Atelier B 20h 10h 160h  Tests véhicules E9  30h F9  10h Entente syndicale : le nombre d’heures de tests ne peut baisser plus que 10% en dessous de 150h  Politique uploads/Industriel/ programme-lin.pdf