Programmation linéaire en L3 : cours et exercices corrigés

Objectifs du chapitre

Formaliser un programme linéaire sous forme standard et définir les solutions de base admissibles.
Énoncer le théorème fondamental de la programmation linéaire (optimum atteint en un sommet).
Dérouler l'algorithme du simplexe (variable entrante, test du ratio, pivot) et détecter un problème non borné.
Écrire le dual d'un programme linéaire, démontrer la dualité faible et utiliser la dualité forte et les écarts complémentaires.
Énoncer les conditions de Karush-Kuhn-Tucker pour un problème d'optimisation convexe.

Le cours

1. Polyèdres et forme standard

Polyèdre : intersection finie de demi-espaces fermés, $P = \{x \in \mathbb{R}^n \mid Ax \le b\}$ ; il est convexe et fermé. Un polyèdre borné est un polytope.
Point extrême (sommet) : $x \in P$ qui n'est le milieu d'aucun segment $[y ; z] \subset P$ avec $y \neq z$ .
Forme standard :

$\max_{x \in \mathbb{R}^n} \; {}^tc\,x \quad \text{sous} \quad Ax = b, \; x \ge 0$
avec $A \in \mathcal{M}_{m,n}(\mathbb{R})$ de rang $m \le n$ .

Passage en forme standard : une contrainte ${}^ta_i x \le b_i$ devient ${}^ta_i x + s_i = b_i$ avec une variable d'écart $s_i \ge 0$ ; une variable libre s'écrit $x_j = x_j^+ - x_j^-$ avec $x_j^\pm \ge 0$ ; minimiser ${}^tc\,x$ revient à maximiser $-{}^tc\,x$ .

2. Solutions de base admissibles et théorème fondamental

Base : ensemble $B$ de $m$ indices tel que la sous-matrice $A_B$ soit inversible ; $N$ désigne les autres indices. La solution de base associée est $x_N = 0$ , $x_B = A_B^{-1}b$ .
Solution de base admissible (SBA) : solution de base avec $x_B \ge 0$ . Théorème : les SBA sont exactement les sommets du polyèdre $\{Ax = b, \, x \ge 0\}$ . Il y en a au plus $\binom{n}{m}$ .
Dégénérescence : une SBA est dégénérée si une variable de base est nulle ; plusieurs bases peuvent alors définir le même sommet.
Théorème fondamental : pour un programme linéaire sous forme standard,

1. si l'ensemble admissible est non vide, il possède au moins un sommet ;
2. si le problème admet une solution optimale, il existe une SBA optimale ;
3. si l'ensemble admissible est non vide et l'objectif majoré sur cet ensemble, une solution optimale existe.

L'ensemble des solutions optimales est une face du polyèdre : il peut y avoir une infinité d'optima (une arête entière, par exemple).

3. Algorithme du simplexe

On part d'une SBA de base $B$ .

Coûts réduits : ${}^t\bar{c}_N = {}^tc_N - {}^tc_B A_B^{-1}A_N$ ; l'objectif s'écrit $z = {}^tc_B A_B^{-1}b + {}^t\bar{c}_N x_N$ .
Optimalité (en maximisation) : si $\bar{c}_j \le 0$ pour tout $j \in N$ , la SBA courante est optimale.
Variable entrante : un indice $e$ avec $\bar{c}_e > 0$ (règle de Dantzig : le plus grand).
Variable sortante (test du ratio) : avec $\bar{A} = A_B^{-1}A$ et $\bar{b} = A_B^{-1}b$ , on choisit

$i^{\ast} \in \arg\min \left\{ \frac{\bar{b}_i}{\bar{a}_{ie}} \;\middle|\; \bar{a}_{ie} > 0 \right\}$
Si aucun $\bar{a}_{ie}$ n'est $> 0$ , le problème est non borné.

