Décomposition

des
Grands
Systèmes
Cours & TD

Master Engeneering en Recherche Opérationnelle

(ERO)
Yacine Chaiblaine
USTHB
Faculté de mathématiques
Master ERO

Université des sciences et de la technologie Houari-Boumédiène

Faculté de Mathématiques
Département de Recherche Opérationnelle
Plan de cours

Chapitre 0 : Motivation du cours

— Pourquoi étudier la décomposition des grands systèmes linéaires ?
— Les défis des grands systèmes
— L’importance de la décomposition
— Objectifs du cours

Chapitre 1 : Introduction à la Programmation

Linéaire (PL)
— Définition et applications de la Programmation Linéaire
— Convexité et ensembles convexes
— Points extrêmes et enveloppe convexe
— Formes standard de la Programmation Linéaire
— Applications graphiques de la Programmation Linéaire

Chapitre 2 : L’Algorithme du Simplexe

— Introduction à la Méthode du Simplexe
— Détail de l’algorithme du Simplexe
— Méthode Révisé du Simplexe
— Méthode du Dual Simplexe
— Algorithme Primal-Dual

Chapitre 3 : Programmation en Nombres Entiers

Chapitre 4 : Introduction à la Décomposition et

aux Problèmes Pratiques
— Pourquoi la décomposition est-elle nécessaire ?

1
2

— Problèmes pratiques nécessitant une décomposition : Le problème de

découpe de stock

Chapitre 5 : Décomposition de Dantzig-Wolfe

Chapitre 6 : Décomposition de Benders
Chapitre 7 : Techniques de Décomposition Avancées
Chapitre 8 : Études de Cas et Applications Pra-
tiques
— Étude de cas 1 : Problème de transport avec Dantzig-Wolfe
— Étude de cas 2 : Problème de découpe de stock avec Benders

Projet Final
— Application des techniques de décomposition à un problème réel choisi
(découpe de stock, transport, optimisation de flux)

Références :
— Linear Programming and Game Theory (Chakravorty and Chosh).
— Linear Programming (VASEK CHVATAL).
— Convex Optimization (Stephen Boyd)
Chapitre 1

Rappels sur la
programmation linéaire

L’optimisation joue un rôle fondamental dans notre vie quotidienne. Que ce

soit pour choisir la meilleure voiture en termes de rapport qualité-prix, planifier
un itinéraire rapide ou économique, ou encore allouer des ressources de manière
efficace, nous cherchons constamment à prendre les meilleures décisions. Ce
type de prise de décision dépasse les choix individuels et est essentiel dans des
domaines tels que la finance, la logistique ou la production. Dans ces secteurs,
les décideurs cherchent à maximiser les profits, minimiser les coûts ou améliorer
l’efficacité opérationnelle.

Ces situations peuvent être formalisées sous la forme de problèmes d’opti-

misation, où l’objectif est soit de maximiser, soit de minimiser une fonction ob-
jectif, tout en respectant un ensemble de contraintes. En termes mathématiques,
ces situations réelles sont traduites en modèles mathématiques. Les contraintes,
comme les ressources limitées ou le temps, sont représentées par des systèmes
d’équations ou d’inéquations, tandis que la fonction objectif décrit le but à
atteindre (par exemple, maximiser le profit ou minimiser le coût).

3
4 CHAPITRE 1. RAPPELS SUR LA PROGRAMMATION LINÉAIRE

Problème Réel

Comprendre le problème Analyser les contraintes et objectifs Identifier les variables et paramètres

Élaborer un modèle mathématique

Implémentation pas possible

Trouver la solution optimale Utiliser des techniques d'optimisation

Analyser la solution

Implémentation possible

Implémenter la solution

Figure 1.1 – Principales étapes de la résolution d’un problème d’optimisation

réel

Un problème d’optimisation se présente généralement sous la forme sui-

vante :

Maximiser (ou Minimiser) f (x)

sous la contrainte x ∈ S,
où S représente l’ensemble des solutions admissibles, également appelé la région
admissible.

1.0.1 Concepts clés en optimisation

Définition 1. Ensemble convexe : Un ensemble S est dit convexe si,

