Programmation linéaire - Définition et Explications

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

Introduction

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...) considérée. La programmation linéaire (En mathématiques, les problèmes de programmation linéaire (PL) sont des...) désigne également la manière de résoudre les problèmes linéaires.

La programmation (La programmation dans le domaine informatique est l'ensemble des activités qui permettent...) 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...) 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...) 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 (contraintes dites d'intégrité), 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.

Exemple

Considérons un agriculteur (L'agriculteur ne désigne pas seulement la personne qui cultive la terre mais aussi celle qui...) 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...) égale à H hectares, dans lesquelles il peut planter du blé (« Blé » est un terme générique qui désigne plusieurs...) et du maïs (Le maïs (aussi appelé blé d’Inde au Canada) est une plante tropicale...). L'agriculteur possède une quantité (La quantité est un terme générique de la métrologie (compte, montant) ; un scalaire,...) E d'engrais (Les engrais sont des substances, le plus souvent des mélanges d'éléments...) et I d'insecticide (Étymologiquement, les insecticides sont des substances actives ou des préparations ayant...). 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:

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

Dualité

Tous les programmes linéaires peuvent s'écrire sous la forme suivante :

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

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...) 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 = & {}^tb\,y & &\\      s.c & {}^tA\,y   &\geq& c\\          &  y   &\geq&0 \end{array}

A, b et c sont les mêmes et y un vecteur de taille m.

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 (Marginal (sous-titrée Anthologie de l'imaginaire) est une collection des éditions OPTA,...) associé à la contrainte primale.

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) = & {}^tc\,x & &\\      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 (Graphie) de vue (La vue est le sens qui permet d'observer et d'analyser l'environnement par la réception et...) géométrique, les contraintes linéaires forment un polyèdre (Un polyèdre est une forme géométrique à trois dimensions ayant des faces planes...) convexe (En géométrie, un objet est convexe si pour toute paire de points { A , B } de cet objet, le...) (ou polytope). 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...) 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...). 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...) de solutions optimales correspondant à une arête ou à une face du polytope, voire au polytope en entier.

Page générée en 0.127 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