Simplexe

` ´ Algebre lineaire Algorithme du simplexe Algorithme du simplexe ` ´ Une solution a la programmation lineaire Hugues Talbot Laboratoire A2SI 18 mars 2008 ´ ´ Resume ` ´ Algebre lineaire Algorithme du simplexe Plan ` ´ Algebre lineaire Algorithme du simplexe Formulation et forme standard Notations Recherche d’une solution optimale ´ ´ Resume ` ´ Algebre lineaire Algorithme du simplexe Matrices, inverses etc • Il est necessaire de

la gestion; mais les techniques utilis´ees s’appliquent ´egalement `a la mod´elisation en ing´eni´erie et en sciences. Certaines m´ethodes de la Recherche Op´erationnelle se d´emontrent - au niveau math´ematique - assez facilement. L’algorithme du simplexe, par exemple, repose sur des arguments ´el´ementaires de l’alg`ebre lin´eaire. D’autres m´ethodes pr´esent´ees dans ce cours, par exemple celles de la programmation dynamique, sont des cas particuliers de d´eveloppements analytiques et stochastiques

base réalisable 4 Théorème 4 Solutions optimales 5 Caractérisation des bases optimales 5 Théorème 5 Exemple classique 5 Algorithme du simplexe – Méthode des tableaux 5 Méthode 5 Exemple classique 6 Analyse du tableau final du simplexe 7 Méthode révisée du simplexe 8 Convergence & Initialisation du simplexe 8 Théorème : Convergence de l’algorithme 8 Initialisation 8 Initialisation : Méthode du gros M 9 Initialisation : Méthode des deux phases 9

Révision de l’algorithme du simplexe Forme standard • Après avoir transformé les contraintes d’inégalité en égalités, nous retrouvons le problème sous sa forme standard où certaines variables peuvent être des variables d’écart: min Sujet à z = c1x1 +c2x2 +... +cnxn a11 x1 + a12 x 2 + ... + a1n x n = b1 a 21 x1 + a 22 x 2 + ... + a 2 n x n = b 2 . . . . . . . . a m1 x1 + a m 2 x 2 + ... + a mn x n = b m x1 , x 2 , ..., x n ≥ 0 min z Sujet à a11 x1 +

. . . e 2.4 Propri´t´s g´om´triques des solutions de base r´alisables . . . . . ee e e e 2.5 Algorithme du simplexe . . . . . . . . . . . . . . . . . . . . . . . 2.5.1 L’algorithme du simplexe proprement dit : la phase 2 . . 2.5.2 M´thode des dictionnaires . . . . . . . . . . . . . . . . . . e 2.5.3 M´thode des tableaux . . . . . . . . . . . . . . . . . . . . e 2.5.4 Finitude du simplexe . . . . . . . . . . . . . . . . . . . . . 2.5.5 Initialisation et variables artificielles : la phase 1 . . .

Introduction M´ ethode graphique Simplexe Dualit´ e Introduction M´ ethode graphique Simplexe Dualit´ e Recherche op´erationnelle Tentative de d´efinition Programmation lin´eaire et recherche op´erationnelle Ensemble de m´ethodes (algorithmiques, math´ematiques, mod´elisation) afin de prendre des d´ecisions optimales ou proches de l’optimum dans des probl`emes complexes, qui traitent de la maximisation d’un profit ou la minimisation d’un coˆ ut. Ioan Todinca • Comment aller le plus vite

Caractérisation d’une base réalisable 5 Théorème 5 Solutions optimales 5 Caractérisation des bases optimales 5 Théorème 5 Exemple classique 6 Algorithme du simplexe – Méthode des tableaux 6 Méthode 6 Exemple classique 7 Analyse du tableau final du simplexe 8 Méthode révisée du simplexe 9 Convergence & Initialisation du simplexe 10 Théorème : Convergence de l’algorithme 10 Initialisation 10 Initialisation : Méthode du gros M 10 Initialisation : Méthode des deux phases 10 Perturbation

Introduction M´thode graphique e Simplexe Dualit´ e Introduction M´thode graphique e Simplexe Dualit´ e Recherche op´rationnelle e Tentative de d´finition e Programmation lin´aire et recherche e op´rationnelle e Ensemble de m´thodes (algorithmiques, math´matiques, e e mod´lisation) afin de prendre des d´cisions optimales ou proches e e de l’optimum dans des probl`mes complexes, qui traitent de la e maximisation d’un profit ou la minimisation d’un coˆt

 problème  du  plus  courts  chemins.     •  Programma0on  linéaire  :  modélisa0on  des   problèmes,  de  la  resolu0on  graphique  au   algorithme  du  simplexe.  Problème  de  la  dualité  et   méthode  dual-­‐simplexe.     •  Modèle  de  Markov  :  Simula0on,  illustra0ons  et   applica0ons.   Objec0fs  généraux   •  L’objec0f  premier  de  ce  cours  est  d’acqurir

mais les e e techniques utilis´es s’appliquent ´galement ` la mod´lisation en ing´ni´rie et en e e a e e e sciences. Certaines m´thodes de la Recherche Op´rationnelle se d´montrent - au niveau e e e math´matique - assez facilement. L’algorithme du simplexe, par exemple, repose e ee e e sur des arguments ´l´mentaires de l’alg`bre lin´aire. D’autres m´thodes pr´sent´es dans ce cours, par exemple celles de la programmation e e e dynamique, sont des cas particuliers de d´veloppements analytiques et stochastiques