Remerciez-le!

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

CORRIGE du TD N°1 : PROGRAMMATION LINÉAIRE EXERCICE 1 : corrigé 1- Modélisation

CORRIGE du TD N°1 : PROGRAMMATION LINÉAIRE EXERCICE 1 : corrigé 1- Modélisation sous forme de programme linéaire Désignons par et les nombres d’articles de chaque type (poterie, émaux sur cuivre) produits et par Z, le bénéfice généré par cette fabrication. et sont les variables de décision du modèle. Le problème comporte les contraintes suivantes : La production d’une poterie nécessite 1 heure de temps de fabrication et la fabrication de poteries en nécessitera heures. La fabrication d’un émail nécessite 4 heures de temps de fabrication et la production de émaux en nécessitera heures. La charge de travail pour les émaux ne doit pas dépasser celle de la poterie de plus de 160 heures, soit : La production d’articles de poterie ne doit pas excéder de plus de 30 unités la production d’émaux, soit : Le nombre d’articles fabriqués ne doit pas excéder 80 unités par jour, soit : Enfin remarquons que les variables et qui représentent des quantités produites, ne peuvent pas prendre des valeurs négatives. L’objectif ici est d’avoir un bénéfice global maximum sachant que le bénéfice est de 20 DH pour une poterie et de 60 DH pour un émail. Il s’agit donc de maximiser la fonction : C’est la fonction objectif ou économique du modèle. En rassemblant tous ces éléments, on peut donner une formulation algébrique du problème : [ ] Sous les contraintes { 2- Résolution graphique En dimension deux (2 variables de décision), il est facile de donner une représentation géométrique du problème dans un plan . Ici, chaque contrainte correspond à une inéquation linéaire donc à un demi-plan. Par exemple la première contrainte : définit un demi-plan situé en bas d’une « frontière » : la droite d’équation : . Les cinq contraintes du problème (les trois contraintes plus deux contraintes de non-négativité) déterminent cinq demi-plans dont l’intersection est non vide (ce n’est pas toujours le cas). Elle est représentée en hachuré sur la figure 1.1 ; on l’appelle domaine des solutions réalisables : tous les points de ce domaine satisfont l’ensemble des contraintes. Cet ensemble qui est ici borné (ce n’est pas toujours le cas) est un polygone convexe. Pour trouver la solution optimale dans cet ensemble infini de solutions réalisables, on peut utiliser deux techniques : le recensement des sommets du polygone ou les droites parallèles. Le recensement des sommets consiste à calculer les coordonnées de toutes les arêtes du polygone, ici OABCD, à les substituer dans l’expression de la fonction objectif Z et à retenir le ou les points réalisant la plus grande valeur de Z. L’autre technique part de la remarque que la fonction objectif peut être représentée par une famille de droites parallèles entre elles. Par exemple, les droites d’équations : Figure 1.1 : domaine des solutions réalisables Représentées sur le graphique correspondent à des bénéfices : . On peut qualifier ces droites de droites d’iso-profit. Tous les points de la première droite donnent un bénéfice nul mais un seul correspond à une solution réalisable : le point O. Tous les points de la deuxième droite situés à l’intérieur du polygone donnent un bénéfice de 600. Il est clair qu’en se déplaçant « vers le haut et vers la droite » dans les familles de droites (parallèles) d’iso-profit, on augmente le dit profit. En revanche, on voit qu’il faut s’arrêter à temps et ne pas dépasser la droite d’équation : , car sinon la droite ne coupera plus le polygone des solutions réalisables. La solution optimale est donc le sommet C situé à l’intersection des droites : . Il a pour coordonnées : . La valeur de la fonction économique en ce sommet est : La solution optimale est donc de produire 32 articles de poterie et 48 articles d’émaux sur cuivre pour un bénéfice de 3520 DH. Remarque : dans cet exemple, l’ensemble des solutions réalisables est un polygone convexe et la solution optimale correspond à un sommet de ce polygone. D’autres cas peuvent se produire : - Les contraintes peuvent définir un ensemble de solutions réalisables vide. Dans ce cas le programme linéaire n’a pas de solution. - Les contraintes peuvent définir un domaine de solutions réalisables non borné. Dans ce cas le programme linéaire peut ne pas avoir de solution optimale finie. - La droite d’iso-profit peut être parallèle à l’une des contraintes. Dans ce cas, il existe une infinité de solutions optimales. 3- Résolution avec le solveur d’Excel Le solveur est une macro commande disponible avec les principaux tableurs. Il permet de choisir les variables de décision, d’ajouter les contraintes et la fonction économique, mais il faut, au préalable, préparer les données dans une feuille de calcul. Il est conseillé de bien organiser cette feuille afin de faciliter la saisie, la correction des erreurs et les modifications futures du modèle. Figure 1.2 : Problème de la fabrique artisanale Figure 1.3 : Paramètres du solveur Figure 1.4 : Options du solveur La disposition présentée pour l’exercice 1 respecte les consignes de construction d’un modèle d’aide à la décision sur un tableur : on sépare clairement les variables de décision, les contraintes du modèle et la fonction économique, qui est le résultat du modèle. Par ailleurs, la représentation sur tableur colle de près à la représentation algébrique. Les valeurs des variables et sont dans les cellules B5 et C5. Leur valeur initiale importe peu puisque c’est ensuite le solveur qui va les déterminer. Les coefficients des inéquations (la matrice des contraintes) sont dans la plage B8:C10. Les premiers membres de ces inéquations sont dans la plage D8:D10 et les seconds membres dans la plage F8:F10. Par exemple, pour la première contrainte : le premier membre de l’inéquation est calculé dans la cellule D8 par la formule : ou encore par la formule (plus rapide à écrire lorsqu’il y a beaucoup de variables) . Cette formule (produit des coefficients par les variables) peut être copiée en D9 et D10. Pour la fonction économique, on entre les coefficients 20 et 60 en B13 et C13. La formule donnant l’expression de Z, entrée en D13, est similaire (on peut la copier) à celle des premiers membres des inéquations soit : . On fait alors appel au solveur en sélectionnant (dans Excel 2007) Données Analyse Solveur et on saisit les paramètres suivants : 1. Cellule cible à définir : on entre la référence de la cellule contenant la fonction économique Z, soit D13, puis on choisit le type de l’optimisation (ici : Max). 2. Cellules variables : on entre les références des cellules qui contiennent les variables de décision (dans notre exemple, il s’agit de la plage B5:C5). 3. Contraintes : on peut entrer les contraintes une par une : par exemple pour la première contrainte, on clique sur Ajouter puis on entre la référence de la cellule contenant le premier membre (D8), le sens ≤ et la référence de la cellule contenant le second membre (F8). On peut aussi entrer d’un seul coup les trois contraintes, de manière vectorielle, car elles sont toutes de même type (≤) : D8:D10 ≤ F8:F10. On clique alors sur OK lorsque toutes les contraintes sont ajoutées. 4. Options : on clique sur le bouton Options. On coche Modèle supposé linéaire pour que le solveur utilise la méthode du simplexe (plus efficace). On coche également Supposé non négatif, à moins que l’on n’ait entré les contraintes de non-négativité dans la partie Contraintes. On clique ensuite sur OK. On clique enfin sur le bouton Résoudre. S’il y a une solution (c’est notre cas), une fenêtre apparaît indiquant le solveur à trouvé une solution satisfaisant toutes les contraintes et les conditions d’optimisation. Les cellules B5 et C5 indiquent les valeurs optimales de x et y, soit 32 et 48 et la cellule D13 fournit la valeur optimale de Z soit 3 520 DH. On peut choisir l’option Garder la solution du solveur et également faire afficher un rapport complet des réponses. EXERCICE 2 : corrigé 1- Formulation sous forme de programme linéaire Soient et les nombres de coussinets (A) et de paliers (B) à fabriquer. et sont les variables de décision du problème. Les contraintes du problème sont : On doit fabriquer au moins 4 000 unités de coussinets (A) et au moins 5 000 paliers (B), soit : Il faut 2 kg de matière première pour fabriquer un coussinet (A) et 3 kg pour fabriquer un palier (B), donc kg pour coussinets et kg pour paliers. L’unité de production doit traiter un minimum de 36 000 kg de matière première, soit : Il faut 1 heure de main d’œuvre pour fabriquer un coussinet (A) et une demi-heure pour un palier (B), donc heures pour coussinets et heures pour paliers. Le maximum d’heures de main d’œuvre est fixé à 10 000 heures, soit : Enfin remarquons que les variables x et y qui représentent des quantités produites, ne peuvent pas avoir des valeurs négatives. L’objectif ici est de rendre minimal le coût des transports, mis en place entre l’unité de production et l’usine principale pour l’acheminement uploads/S4/ corrige-td-1.pdf