pour tout couple de points x1 , x2 ∈ S, le segment de droite qui les relie est
entièrement contenu dans S. i.e., pour tout λ ∈ [0, 1],

λx1 + (1 − λ)x2 ∈ S.
 5

Ensemble Ensemble non

convexe convexe

Figure 1.2 – Exemple d’un ensemble convexe et d’un ensemble non convexe

Proposition 1. L’intersection
N
\
Ki
i=1

d’une famille d’ensembles convexes Ki est aussi convexe.

Considérons l’ensemble
K1 = {x ∈ Rn | Ax ≤ b}.
Montrons qu’il est convexe.
Démonstration. Soit 0 ≤ t ≤ 1.
Si x ∈ K1 =⇒ Ax ≤ b =⇒ (1 − t)Ax ≤ (1 − t)b,
et si y ∈ K1 =⇒ Ay ≤ b =⇒ tAy ≤ tb.
On additionne les deux lignes :
(1 − t)Ax + tAy = A((1 − t)x + ty) ≤ (1 − t)b + tb = b =⇒ (1 − t)x + ty ∈ K1 .
De même, l’ensemble
K2 = {x ∈ Rn | x ≥ 0}
est aussi convexe.
Grâce à la proposition, on peut déduire que
K = {x ≥ 0 | Ax ≤ b}
est convexe, car K est l’intersection des ensembles K1 et K2 .
6 CHAPITRE 1. RAPPELS SUR LA PROGRAMMATION LINÉAIRE

Définition 2. Fonction convexe Une fonction f : S → R est convexe

si, pour tout couple de points x1 , x2 ∈ S et pour tout λ ∈ [0, 1],

f (λx1 + (1 − λ)x2 ) ≤ λf (x1 ) + (1 − λ)f (x2 ).

Théoreme 1. Soit f une fonction continue définie sur un domaine K ⊂

Rn fermé et borné, alors f atteint ses valeurs minimale et maximale.

∃x̄ ∈ K f (x̄) = max f (x), ∃ȳ ∈ K f (ȳ) = min f (x).

x∈K x∈K

Toutefois, ce théorème sera d’une importance limitée dans le cours car il arrivera
souvent que la région admissible K n’est pas bornée.
Les fonctions convexes présentent la propriété qu’un minimum local est
aussi un minimum global, ce qui les rend particulièrement importantes dans
les problèmes d’optimisation.

Fonction Convexe Fonction Non-Convexe

f (x) f (x)
3
5
2
x
−2 −1 1 2
1
−5
x
−2 −1 1 2

Figure 1.3 – Exemple d’une fonction convexe et une fonction non convexe

Fonction affine : Une fonction f (x) est dite affine si elle peut s’écrire sous
la forme f (x) = aT x + b, où a est un vecteur et b un scalaire. Les fonctions
affines sont linéaires à une constante près et apparaissent fréquemment dans les
problèmes d’optimisation.

Système d’inéquations linéaires : Un système d’inéquations linéaires est

un ensemble de contraintes qui peut s’écrire sous la forme :

Ax ≤ b,

où A est une matrice et b est un vecteur. Un résultat important en optimisation

est que l’ensemble des solutions à un système d’inéquations linéaires forme
 7

un ensemble convexe. Cette propriété est fondamentale en programmation

linéaire.

Définition 3. Un hyperplan dans Rn est défini comme l’ensemble des

points x ∈ Rn qui satisfont une équation affine de la forme :

H = {x ∈ Rn | aT x = b},

où a ∈ Rn est un vecteur non nul, et b ∈ R est un scalaire. Géométriquement,

un hyperplan est une sous-variété de dimension n − 1 de l’espace Rn , c’est-
à-dire une ”coupure” qui divise l’espace en deux demi-espaces.

Dans 2 dimensions (n = 2), une équation linéaire en x1 , x2 de la forme :

a1 x1 + a2 x2 = b
représente une ligne droite.
Dans 3 dimensions (n = 3), une équation linéaire en x1 , x2 , x3 de la forme :
a1 x1 + a2 x2 + a3 x3 = b
représente un plan.
L’hyperplan aT x = b divise l’espace Rn en 3 ensembles distinct :
X1 = {x : aT x < b}, X2 = {x : aT x = b}, X3 = {x : aT x > b}.
X1 etX3 sont appelés des demi-espaces ouverts.

