Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Exercice 1 : Un entrepreneur a besoin de deux matières premières A et B pour fa

Exercice 1 : Un entrepreneur a besoin de deux matières premières A et B pour fabriquer un produit, il lui faut au moins 1800 tonnes de A et 800 tonnes de B. il ne peut acheter que les mélanges X et Y. le produit X contient 80% de A et 20% de B et coûte 1000 DH la tonne. Le produit Y contient 60% de A et 40% de B et coûte 800 DH la tonne. Par ailleurs, il ne peut pas acheter plus de 4400 tonnes de Y et 6400 tonnes de X. TAF : 1. Formuler le PL qui permet de déterminer les quantités de X et Y que l’entrepreneur doit acheter pour répondre à ses besoins au moindre coût. 2. Résoudre ce PL par l’algorithme du simplexe. Corrigé : 1. Formulation du PL : Etape 1 : Variables de décision : 2 variables réelles positives x₁ : quantité en tonnes du mélange X à acheter x₂ : quantité en tonnes du mélange Y à acheter Etape 2 : Objectif Min Z : 1000 x₁ + 800 x₂ (Coût d’achat) Etape 3 : Contraintes Contraintes de besoin de MP A : 0,8 x₁+ 0,6 x₂ ≥ 1800 B : 0,2 x₁+ 0,4 x₂ ≥ 800 Contraintes d’achat : X : x₁ ≤ 6400 Y : x₂ ≤ 4400 Contraintes naturelles x₁, x₂ ꞓ ℝ* ➢ Donc le PL à résoudre : Min Z = 1000 x₁ + 800 x₂ SC : 4x₁+ 3x₂ ≥ 9000 x₁+ 2x₂ ≥ 4000 x₁ ≤ 6400 x₂ ≤ 4400 x₁, x₂ ꞓ ℝ 4x₁+ 3x₂ = 9000 (0 ; 3000) ; (2250 ;0) x₁+ 2x₂ = 4000 (0 ; 2000) ; (4000 ;0) x₁ = 6400 (0 ;6400) x₂ = 4400 (4400 ;0) Graphique : 2. Résoudre le PL : ➢ Pour résoudre ce PL, on utilise la méthode du simplexe La fonction devient : Min Z =1000x₁ + 800 x₂ SC : 4x₁+ 3x₂ - e₁ = 9000 x₁+ 2x₂ - e₂ = 4000 x₁ + e₃ = 6400 x₂ + e₄ = 4400 x₁, x₂, e₁ e₂, e₃, e₄ ≥ 0 ➢ Détermination de la base initiale : L’écriture matricielle du système : x₁ x₂ e₁ e₂ e₃ e₄ = Absence de la matrice d’identité de taille 4 donc absence d’une base initiale évidente Donc, on va appliquer la méthode de 2 phases : 1ère phase : Résoudre le PL* auxiliaire suivant L’objectif est de minimiser la somme des variables artificielles. Min Z* = a₁ + a₂ SC : 4x₁+ 3x₂ - e₁ + a₁ = 9000 x₁+ 2x₂ - e₂ + a₂ = 4000 x₁ + e₃ = 6400 x₂ + e₄ = 4400 xᵢ, eᵢ, aᵢ ≥ 0 ➢ Recherche de la base initiale du PL* : = 4 3 -1 0 0 0 1 2 0 -1 0 0 1 0 0 0 1 0 0 1 0 0 1 1 x₁ x₂ e₁ e₂ e₃ e₄ 9000 4000 6400 4400 4 3 -1 0 1 0 0 0 1 2 0 -1 0 1 0 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1 x₁ x₂ e₁ e₂ a₁ a₂ e₃ e₄ 9000 4000 6400 4400 Donc la base initiale évidente du PL* est : (a₁, a₂, e₃, e₄) Tableau initial du PL* : T₀* x₁↓ x₂ e₁ e₂ e₃ e₄ a₁ a₂ C Rapport a₁← 4 3 -1 0 0 0 1 0 9000 2200 a₂ 1 2 0 -1 0 0 0 1 4000 4000 e₃ 1 0 0 0 1 0 0 0 6400 6400 e₄ 0 1 0 0 0 1 0 0 4400 +∞ Z -5 -5 1 1 0 0 0 0 -13000 On a Z = a₁ + a₂ = f (x₁, x₂, e₁, e₂) D’après T₀, on a : a₁ = 9000 - 4 x₁ -3 x₂ + e₁ a₂ = 4000 - x₁ - 2 x₂ + e₂ D’où Z = 1300 - 5 x₁ - 5 x₂ + e₁ + e₂ Le critère d’optimalité d’un problème d’une minimalisation est que toutes les variables hors base (VHB) doivent avoir des contributions positives ou nulles. T₀* n’est pas optimal car les VHB ont des contributions négatives. 1ère itération : T₀* T₁* VE : x₁ VS : a₁ Pivot : 4 T₁* x₁ x₂↓ e₁ e₂ e₃ e₄ a₁ a₂ C Rapport x₁ 1 3 / 4 -1 / 4 0 0 0 1 / 4 0 2250 3000 a₂ ← 0 5 / 4 1 / 4 -1 0 0 -1 / 4 1 1750 1400 e₃ 0 -3 / 4 1 / 4 0 1 0 -1 / 4 0 4150 - e₄ 0 1 0 0 0 1 0 0 4400 4400 Z 0 -5 / 4 -1 / 4 1 0 0 5 / 4 0 -1750 T₁* n’est pas optimal car Contr (x₂) = -5 / 4 ≤ 0 Contr (e₁) = -1 / 4 ≤ 0 2ère itération : T₁* T₂* VE : x₂ VS : a₂ Pivot : 5/4 T₁* x₁ x₂ e₁ e₂ e₃ e₄ a₁ a₂ C Rapport x₁ 1 0 -2/5 3/5 0 0 2/5 -3/5 1200 x₂ 0 1 1/5 -4/5 0 0 -1/5 4/5 1400 e₃ 0 0 2/5 -3/5 1 0 -2/5 3/5 5200 e₄ 0 0 -1/5 4/5 0 1 1/5 -4/5 3000 Z 0 0 0 0 0 0 1 1 0 T₂*est optimal car les contributions des variables hors base VHB sont positives. Donc : Fin de la première phase 2ème phase : Le tableau initial de la 2ème phase c’est le dernier tableau de la 1ère phase sans les colonnes a₁ et a₂. L’objectif de la 2ème phase est : Min Z = 1000 x₁ + 800 x₂ T° x₁ x₂ e₁ e₂ e₃ e₄ C Rapport x₁ 1 0 -2/5 3/5 0 0 1200 x₂ 0 1 1/5 -4/5 0 0 1400 e₃ 0 0 2/5 -3/5 1 0 5200 e₄ 0 0 -1/5 4/5 0 1 3000 Z 0 0 240 40 0 0 2320000 On a Z = 1000 x₁ + 800 x₂= f (e₁, e₂) D’après T°, on a : x₁ = 1200 + 2/5 e₁ - 3/5 e₂ x₂ = 1400 - 1/5 e₁ + 4/5 e₂ Donc : 1000 x₁ = 1200000 + 400 e₁ - 600 e₂ 800 x₂ = 1120000 – 160 e₁ + 640 e₂ D’où : Z = 2320000 + 240 e₁ + 40 e₂ T° est optimal, car les contributions des VHB sont positives. Puisque les contributions des VHB sont positives, donc la solution optimale du PL est unique La solution optimale : x₁ = 1200 t x₂ = 1400 t e₁ = 0 e₂ = 0 e₃ = 5200 t e₄ = 3000 t Z = 2320000 Dhs Les deux contraintes de besoin sont saturées : (e₁ = e₂ = 0) Les deux contraintes du marché e₃ et e₄ ne sont pas saturées L’entrepreneur doit acheter 1200 t de X et 1400 t de Y Le coût d’achat minimum est 2320000 Dhs Exercice 2 : Max Z = 3x₁ - 5x₂ SC : 4x₁ + 5x₂ ≥ 3 6x₁ - 6x₂ = 7 x₁ + 8x₂ ≤ 20 x₁≥ 0 ; x₂≥0 TAF : Résoudre par la méthode graphique et l’algorithme du simplexe ce PL Corrigé : 1. Résolution graphique : En vert, les points dont on trouve la solution. En rouge, les points qui ne satisfont pas les contraintes 2. Résolution par la méthode de simplexe : On a : Max Z = 3x₁ - 5x₂ SC : 4x₁ + 5x₂- e₁= 3 6x₁ - 6x₂ = 7 x₁ + 8x₂ + e₂ = 20 x₁≥ 0 ; x₂≥0 ➢ Détermination de la base initiale : L’écriture matricielle du système : Absence de base initiale évidente donc il faut appliquer la méthode des 2 phases 1ère phase : Résoudre le PL* auxiliaire Min Z = a₁ + a₂ SC : 4x₁ + 5x₂- e₁ + a₁ = 3 6x₁ - 6x₂ + a₂ = 7 x₁ + 8x₂ + e₂ = 20 xᵢ, eᵢ, aᵢ ≥ 0 ➢ Recherche de la base initiale : = T₀* x₁↓ x₂ e₁ e₂ a₁ a₂ C Rapport a₁ ← 4 5 -1 0 1 0 3 3/4 a₂ 6 -6 0 0 0 1 7 7/6 4 5 -1 0 6 -6 0 0 1 8 0 1 0 1 0 0 x₁ x₂ e₁ e₂ 3 7 20 4 5 -1 1 0 0 6 -6 0 0 1 0 1 8 0 0 0 1 0 1 0 0 x₁ x₂ e₁ a₁ a₂ e₂ 3 7 20 e₂ 1 8 0 1 0 0 20 20 Z* -10 1 1 0 0 0 -10 D’après Z*= a₁+ a₂ Selon T°* : a₁ = -4x₁ - 5x₂ +e₁ + 3 a₂ = -6x₁ + 6x₂ + 7 Z*= 10 -10x₁ +x₂ +e₁ T°*n’est pas optimal car on a la variable x₁ a uploads/Voyage/ exercice-deux-phases-et-ordonancement-corrige.pdf