Recherche Opérationnelle

1. La programmation linéaire

1.1 Introduction

La programmation linéaire (PL) est une technique d'optimisation
dont les premiers travaux remontent à 1947 (George B. Dantzig).
Elle s'applique à tout problème où la fonction objectif
et les contraintes sont purement linéaires.

La formulation d'un problème d'optimisation comporte trois étapes :
(1) choix des variables du modèle,
(2) formulation de l'objectif,
(3) formulation des contraintes.

1.2 Exemple introductif

Une entreprise fabrique deux types de châssis ($x_1$ et $x_2$)
dans trois ateliers. Le problème s'écrit :
$$\max z = 3x_1 + 5x_2$$
$$\text{s.c.q.} \quad
x_1 \leq 4, \quad
2x_2 \leq 12, \quad
3x_1 + 2x_2 \leq 18, \quad
x_1, x_2 \geq 0$$

1.3 Résolution graphique

La résolution graphique se déroule en trois étapes :
représentation de la région réalisable
(intersection des demi-plans définis par les contraintes),
représentation des droites d'isovaleur $z = k$,
détermination du point optimum.

La solution optimale est $x^* = (2, 6)$ pour $z^* = 36$.

Trois observations importantes :

Observation 1.1 : Pour maximiser l'objectif,
il faut prendre la droite d'isovaleur qui touche encore
la région réalisable et qui donne la plus grande valeur.

Observation 1.2 : La solution optimale est à un sommet
de la région réalisable.

Observation 1.3 : Même si tout un côté est optimal,
on peut toujours choisir une solution correspondant à un sommet.

1.4 Formulation générale

Avec $n$ produits et $m$ ressources, le programme linéaire général s'écrit :
$$\max z = c^T x \quad \text{s.c.q.} \quad Ax \leq b, \quad x \geq 0$$
avec $A$ matrice $(m \times n)$,
$b$ vecteur $(m \times 1)$,
$c$ et $x$ vecteurs $(n \times 1)$.

2. Algorithme du Simplexe

2.1 Principe

L'algorithme du Simplexe détermine la solution optimale
en allant de sommet en sommet adjacent de la région réalisable.

Un sommet est un point intersection de deux contraintes
à l'égalité vérifiant toutes les contraintes.
Une arête est un segment de droite situé à la frontière
de la région réalisable.
Deux sommets adjacents sont reliés par une arête.

2.2 Variables d'écart

On transforme les inégalités en égalités par ajout de
variables d'écart non négatives. Exemple :
$$x_1 \leq 4 \implies x_1 + x_3 = 4, \quad x_3 \geq 0$$

Le problème sous forme standard devient :
$$\max z = 3x_1 + 5x_2$$
$$\text{s.c.q.} \quad
x_1 + x_3 = 4, \quad
2x_2 + x_4 = 12, \quad
3x_1 + 2x_2 + x_5 = 18, \quad
x_1, \ldots, x_5 \geq 0$$

2.3 Solutions de base

On fixe $n$ variables à zéro
(variables hors base, v.h.b.) ;
les $m$ variables restantes sont les
variables de base (v.d.b.).

Une solution de base réalisable est une solution de base
vérifiant les contraintes de positivité.
Elle correspond géométriquement à un sommet de la région réalisable.

Deux solutions de base sont adjacentes si leurs variables de base
ne diffèrent que par une seule variable.

2.4 Initialisation

Si le problème est sous forme d'inégalités avec $b_i \geq 0$,
on part de l'origine $(x_1, x_2) = (0, 0)$,
ce qui donne la solution de base réalisable de départ :
$$(0, 0, 4, 12, 18) \quad \text{avec} \quad z = 0$$

2.5 Une itération Simplexe

Chaque itération comprend trois étapes :

Choix de la variable entrante :
On choisit la variable hors base avec le coefficient objectif
le plus élevé (la plus forte augmentation de $z$).

Choix de la variable sortante :
On calcule le minimum du rapport
membre de droite / coefficient de la colonne entrante
(pour les coefficients strictement positifs).
La variable sortante est la première à s'annuler.

Calcul du nouveau sommet :
On exprime le système en fonction des nouvelles variables de base
par opérations élémentaires (multiplication d'une ligne
par une constante, addition d'un multiple d'une ligne à une autre).

Test d'optimalité :
La solution courante est optimale si tous les coefficients
de la ligne objectif sont négatifs ou nuls
(lorsque $z$ est exprimée en fonction des seules variables hors base).

Application sur l'exemple : après deux itérations,
on obtient la solution optimale :
$$(x_1, x_2, x_3, x_4, x_5) = (2, 6, 2, 0, 0), \quad z^* = 36$$

3. Algorithme du Simplexe en tableaux

3.1 Notion de tableau Simplexe