Proposition 2. Un hyperplan H = {x ∈ Rn | aT x = b}, où a ∈ Rn et

b ∈ R, est un ensemble convexe.

Démonstration. Soit x1 , x2 ∈ H et t ∈ [0, 1]. Montrons que la combinaison

convexe de x1 et x2 , c’est-à-dire xt = (1 − t)x1 + tx2 , appartient également à
H.
Puisque x1 , x2 ∈ H, on a :
aT x1 = b et aT x2 = b.
Calculons aT xt pour vérifier s’il appartient à H :
aT xt = aT ((1 − t)x1 + tx2 ) = (1 − t)aT x1 + taT x2 .
En utilisant les relations aT x1 = b et aT x2 = b, nous obtenons :
aT xt = (1 − t)b + tb = b.
Ainsi, aT xt = b, ce qui implique que xt ∈ H.
Puisque xt ∈ H pour tout t ∈ [0, 1], cela prouve que l’hyperplan H est un
ensemble convexe.
8 CHAPITRE 1. RAPPELS SUR LA PROGRAMMATION LINÉAIRE

Les hyperplans jouent un rôle important dans les problèmes d’optimisation,

notamment en programmation linéaire, où les contraintes linéaires définissent
des demi-espaces, et l’ensemble des solutions est souvent l’intersection de ces
demi-espaces, formant ainsi un ensemble convexe.

Définition 4. Un point x ∈ C est un point extrême de l’ensemble convexe

C s’il ne peut pas être exprimé comme une combinaison convexe non tri-
viale de deux autres points dans C.

Définition 5. L’enveloppe convexe (convex hull) d’un ensemble de points

S ⊆ Rn , notée Conv(S), est le plus petit ensemble convexe contenant S.
Elle peut être définie comme l’ensemble des combinaisons convexes de tous
les points de S, c’est-à-dire :
( k k
)
X X
Conv(S) = λi xi | xi ∈ S, λi ≥ 0, λi = 1 .
i=1 i=1

Proposition 3. L’enveloppe convexe Conv(S) d’un ensemble S ⊆ Rn est

un ensemble convexe.

Définition 6. L’ensemble de toutes les combinaisons convexe d’un nombre

finis de points est appelé un polyèdre convexe généré pas ces points.

un simplexe est l’enveloppe convexe d’un ensemble de (n + 1) points utilisé

pour former un repère affine dans un espace affine de dimension n, ce qui signifie
que :
— sur une droite le repère sera fait d’une origine et de 1 point (généralement
un repère (O, I), définissant l’unité de l’axe), et [OI] est un segment.
— dans le plan le repère sera fait d’une origine et de 2 points (généralement
un repère (O, I, J), définissant l’unité pour chaque axe), et OIJ est un
triangle.
— dans l’espace le repère sera fait d’une origine et de 3 points (généralement
un repère (O, I, J, K), définissant l’unité pour chaque axe), et OIJK est
un tétraèdre (pyramide à base triangulaire).

1.0.2 Définition d’un programme linéaire

Un programme linéaire est un type particulier de problème d’optimisation
dans lequel la fonction objectif et les contraintes sont linéaires. Un programme
linéaire est dit qu’il est sous la forme canonique si les variables sont positive, les
1.1. FORME STANDARD EN PROGRAMMATION LINÉAIRE 9

contraintes sont tous de type ≤ et l’objectif est à maximiser. La forme canonique

d’un PL se formule ainsi :

MaximisercT x

sous les contraintes Ax ≤ b et x ≥ 0,

où c est un vecteur représentant les coefficients de la fonction objectif, A est

une matrice de coefficients pour les contraintes, et b est un vecteur.

1.1 Forme Standard en Programmation Linéaire

