2.1 Une présentation simple et informelle de la programmation linéaire☝

De nombreux problèmes incorporent un certain nombre d'inégalités qui doivent être vérifiées. L'exemple le plus simple correspond à  la limitation des ressources qui sont disponibles :

  1. si $x_i$ est la quantité utilisée de la ressource $i$ ($i = 1, \ldots, n$), on a nécessairement pour tout $i$ : $x_i \geq 0$.
  2. De même, on ne peut utiliser plus de ressources que les ressources disponibles. Si $\overline{x}_j$ est la quantité disponible de la ressource, on doit avoir $\overline{x}_j \geq x_j$.
  3. Enfin, il est possible que la combinaison des ressources soit elle-même sujette à  plusieurs contraintes. La programmation linéaire suppose que ces contraintes en nombre $m$ peuvent s'écrire sous la forme :
\[ a_{1j} x_{1}+ a_{2j} x_{2}+ \cdots+ a_{nj} x_{n} = \sum_{i = 1}^n a_{ij} x_i \leq b_j \hspace{.25cm} \text{ou}\hspace{.25cm} \sum_{i = 1}^n a_{ij} x_i \geq b_j, \hspace{.25cm}j = 1, \ldots, m \]

Face à  ces contraintes, on suppose que le décideur cherche à  optimiser (maximiser ou minimiser) une fonction linéaire des variables $x_i$, i.e. :

\[ z = c_1 x_1 + c_2 x_2 + \cdots+c_n x_n \]

Sous cette forme, le plus simple des programmes linéaires s'écrit :

\[ \begin{array}{c} \max(\min)\, c_1x_1 + c_2x_2\\\\ \text{sous les contraintes}\\\\ x_1 \leq b_1\\ x_2 \leq b_2\\ x_1\ \geq 0\\ x_2\ \geq 0 \end{array} \]

Il est évident que le domaine délimité par les contraintes représente un rectangle comme celui qui est représenté à  la figure ci-dessous (les points rouges peuvent être déplacés à la souris).

Domaine défini par les inégalités $x_1 \leq b_1, x_2\leq b_2, x_1 \geq 0\, \mathrm{et}\, x_2 \geq 0$



Considérons maintenant l'objectif en supposant qu'on cherche un maximum \footnote{Le raisonnement est inversé pour un minimum puisque $\max a_1 x_1 + a_2 x_2$ est identique à  $\min -[a_1 x_1 + a_2 x_2]$.}. Objectivement, pour un niveau donné $\overline{z}$, il s'agit d'une droite puisque, sous l'hypothèse selon laquelle $a_2 \not=0$, on peut la réécrire sous la forme :

\[ x_2 =- \left(\frac{a_1}{a_2}\right) x_1 + \left(\frac{\overline{z}}{a_2}\right) \]

Trois cas sont possibles :

  1. $a_1/a_2 >0$, ce qui signifie simplement que $a_1$ et $ a_2$ sont de même signe (tous deux positifs ou négatifs). Dans ce cas la pente est négative.
  2. $a_1/a_2 <0$, ce qui signifie simplement que $a_1$ et $ a_2$ sont de signes contraires ($a_1 >0$ et $a_2 <0$ ou $a_1 <0$ et $a_2 >0$). Ici, la pente est positive.
  3. $a_1 = 0$ ou $a_2 = 0$, il n'existe pas de dépendance entre $x_2$ et $x_1$.

Notons encore que $x_2$ est d'autant plus grand que $\overline{z}$ l'est si $a_2\ > 0$ et réciproquement pour $a_2<0$.

Commençons par le cas $a_1/a_2 >0$ et $a_2 >0$.

Déplacement de l'objectif pour un accroissement de $Z$ ($a_1/a_2>0, a_2>0)$



Celle-ci montre que pour $x_1$ fixé, un accroissement de $z$ déplace l'objectif vers le Nord-Est de la figure ci-dessus. Par conséquent, c'est en se déplaçant dans cette direction que l'on trouvera un maximum comme le montre la figure suivante.

Il est évident que si, sous les mêmes circonstances (i.e. : $a_1/a_2 >0$), $a_2 <0$, l'effet d'un accroissement de $z$ est inversé et l'on aboutit au graphique présenté ci-dessous.

Considérons maintenant le cas $a_1/a_2 <0$, $a_2 >0$. Observons à  nouveau l'objectif tel qu'il est décrit par la figure qui suit. Cette fois-ci, il est clair que pour $x_1$ donné, une augmentation de $z$ conduit à  une augmentation de $x_2$.

En rassemblant l'objectif et les contraintes, on aboutit directement à  la figure suivante.

De même, pour $a_1/a_2 >0$ et $a_2 <0$, on aura la figure qui suit.

Il reste les deux cas $a_1 = 0$ et $a_2 = 0$ à  traiter en excluant le cas $(a_1,a_2) = (0,0)$ qui est sans intérêt. Dans le premier cas, on a $z = a_2 x_2$ Si $a_2 > 0$, plus $x_2$ est élevé plus $z$ l'est. Par conséquent, de manière à  respecter les contraintes, on doit avoir $(\hat{x}_1, \hat{x}_2) = ([0, b_1],b_2)$, ce qui signifie que l'on doit fixer $x_2$ à  $b_2$ et prendre n'importe quelle valeur appartenant à  $[0, b_1]$ pour $x_1$. Il existe donc une infinité de solutions. Ce cas est représenté à  la figure ci-dessous.

Mais, si $a_2 < 0$, la représentation est inversée et le résultat devient $(\hat{x}_1, \hat{x}_2) = ([0,b_1],0)$, comme le montre la figure qui suit.

Maintenant, dans le second cas ($a_2 =0$), $z= a_1 x_1$. Si $a_1>0$, il est évident que l'on doit choisir la plus grande valeur de $x_1$ possible, soit $\hat{x}_1 = b_1$. Dans ce cas, peut importe la valeur de $x_2$ tant qu'elle vérifie la contrainte. Par conséquent, la solution est de la forme $(\hat{x}_1, \hat{x}_2) = (b_1,[0, b_2])$ comme le montre la figure~\ref{ppl10}.

Enfin, pour finir si, toujours dans le cas où $a_2= 0$, $a_1 <0$, il est clair qu'il faut choisir $(\hat{x}_1, \hat{x}_2) = (0, [0, b_2])$ comme le montre la figure ci-après.

👈 ☝ 👉