Programmation linéaire en nombre entiers

Programmation linéaire

En mathématiques, les problèmes de programmation linéaire (PL) sont des problèmes d'optimisation où la fonction objectif et les contraintes sont toutes linéaires. Néanmoins, la plupart des résultats présentés ici sont également vrais si l'objectif est une fonction monotone croissante de chaque variable considérée. La programmation linéaire désigne également la manière de résoudre les problèmes linéaires.

La programmation linéaire est un domaine central de l'optimisation, car les problèmes de PL sont les problèmes d'optimisation les plus faciles - toutes les contraintes y étant linéaires. Beaucoup de problèmes réels de recherche opérationnelle peuvent être exprimés comme un problème de PL. Pour cette raison un grand nombre d'algorithmes pour la résolution d'autres problèmes d'optimisation sont fondés sur la résolution de problèmes linéaires.

Le terme programmation linéaire suppose que les solutions à trouver doivent être représentées en variables réelles. S'il est nécessaire d'utiliser des variables discrètes dans la modélisation du problème, on parle alors de programmation linéaire en nombres entiers (PLNE). Il est important de savoir que ces derniers sont nettement plus complexes à résoudre que les PL à variables continues.

Sommaire

1 Exemple
2 Théorie
3 Dualité
4 Algorithmes de la programmation linéaire
5 Programmation linéaire en nombres entiers
6 Applications
- 6.1 Applications dans le pétrole
7 Références
8 Bibliographie
9 Liens externes

Exemple

Considérons un agriculteur qui possède des terres, de superficie égale à H hectares, dans lesquelles il peut planter du blé et du maïs. L'agriculteur possède une quantité E d'engrais et I d'insecticide. Le blé nécessite une quantité E₁ d'engrais par hectare et I₁ d'insecticide par hectare. Les quantités correspondantes pour le maïs sont notées E₂ et I₂.

Soit P₁ le prix de vente du blé et P₂ celui du maïs. Si l'on note par x₁ et x₂ le nombre d'hectares à planter en blé et en maïs, alors le nombre optimal d'hectares à planter en blé et en maïs peut être exprimé comme un programme linéaire:

