Bibliographie & annexes
Présentation
En anglais
RÉSUMÉ
Cet article expose les concepts fondamentaux de la programmation linéaire qui consiste à minimiser ou à maximiser une fonction objectif linéaire avec des contraintes d'inégalités et d'égalités linéaires sur les variables du système. Les propriétés fondamentales de la programmation linéaire sont établies et la méthode de résolution du simplexe est présentée. Un exemple de problème de production sert de référence pour illustrer les différentes propriétés, concepts et méthodes développées. Un code MATLAB de la méthode du simplexe est fourni en annexe et une liste de quelques solveurs de programmation linéaire est proposée avec un exemple d'utilisation. La sensibilité aux données de la solution d'un programme linéaire et la notion de dualité en programmation linéaire sont introduites.
Lire cet article issu d'une ressource documentaire complète, actualisée et validée par des comités scientifiques.
Lire l’articleABSTRACT
This paper presents the basic concepts of linear programming, which consists in minimizing or maximizing a linear objective function with linear inequality or equality constraints on the variables of the system. The properties of solutions of a linear programming problem are established and the simplex method for solving a linear programming problem is presented in detail. Throughout the paper, a simple example of a production problem serves as a reference to illustrate the various concepts and methods developed. A MATLAB code of the simplex method is supplied, and some linear programming solvers are listed with an example of use. The data sensitivity of the solution of a linear program is analyzed, and the concept of linear programming duality is introduced.
Auteur(s)
-
Jean-François SCHEID : Maître de conférences en mathématiques appliquées - Institut Elie Cartan de Lorraine & TELECOM Nancy - Université de Lorraine, Nancy, France
INTRODUCTION
De nombreux phénomènes économiques et industriels peuvent se modéliser par des systèmes mathématiques d’inégalités et d’égalités linéaires conduisant à des problèmes d’optimisation linéaire. Dans ces problèmes d’optimisation linéaire, on cherche à minimiser ou maximiser une fonction linéaire sous des contraintes linéaires portant sur les variables du problème. On parle souvent de programmation linéaire (ou encore de programme linéaire), le terme de programmation faisant référence à l’idée d’organisation et de planification lié à la nature des phénomènes modélisés. Ce terme a été introduit pendant la Seconde Guerre mondiale et systématiquement utilisé à partir de 1947 lorsque G. Dantzig inventa la méthode du simplexe pour résoudre les problèmes de programmation linéaire. Les applications industrielles de la programmation linéaire sont très présentes par exemple dans l’industrie pétrolière (pour l’extraction, le raffinage et la distribution du pétrole), dans l’agroalimentaire (composition optimale des ingrédients de plats cuisinés, etc.), industrie du fer et de l’acier (composition optimale des aciers), l’industrie du papier (problèmes de découpe), les transports (plan de vols d’avions, minimisation des coûts de transport…) et les réseaux (optimisation des réseaux de communication).
Cet article présente les propriétés et les concepts fondamentaux de la programmation linéaire puis expose l’algorithme du simplexe pour résoudre un programme linéaire. L’algorithme du simplexe est mis en œuvre selon deux méthodes, la méthode des dictionnaires et la méthode des tableaux. La première méthode permet de bien comprendre le déroulement du simplexe alors que la méthode des tableaux est plus algébrique et elle conduit à la mise en œuvre effective de l’algorithme du simplexe. Un code MATLAB basé sur la méthode des tableaux est proposé en annexe. Une application de la méthode du simplexe à l’analyse de sensibilité d’un programme linéaire est également présentée ainsi qu’une introduction à la dualité en programmation linéaire.
L'expertise technique et scientifique de référence
MOTS-CLÉS
KEYWORDS
linear programming | simplex method | MATLAB
DOI (Digital Object Identifier)
Cet article fait partie de l’offre
Mathématiques
(166 articles en ce moment)
Cette offre vous donne accès à :
Une base complète d’articles
Actualisée et enrichie d’articles validés par nos comités scientifiques
Des services
Un ensemble d'outils exclusifs en complément des ressources
Un Parcours Pratique
Opérationnel et didactique, pour garantir l'acquisition des compétences transverses
Doc & Quiz
Des articles interactifs avec des quiz, pour une lecture constructive
Présentation
Modélisation et résolution graphique
En anglais
12. Glossaire – Définitions
Coûts réduits ; reduced costs
Coefficients des variables hors-base dans la fonction objectif exprimée uniquement en fonction des variables hors-base.
Dictionnaire ; dictionary
Dans la méthode du simplexe, les contraintes sous forme standard sont écrites en exprimant les variables de base en fonction des variables hors-base. Un dictionnaire est constitué de ces relations ainsi que de la fonction objectif exprimée également avec les variables hors-base.
Forme canonique pure ; canonical form
Dans un programme linéaire sous forme canonique pure, les contraintes apparaissent sous forme d'inégalités linéaires
.
Forme standard ; standard form
Dans un programme linéaire sous forme standard, les contraintes apparaissent sous forme d'égalités linéaires A x = b.
Forme standard simpliciale ; simplicial standard form
Programme linéaire sous forme standard dans laquelle les coefficients des variables de base sont tous égaux à 1.
Méthode du simplexe ; simplex method
Méthode itérative de résolution d'un programme linéaire. Seuls les sommets du polyèdre des contraintes qui permettent d'augmenter la fonction objectif (dans le cas d'une maximisation) sont explorés.
Méthode des tableaux ; simplex tableaus method
Mise en œuvre de la méthode du simplexe dans laquelle on maintient la forme simpliciale de la matrice des contraintes d'une itération à l'autre. On utilise des formules de mise à jour de l'inverse de la matrice de base.
Polyèdre des contraintes ; constraints polyhedron
L'ensemble des solutions réalisables forme un polyèdre convexe appelé polyèdre des contraintes.
Programme linéaire ; linear programming
Recherche d'un minimum ou d'un maximum d'une fonction objectif linéaire par rapports à des variables qui sont soumises à des contraintes d'inégalités ou d'égalités linéaires.
Solution de base ; basic solution
Vecteur dont les variables hors-base sont nulles.
Solution réalisable ; feasible solution
Vecteur qui vérifie toutes les contraintes d'un programme linéaire.
Variables de...
L'expertise technique et scientifique de référence
Cet article fait partie de l’offre
Mathématiques
(166 articles en ce moment)
Cette offre vous donne accès à :
Une base complète d’articles
Actualisée et enrichie d’articles validés par nos comités scientifiques
Des services
Un ensemble d'outils exclusifs en complément des ressources
Un Parcours Pratique
Opérationnel et didactique, pour garantir l'acquisition des compétences transverses
Doc & Quiz
Des articles interactifs avec des quiz, pour une lecture constructive
Glossaire – Définitions
BIBLIOGRAPHIE
-
(1) - BILLIONNET (A.) - Optimisation discrète – De la modélisation à la résolution par des logiciels de programmation mathématique. - Dunod (2007).
-
(2) - BREZINSKI (C.) - Initiation à la programmation linéaire et à l'algorithme du simplexe. - Ellipse, Paris (2006).
-
(3) - CHVATAL (V.) - Linear programming. - W. H. Freeman (1983).
-
(4) - DANTZIG (G.), THAPA (M.) - Linear Programming 1 : Introduction. - Springer Series in Operations Research and Financial Engineering (2013).
-
(5) - DANTZIG (G.), THAPA (M.) - Linear Programming 2 : Theory and Extensions. - Springer Series in Operations Research and Financial Engineering (2013).
-
(6) - HECHE (J.-F.), LIEBLING (T.), DE WERRA (D.) - Recherche...
DANS NOS BASES DOCUMENTAIRES
ANNEXES
GLPK – Gnu Linear Programming Kit (version pour Linux) [Logiciel]
LPSOLVE, (version multi-plateforme sous licence LGPL)
IBM ILOG CPLEX Optimization Studio (version multi-plateforme)
MATLAB – Optimization toolbox
CMPL – <Coliop|Coin> Mathematical Programming Language
HAUT DE PAGE
COIN-OR : COmputational INfrastructure for Operations Research
ROADEF : Société française de Recherche Opérationnelle et d'Aide à la Décision
http://www.roadef.org/content/index.htm
Portail ENSTA de la Recherche Opérationnelle
http://perso.ensta-paristech.fr/~diam/ro/
AFPC : Association Française pour la Programmation par Contraintes
HAUT DE PAGE
L'expertise technique et scientifique de référence
Cet article fait partie de l’offre
Mathématiques
(166 articles en ce moment)
Cette offre vous donne accès à :
Une base complète d’articles
Actualisée et enrichie d’articles validés par nos comités scientifiques
Des services
Un ensemble d'outils exclusifs en complément des ressources
Un Parcours Pratique
Opérationnel et didactique, pour garantir l'acquisition des compétences transverses
Doc & Quiz
Des articles interactifs avec des quiz, pour une lecture constructive
