Tableaux des correspondances entre variables du primal et du
Télécharger PDFOptimisation Linéaire - Travaux Dirigés 8
E.I.S.T.I. - Département Mathématiques
1re Année Ingénieurs - 27 mars 2012
Concepts Clés
- Méthode Géométrique
- Méthode des tableaux du Simplexe
- Méthode des Pénalités
- Méthode de Dualité
- Programmation en nombres entiers (Méthodes des coupes ou des congruences décroissantes)
Exercice 1 : Résolution de Programme Linéaire
1. Résolution par la méthode géométrique
Résoudre le programme linéaire suivant (P.1) par la méthode géométrique :
Maximiser Z = -3x1 + x2
Sous les contraintes :
- -4x1 + 10x2 ≤ 25
- 2x1 + x2 ≤ 10
- 2x1 - x2 ≤ 6
- x1 ≥ 0, x2 ≥ 0
Étapes de la résolution graphique :
Les droites associées aux contraintes sont :
- L1 : -4x1 + 10x2 = 25 ⇒ x2 = 2,5 + 0,4x1
- L2 : 2x1 + x2 = 10 ⇒ x2 = 10 - 2x1
- L3 : 2x1 - x2 = 6 ⇒ x2 = 2x1 - 6
La droite d'iso-profit pour Z = -3x1 + x2 est de la forme x2 = Z + 3x1. La direction de maximisation est celle où Z augmente.
Le domaine des solutions réalisables K est le polygone défini par l'intersection des demi-plans des contraintes et les conditions de non-négativité.
En analysant les sommets du domaine réalisable, le point qui maximise Z est l'intersection de la contrainte -4x1 + 10x2 = 25 et de la contrainte x1 = 0.
Pour x1 = 0 : 10x2 = 25 ⇒ x2 = 2,5.
La solution optimale est donc (x1*, x2*) = (0, 2,5).
La valeur maximale de la fonction objectif est Zmax = -3(0) + 2,5 = 2,5.
2. Formulation du problème dual et résolution
i) Établissement du problème dual et méthode des pénalités
Le problème primal (P.1) est sous forme de maximisation avec des contraintes de type ≤ et des variables non-négatives.
Maximiser Z = -3x1 + x2
Sous les contraintes :
- -4x1 + 10x2 ≤ 25
- 2x1 + x2 ≤ 10
- 2x1 - x2 ≤ 6
- x1 ≥ 0, x2 ≥ 0
Tableau des correspondances Primal-Dual
| Primal (Maximisation) | Dual (Minimisation) |
|---|---|
| Maximiser Z = cTx | Minimiser W = bTu |
| Contrainte i : ≤ bi | Variable duale ui ≥ 0 |
| Contrainte i : ≥ bi | Variable duale ui ≤ 0 |
| Contrainte i : = bi | Variable duale ui sans restriction de signe |
| Variable xj ≥ 0 | Contrainte duale j : ≥ cj |
| Variable xj ≤ 0 | Contrainte duale j : ≤ cj |
| Variable xj sans restriction de signe | Contrainte duale j : = cj |
| Matrice des contraintes A | Matrice des contraintes AT |
Formulation du problème dual (D) :
Minimiser W = 25u1 + 10u2 + 6u3
Sous les contraintes :
- -4u1 + 2u2 + 2u3 ≥ -3 (correspond à x1)
- 10u1 + u2 - u3 ≥ 1 (correspond à x2)
- u1 ≥ 0, u2 ≥ 0, u3 ≥ 0
Inapplicabilité directe de l'algorithme du simplexe et utilisation de la méthode des pénalités :
Pour appliquer directement l'algorithme du simplexe, le problème doit être sous forme canonique (pour la maximisation) ou standard (pour la minimisation), avec une base réalisable initiale évidente (typiquement des variables d'écart avec des seconds membres non négatifs).
Ici, nous avons un problème de minimisation avec des contraintes de type ≥.
En introduisant des variables d'excédent (s1, s2) :
- -4u1 + 2u2 + 2u3 - s1 = -3
- 10u1 + u2 - u3 - s2 = 1
La première contrainte a un second membre négatif (-3), et les variables d'excédent apparaissent avec un coefficient de -1, ce qui ne permet pas d'avoir une base réalisable initiale facile (matrice identité). Pour remédier à cela, la méthode des pénalités (méthode M) est utilisée. Elle consiste à introduire des variables artificielles (a1, a2) avec un coût M très élevé dans la fonction objectif (pour les forcer à sortir de la base) afin de construire une base réalisable de départ.
Le problème avec variables artificielles (après avoir ajusté la première contrainte pour un second membre positif) :
Minimiser W = 25u1 + 10u2 + 6u3 + Ma1 + Ma2
Sous les contraintes :
- 4u1 - 2u2 - 2u3 + s1 + a1 = 3 (ici s1 est une variable d'écart après changement de signe)
- 10u1 + u2 - u3 - s2 + a2 = 1
- u1, u2, u3, s1, s2, a1, a2 ≥ 0
On peut alors construire le premier tableau du simplexe et appliquer la méthode.
ii) Solution du Dual par le théorème de dualité et le principe de complémentarité
Le théorème de dualité forte stipule que si le primal a une solution optimale finie, alors le dual a aussi une solution optimale finie, et leurs valeurs optimales sont égales (Z* = W*).
La solution optimale du primal (P.1), trouvée graphiquement, est (x1*, x2*) = (0, 2,5) avec Z* = 2,5.
Le principe de complémentarité permet de déduire la solution duale :
- Si une contrainte primale est non saturée (stricte inégalité à l'optimum), la variable duale correspondante est nulle.
- Si une variable primale est positive à l'optimum, la contrainte duale correspondante est saturée (égalité à l'optimum).
Appliquons cela à la solution primale (x1* = 0, x2* = 2,5) :
- Contraintes du primal :
- C1: -4x1 + 10x2 ≤ 25 ⇒ -4(0) + 10(2,5) = 25. Contrainte saturée. u1* n'est pas nulle.
- C2: 2x1 + x2 ≤ 10 ⇒ 2(0) + 2,5 = 2,5 ≤ 10. Contrainte non saturée. Donc u2* = 0.
- C3: 2x1 - x2 ≤ 6 ⇒ 2(0) - 2,5 = -2,5 ≤ 6. Contrainte non saturée. Donc u3* = 0.
- Variables du primal :
- x1* = 0. Donc la première contrainte duale n'est pas nécessairement saturée.
- x2* = 2,5 > 0. Donc la seconde contrainte duale est saturée : 10u1 + u2 - u3 = 1.
En utilisant u2* = 0 et u3* = 0 dans la contrainte duale saturée :
10u1* + 0 - 0 = 1 ⇒ 10u1* = 1 ⇒ u1* = 0,1.
Vérifions la première contrainte duale : -4u1* + 2u2* + 2u3* ≥ -3 ⇒ -4(0,1) + 2(0) + 2(0) = -0,4 ≥ -3. Elle est satisfaite.
La solution optimale du problème dual est donc (u1*, u2*, u3*) = (0,1; 0; 0).
La valeur optimale duale est W* = 25(0,1) + 10(0) + 6(0) = 2,5.
Commentaire : La valeur optimale du dual (W* = 2,5) est égale à celle du primal (Z* = 2,5), confirmant le théorème de dualité forte. Les valeurs des variables duales (prix duaux) indiquent la variation de la fonction objectif si le second membre de la contrainte correspondante est modifié. Par exemple, u1* = 0,1 signifie qu'une augmentation d'une unité du second membre de la première contrainte primale augmenterait Z* de 0,1.
Exercice 2 : Programmation en Nombres Entiers
On considère le problème (P.2) :
Maximiser Z = -3x1 + x2
Sous les contraintes :
- -4x1 + 10x2 ≤ 25
- 2x1 + x2 ≤ 10
- 2x1 - x2 ≤ 6
- x1 ≥ 0, x2 ≥ 0, x2 ∈ ℕ (x2 doit être un entier naturel)
Solution optimale fractionnaire (pour P.1 ou relaxation de P.2) :
Le problème demande d'utiliser un tableau du simplexe qui fournirait une solution pour le problème (P.1) (ou sa relaxation continue). Le tableau fourni dans le texte, bien que présentant des incohérences avec la solution géométrique (0, 2,5) de l'Exercice 1, indique les valeurs suivantes pour les variables de base :
- x1* = 26/10 = 2,6
- x2* = 24/10 = 2,4
Pour la suite de cet exercice sur la programmation en nombres entiers, nous partons de cette solution fractionnaire pour l'application des coupes de Gomory. La valeur de la fonction objectif correspondante serait Z* = -3(2,6) + 2,4 = -7,8 + 2,4 = -5,4.
Comparaison avec la solution géométrique (0, 2,5) : Il est à noter que la solution optimale (2,6; 2,4) obtenue par la méthode du simplexe (selon le tableau fourni) diffère de la solution graphique trouvée précédemment (0; 2,5). Pour les besoins de l'exercice 2, nous utiliserons la solution (2,6; 2,4) comme point de départ pour l'application des coupes de Gomory, comme suggéré par l'énoncé ("Comparer ce résultat avec votre solution géometrique du 1.)").
1. Analyse de la solution fractionnaire pour P.2
La solution (x1*, x2*) = (2,6; 2,4) n'est pas une solution optimale pour le problème (P.2) car la variable x2, qui doit être un entier (x2 ∈ ℕ), a une valeur fractionnaire (2,4). Par conséquent, cette solution n'est pas réalisable pour le problème en nombres entiers.
2. Application de la méthode des coupes de Gomory
i) Obtention d'une coupe de Gomory pour x2 entier
Nous cherchons à rendre x2 entier. Puisque x2* = 2,4, nous devons ajouter une contrainte (coupe) qui élimine cette solution fractionnaire sans éliminer de solution entière réalisable.
En se basant sur la première contrainte du primal après l'ajout de la variable d'écart x3 :
-4x1 + 10x2 + x3 = 25
Puisque x2 doit être un entier (x2 ∈ ℕ), le terme 10x2 est un multiple de 10. Par conséquent, l'expression 25 + 4x1 - x3 doit être un multiple de 10.
25 + 4x1 - x3 ≡ 0 [10]
En réduisant les constantes modulo 10 :
5 + 4x1 - x3 ≡ 0 [10]
Ceci implique que 4x1 - x3 doit être congru à -5 modulo 10, ou à 5 modulo 10, etc.
Une expression équivalente est : 6x1 + x3 ≡ 5 [10].
Une coupe de Gomory valide est dérivée de cette congruence : 6x1 + x3 ≥ 5.
Pour intégrer cette nouvelle contrainte au simplexe, on la transforme en égalité en ajoutant une variable d'écart x6 :
6x1 + x3 - x6 = 5 (ou -6x1 - x3 + x6 = -5)
On ajoute cette ligne au tableau du simplexe et on applique les itérations nécessaires.
Solution après l'ajout de la coupe :
Après l'ajout de la coupe (x2 ≤ x1 + 2) et la réoptimisation, le texte suggère une solution entière.
Le résultat attendu après l'application de cette coupe et la résolution du nouveau programme linéaire serait la solution suivante :
- x1* = 0
- x2* = 2
Cette solution respecte la contrainte d'intégrité pour x2. La valeur de la fonction objectif est Z = -3(0) + 2 = 2.
ii) Représentation graphique de la coupe
Pour représenter la coupe sur le graphique (plan (x1, x2)), il faut exprimer la variable d'écart x3 en fonction de x1 et x2 à partir de la première contrainte du problème initial :
-4x1 + 10x2 + x3 = 25
Donc, x3 = 25 + 4x1 - 10x2.
Substituons cette expression de x3 dans l'inégalité de la coupe (6x1 + x3 ≥ 5) :
6x1 + (25 + 4x1 - 10x2) ≥ 5
10x1 - 10x2 + 25 ≥ 5
10x1 - 10x2 ≥ -20
En divisant par 10 :
x1 - x2 ≥ -2
Ou, de manière équivalente : x2 ≤ x1 + 2.
Cette nouvelle contrainte est une droite qui doit être ajoutée au graphique. Elle coupe le domaine des solutions réalisables, éliminant la solution fractionnaire (2,6; 2,4) et réduisant le domaine. Le nouveau domaine contient uniquement les solutions entières qui satisfont toutes les contraintes, y compris la coupe. L'optimum entier (0, 2) se trouve dans ce nouveau domaine.
Exercice 3 : Modélisation d'un problème de régime alimentaire
1. Formalisation du problème et justification
Définissons les variables de décision :
- x1 : quantité de produit de la Marque 1
- x2 : quantité de produit de la Marque 2
Fonction objectif (minimiser le coût total) :
Minimiser Z = 4x1 + 2x2
Contraintes (besoins minimaux en vitamines) :
- Vitamine A : 2x1 + 4x2 ≥ 7
- Vitamine C : 3x1 + x2 ≥ 5
- Vitamine D : 3x1 + 5x2 ≥ 2
Contraintes de non-négativité :
- x1 ≥ 0, x2 ≥ 0
Ce problème est un problème de programmation linéaire (PL).
Justification :
- La fonction objectif (le coût total) est une fonction linéaire des variables x1 et x2.
- Toutes les contraintes (liées aux besoins en vitamines) sont des inégalités linéaires.
- Les variables de décision x1 et x2 sont continues et soumises à des contraintes de non-négativité.
2. Résolution graphique
Oui, une résolution graphique de ce problème est envisageable car il ne comporte que deux variables de décision (x1 et x2).
Étapes de la résolution graphique :
Les droites correspondant aux contraintes sont :
- L1 : 2x1 + 4x2 = 7 ⇒ x2 = 1,75 - 0,5x1
- L2 : 3x1 + x2 = 5 ⇒ x2 = 5 - 3x1
- L3 : 3x1 + 5x2 = 2 ⇒ x2 = 0,4 - 0,6x1
Le domaine des solutions réalisables est l'intersection des demi-plans définis par ces contraintes (de type ≥) et les conditions de non-négativité (x1 ≥ 0, x2 ≥ 0). C'est un polygone non borné vers le haut et la droite.
La droite d'iso-coût est Z = 4x1 + 2x2, ou x2 = Z/2 - 2x1. On cherche à minimiser Z en déplaçant cette droite vers l'origine.
Le point optimal est un sommet du polygone des solutions réalisables. Cherchons l'intersection des droites L1 et L2, car elles semblent critiques pour le domaine :
- De L2, exprimons x2 : x2 = 5 - 3x1
- Substituons dans L1 : 2x1 + 4(5 - 3x1) = 7
- 2x1 + 20 - 12x1 = 7
- -10x1 = -13 ⇒ x1 = 13/10 = 1,3
- Calculons x2 : x2 = 5 - 3(1,3) = 5 - 3,9 = 1,1
Le point d'intersection est (1,3; 1,1).
Vérifions si ce point satisfait la troisième contrainte (L3) :
3(1,3) + 5(1,1) = 3,9 + 5,5 = 9,4.
Puisque 9,4 ≥ 2, la contrainte L3 est satisfaite. Ce point est donc réalisable.
Le coût Z à ce point est : Z = 4(1,3) + 2(1,1) = 5,2 + 2,2 = 7,4.
En déplaçant la droite d'iso-coût, on peut confirmer que le sommet (1,3; 1,1) est la solution optimale.
La solution optimale est (x1*, x2*) = (1,3; 1,1) avec un coût minimal Zmin = 7,4.
Foire Aux Questions (FAQ)
Qu'est-ce que la méthode des pénalités en programmation linéaire ?
La méthode des pénalités, ou méthode M, est une technique utilisée en programmation linéaire pour trouver une base réalisable initiale lorsque le problème ne présente pas de variables d'écart formant une matrice identité (par exemple, avec des contraintes de type "supérieur ou égal" ou "égal"). Elle consiste à introduire des "variables artificielles" dans les contraintes et à leur assigner un très grand coût (M) dans la fonction objectif (M pour la minimisation, -M pour la maximisation) afin de les forcer à être nulles dans la solution optimale.
Pourquoi une solution non entière n'est-elle pas optimale pour un problème en nombres entiers ?
Dans un problème de programmation en nombres entiers (PNI), certaines ou toutes les variables de décision sont contraintes à prendre des valeurs entières. Une solution obtenue en relâchant ces contraintes (appelée solution fractionnaire ou continue) peut être mathématiquement optimale pour le problème continu, mais elle est invalide pour le PNI si les variables entières prennent des valeurs non entières. L'objectif est de trouver la meilleure solution qui satisfasse également toutes les contraintes d'intégrité.
Comment une coupe de Gomory modifie-t-elle le domaine des solutions ?
Une coupe de Gomory est une contrainte linéaire supplémentaire, dérivée des lignes du tableau du simplexe à une solution fractionnaire. Elle est conçue pour "couper" le domaine des solutions réalisables en éliminant la solution fractionnaire actuelle (et d'autres solutions non entières) sans exclure aucune solution entière qui aurait été réalisable. Graphiquement, cela correspond à l'ajout d'une nouvelle frontière qui réduit l'espace de recherche des solutions, guidant l'algorithme vers une solution entière optimale.