Pivot sur $\bar{a}_{i^{\ast}e}$ , puis itération.
Terminaison : sans dégénérescence, l'objectif augmente strictement et l'algorithme s'arrête (nombre fini de bases). En cas de dégénérescence, il peut cycler ; la règle de Bland (plus petit indice) l'évite.
Initialisation : si $0$ n'est pas admissible, une phase I (minimiser la somme de variables artificielles) fournit une SBA de départ ou prouve que le problème est irréalisable.

4. Dualité : énoncés et démonstration de la dualité faible

Primal $(P)$ : $\max {}^tc\,x$ sous $Ax \le b$ , $x \ge 0$ . Dual $(D)$ : $\min {}^tb\,y$ sous ${}^tA\,y \ge c$ , $y \ge 0$ . Le dual du dual est le primal.

Théorème (dualité faible). Si $x$ est admissible pour $(P)$ et $y$ admissible pour $(D)$ , alors ${}^tc\,x \le {}^tb\,y$ .

Démonstration.
1. Comme $x \ge 0$ et ${}^tA\,y - c \ge 0$ (composante par composante), le produit scalaire ${}^t({}^tA\,y - c)\,x = \sum_j ({}^tA\,y - c)_j x_j$ est une somme de termes positifs : ${}^tc\,x \le {}^t({}^tA\,y)\,x = {}^ty\,Ax$ .
2. Comme $y \ge 0$ et $b - Ax \ge 0$ : ${}^ty\,(b - Ax) \ge 0$ , donc ${}^ty\,Ax \le {}^ty\,b = {}^tb\,y$ .
3. En combinant : ${}^tc\,x \le {}^ty\,Ax \le {}^tb\,y$ . $\square$

Corollaires.

Si ${}^tc\,x = {}^tb\,y$ pour des points admissibles $x, y$ , ils sont optimaux tous les deux (certificat d'optimalité).
Si $(P)$ est non borné, $(D)$ est irréalisable ; si $(D)$ est non borné, $(P)$ est irréalisable.
Écarts complémentaires : l'égalité ${}^tc\,x = {}^tb\,y$ équivaut à l'égalité dans les étapes 1 et 2, c'est-à-dire, les termes étant positifs, à

$x_j\,({}^tA\,y - c)_j = 0 \;\; \forall j \qquad \text{et} \qquad y_i\,(b - Ax)_i = 0 \;\; \forall i$

Dualité forte : si $(P)$ (ou $(D)$ ) admet une solution optimale, alors l'autre aussi et $\max (P) = \min (D)$ . La preuve utilise le simplexe (coûts réduits à l'optimum) ou le lemme de Farkas : $Ax = b$ , $x \ge 0$ a une solution si et seulement s'il n'existe pas de $y$ avec ${}^tA\,y \ge 0$ et ${}^tb\,y < 0$ .
Ainsi $x^{\ast}$ et $y^{\ast}$ admissibles sont optimaux si et seulement s'ils vérifient les écarts complémentaires.

5. Conditions de Karush-Kuhn-Tucker

On considère $\min f(x)$ sous $g_i(x) \le 0$ ( $1 \le i \le p$ ), avec $f, g_i$ de classe $\mathcal{C}^1$ sur $\mathbb{R}^n$ .

Conditions KKT en $x^{\ast}$ admissible : il existe $\mu_1, \dots, \mu_p$ tels que

$\nabla f(x^{\ast}) + \sum_{i=1}^p \mu_i \nabla g_i(x^{\ast}) = 0, \qquad \mu_i \ge 0, \qquad \mu_i\, g_i(x^{\ast}) = 0$
(les multiplicateurs des contraintes inactives sont nuls).

Nécessité : si $x^{\ast}$ est un minimum local et si les contraintes sont qualifiées en $x^{\ast}$ (par exemple contraintes affines, ou gradients des contraintes actives linéairement indépendants, ou, dans le cas convexe, condition de Slater : existence de $\tilde{x}$ avec $g_i(\tilde{x}) < 0$ pour tout $i$ ), alors les conditions KKT sont satisfaites.
Suffisance : si $f$ et les $g_i$ sont convexes, tout point admissible vérifiant KKT est un minimum global.
Lien avec la programmation linéaire : pour un programme linéaire, les multiplicateurs KKT sont une solution du dual et la condition $\mu_i g_i(x^{\ast}) = 0$ est exactement la condition des écarts complémentaires.

