Simplexe

dans beaucoup de problèmes réels, on peut retrouver des contraintes de type (Q) et/ou de type (R), ainsi que des problèmes où on a à minimiser au lieu de maximiser. • Dans ce chapitre, on étudiera les modifications à apporter à la méthode du simplexe pour qu’elle puisse résoudre tous ces types de programmes H. ELIDRISSI 4 Chapitre 5 : Cas général : Emploi des variables artificielles Les variables artificielles • Prenons un exemple avec m=3 contraintes explicites : la 1ère de type

universitaire : 2009 - 2010 Plan du cours  Introduction  Partie    à la recherche opérationnelle 1 : Programmation Linéaire Chapitre 1 : Introduction à la programmation linéaire Chapitre 2 : Résolution d’un programme linéaire : méthode de simplexe Chapitre 3 : Dualité et analyse de sensibilité dans la programmation linéaire Plan du cours  Partie    2 : Graphes Chapitre 1 : Notions fondamentales sur les graphes Chapitre 2 : Problème du plus court chemin Chapitre 3 : Problème de planification

opérations. 129Programmation linéaire Propriétés géométriques des solutions de base réalisables:  Méthode du simplexe: On explore seulement les sommets qui permettent d’augmenter la fonction objectif ⟹ on réduit le nombre de solution de base à explorer. 130Algorithme du simplexe  On a vu que pour résoudre un PL, il suffit de se restreindre aux solutions de bases réalisables.  Méthode du simplexe due à Dantzig (1947).  Deux phases:  Phase 1 – Initialisation: Trouver une solution de base réalisable

lin´aire e Interpr´tation g´om´trique e e e Bases et points extrˆmes e L’algorithme du simplexe Plan 9 Introduction ` la programmation lin´aire a e 10 Interpr´tation g´om´trique e e e 11 Bases et points extrˆmes e 12 L’algorithme du simplexe N. Brauner 88 Programmation lin´aire e Interpr´tation g´om´trique e e e Bases et points extrˆmes e L’algorithme du simplexe Plan 9 Introduction ` la programmation lin´aire a e 10 Interpr´tation g´om´trique

Programmer la méthode de SIMPLEXE Et Dual simplexe Et Méthode reversé min Z = cT x  ( P) :  Ax = b  x ≥ 0, A ∈ M , b ∈ IR m ( m,n )  Avec JAVA En utilisons Logiciel éclipse Remerciement. Introduction. Formulation mathématique d’un programme linéaire. terminologie du modèle. terminologie de la solution. Présentation de fonctions de notre programme. Quelques Image de l’exécution de programme. Conclusion. Notre remerciement sincère est adressé à Monsieur TAA qui a su nous apprendre

8 8 9 3 4 Forme matricielle d’un programme linéaire . . . . . . . . . . . . . . 11 . . . . . . 12 Interprétation économique d’un programme linéaire Résolution graphique . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 Méthode du simplexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.5.1 1.5.2 1.5.3 1.5.4 1.5.5 1.5.6 1.5.7 Forme standard . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 Correspondance base-sommet, changement de base, itération . . . . 19

Donner le programme optimale qui permet à l’entreprise de rembourser les dettes sur le produit chargé afin de maximiser son bénéfice. 2) Résoudre le programme linéaire par la méthode graphique. 3) Résoudre le programme linéaire par la méthode du simplexe. 4) Indiquer les contraintes saturés de l’entreprise. Interpréter le résultat . 4 TRAVAIL REALISE PAR : MR ABDELGHANI TOURAB Recherche opérationnelle Exercice 5 : On doit organiser un pont aérien pour transporter 1600 personnes et 90 tonnes

classique. Intervient fréquemment en agriculture (rations pour animaux) ou dans l’industrie (mélanges de produits pétroliers ayant des caractéristiques minimales – volatilité, indices d’octanes, etc –). ´ Programmation lineaire – p.6/49 Simplexe – Exemple Considérons le problème suivant : max M = 40x1 + 60x2 x (1a) sous les contraintes 2x1 + x2 ≤ 70 x1 + x2 ≤ 40 x1 + 3x2 ≤ 90 x1 ≥ 0 x2 ≥ 0 (1b) Première approche : résolution graphique. ´ Programmation lineaire –

x bi min c T x Sujet à Ax  Is b x, s 0 Algorithme dual du simplexe • L’algorithme dual du simplexe est une méthode itérative pour résoudre un problème de programmation linéaire sous sa forme standard min z c1 x1  c 2 x 2  c n x n Sujet à a11 x1  a12 x 2  ...  a1n x n b1 a 21 x1  a 22 x 2  ...  a 2 n x n b2 . . . . . . . . a m1 x1  a m 2 x 2  ...  a mn x n bm x j 0 j 1,2,..., n Algorithme dual du simplexe • À chaque itération nous avons une solution de base du problème

points extrˆ emes L’algorithme du simplexe Plan 6 Introduction `a la programmation lin´eaire 7 Interpr´etation g´eom´etrique 8 Bases et points extrˆemes 9 L’algorithme du simplexe N. Brauner 53 Programmation lin´ eaire Interpr´ etation g´ eom´ etrique Bases et points extrˆ emes L’algorithme du simplexe Plan 6 Introduction `a la programmation lin´eaire 7 Interpr´etation g´eom´etrique 8 Bases et points extrˆemes 9 L’algorithme du simplexe N. Brauner 54 Programmation lin´