Programmation linéaire
Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.

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 (En mathématiques et en logique, une variable est représentée par un symbole. Elle est utilisée pour marquer un rôle dans une formule, un prédicat ou un algorithme. En statistiques, une variable peut aussi...) considérée. La 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...) désigne également la manière de résoudre les problèmes de PL.

La programmation (La programmation dans le domaine informatique est l'ensemble des activités qui permettent l'écriture des programmes informatiques. C'est une étape importante de la conception de logiciel (voire de matériel,...) 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 (La recherche opérationnelle (aussi appelée aide à la décision) peut être définie comme l'ensemble des méthodes et techniques rationnelles d'analyse et de synthèse des phénomènes d'organisation utilisables pour élaborer de meilleures...) peuvent être exprimés comme un problème de PL. Pour cette raison un grand nombre (La notion de nombre en linguistique est traitée à l’article « Nombre grammatical ».) 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 difficiles à résoudre que les PL à variables continues.

Exemple

Considérons un agriculteur (L'agriculteur ne désigne pas seulement la personne qui cultive la terre mais aussi celle qui procède à l'élevage sur cette même terre (apiculteur, aviculteur, cultivateur, éleveur, exploitant...) qui possède des terres, de superficie (L'aire ou la superficie est une mesure d'une surface. Par métonymie, on désigne souvent cette mesure par le terme « surface » lui-même (par exemple, on parle de la « surface d'un...) égale à H hectares, dans lesquelles il peut planter du blé (« Blé » est un terme générique qui désigne plusieurs céréales appartenant au genre Triticum. Ce sont des plantes...) et du maïs (Le maïs (aussi appelé blé d’Inde au Canada) est une plante tropicale herbacée annuelle de la famille des Poacées, largement cultivée comme céréale pour ses grains riches en amidon, mais...). L'agriculteur possède une quantité (La quantité est un terme générique de la métrologie (compte, montant) ; un scalaire, vecteur, nombre d’objets ou d’une autre manière de dénommer la valeur...) E d'engrais (Les engrais sont des substances, le plus souvent des mélanges d'éléments minéraux, destinées à apporter aux plantes des compléments d'éléments...) et I d'insecticide (Étymologiquement, les insecticides sont des substances actives ou des préparations ayant la propriété de tuer les insectes, leurs larves et/ou leurs œufs. Ils font partie de la famille des pesticides,...). Le blé nécessite une quantité E1 d'engrais par hectare et I1 d'insecticide par hectare. Les quantités correspondantes pour le maïs sont notées E2 et I2.

Soit P1 le prix de vente du blé et P2 celui du maïs. Si l'on note par x1 et x2 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 P1x1 + P2x2 (maximiser le revenu net)
sous contraintes x_1 + x_2 \le H (borne sur le nombre total ( Total est la qualité de ce qui est complet, sans exception. D'un point de vue comptable, un total est le résultat d'une addition, c'est-à-dire une somme. Exemple : "Le total des dettes". ...) 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 (Le mot théorie vient du mot grec theorein, qui signifie « contempler, observer, examiner ». Dans le langage courant, une théorie est une idée ou une connaissance spéculative, souvent basée sur...)

D'un point (Graphie) de vue (La vue est le sens qui permet d'observer et d'analyser l'environnement par la réception et l'interprétation des rayonnements lumineux.) géométrique, les contraintes linéaires forment un polyèdre (Traditionnellement, un polyèdre est une forme géométrique à 3 dimensions ayant des faces planes qui se rencontrent le long d'arêtes droites. Le mot polyèdre provient du grec classique...) convexe (En géométrie, un objet est convexe si pour toute paire de points { A , B } de cet objet, le segment [AB] qui les joint est entièrement contenu dans l'objet. Par exemple, un cube plein, un disque ou une boule...). 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 (En géométrie, un polytope est la généralisation à toutes dimensions de la notion de polygone pour deux dimensions et de polyèdre pour trois...) est vide (Le vide est ordinairement défini comme l'absence de matière dans une zone spatiale.) et il n'y a pas de solution optimale puisqu'il n'y a pas de solution du tout (Le tout compris comme ensemble de ce qui existe est souvent interprété comme le monde ou l'univers.). Le PL est alors infaisable.

Le polyèdre peut également être non-borné dans la direction définie par la fonction objectif (par exemple x1 + 3x2 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 (En théorie des ensembles, un ensemble désigne intuitivement une collection d’objets (les éléments de l'ensemble), « une multitude...) 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 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 (En mathématiques, un vecteur est un élément d'un espace vectoriel, ce qui permet d'effectuer des opérations d'addition et de multiplication par un...) de taille m, et A une matrice de taille mXn. 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 détails exacts des deux représentations varient beaucoup d'un ouvrage à l'autre)

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. A chaque contrainte primale correspond une variable duale. La valeur de cette variable dans la solution optimale représente le coût marginal (Marginal (sous-titrée Anthologie de l'imaginaire) est une collection des éditions OPTA, vouée aux anthologies thématiques de science-fiction.) associé à la contrainte primale.

Algorithmes

L'algorithme du simplexe permet de résoudre les problèmes de PL en construisant tout d'abord une solution faisable 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 mathématiques, un ellipsoïde est une surface du second degré de l'espace euclidien à trois dimensions. Il fait donc partie des quadriques, avec pour caractéristique principale de ne pas posséder de point à l'infini.) en optimisation non linéaire précédemment proposée par Naum Shor. Cette méthode est elle-même une généralisation (La généralisation est un procédé qui consiste à abstraire un ensemble de concepts ou d'objets en négligeant les détails de...) de la méthode de l'ellipsoïde en optimisation convexe due à Arkadi Nemirovski (Prix John von Neumann (John von Neumann, mathématicien et physicien américain d'origine hongroise, a apporté d'importantes contributions tant en mécanique quantique, qu'en analyse...) 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 (La recherche scientifique désigne en premier lieu l’ensemble des actions entreprises en vue de produire et de développer les connaissances scientifiques. Par extension métonymique, la recherche scientifique désigne également le cadre...) dans les méthodes de point intérieur. Par opposition à l'algorithme du simplexe qui considère uniquement la frontière (Une frontière est une ligne imaginaire séparant deux territoires, en particulier deux États souverains. Le rôle que joue une frontière peut fortement varier suivant les régions et les époques. Entre les pays...) 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é (La complexité est une notion utilisée en philosophie, épistémologie (par exemple par Anthony Wilden ou Edgar Morin), en physique, en biologie (par exemple par Henri Atlan), en sociologie, en...) 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 (La génération de colonnes est une méthode pour résoudre efficacement les programmes linéaires de grande taille. Elle repose sur la décomposition de Dantzig et Wolfe, qui consiste à décomposer l'ensemble des contraintes en...) 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 (Le mot flux (du latin fluxus, écoulement) désigne en général un ensemble d'éléments (informations / données, énergie, matière, ...) évoluant dans un sens commun. Plus précisément le...) de transports (Le transport, du latin trans, au-delà, et portare, porter, est le fait de porter quelque chose, ou quelqu'un, d'un lieu à un autre.) ou la planification (La planification est la programmation d'actions et d'opérations à mener) 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 permet alors de modéliser un grand nombre de problèmes supplémentaires.

Programmation linéaire en nombres entiers

Un problème de programmation linéaire en nombres entiers (PLNE) est un programme linéaire, c'est-à-dire une fonction objectif linéaire à maximiser ou minimiser, sous des contraintes linéaires, dans lequel il y a la contrainte supplémentaire que les variables sont entières. On parle de programme linéaire mixte lorsque seul un sous-ensemble (En mathématiques, un ensemble A est un sous-ensemble ou une partie d’un ensemble B, ou encore B est sur-ensemble de A, si tout élément du sous-ensemble A...) de variables doivent être entières et les autres réelles.

Il est facile de montrer que la PLNE est un problème NP-complet car de nombreux problèmes NP-complets peuvent être exprimés comme des PLNE. Bien entendu, les algorithmes décrits ci-dessus pour la PL ne résolvent pas les problèmes de PLNE. En revanche, 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. Les algorithmes de résolution de PLNE, tels que les algorithmes par séparation et évaluation (Un algorithme par séparation et évaluation, également appelé selon le terme anglo-saxon branch and bound, est une méthode générique de résolution de problèmes d'optimisation, et plus...) ou les algorithmes de génération de plans sécants, se basent très souvent sur cette relaxation continue.

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 (Le mot contrôle peut avoir plusieurs sens. Il peut être employé comme synonyme d'examen, de vérification et de maîtrise.) de la production, distribution dans des réseaux) que dans les secteurs d'industrie: industrie manufacturière, énergie (Dans le sens commun l'énergie désigne tout ce qui permet d'effectuer un travail, fabriquer de la chaleur, de la lumière, de produire un mouvement.) (pétrole, gaz (Un gaz est un ensemble d'atomes ou de molécules très faiblement liés et quasi-indépendants. Dans l’état gazeux, la matière n'a pas de forme propre ni de volume propre : un gaz tend à occuper tout le...), électricité (L’électricité est un phénomène physique dû aux différentes charges électriques de la matière, se manifestant par une énergie. L'électricité désigne également la...), nucléaire), transports (aériens, routiers et ferroviaires), télécommunications (Les télécommunications sont aujourd’hui définies comme la transmission à distance d’information avec des moyens électroniques. Ce terme est plus utilisé que le terme synonyme...), industrie forestière, finance.

Applications dans le pétrole (Le pétrole est une roche liquide carbonée, ou huile minérale. L'exploitation de cette énergie fossile est l’un des piliers de...)

La technique de la programmation linéaire est couramment appliquée dans l'industrie pétrolière (L'industrie pétrolière traite de la chaîne industrielle du pétrole et du gaz naturel, du gisement jusqu'au consommateur.). C'est l'une des industries, si ce n'est la principale qui utilise quotidiennement la PL (programmation linéaire). Elle est l'outil (Un outil est un objet finalisé utilisé par un être vivant dans le but d'augmenter son efficacité naturelle dans l'action. Cette augmentation se traduit par la simplification des actions entreprises, par une plus grande rentabilisation de ces...) 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 (Une compagnie pétrolière est une entreprise dont l'activité principale est liée à l'exploitation du pétrole.),
  • optimiser le fonctionnement d'une flotte de tankers et la mise en place des produits.

Bibliographie

  • Christelle Guéret, Christian Prins et Marc Sevaux : "Programmation Linéaire". Eyrolles, 2000. ISBN 2-212-09202-4, 365 pages.
Page générée en 0.901 seconde(s) - site hébergé chez Amen
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
Ce site est édité par Techno-Science.net - A propos - Informations légales
Partenaire: HD-Numérique