Méthodes et exemples rédigés

Méthode : Écrire le dual et certifier l'optimalité

Exemple

Former le dual de : $\max\, 3x_1 + 2x_2$ sous $x_1 + 2x_2 \le 4$ , $2x_1 + x_2 \le 5$ , $x_1, x_2 \ge 0$ , puis vérifier que $x^{\ast} = (2, 1)$ est optimal.

Étape 1 (Données) : $c = \begin{pmatrix} 3 \\ 2 \end{pmatrix}$ , $b = \begin{pmatrix} 4 \\ 5 \end{pmatrix}$ , $A = \begin{pmatrix} 1 & 2 \\ 2 & 1 \end{pmatrix}$ .
Étape 2 (Dual) : une variable duale $y_i \ge 0$ par contrainte, une contrainte duale par variable primale : $\min\, 4y_1 + 5y_2$ sous $y_1 + 2y_2 \ge 3$ , $2y_1 + y_2 \ge 2$ , $y_1, y_2 \ge 0$ .
Étape 3 (Écarts complémentaires) : $x_1^{\ast}, x_2^{\ast} > 0$ impose que les deux contraintes duales soient des égalités : $y_1 + 2y_2 = 3$ et $2y_1 + y_2 = 2$ , d'où $y^{\ast} = \left(\frac{1}{3}, \frac{4}{3}\right) \ge 0$ (admissible). Les deux contraintes primales sont saturées en $x^{\ast}$ ( $2 + 2 = 4$ , $4 + 1 = 5$ ), ce qui est compatible avec $y^{\ast} > 0$ .
Conclusion : ${}^tc\,x^{\ast} = 6 + 2 = 8$ et ${}^tb\,y^{\ast} = \frac{4}{3} + \frac{20}{3} = 8$ . Par la dualité faible, $x^{\ast}$ et $y^{\ast}$ sont optimaux, de valeur commune $8$ .

Méthode : Dérouler l'algorithme du simplexe

Exemple

Résoudre par le simplexe : $\max\, Z = 3x_1 + 2x_2$ sous $x_1 + 2x_2 \le 4$ , $2x_1 + x_2 \le 5$ , $x_1, x_2 \ge 0$ .

Étape 1 (Forme standard) : avec des variables d'écart $s_1, s_2 \ge 0$ : $x_1 + 2x_2 + s_1 = 4$ et $2x_1 + x_2 + s_2 = 5$ . Base initiale $(s_1, s_2)$ : $x = (0, 0)$ , $s = (4, 5)$ , $Z = 0$ .
Étape 2 (Entrée) : coûts réduits $\bar{c}_1 = 3$ , $\bar{c}_2 = 2$ ; $x_1$ entre (plus grand coût réduit).
Étape 3 (Ratio) : ligne 1 : $\frac{4}{1} = 4$ ; ligne 2 : $\frac{5}{2} = 2{,}5$ . Le minimum est en ligne 2 : $s_2$ sort, pivot $2$ .
Étape 4 (Pivot) : $x_1 = 2{,}5 - 0{,}5x_2 - 0{,}5s_2$ ; la ligne 1 devient $1{,}5x_2 + s_1 - 0{,}5s_2 = 1{,}5$ ; $Z = 3(2{,}5 - 0{,}5x_2 - 0{,}5s_2) + 2x_2 = 7{,}5 + 0{,}5x_2 - 1{,}5s_2$ .
Étape 5 (Deuxième itération) : $\bar{c}_{x_2} = 0{,}5 > 0$ , $x_2$ entre ; seul ratio : $\frac{1{,}5}{1{,}5} = 1$ (ligne 1), $s_1$ sort. On obtient $x_2 = 1 - \frac{2}{3}s_1 + \frac{1}{3}s_2$ , $x_1 = 2 + \frac{1}{3}s_1 - \frac{2}{3}s_2$ et $Z = 8 - \frac{1}{3}s_1 - \frac{4}{3}s_2$ .
Conclusion : tous les coûts réduits sont négatifs : l'optimum est $(x_1^{\ast}, x_2^{\ast}) = (2, 1)$ , $Z^{\ast} = 8$ . Les opposés des coûts réduits des variables d'écart, $\left(\frac{1}{3}, \frac{4}{3}\right)$ , sont la solution duale.

