Université saad dahlab blida lmd programmation linéaire -Pro
Télécharger PDFExercice 1 : Optimisation de production de verres
Une verrerie produit des verres à café, des verres à thé et des verres à eau. Les prix de vente, les quantités requises de verre ainsi que les temps de façonnage et d'emballage sont différents pour chacun des produits et sont donnés dans le tableau suivant :
| Caractéristique | Verres à café | Verres à thé | Verres à eau |
|---|---|---|---|
| Temps de façonnage (min) | 4 | 2 | 12 |
| Temps d'emballage (min) | 2 | 1 | 4 |
| Quantité de verre (kg) | 0.1 | 0.15 | 0.1 |
| Prix de vente (DA) | 8 | 6 | 15 |
Pour la semaine à venir, l'entreprise dispose de 3000 minutes pour le façonnage, de 1200 minutes pour l'emballage et de 100 kilogrammes de verre.
a. Formulation du programme linéaire
Formuler un programme linéaire aidant l'entreprise à déterminer une production maximisant son chiffre d'affaires.
b. Programme dual
Donner le programme dual du problème.
c. Résolution du problème primal
Résoudre le problème primal.
d. Solution optimale du programme dual
Donner la solution optimale du programme dual.
e. Analyse de sensibilité et recommandation
Si l'entreprise pouvait améliorer le façonnage ou l'emballage de ces produits, ce qui reviendrait à disposer de plus de temps pour l'une ou l'autre de ces deux activités, quelle étape de la production lui conseillerez-vous de modifier en premier ?
Exercice 2 : Aspects théoriques de la programmation linéaire
Soit le problème linéaire P suivant :
max Z = C · X (P)
A · X = b
X ≥ 0
a. Le maximum de la fonction objective
Montrer que la fonction objective du problème (P) définie sur le polyèdre K = { X | X ≥ 0, A · X = b } atteint son maximum en un point extrême de K.
b. Combinaisons linéaires convexes et points extrêmes
Si la fonction objective prend sa valeur maximale à plus d'un point extrême, alors toute combinaison linéaire convexe de ces points donne la même valeur à la fonction objective.
c. Caractérisation d'un point extrême
Un point x de K est un point extrême si et seulement si x est une solution de base réalisable du problème A · X = b.
d. Existence d'un point extrême
En déduire si K ≠ ∅, alors il admet au moins un point extrême.
Exercice 3 : Application de la méthode du grand M
En appliquant la méthode du grand M, montrez que le problème linéaire suivant n'a pas de solution.
Min Z = -2 x1 - 3 x2 + x3
- 4 x1 - 5 x2 - 2 x3 ≥ 5
- x1 + 6 x2 + x3 ≥ 10
x1 ≥ 0 ; x2 ≥ 0; x3 ≥ 0
Solution de l'Exercice 1
a. Formulation du programme linéaire
Définissons les variables de décision par :
- X1 : le nombre de verres à café produits pendant la semaine à venir ;
- X2 : le nombre de verres à thé produits pendant la semaine à venir ;
- X3 : le nombre de verres à eau produits pendant la semaine à venir.
Le plan de production maximisant le chiffre d'affaires est solution du programme linéaire :
Max Z = 8 X1 + 6 X2 + 15 X3
Sous les contraintes :
4 X1 + 2 X2 + 12 X3 ≤ 3000 (Contrainte de temps de façonnage)
2 X1 + X2 + 4 X3 ≤ 1200 (Contrainte de temps d'emballage)
0,1 X1 + 0,15 X2 + 0,1 X3 ≤ 100 (Contrainte de quantité de verre)
X1 ≥ 0, X2 ≥ 0 et X3 ≥ 0 (Contraintes de non-négativité)
b. Le problème dual
Le problème dual du programme précédent est :
Min W = 3000 y1 + 1200 y2 + 100 y3
Sous les contraintes :
4 y1 + 2 y2 + 0,1 y3 ≥ 8
2 y1 + y2 + 0,15 y3 ≥ 6
12 y1 + 4 y2 + 0,1 y3 ≥ 15
y1 ≥ 0, y2 ≥ 0 et y3 ≥ 0
c. Résolution du problème primal par la méthode du simplexe
Le but est d'obtenir une base optimale. La méthode du simplexe est un algorithme itératif qui explore les sommets du polyèdre des solutions admissibles jusqu'à trouver la solution optimale. En dressant les tableaux du simplexe, nous obtenons les itérations suivantes :
Tableau initial du simplexe :
| CB | VB | b | X1 | X2 | X3 | X4 | X5 | X6 | Ratios |
|---|---|---|---|---|---|---|---|---|---|
| 0 | X4 | 3000 | 4 | 2 | 12 | 1 | 0 | 0 | 750 |
| 0 | X5 | 1200 | 2 | 1 | 4 | 0 | 1 | 0 | 600 |
| 0 | X6 | 100 | 0.1 | 0.15 | 0.1 | 0 | 0 | 1 | 1000 |
| Z | 0 | -8 | -6 | -15 | 0 | 0 | 0 |
Si on choisit de faire entrer X1 (car le coût réduit -8 est le plus négatif), il est optimal de faire sortir X5 (ratio minimum de 600).
Premier tableau itératif :
| CB | VB | b | X1 | X2 | X3 | X4 | X5 | X6 | Ratios |
|---|---|---|---|---|---|---|---|---|---|
| 0 | X4 | 600 | 0 | 0 | 4 | 1 | -2 | 0 | ∞ |
| 8 | X1 | 600 | 1 | 1/2 | 2 | 0 | 1/2 | 0 | 1200 |
| 0 | X6 | 40 | 0 | 1/10 | -1/10 | 0 | -1/20 | 1 | 400 |
| Z | 4800 | 0 | -2 | 1 | 0 | 4 | 0 |
Si on fait rentrer X2 dans la base (car le coût réduit -2 est négatif), il est optimal de faire sortir X6 (ratio minimum de 400).
Deuxième tableau itératif :
| CB | VB | b | X1 | X2 | X3 | X4 | X5 | X6 | Ratios |
|---|---|---|---|---|---|---|---|---|---|
| 0 | X4 | 600 | 0 | 0 | 4 | 1 | -2 | 0 | 150 |
| 8 | X1 | 400 | 1 | 0 | 5/2 | 0 | 3/4 | -5 | 160 |
| 6 | X2 | 400 | 0 | 1 | -1 | 0 | -1/2 | 10 | - |
| Z | 5600 | 0 | 0 | -1 | 0 | 3 | 20 |
Si on fait rentrer X3 dans la base (car le coût réduit -1 est négatif), il est optimal de faire sortir X4 (ratio minimum de 150).
Tableau final du simplexe (optimal) :
| CB | VB | b | X1 | X2 | X3 | X4 | X5 | X6 |
|---|---|---|---|---|---|---|---|---|
| 15 | X3 | 150 | 0 | 0 | 1 | 1/4 | -1/2 | 0 |
| 8 | X1 | 25 | 1 | 0 | 0 | -5/8 | 2 | -5 |
| 6 | X2 | 550 | 0 | 1 | 0 | 1/4 | 1/2 | 10 |
| Z | 5750 | 0 | 0 | 0 | 1/4 | 5/2 | 20 |
Ce tableau final est optimal car tous les coûts réduits (dernière ligne) sont positifs ou nuls. La solution est : X1* = 25 verres à café, X2* = 550 verres à thé et X3* = 150 verres à eau pour un chiffre d'affaires maximal de Z* = 5750 DA.
d. Solution optimale du programme dual
La solution optimale duale se lit du tableau optimal (valeurs de la ligne Z sous les variables d'écart) : y1* = 1/4, y2* = 5/2 et y3* = 20. La valeur optimale de la fonction objectif duale est W* = 5750 DA, ce qui confirme l'égalité des objectifs primal et dual à l'optimum.
e. Analyse de sensibilité et décision stratégique
Le coût marginal associé à la première ressource (le temps de façonnage) est y1* = 1/4. Celui associé à la deuxième ressource (le temps d'emballage) est y2* = 5/2. Puisque y2* (5/2 = 2.5) est supérieur à y1* (1/4 = 0.25), cela signifie qu'une augmentation d'une unité de temps d'emballage augmenterait le chiffre d'affaires de 2.5 DA, tandis qu'une augmentation d'une unité de temps de façonnage ne l'augmenterait que de 0.25 DA. Il est donc préférable d'essayer d'augmenter en premier lieu le temps d'emballage car, pour une augmentation égale des ressources, l'impact sur le chiffre d'affaires sera plus important.
Solution de l'Exercice 2
a. Le maximum de la fonction objective
Soit un programme linéaire (PL) sous forme standard (P) avec la fonction objective Z = C · X, et le polyèdre K = {X | X ≥ 0, A · X = b}. Soient x1, …, xp les points extrêmes de K et x0 une solution optimale de (P). Supposons par contradiction que x0 n'est pas un point extrême de K.
Alors x0 peut être exprimé comme une combinaison linéaire convexe des points extrêmes : x0 = Σi=1p λi xi, où Σi=1p λi = 1 et λi ≥ 0 pour tout i.
La valeur de la fonction objective en x0 est Z(x0) = C · x0 = C · (Σi=1p λi xi) = Σi=1p λi (C · xi) = Σi=1p λi Z(xi).
Soit Z(xr) = max { Z(xi) | i = 1, …, p } la valeur maximale que prend la fonction objective aux points extrêmes.
Alors Z(x0) = Σi=1p λi Z(xi) ≤ Σi=1p λi Z(xr) = Z(xr) Σi=1p λi = Z(xr).
D'où Z(x0) ≤ Z(xr). Si Z(x0) < Z(xr), cela contredit l'optimalité de x0. Par conséquent, x0 est un sommet de K.
b. Combinaisons linéaires convexes des points extrêmes
Soient x1, …, xp les points extrêmes de K et Z(x1) = … = Z(xp) = α, la valeur optimale (minimale ou maximale). Soit x = Σi=1p λi xi une combinaison linéaire convexe de ces points, avec Σi=1p λi = 1 et λi ≥ 0.
Alors Z(x) = Z(Σi=1p λi xi) = Σi=1p λi Z(xi) = Σi=1p λi α = α Σi=1p λi = α · 1 = α.
Donc, toute combinaison linéaire convexe de ces points donne la même valeur à la fonction objective.
c. Caractérisation d'un point extrême
⇐ Soit x = (x1, …, xm, 0, …, 0) une solution de base réalisable. Montrons que x est un point extrême. Raisonnons par l'absurde. Supposons qu'il existe y et z deux sommets de K tels que : x = α y + (1 - α) z ; avec 0 ≤ α ≤ 1.
Du fait que x ≥ 0 et 0 ≤ α ≤ 1, les "n - m" dernières composantes de y et z sont nulles (puisque celles de x le sont). Donc :
y = (y1, y2, …, ym, 0, …, 0)
z = (z1, z2, …, zm, 0, …, 0)
Du fait que y et z sont des solutions réalisables (elles satisfont A · X = b) :
y1 a1 + y2 a2 + … + ym am = b
z1 a1 + z2 a2 + … + zm am = b
En soustrayant les deux équations, on obtient :
(y1 - z1) a1 + (y2 - z2) a2 + … + (ym - zm) am = 0
Puisque les colonnes ai (i = 1, …, m) forment une base, elles sont linéairement indépendantes (L.I.). Il en découle que les coefficients de la combinaison linéaire doivent être nuls :
y1 - z1 = 0 ⇒ y1 = z1
y2 - z2 = 0 ⇒ y2 = z2
…
ym - zm = 0 ⇒ ym = zm
Et donc x = y = z. Cela contredit l'hypothèse que y et z sont distincts de x (à moins que α=0 ou α=1, ce qui ferait x=z ou x=y, donc x est bien un point extrême).
⇒ Soit x est un point extrême, montrons qu'il est une solution de base réalisable de K.
x = (x1, …, xm, 0, …, 0) est une solution de K, où m est le nombre de composantes non nulles. On a Σi=1m xi ai = b.
Si a1, a2, …, am sont linéairement indépendants, alors x est une solution de base (et donc réalisable, car x ≥ 0).
Si a1, a2, …, am sont linéairement dépendants, alors il existe des scalaires yi non tous nuls tels que :
(1) Σi=1m yi ai = 0
Nous savons aussi que :
(2) Σi=1m xi ai = b
Pour ε > 0 suffisamment petit, nous pouvons construire deux autres solutions :
Σi=1m (xi + ε yi) ai = Σi=1m xi ai + ε Σi=1m yi ai = b + ε · 0 = b
Et
Σi=1m (xi - ε yi) ai = Σi=1m xi ai - ε Σi=1m yi ai = b - ε · 0 = b
Nous avons trouvé deux vecteurs :
y' = (x1 + ε y1, …, xm + ε ym, 0, …, 0)
z' = (x1 - ε y1, …, xm - ε ym, 0, …, 0)
Comme xi > 0 (pour les composantes non nulles de x), on peut choisir ε suffisamment petit tel que y' et z' soient des solutions réalisables (toutes leurs composantes restent non négatives).
De plus, on observe que x = 1/2 y' + 1/2 z'.
Ceci contredit le fait que x est un point extrême, car un point extrême ne peut pas être exprimé comme une combinaison linéaire convexe stricte de deux autres points réalisables distincts. Par conséquent, les ai doivent être linéairement indépendants, et x est une solution de base réalisable.
d. Existence d'un point extrême
Si le polyèdre de réalisabilité K est non vide (≠ ∅), alors il contient au moins une solution réalisable. À partir de cette solution réalisable, on peut toujours construire une solution de base réalisable en utilisant des techniques comme la phase I du simplexe ou en éliminant les colonnes linéairement dépendantes. Puisqu'une solution de base réalisable correspond à un point extrême, il s'ensuit que K admet au moins un point extrême.
Solution de l'Exercice 3
Le problème linéaire est donné par :
Min Z = -2 x1 - 3 x2 + x3
Sous les contraintes :
-4 x1 - 5 x2 - 2 x3 ≥ 5
- x1 + 6 x2 + x3 ≥ 10
x1 ≥ 0 ; x2 ≥ 0; x3 ≥ 0
Pour appliquer la méthode du grand M, nous devons d'abord convertir les inégalités en égalités en soustrayant des variables d'écart (surplus) et en ajoutant des variables artificielles là où c'est nécessaire pour avoir une base initiale. Le problème est déjà en minimisation.
Avec les variables d'écart (surplus) x4 et x5 :
-4 x1 - 5 x2 - 2 x3 - x4 = 5
- x1 + 6 x2 + x3 - x5 = 10
xi ≥ 0 ; i = 1, …, 5.
Pour obtenir un côté droit (RHS) positif pour l'initialisation du simplexe standard, multiplions les équations par -1 (cela ne change pas la région réalisable, mais l'interprétation des variables d'écart change). Ou bien nous ajoutons des variables artificielles directement.
Le traitement donné dans l'exercice semble faire une manipulation algébrique avant d'ajouter la variable artificielle. On a les contraintes équivalentes (en multipliant par -1 les équations pour avoir RHS négatifs, ce qui est inhabituel pour le simplexe initial) :
4 x1 + 5 x2 + 2 x3 + x4 = - 5 (où x4 est maintenant une variable d'écart avec un coefficient +1)
x1 - 6 x2 - x3 + x5 = -10 (où x5 est une variable d'écart avec un coefficient +1)
xi ≥ 0 ; i = 1, …, 5.
L'approche présentée ici semble introduire une variable artificielle x6 d'une manière non standard, en la combinant avec x1 et x2, et définissant M comme une constante très grande. Une interprétation possible des étapes suivantes est une tentative de trouver une base réalisable en utilisant une phase artificielle implicite.
Dans la solution fournie, une équation artificielle est introduite : x1 + x2 + x6 = M. Cela est inhabituel pour la méthode du Grand M telle qu'elle est traditionnellement enseignée, où les variables artificielles sont ajoutées directement aux contraintes originales avec un grand coefficient M dans la fonction objectif.
Le problème augmenté devient :
Min Z = -2 x1 - 3 x2 + x3
Remplaçant x2 = M - x1 - x6 :
Min Z = -2 x1 - 3 (M - x1 - x6) + x3
Min Z = x1 + x3 + 3 x6 - 3M
Avec les contraintes transformées :
4 x1 + 5 (M - x1 - x6) + 2 x3 + x4 = -5 ⇒ -x1 + 2 x3 + x4 - 5 x6 = -5M - 5
x1 - 6 (M - x1 - x6) - x3 + x5 = -10 ⇒ 7 x1 - x3 + x5 + 6 x6 = 6M - 10
x1 + x2 + x6 = M
xi ≥ 0 ; i = 1, …, 6.
Tableau du simplexe initial pour le problème augmenté :
| CB | VB | b | x1 | x2 | x3 | x4 | x5 | x6 |
|---|---|---|---|---|---|---|---|---|
| 0 | x4 | -5M-5 | -1 | 0 | 2 | 1 | 0 | -5 |
| 0 | x5 | 6M-10 | 7 | 0 | -1 | 0 | 1 | 6 |
| -3 | x2 | M | 1 | 1 | 0 | 0 | 0 | 1 |
| Zj - cj | -3M | -1 | 0 | -1 | 0 | 0 | -3 |
Nous observons que X4 = -5M - 5 < 0 (puisque M est un très grand nombre positif). Une variable de base est négative, ce qui indique que la solution de base actuelle est infaisable. La variable x4 doit sortir de la base. Pour identifier la variable entrante, on regarde les Zj - cj et les coefficients de la ligne de x4 (où le coefficient est négatif).
Calculons min { (Zj - cj) / aij | aij < 0 } pour la ligne de x4. Les colonnes avec a4j < 0 sont x1 (-1) et x6 (-5).
Ratios : { -1 / -1 = 1 (pour x1), -3 / -5 = 0.6 (pour x6) }
Le ratio minimum est 0.6, donc x6 rentre dans la base.
Tableau itératif après pivotement (x6 entre, x4 sort) :
| CB | VB | b | x1 | x2 | x3 | x4 | x5 | x6 |
|---|---|---|---|---|---|---|---|---|
| 3 | x6 | M+1 | 1/5 | 0 | -2/5 | -1/5 | 0 | 1 |
| 0 | x5 | -16 | 29/5 | 0 | 7/5 | 6/5 | 1 | 0 |
| -3 | x2 | -1 | 4/5 | 1 | 2/5 | 1/5 | 0 | 0 |
| Zj - cj | 3 | -2/5 | 0 | -11/5 | -3/5 | 0 | 0 |
Après cette itération, nous avons X5 = -16 < 0. La variable de base x5 est négative, indiquant que la solution est infaisable. Pour la ligne de x5 (la deuxième ligne), tous les coefficients sous les variables non de base (a5j pour j = 1, 3, 4) sont positifs ou nuls (29/5, 7/5, 6/5). Dans une telle situation où une variable de base est négative et tous les coefficients de sa ligne dans les colonnes des variables non de base sont non négatifs, il est impossible d'améliorer la faisabilité. Cela signifie que le problème n'admet pas de solution réalisable.
Par conséquent, le problème augmenté n'admet pas de solution optimale finie. Cela implique que le problème initial n'admet pas de solution réalisable.
Foire aux questions (FAQ)
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, sous un ensemble de contraintes linéaires exprimées sous forme d'égalités ou d'inégalités. Elle est largement employée dans la gestion des opérations, la planification de la production, la logistique et l'allocation des ressources pour trouver la meilleure utilisation des ressources limitées.
Quelle est la différence entre un problème primal et son dual ?
Chaque problème de programmation linéaire (le problème primal) a un problème associé, appelé le problème dual. Si le primal cherche à maximiser une fonction, le dual cherche à minimiser, et vice versa. Les variables du dual correspondent aux contraintes du primal, et les contraintes du dual correspondent aux variables du primal. La résolution de l'un peut fournir des informations précieuses sur l'autre, notamment les prix duaux ou coûts marginaux associés aux ressources.
Pourquoi utilise-t-on la méthode du grand M ?
La méthode du grand M est une technique utilisée pour résoudre des problèmes de programmation linéaire qui ne peuvent pas être directement résolus par la méthode du simplexe standard en raison de l'absence d'une base réalisable initiale. Elle introduit des variables artificielles dans les contraintes d'égalité et de type "supérieur ou égal", et une pénalité (M, un très grand nombre positif) dans la fonction objectif. Cette pénalité vise à forcer ces variables artificielles à être nulles dans la solution optimale, garantissant ainsi une solution réalisable pour le problème original si elle existe.