1.1.1 Introduction : Le Besoin de Standardisation
En programmation linéaire, il est essentiel de représenter les problèmes de
manière uniforme pour simplifier l’application des méthodes de résolution, en
particulier la méthode du simplexe. La forme standard fournit un cadre unifié
pour traiter les différents types de problèmes de programmation linéaire.
Les raisons principales pour lesquelles la standardisation est nécessaire sont
les suivantes :
— Variété des contraintes : Dans les problèmes réels, les contraintes
peuvent être des inéquations (de type ≤ ou ≥) ou des égalités.
— Objectifs différents : Certains problèmes cherchent à maximiser une
fonction, tandis que d’autres cherchent à la minimiser. La standardisa-
tion permet de traiter ces cas de manière uniforme en convertissant tous
les problèmes en des problèmes de maximisation.
— Efficacité computationnelle : Les algorithmes, comme celui du sim-
plexe, nécessitent une représentation standard des problèmes afin d’ap-
pliquer les opérations de manière directe, sans devoir gérer plusieurs
variations dans la structure des problèmes.
La conversion des problèmes linéaires en une forme standard permet de
se concentrer sur une seule méthode de résolution, ce qui simplifie l’analyse
théorique et la mise en œuvre pratique.

1.1.2 Conversion en Forme Standard

La forme standard d’un problème de programmation linéaire consiste en :
— Objectif : Maximiser f (x), où f (x) est une fonction linéaire.
— Contraintes : Toutes les contraintes doivent être représentées sous forme
d’égalités.
— Non-négativité : Toutes les variables doivent être non-négatives (xi ≥
0).
10 CHAPITRE 1. RAPPELS SUR LA PROGRAMMATION LINÉAIRE

2.1 Variables d’écart pour les inéquations ”≤”

Lorsqu’on rencontre des inéquations de la forme :
Ax ≤ b,
on peut les transformer en égalités en introduisant des variables d’écart. Les
variables d’écarts représentent la différence entre le côté gauche et le côté droit
d’une inéquation, convertissant ainsi l’inéquation en une égalité.
Par exemple, considérons l’inéquation :
a1 x1 + a2 x2 ≤ b.
Nous introduisons une variable de détente e ≥ 0 telle que :
a1 x1 + a2 x2 + e = b.
Cela permet de réécrire la contrainte sous forme d’égalité, tout en respectant
la condition de non-négativité avec s ≥ 0.

2.2 Variables d’écart pour les inéquations ”≥”

Pour les inéquations du type :
Ax ≥ b,
on introduit des variables d’écart pour les convertir en égalités. Ces va-
riables ne représentent pas des quantités réelles dans le problème et doivent
être éliminées pendant le processus d’optimisation, via des méthodes comme la
méthode du grand M ou la méthode du simplexe à deux phases.
Par exemple, pour l’inéquation :
a1 x1 + a2 x2 ≥ b,
on peut la réécrire en soustrayant une variable de surplus et en ajoutant une
variable d’écart e ≥ 0 comme suit :
a1 x1 + a2 x2 − e = b,
où e est la variable d’écart introduite pour assurer l’égalité. Ces variables d’écart
sont éliminées à travers le processus d’optimisation.

1.1.3 3. Maximisation et Minimisation

En programmation linéaire, un problème de minimisation peut toujours
être converti en un problème de maximisation en considérant l’opposé de la
fonction objectif. Cela est crucial pour la standardisation, car on préfère souvent
travailler avec des problèmes de maximisation.

3.1 Théorème : Minimiser revient à maximiser −f (x)

1.2. RÉSOLUTION GRAPHIQUE DES PROBLÈMES À DEUX VARIABLES11

Théoreme 2. Tout problème de minimisation peut être transformé en un

problème de maximisation en maximisant l’opposé de la fonction objectif.

Démonstration :
Considérons un problème de minimisation :

min f (x),

où f (x) est une fonction linéaire. L’objectif est de trouver x tel que f (x) soit
minimisé.
Pour convertir ce problème en un problème de maximisation, nous définissons
une nouvelle fonction objectif g(x) comme suit :

g(x) = −f (x).

Le problème devient alors :

max g(x) = max(−f (x)).