Pièges fréquents

Si, pour la variable entrante, tous les coefficients de la colonne pivot sont $\le 0$ , le problème est non borné : on peut augmenter indéfiniment cette variable sans violer les contraintes.
Sens des inégalités au passage au dual : pour un primal $\max$ avec contraintes $\le$ et $x \ge 0$ , le dual est un $\min$ avec contraintes $\ge$ et $y \ge 0$ ; une contrainte primale d'égalité donne une variable duale de signe quelconque.
La dégénérescence peut faire stagner, voire cycler, le simplexe (pivots sans gain) : utiliser la règle de Bland garantit la terminaison.
Un optimum atteint en un sommet n'est pas forcément unique : pour $\max\, x_1 + x_2$ sous $x_1 + x_2 \le 1$ , $x \ge 0$ , tout le segment joignant $(1, 0)$ et $(0, 1)$ est optimal.
Si le primal est irréalisable, le dual n'est pas forcément non borné : les deux problèmes peuvent être irréalisables simultanément.

Questions de révision

Essaie de répondre de tête avant d'afficher la réponse.

Énoncer la dualité faible et sa preuve en une ligne.

${}^tc\,x \le {}^ty\,Ax \le {}^tb\,y$ pour $x, y$ admissibles, en utilisant $x \ge 0$ , ${}^tA\,y \ge c$ , puis $y \ge 0$ , $Ax \le b$ .

Énoncer la dualité forte en programmation linéaire.

Si le primal ou le dual admet une solution optimale, les deux en admettent et $\max\,{}^tc\,x = \min\,{}^tb\,y$ .

Quelle caractérisation géométrique ont les solutions de base admissibles ?

Ce sont exactement les sommets (points extrêmes) du polyèdre admissible.

Critère d'arrêt du simplexe en maximisation ?

Tous les coûts réduits sont $\le 0$ : la SBA courante est optimale.

Énoncer les conditions des écarts complémentaires.

$x_j({}^tA\,y - c)_j = 0$ pour tout $j$ et $y_i(b - Ax)_i = 0$ pour tout $i$ ; avec l'admissibilité, elles caractérisent l'optimalité du couple $(x, y)$ .

Quand les conditions KKT sont-elles suffisantes ?

Lorsque l'objectif et les contraintes $g_i$ sont convexes : un point admissible vérifiant KKT est alors un minimum global.

Exercices corrigés

Exercice 1 Forme standard d'un programme linéaire et variables d'écart

Palier 1 · découverte

Pour mettre la contrainte d'inégalité $2x_1 + 3x_2 \le 12$ sous forme standard d'égalité avec des variables positives, quelle transformation effectue-t-on ?

On introduit une variable d'écart $s \ge 0$ telle que $2x_1 + 3x_2 + s = 12$
On remplace simplement $\le$ par $=$ sans rien ajouter
On introduit une variable $s \le 0$ telle que $2x_1 + 3x_2 = 12 + s$
On élève la contrainte au carré

Un indice

Une contrainte $\le$ signifie que le membre de gauche est inférieur au membre de droite.

Voir la correction

Bonne réponse : A. On introduit une variable d'écart $s \ge 0$ telle que $2x_1 + 3x_2 + s = 12$

Dans la mise sous forme standard, toute contrainte d'inégalité $\le$ est transformée en égalité par l'addition d'une variable d'écart positive ( $s \ge 0$ ) : $2x_1 + 3x_2 + s = 12$ .

Exercice 2 Règle de la variable entrante dans le simplexe

