Simplexe

raffinage se sont développées dans les années 50 avec le développement de l’algorithme du simplexe par Dantzig (mathématicien américain d’origine russe, fondateur du « Centre de Recherche Opérationnel », élu membre de l’Académie nationale des sciences des Etats-Unis en 1977) en 1949. D’autres algorithmes seront développés plus tard comme l’algorithme de Katchian. Cependant on constate que l’algorithme du simplexe demeure « beaucoup plus rapide »[2] jusqu’à maintenant. (Même si il n’est pas parfait d’un

                                  (1)   0,5 x1 + x2 + e2  = 2500                                  (2)   0,04 x1 + 0,1 x2 + e3  = 40                                (3)   x1, x2, e1, e2, e3 ≥ 0                                            (4) 3.6. Tableau du simplexe   Ce tableau est utilisé pour avoir une meilleure visualisation du problème et le résoudre de manière bien plus rapide que l’énumération de toutes les solutions possibles.   |Cj |  | 

valeur 35w pour la solution de base e x = y = z = 0, e1 = e2 = 0, e3 = 10, η1 = 15, η2 = 20. 27 Chapitre II. M´thode de simplexe e 28 M´thode de simplexe e On sait la solution, si elle existe, se trouve au moins sur un sommet du domaine des solutions r´alisables, la recherche de la solution optimale s’effectue uniquement sur ces sommets. e L’algorithme du simplexe examine comme premi`re solution un des sommets (en g´n´ral e e e l’origine), qui constitue la solution de base de l’algorithme

ETUDES DE CAS : PROGRAMMATION LINEAIRE –ALGORITHME DU SIMPLEXE SERIE N° 2 Outils d’aide à la décision Master 1 Professeur : M DIAWARA Problème 1 On considère les deux syst`emes d’´equations lin´eaires donn´es ci-dessous : 2x1 + 2x2 x1 + 2x2 + x1 + x2 − 3x3 = 4 x3 = 4 − 2x3 = 2 x1 + x2 + 2x3 = −2 x1 + x2 + 3x3 = 1 x1 + 2x2 = 3 D´eterminer la solution de chaque syst`eme. Problème 2 Soit le système d’inéquations suivant : 4x1 - 5x2 ≤ 21 (1) 2x1 + 3 x2 ≤ 30 (2) 3x1 -

académique 2002-2003 Yves CRAMA Méthode du Simplexe S1) Ecrivez le problème PL suivant sous forme standard avec des M.d.D. non négatifs: Max z = 2x1 + 3 x2 + 5 x3 [pic] Formulez son dual. S2) Considérons l’ensemble de contraintes suivant: x1 + 7 x2 + 3x3 + 7 x4 ( 46 3 x1 - x2 + x3 + 2 x4 ( 8 2 x1 + 3 x2 - x3 + x4 ( 10 Résolvez par la méthode du simplexe le problème obtenu lorsque la fonction objectif

la production et ce dans le cadre d’une application informatique basée sur une méthode de prise de décision en amont appelée Simplexe s’inscrivant à son tour parmi les outils de la programmation linéaire. On va d’abord présenter la méthode du Simplexe dans le cadre de la programmation linéaire ensuite on va donner l’organigramme permettant de passer de la méthode du Simplexe manuelle à l’informatique puis on terminera avec la description de l’application et des outils utilisés dans son élaboration

heures Contribution au bénéfice 100 F/unité 120 F/unité Comment optimiser le bénéfice de l’entreprise ? Réponse : en fabriquant 1000 unités du modèle Elec-100 et 300 unités du modèle Elec-200. 2 Présentation de l’algorithme du simplexe. L’exemple 2 est modélisable par le système d’équations linéaires suivant : . x est le nombre d’unités Elec-100 ; y est le nombre d’unités Elec-200 ; f est le bénéfice ; f est la fonction économique à maximiser ; a est le nombre d’heures inutilisées

Valeur 18 9 ) du nouveau tableau de simplexe : 1 -1/2 3/2 1 0 1 1 0 1 Page 4/7 0 -1/2 1/2 0 0 0 1/2 0 -1/2 Valeur 22 9 13 2011/2012 Correction du Contrôle Final en Programmation Linéaire Pour obtenir la 3ème ligne (celle de Ancienne Ligne de 4 1 0 NLP ) Nouvelle Ligne de Min cj Base Coeff var 0 0 0 zj cj - zj Semestre S5 / Option: Économie ) du nouveau tableau de simplexe : 1 -1/2 3 0 0 0 0 0 0

. . 11 1.2.3 Forme matricielle d’un programme linéaire . . . . . . . . . . . . . . 13 1.3 Interprétation économique d’un programme linéaire 1.4 Résolution graphique . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 1.5 Méthode du simplexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 1.6 . . . . . . 14 1.5.1 Forme standard . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 1.5.2 Correspondance base-sommet, changement de base, itération . . . . 21 1.5

www.almohandiss.com Devoir à la maison corrigé Méthode simplexe Exercice 1 A) Résoudre avec la méthode du simplexe primal le problème suivant : Max z  2 x1  x 2  3x 3 s.c.  x  2 x  x  6 1 2 3   x1  x 2  24  ( P1 )   x1  x 2  x 3  9  x1 , x 2 , x3  0    Réponse : #1 x1 x2 x3 e1 e2 e3 e1 -1 2 1 1 0 0 e2 1 1 0 0 1 0 e3 1 -1 1 0 0 1 z -2 -1 -3 0 0 0 x3 entre et e1 sort  Li*=L1← L1 / 1. Ensuite, L2← L2 - 0 × L1, L3← L3 - 1 × L1, Lz← Lz + 3 × L1 #2 x1 x2 x3 e1 e2 e3 -1