Correction exercice 1 td n 3 programmation lineaire -Program
Télécharger PDFCorrection du TD n°3 : Programmation Linéaire - Exercice 1
1) Formulation mathématique du problème
Soient x, y et z les nombres de lots achetés respectivement aux fournisseurs X, Y et Z.
Les contraintes portent sur les cycles de fabrication qui nécessitent au moins 120 grammes de lanoline et au moins 90 grammes de glycérine. En se basant sur les coefficients de la formulation duale, les lots achetés contiendront respectivement des quantités de lanoline et de glycérine, menant aux contraintes suivantes :
6x + 6y + 2z ≥ 120 (lanoline)
2x + 4y + 2z ≥ 90 (glycérine)
L’objectif de l’entreprise en cosmétiques est de minimiser le coût d’approvisionnement auprès des fournisseurs. En se référant aux coefficients de la matrice duale, le coût d’achat à minimiser est :
min Z_P = 6x + 2y + 2z
Le programme linéaire permettant de calculer le plan d’approvisionnement optimal est :
[ min Z_P = 6x + 2y + 2z ]
Sous les contraintes :
{ 6x + 6y + 2z ≥ 120
2x + 4y + 2z ≥ 90
x, y, z ≥ 0 }
2) Résolution par passage au dual
Le dual du programme primal de la question précédente est un programme de maximisation :
[ max Z_D = 120u + 90v ]
Sous les contraintes :
{ 6u + 2v ≤ 6
6u + 4v ≤ 2
2u + 2v ≤ 2
u, v ≥ 0 }
Résolvons ce problème de maximisation par la méthode des tableaux simplexe. La forme standard associée est :
[ max Z_D = 120u + 90v + 0e1 + 0e2 + 0e3 ]
Sous les contraintes :
{ 6u + 2v + e1 = 6
6u + 4v + e2 = 2
2u + 2v + e3 = 2
u, v, e1, e2, e3 ≥ 0 }
D’où le premier tableau :
u v e1 e2 e3
e1 6 2 1 0 0 6
e2 6 4 0 1 0 2
e3 2 2 0 0 1 2
Zj 120 90 0 0 0 0
La solution optimale est obtenue par itérations successives de l’algorithme du simplexe en appliquant les différents critères de Dantzig à chaque itération : choix d’une variable entrante, calcul de la variable sortante et test d’optimalité. Ces calculs sont résumés dans les tableaux suivants :
u v e1 e2 e3
e1 0 -2 1 -1 0 4
v 0 1 -3/2 1/4 0 1/2
e3 0 0 1 -1/2 1 1
Zj 0 -30 -15 -22.5 0 45
u v e1 e2 e3
e1 0 0 1 -1/2 1 5
v 0 1 -3/2 1/4 0 1/2
u 1 0 1/2 -1/4 -1/2 1/2
Zj 0 0 30 -30 15 60
u v e1 e2 e3
u 1 0 0 -1 6
v 0 1 0 24
e1 0 0 1 -2 3 36
Zj 0 0 0 -15 -15 2880
D’où la solution optimale du problème dual :
{ u = 6
v = 24 }
On remarque que la variable d’écart e1 (variable d’écart de la première contrainte du dual, correspondant à la variable primale x) est non nulle (e1=36 dans le dernier tableau), et donc la contrainte duale associée n'est pas saturée. On en déduit que la variable primale correspondante est forcément nulle, soit : x = 0 (deuxième propriété fondamentale de la dualité vue en cours).
Les variables duales u et v sont non nulles à l’optimum (u=6, v=24), donc les contraintes primales associées (les deux contraintes initiales) sont saturées à l’optimum, soit le système linéaire :
{ 6x + 6y + 2z = 120
2x + 4y + 2z = 90 }
Or on vient de voir que x est nulle à l’optimum, d’où le système simplifié :
{ 6y + 2z = 120
4y + 2z = 90 }
Ce système linéaire simple à résoudre donne la solution :
{ y = 15
z = 15 }
D’autre part, la fonction objectif du primal a la même valeur optimale que celle du dual, d’où la solution du problème primal :
{ x = 0
y = 15
z = 15
Z_P = 2880 }
Remarque : Les valeurs optimales des variables primales sont, au signe près, les valeurs des coefficients sous les variables d’écart dans la dernière ligne du tableau simplexe final du dual. Ici, sous e1, e2, e3 on a 0, -15, -15, qui correspondent respectivement à x=0, y=15, z=15.
Le plan d’approvisionnement optimal est l’achat de 15 lots auprès du fournisseur Y et 15 lots auprès du fournisseur Z et aucun lot du fournisseur X pour un coût minimal de 2 880 dirhams.
3) Résolution par le solveur d’Excel
Sur la figure 4.1 qui représente le modèle tableur du programme linéaire (non fournie ici), la plage B5:D5 contient les valeurs des variables de décision. La plage B8:D9 contient la matrice des coefficients des équations des contraintes. Les premiers membres des inéquations sont calculés dans la plage E8:E9. Les valeurs des seconds membres sont entrées dans la plage G8:G9. Les coefficients de la fonction économique sont dans la plage B12:D12 et la valeur de cette fonction est calculée en cellule E12. On lance ensuite le solveur et on entre tous les paramètres du problème à résoudre comme cela a été fait dans les exercices précédents. Le solveur affiche alors la solution optimale présentée dans la figure 4.1.
Correction de l'Exercice 2
1) Modélisation mathématique du problème
Il s’agit d’un problème de conditionnement de trois types d’articles référencés A, B, C sous forme de colis de trois types X, Y, Z. Chaque jour, l’entreprise doit satisfaire les besoins de la clientèle tout en minimisant le coût de conditionnement des colis. Désignons par x, y et z les nombres respectifs de colis X, Y et Z qu’il faut traiter quotidiennement afin d’obtenir le coût de conditionnement minimum. Ce dernier s’exprime en fonction du coût de conditionnement de chaque type de colis. D’où l’expression du coût qu’il faut rendre minimal, basée sur les RHS des contraintes du dual :
min Z_P = 32x + 36y + 50z
D’autre part, nous avons des contraintes qui portent sur le nombre d’articles qu’il faut placer dans chaque type de colis sachant qu’il faut conditionner au moins 1 235 articles de type A, 4 004 articles de type B et 2 880 articles de type C pour satisfaire la demande clientèle. Ces contraintes peuvent être traduites facilement en inéquations mathématiques :
{ x + 2y + 2z ≥ 1235 (pour l'article A)
x + 3y + 2z ≥ 4004 (pour l'article B)
x + 5y + 3z ≥ 2880 (pour l'article C)
x, y, z ≥ 0 }
Le problème de l’entreprise de conditionnement se résume donc au programme linéaire suivant :
[ min Z_P = 32x + 36y + 50z ]
Sous les contraintes :
{ x + 2y + 2z ≥ 1235
x + 3y + 2z ≥ 4004
x + 5y + 3z ≥ 2880
x, y, z ≥ 0 }
2) Résolution par passage au dual
Le problème à résoudre est de type minimisation. Sa résolution peut se faire à l’aide de la méthode du simplexe mais nécessitera l’introduction de variables artificielles et donc plus de calculs. Pour pallier cet inconvénient, on résoudra d’abord le problème dual associé et on en déduira la solution du primal. L’expression du problème dual est alors :
[ max Z_D = 1235u + 4004v + 2880w ]
Sous les contraintes :
{ u + v + w ≤ 32
2u + 3v + 5w ≤ 36
2u + 2v + 3w ≤ 50
u, v, w ≥ 0 }
Résolvons ce problème de maximisation par la méthode des tableaux simplexe. La forme standard associée est :
[ max Z_D = 1235u + 4004v + 2880w + 0e1 + 0e2 + 0e3 ]
Sous les contraintes :
{ u + v + w + e1 = 32
2u + 3v + 5w + e2 = 36
2u + 2v + 3w + e3 = 50
u, v, w, e1, e2, e3 ≥ 0 }
Le premier tableau associé à la solution de base réalisable initiale est :
u v w e1 e2 e3
e1 1 2 2 1 0 0 32
e2 1 3 2 0 1 0 36
e3 1 5 3 0 0 1 50
Zj 1235 4004 2880 0 0 0 0
Les tableaux suivants résument les différents calculs avant d’atteindre l’optimum.
u v w e1 e2 e3
e1 1/2 0 1/2 1 -2/3 0 8
v 1/3 1 2/3 0 1/3 0 12
e3 -1/3 0 -1/3 0 -5/3 1 -10
Zj -1235/3 0 -2880/3 0 -4004/3 0 -48048
u v w e1 e2 e3
e1 0 1 0 12
e2 0 0 1 6
v 1 0 0 10
Zj 434.2 0 477.6 0 0 -8008.8 -40040
u v w e1 e2 e3
w 0 1 0 15
e2 0 1 3
v 1 0 0 1 76
Zj 0 0 -597 0 -562 -47204
u v w e1 e2 e3
w 0 0 1 2 -3 1 6
u 1 0 0 -1 4 -2 12
v 0 1 0 -1 1 0 4
Zj 0 0 0 -521 -304 -410 -48116
Ce dernier tableau simplexe contient la solution optimale du problème dual :
{ u = 12
v = 4
w = 6 }
Les variables duales u, v et w sont non nulles à l’optimum, donc les contraintes primales associées sont saturées à l’optimum, soit le système linéaire :
{ x + 2y + 2z = 1235
x + 3y + 2z = 4004
x + 5y + 3z = 2880 }
La résolution de ce système fournit la solution optimale du primal :
{ x = 521
y = 304
z = 410 }
D’autre part, la fonction objectif du primal a la même valeur optimale que celle du dual, d’où la solution du problème primal :
{ x = 521
y = 304
z = 410
Z_P = 48116 }
Remarque : Les valeurs optimales des variables primales sont, au signe près, les valeurs des coefficients sous les variables d’écart dans la dernière ligne du tableau simplexe final du dual. Ici, sous e1, e2, e3 on a -521, -304, -410, qui correspondent respectivement à x=521, y=304, z=410.
Le plan de conditionnement optimal est de faire emballer 521 colis de type X, 304 colis de type Y et 410 colis de type Z pour un coût minimal de 48 116 dirhams.
3) Résolution par le solveur d’Excel
La figure 4.2 ci-dessous représente le modèle tableur du programme linéaire (non fournie ici) avec ses trois caractéristiques : les variables de décision, les contraintes et la fonction économique. La plage B5:D5 contient les valeurs des variables de décision. La plage B8:D10 contient la matrice des coefficients des inéquations des contraintes. Les premiers membres des inéquations sont calculés dans la plage E8:E10. Les valeurs des seconds membres sont entrées dans la plage G8:G10. Les coefficients de la fonction économique sont dans la plage B13:D13 et la valeur de cette fonction est calculée en cellule E13. Après avoir renseigné les différentes zones (Cellule cible à définir, Égale à, Cellules variables, Contraintes et Options) de la boîte de dialogue Paramètres du solveur, on lance la résolution par le bouton Résoudre. Le solveur affiche alors la solution optimale présentée dans la figure 4.2.
Foire aux questions (FAQ) sur la Programmation Linéaire et le Dual
Qu'est-ce que la programmation linéaire ?
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 sous forme d'égalités ou d'inégalités. Elle est largement appliquée dans divers domaines tels que l'économie, l'ingénierie, la logistique et la gestion de la production pour l'allocation optimale des ressources.
Pourquoi utiliser le dual d'un programme linéaire ?
L'utilisation du dual d'un programme linéaire présente plusieurs avantages. Premièrement, il peut simplifier la résolution, notamment lorsque le problème primal est de minimisation avec des contraintes de type "supérieur ou égal", ce qui nécessiterait l'introduction de variables artificielles dans la méthode du simplexe. Le dual, étant souvent un problème de maximisation avec des contraintes de type "inférieur ou égal", est plus direct à résoudre par l'algorithme du simplexe standard. Deuxièmement, la solution du dual fournit des informations économiques précieuses, comme les prix virtuels (ou prix-ombres) des ressources, qui peuvent éclairer les décisions de gestion.
Comment interpréter les résultats du solveur Excel en programmation linéaire ?
Le solveur Excel est un outil puissant pour la programmation linéaire. Il fournit les valeurs optimales des variables de décision, indiquant les quantités à produire, acheter ou allouer pour optimiser la fonction objectif. Il donne également la valeur optimale de cette fonction (coût minimal, profit maximal, etc.). De plus, les rapports de sensibilité générés par le solveur sont cruciaux. Ils aident à comprendre l'impact des changements dans les coefficients de la fonction objectif ou les limites des contraintes, offrant ainsi une aide précieuse à la décision pour évaluer la robustesse de la solution optimale.