Minimiser f (x) équivaut à maximiser −f (x) car si f (x) diminue, alors −f (x)
augmente de la même quantité. Ainsi, tout problème de minimisation peut
être traité comme un problème de maximisation, ce qui permet d’appliquer les
mêmes techniques de résolution.

La conversion d’un problème de programmation linéaire en forme standard

est une étape fondamentale. Cette transformation simplifie l’application des
méthodes de résolution, notamment la méthode du simplexe, et garantit une
approche cohérente pour résoudre une grande variété de problèmes d’optimisa-
tion.

1.2 Résolution Graphique des Problèmes à Deux

Variables
Pour des problèmes de programmation linéaire à deux variables, la solution
peut être représentée graphiquement. La région admissible, ou domaine fai-
sable, est formée par l’intersection des demi-espaces définis par les contraintes
linéaires. La solution optimale, dans un tel cadre, se trouve toujours à l’un
des sommets de cette région, car la fonction objectif est linéaire et atteint son
extrême sur les frontières du domaine faisable, en particulier aux sommets.
12 CHAPITRE 1. RAPPELS SUR LA PROGRAMMATION LINÉAIRE

Exemple 1. Considérons le problème suivant :

Maximiser Z = 8x + y
sous les contraintes
(P ) x + y ≤ 40,
2x + y ≤ 60,
x, y ≥ 0.

1.2.1 Représentation Graphique

La région admissible est délimitée par les contraintes du problème. Pour
représenter ces contraintes graphiquement, on trace les droites correspondantes
aux équations des contraintes en supposant que les inégalités soient des égalités.
Ensuite, on identifie la région admissible comme étant l’intersection des demi-
espaces formés par ces droites.
Les deux premières contraintes sont des inéquations linéaires :
— x + y ≤ 40,
— 2x + y ≤ 60,
avec les contraintes de non-négativité x ≥ 0 et y ≥ 0, ce qui restreint la solution
à la première partie du plan (quadrant positif).
Après avoir tracé ces contraintes, nous obtenons la figure suivante :

Figure 1.4 – La région admissible déterminée par l’intersection des demi-

espaces.
1.3. BASES RÉALISABLES 13

1.2.2 Résolution par l’Évaluation des Sommets

La solution optimale se trouve à l’un des sommets du polyèdre qui constitue
la région admissible. Les sommets de la région admissible peuvent être obte-
nus en résolvant les systèmes d’équations associés aux points d’intersection des
contraintes. Les sommets pour ce problème sont :
— (0, 0),
— (0, 40), intersection de x = 0 et x + y = 40,
— (20, 20), intersection de x + y = 40 et 2x + y = 60,
— (30, 0), intersection de 2x + y = 60 et y = 0.
Nous allons maintenant calculer la valeur de la fonction objectif Z = 8x + y
en chaque sommet :

Points Z = 8x + y
(0, 0) Z = 8(0) + 0 = 0
(0, 40) Z = 8(0) + 40 = 40
(20, 20) Z = 8(20) + 20 = 160 + 20 = 180
(30, 0) Z = 8(30) + 0 = 240
Ainsi, le maximum de Z est atteint au point (30, 0) avec une valeur de
Z ∗ = 240.

1.2.3 Validation Graphique

Une méthode graphique complémentaire pour déterminer la solution opti-
male consiste à tracer des lignes de niveau de la fonction objectif, c’est-à-dire
des droites de la forme 8x + y = K, où K est une constante. En déplaçant
cette droite parallèlement à elle-même dans la direction de l’augmentation de
Z, le dernier point où la droite intersecte la région admissible est la solution
optimale.
Dans ce cas, la droite 8x + y = K pour K = 240 intersecte la région
admissible au point (30, 0), confirmant ainsi que ce point est bien la solution
optimale.

Figure 1.5 – Illustration du déplacement de la droite 8x+y = K pour identifier

la solution optimale.

1.3 Bases réalisables

Considérons un programme linéaire sous sa forme standard :


 Maximiser Z = cT x
s.c.

(P ) (1.1)

 Ax =b
x ≥0

14 CHAPITRE 1. RAPPELS SUR LA PROGRAMMATION LINÉAIRE

