Devoir à la maison corrigé
Exercice 1 - Résolution par la méthode simplexe Partie A - Simplexe primal Le problème à résoudre est le suivant : Maximiser z = 2x₁ + x₂ + 3x₃ Sous les contraintes : -x₁ + 2x₂ + x₃ ≤ 6 x₁ + x₂ ≤ 24 x₁ - x₂ + x₃ ≤ 9 x₁, x₂, x₃ ≥ 0 Nous introduisons les variables d'écart e₁, e₂ et e₃ pour obtenir la forme standard.
D'après le document Devoir à la maison corrigé
Cet article a été rédigé automatiquement à partir du document source, puis vérifié avant publication.
Document source
Mathematics, Optimization · PDF · 7 pages
Afficher l'aperçu du document
Exercice 1 - Résolution par la méthode simplexe
Partie A - Simplexe primal
Le problème à résoudre est le suivant : Maximiser z = 2x₁ + x₂ + 3x₃ Sous les contraintes : -x₁ + 2x₂ + x₃ ≤ 6 x₁ + x₂ ≤ 24 x₁ - x₂ + x₃ ≤ 9 x₁, x₂, x₃ ≥ 0
Nous introduisons les variables d'écart e₁, e₂ et e₃ pour obtenir la forme standard.
Tableau 1
| Base | x₁ | x₂ | x₃ | e₁ | e₂ | e₃ | b |
|---|---|---|---|---|---|---|---|
| e₁ | -1 | 2 | 1 | 1 | 0 | 0 | 6 |
| e₂ | 1 | 1 | 0 | 0 | 1 | 0 | 24 |
| e₃ | 1 | -1 | 1 | 0 | 0 | 1 | 9 |
| z | -2 | -1 | -3 | 0 | 0 | 0 | 0 |
x₃ entre dans la base et e₁ sort ⇒ L₁* = L₁ ← L₁ / 1. Ensuite, L₂ ← L₂ - 0 × L₁, L₃ ← L₃ - 1 × L₁, Lz ← Lz + 3 × L₁
Tableau 2
| Base | x₁ | x₂ | x₃ | e₁ | e₂ | e₃ | b |
|---|---|---|---|---|---|---|---|
| x₃ | -1 | 2 | 1 | 1 | 0 | 0 | 6 |
| e₂ | 1 | 1 | 0 | 0 | 1 | 0 | 24 |
| e₃ | 2 | -3 | 0 | -1 | 0 | 1 | 3 |
| z | -5 | 5 | 0 | 3 | 0 | 0 | 18 |
x₁ entre dans la base et e₃ sort ⇒ L₃* = L₃ ← L₃ / 2. Ensuite, L₁ ← L₁ + 1 × L₃, L₂ ← L₂ - 1 × L₃, Lz ← Lz + 5 × L₃ Note de correction : La source indiquait par erreur Lz ← Lz + 5 × L₁ pour cette itération. La formule exacte utilise la nouvelle ligne pivot L₃.
Tableau 3
| Base | x₁ | x₂ | x₃ | e₁ | e₂ | e₃ | b |
|---|---|---|---|---|---|---|---|
| x₃ | 0 | 1/2 | 1 | 1/2 | 0 | 1/2 | 15/2 |
| e₂ | 0 | 5/2 | 0 | 1/2 | 1 | -1/2 | 45/2 |
| x₁ | 1 | -3/2 | 0 | -1/2 | 0 | 1/2 | 3/2 |
| z | 0 | -5/2 | 0 | 1/2 | 0 | 5/2 | 51/2 |
x₂ entre dans la base et e₂ sort ⇒ L₂* = L₂ ← L₂ × 2/5. Ensuite, L₁ ← L₁ - 1/2 × L₂, L₃ ← L₃ + 3/2 × L₂, Lz ← Lz + 5/2 × L₂
Tableau 4
| Base | x₁ | x₂ | x₃ | e₁ | e₂ | e₃ | b |
|---|---|---|---|---|---|---|---|
| x₃ | 0 | 0 | 1 | 2/5 | -1/5 | 3/5 | 3 |
| x₂ | 0 | 1 | 0 | 1/5 | 2/5 | -1/5 | 9 |
| x₁ | 1 | 0 | 0 | -1/5 | 3/5 | 1/5 | 15 |
| z | 0 | 0 | 0 | 1 | 1 | 2 | 48 |
Solution de Base Réalisable (SBR) optimale (car les coefficients de la ligne z sont ≥ 0) : xB = (x₃, x₂, x₁)ᵀ = (3, 9, 15)ᵀ xL = (e₁, e₂, e₃)ᵀ = (0, 0, 0)ᵀ z* = 48
Remarque : L'exactitude du calcul peut être vérifiée en recalculant z* à partir de son expression initiale : z* = 2(15) + 9 + 3(3) = 30 + 9 + 9 = 48 (ok).
Partie B - Simplexe dual et méthode en deux phases
Le problème à résoudre est modélisé par : Maximiser z = 2x₁ - x₂ + x₃ Sous les contraintes : -x₁ + 2x₂ + 2x₃ ≤ 10 -x₁ + 4x₃ ≤ -2 (équivalent à x₁ - 4x₃ ≥ 2) x₁ - x₂ + 2x₃ ≤ 4 x₁, x₂, x₃ ≥ 0
Méthode 1 : Simplexe dual
Tableau 1
| Base | x₁ | x₂ | x₃ | e₁ | e₂ | e₃ | b |
|---|---|---|---|---|---|---|---|
| e₁ | -1 | 2 | 2 | 1 | 0 | 0 | 10 |
| e₂ | 1 | 0 | -4 | 0 | 1 | 0 | -2 |
| e₃ | 1 | -1 | 2 | 0 | 0 | 1 | 4 |
| z | -2 | 1 | -1 | 0 | 0 | 0 | 0 |
e₂ sort et x₃ entre ⇒ L₂* = L₂ ← L₂ / -4. Ensuite, L₁ ← L₁ - 2 × L₂, L₃ ← L₃ - 2 × L₂, Lz ← Lz + L₂. Note de correction : La source répétait L₁ ← L₁ - 2 × L₂ deux fois au lieu d'indiquer la transformation pour L₃. Le calcul a été correctement appliqué ci-dessous.
Tableau 2
| Base | x₁ | x₂ | x₃ | e₁ | e₂ | e₃ | b |
|---|---|---|---|---|---|---|---|
| e₁ | -1/2 | 2 | 0 | 1 | 1/2 | 0 | 9 |
| x₃ | -1/4 | 0 | 1 | 0 | -1/4 | 0 | 1/2 |
| e₃ | 3/2 | -1 | 0 | 0 | 1/2 | 1 | 3 |
| z | -9/4 | 1 | 0 | 0 | -1/4 | 0 | 1/2 |
Le vecteur b étant devenu positif, nous revenons au simplexe primal. x₁ entre et e₃ sort ⇒ L₃* = L₃ ← L₃ × 2/3. Ensuite, L₁ ← L₁ + 1/2 × L₃, L₂ ← L₂ + 1/4 × L₃, Lz ← Lz + 9/4 × L₃.
Tableau 3
| Base | x₁ | x₂ | x₃ | e₁ | e₂ | e₃ | b |
|---|---|---|---|---|---|---|---|
| e₁ | 0 | 5/3 | 0 | 1 | 2/3 | 1/3 | 10 |
| x₃ | 0 | -1/6 | 1 | 0 | -1/6 | 1/6 | 1 |
| x₁ | 1 | -2/3 | 0 | 0 | 1/3 | 2/3 | 2 |
| z | 0 | -1/2 | 0 | 0 | 1/2 | 3/2 | 5 |
x₂ entre et e₁ sort ⇒ L₁* = L₁ ← L₁ × 3/5. Ensuite, L₂ ← L₂ + 1/6 × L₁, L₃ ← L₃ + 2/3 × L₁, Lz ← Lz + 1/2 × L₁.
Tableau 4
| Base | x₁ | x₂ | x₃ | e₁ | e₂ | e₃ | b |
|---|---|---|---|---|---|---|---|
| x₂ | 0 | 1 | 0 | 3/5 | 2/5 | 1/5 | 6 |
| x₃ | 0 | 0 | 1 | 1/10 | -1/10 | 1/5 | 2 |
| x₁ | 1 | 0 | 0 | 2/5 | 3/5 | 4/5 | 6 |
| z | 0 | 0 | 0 | 3/10 | 2/3 | 8/5 | 8 |
Note de correction : Le coefficient de e₁ dans la ligne z de la source indiquait "2/7". Le calcul exact donne (1/2 × 3/5 = 3/10).
Méthode 2 : Simplexe en deux phases
Phase 1
Tableau 1
| Base | x₁ | x₂ | x₃ | e₁ | e₂ | e₃ | a₁ | b |
|---|---|---|---|---|---|---|---|---|
| e₁ | -1 | 2 | 2 | 1 | 0 | 0 | 0 | 10 |
| a₁ | -1 | 0 | 4 | 0 | -1 | 0 | 1 | 2 |
| e₃ | 1 | -1 | 2 | 0 | 0 | 1 | 0 | 4 |
| z' | 1 | 0 | -4 | 0 | 1 | 0 | 0 | -2 |
Remarque : La ligne z' a été recalculée selon la formule Lz' ← Lz' - L₂ pour que la variable de base a₁ admette une colonne valide. x₃ entre et a₁ sort ⇒ L₂* = L₂ ← L₂ / 4. Ensuite, L₁ ← L₁ - 2 × L₂, L₃ ← L₃ - 2 × L₂, Lz' ← Lz' + 4 × L₂.
Tableau 2
| Base | x₁ | x₂ | x₃ | e₁ | e₂ | e₃ | a₁ | b |
|---|---|---|---|---|---|---|---|---|
| e₁ | -1/2 | 2 | 0 | 1 | 1/2 | 0 | - | 9 |
| x₃ | -1/4 | 0 | 1 | 0 | -1/4 | 0 | - | 1/2 |
| e₃ | 3/2 | -1 | 0 | 0 | 1/2 | 1 | - | 3 |
| z' | 0 | 0 | 0 | 0 | 0 | 0 | - | 0 |
Phase 2
Tableau 3
| Base | x₁ | x₂ | x₃ | e₁ | e₂ | e₃ | b |
|---|---|---|---|---|---|---|---|
| e₁ | -1/2 | 2 | 0 | 1 | 1/2 | 0 | 9 |
| x₃ | -1/4 | 0 | 1 | 0 | -1/4 | 0 | 1/2 |
| e₃ | 3/2 | -1 | 0 | 0 | 1/2 | 1 | 3 |
| z | -9/4 | 1 | 0 | 0 | -1/4 | 0 | 1/2 |
Remarque : La ligne z a été recalculée avec Lz ← Lz(initiale) + L₂ pour annuler le coefficient de x₃. x₁ entre et e₃ sort ⇒ L₃* = L₃ ← L₃ × 2/3. Ensuite, L₁ ← L₁ + 1/2 × L₃, L₂ ← L₂ + 1/4 × L₃, Lz ← Lz + 9/4 × L₃.
Tableau 4
| Base | x₁ | x₂ | x₃ | e₁ | e₂ | e₃ | b |
|---|---|---|---|---|---|---|---|
| e₁ | 0 | 5/3 | 0 | 1 | 2/3 | 1/3 | 10 |
| x₃ | 0 | -1/6 | 1 | 0 | -1/6 | 1/6 | 1 |
| x₁ | 1 | -2/3 | 0 | 0 | 1/3 | 2/3 | 2 |
| z | 0 | -1/2 | 0 | 0 | 1/2 | 3/2 | 5 |
x₂ entre et e₁ sort ⇒ L₁* = L₁ ← L₁ × 3/5. Ensuite, L₂ ← L₂ + 1/6 × L₁, L₃ ← L₃ + 2/3 × L₁, Lz ← Lz + 1/2 × L₁.
Tableau 5
| Base | x₁ | x₂ | x₃ | e₁ | e₂ | e₃ | b |
|---|---|---|---|---|---|---|---|
| x₂ | 0 | 1 | 0 | 3/5 | 2/5 | 1/5 | 6 |
| x₃ | 0 | 0 | 1 | 1/10 | -1/10 | 1/5 | 2 |
| x₁ | 1 | 0 | 0 | 2/5 | 3/5 | 4/5 | 6 |
| z | 0 | 0 | 0 | 3/10 | 2/3 | 8/5 | 8 |
SBR optimale : xB = (x₂, x₃, x₁)ᵀ = (6, 2, 6)ᵀ, avec z* = 8.
Exercice 2 - Simplexe en deux phases
Note de correction : Les valeurs initiales extraites du document source (b = 6, 3, 12) indiquent que le problème résolu dans les tableaux est le suivant : Maximiser z = 2x₁ + x₂ + 3x₃ Sous les contraintes : -x₁ + 2x₂ + x₃ ≤ 6 x₃ ≥ 3 x₁ - x₂ + 2x₃ ≤ 12 x₁, x₂, x₃ ≥ 0
Phase 1
| Base | x₁ | x₂ | x₃ | e₁ | e₂ | e₃ | a₁ | b |
|---|---|---|---|---|---|---|---|---|
| e₁ | -1 | 2 | 1 | 1 | 0 | 0 | 0 | 6 |
| a₁ | 0 | 0 | 1 | 0 | -1 | 0 | 1 | 3 |
| e₃ | 1 | -1 | 2 | 0 | 0 | 1 | 0 | 12 |
| z' | 0 | 0 | -1 | 0 | 1 | 0 | 0 | -3 |
Pivot sur la ligne a₁, colonne x₃.
| Base | x₁ | x₂ | x₃ | e₁ | e₂ | e₃ | b |
|---|---|---|---|---|---|---|---|
| e₁ | -1 | 2 | 0 | 1 | 1 | 0 | 3 |
| x₃ | 0 | 0 | 1 | 0 | -1 | 0 | 3 |
| e₃ | 1 | -1 | 0 | 0 | 2 | 1 | 6 |
| z' | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
Phase 2
| Base | x₁ | x₂ | x₃ | e₁ | e₂ | e₃ | b |
|---|---|---|---|---|---|---|---|
| e₁ | -1 | 2 | 0 | 1 | 1 | 0 | 3 |
| x₃ | 0 | 0 | 1 | 0 | -1 | 0 | 3 |
| e₃ | 1 | -1 | 0 | 0 | 2 | 1 | 6 |
| z | -2 | -1 | 0 | 0 | -3 | 0 | 9 |
Pivot sur la ligne e₁, colonne e₂.
| Base | x₁ | x₂ | x₃ | e₁ | e₂ | e₃ | b |
|---|---|---|---|---|---|---|---|
| e₂ | -1 | 2 | 0 | 1 | 1 | 0 | 3 |
| x₃ | -1 | 2 | 1 | 1 | 0 | 0 | 6 |
| e₃ | 3 | -5 | 0 | -2 | 0 | 1 | 0 |
| z | -5 | 5 | 0 | 3 | 0 | 0 | 18 |
Pivot sur la ligne e₃, colonne x₁.
| Base | x₁ | x₂ | x₃ | e₁ | e₂ | e₃ | b |
|---|---|---|---|---|---|---|---|
| e₂ | 0 | 1/3 | 0 | 1/3 | 1 | 1/3 | 3 |
| x₃ | 0 | 1/3 | 1 | 1/3 | 0 | 1/3 | 6 |
| x₁ | 1 | -5/3 | 0 | -2/3 | 0 | 1/3 | 0 |
| z | 0 | -10/3 | 0 | -1/3 | 0 | 5/3 | 18 |
Pivot sur la ligne e₂, colonne x₂.
| Base | x₁ | x₂ | x₃ | e₁ | e₂ | e₃ | b |
|---|---|---|---|---|---|---|---|
| x₂ | 0 | 1 | 0 | 1 | 3 | 1 | 9 |
| x₃ | 0 | 0 | 1 | 0 | -1 | 0 | 3 |
| x₁ | 1 | 0 | 0 | 1 | 5 | 2 | 15 |
| z | 0 | 0 | 0 | 3 | 10 | 5 | 48 |
SBR optimale : xB = (x₂, x₃, x₁)ᵀ = (9, 3, 15)ᵀ et z* = 48.
Exercice 3 - Simplexe primal
Le problème posé : Maximiser z = 3x₁ + 2x₂ + 4x₃ Sous les contraintes : x₁ + x₂ + 2x₃ ≤ 4 2x₁ + 3x₂ + 0x₃ ≤ 7 2x₁ + x₂ + 3x₃ ≤ 7 x₁, x₂, x₃ ≥ 0
Tableau 1
| Base | x₁ | x₂ | x₃ | e₁ | e₂ | e₃ | b |
|---|---|---|---|---|---|---|---|
| e₁ | 1 | 1 | 2 | 1 | 0 | 0 | 4 |
| e₂ | 2 | 3 | 0 | 0 | 1 | 0 | 7 |
| e₃ | 2 | 1 | 3 | 0 | 0 | 1 | 7 |
| z | -3 | -2 | -4 | 0 | 0 | 0 | 0 |
x₃ entre et e₁ sort ⇒ L₁* = L₁ ← L₁ / 2. Ensuite, L₂ ← L₂ - 0 × L₁, L₃ ← L₃ - 3 × L₁, Lz ← Lz + 4 × L₁
Tableau 2
| Base | x₁ | x₂ | x₃ | e₁ | e₂ | e₃ | b |
|---|---|---|---|---|---|---|---|
| x₃ | 1/2 | 1/2 | 1 | 1/2 | 0 | 0 | 2 |
| e₂ | 2 | 3 | 0 | 0 | 1 | 0 | 7 |
| e₃ | 1/2 | -1/2 | 0 | -3/2 | 0 | 1 | 1 |
| z | -1 | 0 | 0 | 2 | 0 | 0 | 8 |
x₁ entre et e₃ sort ⇒ L₃* = L₃ ← L₃ × 2. Ensuite, L₁ ← L₁ - 1/2 × L₃, L₂ ← L₂ - 2 × L₃, Lz ← Lz + L₃
Tableau 3
| Base | x₁ | x₂ | x₃ | e₁ | e₂ | e₃ | b |
|---|---|---|---|---|---|---|---|
| x₃ | 0 | 1 | 1 | 2 | 0 | -1 | 1 |
| e₂ | 0 | 5 | 0 | 6 | 1 | -4 | 3 |
| x₁ | 1 | -1 | 0 | -3 | 0 | 2 | 2 |
| z | 0 | -1 | 0 | -1 | 0 | 2 | 10 |
x₂ entre et e₂ sort ⇒ L₂* = L₂ ← L₂ / 5. Ensuite, L₁ ← L₁ - 1 × L₂, L₃ ← L₃ + 1 × L₂, Lz ← Lz + L₂
Tableau 4
| Base | x₁ | x₂ | x₃ | e₁ | e₂ | e₃ | b |
|---|---|---|---|---|---|---|---|
| x₃ | 0 | 0 | 1 | 4/5 | -1/5 | -1/5 | 2/5 |
| x₂ | 0 | 1 | 0 | 6/5 | 1/5 | -4/5 | 3/5 |
| x₁ | 1 | 0 | 0 | -9/5 | 1/5 | 6/5 | 13/5 |
| z | 0 | 0 | 0 | 1/5 | 1/5 | 6/5 | 53/5 |
SBR optimale (la ligne z est positive ou nulle) : xB = (x₃, x₂, x₁)ᵀ = (2/5, 3/5, 13/5)ᵀ xL = (e₁, e₂, e₃)ᵀ = (0, 0, 0)ᵀ z* = 53/5 = 10,6.
Note de correction : Le résultat imprimé dans la source indiquait "z = 53 = 6,105" ce qui constituait une erreur d'impression. La valeur exacte calculée est bien 53/5 soit 10,6.*
Exercice 4 - Simplexe primal
Le problème posé : Maximiser z = 2x₁ + x₂ + 3x₃ Sous les contraintes : -x₁ + 2x₂ + x₃ ≤ 6 x₁ + x₂ ≤ 24 x₁ - x₂ + 2x₃ ≤ 12 x₁, x₂, x₃ ≥ 0
Tableau 1
| Base | x₁ | x₂ | x₃ | e₁ | e₂ | e₃ | b |
|---|---|---|---|---|---|---|---|
| e₁ | -1 | 2 | 1 | 1 | 0 | 0 | 6 |
| e₂ | 1 | 1 | 0 | 0 | 1 | 0 | 24 |
| e₃ | 1 | -1 | 2 | 0 | 0 | 1 | 12 |
| z | -2 | -1 | -3 | 0 | 0 | 0 | 0 |
Tableau 2
| Base | x₁ | x₂ | x₃ | e₁ | e₂ | e₃ | b |
|---|---|---|---|---|---|---|---|
| x₃ | -1 | 2 | 1 | 1 | 0 | 0 | 6 |
| e₂ | 1 | 1 | 0 | 0 | 1 | 0 | 24 |
| e₃ | 3 | -5 | 0 | -2 | 0 | 1 | 0 |
| z | -5 | 5 | 0 | 3 | 0 | 0 | 18 |
Tableau 3
| Base | x₁ | x₂ | x₃ | e₁ | e₂ | e₃ | b |
|---|---|---|---|---|---|---|---|
| x₃ | 0 | 1/3 | 1 | 1/3 | 0 | 1/3 | 6 |
| e₂ | 0 | 8/3 | 0 | 2/3 | 1 | -1/3 | 24 |
| x₁ | 1 | -5/3 | 0 | -2/3 | 0 | 1/3 | 0 |
| z | 0 | -10/3 | 0 | -1/3 | 0 | 5/3 | 18 |
Tableau 4
| Base | x₁ | x₂ | x₃ | e₁ | e₂ | e₃ | b |
|---|---|---|---|---|---|---|---|
| x₃ | 0 | 0 | 1 | 1/4 | -1/8 | 3/8 | 3 |
| x₂ | 0 | 1 | 0 | 1/4 | 3/8 | -1/8 | 9 |
| x₁ | 1 | 0 | 0 | -1/4 | 5/8 | 1/8 | 15 |
| z | 0 | 0 | 0 | 1/2 | 5/4 | 5/4 | 48 |
SBR optimale : xB = (x₃, x₂, x₁)ᵀ = (3, 9, 15)ᵀ et z* = 48.
Méthode
Voici les étapes clés pour réussir ce type d'examen portant sur la méthode du simplexe :
- La mise en forme standard : Identifiez bien le sens de l'inégalité. Introduisez des variables d'écart (slack variables) de signe positif pour transformer des inégalités "≤" en égalités. Si l'inégalité est de type "≥", introduisez une variable d'excédent (négative) accompagnée d'une variable artificielle, puis utilisez la méthode en deux phases.
- Choix de la méthode :
- Primal : Le vecteur b est entièrement positif (b ≥ 0). L'objectif est de chasser les négatifs de la ligne z.
- Dual : Utile si la ligne z satisfait déjà la condition d'optimalité (coefficients non négatifs pour un problème de maximisation) mais que le vecteur b contient des termes négatifs.
- Deux phases : Indispensable lorsque des variables artificielles sont introduites. La première phase minimise la somme des variables artificielles pour trouver une base de départ valide, puis la deuxième phase optimise la vraie fonction objectif.
- Opérations sur les lignes (Pivots) : La rigueur arithmétique est essentielle. Ne sautez aucune étape intermédiaire et calculez toujours vos fractions de manière exacte sans les arrondir. Un tableau erroné fausse inévitablement tous les calculs suivants.
- Vérification du résultat final : Prenez toujours une minute pour injecter votre solution de base finale (les valeurs de x₁, x₂, etc.) dans la fonction objectif z de départ. Si le résultat obtenu ne correspond pas au z* de votre dernier tableau, c'est le signe immédiat qu'une erreur de calcul s'est glissée dans vos pivots.
Commentaires
Aucun commentaire pour le moment. Posez la première question.