Simplexe

Prf. Adil Chergui 2012/2013 I. II. III. IV. V. VI. Introduction à la recherche opérationnelle Modélisation et formulation d’un programme linéaire Résolution graphique d’un PL La méthode simplexe Problèmes de minimisation et problèmes irréguliers Dualité  Définition la recherche opérationnelle (RO) peut être définie comme un ensemble de méthodes d’analyse scientifique (mathématique et informatique) des phénomènes d’organisation qui traite de la maximisation d’un profit, d’une

Approximation d’un problème elliptique par la méthode des volumes finis Maillage d’un domaine Définition Soit Ω un ouvert borné polyédrique de ℝ associé à l'équation aux dérivées partielles qui ( ) nous intéresse. On appelle volume de contrôle, les d-simplexes d , vérifiant :    ∀ = 1… ; est un ouvert de Ω ∩ = ,∀ ≠ ∪ =Ω On définit =( ) l’ensemble des volumes de contrôle. Soit Δ l’ensemble des p-faces faces pris sur chaque volume de contrôle et soit alors : ∈ Δ. On a soit = ∩ , ≠ , alors est

linéaires . . . . . . . . . . . . . . . . 3.3 Forme standard et forme canonique d’un programme linéaire 3.4 Résolution de programmes linéaires . . . . . . . . . . . . . 3.4.1 Résolution graphique . . . . . . . . . . . . . . . . . 3.4.2 La méthode du simplexe . . . . . . . . . . . . . . . 3.4.3 La méthode des deux phases . . . . . . . . . . . . . 3.4.4 Cas particuliers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

de conservation de flot est dénoté matrice d’incidence sommets-arcs: ligne i ↔ sommet i colonne (i, j) ↔ arc (i, j) ligne i ligne j • La matrice d’incidence sommets-arcs jouit de la propriété d’unimodularité qui fait que l’algorithme du simplexe génère une solution entière pour le problème (FMC) lorsque lij, dij et v sont des entiers. • Exemple de matrice d’incidence pour le réseau 2 1 3 4 1 x12 x13 x23 x24 x32 x34  1 1 0 0 0 0   2  1 0 1 1  1 0  1 1 3  0 1 1 0 

75 francs | 5 heures | 3 heures | Mécanicien de niveau 1 | 90 francs | 3 heures | 3 heures | 1- Déterminer graphiquement la composition de l’équipe qui minimise le coût hebdomadaire du travail. 2- Donner la solution par la méthode du simplexe.

tableau suivant : | P1 | P2 | Atelier 1 | 3 | 1 | Atelier 2 | 2 | 4 | 1. Formuler le problème de l’entreprise qui cherche à maximiser son chiffre d’affaires. 2. Donner la solution optimale du problème primale par une résolution simplexe. 3. donner l’interprétation économique de la solution optimale.

l'algorithme dual du simplexe. Il s’agit d’ajouter des contraintes afin d'amputer des "morceaux" au polyèdre des solutions réalisables du problème continu, jusqu'à ce que la solution optimale de ce dernier satisfasse les contraintes d'intégralité. Le "morceau" à amputer devra évidemment contenir la solution optimale du problème continu et il faut aussi s'assurer qu'aucune solution entière n'est amputée. Après l'ajout d'une contrainte, on réoptimise en utilisant le dual du simplexe. On se rapproche ainsi

présentés les modèles classiques vus dans le cadre du cours, qui font intervenir des variables continues, i.e. qui peuvent prendre n’importe quelle valeur à l’intérieur d’un intervalle donné. Pour ces modèles linéaires, l’utilisation de l’algorithme du simplexe permet une résolution très efficace, ce qui en fait un outil très utilisé dans l’industrie et le monde des affaires. Les modèles présentés ici ne forment, en aucun cas, une énumération exhaustive des modèles linéaires en variables continues. Il s’agit

Modélisation et résolution de pbs en RO 1 2013-2014 Master ID Solveurs et Modeleurs Solveurs : Logiciels de résolution de Programme Mathématique (excel, CPLEX, GLPK, lindo, Xpress, gurobi, coin-OR…) – – PL : méthode révisée du simplexe PLNE : méthode par séparation et évaluation Modeleurs : Langage pour écrire, intégrer, résoudre et afficher un PM : GAMS, AMPL, OPL… 2 2013-2014 Master ID Cplex Optimization Studio Offre un environnement de développement intégré

réparation périphérique est de 500€, le directeur se demande combien d’interventions de chaque type doivent être effectuées chaque jour. 1) Ecrire le programme 2) Réécrire le programme sous forme standard 3) Ecrire le premier tableau du simplexe 4) Combien d’interventions de chaque type faut-il effectuer ? Exercice 2 Un atelier de couture utilise un nouveau procédé pour fabriquer 3 types de vêtements : des chemises (X1), des pantalons (X2) et des bermudas (X3). Compte tenu de la