Soit B une matrice m×m non singulière, que nous appelons une base formée
de m colonnes indépendantes de A. Nous notons B1 , B2 , . . . , Bm les colonnes
de la matrice B.
Nous définissons xB comme la solution de base, où xB = [xB1 , xB2 , . . . , xBm ]T .
Dans une solution réalisable de base, toutes les variables excepté celles de
base xB sont nulles. Ainsi, de Ax = b, nous avons :

BxB = b ⇒ xB = B −1 b
Les variables qui ne sont pas dans la base sont appelées les variables hors
base.
Puisque B est une base de A, nous pouvons exprimer les colonnes de A
comme des combinaisons linéaires des vecteurs de B. Pour une colonne aj de
A, nous avons :

aj = y1j B1 + y2j B2 + . . . + ymj Bm = Byj

où yj est un vecteur de coefficients qui indique la combinaison linéaire utilisée
pour exprimer aj en fonction des colonnes de la base B.

1.4 Valeur de la solution et exemple d’une base

réalisable
La valeur de la solution pour un programme linéaire donné peut être ex-
primée comme suit :

Z = cTB xB
où cB est le vecteur des coefficients de la fonction objectif associés aux
variables de base, et xB est la solution de base. Étant donné que les variables
hors base sont égales à zéro dans une solution réalisable de base, la valeur de
la fonction objectif dépend uniquement des variables de base.

1.4.1 Exemple d’une base réalisable

Considérons le programme linéaire suivant :


 Maximiser Z = 3x1 + 2x2
s.c.



(P ) x1 + 2x2 ≤6 (1.2)
2x + x ≤ 8

1 2



x1 , x2 ≥0


Pour mettre ce programme sous forme standard, nous ajoutons des variables
de surplus. Nous obtenons :
1.5. OBTENTION D’UNE NOUVELLE BASE À PARTIR D’UNE BASE DONNÉE15



 Maximiser Z = 3x1 + 2x2
s.c.



(P ′ ) x1 + 2x2 + s1 =6 (1.3)
2x1 + x2 + s2 =8




x1 , x2 , s1 , s2 ≥0


Dans ce cas, les colonnes de la matrice A (qui contient les coefficients des
variables dans les contraintes) peuvent être représentées par les colonnes sui-
vantes :
 
1 2 1 0
A=
2 1 0 1
 
1 2
Supposons que nous choisissons B = comme matrice de base, où B1
2 1
correspond à x1 et B2 correspond à x2 . Les autres variables, s1 et s2 , sont les
variables hors base.
Calculons xB :

xB = B −1 b
 
6
où b = . En résolvant, nous trouvons que
8
   
−1 1 −2 1
B = ⇒ xB =
−2 1 2
Par conséquent, la solution de base est :
   
x 2
xB = 1 =
x2 1
Calculons maintenant la valeur de la fonction objectif Z :
 T  
3 2
Z = cTB xB = =3×2+2×1=6+2=8
2 1
Ainsi, la valeur de la fonction objectif est Z ∗ = 8, obtenue à partir de la
solution de base, où les variables hors base sont nulles.

1.5 Obtention d’une nouvelle base à partir d’une

base donnée
Pour obtenir une nouvelle base à partir d’une base donnée, nous allons chan-
ger un vecteur de la base par un autre. Considérons une matrice A formée des
colonnes a1 , a2 , . . . , an et une base B constituée des colonnes B1 , B2 , . . . , Bm .
16 CHAPITRE 1. RAPPELS SUR LA PROGRAMMATION LINÉAIRE

Soit aj une colonne correspondant à une variable hors base. Comme aj

peut s’écrire comme une combinaison linéaire des colonnes de B, nous pouvons
exprimer aj sous la forme suivante :

aj = y1j B1 + y2j B2 + . . . + ymj Bm

où yij sont les coefficients de la combinaison linéaire.
Nous pouvons remplacer une colonne Br de la base par la colonne aj si
au moins un des coefficients yij est non nul. Après cette substitution, nous
obtiendrons une nouvelle base B ′ avec :
1 X yij
Br′ = aj − Bi
yrj yrj
i̸=r

Br′
où représente la nouvelle colonne de base résultant du remplacement de
la colonne Br par aj .