Démarrez le simplexe avec le grand M ou deux phases

Au chapitre précédent, le simplexe démarrait tout seul : en ne brassant rien, on obtenait un sommet réalisable, l’origine. C’est un luxe. Dès qu’une contrainte impose un minimum (« livrer au moins 2 hectolitres », « couvrir au moins 4 unités d’amidon »), l’origine n’est plus réalisable, et l’on ne sait même pas s’il existe un seul point qui respecte toutes les contraintes.

Ce chapitre présente les deux techniques classiques pour trouver un sommet de départ : la méthode des deux phases et la méthode du grand M. Elles reposent sur la même astuce, des variables « artificielles » que l’on s’efforce ensuite de faire disparaître.

Le problème : pas de base de départ évidente

Changeons de côté : la brasserie doit maintenant acheter ses céréales. Deux mélanges sont proposés par un fournisseur.

	Mélange A (par tonne)	Mélange B (par tonne)	Besoin minimal
Amidon (unités)	1	1	4
Arômes (unités)	1	3	6
Coût (centaines d’euros)	2	3

En notant $x_1$ et $x_2$ les tonnes achetées de chaque mélange, on cherche le panier le moins cher qui couvre les besoins :

$$\min \; w = 2x_1 + 3x_2 \quad \text{s.c.} \quad x_1 + x_2 \geq 4, \quad x_1 + 3x_2 \geq 6, \quad x_1, x_2 \geq 0$$

Pour passer en forme standard, on retranche cette fois une variable d’excédent (surplus) positive, qui mesure ce qu’on achète en trop :

$$x_1 + x_2 - s_1 = 4, \qquad x_1 + 3x_2 - s_2 = 6$$

Et c’est là que ça coince. Si l’on prend $s_1$ et $s_2$ comme variables de base, avec $x_1 = x_2 = 0$, on obtient $s_1 = -4$ et $s_2 = -6$ : la solution n’est pas réalisable. N’acheter rien ne couvre évidemment pas les besoins.

Attention

Une variable d’excédent entre avec un signe moins dans la contrainte. C’est ce qui l’empêche de servir de variable de base au départ, contrairement à une variable d’écart. Le même problème se pose pour une contrainte d’égalité, qui n’a ni écart ni excédent.

L’astuce des variables artificielles

On ajoute dans chaque contrainte problématique une variable artificielle $a_i \geq 0$, qui n’a aucun sens concret :

$$x_1 + x_2 - s_1 + a_1 = 4, \qquad x_1 + 3x_2 - s_2 + a_2 = 6$$

Cette fois, la base $\lbrace a_1, a_2 \rbrace$ est réalisable : avec toutes les autres variables à zéro, $a_1 = 4$ et $a_2 = 6$. Mais ce point ne correspond à rien, puisqu’il ne vérifie les contraintes d’origine que si $a_1 = a_2 = 0$. Tout le travail consiste donc à chasser les variables artificielles de la base, jusqu’à ce qu’elles valent zéro. Deux méthodes le font.

La méthode des deux phases

Phase 1 : trouver un point réalisable

On oublie provisoirement le vrai coût, et l’on minimise la somme des variables artificielles :

$$\min \; W = a_1 + a_2$$

Comme les $a_i$ sont positifs, $W$ vaut au moins 0, et $W = 0$ exactement quand on a trouvé un point réalisable du problème d’origine. On résout ce problème auxiliaire par le simplexe. Pour une minimisation, on fait entrer la variable de coût réduit le plus négatif, et l’on s’arrête quand tous sont positifs ou nuls.

Exemple

On exprime $W$ en fonction des variables hors base, en remplaçant $a_1$ et $a_2$ par leurs expressions :

$$\begin{aligned} a_1 &= 4 - x_1 - x_2 + s_1 \\ a_2 &= 6 - x_1 - 3x_2 + s_2 \\ W &= 10 - 2x_1 - 4x_2 + s_1 + s_2 \end{aligned}$$

Itération 1. Le coût réduit le plus négatif est celui de $x_2$ ($-4$). Rapports : $4/1 = 4$ pour $a_1$, $6/3 = 2$ pour $a_2$. C’est $a_2$ qui sort, avec $x_2 = 2 - \tfrac13 x_1 + \tfrac13 s_2 - \tfrac13 a_2$. Après substitution :

$$\begin{aligned} x_2 &= 2 - \tfrac13 x_1 + \tfrac13 s_2 - \tfrac13 a_2 \\ a_1 &= 2 - \tfrac23 x_1 + s_1 - \tfrac13 s_2 + \tfrac13 a_2 \\ W &= 2 - \tfrac23 x_1 + s_1 - \tfrac13 s_2 + \tfrac43 a_2 \end{aligned}$$

