Correction td n1 programmation lineaire -Programmation linai
Télécharger PDFCorrigé du TD numéro 1 : Programmation Linéaire
1. Modélisation sous forme de programme linéaire
Désignons par x et y 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. Les variables x et y 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 x poteries en nécessitera x heures.
- La fabrication d’un émail nécessite 4 heures de temps de fabrication et la production de y émaux en nécessitera 4y heures.
- La charge de travail pour les émaux ne doit pas dépasser celle de la poterie de plus de 160 heures, soit : 4y - x ≤ 160.
- La production d’articles de poterie ne doit pas excéder de plus de 30 unités la production d’émaux, soit : x - y ≤ 30.
- Le nombre d’articles fabriqués ne doit pas excéder 80 unités par jour, soit : x + y ≤ 80.
- Enfin, remarquons que les variables x et y, qui représentent des quantités produites, ne peuvent pas prendre de valeurs négatives, d'où x ≥ 0 et y ≥ 0.
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 : Z = 20x + 60y. 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 :
Maximiser Z = 20x + 60y
Sous les contraintes :
- -x + 4y ≤ 160
- x - y ≤ 30
- x + y ≤ 80
- x ≥ 0
- y ≥ 0
2. Résolution graphique
En dimension deux (deux variables de décision), il est facile de donner une représentation géométrique du problème dans un plan cartésien. Ici, chaque contrainte correspond à une inéquation linéaire, donc à un demi-plan. Par exemple, la contrainte x + y ≤ 80 définit un demi-plan situé en bas d’une « frontière » : la droite d’équation x + y = 80.
Les cinq contraintes du problème (les trois contraintes spécifiques plus les deux contraintes de non-négativité) déterminent cinq demi-plans dont l’intersection est non vide. Cette intersection est appelée le domaine des solutions réalisables. Tous les points de ce domaine satisfont l’ensemble des contraintes. Cet ensemble, qui est ici borné, 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 la méthode des droites parallèles (lignes d'iso-profit).
Le recensement des sommets consiste à calculer les coordonnées de tous les points d'intersection du polygone, à 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 20x + 60y = K (où K est une constante) correspondent à des bénéfices constants. On peut qualifier ces droites de droites d’iso-profit. Tous les points d'une droite d'iso-profit donnent le même bénéfice.
En se déplaçant « vers le haut et vers la droite » dans la famille de droites (parallèles) d’iso-profit, on augmente le profit. La solution optimale correspond au dernier point du domaine des solutions réalisables touché par une de ces droites d'iso-profit, juste avant qu'elle ne quitte complètement le domaine.
Dans cet exemple, la solution optimale est le sommet C situé à l’intersection des droites x + y = 80 et -x + 4y = 160. Ce sommet a pour coordonnées (32, 48). La valeur de la fonction économique en ce sommet est Z = 20(32) + 60(48) = 640 + 2880 = 3520 DH.
La solution optimale est donc de produire 32 articles de poterie et 48 articles d’émaux sur cuivre pour un bénéfice maximal 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 un solveur de tableur
Un solveur est une fonctionnalité disponible avec les principaux tableurs, permettant de résoudre des problèmes d'optimisation. Il permet de choisir les variables de décision, d’ajouter les contraintes et la fonction économique. Il est nécessaire, au préalable, de 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.
La disposition recommandée pour un problème de ce type sur un tableur implique de séparer clairement les variables de décision, les contraintes du modèle et la fonction économique. Cette représentation sur tableur correspond étroitement à la représentation algébrique.
Les variables de décision sont placées dans des cellules dédiées. 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 également organisés dans une plage de cellules. Les premiers membres de ces inéquations sont calculés par des formules basées sur les variables de décision et leurs coefficients, et les seconds membres sont entrés comme valeurs fixes. Par exemple, le premier membre d'une inéquation est calculé par une formule qui multiplie les coefficients par les valeurs des variables.
Pour la fonction économique, ses coefficients sont saisis dans des cellules, et l'expression de la fonction objectif Z est calculée dans une cellule spécifique, de manière similaire aux premiers membres des inéquations.
Pour lancer le solveur, il faut généralement spécifier les paramètres suivants :
- Définir la fonction objectif (cellule cible) et le sens de l’optimisation (maximisation ou minimisation).
- Spécifier les cellules contenant les variables de décision.
- Ajouter les contraintes en définissant la relation entre le membre de gauche (calculé) et le membre de droite (valeur fixe), ainsi que le type d'inégalité (inférieur ou égal, supérieur ou égal, égal). Il est souvent possible d'ajouter plusieurs contraintes de même type en une seule fois.
- Accéder aux options du solveur pour cocher des paramètres importants, comme "Modèle supposé linéaire" pour utiliser la méthode du simplexe (plus efficace pour ce type de problème) et "Supposé non négatif" pour les variables, si ces contraintes ne sont pas déjà entrées explicitement.
Après avoir lancé la résolution, si une solution existe, le solveur affichera les valeurs optimales des variables de décision (x et y) et la valeur optimale de la fonction objectif Z. Dans cet exemple, les valeurs optimales de x et y sont 32 et 48, et la valeur optimale de Z est 3520 DH.
Exercice 2 : Optimisation des Coûts de Fabrication
1. Formulation sous forme de programme linéaire
Soient x et y les nombres de coussinets (A) et de paliers (B) à fabriquer. x et y 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), soit x ≥ 4000.
- On doit fabriquer au moins 5 000 paliers (B), soit y ≥ 5000.
- Il faut 2 kg de matière première pour fabriquer un coussinet (A) et 3 kg pour fabriquer un palier (B). L’unité de production doit traiter un minimum de 36 000 kg de matière première, soit : 2x + 3y ≥ 36000.
- Il faut 1 heure de main d’œuvre pour fabriquer un coussinet (A) et une demi-heure pour un palier (B). Le maximum d’heures de main d’œuvre est fixé à 10 000 heures, soit : x + 0.5y ≤ 10000.
- Enfin, les variables x et y qui représentent des quantités produites, ne peuvent pas avoir des valeurs négatives. (Ces contraintes sont déjà couvertes par x ≥ 4000 et y ≥ 5000).
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 des matières premières et le retour des produits finis. Le coût est défini comme suit :
- La quantité de matières premières acheminée est (2x + 3y) kg, avec un coût de 2 DH par kg, soit un coût de : 2(2x + 3y).
- Le poids des produits finis retournés est (x + y) kg, avec un coût de 3 DH par kg, soit un coût de : 3(x + y).
Le coût total à minimiser est donc : Z = 2(2x + 3y) + 3(x + y) = 4x + 6y + 3x + 3y = 7x + 9y. C’est la fonction objectif du modèle.
Le programme linéaire permettant de trouver le programme mensuel de fabrication des coussinets (A) et des paliers (B) est :
Minimiser Z = 7x + 9y
Sous les contraintes :
- x ≥ 4000
- y ≥ 5000
- 2x + 3y ≥ 36000
- x + 0.5y ≤ 10000
2. Résolution graphique
Géométriquement, les quatre contraintes du problème déterminent quatre demi-plans dont l’intersection est non vide. C'est l’ensemble des solutions réalisables : tous les points de ce domaine satisfont l’ensemble des contraintes. Cet ensemble, qui est ici fermé et borné, est un polygone convexe.
Le domaine des solutions réalisables est un polygone dont les sommets sont des points d'intersection des droites délimitant les contraintes. Les sommets pertinents sont :
- A, sommet d’intersection des droites des contraintes x = 4000 et 2x + 3y = 36000. Ses coordonnées sont (4000, 28000/3 ≈ 9333.33). La valeur de la fonction économique Z en A est Z = 7(4000) + 9(28000/3) = 28000 + 84000 = 112000.
- B, sommet d’intersection des droites des contraintes x = 4000 et x + 0.5y = 10000. Ses coordonnées sont (4000, 12000). La valeur de la fonction économique Z en B est Z = 7(4000) + 9(12000) = 28000 + 108000 = 136000.
- C, sommet d’intersection des droites des contraintes 2x + 3y = 36000 et x + 0.5y = 10000. Ses coordonnées sont (6000, 8000). La valeur de la fonction économique Z en C est Z = 7(6000) + 9(8000) = 42000 + 72000 = 114000.
Puisque l'objectif est de minimiser Z, nous comparons les valeurs de Z aux sommets. La solution optimale est donc le sommet A, situé à l’intersection des droites x = 4000 et 2x + 3y = 36000. Il a pour coordonnées (4000, 28000/3). La valeur minimale de la fonction économique en ce sommet est 112000 DH.
3. Résolution avec un solveur de tableur
Le modèle est construit sur tableur de manière similaire à l’exercice précédent. Il est nécessaire de structurer la feuille de calcul avec des zones distinctes pour les variables de décision, la matrice des coefficients des contraintes, les membres de gauche calculés pour les inéquations, les valeurs des seconds membres, les coefficients de la fonction économique et le calcul de la valeur de la fonction objectif.
On fait ensuite appel au solveur en spécifiant tous les paramètres comme dans l’exercice précédent (fonction objectif à minimiser, variables de décision, et toutes les contraintes) pour obtenir la solution optimale. Les résultats indiquent les quantités optimales à produire pour les coussinets et les paliers qui minimisent les coûts totaux.
Foire Aux Questions (FAQ) sur la Programmation Linéaire
Qu'est-ce que la programmation linéaire et à quoi sert-elle ?
La programmation linéaire est une technique mathématique utilisée pour optimiser (maximiser ou minimiser) une fonction objectif linéaire, sujette à un ensemble de contraintes linéaires. Elle est largement employée dans divers domaines comme la production, la logistique, la finance et la gestion des ressources pour prendre des décisions optimales.
Comment interpréter un domaine des solutions réalisables ?
Le domaine des solutions réalisables est l'ensemble de tous les points (combinaisons de valeurs pour les variables de décision) qui satisfont simultanément toutes les contraintes du problème de programmation linéaire. Graphiquement, il est souvent représenté par un polygone ou une région bornée (ou non) dans un plan. La solution optimale, si elle existe, se trouve toujours sur l'un des sommets de ce domaine.
Quels sont les avantages d'utiliser un solveur de tableur pour la résolution de problèmes de programmation linéaire ?
Les solveurs intégrés aux tableurs facilitent grandement la résolution de problèmes de programmation linéaire, surtout pour des modèles complexes. Ils permettent une modélisation rapide et flexible, une analyse de sensibilité aisée, et fournissent des rapports détaillés sur les solutions optimales et les contraintes. Cela réduit les erreurs de calcul manuel et permet de tester rapidement différents scénarios.