Correction exercice td m09 programmation lineaire -Programma
Télécharger PDFCorrection d'exercices de Programmation Linéaire
Cette section présente la correction de plusieurs exercices de travaux dirigés sur la programmation linéaire.
Exercice 1 : Formulation d'un programme linéaire pour une campagne publicitaire
Une entreprise souhaite lancer une campagne publicitaire à la télévision, à la radio et dans les journaux pour un produit récemment introduit sur le marché. L'objectif est d'attirer le maximum de clients potentiels. Les informations suivantes sont disponibles pour la campagne :
- Le budget total ne doit pas excéder 800 DT.
- Au minimum 2000 femmes doivent voir, entendre ou lire la publicité.
- La campagne publicitaire télévisée ne doit pas dépasser 500 DT.
- Au moins 3 spots publicitaires doivent être assurés par la télévision locale et au moins 2 spots par la télévision par satellite.
- Le nombre de publicités à la radio et dans les journaux doit être compris entre 5 et 10 pour chaque média.
Formuler ce problème sous forme de programme linéaire.
Solution 1
Les variables de décision du problème sont :
- x1 : le nombre de spots publicitaires à la télévision locale.
- x2 : le nombre de spots publicitaires à la télévision par satellite.
- x3 : le nombre de spots publicitaires à la radio.
- x4 : le nombre d'affiches publicitaires dans les journaux.
Les contraintes de non-négativité (xi ≥ 0) sont vérifiées.
Les contraintes spécifiques du problème sont :
- Coût total de la campagne publicitaire : 40x1 + 75x2 + 30x3 + 15x4 ≤ 800
- Nombre de femmes touchées : 300x1 + 400x2 + 200x3 + 100x4 ≥ 2000
- Contrainte budgétaire pour la télévision : 40x1 + 75x2 ≤ 500
- Nombre minimal de spots télévisés : x1 ≥ 3 et x2 ≥ 2
- Nombre de publicités radio/journaux : 5 ≤ x3 ≤ 10 et 5 ≤ x4 ≤ 10
La fonction objectif à maximiser représente le nombre de clients potentiels par publicité (ces coefficients sont basés sur une étude de marché non détaillée ici, mais dont les valeurs seraient typiquement issues d'un tableau d'efficacité) :
Z = 400x1 + 900x2 + 500x3 + 200x4
Le programme linéaire résultant est :
Maximiser Z = 400x1 + 900x2 + 500x3 + 200x4
Sous contraintes :
- 40x1 + 75x2 + 30x3 + 15x4 ≤ 800
- 300x1 + 400x2 + 200x3 + 100x4 ≥ 2000
- 40x1 + 75x2 ≤ 500
- x1 ≥ 3
- x2 ≥ 2
- x3 ≥ 5
- x3 ≤ 10
- x4 ≥ 5
- x4 ≤ 10
- xi ≥ 0, pour i = 1, ..., 4
Exercice 2 : Forme standard et solution graphique d'un programme linéaire
Soit le problème de minimisation suivant (PL) :
Minimiser Z = x1 + 2x2 + x3
Sous contraintes :
- x1 + x2 − x3 ≥ 2
- x1 − x2 + x3 = 1
- x1 + x2 + x3 ≥ 2
- x1, x2 ≥ 0
- x3 est une variable quelconque (non restreinte en signe)
- Donner la forme standard du problème.
- Représenter graphiquement l'ensemble-solution.
- Déterminer les coordonnées des points-sommets de l'ensemble solution.
Solution 2
-
La forme standard du problème, qui exige des contraintes d'égalité et des variables non-négatives, est :
Minimiser Z = x1 + 2x2 + x3+ - x3-
Sous contraintes :
- x1 + x2 − (x3+ - x3-) − e1 = 2
- x1 − x2 + (x3+ - x3-) = 1
- x1 + x2 + (x3+ - x3-) − e2 = 2
- x1, x2, x3+, x3-, e1, e2 ≥ 0
Note : Une variable quelconque x3 est remplacée par la différence de deux variables non-négatives : x3 = x3+ - x3-. Les variables d'excédent e1 et e2 sont ajoutées pour convertir les inégalités "≥" en égalités.
-
Pour la représentation graphique, nous pouvons utiliser la deuxième contrainte x1 − x2 + x3 = 1 pour exprimer x3 en fonction de x1 et x2, ce qui donne x3 = 1 − x1 + x2. En substituant cette expression dans le problème (PL), on obtient un problème réduit en deux dimensions :
Minimiser Z = x1 + 2x2 + (1 − x1 + x2) = 3x2 + 1
Sous contraintes :
- x1 + x2 − (1 − x1 + x2) ≥ 2 ⇒ 2x1 − 1 ≥ 2 ⇒ 2x1 ≥ 3 ⇒ x1 ≥ 3/2
- x1 + x2 + (1 − x1 + x2) ≥ 2 ⇒ 2x2 + 1 ≥ 2 ⇒ 2x2 ≥ 1 ⇒ x2 ≥ 1/2
- x1, x2 ≥ 0
L'ensemble-solution réalisable est la région définie par x1 ≥ 3/2 et x2 ≥ 1/2. Graphiquement, il s'agit d'une région non bornée dans le premier quadrant, commençant à l'intersection de ces deux droites.
-
Il y a un seul sommet dans l'ensemble réalisable qui est l'intersection des deux droites x1 = 3/2 et x2 = 1/2. Ce point-sommet est S = (3/2, 1/2).
Pour trouver la valeur de x3 à ce sommet : x3 = 1 − x1 + x2 = 1 − 3/2 + 1/2 = 1 − 1 = 0.
La solution est donc x = (3/2, 1/2, 0) et la valeur de la fonction objectif est Z = 3(1/2) + 1 = 5/2.
Exercice 3 : Résolution par la méthode du Simplexe
Résoudre à l'aide de la méthode du Simplexe le programme linéaire suivant :
Maximiser Z = 5x1 + 11x2
Sous contraintes :
- x1 + x2 ≤ 20
- 3x1 + 15x2 ≤ 225
- 5x1 + 10x2 ≤ 160
- x1, x2 ≥ 0
Solution 3
Après l'ajout des variables d'écart (e1, e2, e3) pour convertir les inégalités en égalités, on obtient :
Maximiser Z = 5x1 + 11x2
Sous contraintes :
- x1 + x2 + e1 = 20
- 3x1 + 15x2 + e2 = 225
- 5x1 + 10x2 + e3 = 160
- xi, ej ≥ 0, pour i = 1, 2 et j = 1, 2, 3
On construit le premier tableau du Simplexe :
| Variables de base | x1 | x2 | e1 | e2 | e3 | Z | b (Côté droit) | R (Ratio) |
|---|---|---|---|---|---|---|---|---|
| e1 | 1 | 1 | 1 | 0 | 0 | 0 | 20 | 20/1 = 20 |
| e2 | 3 | 15 | 0 | 1 | 0 | 0 | 225 | 225/15 = 15 ← (Pivot) |
| e3 | 5 | 10 | 0 | 0 | 1 | 0 | 160 | 160/10 = 16 |
| -Z | -5 | -11 ↑ | 0 | 0 | 0 | 1 | 0 |
x2 entre en base et e2 sort de la base. Voici le deuxième tableau du Simplexe :
| Variables de base | x1 | x2 | e1 | e2 | e3 | Z | b (Côté droit) | R (Ratio) |
|---|---|---|---|---|---|---|---|---|
| e1 | 4/5 | 0 | 1 | -1/15 | 0 | 0 | 5 | 5 / (4/5) = 25/4 = 6.25 |
| x2 | 1/5 | 1 | 0 | 1/15 | 0 | 0 | 15 | 15 / (1/5) = 75 |
| e3 | 3 ↑ | 0 | 0 | -2/3 | 1 | 0 | 10 | 10 / 3 = 10/3 ← (Pivot) |
| -Z | -14/5 | 0 | 0 | 11/15 | 0 | 1 | 165 |
x1 entre en base et e3 sort de la base. Voici le troisième tableau du Simplexe :
| Variables de base | x1 | x2 | e1 | e2 | e3 | Z | b (Côté droit) | R (Ratio) |
|---|---|---|---|---|---|---|---|---|
| e1 | 0 | 0 | 1 | 1/9 | -4/15 | 0 | 7/3 | |
| x2 | 0 | 1 | 0 | 1/9 | -1/15 | 0 | 47/3 | |
| x1 | 1 | 0 | 0 | -2/9 | 1/3 | 0 | 10/3 | |
| -Z | 0 | 0 | 0 | -71/45 | -14/15 | 1 | 523/3 |
Les coefficients de la ligne d'objectif (dernière ligne) pour les variables hors base sont tous négatifs ou nuls. La solution obtenue est optimale avec x* = (10/3, 47/3) et la valeur optimale de la fonction objectif est Z* = 523/3.
Exercice 4 : Analyse de sensibilité et Dualité
On considère le programme linéaire Pα suivant, où α est un réel :
Maximiser Z = 2x1 + αx2 + 3x3
Sous contraintes :
- x1 + 3x2 + 2x3 ≤ 30
- x1 + x2 + x3 ≤ 24
- 3x1 + 5x2 + 3x3 ≤ 60
- x1, x2, x3 ≥ 0
On considère le problème P4 (où α = 4). On nous informe que x1 > 0, x2 = 0 et x3 > 0 dans la base optimale de P4.
- Comment utiliser cette information pour résoudre le problème P4 donné en un nombre minimum d'itérations. Étudier, sans développer aucune itération, la solution optimale de P4 et donner cette solution quand c'est possible.
- Donner le dual D4 de P4. Déduire de la question précédente et sans aucun calcul supplémentaire, la valeur des variables duales et des variables d'écart duales.
- En tenant compte des calculs effectués dans la partie précédente, résoudre par le Simplexe le problème P5 (où α = 5).
Solution 4
-
Puisque x2 = 0 dans la base optimale, nous pouvons réduire le problème P4 à deux variables (x1 et x3) :
Maximiser Z = 2x1 + 3x3
Sous contraintes :
- x1 + 2x3 ≤ 30 (1)
- x1 + x3 ≤ 24 (2)
- 3x1 + 3x3 ≤ 60 (3)
- x1, x3 > 0
De la contrainte (3), on peut déduire que 3(x1 + x3) ≤ 60, ce qui implique x1 + x3 ≤ 20. Cette contrainte (x1 + x3 ≤ 20) est plus restrictive que la contrainte (2) (x1 + x3 ≤ 24). Par conséquent, la contrainte (2) devient redondante et peut être ignorée. Le problème réduit P4 devient :
Maximiser Z = 2x1 + 3x3
Sous contraintes :
- x1 + 2x3 ≤ 30 (1)
- x1 + x3 ≤ 20 (contrainte (3) simplifiée)
- x1, x3 > 0
Pour trouver la solution optimale, nous cherchons le point d'intersection des frontières des contraintes actives. En additionnant les deux contraintes (x1 + 2x3) + (x1 + x3) = 2x1 + 3x3, nous obtenons 2x1 + 3x3 ≤ 50. La fonction objectif est Z = 2x1 + 3x3. Ainsi, la valeur maximale de Z est bornée par 50.
Si nous résolvons le système d'équations :
- x1 + 2x3 = 30
- x1 + x3 = 20
En soustrayant la deuxième équation de la première, nous obtenons x3 = 10. En substituant x3 = 10 dans la deuxième équation, nous obtenons x1 + 10 = 20, donc x1 = 10.
La solution optimale est x* = (10, 0, 10) (avec x2 = 0 tel qu'indiqué). Pour cette solution, Z = 2(10) + 3(10) = 20 + 30 = 50. Puisque cette solution atteint la borne supérieure de la fonction objectif, elle est optimale. Ainsi, xopt = (10, 10) pour les variables (x1, x3).
-
Le dual D4 du problème P4 (réduit pour x2=0) s'écrit comme suit :
Minimiser ZD = 30y1 + 20y2
Sous contraintes :
- y1 + y2 ≥ 2 (pour x1)
- 2y1 + y2 ≥ 3 (pour x3)
- y1, y2 ≥ 0
En utilisant les conditions d'optimalité de la dualité (C.O.P.D.) :
Puisque x1* > 0 (10), la première contrainte duale est active : y1 + y2 = 2.
Puisque x3* > 0 (10), la deuxième contrainte duale est active : 2y1 + y2 = 3.
En résolvant ce système linéaire :
- y1 + y2 = 2
- 2y1 + y2 = 3
En soustrayant la première équation de la seconde, on obtient y1 = 1. En substituant y1 = 1 dans la première équation, on obtient 1 + y2 = 2, donc y2 = 1.
La solution optimale duale est y* = (1, 1). Les variables d'écart duales sont nulles, car les contraintes duales sont actives.
-
Nous avons le problème P5 (où α = 5) :
Maximiser Z = 2x1 + 5x2 + 3x3
Sous contraintes :
- x1 + 3x2 + 2x3 ≤ 30
- x1 + x2 + x3 ≤ 24
- 3x1 + 5x2 + 3x3 ≤ 60
- x1, x2, x3 ≥ 0
En ajoutant les variables d'écart (e1, e2, e3), on obtient :
Maximiser Z = 2x1 + 5x2 + 3x3
Sous contraintes :
- x1 + 3x2 + 2x3 + e1 = 30
- x1 + x2 + x3 + e2 = 24
- 3x1 + 5x2 + 3x3 + e3 = 60
- xi, ei ≥ 0, pour i = 1, 2, 3
D'après la question précédente, pour x2 = 0, nous avions calculé la solution optimale de (P4) comme x1 = 10 et x3 = 10. Cette information peut servir de point de départ pour la phase II du Simplexe. En posant x1 = 10, x2 = 0, x3 = 10 et en calculant les valeurs des variables d'écart :
- 10 + 3(0) + 2(10) + e1 = 30 ⇒ 30 + e1 = 30 ⇒ e1 = 0
- 10 + 0 + 10 + e2 = 24 ⇒ 20 + e2 = 24 ⇒ e2 = 4
- 3(10) + 5(0) + 3(10) + e3 = 60 ⇒ 60 + e3 = 60 ⇒ e3 = 0
Ainsi, la solution de base de départ est x = (10, 0, 10, 0, 4, 0) pour (x1, x2, x3, e1, e2, e3). Nous pouvons former le tableau du Simplexe en transformant cette base pour obtenir la forme canonique des variables de base (x1, x3, e2) :
Variables de base x1 x2 x3 e1 e2 e3 Z b R (Ratio) x1 1 1/3 0 -1 0 2/3 0 10 x3 0 4/3 1 1 0 -1/3 0 10 10 / (4/3) = 30/4 = 7.5 ← (Pivot) e2 0 -2/3 0 -1 1 -1/3 0 4 -Z 0 -1/3 ↑ 0 1 0 1/3 1 50 x2 est la variable entrante (coefficient le plus négatif dans la ligne Z). x3 est la variable sortante.
En effectuant une itération du Simplexe (pivotage sur l'élément (x3, x2) = 4/3), on obtient le tableau suivant :
Variables de base x1 x2 x3 e1 e2 e3 Z b x1 1 0 -1/4 -5/4 0 3/4 0 30/4 = 7.5 x2 0 1 3/4 3/4 0 -1/4 0 30/4 = 7.5 e2 0 0 1/2 -1/2 1 -1/2 0 9 -Z 0 0 1/4 5/4 0 1/4 1 52.5 Tous les coefficients de la ligne Z sont positifs ou nuls. La solution est optimale. La solution optimale primale est x* = (30/4, 30/4, 0), c'est-à-dire (7.5, 7.5, 0). Les valeurs des variables d'écart sont e1* = 0, e2* = 9, e3* = 0. La valeur optimale de Z est 52.5.
Exercice 5 : Réalisabilité de base et Dualité
Soit (P) le programme linéaire suivant :
Minimiser Z = 5x1 + 4x2 + 7x3
Sous contraintes :
- 3x1 + 8x2 + 2x3 ≤ 40
- 9x1 + 5x2 + 7x3 ≥ 35
- 7x1 + 3x2 + 3x3 ≥ 51
- x1, x2, x3 ≥ 0
- Montrer qu'une seule des solutions suivantes est réalisable de base pour (P). Justifier chaque cas.
- x = (5/3, 3, 0)
- x = (51/7, 0, 0)
- x = (4, 2, 6)
- Écrire le dual (D) de (P).
- Sans aucun calcul, utiliser les questions précédentes pour obtenir la solution du dual (D).
- On suppose maintenant que le sens de l'inégalité dans la 2ème contrainte de (P) est inversé, c'est-à-dire qu'on remplace 9x1 + 5x2 + 7x3 ≥ 35 par 9x1 + 5x2 + 7x3 ≤ 35. Montrer en utilisant la phase I du Simplexe que le nouveau programme linéaire est irréalisable.
Solution 5
En ajoutant des variables d'écart (e1) et d'excédent (e2, e3), le problème (P) devient :
Minimiser Z = 5x1 + 4x2 + 7x3
Sous contraintes :
- 3x1 + 8x2 + 2x3 + e1 = 40 (1)
- 9x1 + 5x2 + 7x3 − e2 = 35 (2)
- 7x1 + 3x2 + 3x3 − e3 = 51 (3)
- xi, ei ≥ 0, pour i = 1, 2, 3
-
- Pour x = (5/3, 3, 0) :
Vérifions les contraintes :
- (1) : 3(5/3) + 8(3) + 2(0) = 5 + 24 = 29 ≤ 40 (valide)
- (2) : 9(5/3) + 5(3) + 7(0) = 15 + 15 = 30 ≥ 35 (faux)
Cette solution n'est pas réalisable car la deuxième contrainte n'est pas satisfaite.
- Pour x = (51/7, 0, 0) :
Vérifions les contraintes :
- (1) : 3(51/7) + 8(0) + 2(0) = 153/7 = 21.86 ≤ 40 (valide). Donc e1 = 40 - 153/7 = (280 - 153)/7 = 127/7.
- (2) : 9(51/7) + 5(0) + 7(0) = 459/7 = 65.57 ≥ 35 (valide). Donc e2 = 459/7 - 35 = (459 - 245)/7 = 214/7.
- (3) : 7(51/7) + 3(0) + 3(0) = 51 ≥ 51 (valide). Donc e3 = 51 - 51 = 0.
Toutes les contraintes sont satisfaites, et toutes les variables (x1 = 51/7, x2 = 0, x3 = 0, e1 = 127/7, e2 = 214/7, e3 = 0) sont non-négatives. Nous avons trois variables de base non nulles (x1, e1, e2) et trois variables hors base nulles (x2, x3, e3), ce qui correspond à une solution de base réalisable.
- Pour x = (4, 2, 6) :
Vérifions les contraintes :
- (1) : 3(4) + 8(2) + 2(6) = 12 + 16 + 12 = 40 ≤ 40 (valide). Donc e1 = 0.
- (2) : 9(4) + 5(2) + 7(6) = 36 + 10 + 42 = 88 ≥ 35 (valide). Donc e2 = 88 - 35 = 53.
- (3) : 7(4) + 3(2) + 3(6) = 28 + 6 + 18 = 52 ≥ 51 (valide). Donc e3 = 52 - 51 = 1.
La solution x = (4, 2, 6) est réalisable. Cependant, pour être une solution de base, le nombre de variables non nulles doit être égal au nombre de contraintes (3 dans ce cas). Ici, nous avons x1=4, x2=2, x3=6, e2=53, e3=1 qui sont non nuls (5 variables). Comme e2 ≠ 0 et e3 ≠ 0, cette solution n'est pas une solution de base.
Seule la solution x = (51/7, 0, 0) est une solution de base réalisable.
- Pour x = (5/3, 3, 0) :
-
Le dual (D) du problème (P) est :
Maximiser ZD = 40y1 + 35y2 + 51y3
Sous contraintes :
- 3y1 + 9y2 + 7y3 ≤ 5 (pour x1)
- 8y1 + 5y2 + 3y3 ≤ 4 (pour x2)
- 2y1 + 7y2 + 3y3 ≤ 7 (pour x3)
- y1 ≤ 0 (car la 1ère contrainte primale est de type "≤")
- y2 ≥ 0 (car la 2ème contrainte primale est de type "≥")
- y3 ≥ 0 (car la 3ème contrainte primale est de type "≥")
-
D'après la question 1, la solution primale de base réalisable est x* = (51/7, 0, 0), avec les variables d'écart/excédent e1 = 127/7, e2 = 214/7 et e3 = 0.
En utilisant les conditions d'optimalité de la dualité (C.O.P.D.) :
- x1* = 51/7 > 0 implique que la 1ère contrainte duale est active : 3y1 + 9y2 + 7y3 = 5.
- e1 = 127/7 > 0 (variable d'écart de la 1ère contrainte primale) implique y1 = 0.
- e2 = 214/7 > 0 (variable d'excédent de la 2ème contrainte primale) implique y2 = 0.
- e3 = 0 (variable d'excédent de la 3ème contrainte primale) implique que la 3ème contrainte primale est active (ce qui est vrai : 7(51/7) = 51), donc y3 peut être non nulle.
En substituant y1 = 0 et y2 = 0 dans l'équation 3y1 + 9y2 + 7y3 = 5, on obtient :
3(0) + 9(0) + 7y3 = 5 ⇒ 7y3 = 5 ⇒ y3 = 5/7.
La solution optimale duale est donc y* = (0, 0, 5/7).
-
Si le sens de l'inégalité de la 2ème contrainte de (P) est inversé, le nouveau programme linéaire est :
Minimiser Z = 5x1 + 4x2 + 7x3
Sous contraintes :
- 3x1 + 8x2 + 2x3 ≤ 40
- 9x1 + 5x2 + 7x3 ≤ 35
- 7x1 + 3x2 + 3x3 ≥ 51
- x1, x2, x3 ≥ 0
En ajoutant les variables d'écart et d'excédent, et les variables artificielles (t1, t2, t3) pour les contraintes qui n'ont pas de base initiale immédiate (après transformation en égalités) :
- 3x1 + 8x2 + 2x3 + e1 = 40 (1)
- 9x1 + 5x2 + 7x3 + e2 = 35 (2)
- 7x1 + 3x2 + 3x3 − e3 + t = 51 (3) (où 't' est la variable artificielle pour cette contrainte)
Le problème auxiliaire de la Phase I consiste à minimiser la somme des variables artificielles. Ici, minimiser t (puisqu'une seule variable artificielle est nécessaire pour la 3ème contrainte).
Minimiser Zaux = t
Le premier tableau de la Phase I est construit avec la variable artificielle 't' dans la base et en exprimant Zaux en fonction des variables non basiques :
Variables de base x1 x2 x3 e1 e2 e3 t -Zaux b e1 3 8 2 1 0 0 0 0 40 e2 9 5 7 0 1 0 0 0 35 t 7 3 3 0 0 -1 1 0 51 -Zaux (initial) 0 0 0 0 0 0 0 1 0 -Zaux (ajusté) -7 -3 -3 0 0 1 0 1 -51 La variable x1 entre en base (coefficient le plus négatif, -7) et e2 sort de la base (35/9 est le ratio minimum, en supposant que e2 était une variable de base initiale, mais ici ce sont e1, e2, t qui sont initialement en base).
Pivot : x1 entre, e2 sort. Le ratio pour x1 dans la ligne e2 est 35/9 ≈ 3.88. Les autres sont 40/3 ≈ 13.33 et 51/7 ≈ 7.28. Donc, x1 entre en base à la place de e2.
Tableau après la première itération de la Phase I :
Variables de base x1 x2 x3 e1 e2 e3 t -Zaux b e1 0 19/3 -1/3 1 -1/3 0 0 0 85/3 x1 1 5/9 7/9 0 1/9 0 0 0 35/9 t 0 -8/9 -22/9 0 -7/9 -1 1 0 214/9 -Zaux 0 8/9 22/9 0 7/9 1 0 1 -214/9 Tous les coefficients de la ligne d'objectif de Zaux sont maintenant positifs ou nuls. Cela indique que l'optimalité pour la Phase I a été atteinte. Cependant, la variable artificielle 't' est restée en base avec une valeur non nulle (t = 214/9). Cela signifie qu'il est impossible de trouver une solution réalisable pour le problème initial, car les contraintes originales ne peuvent pas être satisfaites simultanément. Donc, le programme linéaire est irréalisable.
Exercice 6 : Analyse de solution optimale et dualité
Soit le programme linéaire suivant :
Minimiser Z = x2 − 3x3 + 2x5
Sous contraintes :
- 3x1 + 3x2 − x3 + 2x5 = 7
- −2x2 + 4x3 + x4 = 12
- −4x2 + 3x3 + 8x5 + x6 = 10
- xi ≥ 0, pour i = 1, ..., 6
La solution optimale de ce problème est x* = (0, 4, 5, 0, 0, 11).
- Donner l'ensemble des indices de base B associé à la solution optimale.
- Quelle est la solution de base duale y* associée à B ?
- Prouver l'optimalité des solutions x* et y*.
Solution 6
-
L'ensemble des indices de base B est constitué des indices des variables dont la valeur est non nulle dans la solution optimale. Pour x* = (0, 4, 5, 0, 0, 11), les variables non nulles sont x2, x3 et x6.
Donc, B = {2, 3, 6}.
-
Écrivons d'abord le dual de ce programme linéaire. Puisque toutes les contraintes primales sont des égalités et les variables primales sont non-négatives, les variables duales yi sont non restreintes en signe.
Maximiser ZD = 7y1 + 12y2 + 10y3
Sous contraintes :
- 3y1 ≤ 0 (pour x1)
- 3y1 − 2y2 − 4y3 ≤ 1 (pour x2)
- −y1 + 4y2 + 3y3 ≤ −3 (pour x3)
- y2 ≤ 0 (pour x4)
- 2y1 + 8y3 ≤ 2 (pour x5)
- y3 ≤ 0 (pour x6)
- yi quelconque, pour i = 1, 2, 3
En utilisant les conditions d'optimalité de la dualité (C.O.P.D.) :
Puisque x2* > 0 (4), la contrainte duale pour x2 est active : 3y1 − 2y2 − 4y3 = 1.
Puisque x3* > 0 (5), la contrainte duale pour x3 est active : −y1 + 4y2 + 3y3 = −3.
Puisque x6* > 0 (11), la contrainte duale pour x6 est active : y3 = 0.
En substituant y3 = 0 dans les deux premières équations, nous obtenons le système :
- 3y1 − 2y2 = 1
- −y1 + 4y2 = −3
De la deuxième équation, y1 = 4y2 + 3. Substituons ceci dans la première équation :
3(4y2 + 3) − 2y2 = 1
12y2 + 9 − 2y2 = 1
10y2 = −8
y2 = −8/10 = −4/5.
Maintenant, trouvons y1 : y1 = 4(−4/5) + 3 = −16/5 + 15/5 = −1/5.
Ainsi, la solution optimale duale est y* = (−1/5, −4/5, 0).
-
Pour prouver l'optimalité des solutions x* et y*, il suffit de vérifier trois conditions :
- x* est réalisable pour le primal : Vérifier que x* = (0, 4, 5, 0, 0, 11) satisfait toutes les contraintes primales et les conditions de non-négativité.
- 3(0) + 3(4) − (5) + 2(0) = 12 − 5 = 7 (valide)
- −2(4) + 4(5) + (0) = −8 + 20 = 12 (valide)
- −4(4) + 3(5) + 8(0) + (11) = −16 + 15 + 11 = 10 (valide)
- Toutes les xi sont ≥ 0 (valide).
- y* est réalisable pour le dual : Vérifier que y* = (−1/5, −4/5, 0) satisfait toutes les contraintes duales et les conditions de signe.
- 3(−1/5) = −3/5 ≤ 0 (valide)
- 3(−1/5) − 2(−4/5) − 4(0) = −3/5 + 8/5 = 5/5 = 1 ≤ 1 (valide)
- −(−1/5) + 4(−4/5) + 3(0) = 1/5 − 16/5 = −15/5 = −3 ≤ −3 (valide)
- −4/5 ≤ 0 (valide)
- 2(−1/5) + 8(0) = −2/5 ≤ 2 (valide)
- 0 ≤ 0 (valide)
- Les valeurs objectives primale et duale sont égales :
- Z* (primal) = x2* − 3x3* + 2x5* = 4 − 3(5) + 2(0) = 4 − 15 = −11.
- ZD* (dual) = 7y1* + 12y2* + 10y3* = 7(−1/5) + 12(−4/5) + 10(0) = −7/5 − 48/5 = −55/5 = −11.
Puisque toutes ces conditions sont remplies, les solutions x* et y* sont optimales.
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 (PL) est une technique mathématique utilisée pour optimiser (maximiser ou minimiser) une fonction linéaire, appelée fonction objectif, sous un ensemble de contraintes linéaires (égalités ou inégalités). Elle est largement utilisée dans la gestion des opérations, l'économie, l'ingénierie et la planification pour prendre des décisions optimales, comme la maximisation des profits, la minimisation des coûts, l'allocation de ressources ou l'ordonnancement de production.
- En quoi consiste la méthode du Simplexe et quand est-elle appliquée ?
- La méthode du Simplexe est un algorithme itératif populaire pour résoudre les problèmes de programmation linéaire. Elle commence par une solution de base réalisable et se déplace itérativement vers des solutions adjacentes, améliorant la valeur de la fonction objectif à chaque étape, jusqu'à atteindre la solution optimale. Elle est appliquée lorsque le problème a de nombreuses variables et contraintes, et ne peut pas être résolu graphiquement (ce qui est généralement limité à deux ou trois dimensions).
- Quel est le principe de la dualité en programmation linéaire ?
- La dualité en programmation linéaire est un concept fondamental qui stipule que chaque problème de programmation linéaire (appelé problème primal) a un problème de programmation linéaire associé (appelé problème dual). Le problème dual est formulé à partir des contraintes et coefficients du primal, et inversement. La relation de dualité est très utile : elle fournit une borne sur la valeur de la fonction objectif du primal, et des théorèmes clés comme le théorème de la dualité forte garantissent que si un problème a une solution optimale, son dual en a également une, et leurs valeurs optimales sont égales. Les solutions duales fournissent également des informations précieuses sur la sensibilité de la solution primale aux changements dans les contraintes.