Itération 2. $x_1$ entre (coût réduit $-\tfrac23$). Rapports : $2 / \tfrac23 = 3$ pour $a_1$, $2 / \tfrac13 = 6$ pour $x_2$. C’est $a_1$ qui sort :

$$\begin{aligned} x_1 &= 3 + \tfrac32 s_1 - \tfrac12 s_2 - \tfrac32 a_1 + \tfrac12 a_2 \\ x_2 &= 1 - \tfrac12 s_1 + \tfrac12 s_2 + \tfrac12 a_1 - \tfrac12 a_2 \\ W &= 0 + a_1 + a_2 \end{aligned}$$

Les deux variables artificielles sont hors base, $W = 0$ : la phase 1 a trouvé le sommet réalisable $(3, 1)$.

La phase 1 part d'un point qui n'existe que grâce aux artificielles, hors de la zone réalisable, et fait baisser W = a₁ + a₂ de 10 à 2 puis à 0 : elle atterrit sur le sommet réalisable (3, 1).

Phase 2 : optimiser le vrai coût

On supprime les colonnes des variables artificielles (elles restent à zéro pour toujours) et l’on réécrit le vrai objectif en fonction des variables hors base :

$$w = 2x_1 + 3x_2 = 2\big(3 + \tfrac32 s_1 - \tfrac12 s_2\big) + 3\big(1 - \tfrac12 s_1 + \tfrac12 s_2\big) = 9 + \tfrac32 s_1 + \tfrac12 s_2$$

On repart alors avec le simplexe ordinaire. Ici, les coûts réduits $\tfrac32$ et $\tfrac12$ sont déjà positifs : pour une minimisation, c’est l’optimum. La brasserie achète 3 tonnes du mélange A et 1 tonne du mélange B, pour 900 €, et couvre exactement ses deux besoins ($s_1 = s_2 = 0$). Vous pouvez vérifier aux sommets : $(6, 0)$ et $(0, 4)$ coûtent tous les deux 12.

L'origine n'est pas réalisable : c'est pourquoi le simplexe ne peut pas y démarrer. En faisant descendre la droite de coût, on quitte la zone au sommet (3, 1), pour w = 9.

Le verdict de la phase 1

La phase 1 a un second rôle, aussi précieux que le premier : elle décide si le problème a des solutions.

• Si le minimum de $W$ vaut 0, le problème est réalisable, et l’on passe à la phase 2.
• Si le minimum de $W$ est strictement positif, aucune combinaison ne permet d’annuler les artificielles : l’ensemble réalisable est vide, et l’on s’arrête.

À retenir

Deux phases : on ajoute une variable artificielle dans chaque contrainte « supérieur ou égal » ou d’égalité. Phase 1 : minimiser la somme des artificielles ; un optimum strictement positif prouve que le problème est irréalisable. Phase 2 : supprimer les artificielles, réécrire le vrai objectif dans la base trouvée, et poursuivre le simplexe.

La méthode du grand M

La méthode du grand M fait les deux phases en une seule, en pénalisant les variables artificielles dans le vrai objectif. On choisit un nombre $M$ « aussi grand qu’on veut » et l’on résout :

$$\min \; 2x_1 + 3x_2 + M a_1 + M a_2$$

Pour un problème de maximisation, on retranche au contraire $M a_i$ à l’objectif. Dans les deux cas, garder une artificielle non nulle coûte si cher que le simplexe la chasse en priorité.

Exemple

En exprimant l’objectif en fonction des variables hors base, on obtient

$$10M + (2 - 2M)x_1 + (3 - 4M)x_2 + M s_1 + M s_2$$

On compare les coûts réduits comme des expressions en $M$, avec $M$ très grand : $3 - 4M$ est le plus négatif, donc $x_2$ entre, $a_2$ sort (mêmes rapports que tout à l’heure). À l’itération suivante, $x_1$ a un coût réduit $1 - \tfrac23 M$, plus négatif que celui de $s_2$ ($1 - \tfrac13 M$) : $x_1$ entre et $a_1$ sort. L’objectif final s’écrit

$$9 + \tfrac32 s_1 + \tfrac12 s_2 + \big(M - \tfrac32\big) a_1 + \big(M - \tfrac12\big) a_2$$

Tous les coûts réduits sont positifs dès que $M \geq \tfrac32$ : on retrouve le même optimum, $(3, 1)$ pour un coût de 9.

Les deux méthodes suivent ici exactement le même chemin. Laquelle choisir ?

	Deux phases	Grand M