$maximise$	$P 1 x 1 + P 2 x 2$	(maximiser le revenu net)
$sous contraintes$	$x_1 + x_2 \le H$	(borne sur le nombre total d'hectares)
	$E_1 x_1 + E_2 x_2 \le E$	(borne sur la quantité d'engrais)
	$I_1 x_1 + I_2 x_2 \le I$	(borne sur la quantité d'insecticide)
	$x_1 \ge 0,\, x_2 \ge 0$	(on ne peut pas planter un nombre négatif d'hectares)

Théorie

Comme l'exemple précédent le montre, la programmation consiste à déterminer disons n variables, $x_1, \cdots, x_n$ afin de maximiser l'objectif linéaire

$L(x_1, \cdots, x_n) = \sum_{i=1}^n c_i x_i$

sous différentes contraintes, comme par exemple les m inégalités suivantes

$\sum_{j=1}^n A_{i,j} x_j \leq b_i$

pour i allant de 1 à m. De telles contraintes permettent d'inclure des contraintes de signe, comme par exemple $x_1 \geq 0$ ou $x_1 \leq 0$ . L'adoption de l'écriture matricielle de la forme standard donne

$\begin{array}{rrll} \max L(x) = & c^tx & &\\ s.c & Ax &\leq& b\\ & x &\geq&0 \end{array}$

On peut, lors de la programmation linéaire, chercher à minimiser la fonction objectif. On se ramène au cas précédent (la forme standard) en cherchant à maximiser $-L(x_1,\cdots,x_n)$ .

D'un point de vue géométrique, les contraintes linéaires forment un polyèdre convexe. Si la fonction objectif est elle aussi linéaire, tous les optima locaux sont également des optima globaux; cela reste vrai si elle est monotone croissante sur chaque variable considérée, le cas linéaire ne représentant qu'un cas particulier dont la propriété n'est d'ailleurs pas utilisée.

Il y a deux cas où il n'existe pas de solution optimale. Le premier est lorsque les contraintes se contredisent mutuellement (par exemple $((x \ge 2) \wedge (x \le 1))$ ). Dans un tel cas, le polytope est vide et il n'y a pas de solution optimale puisqu'il n'y a pas de solution du tout. Le PL est alors infaisable.

Le polyèdre peut également être non-borné dans la direction définie par la fonction objectif (par exemple $x 1 + 3 x 2$ tel que $x_1 \ge 0$ , $x_2 \ge 0$ , $x_1 + x_2 \ge 10$ ). Dans ce cas, il n'y a pas de solution optimale puisqu'il est possible de construire des solutions satisfaisant les contraintes avec des valeurs arbitrairement élevées (ou basses) de la fonction objectif.

En dehors de ces deux cas (qui sont finalement rares dans les problèmes pratiques), l'optimum est toujours atteint à un sommet du polytope. Cependant, l'optimum n'est pas nécessairement unique: il est possible d'avoir un ensemble de solutions optimales correspondant à une arête ou à une face du polytope, voire au polytope en entier.

Dualité

Tous les programmes linéaires peuvent s'écrire^[1] sous la forme suivante:

$\begin{array}{rrll} \max z = & c^tx & &\\ s.c & Ax &\leq& b\\ & x &\geq&0 \end{array}$

Où $c$ et $x$ sont des vecteurs de taille $n$ , $b$ un vecteur de taille $m$ , et $A$ une matrice de taille $m \times n$ . Si on désigne cette représentation sous le terme de forme primale, on désigne alors sous le terme de forme duale le problème suivant:

$\begin{array}{rrll} \min w = & b^ty & &\\ s.c & A^ty &\geq& c\\ & y &\geq&0 \end{array}$

Où $A$ , $b$ et $c$ sont les mêmes et $y$ un vecteur de taille $m$ . (Note: )

Les deux problèmes sont très fortement liés. Si l'un d'entre eux possède une solution optimale, alors l'autre aussi. De plus, les deux solutions ont alors la même valeur (w*=z*). Si l'un d'entre eux est non-borné, l'autre ne possède pas de solution.

Outre son intérêt théorique, le problème dual possède de très intéressantes applications économiques. À chaque contrainte primale correspond une variable duale. La valeur de cette variable dans la solution optimale représente le coût marginal associé à la contrainte primale.

Algorithmes de la programmation linéaire

L'algorithme du simplexe permet de résoudre les problèmes de PL en construisant tout d'abord une solution réalisable qui est un sommet du polytope puis en se déplaçant selon les arêtes du polytope pour atteindre des sommets pour lesquels la valeur de l'objectif est de plus en plus grande, jusqu'à atteindre l'optimum. Bien que cet algorithme soit efficace en pratique et qu'il soit assuré de trouver l'optimum, son comportement dans le pire cas peut être mauvais. Il est ainsi possible de construire un PL pour lequel la méthode du simplexe requiert un nombre d'étapes exponentiel en la taille du problème. Ainsi, pendant plusieurs années, savoir si la PL était un problème NP-complet ou polynomial est resté une question ouverte.

Le premier algorithme polynomial pour la PL a été proposé par Leonid Khachiyan en 1979. Il est basé sur la méthode de l'ellipsoïde en optimisation non linéaire précédemment proposée par Naum Shor. Cette méthode est elle-même une généralisation de la méthode de l'ellipsoïde en optimisation convexe due à Arkadi Nemirovski (Prix John von Neumann 2003), et à D. Yudin.

Cependant, l'efficacité pratique de l'algorithme de Khachiyan est décevante : l'algorithme du simplexe est pratiquement toujours plus performant. En revanche, ce résultat a encouragé la recherche dans les méthodes de point intérieur. Par opposition à l'algorithme du simplexe qui considère uniquement la frontière du polytope définie par les contraintes, les méthodes de point intérieur évoluent à l'intérieur du polytope.

En 1984, N. Karmarkar propose la méthode projective. C'est le premier algorithme efficace à la fois en théorie et en pratique. Sa complexité dans le pire cas est polynomiale et les expérimentations sur les problèmes pratiques montrent que la méthode peut raisonnablement être comparée à l'algorithme du simplexe. Depuis lors, plusieurs méthodes de point intérieur ont été proposées et étudiées. Une des méthodes les plus célèbres est la méthode prédictive/corrective qui fonctionne très bien en pratique même si son étude théorique est encore imparfaite.

Pour la résolution pratique de problèmes de PL ordinaires, il est actuellement commun de considérer comme équivalentes les (bons) codes basés sur les méthodes dérivées du simplexe ou du point intérieur. De plus, pour la résolution de problèmes de grande taille, une technique comme la génération de colonnes peut se révéler extrêmement efficace.

Les solveurs basés sur la PL sont de plus en plus utilisés pour l'optimisation de divers problèmes industriels tels que l'optimisation des flux de transports ou la planification de la production. Toutefois, les modèles de PL se révèlent insuffisants pour représenter de nombreux problèmes, la programmation linéaire en nombres entiers (PLNE) permet alors de modéliser un grand nombre de problèmes supplémentaires, notamment les problèmes NP-complets.

Programmation linéaire en nombres entiers

Un problème de programmation linéaire en nombres entiers (PLNE) n'est pas un programme linéaire dans le sens où son domaine de réalisabilité n'est pas un polyèdre mais un ensemble discret de points. Pourtant, on peut le décrire comme un PL auquel on ajoute la contrainte supplémentaire que certaines variables ne peuvent prendre que des valeurs entières. On distingue le programme linéaire mixte avec variables entières et continues du programme entier avec toutes ses variables entières.

La PLNE est un problème NP-complet car de nombreux problèmes NP-complets peuvent être exprimés comme des PLNE (par exemple trouver un stable dans un graphe $G = (V, E)$ revient à trouver un vecteur $x\in \{0,1\}^E$ satisfaisant $x_u +x_v \le 1$ pour tout arête $uv \in E$ ). Les algorithmes décrits ci-dessus pour la PL ne résolvent pas les problèmes de PLNE. Algorithmiquement donc, la résolution d'un PLNE est autrement plus difficile celle d'un PL qui joue pourtant un rôle crucial quant à leur résolution, principalement pour deux raisons. Premièrement, la relaxation continue d'un PLNE (c'est le PLNE sans les contraintes d'intégrité) est un PL qui peut être résolu efficacement et fournir ainsi une borne duale (dans le sens non-réalisable). Les algorithmes de résolution de PLNE, tels que les algorithmes par séparation et évaluation se basent sur cette relaxation continue pour diminuer au maximum l'énumération des solutions. Deuxièmement, le théorème Optimisation/Séparation de Grötschel, Lovasz et Schrijver permet de résoudre en pratique par la PL les problèmes entiers dont on connait une bonne description polyèdrale (c'est-à-dire dont on peut séparer les contraintes en temps polynomial). C'est le principe de fonctionnement des algorithmes de plans sécants,

Applications

La programmation linéaire est essentiellement appliquée pour résoudre des problèmes d'optimisation à moyen et long terme (problèmes stratégiques et tactiques, dans le vocabulaire de la recherche opérationnelle). Les domaines d'application de ces problèmes sont très nombreux aussi bien dans la nature des problèmes abordés (planification et contrôle de la production, distribution dans des réseaux) que dans les secteurs d'industrie : industrie manufacturière, énergie (pétrole, gaz, électricité, nucléaire), transports (aériens, routiers et ferroviaires), télécommunications, industrie forestière, finance.

Applications dans le pétrole

Articles détaillés : Pétrole, Raffinage du pétrole et Plans d'approvisionnement, de production et de distribution du pétrole.

La technique de la programmation linéaire est couramment appliquée dans l'industrie pétrolière. C'est l'une des industries, si ce n'est la principale qui utilise quotidiennement la PL (programmation linéaire). Elle est l'outil qui permet au raffineur de faire la détermination optimale de production d'une raffinerie. Pour ce faire, le programme doit tenir compte d'un certain nombre de contraintes telles que :

bruts disponibles, leurs rendements et les qualités des coupes,
spécifications des produits à fabriquer,
limitations de débouchés pour certains produits,
capacités des unités,
modes de réglages des installations,
capacités de stockage disponibles.

La PL peut également être utilisée dans d'autres domaines du raffinage, par exemple :

calculs de la composition optimale des mélanges de produits (carburants, gasoils, fuels) en tenant compte des spécifications.
l'optimisation dans l'utilisation des installations,
calculs de l'obtention du meilleur préchauffage des bruts et des charges,
détermination du meilleur équilibre «vapeur-électricité» d'une raffinerie.

En dehors des raffineries, on peut utiliser la PL dans la recherche opérationnelle pour :

bâtir des plans à long/moyen et court termes d'une compagnie pétrolière,
optimiser le fonctionnement d'une flotte de tankers et la mise en place des produits.

Références

↑ Les détails exacts des deux représentations varient beaucoup d'un ouvrage à l'autre

Bibliographie

Christelle Guéret, Christian Prins et Marc Sevaux, Programmation Linéaire, Eyrolles, 2000 (ISBN 2-212-09202-4), 365 pages.

Eric Jacquet-Lagrèze. Programmation Linéaire - Modélisation et mise en œuvre informatique. Collection : P.I.Q. Poche - Éditeur : Economica

Liens externes

(en) Linear Programming: Foundations and Extensions.
(en) IBM's article on GLPK A technical article on GPLK (en) with an introduction to Linear Programming by IBM
(en) lp_solve, un autre logiciel libre pour la programmation linéaire. Il peut être appelé via une interface de programmation, un fichier texte, ou un environnement de développement intégré.
(en) Guidance on Formulating LP problems
(en) 0-1 Integer Programming Benchmarks with Hidden Optimum Solutions
(en) A Tutorial on Integer Programming
(en) The linear programming FAQ
(en) Linear Programming Survey OR/MS Today
(en) Linear Programming: Guide to Formulation, Simplex Algorithm, Goal Programming and Excel Solver examples
(en) George Dantzig
(en) Benchmark de différents logiciels sur différentes instances de PLNE

Logiciels

(en) AIMMS Optimization Modeling AIMMS — include linear programming in industry solutions (free trial license available);
(en) CGAL — The Computational Geometry Algorithms Library includes a linear solver, which is exact and optimized for problems with few constraints or few variables
(en) COIN-OR — COmputational INfrastructure for Operations Research, open-source library
(en) Cplex — Commercial library for linear programming
(en) DecisionPro Linear Programming Optimization Software
(en) GNU Linear Programming Kit, Bibliothèque libre GLPK (en) pour la programmation linéaire, méthode du simplex, du point intérieur…
(en) GIPALS — Linear programming environment and dynamic link library (DLL)
(en) HOPDM — Higher Order Primal Dual Method
(en) LINDO — LP, IP, Global solver/modeling langage
(en) Linear programming and linear goal programming A freeware program for MS-DOS
(en) MOSEK — Optimization software for LP, IP, QP, SOCP and MIP. Free trial is available. Free for students.
(en) Mathematica — General technical computing system includes large scale linear programming support
(en) Microarray Data Classification Server (MDCS) based on linear programming
(en) Optimj OptimJ is an extension of the Java programming langage with langage support for writing optimization models and powerful abstractions for bulk data processing.
(en) Orstat2000 — Includes easy-to-use modules for linear and integer programming (free for educational purposes).
(en) Premium Solver — Spreadsheet add-in
(en) QSopt Optimization software for LP (free for research purposes).
(en) R Logiciel libre de calcul statistique contenant des librairies aditionnelles pour la PL: glpk, linprog (simplex), Rglpk (interface R pour GPLK (en))
(en) Simplex Method Tool A quick-loading web page
(en) What's Best! — Spreadsheet add-in
(en) Xpress-MP — Optimization software free to students
(fr) IMSL — implémentations pour Fortran, C/C++, Java et C#

Articles en rapport avec la convexité
Géométrie convexe	Article principal : Ensemble convexe Outils et résultats fondamentaux : Enveloppe convexe • Adhérence, intérieur et frontière d'un convexe • Projection sur un convexe fermé • Séparation des convexes • Points remarquables à la frontière d'un convexe • Polytope • Théorème de Krein-Milman • Lemme de Farkas Géométrie combinatoire : Théorème de Carathéodory • Théorème de Radon • Théorème de Helly Géométrie métrique : Courbe de largeur constante • Théorème des quatre sommets Algorithmes de géométrie convexe : Approche polyèdrale • Marche de Jarvis • Parcours de Graham • Théorème optimisation/séparation Optimisation linéaire : Programmation linéaire • Algorithme du simplexe • Génération de colonnes
Interactions géométrie-analyse	Théorème de Hahn-Banach • Jauge
Analyse convexe	Article principal : Fonction convexe Outils et résultats fondamentaux : Inégalité de Jensen Optimisation convexe : Conditions de Kuhn-Tucker • Méthode du point intérieur
Utilisations de la convexité	Inégalités de convexité : Inégalité arithmético-géométrique • Inégalité de Hölder Analyse fonctionnelle : Espace localement convexe • Théorème du point fixe de Schauder Localisation de zéros de polynômes : Théorème de Gauss-Lucas Théorie des nombres : Théorème de Minkowski

Portail des mathématiques

Ce document provient de « Programmation lin%C3%A9aire#Programmation lin.C3.A9aire en nombres entiers ».

Catégories : Optimisation | Recherche opérationnelle | Optimisation combinatoire

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Programmation linéaire en nombre entiers de Wikipédia en français (auteurs)

Игры ⚽ Нужен реферат?

Regardez d'autres dictionnaires:

Programmation linéaire en nombres entiers — Programmation linéaire En mathématiques, les problèmes de programmation linéaire (PL) sont des problèmes d optimisation où la fonction objectif et les contraintes sont toutes linéaires. Néanmoins, la plupart des résultats présentés ici sont… … Wikipédia en Français
Programmation lineaire — Programmation linéaire En mathématiques, les problèmes de programmation linéaire (PL) sont des problèmes d optimisation où la fonction objectif et les contraintes sont toutes linéaires. Néanmoins, la plupart des résultats présentés ici sont… … Wikipédia en Français
Programmation linéaire — En mathématiques, les problèmes de programmation linéaire (PL) sont des problèmes d optimisation où la fonction objectif et les contraintes sont toutes linéaires. Néanmoins, la plupart des résultats présentés ici sont également vrais si l… … Wikipédia en Français
Programmation non linéaire — Optimisation (mathématiques) En mathématiques, l optimisation est l’étude des problèmes qui sont de la forme : Étant donné : une fonction d’un ensemble A dans l ensemble des nombre réels Rechercher : un élément x0 de A tel que pour … Wikipédia en Français
Programmation mathématique — Optimisation (mathématiques) En mathématiques, l optimisation est l’étude des problèmes qui sont de la forme : Étant donné : une fonction d’un ensemble A dans l ensemble des nombre réels Rechercher : un élément x0 de A tel que pour … Wikipédia en Français
PROGRAMMATION MATHÉMATIQUE — La programmation mathématique consiste à chercher, parmi tous les points x vérifiant certaines conditions du type: celui ou ceux qui rendent minimal (ou maximal, suivant le cas) un certain critère f (x ), qui sera interprété comme un gain dans le … Encyclopédie Universelle
Programme linéaire — Programmation linéaire En mathématiques, les problèmes de programmation linéaire (PL) sont des problèmes d optimisation où la fonction objectif et les contraintes sont toutes linéaires. Néanmoins, la plupart des résultats présentés ici sont… … Wikipédia en Français
Optimisation linéaire — En optimisation, qui est une branche des mathématiques, un problème d optimisation linéaire est un problème d optimisation dans lequel on minimise une fonction linéaire sur un polyèdre convexe. La fonction coût et les contraintes peuvent donc… … Wikipédia en Français
Générateur de nombre pseudo-aléatoire — Générateur de nombres pseudo aléatoires Un générateur de nombres pseudo aléatoires, pseudorandom number generator (PRNG) en anglais, est un algorithme qui génère une séquence de nombres présentant certaines propriétés du hasard. Par exemple, les… … Wikipédia en Français
PLNE — Programmation linéaire En mathématiques, les problèmes de programmation linéaire (PL) sont des problèmes d optimisation où la fonction objectif et les contraintes sont toutes linéaires. Néanmoins, la plupart des résultats présentés ici sont… … Wikipédia en Français

Dictionnaires et Encyclopédies sur 'Academic'

Programmation linéaire en nombre entiers