24 0 558KB
Résolution par la méthode des tableaux du simplexe (Exemple complet) Abdelaziz CHETOUANI
Résolution par la méthode des tableaux du simplexe (Exemple complet)
Abdelaziz CHETOUANI École Nationale de Commerce et de Gestion - Oujda Département de commerce Recherche opérationnelle
23 novembre 2020
1/8
Résolution par la méthode des tableaux du simplexe (Exemple complet)
Application : Problème de maximisation avec trois variables La société BETA fabrique trois modèles de meubles : classiques, rustiques, modernes.
Abdelaziz CHETOUANI
La société BETA souhaite déterminer un programme de production optimal. 2/8
Résolution par la méthode des tableaux du simplexe (Exemple complet) Abdelaziz CHETOUANI
3/8
Forme canonique du programme
• Variables
Résolution par la méthode des tableaux du simplexe (Exemple complet) Abdelaziz CHETOUANI
3/8
Forme canonique du programme
• Variables • x :
nombre de modèles classiques à produire
Résolution par la méthode des tableaux du simplexe (Exemple complet) Abdelaziz CHETOUANI
3/8
Forme canonique du programme
• Variables • x : • y :
nombre de modèles classiques à produire nombre de modèles rustiques à produire
Résolution par la méthode des tableaux du simplexe (Exemple complet) Abdelaziz CHETOUANI
3/8
Forme canonique du programme
• Variables • x : nombre de modèles classiques à produire • y : nombre de modèles rustiques à produire • z : nombre de modèles modernes à produire
Résolution par la méthode des tableaux du simplexe (Exemple complet) Abdelaziz CHETOUANI
Forme canonique du programme
• Variables • x : nombre de modèles classiques à produire • y : nombre de modèles rustiques à produire • z : nombre de modèles modernes à produire • Contraintes x ≥ 0, y ≥ 0, z ≥ 0 5x + 8y + 5z ≤ 900 x + 2y + 3z ≤ 516 2x + 2y ≤ 200 F (x, y , z) = 1000x + 960y + 1200z
Objectif : Maximiser F (x, y , z)
3/8
Résolution par la méthode des tableaux du simplexe (Exemple complet) Abdelaziz CHETOUANI
Forme canonique du programme
• Variables • x : nombre de modèles classiques à produire • y : nombre de modèles rustiques à produire • z : nombre de modèles modernes à produire • Contraintes x ≥ 0, y ≥ 0, z ≥ 0 5x + 8y + 5z ≤ 900 x + 2y + 3z ≤ 516 2x + 2y ≤ 200 F (x, y , z) = 1000x + 960y + 1200z
Objectif : Maximiser F (x, y , z)
• Forme standard x ≥ 0, y ≥ 0, z ≥ 0, e1 ≥ 0, e2 ≥ 0, e3 ≥ 0 5x + 8y + 5z + e1 = 900 x + 2y + 3z + e2 = 516 2x + 2y + e3 = 200 F (x, y , z) = 1000x + 960y + 1200z
3/8
Résolution par la méthode des tableaux du simplexe (Exemple complet) Abdelaziz CHETOUANI
4/8
Étape 1 : détermination d'une solution initiale La solution initiale ou solution de base consiste à annuler les variables de décision ( variables hors base) et donc les variables d'écarts (variables de base) prennent les valeurs maximales. x = y = z = 0, e1 = 900; e2 = 516 et e3 = 200. Il correspondent à une production est nulle (x = 0; y = 0; z = 0), la valeur de la fonction économique est donc nulle. La capacité disponible des facteurs de production est intacte : e1 = 900; e2 = 516 et e3 = 200. Premier tableau
Résolution par la méthode des tableaux du simplexe (Exemple complet) Abdelaziz CHETOUANI
5/8
Étape 2 : Critère de la variable sortante On calcule les rapports : second membre coef. de la col. de la var. entrante >0 (ici min(900/5; 519/3; 100/0) = 519/3 = 172) que l'on indiquera dans une colonne θ ⇒ e2 variable sortante.
Résolution par la méthode des tableaux du simplexe (Exemple complet) Abdelaziz CHETOUANI
6/8
On obtient le deuxième tableau
Résolution par la méthode des tableaux du simplexe (Exemple complet) Abdelaziz CHETOUANI
7/8
Résolution par la méthode des tableaux du simplexe (Exemple complet) Abdelaziz CHETOUANI
8/8
Il s'agit de la solution optimale : tous les coecients de la dernière ligne sont négatifs ou nuls. • Il faut donc fabriquer 12 meubles classiques, 0 rustiques et 168 modernes.
Résolution par la méthode des tableaux du simplexe (Exemple complet) Abdelaziz CHETOUANI
8/8
Il s'agit de la solution optimale : tous les coecients de la dernière ligne sont négatifs ou nuls. • Il faut donc fabriquer 12 meubles classiques, 0 rustiques et 168 modernes. • La fonction économique a pour valeur : 213 600.
Résolution par la méthode des tableaux du simplexe (Exemple complet) Abdelaziz CHETOUANI
8/8
Il s'agit de la solution optimale : tous les coecients de la dernière ligne sont négatifs ou nuls. • Il faut donc fabriquer 12 meubles classiques, 0 rustiques et 168 modernes. • La fonction économique a pour valeur : 213 600. • e1 = e2 = 0, les deux premières contraintes sont saturées.
Résolution par la méthode des tableaux du simplexe (Exemple complet) Abdelaziz CHETOUANI
8/8
Il s'agit de la solution optimale : tous les coecients de la dernière ligne sont négatifs ou nuls. • Il faut donc fabriquer 12 meubles classiques, 0 rustiques et 168 modernes. • La fonction économique a pour valeur : 213 600. • e1 = e2 = 0, les deux premières contraintes sont saturées. • e3 = 176, il reste 176 unités du centre de nition non exploitées.