Nombre de résolutions	deux problèmes successifs	un seul problème
Calculs à la main	nombres simples	expressions en $M$ à comparer
Sur ordinateur	stable	une valeur numérique de $M$ trop grande crée des erreurs d’arrondi, trop petite fausse le résultat
Détection d’un problème irréalisable	$W > 0$ en fin de phase 1	une artificielle reste non nulle à l’optimum

C’est pourquoi les logiciels utilisent plutôt des variantes des deux phases, tandis que le grand M reste pratique pour les petits exercices à la main.

Avec une valeur numérique de M trop petite (ici sous 3/2), il revient moins cher de garder des artificielles non nulles : le solveur renvoie un faux optimum. Au-delà, on retrouve le vrai coût 9.

Piège

Pour un problème de maximisation, la pénalité s’écrit $-M a_i$, pas $+M a_i$. Avec le mauvais signe, le simplexe cherche au contraire à garder les variables artificielles, puisqu’elles augmentent l’objectif, et renvoie un « optimum » qui ne respecte pas les contraintes.

Quelques subtilités

Deux situations peuvent vous surprendre en fin de phase 1.

• Une artificielle reste en base avec la valeur 0. Le point trouvé est bien réalisable, mais la base contient une variable qui n’existe pas dans le problème d’origine. On la fait sortir par un pivot sur n’importe quel coefficient non nul de sa ligne (dans une colonne non artificielle). Si toute la ligne est nulle, c’est que la contrainte correspondante était redondante (combinaison des autres), et l’on peut la supprimer.
• Une contrainte d’égalité. Elle reçoit une artificielle, mais ni écart ni excédent. Une fois l’artificielle chassée, la contrainte reste satisfaite exactement, comme on le souhaite.

Enfin, rien ne vous oblige à ajouter une artificielle partout : une contrainte « inférieur ou égal » à second membre positif apporte déjà sa variable d’écart à la base de départ. On n’ajoute d’artificielles que là où il en manque, ce qui raccourcit la phase 1.

En entretien

« Quand l’origine n’est pas réalisable, on ajoute des variables artificielles pour avoir une base de départ, puis on les chasse : soit en minimisant d’abord leur somme (deux phases), soit en les pénalisant par un coefficient énorme dans l’objectif (grand M). Si on n’arrive pas à les annuler, le problème n’a pas de solution. »

En résumé

• Une contrainte « supérieur ou égal » reçoit une variable d’excédent avec un signe moins ; elle ne fournit pas de base de départ réalisable, pas plus qu’une égalité.
• On ajoute alors des variables artificielles, qui donnent une base de départ mais doivent finir à zéro.
• Deux phases : la phase 1 minimise la somme des artificielles ; la phase 2 repart du sommet trouvé avec le vrai objectif.
• Un optimum de phase 1 strictement positif prouve que le problème est irréalisable.
• Grand M : on pénalise les artificielles par $+M$ (minimisation) ou $-M$ (maximisation) et l’on résout en une fois, en comparant des expressions en $M$.
• Une artificielle restée en base à la valeur 0 se chasse par un pivot, ou signale une contrainte redondante.

Exercices

Exercice · Écrire le problème auxiliaire

facile

On considère $\max z = x_1 + 4x_2$ sous $x_1 + x_2 \leq 6$, $x_1 + 2x_2 \geq 4$, $x_1 - x_2 = 1$, $x_1, x_2 \geq 0$. Mettez le problème sous forme standard en n’ajoutant de variables artificielles que là où c’est nécessaire, puis écrivez l’objectif de la phase 1 et celui du grand M.

Voir la solution

• $x_1 + x_2 + e_1 = 6$ : l’écart $e_1$ peut servir de base de départ ($e_1 = 6$), pas besoin d’artificielle.
• $x_1 + 2x_2 - s_2 + a_2 = 4$ : l’excédent $s_2$ a un signe moins, il faut une artificielle $a_2$.
• $x_1 - x_2 + a_3 = 1$ : une égalité n’a ni écart ni excédent, il faut une artificielle $a_3$.

La base de départ est $\lbrace e_1, a_2, a_3 \rbrace$, avec $e_1 = 6$, $a_2 = 4$, $a_3 = 1$.

Phase 1 : $\min W = a_2 + a_3$. Grand M : comme on maximise, on pénalise en retranchant, $\max \; x_1 + 4x_2 - M a_2 - M a_3$.

En code

Python

import numpy as np
from scipy.optimize import linprog

