Bibliographie & annexes
Présentation
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’articleAuteur(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
DOI (Digital Object Identifier)
Cet article fait partie de l’offre
Mathématiques
(170 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
Des modules pratiques
Opérationnels et didactiques, pour garantir l'acquisition des compétences transverses
Doc & Quiz
Des articles interactifs avec des quiz, pour une lecture constructive
Présentation
Dualité8. Analyse post-optimale
L'analyse post-optimale ou analyse de sensibilité permet de déterminer les intervalles de variations des données pour lesquels la base optimale B* n'est pas modifiée et reste toujours optimale. Cette analyse permet de déterminer la sensibilité d'un programme linéaire par rapport aux données. La problématique de cette section est de savoir si une faible variation des données entraîne ou non un changement important de la solution optimale.
On considère un programme linéaire sous la forme standard (5) qui admet une base optimale B*, c'est-à-dire un programme linéaire pour lequel l'algorithme du simplexe se termine normalement. À une permutation près des colonnes (cf. (8)), la matrice A se décompose en
où AB * est inversible.
8.1 Analyse de sensibilité de l'objectif
On veut étudier l'influence des coefficients c de la fonction objectif F sur la solution optimale.
Les coefficients c se décompose en
et la solution optimale s'écrit
L'expertise technique et scientifique de référence
Cet article fait partie de l’offre
Mathématiques
(170 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
Des modules pratiques
Opérationnels et didactiques, pour garantir l'acquisition des compétences transverses
Doc & Quiz
Des articles interactifs avec des quiz, pour une lecture constructive
Analyse post-optimale