Palier 2 · application

Dans l'algorithme du simplexe en maximisation, comment choisit-on la variable hors-base entrante selon la règle de Dantzig ?

On choisit la variable ayant le coût réduit strictement positif le plus grand ( $\bar{c}_e = \max_{j} \bar{c}_j > 0$ )
On choisit la variable ayant le coût réduit le plus négatif
On choisit la variable ayant la plus grande valeur dans le vecteur $b$
On choisit arbitrairement n'importe quelle variable de base

Un indice

Un coût réduit positif $\bar{c}_j > 0$ indique que faire croître $x_j$ augmentera la fonction objectif.

Voir la correction

Bonne réponse : A. On choisit la variable ayant le coût réduit strictement positif le plus grand ( $\bar{c}_e = \max_{j} \bar{c}_j > 0$ )

En maximisation, le critère de Dantzig prescrit de faire entrer en base la variable hors-base $x_e$ dont le coût réduit est le plus grand strictement positif : $\bar{c}_e = \max_{j \in N} \bar{c}_j > 0$ . Si tous les coûts réduits sont $\le 0$ , la solution actuelle est optimale.

Exercice 3 Test du ratio minimum et variable sortante

Palier 3 · approfondissement

Lors d'une itération du simplexe avec colonne pivot $A_e$ , la variable de base sortante est déterminée par :

Le minimum des ratios $\frac{\bar{b}_i}{\bar{a}_{i, e}}$ pour les lignes où $\bar{a}_{i, e} > 0$
Le maximum des ratios $\frac{\bar{b}_i}{\bar{a}_{i, e}}$
La ligne où $\bar{a}_{i, e}$ est le plus proche de 0
La ligne où le terme indépendant $\bar{b}_i$ est négatif

Un indice

En augmentant la variable entrante $x_e$ , les composantes de base deviennent $x_{B(i)} = \bar{b}_i - \bar{a}_{i, e} x_e$ .

Voir la correction

Bonne réponse : A. Le minimum des ratios $\frac{\bar{b}_i}{\bar{a}_{i, e}}$ pour les lignes où $\bar{a}_{i, e} > 0$

Pour préserver la positivité de toutes les variables (admissibilité), la variable de base qui quitte la base est celle dont la valeur s'annule en premier : $i^* = \arg \min \{ \frac{\bar{b}_i}{\bar{a}_{i,e}} \mid \bar{a}_{i,e} > 0 \}$ .

Exercice 4 Théorème des écarts complémentaires

Palier 4 · défi

Soient $x^*$ et $y^*$ des solutions admissibles respectives du problème primal ( $\max {}^t c x$ sous $Ax \le b, x \ge 0$ ) et dual ( $\min {}^t b y$ sous ${}^t A y \ge c, y \ge 0$ ). Quelle condition caractérise leur optimalité conjointe ?

$y_i^* (b - Ax^*)_i = 0$ pour tout $i$ et $x_j^* ({}^t A y^* - c)_j = 0$ pour tout $j$
$x^* = y^*$ obligatoirement
${}^t c x^* < {}^t b y^*$ , strictement
$\det(A) = 0$

Un indice

Pour $x^*, y^*$ admissibles : ${}^tc\,x^* \le {}^ty^* A x^* \le {}^tb\,y^*$ . Par dualité, l'optimalité conjointe équivaut à ${}^tc\,x^* = {}^tb\,y^*$ : les deux inégalités doivent être des égalités.

Voir la correction

Bonne réponse : A. $y_i^* (b - Ax^*)_i = 0$ pour tout $i$ et $x_j^* ({}^t A y^* - c)_j = 0$ pour tout $j$

D'après le théorème des écarts complémentaires, deux solutions admissibles sont optimales si et seulement si pour tout $i$ , $y_i^*(b_i - (Ax^*)_i) = 0$ (le produit du multiplicateur par la variable d'écart est nul) et pour tout $j$ , $x_j^*(({}^t A y^*)_j - c_j) = 0$ .