Présentation

Article

1 - MODÉLISATION ET RÉSOLUTION GRAPHIQUE

  • 1.1 - Modélisation
  • 1.2 - Résolution graphique

2 - FORMES GÉNÉRALES D’UN PROGRAMME LINÉAIRE

  • 2.1 - Forme canonique mixte
  • 2.2 - Forme canonique pure
  • 2.3 - Forme standard
  • 2.4 - Variables d’écarts

3 - SOLUTIONS DE BASE RÉALISABLES ET LEURS PROPRIÉTÉS GÉOMÉTRIQUES

  • 3.1 - Solutions de base réalisables
  • 3.2 - Propriétés géométriques des solutions de base réalisables

4 - MÉTHODE DU SIMPLEXE

  • 4.1 - La méthode du simplexe proprement dite : la phase 2
  • 4.2 - Calcul des coûts réduits et variable entrante
  • 4.3 - Variable sortante

5 - MISES EN ŒUVRE DE LA MÉTHODE DU SIMPLEXE

  • 5.1 - Méthode des dictionnaires
  • 5.2 - Méthode des tableaux

6 - CONVERGENCE DU SIMPLEXE

7 - INITIALISATION, PROBLÈME AUXILIAIRE ET VARIABLES ARTIFICIELLES : LA PHASE 1

8 - ANALYSE POST-OPTIMALE

  • 8.1 - Analyse de sensibilité de l'objectif
  • 8.2 - Analyse de sensibilité du second membre des contraintes

9 - DUALITÉ

  • 9.1 - Introduction et définition
  • 9.2 - Propriétés – théorèmes de dualité
  • 9.3 - Conditions d’optimalité primal-dual

10 - ANNEXE : QUELQUES SOLVEURS DE PROGRAMMES LINÉAIRES ET CODES MATLAB

  • 10.1 - Quelques solveurs de programmes linéaires
  • 10.2 - Codes MATLAB

11 - CONCLUSION

12 - GLOSSAIRE – DÉFINITIONS

Article de référence | Réf : AF1254 v1

Modélisation et résolution graphique
Programmation linéaire - Méthodes et applications

Auteur(s) : Jean-François SCHEID

Date de publication : 10 oct. 2015

Pour explorer cet article
Télécharger l'extrait gratuit

Vous êtes déjà abonné ?Connectez-vous !

Sommaire

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’article

ABSTRACT

Linear Programming. Methods and Applications

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.

Cet article est réservé aux abonnés.
Il vous reste 93% à découvrir.

Pour explorer cet article
Téléchargez l'extrait gratuit

Vous êtes déjà abonné ?Connectez-vous !


L'expertise technique et scientifique de référence

La plus importante ressource documentaire technique et scientifique en langue française, avec + de 1 200 auteurs et 100 conseillers scientifiques.
+ de 10 000 articles et 1 000 fiches pratiques opérationnelles, + de 800 articles nouveaux ou mis à jours chaque année.
De la conception au prototypage, jusqu'à l'industrialisation, la référence pour sécuriser le développement de vos projets industriels.

KEYWORDS

linear programming   |   simplex method   |   MATLAB

DOI (Digital Object Identifier)

https://doi.org/10.51257/a-v1-af1254


Cet article fait partie de l’offre

Mathématiques

(202 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

ABONNEZ-VOUS

1. Modélisation et résolution graphique

1.1 Modélisation

En optimisation et plus généralement en recherche opérationnelle, modéliser un problème consiste à identifier les variables intrinsèques, les différentes contraintes auxquelles sont soumises ces variables et enfin à définir l’objectif visé (optimisation). Dans un problème de programmation linéaire (PL en abrégé) les contraintes et l’objectif sont des fonctions linéaires des variables.

On va étudier un exemple particulier de programmation linéaire qui servira d’exemple de référence tout au long de l’article. Il s’agit d’un problème de production volontairement très simple. Le but ici n’étant pas de résoudre ce problème mais d’introduire les notions et concepts fondamentaux liés à la programmation linéaire. Dans cet exemple, on considère une usine qui fabrique deux produits P1 et P2 en utilisant un certain nombre de ressources : équipement, main d’œuvre et matières premières. Ces besoins sont indiqués dans le tableau 1. Par ailleurs, chaque ressource est disponible en quantité limitée (cf. tableau 1).

Les deux produits P1 et P2 rapportent à la vente respectivement des bénéfices de 6 euros et 4 euros par unité. On cherche à savoir quelles quantités de produits P1 et P2 doit produire l’usine afin de maximiser le bénéfice total venant de la vente des deux produits. Les quantités de produits sont des valeurs non nécessairement entières.

  • Choix des variables (les inconnues) : x 1 et x 2 sont respectivement les quantités des produits P1 et P2 fabriqués (x 1, ) ;

  • Choix de la fonction objectif à maximiser : la fonction objectif F correspond au bénéfice total provenant de la vente des produits P1 et P2 en quantité x 1 et x 2. Elle vaut F  (x 1, x 2) = 6x 1 + 4x 2. Le problème se traduit donc par :

    ...

Cet article est réservé aux abonnés.
Il vous reste 92% à découvrir.

Pour explorer cet article
Téléchargez l'extrait gratuit

Vous êtes déjà abonné ?Connectez-vous !


L'expertise technique et scientifique de référence

La plus importante ressource documentaire technique et scientifique en langue française, avec + de 1 200 auteurs et 100 conseillers scientifiques.
+ de 10 000 articles et 1 000 fiches pratiques opérationnelles, + de 800 articles nouveaux ou mis à jours chaque année.
De la conception au prototypage, jusqu'à l'industrialisation, la référence pour sécuriser le développement de vos projets industriels.

Cet article fait partie de l’offre

Mathématiques

(202 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

ABONNEZ-VOUS

Lecture en cours
Modélisation et résolution graphique
Sommaire
Sommaire

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...

1 Outils logiciels

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

2 Sites Internet

COIN-OR : COmputational INfrastructure for Operations Research

http://www.coin-or.org/

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

http://afpc.greyc.fr

HAUT DE PAGE

Cet article est réservé aux abonnés.
Il vous reste 94% à découvrir.

Pour explorer cet article
Téléchargez l'extrait gratuit

Vous êtes déjà abonné ?Connectez-vous !


L'expertise technique et scientifique de référence

La plus importante ressource documentaire technique et scientifique en langue française, avec + de 1 200 auteurs et 100 conseillers scientifiques.
+ de 10 000 articles et 1 000 fiches pratiques opérationnelles, + de 800 articles nouveaux ou mis à jours chaque année.
De la conception au prototypage, jusqu'à l'industrialisation, la référence pour sécuriser le développement de vos projets industriels.

Cet article fait partie de l’offre

Mathématiques

(202 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

ABONNEZ-VOUS