# Colonnes : x1, x2, e1, s2, a2, a3 (artificielles seulement en lignes 2 et 3)
A_eq = np.array([[1,  1, 1,  0, 0, 0],     # x1 + x2 + e1 = 6
                 [1,  2, 0, -1, 1, 0],     # x1 + 2 x2 - s2 + a2 = 4
                 [1, -1, 0,  0, 0, 1]])    # x1 - x2 + a3 = 1
b_eq = np.array([6, 4, 1])
print(A_eq[:, [2, 4, 5]])                  # identité : base de départ {e1, a2, a3} = (6, 4, 1)

# Phase 1 : min W = a2 + a3
p1 = linprog([0, 0, 0, 0, 1, 1], A_eq=A_eq, b_eq=b_eq)
print(p1.fun, p1.x[:2])                    # 0.0 : W = 0, le problème est réalisable

# Grand M : max x1 + 4 x2 - M a2 - M a3, soit min -x1 - 4 x2 + M a2 + M a3
M = 100
gm = linprog([-1, -4, 0, 0, M, M], A_eq=A_eq, b_eq=b_eq)
print(gm.x[:2], -gm.fun)                   # [3.5 2.5] 13.5, artificielles nulles

R

# min cout'x sous A x = b, x >= 0, en énumérant les solutions de base
meilleure_base <- function(A, b, cout) {
  meilleur <- NULL
  for (B in combn(ncol(A), nrow(A), simplify = FALSE)) {
    if (abs(det(A[, B])) < 1e-9) next
    x <- numeric(ncol(A)); x[B] <- solve(A[, B], b)
    if (all(x >= -1e-9) && (is.null(meilleur) || sum(cout * x) < sum(cout * meilleur)))
      meilleur <- x
  }
  meilleur
}
# Colonnes : x1, x2, e1, s2, a2, a3
A <- rbind(c(1, 1, 1, 0, 0, 0), c(1, 2, 0, -1, 1, 0), c(1, -1, 0, 0, 0, 1))
b <- c(6, 4, 1)
A[, c(3, 5, 6)]                                  # identité : base de départ {e1, a2, a3}
x1 <- meilleure_base(A, b, c(0, 0, 0, 0, 1, 1))  # phase 1 : min a2 + a3
sum(x1[5:6])                                     # 0 : réalisable
M <- 100                                         # grand M
x <- meilleure_base(A, b, c(-1, -4, 0, 0, M, M))
x[1:2]; x[1] + 4 * x[2]                          # 3.5 2.5 ; 13.5

Exercice · Détecter l'impossible

moyen

Appliquez la phase 1 au problème $\max z = x_1 + x_2$ sous $x_1 + x_2 \leq 2$, $x_1 + x_2 \geq 3$, $x_1, x_2 \geq 0$. Conclure.

Voir la solution

Forme standard : $x_1 + x_2 + e = 2$ et $x_1 + x_2 - s + a = 3$. Base de départ $\lbrace e, a \rbrace$, et l’objectif de phase 1 est $W = a = 3 - x_1 - x_2 + s$.

$x_1$ entre (coût réduit $-1$, à égalité avec $x_2$ ; on prend le plus petit indice). Rapports : $2/1 = 2$ pour $e$, $3/1 = 3$ pour $a$. C’est $e$ qui sort : $x_1 = 2 - x_2 - e$. Alors $W = 3 - (2 - x_2 - e) - x_2 + s = 1 + e + s$.

Tous les coûts réduits sont positifs : la phase 1 est terminée avec $W = 1 > 0$. L’artificielle ne peut pas être annulée, le problème est irréalisable. Ce n’est pas étonnant : on ne peut pas avoir à la fois $x_1 + x_2 \leq 2$ et $x_1 + x_2 \geq 3$.

En code

Python

from scipy.optimize import linprog

# Colonnes : x1, x2, e, s, a  (x1 + x2 + e = 2 ; x1 + x2 - s + a = 3)
A_eq = [[1, 1, 1, 0, 0],
        [1, 1, 0, -1, 1]]
b_eq = [2, 3]
p1 = linprog([0, 0, 0, 0, 1], A_eq=A_eq, b_eq=b_eq)   # phase 1 : min W = a
print(p1.fun, p1.x)          # 1.0 : W > 0, le problème est irréalisable

# linprog le détecte directement sur le problème d'origine
res = linprog([-1, -1], A_ub=[[1, 1], [-1, -1]], b_ub=[2, -3])
print(res.status)            # 2 = irréalisable

R