Le tableau Simplexe contient les coefficients
des équations algébriques sans le nom des variables :
coefficients de la fonction objectif (ligne 0),
coefficients des contraintes (lignes 1 à $m$),
membre de droite (dernière colonne).

Tableau initial de l'exemple :
$$\begin{array}{c|ccccc|c}
& x_1 & x_2 & x_3 & x_4 & x_5 & \\
\hline
z & -3 & -5 & 0 & 0 & 0 & 0 \\
& 1 & 0 & 1 & 0 & 0 & 4 \\
& 0 & 2 & 0 & 1 & 0 & 12 \\
& 3 & 2 & 0 & 0 & 1 & 18 \\
\end{array}$$

On identifie une variable de base à une colonne
de la matrice identité avec coefficient objectif nul.

3.2 Pivotage

À chaque itération, on sélectionne :
la colonne pivot (variable entrante : coefficient
le plus négatif dans la ligne objectif),
la ligne pivot (variable sortante : minimum des rapports
membre de droite / coefficient de la colonne pivot),
l'élément pivot à leur intersection.

On divise la ligne pivot par le pivot,
puis on élimine la variable entrante des autres lignes
en retranchant un multiple de la ligne pivot.

Tableau final après deux itérations :
$$\begin{array}{c|ccccc|c}
& x_1 & x_2 & x_3 & x_4 & x_5 & \\
\hline
z & 0 & 0 & 0 & 3/2 & 1 & 36 \\
& 0 & 0 & 1 & 1/3 & -1/3 & 2 \\
& 0 & 1 & 0 & 1/2 & 0 & 6 \\
& 1 & 0 & 0 & -1/3 & 1/3 & 2 \\
\end{array}$$

Solution optimale : $(x_1, x_2, x_3, x_4, x_5) = (2, 6, 2, 0, 0)$,
$z^* = 36$.

3.3 Problèmes non bornés

Si tous les coefficients de la colonne entrante sont négatifs ou nuls,
aucune variable de base n'est bloquante :
la variable entrante et l'objectif peuvent croître sans limite.
On parle de problème non borné.
Dans la pratique, cela indique généralement une erreur de formulation.

4. Analyse postoptimale

4.1 Introduction

L'analyse postoptimale étudie la sensibilité de la solution
optimale à des modifications des données
(coefficients objectif ou membres de droite),
sans résoudre à nouveau le problème, à condition
que la base optimale ne change pas.

4.2 Prix cachés — variation du second membre

Le prix caché $y_i^*$ mesure l'augmentation de la fonction objectif
si l'on accroît d'une unité la capacité disponible $b_i$.
Il se lit dans la ligne objectif du tableau Simplexe optimal :
$y_i^*$ est le coefficient de la variable d'écart
de la contrainte $i$.

Pour l'exemple, les prix cachés sont :
$$y_1^* = 0, \quad y_2^* = \frac{3}{2}, \quad y_3^* = 1$$

Interprétation : augmenter d'une unité la capacité de l'atelier 2
accroît le profit de $3/2$ ; augmenter l'atelier 3 l'accroît de $1$ ;
augmenter l'atelier 1 ne change pas le profit (contrainte non liante).

Domaines de validité :
$$b_1 \in [2, +\infty], \quad b_2 \in [6, 18], \quad b_3 \in [12, 24]$$

Remarque : une contrainte non liante (variable d'écart non nulle)
a toujours un prix caché nul.

4.3 Variation des coefficients objectif

La valeur de $x_j^*$ à l'optimum mesure l'augmentation de $z$
si l'on accroît d'une unité la marge unitaire $c_j$.

Pour l'exemple : $x_1^* = 2$ et $x_2^* = 6$.

Analyse de sensibilité :
$$c_1 \in \left[0,\; \frac{15}{2}\right], \quad c_2 \in [2, +\infty[$$

Tant que $c_j$ reste dans ces intervalles, la base optimale
et la solution optimale ne changent pas.

4.4 Coût réduit des variables hors base

Le coût réduit $d_j$ d'une variable hors base $x_j$
mesure l'augmentation de $z$ si l'on accroît d'une unité $x_j$.
Il est l'opposé du coefficient de $x_j$ dans la ligne objectif
du tableau Simplexe optimal.

Si $d_j < 0$, produire $x_j$ diminue le profit.
Pour rendre $x_j$ intéressant à produire, il faut augmenter
sa marge d'au moins $|d_j|$.

Pour l'exemple avec un troisième châssis mixte :
$$d_3 = -2, \quad d_5 = -\frac{3}{2}, \quad d_6 = -1$$

Seules les productions des châssis 1 et 2 sont rentables.

Ref. : Abdelaziz BEN KHALIFA — 2007-2008

---

Pour plus de détails, consulter le PDF ci-joint.

---