# Colonnes : x1, x2, e, s, a  (x1 + x2 + e = 2 ; x1 + x2 - s + a = 3)
A <- rbind(c(1, 1, 1, 0, 0), c(1, 1, 0, -1, 1))
b <- c(2, 3)
W_min <- Inf
for (B in combn(ncol(A), nrow(A), simplify = FALSE)) {   # toutes les bases
  if (abs(det(A[, B])) < 1e-9) next
  x <- numeric(5); x[B] <- solve(A[, B], b)
  if (all(x >= -1e-9)) W_min <- min(W_min, x[5])         # W = a
}
W_min                        # 1 : W > 0, le problème est irréalisable

Exercice · Un contrat d'ambrée

difficile

Un bar du centre-ville impose à la brasserie de lui livrer au moins 2 hl d’ambrée par semaine. Le programme devient : $\max z = 3x_1 + 2x_2$ sous $x_1 + x_2 \leq 4$, $x_1 + 3x_2 \leq 9$, $x_1 \leq 3$, $x_2 \geq 2$, $x_1, x_2 \geq 0$. Résolvez-le par la méthode des deux phases. Combien ce contrat coûte-t-il à la brasserie ?

Voir la solution

Forme standard : $x_1 + x_2 + e_1 = 4$, $x_1 + 3x_2 + e_2 = 9$, $x_1 + e_3 = 3$, $x_2 - s_4 + a = 2$. Base de départ $\lbrace e_1, e_2, e_3, a \rbrace$.

Phase 1. $W = a = 2 - x_2 + s_4$. $x_2$ entre ; rapports $4/1$, $9/3 = 3$ et $2/1 = 2$ : $a$ sort, et $x_2 = 2 + s_4 - a$. Alors $W = a$ : minimum 0, le problème est réalisable. En supprimant $a$ : $x_2 = 2 + s_4$, $e_1 = 2 - x_1 - s_4$, $e_2 = 3 - x_1 - 3s_4$, $e_3 = 3 - x_1$.

Phase 2. $z = 3x_1 + 2(2 + s_4) = 4 + 3x_1 + 2s_4$. $x_1$ entre ; rapports $2$ pour $e_1$, $3$ pour $e_2$, $3$ pour $e_3$ : $e_1$ sort, avec $x_1 = 2 - s_4 - e_1$. D’où $z = 4 + 3(2 - s_4 - e_1) + 2s_4 = 10 - e_1 - s_4$.

Les coûts réduits sont négatifs : l’optimum est $x_1 = 2$, $x_2 = 2$, $z = 10$. Il reste $e_2 = 1$ sac de malt et $e_3 = 1$ lot de houblon. Sans le contrat, le bénéfice était de 11 : le contrat coûte 100 € par semaine. Le coût réduit $-1$ de $s_4$ dit même plus : chaque hectolitre d’ambrée exigé en plus coûterait encore 100 € (tant que la base reste la même).

En code

Python

from scipy.optimize import linprog

A_ub = [[1, 1], [1, 3], [1, 0]]
b_ub = [4, 9, 3]
sans = linprog([-3, -2], A_ub=A_ub, b_ub=b_ub)
print(sans.x, -sans.fun)                       # [3. 1.] 11.0

for d in [2, 2.25, 2.5]:                       # x2 >= d, écrit -x2 <= -d
    res = linprog([-3, -2], A_ub=A_ub + [[0, -1]], b_ub=b_ub + [-d])
    print(d, res.x, -res.fun, res.slack[:3])
# 2    [2. 2.]      10.0  [0. 1. 1.]  : il reste 1 sac de malt et 1 lot de houblon
# 2.25 [1.75 2.25]  9.75  [0. 0.5 1.25]
# 2.5  [1.5 2.5]    9.5   [0. 0. 1.5]  : -1 (100 €) par hectolitre exigé en plus

R

sommets_pl <- function(A, b) {                  # sommets du polygone A x <= b
  S <- NULL
  for (i in combn(nrow(A), 2, simplify = FALSE)) {
    if (abs(det(A[i, ])) < 1e-9) next
    x <- solve(A[i, ], b[i])
    if (all(A %*% x <= b + 1e-9)) S <- rbind(S, x)
  }
  S
}
A <- rbind(c(1, 1), c(1, 3), c(1, 0), c(0, -1), c(-1, 0), c(0, -1))
for (d in c(0, 2, 2.25, 2.5)) {                 # contrat x2 >= d (d = 0 : sans contrat)
  S <- sommets_pl(A, c(4, 9, 3, -d, 0, 0))
  z <- S %*% c(3, 2)
  cat("d =", d, ": x =", S[which.max(z), ], ", z =", max(z), "\n")
}
# d = 0 : x = 3 1 , z = 11
# d = 2 : x = 2 2 , z = 10
# d = 2.25 : x = 1.75 2.25 , z = 9.75
# d = 2.5 : x = 1.5 2.5 , z = 9.5