Prog Linéaire 2018
Prog Linéaire 2018
Prog Linéaire 2018
3 juillet 2018
Table des matières
1 Notions de base 3
1.1 Sous espaces vectoriels et applications linéaires . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Sous espaces affines et applications affines . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3 Systèmes d’équations linéaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.4 Ensembles convexes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.5 Polyèdres convexes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1
5.4.1 Modification d’un coefficient de c . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
5.4.2 Modification d’un coefficient de b . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
5.4.3 Ajout d’une variable . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
5.4.4 Ajout d’une contrainte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
5.4.5 Suppression d’une variable . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
2
Chapitre 1
Notions de base
Le cadre général de ce cours est un espace vectoriel réel de dimension n. On peut donc sans perdre
de généralités considérer l’espace vectoriel réel Rn .
Définition 1.1.2 Etant donné M ⊂ Rn , E ̸= ∅, on dit que E est un sous espace vectoriel de Rn , si E
est stable par combinaison linéaire. C’est-à-dire :
∀ x, y ∈ E, ∀α, β ∈ R, αx + βy ∈ E.
On rappelle que :
Définition 1.1.3 Une application f de Rn dans Rm est dite linéaire si : Pour tout x, y dans Rn et
α, β ∈ R, on a :
f (αx + βy) = αf (x) + βf (y).
Définition 1.2.2 Etant donné M ⊂ Rn , M ̸= ∅, on dit que M est un sous espace affine (ou une variété)
de Rn , si M est stable par combinaison linéaire affine. C’est-à-dire :
∀ x y ∈ M, ∀α ∈ R, (1 − α)x + αy ∈ M.
Proposition 1.2.1 Pour un sous ensemble non vide de Rn , les conditions suivantes sont équivalentes :
1) M est un sous espace affine de Rn
2) Il existe un sous espace vectoriel V unique de Rn tel que :
∀a ∈ M, M = a + V = {a + v : v ∈ V }.
3
Définition 1.2.3 Soit M un sous espace affine de Rn . Le sous espace vectoriel V vérifiant : ∀ a ∈
M, M = a + V est appelé la direction de M . La dimension de V est la dimension de M .
Proposition 1.2.2 Si {Mi }i∈I est une famille de sous espaces affines d’intersection non vide, alors
∩i∈I Mi est un sous espace affine.
Définition 1.2.5 Une forme linéaire φ sur Rn est une application linéaire de Rn dans R.C’est-à-dire il
existe a ∈ Rn tel que :
φ(x) = ⟨a, x⟩, ∀x ∈ Rn .
Proposition 1.2.3 ∅ ̸= H ⊂ Rn
Les conditions suivantes sont équivalentes
i) H est un hyperplan
ii) Il existe a ∈ Rn non nul et α ∈ R tels que :
H = {x ∈ Rn : ⟨a, x⟩ = α}.
Définition 1.2.6 Une application f de Rn dans Rm est dite affine s’il existe une application linéaire L
de Rn dans Rm et b ∈ Rm tels que :
∀ x ∈ Rn , f (x) = L(x) + b.
Proposition 1.2.4 Une application f de Rn dans Rm est dite affine si et seulement si pour tout x, y
dans Rn et λ ∈ R, on a
4
1.3 Systèmes d’équations linéaires
Soit un système de m équations à n inconnues :
∑
n
aij xj = bi i = 1, · · · m. (1.1)
j=1
Définition 1.3.1 Une matrice carrée B ∈ Mm (R) est dite régulière si son rang est m.
On montre que :
{x ∈ Rn : Ax = b} = {x ∈ Rn : BAx = Bb}.
En particulier, une combinaison linéaire convexe de deux points x et y, est tout point z = (1−λ)x+λy
avec λ ∈ [0, 1] .
On définit aussi :
Définition 1.4.2 Soit x, y ∈ Rn ; on appelle segment ”fermé” d’extrémités x et y, l’ensemble noté [x, y]
et défini par :
[x, y] = {z ∈ Rn : z = (1 − λ) x + λy : λ ∈ [0, 1]} .
Définition 1.4.3 On appelle segment ”ouvert” d’extrémités x et y, et on le note ]x, y[, l’ensemble
5
On définit aussi ]x, y] et [x, y[ qui sont appelés segments semi ouvert en x respectivement en y.
Définition 1.4.4 Soit C une partie de Rn . C est convexe si seulement si pour tout x, y ∈ C, (1 − λ) x +
λy ∈ C pour tout λ ∈ [0, 1]. Autrement dit, C est convexe si seulement si C contient tout segment fermé
d’extrémités deux quelconques de ses points.
On a la caractérisation suivante :
Proposition 1.4.1 Une partie C de Rn est convexe si seulement si toute combinaison convexe de points
de C appartient à C.
Exemple 1.4.1 - Dans Rn , les ensembles suivants sont convexes : Rn , l’ensemble vide, les singletons,
les boules, les segments.
- Dans R, les parties convexes sont les intervalles.
Remarque 1.5.1 1) Un polyèdre convexe de Rn est toujours convexe comme son nom l’indique et il est
aussi fermé.
2) Dans la définition ci-dessus, on peut toujours supposer qu’on a un seul type d’inégalité. C’est-à-
dire : { }
ai x ≤ (≥)bi , i = 1, · · · , p,
P= x∈R : n
ai x = bi , i = p + 1, · · · , m
Définition 1.5.2 Un polyèdre convexe non vide et borné est appeplé un polytope.
Définition 1.5.3 Soit P un polyèdre convexe de Rn . Un point x ∈ P est un sommet de P s’il existe
c ∈ M1,n (R) tel que cx < cy pour tout y ∈ P, y =
̸ x.
P = {x ∈ Rn : ai x ≤ (≥)bi , i = 1, · · · , m} ,
6
Chapitre 2
On peut supposer que ce programme est sous la forme suivante dite forme générale :
∑
min (max) Z(x) = nj=1 cj xj
∑ n
∑ j=1 aij xj ≥ bi , i = 1, · · · , m1 (1)
n
aij xj ≤ bi , i = m1 + 1, · · · , m2 (2)
∑j=1n
j=1 aij xj = bi , i = m2 + 1, · · · , m (3)
x ≥ 0, j = 1, · · · , n1
j
xj ≤ 0, j = n1 + 1, · · · , n2
xj ∈ R, j = n2 + 1, · · · , n.
Remarque 2.1.1 - Etant donné un programme linéaire, on peut toujours se ramener à un programme
linéaire où les variables sont astreintes à être non négatives. En effet si xj est une variable négative on
−
fait le changement de variable x′j = −xj . Si par contre xj est quelconque dans R on pose xj = x+ j − xj
−
avec x+ j , xj ≥ 0 car tout réel peut s’écrire comme la différence de deux réels positifs ou nuls.
7
- Dans un programme linéaire on peut ramener toutes les contraintes d’inégalité (1) et (2) à des
inégalités de même type. il suffit de multiplier la contrainte par −1 le cas échéant.
Par convention les contraintes d’inégalité pour un problème de minimisation sont du type ” ≥ ” et les
contraintes d’inégalité pour un problème de maximisation sont du type ” ≤ ”
On peut dire alors qu’un programme linéaire est un programme mathématique de la forme :
∑
min (max) Z(x) = nj=1 cj xj
∑n
∑j=1 aij xj ≥ (≤) bi , i = 1, · · · , p
n
j=1 aij xj = bi , i = p + 1, · · · , m
xj ≥ 0, j = 1, · · · , n
Dans ce programme linéaire on distingue deux types de contraintes : les contraintes relatives au signe
des variables, dites contraintes de restriction de signe ou de non-négativité et les autres dites ”vraies
contraintes” on dit aussi contraintes structurelles.
Si on note :
∑n
aij xj ≥ (≤) bi , i = 1, · · · , p
∑n j=1
D = x ∈ Rn : j=1 aij xj = bi , i = p + 1, · · · , m ,
xj ≥ 0, j = 1, · · · , n
C’est un polyèdre convexe, ses éléments sont appelés solutions réalisables, admissibles ou acceptables
du programme et Z la fonction-objectif.
Exemple 4
Les produits d’une société anonyme sont conditionnés dans des récipients de deux type A et B. Afin
de pouvoir satisfaire la clientèle, le Directeur de la société se fixe comme objectif annuel de disposer d’au
moins 3 200 000 récipients de type A et d’au moins 400 000 récipients de type B.
Pour produire ces récipients, le Directeur dispose de deux ateliers dont les rendements sont differents
8
Nombre de récipients par heure de fonctionnement
Atelier 1 Atelier 2
Récipient type A 500 400
Récipient type B 400 320
Chaque atelier fonctionne au maximum 4 000 heures dans l’année. Les prévisions de coût variable de
production de chaque type de récipient donnent comme résultats :
Atelier 1 Atelier 2
Récipient type A 0.4 0.55
Récipient type B 0.75 0.85
Mais le Directeur peut également sous traiter la fabrication de ces récipients à une société qui propose
comme tarifs :
0.55u. m. le récipient de type A
1u. m. le récipient de type B
Donner la formulation mathématique du problème correspondant à un programme de production
optimale.
Exemple 5
Le propriétaire d’une station d’essence qui vend du Super, de l’Ordinaire et du Gas-oil aux prix
respectifs de 415, 390 et 295 unités monétaires le litre, mais livrés par la station mère aux prix de 405,
375 et 270 unités monétaires.
Comme le propriétaire de la station est peu scrupuleux et qu’il veut s’enrichir rapidement, il se livre
au trafic suivant : se basant sur son expérience du métier, il sait qu’il peut vendre à la pompe ”Super”
un mélange des trois carburants à condition qu’il y ait au moins 70% de Super et pas plus de 10%
d’Ordinaire.
De même, à la pompe ”Ordinaire”, il peut vendre un mélange comportant au moins 15% de Super et
pas plus de 70% de Gas-oil.
Enfin, le mélange vendu à la pompe ”Gas-oil” doit contenir au moins 80% de Gas-oil.
D’autre part, le marché est tel que le propriétaire de la station ne peut vendre plus de 20 000 litres
de Super, 30 000 litres d’Ordinaire et 20 000 litres de Gas-oil.
Donner la formulation mathématique de ce problème.
Exemple 6
Les demandes journalières en chauffeurs dans une entreprise de transport sont :
lu ma me je ve sa di
13 18 21 16 12 25 9
Les chauffeurs travaillent cinq jours d’affilée (et peuvent donc avoir leurs deux jours adjacents de
congé n’importe quand dans la semaine).
On se propose de déterminer les effectifs formant les sept équipes possibles de chauffeurs de manière
à
- couvrir tous les besoins.
- engager un nombre minimum de chauffeurs.
Formuler ce problème sous forme d’un programme linéaire.
Exemple 7
9
On désire déterminer la composition, à coût minimal, d’un aliment pour bétail qui est obtenu en
mélangeant au plus deux produits bruts : orge et arachide.
- la quantité nécessaire par portion est de 400g.
- l’aliment ainsi fabriqué devra comporter au moins 30% de protéı̈nes et au plus 5% de fibres.
On a les données suivantes :
quantité par gramme d’aliment
Aliment Protéı̈ne Fibres Coût (F/kg)
orge 0,09 0,02 450
arachide 0,60 0,06 500
Modéliser le problème sous forme d’un programme linéaire.
u ≤ v ⇔ ui ≤ vi ∀ i = 1, · · · , n.
Définition 2.3.1 Un programme linéaire est sous forme standard si les vraies contraintes sont des
égalités et les variables sont astreintes à être non négatives. En d’autres termes, le problème est sous
la forme
∑n
min
{ ∑ (max) Z = j=1 cj xj
n
j=1 aij xj = bi , i = 1, · · · , m
xj ≥ 0, j = 1, · · · , n
min(max)
{ Z = cx
Ax = b
x ∈ Rn , x ≥ 0
On a la proposition suivante.
Proposition 2.3.1 Tout programme linéaire peut se mettre sous forme standard
Preuve : Il suffit de transformer les contraintes d’inégalité en contraintes d’égalité en considérant les
équivalences suivantes :
∑n ∑n
aij xj ≥ bi ⇔ aij xj − si = bi , si ≥ 0
j=1 j=1
∑
n ∑
n
aij xj ≤ bi ⇔ aij xj + si = bi , si ≥ 0
j=1 j=1
Définition 2.3.2 La variable si introduite pour passer d’une contrainte d’inégalité à une contrainte
d’égalité est appelée variable d’écart.
Remarque 2.3.1 Le passage à la forme standard augmente le nombre de variables dans le programme
linéaire.
10
Définition 2.3.3 Un programme linéaire est sous forme canonique si les vraies contraintes sont des
inégalités et les variables sont astreintes à être non négatives. Pour les problèmes de minimisation on a
∑n
min Z =
{ j=1 cj xj
∑n
≥ bi , i = 1, · · · , m
j=1 aij xj
xj ≥ 0, j = 1, · · · , n
En considérant les mêmes notations que ci-dessus, on obtient respectivement pour la minimisation et
la maximisation la notation matricielle suivante :
min Z = cx
{ max
{ Z = cx
Ax ≥ b Ax ≤ b
x ∈ Rn , x ≥ 0 x ∈ Rn , x ≥ 0
Proposition 2.3.2 Tout programme linéaire peut se mettre sous forme canonique
Preuve : Il suffit de transformer les contraintes d’égalité en contraintes d’inégalité en considérant l’une
des équivalences suivantes :
∑
n { ∑n
j=1 aij xj ≥ bi ,
∑
aij xj = bi ⇔
− nj=1 aij xj ≥ −bi
j=1
ou
∑
n { ∑n
j=1 aij xj ≤ bi ,
∑
aij xj = bi ⇔
− nj=1 aij xj ≤ −bi
j=1
Remarque 2.3.2 Le passage à la forme canonique augmente le nombre de contraintes dans le programme
linéaire.
11
Chapitre 3
∀ x ∈ X, m ≤ x.
∀ x ∈ X, x ≤ M.
12
Proposition 3.1.2 Pour tout X ⊂ R, on a supx∈X (x) = − inf x∈X (−x)
Il faut noter d’après la proposition (3.1.2) que tout problème de maximisation peut se ramener à un
problème de minimisation. En effet, on a :
Proposition 3.1.3
max Z(x) = − min −Z(x).
x∈P x∈P
Sans perdre de généralités, on peut donc considérer dans ce qui suit que nous avons un problème de
minimisation.
Soit le programme linéaire :
min Z(x) (P ),
x∈D
On sait que
Proposition 3.1.4 L’ensemble des solutions réalisables d’un programme linéaire est un polyèdre convexe
fermé. Il peut être :
- vide,
- non vide et borné, on dit que c’est un polytope,
- non vide et non borné.
Z(x∗ ) ≤ Z(x), ∀ x ∈ D
- dans ce cas la valeur Z ∗ = Z(x∗ ) est dite valeur optimale ou plus précisément le minimum.
Théorème 3.1.1 Etant donné le programme linéaire (P ), si son polyèdre des solutions réalisables est
non vide, fermé et borné alors il possède une solution optimale.
Nous avons dans ce qui suit la propriété dite propriété fondamentale de la programmation linéaire.
Théorème 3.1.2 Si un programme linéaire possède une solution optimale, alors son polyèdre des solu-
tions réalisables contient au moins un sommet et un d’entre eux est solution optimale.
13
3.2 Méthode graphique
La méthode graphique est l’une des premières méthodes utilisées pour résoudre les programmes
linéaires.
On considère le programme linéaire (P ).
On rappelle que les courbes de niveau de la fonction-objectif Z, sont les courbes d’équation : Z(x) = α
avec α ∈ R. Dans le plan, les lignes de niveau sont des droites perpendiculaires au vecteur gradient de
la fonction-objectif. Le vecteur gradient est le vecteur dont les coordonnées sont les coefficients de la
fonction-objectif.
On suppose que (P ) admet une solution optimale. Pour résoudre ce problème par la méthode gra-
phique, on peut procèder de la façon suivante :
- dessiner le polyèdre des solutions réalisables dans un repère (de préférence orthonormé),
- considérer les lignes de niveau de la fonction-objectif passant par les différents sommets,
- éliminer tous les sommets dont la ligne de niveau rencontre l’intérieur du polyèdre des solutions
réalisables,
- prendre comme solution, le premier sommet (par rapport au sens du vecteur gradient de la fonction-
objectif) dont la ligne de niveau correspondante ne rencontre pas l’intérieur du polyèdre des solutions
réalisables.
A titre d’exemples, résoudre graphiquement les programmes linéaires suivants :
1)
min Z = 2x1 + 3x2 2)
min Z = x1 + x2 min Z = 2x1 − 3x2
3)
x1 + x2 ≤ 4
2x1 + x2 ≥ 12 x1 − x2 ≥ 5
6x1 + 2x2 ≥ 8
5x1 + 8x2 ≥ 74 x2 ≥ 5
x1 + 5x2 ≥ 4
x + 6x2 ≥ 24 x1 , x2 ≥ 0
1
x1 ≤ 3 x1 , x 2 ≥ 0
x ≤3
2
x 1 , x2 ≥ 0
4)
max Z = 3x1 + 2x2 5)
max Z = 6x1 + 5x2 6)
max Z = x1 + x2
−2x1 + x2 ≤ 1
x1 + x2 ≥ 8
−2x1 + x2 ≤ 1
x1 + x2 ≤ 3 −2x1 + 3x2 ≤ 6 x1 + x2 ≤ 3
x ≤2
x − x2 ≥ 2
x ≤2
1 1 1
x 1 , x2 ≥ 0 x 1 , x2 ≥ 0 x1 , x 2 ≥ 0
Cette méthode est limitée car elle ne s’applique qu’à des programmes linéaires où le nombre de
variables est faible (au maximum 3 variables). Nous allons nous intéresser dans ce qui suit à une méthode
algébrique, la méthode du simplexe.
14
Définition 3.3.2 Soit B une base de (P L), les variables associées aux colonnes de B sont appelées
variables de base associées à B, et les autres, variables hors base ou libres associées à B.
Remarque 3.3.1 La matrice des vraies contraintes du programme linéaire (P L) étant dans Mm,n (R),
il possède au plus Cm
n bases.
Remarque 3.3.2 Dans la pratique, on représente une base par son ensemble de variables de base ou
par son ensemble des indices des variables de base. Cela permet d’éviter certaines indéterminations. En
effet, si on considère un programme dont le système des vraies contraintes est :
{
x1 − x2 + x3 − x4 + x5 = 4
x1 + x2 + x3 + x4 + x5 = 1
on sait que ( )
1 −1
B=
1 1
est une base mais il est difficile de dire quelles sont les variables de base associées.
Soit B une base de (P L). Notons N la sous matrice de A constituée des colonnes des variables hors
base. Moyennant une permutation on peut supposer que les colonnes de B sont les m premières colonnes
de A. Donc on peut supposer que A est sous la forme ( (matrices
) blocs) A = (B, N ). De même on peut
xB
décomposer le vecteur variable x sous la forme x = où xB est constitué des variables de base et
xN
xN des variables hors base. Le système Ax = b s’écrit alors :
BxB + N xN = b ⇐⇒ xB + B −1 N xN = B −1 b. (3.1)
Définition 3.3.3 On appelle solution de base de (P L) associée (ou relative) à la base B, la solution
particulière x(B)
( du système
) Ax = b obtenue en fixant les variables hors base à zéro (en prenant xN = 0)
B −1 b
i. e. x(B) =
0
Exemple 3.3.1
Considérons le programme linéaire ci-dessous où c quelconque est une matrice ligne à 5 colonnes.
∗
= min Z = 2x1 − 3x2
Z
x1 − x2 + x3 = 5
(P L)
x2 + x4 = 5
xi ≥ 0, i = 1, · · · , 4
Il est immédiat que rangA = 2. Il y a cinq bases possibles (seul I = {1, 3} est exclu)
I1 = {1, 2}, I2 = {1, 4}, I3 = {2, 3}, I4 = {2, 4}, I5 = {3, 4}.
15
avec les solutions de base :
10 5 0 0 0
5 0 5 −5 0
x(I1 ) =
0 , x(I2 ) =
, x(I3 ) =
, x(I4 ) =
, x(I5 ) =
.
0 10 0 5
0 5 0 10 5
Définition 3.3.4 On dit qu’une base B de (P L) est une base réalisable, si la solution de base x(B)
associée à B, est telle que x(B) ≥ 0 c’est-à-dire B −1 b ≥ 0. On dit alors que x(B) est une solution de
base réalisable de (P L).
Exemple 3.3.3
Définition 3.3.5 Une base réalisable B de (P L) est dite dégénérée si le vecteur xB = B −1 b contient au
moins une composante nulle.
Exemple 3.3.4
Z = −3x1 − 2x2
min
4x1 + 3x2 + x3 = 18
4x1 + x2 + x4 = 8
4x1 − x2 + x5 = 8
x ∈ R5 , x ≥ 0
16
Définition 3.3.6 Le programme linéaire (P L) est dit dégénéré s’il possède une base réalisable dégénérée.
Définition 3.3.7 On dit que deux bases B et B ′ sont adjacentes, si les colonnes qui les constituent ne
diffèrent que d’un seul élément.
On montre que :
Proposition 3.3.1 Etant donné un programme linéaire sous forme standard, si l’ensemble des solutions
réalisables est non vide, il contient au moins une solution de base réalisable. En outre, si le programme
possède une solution optimale, alors il possède une solution de base réalisable optimale.
Soit B une base réalisable de (P L). On note I l’ensemble des indices des variables de base et J
l’ensemble des indices des variables hors base.
On sait qu’on peut supposer sans perdre de généralités que B est formée des m premières colonnes
de A et donc A est de la forme (matrices blocs) A = (B, N ) où N est la(sous-matrice
) formée par les
xB
colonnes de A qui ne sont pas dans B. De même on peut partitionner x = où xB est constitué
xN
des variables de base et xN des variables hors base.
Le système Ax = b est alors équivalent à
BxB + N xN = b ⇔ xB + B −1 N xN = B −1 b. (3.2)
On peut aussi partitionner c de la façon suivante : c = (cB , cN ) où cB est formé des coefficients des
variables de base et cN des coefficients des variables hors base. On a alors :
Z(x) = cx = cB xB + cN xN .
Posons
 = B −1 A, ĉ = c − cB B −1 A, Ẑ = cB B −1 b (3.4)
Définition 3.3.8 Deux programmes linéaires sont dits équivalents s’ils ont les mêmes solutions réalisables
et les mêmes solutions optimales.
Z ∗ = min Z = ĉx + Ẑ
{
Âx = b̂
x ∈ Rn , x ≥ 0
C’est la forme canonique (ou forme équivalente) de (P L) par rapport à la base réalisable B.
17
Remarque 3.3.3 Ecrire un programme linéaire sous forme canonique par rapport à une base réalisable,
c’est écrire sa fonction-objectif ainsi que ses variables de base en fonction des seules variables hors base.
En d’autres termes il s’agit d’écrire la fonction-objectif à l’aide des seules variables hors base et
transformer le système des vraies contraintes en un système équivalent dans lequel chaque variable de
base n’intervient que dans une seule équation, et dans cette équation son coefficient est égal à 1. On dira
alors que cette dernière est la variable de base associée à cette équation.
Exemple 3.3.6
La forme canonique du programme linéaire de l’exemple (3.3.3) par rapport à la base réalisable I =
{x1 , x3 } est :
Théorème 3.3.1 Une condition suffisante pour que B soit une base réalisable optimale est ĉ ≥ 0.
Preuve : Dans (P L) on a la contrainte xN ≥ 0. Donc pour toute solution réalisable x de (P L), on aura :
Dans le cas de non dégénérescence, la condition suffisante ci-dessus est aussi nécessaire.
Théorème 3.3.2 Si le problème (P L) est non dégénéré i.e. ne possède pas de base réalisable dégénérée,
une condition nécessaire et suffisante pour que B soit optimale est ĉ ≥ 0.
Théorème 3.3.3 Soit k dans J tel que ĉk < 0. Si Âk , la colonne associée à la variable xk dans la
matrice  est telle que Âk ≤ 0, alors on peut diminuer indéfiniment la fonction objectif, ce qui signifie
que (z ∗ = −∞). On dit alors que l’optimum de (P L) est non borné ou que (P L) n’admet pas de solution
optimale à distance finie.
Preuve : Considérons dans le système Ax = b la solution x(α) obtenue en imposant aux variables hors
base les valeurs suivantes :
xj = 0 ∀ j ∈ J − k et xk = α.
On obtient alors
xi = b̂i − αâik ∀i ∈ I.
La solution x(α) est réalisable pour tout α ≥ 0.
On a : ∑
Z(x(α)) = Ẑ + ĉj xj = Ẑ + αĉk
j∈J
Comme ĉk < 0, on a Z(x(α)) qui tend vers −∞ pour λ tendant vers +∞. Donc Z ∗ = −∞.
18
Exemple 3.3.7
Z = −x1 − 2x2
min
−2x1 + x2 + x3 = 2
−x1 + 2x2 + x4 = 5
x − 4x2 + x5 = 4
1
x ∈ R5 , x ≥ 0
Soit I = {1, 2, 5}. La matrice associée à I est :
−2 1 0
B = −1 2 0
1 −4 1
On a :
− 23 1
3 0 1
3
B −1 = − 13 2
3 0 , B −1 b = 8
3
≥ 0.
− 23 7
3 1 43
3
Donc c’est une base réalisable. La forme canonique par rapport à cette base est :
Z =2 − 3 −
17 4 5
min 3 x3 + 3 x4
x1 − 3 x3 + 13 x4 = 13
x2 − 13 x3 + 23 x4 = 83
x − 2 x + 7 x = 43
5 3 3 3 4 3
x≥0
La colonne de la variable hors base x3 est négative dans cette forme. On remarque que
1 2
3 + 3α
8 + 1α
3 3
x(α) = α
0
43 2
3 + 3α
Remarque 3.3.5 On a les mêmes résultats dans le cas des problèmes de maximisation si on remplace
la condition ĉk < 0 par ĉk > 0 dans le théorème (3.3.3).
Dans le théorème qui suit on montre que si pour tout k ∈ J tel que ĉk < 0, on a Âk 0 alors il existe
une base réalisable qui améliore la fonction-objectif Z.
Théorème 3.3.4 Soit B une base réalisable, on note I et J respectivement les ensembles des indices
des variables de base et hors base, b̂ = B −1 b, Â = B −1 A et ĉ = c − cB B −1 A. Soit k ∈ J tel que ĉk < 0 et
Âk 0. Soit l tel que [ ]
b̂l b̂i
= min : i ∈ I, âik > 0 .
âlk âik
Alors la matrice B ′ associée aux variables dont les indices sont dans I ′ = I − l + k est une base réalisable
adjacente à B. Et on a
b̂l
Z(x(B ′ )) = Z(x(B)) + ĉk .
âlk
19
Preuve : La matrice associée à I ′ = I − l + k est B ′ = BM . où
( )
M = e1 e2 · · · el−1 Âk el+1 · · · em
Pour que cette solution de base soit réalisable il suffit qu’elle vérifie les contraintes de non-négativité,
c’est-à-dire : {
xk = âb̂lkl ≥ 0
xi = b̂i − âik âb̂lkl ≥ 0 ∀ i ∈ I − l
Ce qui est équivalent à : [ ]
b̂l b̂i
0≤ = min : i ∈ I, âik > 0 ,
âlk âik
qui est vrai par le choix de l. Par suite I ′ = I − l + k est une base réalisable. En outre on a :
b̂l b̂l
Z(x(B ′ )) = Ẑ + ĉk xk = Ẑ + ĉk = Z(x(B)) + ĉk .
âlk âlk
Comme
b̂l
ĉk < 0 et ≥ 0,
âlk
on a bien Z(x(B ′ )) ≤ Z(x(B)).
Remarque 3.3.6 Si la base B est non dégénérée, on a : Z(x(B ′ )) < Z(x(B)). c’est-à-dire que la
décroissance est stricte.
Phase 1
Dans cette phase on détermine une première solution de base réalisable du problème. Si cette procédure
échoue, cela signifie que le polyèdre des solutions réalisables D du problème est vide.
Phase 2
Dans cette partie, on calcule à partir de la solution réalisable obtnue dans la phase 1 une autre solution
de base réalisable donnant une meilleure valeur de la fonction-objectif. Géométriquement, une itération
20
consiste à passer d’un sommet de D à un sommet de D ; ce nouveau sommet est adjacent au premier en
ce sens qu’ils sont les extrémités d’une arête de D.
Nous donnons ici une itération de la phase 2 de l’algorithme du simplexe.
Début
On suppose qu’on dispose d’une base réalisable de depart B. Soit I et J respectivement les ensembles
des indices des variables de base et hors base.
1) Calculer b̂ = B −1 b, Â = B −1 A et ĉ = c − cB B −1 A.
2) Tester ĉ.
a) Si ĉ ≥ 0, stop : ”La base B est optimale.”
b) S’il existe k ∈ J tel que ĉk < 0 avec Âk ≤ 0, stop : ”Le problème est non bornée i.e. la valeur
optimale est infinie.”
c) Autrement effectuer un changement de base.
3) Changement de base
a) Test d’entrée : Soit k ∈ J tel que
I := I − l + k et J := J − k + l
Aller à 1).
Fin
Remarque 3.3.7 Dans le cas d’un problème de maximisation, il n’est pas nécessaire de transformer le
problème en un problème de minimisation afin d’appliquer l’algorithme du simplexe. Il suffit de considérer
les modifications suivantes :
21
3.3.5 Convergence de l’algorithme du simplexe
On a le résultat suivant
Théorème 3.3.5 Si à chaque base réalisable rencontrée dans résolution du problème (P L) la solution
de base associée est non dégénérée, l’algorithme se termine en un nombre fini d’itérations par l’une des
deux situations suivantes :
i) obtention d’une solution de base réalisable optimale de (P L)
ii) absence de solution optimale à distance finie.
contient plus d’un élément, alors le problème (P L) est dégénéré i.e. il existe une base dégénérée.
Lorsque le problème est dégénéré, l’algorithme du simplexe peut cycler c’est-à-dire qu’on peut retrou-
ver une base déjà rencontrée. Pour remédier à cela on peut utiliser l’une des règles suivantes.
- la règle de Bland ou la règle du plus petit indice
- la règle lexicographique
- la règle de perturbation
La règle de Bland
Test d’entrée : La variable qui rentre dans la base est xk avec k le plus petit indice pour lequel
ĉk < 0
Test de sortie : La variable qui sort de la base est xl avec l le plus petit élément de L.
Z ∗ = min Z = cx
{
Ax = b
x ∈ Rn , x ≥ 0
toujours avec A ∈ Mm,n (R), c ∈ M1,n (R), et b ∈ Mm,1 (R) et rangA = m < n.
On suppose qu’on dispose d’une base réalisable de départ B Les ensembles des indices des variables
de base et hors-base sont I et J.
La forme canonique de (P L) par rapport à B est :
b
Z ∗ = min Z = ĉx + Z
{
Âx = b̂
x ∈ Rn , x ≥ 0
22
Définition 3.3.10 On appelle tableau simplexe complet de (P L) par rapport à la base réalisable B, le
tableau à m + 1 lignes et n + 1 colonnes ci-dessous :
xi i ∈ I xj j ∈ J
xi
 b̂
i∈I
ĉ −Ẑ
Définition 3.3.11 On appelle tableau simplexe de (P L) par rapport à la base réalisable B, le tableau à
m + 1 lignes et n − m + 1 colonnes ci-dessous
xj j ∈ J
xi
ÂN = B −1 N b̂
i∈I
ĉN −Ẑ
A partir du tableau simplexe on peut écrire la forme canonique de (P L) par rapport à la base B et
inversement.
On définit :
Définition 3.3.12 Dans le tableau simplexe, on appelle pivot l’élément qui est à l’intersection de la
colonne de la variable rentrante et de la ligne de la variable sortante.
Dans ce cas la ligne correspondante est dite ligne du pivot et la colonne, colonne du pivot.
La méthode des tableaux consiste à écrire les tableaux simplexes relatifs aux différentes bases ren-
contrées dans la résolution du programme (P L) à l’aide de l’algorithme du simplexe. Il faut donc
déterminer pour deux bases successives dans l’algorithme du simplexe B et B ′ comment passer du tableau
simplexe relatif à B à celui relatif à B ′ .
Pour obtenir le tableau simplexe de (P L) relatif à B ′ à partir de celui relatif à B on utilise le cadre
du tableau simplexe relatif à B et on considère les règles suivantes.
Règle du rectangle
Soit l ∈ I la ligne du pivot et k ∈ J la colonne du pivot.
âik âlj
Pour i ∈ I − l et j ∈ J − k, l’élément âij est remplacé par âij − âlk .
On note alors
âik âlj
âij := âij −
âlk
Remarque 3.3.8 Si une ligne intersecte la colonne du pivot par un zéro, la ligne reste inchangée.
Si une colonne intersecte la ligne du pivot par un zéro, la colonne reste inchangée.
Dans la méthode des tableaux une base sera désignée indifféremment par la matrice elle-même ou par
l’ensembles des indices des variables de base associées.
23
Exemple 3.3.8
Z = −3x1 + 2x2
min
2x1 + x2 ≤ 5
x1 − x2 ≤ 1
x + 2x2 ≤ 3
1
x 1 , x2 ≥ 0
On écrit le programme sous forme standard. On obtient :
Z = −3x1 + 2x2
min
2x1 + x2 + x3 = 5
x1 − x2 + x4 = 1
x + 2x2 + x5 = 3
1
xi ≥ 0, i = 1, · · · , 5
On remarque que I = {x3 , x4 , x5 } est une base réalisable évidente. En outre le programme est déjà
sous forme canonique par rapport à cette base. Les tableaux simplexes sont les suivants. :
x1 x2 x4 x2
x3 2 1 5 x3 -2 3 3
x4 1 -1 1 ← x1 1 -1 1
TS1 TS2
x5 1 2 3 x5 -1 3 2 ←
-3 2 0 3 -1 3
↑ ↑
x4 x5
x3 -1 -1 1
x1 2/3 1/3 5/3
TS3
x2 -1/3 1/3 2/3
8/3 1/3 11/3
Exemple 3.3.9
max
Z = 6x1 + 5x2
x1 + x2 ≤ 8
−2x1 + 3x2 ≤ 6
x − x2 ≤ 2
1
x1 , x 2 ≥ 0
On écrit le programme sous forme standard. On obtient :
max
Z = 6x1 + 5x2
x1 + x2 + x3 = 8
−2x1 + 3x2 + x4 = 6
x − x2 + x5 = 2
1
xi ≥ 0, i = 1, · · · , 5
On remarque que I = {x3 , x4 , x5 } est une base réalisable évidente. En outre le programme est déjà
sous forme canonique par rapport à cette base. Les tableaux simplexes sont les suivants.
24
x1 x2 x5 x2
x3 1 1 8 x3 -1 2 6 ←
x4 -2 3 6 x4 2 1 10
TS1 TS2
x5 1 -1 2 ← x1 1 -1 2
6 5 0 -6 11 -12
↑ ↑
x5 x3
x2 -1/2 1/2 3
x4 5/2 -1/2 7
TS3
x1 1/2 1/2 5
-1/2 -11/2 -45
Tous les coefficients de la fonction-objectif sont négatifs ou nuls on est donc à l’optimum. Une solution
optimale du problème initial est x∗ = (5, 3)T et la valeur optimale est Z ∗ = 45.
Exemple 3.3.10
Z = −3x1 + 5x2
min
−2x1 + 3x2 ≤ 6
x1 − 4x2 ≤ 4
x 1 , x2 ≥ 0
On écrit le programme sous forme standard. On obtient :
Z = −3x1 + 5x2
min
−2x1 + 3x2 + x3 = 6
x1 − 4x2 + x4 = 4
xi ≥ 0, i = 1, · · · , 4
On remarque que I = {x3 , x4 } est une base réalisable évidente. En outre le programme est déjà sous
forme canonique par rapport à cette base. Les tableaux simplexes sont les suivants.
x1 x2 x4 x2
x3 -2 3 6 x3 2 -5 14
TS1 x4 1 -4 4 ← TS2 x1 1 -4 4
-3 5 0 3 -7 12
↑ ↑
On remarque que la colonne de la variable x2 est toute négative, il n y a donc pas de pivot. Le
programme linéaire est alors non borné ; c’est-à-dire que la valeur optimale est −∞.
max
Z = 3x1 + 2x2
4x1 + 3x2 ≤ 12
4x1 + x2 ≤ 8
4x 1 − x2 ≤ 8
x1 , x2 ≥ 0
On remarque que I = {x3 , x4 , x5 } est une base réalisable évidente. En outre le programme est déjà
sous forme canonique par rapport à cette base.
x1 x2 x4 x2
x3 4 3 12 x3 -1 2 4 ←
x4 4 1 8 ← x1 1/4 1/4 2
TS1 TS2
x5 4 -1 8 x5 -1 0 0
3 2 0 -3/4 5/4 -6
↑ ↑
25
x4 x3
x2 -1/2 1/2 2
x1 3/8 -1/8 3/2
TS3
x5 -2 1 4
-1/8 -5/8 -17/2
On est à l’optimum. Une solution optimale du problème initial est x∗ = ( 32 , 2)T et la valeur optimale
est Z ∗ = 172 .
Dans les exemples que nous venons de traiter, on avait toujours une base réalisable évidente. Mais
très souvent il arive qu’on ne dispose pas de base réalisable dès le depart. Alors on utilise la phase
d’initialisation pour déterminer une première base réalisable.
Z ∗ = min Z = cx
{
Ax = b (P L)
x ∈ Rn , x ≥ 0
où A ∈ Mm,n (R), c ∈ M1,n (R), et b ∈ Mm,1 (R).
On suppose ici que b ≥ 0. Mais on ne fait pas l’hypothèse que rangA = m < n.
Les variables xai , i ∈ {1, · · · , m} sont appelées variables artificielles. Elles sont introduites juste pour
créer une base réalisable évidente pour (Pa ).
Par définition de (Pa ), on a ξ ∗ ≥ 0. Donc (Pa ) ne peut pas être non borné. En outre il n’est pas non
plus impossible car avec l’hypothèse que b ≥ 0, la solution (0, b)T est réalisable.
La matrice des vraies contraintes de (Pa ) est à = (A, Im ). Donc rangà = m < n + m et la matrice
formée des colonnes des variables artificielles est une base réalisable évidente de (Pa ). on peut donc
résoudre ce dernier à l’aide de la phase 2 du simplexe en partant de cette base.
Si la valeur optimale de (Pa ) n’est pas nulle alors le problème (P L) est impossible. Car en effet si
(P L) possédait une solution réalisable on montre facilement que ξ ∗ ≤ 0.
2ème cas ξ ∗ = 0 :
Notons (x∗ , xa∗ ) la solution optimale de (Pa ) obtenue où x∗ est relative aux variables structurelles ou
initiales du problème (P L) et xa∗ les variables artificielles. On a nécessairement xa∗ = 0.
26
1) Si dans cette solution toutes les variables artificielles sont hors-base c’est-à-dire que la base optimale
de (Pa ) est constituée uniquement de colonnes de la matrice A, alors cette dernière est une base réalisable
de (P L).
2) Si par contre il existe des variables artificielles dans la base, c’est-à-dire que la base optimale de
(Pa ) est constituée de colonnes de A pour les variables structurelles et de colonnes de la matrice Im pour
les variables artificielles. Cette base n’est pas nécessairement une base de (P L).
Supposons que les variables artificielles dans la base optimale de (Pa ) sont xai , i ∈ P . On a deux cas
possibles.
On suppose que le problème (Pa ) est sous forme canonique par rapport à la base optimale.
a) Si ∀ i ∈ P , la ligne correspondant à la variable de base artificielle xai contient un coefficient non nul
relatif à une variable non artificielle xj , alors on peut faire un changement de base. Dans la nouvelle base
la variable artificielle xai est remplacée par la variable xj . On obtient ainsi à la fin une base réalisable
optimale de (Pa ) constituée uniquement de colonnes de A. C’est donc une base réalisable de (P L). Mais
cette base est dégénérée.
b) Dans le cas contraire, si une variable artificielle dans la base optimale ne peut pas être remplacée
par une variable non artificielle, cela signifie que l’équation à laquelle est associée cette variable artifi-
cielle est redondante. C’est-à-dire qu’elle est combinaison linéaire d’autres équations. Elle peut donc être
supprimée.
Donc si on a un nombre q variables de ce genre, on a rangA = m − q. Dans ce cas les q lignes
correspondantes peuvent être éliminées. Les m − q variables restantes dans la base optimale de (Pa )
forment une base réalisable de (P L).
Remarque 3.3.9 1) Dans la méthode des tableaux lorsqu’on ne dispose pas de base réalisable évidente
et qu’on veuille appliquer soit la méthode des deux phases, on peut tenir compte de la situation suivante.
Etant donné que dans le programme auxiliaire l’introduction des variables artificielles sert à créer
uniquement une base réalisable évidente, il n’est pas nécessaire d’en ajouter systématiquement à chaque
équation.
Si une variable n’intervient que dans une seule équation et si le signe de son coefficient est égal à
celui du second membre de cette équation il n’est pas nécessaire d’ajouter une variable artificielle à cette
équation. Cette variable peut être considérée comme variable de base associée associée à cette équation.
2) Dans la méthode des tableaux lorsqu’une variable artificielle sort de la base il est certain qu’elle ne
peut plus y revenir la colonne correspondante devient superflue et peut être supprimée.
Exemple 3.3.12
27
min
ξ = x5 + x6
x1 + x2 + x3 + x5 = 5
2x1 + x2 + 3x3 − x4 + x6 = 9
xi ≥ 0, i = 1, · · · , 6
I = {x5 , x6 } est une base réalisable évidente de ce problème.
La forme canonique par rapport à cette base est :
ξ = 14 − 3x1 − 2x2 − 4x3 + x4
min
x1 + x2 + x3 + x5 = 5
2x1 + x2 + 3x3 − x4 + x6 = 9
xi ≥ 0, i = 1, · · · , 6
On a les tableaux simplexes suivants :
x1 x2 x3 x4
x5 1 1 1 0 5
∗ ←
TS1 x6 2 1 3 -1 9
-3 -2 -4 1 -14
↑
x1 x2 x6 x4
..
x5 1/3 2/3 . 1/3 2 ←
TS2 x3 2/3 1/3 .
.. -1/3 3
.
-1/3 -2/3 .. -1/3 -2
↑
x1 x5 x4
..
x2 1/2 . 1/2 3
TS3 ..
x3 1/2 . -1/2 2
..
0 . 0 0
I = {x2 , x3 } est une base réalisable du problème initial.
La forme canonique par rapport à cette base est :
Z =1 −x4 +
min
1
11
2 2 1 2 4=3
x + x + x
x3 + 21 x1 − 12 x4 = 2
xi ≥ 0, i = 1, · · · , 4
On a les tableaux simplexes suivants :
x1 x4
x1 x2
x2 1/2 1/2 3 ←
x4 1 2 6
TS4 x3 1/2 -1/2 2 TS5
x3 1 1 5
0 -1 -11
1 2 -5
↑
La condition d’optimalité est vérifiée, une solution optimale est :
x∗ = (0, 0, 5)T et la valeur optimale est Z ∗ = 5.
2) max Z = 2x1 − x2 + 3x3
x1 + x2 + x3 = 3
x1 − 2x2 + x3 ≥ 1
2x2 + x3 ≤ 2
xi ≥ 0, i = 1, · · · , 3
La forme standard de ce problème est :
28
Z = 2x1 − x2 + 3x3
max
x1 + x2 + x3 = 3
x1 − 2x2 + x3 − x4 = 1
2x2 + x3 + x5 = 2
xi ≥ 0, i = 1, · · · , 5
On n’a pas de base réalisable évidente. Utilisons la phase 1.
Considérons le programme auxiliaire :
min
ξ = x6 + x7
x1 + x2 + x3 + x6 = 3
x1 − 2x2 + x3 − x4 + x7 = 1
2x2 + x3 + x5 = 2
xi ≥ 0, i = 1, · · · , 7
I = {x6 , x7 , x5 } est une base réalisable de ce problème.
La forme canonique par rapport à cette base est :
ξ = 4 − 2x1 + x2 − 2x3 + x4
min
x1 + x2 + x3 + x6 = 3
x1 − 2x2 + x3 − x4 + x7 = 1
2x 2 + x3 + x5 = 2
xi ≥ 0, i = 1, · · · , 7
On a les tableaux simplexes suivants :
x7 x2 x3 x4
x1 x2 x3 x4 ..
x6 . 3 0 1 2 ←
x6 1 1 1 0 3
..
x7 1 -2 1 -1 1 ← x1 . -2 1 -1 1
TS1 TS2 ..
x5 0 2 1 0 2
x5 . 2 1 0 2
-2 1 -2 1 -4 ..
↑ . -3 0 -1 -2
↑
x6 x3 x4
..
x2 . 0 1/3 2/3
..
TS3 x1 . 1 -1/3 7/3
..
x5 . 1 -2/3 2/3
..
. 0 0 0
I = {x2 , x1 , x5 } est une base réalisable du problème initial.
La forme canonique par rapport à cette base est :
max
Z = 41 + x3 + x4
2
x 2 + x
3 4 =
3
x1 + x3 − 13 x4 = 37
x + x3 − 23 x4 = 32
5
xi ≥ 0, i = 1, · · · , 5
On a les tableaux simplexes suivants :
29
x3 x4 x3 x2
x2 0 1/3 2/3 ← x4 0 3 2
x1 1 -1/3 7/3 x1 1 1 3
TS4 TS5
x5 1 -2/3 2/3 x5 1 2 2 ←
1 1 -4 1 -3 -6
↑ ↑
x5 x2
x4 0 3 2
TS6 x1 -1 -1 1
x3 1 2 2
-1 -5 -8
La condition d’optimalité est vérifiée, une solution optimale est :
x∗ = (1, 0, 2)T et la valeur optimale est Z ∗ = 8.
3) min Z = 2x1 + 3x2 + 3x3 + x4 − 2x5
x1 + 3x2 + 4x4 + x5 = 2
x1 + 2x2 − 3x4 + x5 = 2
− 1 x − 4 x + x3 = 31
3 1 3 2
xi ≥ 0, i = 1, · · · , 5
On n’a pas de base réalisable évidente, utilisons la phase 1.
Considérons le programme auxiliaire suivant :
min ξ = x6 + x7
x1 + 3x2 + 4x4 + x5 + x6 = 2
x1 + 2x2 − 3x4 + x5 + x7 = 2
− 3 x1 − 3 x2 + x3 = 3
1 4 1
xi ≥ 0, i = 1, · · · , 7
I = {x6 , x7 , x3 } est une base réalisable évidente. La forme canonique par rapport à cette base est :
min ξ = 4 − 2x1 − 5x2 − x4 − 2x5
x1 + 3x2 + 4x4 + x5 + x6 = 2
x1 + 2x2 − 3x4 + x5 + x7 = 2
− 1 x − 4 x + x3 = 31
3 1 3 2
xi ≥ 0, i = 1, · · · , 7
On a les tableaux simplexes suivants :
x1 x6 x4 x5
x1 x2 x4 x5 ..
x2 1/3 . 4/3 1/3 2/3 ←
x6 1 3 4 1 2 ←
..
x7 1 2 -3 1 2 x7 1/3 . -17/3 1/3 2/3
x3 -1/3 -4/3 0 0 1/3 ..
x3 1/9 . 16/9 4/9 11/9
-2 -5 -1 -2 -4 ..
↑ -1/3 . 17/3 -1/3 -2/3
↑
x2 x6 x4 x5
..
x1 3 . 4 1 2
..
x7 -1 . -7 0 0
..
x3 -1/3 . 4/3 1/3 1
..
1 . 7 0 0
La condition d’arrêt est vérifiée mais la variable artificielle x7 est dans la base optimale. On remarque
que les coefficients de x2 et x4 sont non nuls dans la ligne de x7 . On peut donc remplacer dans la base
optimale x7 soit par x2 soit par x4 .
Si x2 rentre dans la base, on a les tableaux suivants :
30
x2 x6 x4 x5
.. x7 x4 x5
x1 3 . 4 1 2 ..
.. x1 . -17 1 2
x7 -1 . -7 0 0 ← ..
.. x2 . 7 0 0
x3 -1/3 . 4/3 1/3 1 ..
.. x3 . 11/3 1/3 1
1 . 7 0 0 ..
. 0 0 0
↑
Dans ce cas I = {x1 , x2 , x3 } est une base réalisable du programme initial.
Si par contre x4 rentre dans la base, on a les tableaux suivants :
x2 x6 x4 x5
.. x2 x7 x5
x1 3 . 4 1 2 ..
.. x1 17/7 . 1 2
x7 -1 . -7 0 0 ← ..
.. x4 1/7 . 0 0
x3 -1/3 . 4/3 1/3 1 ..
.. x3 -11/21 . 1/3 1
1 . 7 0 0 ..
0 . 0 0
↑
Dans ce cas I = {x1 , x4 , x3 } est une base réalisable du programme initial.
En partant de la base I = {x1 , x2 , x3 }, on obtient la phase 2 suivante :
x4 x5 x4 x1
x1 -17 1 2 ← x5 -17 1 2
x2 7 0 0 x2 7 0 0 ←
x3 11/3 1/3 1 x3 28/3 -1/3 1/3
3 -5 -7 -82 5 3
↑ ↑
x4 x1
x5 17/7 1 2
x4 1/7 0 0
x3 -4/3 -1/3 1/3
82/7 5 3
La condition d’arrêt du simplexe est vérifiée, on est à l’opitimum. Une solution optimale est : x∗ =
(0, 0, 13 , 0, 2)T et la valeur optimale est Z ∗ = −3.
4) min Z = x1 + x2 + x3
x1 + 2x2 + 3x3 = 3
−x1 + 2x2 + 6x3 = 2
4x2 + 9x3 = 5
3x3 + x4 = 1
xi ≥ 0, i = 1, · · · , 4
On n’a pas de base réalisable évidente, on va donc utiliser la phase 1.
Le programme auxiliaire est le suivant :
min ξ = x5 + x6 + x7
x1 + 2x2 + 3x3 + x5 = 3
−x1 + 2x2 + 6x3 + x6 = 2
4x2 + 9x3 + x7 = 5
3x3 + x4 = 1
xi ≥ 0, i = 1, · · · , 7
I = {x5 , x6 , x7 , x4 } est une base réalisable évidente. La forme canonique par rapport à cette base est :
31
ξ = 10 − 8x2 − 18x3
min
x1 + 2x2 + 3x3 + x5 = 3
−x1 + 2x2 + 6x3 + x6 = 2
4x2 + 9x3 + x7 = 5
3x3 + x4 = 1
xi ≥ 0, i = 1, · · · , 7
On a les tableaux simplexes suivants :
x1 x2 x6
x1 x2 x3 ..
x5 3/2 1 . 2
x5 1 2 3 3 ..
x6 -1 2 6 2 ← x3 -1/6 1/3 . 1/3
x7 0 4 9 5 ..
x7 3/2 1 . 2
x4 0 0 3 1 ..
0 -8 -18 -10 x4 1/2 -1 . 0 ←
..
↑ -3 -2 . -4
↑
x4 x5
x4 x2 ..
x5 -3 4 2 ← x2 -3/4 . 1/2
x3 1/3 0 1/3 ..
x3 1/3 . 1/3
x7 -3 4 2 ..
x1 2 -2 0 x7 0 . 0
..
6 -8 -4 x1 1/2 . 1
↑ ..
0 . 0
On est à l’optimum du programme auxiliaire. dans le tableau optimal la ligne de la variable de base x7
qui est une variable artificielle est toute nulle. La troisième équation du programme initial à laquelle est
associée la variable x7 est donc une équation redondante on peut donc la supprimer. Ainsi I = {x2 , x3 , x1 }
est une base réalisable du programme initial. La forme canonique par rapport à la base I est
Z = 63 − 12 x14
11 1
min
x2 − 4 x4 = 2
x3 + 13 x4 = 13
x1 + 12 x4 = 1
xi ≥ 0, i = 1, · · · , 4
On a les tableaux simplexes suivants :
x4 x3
x2 -3/4 1/2 x2 9/4 5/4
x3 1/3 1/3 ← x4 3 1
x1 1/2 1 x1 -3/2 1/2
-1/12 -11/6 1/4 -7/4
La condition d’arrêt du simplexe est vérifiée. On est à l’optiumum et une solution optimale du pro-
gramme est x∗ = ( 12 , 45 , 0, 1)T et la valeur optimale est Z ∗ = 74 .
32
On considère le problème auxiliaire suivant.
∗ = min Z
∑m a
ZM
{ M = cx + M i=1 xi
a
Ax + Im x = b (PM )
x ≥ 0, xa ≥ 0
Comme dans la phase 1, les variables xai , i ∈ {1, · · · , m} sont des variables artificielles.
La constante M est une constante symbolique et elle est aussi grande que l’on veut (c’est-à-dire
supérieure à tout nombre auquel elle pourra être comparée lors de la résolution du problème).
On remarque comme précédemment dans la phase 1 que la matrice des vraies contraintes de (PM )
est Ā = (A, Im ). Donc, rangĀ = m < n + m. Par suite avec l’hypothèse que b ≥ 0, la matrice formée des
colonnes des variables artificielles est une base réalisable évidente pour (PM ). On peut donc le résoudre
à l’aide de la phase 2 du simplexe en partant de cette base.
On montre que
Remarque 3.3.11 1) Etant donné que dans le programme auxiliaire l’introduction des variables artifi-
cielles sert à créer uniquement une base réalisable évidente, il n’est pas nécessaire d’en ajouter systématiqueme
à chaque équation. En effet, si une variable n’intervient que dans une seule équation et si le signe de
son coefficient est égal à celui du second membre de cette équation il n’est pas nécessaire d’ajouter une
variable artificielle à cette équation. Cette variable peut être considérée comme variable de base associée
associée à cette équation.
2) Dans la méthode des tableaux lorsqu’une variable artificielle sort de la base il est certain qu’elle ne
peut plus y revenir la colonne correspondante devient superflue et peut être supprimée.
Exemple 3.3.13
33
min ZM = 8x1 + 7x2 + 3x3 + M x6
2x1 + x2 − x4 + x6 = 1
x1 + 2x2 + x3 − x5 = 1
xi ≥ 0, i = 1, · · · , 5
I = {x6 , x3 } est une base réalisable évidente de ce problème.
La forme canonique par rapport à cette base est :
x3 x4 x5
x1 -1/3 -2/3 1/3 1/3
TS3 x2 2/3 1/3 -2/3 1/3
1 3 2 -5
34
On a : ZM = −10M + x1 + (1 − 8M )x2 + (1 − 18M )x3
Donc la forme canonique du programme par rapport à la base I est :
x1 x2 x4
x5 1 2 -1 2
x6 -1 2∗ -2 0 ←
TS2 x7 0 1 -3 2
x3 0 0 1/3 1/3
1 1-8M -1/3+6M -1/3-4M
↑
x1 x6 x4
..
x5 2 . 1 2 ←
..
x2 -1/2 . -1 0
TS3 ..
x7 2 . 1 2
..
x3 0 . 1/3 1/3
..
3/2-4M . 2/3-2M -1/3-4M
↑
x5 x4
.. x3
x1 . 1/2 1
.. x1 -3/2 1/2
x2 . -3/4 1/2 x2 9/4 5/4
TS4 .. TS5 x7 0 0
x7 . 0 0
.. x4 3 1
x3 . 1/3 1/3 ← 1/4 -7/4
..
. -1/12 -11/6
↑
35
3) min Z = x1 − x2
−2x1 + x2 ≤ 2
−x1 + 2x2 ≥ 8
x + x2 ≤ 5
1
xi ≥ 0, i = 1, · · · , 2
La forme standard de ce problème est
Z = x1 − x2
min
−2x1 + x2 + x3 = 2
−x1 + 2x2 + x3 − x4 = 8
x + x2 + x5 = 5
1
xi ≥ 0, i = 1, · · · , 5
On n’a pas de base réalisable évidente. Utilisons la méthode du grand M .
Considérons le programme auxiliaire :
min ZM = x1 − x2 + M x6
−2x1 + x2 + x3 = 2
−x1 + 2x2 + x3 − x4 + x6 = 8
x + x2 + x5 = 5
1
xi ≥ 0, i = 1, · · · , 6
I = {x3 , x6 , x5 } est une base réalisable évidente de ce problème.
La forme canonique par rapport à cette base est :
x1 x3 x4
x2 −2 1 0 2
x6 3 -2 -1 4
TS2
x5 3 -1 0 3 ←
-1-3M 1+2M M 2-4M
↑
x5 x3 x4
x2 2/3 5/3 0 4
x6 -1 -3 -1 1
TS3
x1 1/3 -1/3 0 1
1/3+M 2/3+M M 3-M
On est à l’optimum pour PM ; mais il existe une variable artificielle non nulle à l’optimum. Alors le
problème initial est impossible.
36
Chapitre 4
Etant donné un programme linéaire on peut toujours lui associer un autre programme linéaire appelé
programme dual du programme initial : dans ce cas le programme initial est appelé programme primal.
Ces deux programmes sont dits alors programmes duaux, ou duals, ou en dualité.
4.1 Définitions
On sait que par convention les contraintes d’inégalité pour un problème de minimisation sont du type
” ≥ ” et les contraintes d’inégalité pour un problème de maximisation sont du type ” ≤ ”.
Nous allons adopter les conventions suivantes :
Dans un programme de minimisation une contrainte d’inégalité du type ” ≥ ” sera dite ”vraie
inégalité” et une contrainte du type ” ≤ ” sera dite ”fausse inégalité”.
Dans un programme de maximisation une contrainte d’inégalité du type ” ≤ ” sera dite ”vraie
inégalité” et une contrainte du type ” ≥ ” sera dite ”fausse inégalité”.
Définition 4.1.1 Etant donné le programme linéaire sous la forme générale (P ) ci-dessous
∑
min Z(x) = nj=1 cj xj
∑n
aij xj ≥ bi , i = 1, · · · , m1
∑j=1
n
aij xj ≤ bi , i = m1 + 1, · · · , m2
∑j=1
n
i = m2 + 1, · · · , m
j=1 aij xj = bi ,
xj ≥ 0, j = 1, · · · , n1
xj ≤ 0, j = n1 + 1, · · · , n2
xj ∈ R, j = n2 + 1, · · · , n.
On appelle programme dual de (P ) le programme linéaire (D) ci-dessous
∑
m
max W = bi yi
i=1
yi ≥ 0 i = 1, ..., m1
yi ≤ 0 i = m1 + 1, ..., m2
yi libre j = m2 + 1, ..., m
∑m (D)
aij yi ≤ cj j = 1, ..., n1
i=1
∑m
aij yi ≥ cj j = n1 + 1, ..., n2
i=1
∑m
aij yi = cj i = n2 + 1, ..., n.
i=1
37
Cette définition est caractérisée par les règles suivantes :
1) A un problème primal de minimisation (de maximisation) correspond un problème dual de maxi-
misation (minimisation).
2) A toute vraie contrainte primale correspond une variable duale : si la vraie contrainte est une ”vraie
inégalité”, la variable duale est soumise à une condition de non-négativité (” ≥ 0”) ;
si la vraie contrainte est une ”fausse inégalité”, la variable duale est soumise à une condition de non-
positivité (” ≤ 0”) ;
si la contrainte est une égalité, la variable duale est libre.
3) A toute variable primale correspond une contrainte duale :
- si la variable primale est soumise à une condition de non-négativité, la contrainte duale est une ”vraie
inégalité”.
- si la variable primale est soumise à une condition de non-positivité, la contrainte duale est une ”fausse
inégalité”.
- si la variable primale est libre, la contrainte duale est une égalité.
4) Les coefficients de la fonction-objectif du primal deviennent les seconds membres des contraintes
duales. Les seconds membres des vraies contraintes primales deviennent les coefficients de la fonction-
objectif du dual.
5) La matrice des vraies contraintes du dual est la transposée de la matrice des vraies contraintes du
primal.
Exemple 4.1.1
min
Z = 3x1 + 2x2 + x3
2x1 + 5x2 + x3 = 5
x1 − 3x2 − x3 ≥ 1
4x1 + 2x2 + 6x3 ≤ 3
x1 ≥ 0, x2 ≤ 0, x3 ∈ R.
On considère les variables duales : y1 associée à la première contrainte, y2 à la deuxième et y3 à la
troisième. Le dual est alors :
max
W = 5y1 + y2 + y3
2y1 + 4y2 + y3 ≤ 3
5y1 − 3y2 + 2y3 ≥ 2
y1 − y2 + 6y3 = 1
y1 ∈ R, y2 ≥ 0, y3 ≤ 0.
38
Exemple 4.1.2
max
{ W = yb
yA ≤ c
y ≥ 0.
Afin de conserver les mêmes données dans les deux programmes,nous considérons dans la notation
matricielle du dual la variable duale y sous forme de matrice ligne contrairement à la variable primale
qui elle est une matrice colonne. Signalons qu’un programme linéaire et son dual sont deux aspects d’un
même problème.
Remarque 4.1.1 On remarque une symétrie dans les deux programmes. Ils sont tous sous forme cano-
nique : (contraintes d’inégalités et variables non-négatives).
On a la propriété suivante :
Proposition 4.1.1 L’opération de la dualité est involutive (i.e le dual du dual est le primal).
Z ∗ ={min Z = cx
Ax ≥ b (P )
x≥0
W∗ =
{ max W = yb
yA ≤ c (D)
y≥0
Corollaire 4.2.2 Si Z ∗ = −∞, le problème (D) n’admet pas de solution réalisable (i.e le dual (D) est
impossible si (P ) est non borné).
De même si W ∗ = +∞, le problème primal n’admet pas de solution réalisable, en d’autres termes, si le
dual (D) est non borné, le primal (P ) est impossible.
39
Preuve : Si x∗ n’est pas solution optimale de (P ) i.e ∃x solution réalisable de (P ) avec cx < cx∗ (car
problème de minimisation)
cx < cx∗ = y ∗ b, absurde !
On montre de même pour l’autre cas.
Le problème (P ) admet une solution optimale finie si et seulement si (Pe) admet une solution optimale
finie. ( )
e x
c = (c, 0), A = (A − Im ) et u =
Notons e . Le problème (Pe) s’écrit alors
s
Z ∗ = min Z = e
cu
{
e
Au = b
u≥0
Supposons alors que (Pe) possède une solution optimale finie, il existe donc une solution réalisable de
base optimale. Soit B une base réalisable optimale et u∗ la solution de base réalisable optimale associée.
On sait par ailleurs que le dual de (Pe) est :
W∗ =
{ max W = yb
yA ≤ c
y≥0
e ≥ 0 (car problème de minimisation). Ce qui est équivalent
c − c̃B B −1 A
Comme B est optimale, alors e
à {
c−e cB B −1 A ≥ 0
cB B −1 ≥ 0
e
Posons y ∗ = e
cB B −1 . On remarque que y ∗ est solution réalisable du dual. En outre on a : Z(u∗ ) =
cB B b = y b = W (y ∗ ). Ce qui implique d’après le corollaire(4.2.3) que y ∗ est solution optimale de (D).
e −1 ∗
Corollaire 4.2.5 Etant donné une paire de problèmes en dualité, il n’existe que 4 situations possibles
parmi les 9 potentielles.
1) Les deux problèmes possèdent des solutions optimales finies
2) a) Le problème primal non borné, et le problème dual est impossible
b) le problème dual est non borné et le problème primal est impossible
3) Les deux problèmes sont impossibles.
40
On peut schématiser cela dans le tableau suivant
Solution optimale Problème Problème
Primal/ dual
finie non borné impossible
Solution optimale
1) non non
finie
Problème
non non 2) a)
non borné
Problème
non 2) b) 3)
impossible
41
Théorème 4.3.2 (théorème fort des écarts complémentaires)
Une solution réalisable x de (P ) est une solution optimale de (P ) si et seulement si il existe y une solution
réalisable du dual telle que {
yAj = cj si xj > 0 ∀ j
yi = 0 si ai x > bi ∀ i
Exemple 4.3.1
min
Z = x1 + x2
3x1 + x2 ≥ 4
x1 + 4x2 ≥ 5
x 1 , x2 ≥ 0
min
Z = 2x1 + 3x2
2x1 + x2 ≥ 3
2x1 − x2 ≥ 5
x + 4x2 ≥ 6
1
x 1 , x2 ≥ 0
42
y1 =0
y3 =0
y =1
2
y2 = −3
Ce qui n’est pas. En conclusion le point x n’est pas solution optimale.
ii) On vérifie facilement la réalisabilité de x. C’est une solution optimale si et seulement si il existe
une solution réalisable y du dual telle que
(2x1 + x2 − 3)y1 = 0
(2x1 − x2 − 5)y2 = 0
(x1 + 4x2 − 6)y3 = 0
(2y1 + 2y2 + y3 − 2)x1 = 0
(y1 − y2 + 4y3 − 3)x2 = 0
Ce qui donne la solution y = (0, 59 , 89 )T qui est bien une solution réalisable du dual. Par suite x est une
solution optimale.
Z ∗ ={min Z = cx
Ax = b (P L)
x≥0
On a la définition suivante :
c = c − cB B −1 A ≥ 0.
Définition 4.4.1 Soit B une base de (P L). Cette base est dite duale réalisable si b
Par opposition, B est primale réalisable si bb = B −1 b ≥ 0.
Remarque 4.4.1 1) Pour un problème de maximisation une base B est dite duale réalisable si b
c =
−1 b −1
c − cB B A ≤ 0. Elle est primale réalisable si b = B b ≥ 0.
2) Une base B qui est à la fois primale et duale réalisable est optimale.
43
b = B −1 A, b
A c = c − cB B −1 A et bb = B −1 b.
On suppose que B est dual réalisable.
2) Tester bb = B −1 b.
a) Si bb ≥ 0, stop : (la solution courante est optimale).
b) Si ∃i ∈ I tel que bbi < 0 et baij ≥ 0 ∀j ∈ J, stop : (le problème (P L) est impossible).
c) Autrement, on effectue un changement de base.
3) Changement de base
a) Test de sortie : Soit l ∈ I telle que
bbl = min[bbi : i ∈ I, bbi < 0].
i
Remarque 4.4.2 Dans le cas d’un problème de maximisation cet algorithme reste valable
Exemple 4.4.1
min
Z = 8x1 + 6x2 + 2x3
x1 − 2x2 + x3 ≥ 6
x1 + 3x2 − x3 ≥ 5
x1 , x2 , x3 ≥ 0.
La forme standard de (P1 ) est :
min
Z = 8x1 + 6x2 + 2x3
x1 − 2x2 + x3 − x4 = 6
x1 + 3x2 − x3 − x5 = 5
xi ≥ 0, i = 1, · · · , 5.
L’ensemble I = {4, 5} est une base évidente. La forme canonique par rapport à I est :
min
Z = 8x1 + 6x2 + 2x3
−x1 + 2x2 − x3 + x4 = −6
−x1 − 3x2 + x3 + x5 = −5
xi ≥ 0, i = 1, · · · , 5.
On a ĉ ≥ 0 donc I est une base duale réalisable.
On a les tableaux simplexes successifs suivants.
x1 x2 x3 x1 x2 x4
x4 -1 2 -1 -6 ← x3 1 -2 -1 6
TS1 x5 -1 -3 1 -5 TS2 x5 -2 -1 1 -11 ←
8 6 2 0 6 10 2 -12
↑ ↑
x5 x2 x4
x3 1/2 -5/2 -1/2 1/2
TS3
x1 -1/2 1/2 -1/2 11/2
3 7 5 -45
La condition d’arrêt de l’algorithme est vérifiée une solution optimale du problème est x∗ = ( 11 1 T
2 , 0, 2 )
et la valeur optimale est Z ∗ = 45.
44
Exemple 4.4.2
Z = −5x1 − 21x3
max
x1 − x2 + 6x3 ≥ 2
x1 + x2 + 2x3 ≥ 1
x1 , x2 , x3 ≥ 0.
La forme standard est :
Z = −5x1 − 21x3
max
x1 − x2 + 6x3 − x4 = 2
x1 + x2 + 2x3 − x5 = 1
xi ≥ 0, i = 1, · · · , 5.
L’ensemble I = {4, 5} est une base évidente. La forme canonique par rapport à I est :
Z = −5x1 − 21x3
max
−x1 + x2 − 6x3 + x4 = −2
−x1 − x2 − 2x3 + x5 = −1
xi ≥ 0, i = 1, · · · , 5.
On a ĉ ≤ 0 donc I est une base duale réalisable.
On a les tableaux simplexes successifs suivants.
x1 x2 x3 x1 x2 x4
x4 -1 1 -6 -2 ← x3 1/6 -1/6 -1/6 1/3
TS1 x5 -1 -1 -2 -1 TS2 x5 -2/3 -4/3 -1/3 -1/3 ←
-5 0 -21 0 -3/2 -21/6 -21/6 7
↑ ↑
x5 x2 x4
x3 1/2 -1/2 -1/4 1/4
TS3
x1 -3/2 2 1/2 1/2
-9/4 -1/2 -11/4 31/4
La condition d’arrêt de l’algorithme est vérifiée une solution optimale du problème est x∗ = ( 12 , 0, 14 )T
et la valeur optimale est Z ∗ = − 314 .
Cette méthode est nécessaire dans le cas où il existe B une base initiale mais qui n’est pas duale
réalisable. On considère pour cela un problème artificiel (Pa ), créé de la façon suivante.
Soit le problème (P L) mis sous forme canonique par rapport à la base B. A ce problème on ajoute
une contrainte supplémentaire appelée contrainte artificielle :
∑
v+ xj = M
j∈K
où
• v est une variable artificielle non négative (v ≥ 0)
• K = {j ∈ J : bcj < 0}
• M est une constante symbolique positive aussi grande que l’on veut (c’est-à-dire supérieur à tout
nombre auquel il pourra être comparé).
En résumé on a :
min Z = Z b+b cx
−1 N x = b
x
B ∑ + B N b
v+ xj = M (Pa )
j∈K
x ≥ 0, v ≥ 0.
45
Il est immédiat que Ia = I ∪ {v} est une base évidente de (Pa ).
On considère le changement de base imposé suivant :
• v sort de la base Ia
• la variable xk telle que b cj : j ∈ K} rentre dans la base.
ck = min{b
On obtient immédiatement une base duale réalisable pour (Pa ). On résout ce dernier à l’aide de
l’algorithme dual phase 2 en partant de cette base.
1) Si (Pa ) n’admet pas de solution réalisable, le problème initial (P L) n’admet pas de solution
réalisable non plus.
2) Si (Pa ) admet une solution optimale dans laquelle la variable artificielle v est nulle, et si Z dépend
de M , le problème (P L) est non borné. Si par contre Z ne dépend pas de M , on obtient une solution
optimale de base réalisable de (P L) en donnant à M la plus petite valeur vérifiant xi ≥ 0 pour tout xi
variable de base à l’optimum.
3) Si (Pa ) admet une solution optimale dans laquelle v est positive, alors mise à part la variable v, la
solution obtenue constitue une solution optimale de (P L).
Remarque 4.4.3 1) Dans le cas d’un problème de maximisation, l’algorithme reste valable moyennant
les modifications suivantes :
• K = {j ∈ J : bcj > 0}
• Dans le changement de base initial imposé, la variable rentrante est xk avec k tel que bck = max{b cj :
j ∈ K}
2) Dans la méthode des tableaux, après le changement de base initial imposé, si en cours d’algorithme,
la variable artificielle v, revient dans la base, il est certain qu’elle n’en sortira plus. Ainsi, la ligne
correspondante dans le tableau simplexe devient superflue et peut être supprimée.
3) La méthode duale simplexe s’applique de préférence à des programmes linéaires sous forme cano-
nique.
Exemple 4.4.3
46
Ici on a K = {x3 }. Donc le programme auxiliaire est :
Ia = {x4 , x5 , v} est une base évidente du programme auxiliaire ci-dessus et le programme est sous
forme canonique par rapport à Ia .
On a le premier tableau simplexe à partir duquel on fait le changement de base initial imposé.
x1 x2 x3 x1 x2 v
x4 -1 -1 -1 -6 x4 -1 -1 1 -6+M
x5 -2 0 2 -9 x5 -2 0 -2 -9-2M ←
TS1 TS2
v 0 0 1 M ← x3 0 0 1 M
6 3 -2 0 6 3 2 2M
↑ ↑
La variable artificielle v est rentrée dans la base il est certain qu’elle n’en sortira plus donc la ligne
correspondante peut être supprimée.
x1 x2 x5
x4 -2 -1 1/2 -21/2 ← x4 x2 x5
v ... ... ... ... x1 -1/2 1/2 -1/4 21/4
TS3 TS4
x3 -1 0 1/2 -9/2 x3 -1/2 1/2 1/4 3/4
4 3 1 -9 2 1 2 -30
↑
La condition d’arrêt de l’algorithme est vérifiée. Une solution optimale du problème est x∗ = ( 21 3 T
4 , 0, 4 )
et la valeur optimale est Z ∗ = 30.
Règles de Bland
Test de sortie : La variable sortante est xl qui vérifie :
[ ]
l = min i ∈ I : bbi < 0 .
47
Chapitre 5
Il peut arriver, dans de nombreux problèmes, que certaines données soient liées à des fluctuations, ou
ne soient pas connues avec précision au moment où le programme mathématique est construit. Une telle
situation se présente notamment, lorsque le même problème de décision se pose de façon répétée (tous les
jours, toutes les semaines, ou tous les mois), mais fait intervenir la valeur de certaines grandeurs (stocks
disponibles, cours des matières premières, niveau de la demande, etc) variables dans le temps. On peut
songer dans ce cas, à faire dépendre ces données d’un ou plusieurs paramètre(s).
La programmation linéaire paramétrique est la résolution d’un programme linéaire dont certains
coefficients dépendent linéairement d’un paramètre λ ou de plusieurs. Il s’agit de déterminer la solution
optimale x∗ (λ) en fonction de λ. On considère généralement les cas suivants :
- le paramètre intervient exclusivement dans la fonction-objectif ;
- le paramètre intervient exclusivement dans le second membre des vraies contraintes.
Les autres cas ne sont étudiés ici car moins fréquents dans la pratique et plus difficiles à résoudre.
Deux autres problématiques étroitement liés à la programmation linéaire paramétrique.
On suppose qu’il existe un λ tel que le polyèdre des solutions réalisables de (P L(λ)) est non vide
et qu’on dispose d’une base primale réalisable B. Soit I (respectivement J) l’ensemble des indices des
variables (respectivement hors base) associées à B.
Définition 5.1.1 On appelle intervalle de stabilité relatif à la solution associée à B, l’intervalle (éventuelleme
vide) des valeurs du paramètre λ pour lesquelles la solution associée à B est solution optimale de (P L(λ)).
On montre que
48
Proposition 5.1.1 L’intervalle de stabilité associé à B est [λ, λ] avec
{ } { }
ĉ1j ĉ1
j
λ = max − 2 : j ∈ J ĉ2j > 0 et λ = min − 2 : j ∈ J ĉ2j < 0 .
ĉj ĉj
Remarque 5.1.1
1) On a λ = −∞ si ĉ2j ≤ 0, ∀ j ∈ J et λ = +∞ si ĉ2j ≥ 0, ∀ j ∈ J.
2) L’intervalle de stabilité est vide si λ > λ
On définit
Définition 5.1.2 Deux intervalles de R sont dits adjacents si la borne supérieure du premier coincide
avec la borne inférieure du second. Par exemple [a, b] et [b, c].
On suppose qu’on dispose d’un intervalle de stabilité associé à B. Pour déterminer un éventuel nou-
vel intervalle de stabilité adjacent, on fait le changement de base suivant dans l’algorithme primal du
simplexe :
• la variable xk (k ∈ J) rentrant dans la base est celle dont le coefficient ĉ1j + λĉ2j s’annule pour λ = λ
(respectivement λ).
• la variable sortant de la base est déterminée par la règle classique de l’algorithme primal du simplexe.
Un tel changement de base permet de déterminer l’intervalle de stabilité adjacent à [λ, λ] du côté de
λ (respectivement λ).
Remarque 5.1.2 Si pour un tel changement de base il n’existe pas de pivot (positif ) cela signifie qu’au-
délà de cette valeur λ (respectivement λ) le problème est non borné.
Le problème (P L(λ)) est complètement résolu lorsque l’intervalle de définition du paramètre λ est
décomposé en intervalles de stabilité et en intervalles où le problème est non borné.
Exemple 5.1.1
min
Z = (8 + 2λ)x1 + (7 + 7λ)x2 + (3 + 2λ)x3
2x1 + x2 ≥ 1
x1 + 2x2 + x3 ≥ 1
x 1 , x 2 , x3 ≥ 0
min
Z = (8 + 2λ)x1 + (7 + 7λ)x2 + (3 + 2λ)x3
2x1 + x2 − x4 = 1
x1 + 2x2 + x3 − x5 = 1
x 1 , x 2 , x3 ≥ 0
Il n y a pas de base réalisable évidente on doit donc utiliser soit la phase 1 ou la méthode du grand
M.
Utilisons la méthode du grand M .
La variable x3 n’intervient que dans la deuxième contrainte et le signe de son coefficient est égal à
celui du second membre. Elle peut être considérée comme de base associée à cette équation. Il n’est donc
plus nécessaire d’ajouter une variable artificielle à cette équation.
Le programme auxiliaire est :
49
min
Z = (8 + 2λ)x1 + (7 + 7λ)x2 + (3 + 2λ)x3 + M x6
2x1 + x2 − x4 + x6 = 1
x1 + 2x2 + x3 − x5 = 1
xi ≥ 0, i = 1, · · · , 6.
I = {x6 , x3 } est une base réalisable évidente. Le programme sous forme canonique par rapport à cette
base est :
La base I = {x1 , x3 } est optimale pour λ tel que ĉ ≥ 0. Ce qui donne λ ∈ [ 12 , +∞[.
Dans ce cas une solution optimale est x∗ = ( 12 , 0, 12 )T et la valeur optimale est Z ∗ (λ) = 11
2 + 2λ.
Pour l’étape suivante on considère la variable hors base dont le coefficient s’annule pour λ = 12 .
x3 x4 x5
x1 -1/3 -2/3 1/3 1/3 ←
TS3 x2 2/3 1/3 -2/3 1/3
1 − 2λ 3−λ 2 + 4λ −5 − 3λ
↑
x3 x4 x1
x5 -1 -2 3 1
TS4 x2 0 -1 2 1
3 − 2λ 7 + 7λ −6 − 12λ −7 − 7λ
↑
50
5.2 Paramétrisation du second membre
Soit le problème
min
{ Z = cx
Ax = b = b1 + λb2 (P L(λ))
x ∈ Rn , x ≥ 0
où A ∈ Mm,n (R), c ∈ M1,n (R), et b ∈ Mm,1 (R) avec rangA = m < n.
L’ensemble des valeurs du paramètre λ pour lesquelles le problème possède une solution optimale
peut être décomposé en intervalles de stabilité chacun d’eux correspondant à une base optimale.
Soit B une base duale réalisable (éventuellement obtenue par application de la méthode de la contrainte
artificielle). Soit I (respectivement J) l’ensemble des indices des variables de base (respectivement hors
base) associé à B.
On suppose le problème écrit sous forme canonique par rapport à la base B. On montre que :
Remarque 5.2.1
1) On a λ = −∞ si b̂2i ≤ 0, ∀ i ∈ I et λ = +∞ si b̂2i ≥ 0, ∀ i ∈ I.
2) L’intervalle de stabilité est vide si λ > λ
Pour déterminer un éventuel nouvel intervalle de stabilité adjacent, on fait le changement de base
suivant dans l’algorithme dual du simplexe :
• la variable xl (l ∈ I) sortant de la base est celle dont le coefficient b̂1i + λb̂2i s’annule pour λ = λ
(respectivement λ).
• la variable rentrant dans la base est déterminée par la règle classique de l’algorithme dual du
simplexe.
Un tel changement de base permet de déterminer l’intervalle de stabilité adjacent à [λ, λ] du côté de
λ (respectivement λ).
Remarque 5.2.2 Si pour un tel changement de base, il n’existe pas de pivot (négatif ) cela signifie qu’au-
delà de cette valeur λ (respectivement λ) le problème est impossible.
Le problème (P L(λ)) est complètement résolu lorsque l’intervalle de définition du paramètre λ est
décomposé en intervalles de stabilité et/ou en intervalles pour lesquels le problème est impossible.
Exemple 5.2.1
max
Z = 6x1 + 5x2
x1 + x2 ≤ 8 − 2λ
−2x1 + 3x2 ≤ 6 − λ
x − x2 ≤ 2 + λ
1
x1 , x2 ≥ 0.
51
max
Z = 6x1 + 5x2
x1 + x2 + x3 = 8 − 2λ
−2x1 + 3x2 + x4 = 6 − λ
x − x2 + x5 = 2 + λ
1
xi ≥ 0, i = 1, · · · , 5.
I = {x3 , x4 , x5 } est une base évidente et le programme est déjà sous forme canonique par rapport à
cette base. On remarque qu’elle n’est pas duale réalisable. On va appliquer la méthode de la contrainte
artificielle.
Le programme auxiliaire est :
max
Z = 6x1 + 5x2
x1 + x2 + x3 = 8 − 2λ
−2x1 + 3x2 + x4 = 6 − λ
x1 − x2 + x5 = 2 + λ
x + x2 + v = M
1
xi ≥ 0, i = 1, · · · , 5.
I = {x3 , x4 , x5 , v} est une base évidente. Le premier tableau simplexe est :
x1 x2
x3 1 1 8 − 2λ
x4 -2 3 6−λ
TS1 x5 1 -1 2+λ
v 1 1 M ←
6 5 0
↑
Après le changement de base initial imposé, on obtient :
v x2
x3 -1 0 8 − 2λ − M ←
x4 2 5 6 − λ + 2M
TS2 x5 -1 -2 2+λ−M
x1 1 1 M
-6 -1 -6M
↑
La base duale réalisable I = {x3 , x4 , x5 , x1 } n’est optimale pour aucune valeur de λ. On utilise les
règles classiques pour le changement de base.
x3 x2
v ... ... ...
x4 2 5 22 − 5λ
TS3 x5 -1 -2 −6 + 3λ ←
x1 1 1 8 − 2λ
-6 -1 −48 − 12λ
↑
La base duale réalisable I = {v, x4 , x5 , x1 } est optimale si
22 − 5λ ≥ 0
−6 + 3λ ≥ 0
8 − 2λ ≥ 0
C’est-à-dire pour λ ∈ [2, 4]. Dans ce cas la solution optimale est x∗ (λ) = (8 − 2λ, 0)T et la valeur optimale
est Z ∗ (λ) = 48 + 12λ.
52
Remarque 5.2.3 Il n y a pas d’intervalle de stabilité adjacent du côté de 4 car le coefficient du second
membre qui s’annule pour λ = 4 ne permet pas d’avoir un pivot (négatif ). Donc pour λ ∈]4, +∞[ le
problème est impossible.
x3 x5
x4 -1/2 5/2 7 + 5λ/2 ←
x2 1/2 -1/2 3 − 3λ/2
TS4
x1 1/2 1/2 5 − λ/2
-11/2 -1/2 −45 + 21λ/2
↑
x4 x5
x3 -2 -5 −14 − 5λ
TS5 x2 1 2 10 + λ
x1 1 3 12 + 2λ
-11 -28 −122 − 17λ
Z ∗ = min Z = cx
{
Ax = b (P L)
x ∈ Rn , x ≥ 0
où A ∈ Mm,n (R), c ∈ M1,n (R), et b ∈ Mm,1 (R).
On suppose que B est une base réalisable optimale et que I (resp. J) sont les indices des variables de
base (resp. hors base) associées à la base B.
On note
Z ∗ = min Z = ĉx + Ẑ
{
Âx = b̂
x ∈ Rn , x ≥ 0
la forme canonique de (P L) par rapport à la base B.
Il en résulte que :
53
a) s’il s’agit de la variation d’un coefficient ck , k ∈ J, la solution restera optimale pour les valeurs
ck + ∆ avec ∆ ∈ [∆, ∆] où ∆ = −ĉk et ∆ = +∞.
On remarquera que ∆ ≤ 0.
b) S’il s’agit de la variation d’un coefficient cl , l ∈ I, la solution restera optimale pour les valeurs de
cl + ∆ avec ∆ ∈ [∆, ∆] où :
{ ĉ
∆ = max[ âljj : j ∈ J, âlj < 0]
ĉ
∆ = min[ âljj : j ∈ J, âlj > 0]
Dans le cas d’un problème de maximisation, il faut bien sûr imposer :
∑
ĉj = cj − ci âij ≤ 0 ∀ j ∈ J
i∈I
Lors de la variation d’un coefficient bk , la base restera optimale pour les valeurs bk +∆ avec ∆ ∈ [∆, ∆]
où : {
∆ = max[− βb̂iki : i ∈ I, βik > 0] ≤ 0
∆ = min[− βb̂iki : i ∈ I, βik < 0] ≥ 0.
cb∗ = c∗ − c∗B B −1 A ≥ 0.
Si on on partitionne d comme suit d = (dB dN ), la condition ci-dessus devient :
54
Pour que la base B reste optimale il suffit que :
ĉj + θ(dj − ⟨dB Âj ⟩) ≥ 0 ∀ j ∈ J tel que dj − ⟨dB Âj ⟩ < 0.
C’est-à-dire :
dj
θ≤− ∀ j ∈ J tel que dj − ⟨dB Âj ⟩ < 0.
dj − ⟨dB Âj ⟩
Donc la base B restera optimale si θ ∈ [0, θ] avec
dj
θ = min[ : j ∈ J, dj − ⟨dB Âj ⟩ < 0].
⟨dB Âj ⟩ − dj
b̂i
θ = min[− : i ∈ I, dˆi < 0].
dˆi
5.4 Post-optimisation
L’étude de post-optimisation consiste à réoptimiser ”si nécessaire” la solution optimale du problème
suite à une modification intervenue dans la formulation du problème. On a les quatre types suivants de
modifications.
- Modification d’un coefficient de la fonction-objectif
- Modification d’un coefficient du second membre
- Ajout d’une variable
- Ajout d’une contrainte
- Suppression d’une variable.
On considère le programme linéaire (P L) ci-dessous.
Z ∗ = min Z = cx
{
Ax = b (P L)
x ∈ Rn , x ≥ 0
où A ∈ Mm,n (R), c ∈ M1,n (R), et b ∈ Mm,1 (R).
On suppose que B est une base réalisable optimale et que I (resp. J) sont les indices des variables de
base (resp. hors base) associées à la base B.
On note
Z ∗ = min Z = ĉx + Ẑ
{
Âx = b̂
x ∈ Rn , x ≥ 0
la forme canonique de (P L) par rapport à la base B.
55
5.4.2 Modification d’un coefficient de b
Supposons qu’un coefficient bi de b devient bi + ∆.
On sait que la base reste optimale si ∆ ∈ [∆, ∆] d’après le paragraphe (5.3.2). Autrement, la solution
est encore duale réalisable et peut être réoptimisée par l’algorithme dual simplexe.
56
Chapitre 6
6.1 Définitions
Définition 6.1.1 Un programme linéaire dans Rn est un problème qui consiste à optimiser c’est-à-dire,
déterminer le minimum ou le maximum d’une application linéaire Z à variable x, ainsi que les éléments
qui le réalisent sachant que x vérifie un système mixte d’équations et/ou d’inéquations linéaires dans Rn .
∑
Si la fonction Z est Z(x) = nj=1 cj xj et le système mixte d’équations et/ou d’inéquations linéaires
est :
∑n
∑j=1 aij xj ≥ bi , i = 1, · · · , m1
n
j=1 aij xj ≤ bi , i = m1 + 1, · · · , m2
∑n
j=1 aij xj = bi , i = m2 + 1, · · · , m,
on le note symboliquement :
∑
min (max) Z(x) = nj=1 cj xj
∑n
∑j=1 aij xj ≥ bi , i = 1, · · · , m1
n
aij xj ≤ bi , i = m1 + 1, · · · , m2
∑j=1
n
j=1 aij xj = bi , i = m2 + 1, · · · , m
xj ∈ R, j = 1, · · · , n.
On peut supposer que ce programme est sous la forme suivante dite forme générale :
∑
min (max) Z(x) = nj=1 cj xj
∑n
∑j=1 aij xj ≥ bi , i = 1, · · · , m1
n
∑j=1 aij xj ≤ bi , i = m1 + 1, · · · , m2
n
j=1 aij xj = bi , i = m2 + 1, · · · , m
x ≥ 0, j = 1, · · · , n1
j
xj ≤ 0, j = n1 + 1, · · · , n2
xj ∈ R, j = n2 + 1, · · · , n.
57
qu’on peut écrire matriciellement :
min(max)
{ Z = cx
Ax = b
x ∈ Rn , x ≥ 0
où A = (aij ) ∈ Mm,n (R), c = (cj ) ∈ M1,n (R), et b = (bi ) ∈ Mm,1 (R).
Ce programme linéaire peut aussi se mettre sous la forme canonique.
Pour les problèmes de minimisation :
∑
min Z = nj=1 cj xj
{ ∑n
j=1 aij xj ≥ bi , i = 1, · · · , m
xj ≥ 0, j = 1, · · · , n
Z ∗
=1 min(max)1
Z = cx
A x = b
(P L)
A2 x ≥ (≤)b2
x ∈ Rn , x ≥ 0.
Z ∗
= min(max) Z = cx
1
A x=b
1
(P L)
A2 x ≥ (≤)b2
x ≥ 0, xj entiers ∀j ∈ {1, · · · , n}
Dans toute la suite nous allons supposer sans perdre de généralités que ce problème est de la forme :
Z ∗ = min Z = cx
{
Ax = b (P LN E)
x ≥ 0, xj entiers ∀j ∈ {1, · · · , n}.
58
Le programme linéaire
Z ∗ = min Z = cx
{
Ax = b (P L)
x ≥ 0.
est dit programme linéaire relaxé continu de (P LN E).
Il peut arriver dans certains cas que toutes les variables ne soient pas toutes astreintes à être entières,
mais seulement certaines d’entre elles. Dans ce cas on parle de programme linéaire mixte. Il peut être
mis sous la forme :
Z ∗ = min Z = cx
{
Ax = b
x ≥ 0, xj entiers pour j ∈ N ⊂ {1, · · · , n}.
Un cas très important de la programmation linéaire en nombres entiers est celui où les variables ne
peuvent prendre que deux valeurs : 0 ou 1. C’est un outils très performant de formulation d’une foultitude
d’applications. En effet, on peut modéliser avec cela, le fait qu’un évènement se réalise ou non en posant :
{
1 si l’évènement se réalise
xj =
0 sinon.
6.2 Modélisation
1) Une chaı̂ne de magasins utilise une flotte de camions loués à diverses agences de location.
Elle a prévu des besoins en camions sur une période de six mois décrits au tableau ci-dessous.
Au 1er janvier, la chaı̂ne a 200 camions, dont la location se termine fin février. Elle cherche à satisfaire
ses besoins avec trois types de contrats pouvant prendre effet le premier jour de chaque mois : des contrats
de 3 mois à 1700unités monétaires (u. m.) (coût total, non mensuel), des contrats de 4 mois à 2200 u. m.
et des contrats de 5 mois à 2600u. m..
On se propose de déterminer le nombre de contrats de chaque type à démarrer chaque mois de façon
à couvrir les besoins au moindre coût et à se débarrasser de toute la flotte pour début juillet. Donner le
modèle linéaire de ce problème.
2) A la suite d’une catastrophe naturelle, on organise un pont aérien vers une ville sinistrée. Du
matériel de premières urgences doit être acheminé par avion, ainsi que des techniciens chargés de l’installer
et de le faire fonctionner. Les avions (disponibles en nombre suffisant) sont de deux types :
Type 1 : pouvant transporter 200 tonnes de matériels et 8 techniciens nécessitant un équipage de 5
hommes.
Type 2 : pouvant transporter 125 tonnes de matériels et 4 techniciens nécessitant un équipage de 6
hommes.
On dispose de 150 hommes d’équipages (aviateurs) et de 160 techniciens. De plus, le nombre total d’avions
envoyés sera limité à 25, en raison du mauvais état de la piste d ’atterrissage.
3) Un problème de production : Il y a dans un atelier 5 aléseuses (une aléseuse est un appareil pour
aplanir les bords d’une pièce métallique) qui diffèrent par la taille et l’âge. On doit aléser dans la journée
59
1500 pièces identiques. Les coûts de mise en route des différentes aléseuses, leur capacité quotidienne de
production et leur coût unitaire d’alésage se retrouvent dans le tableau suivant :
Coût de Coût unitaire de
Aléseuse mise en route (en u.m.) d’alésage (en u.m.) Capacité
A1 1000 2 600
A2 500 4 400
A3 400 5 500
A4 600 2,5 500
A5 300 5,5 400
u. m. signifie unité monétaire.
Quelles aléseuses doit-on mettre en route et combien de pièces doit-on aléser sur chacune pour mini-
miser les coûts d’usinage des 1500 pièces ?
Pour la formulation PLNE de ce problème, on utilise xi le nombre de pièces alésées sur l’aléseuse i et
yi = 1 si l’aléseuse i est mise en route et 0 sinon. Les contraintes sont alors :
x1 + x2 + x3 + x4 + x5 ≥ 1500
x1 ≤ 600y1
x2 ≤ 400y2
x3 ≤ 500y3
x4 ≤ 500y4
x ≤ 600y5
5
xi ∈ Z+ , yi ∈ {0, 1}
et la fonction-objectif est
Z = (1000y1 + 2x1 ) + (500y2 + 4x2 ) + (400y3 + 5x3 ) + (600y4 + 2.5x4 ) + (300y5 + 5.5x5 )
à minimiser.
On cherche à acheminer le tonnage maximal de matériel. Donner le modèle linéaire de ce problème.
4) Problème du sac à dos : On dispose de n objets numérotés j = 1, · · · , n. Pour j = 1, · · · , n
l’objet j a une valeur cj u.m (unité monétaire) et un poids aj .
Le problème consiste à choisir les objets pour faire un chargement d’un poids ne dépassant pas b et qui
soit de valeur maximale.
Pour modéliser ce problème, on utilise pour chaque objet j ∈ {1, · · · , n}, une variable booléenne xj
qui vaut 1 si l’objet est sélectionné et 0 sinon. On a une seule contrainte dite contrainte de sac-à-dos :
∑
n
wj x j ≤ W
j=1
Remarque 6.2.1 On peut considérer aussi le cas où il existe plusieurs objets de chaque type. Dans ce
cas on utilise pour chaque objet j, une variable entière xj corrfespondant au nombre de fois que l’objet
j est choisi. Si en plus l’objet j doit être sélectionné au moins pj fois et au plus qj fois, on ajoute à la
contrainte de sac-à-doc ci-dessus, les contraintes : pj ≤ xj ≤ qj .
60
5) Problème de recouvrement, pavage et partition : Soit E = {1, · · · , n} un ensemble fini
d’éléments. Soit E1 , · · · , Em des sous-ensembles de E. Achaque ensemble Ej on associe un poids cj ,
j = 1 · · · , m.
Une famille F ⊂ {E1 , · · · , Em } est dite :
- un recouvrement de E si, ∪Ej ∈F Ej = E,
- un pavage de E si Ej ∩ Ek = ∅ pour tout j ̸= k ∈ {1, · · · m},
- une partition de E si F est à la fois un recouvrement et un pavage.
Par exemple pour E = {1, 2, 3, 4, 5}, E1 = {1, 2}, E2 = {1, 3, 4, 5}, E3 = {3, 4} et E4 = {3, 4, 5},
on peut remarquer que {E1 , E2 } est un recouvrement, que {E1 , E3 } est un pavage et {E1 , E4 } est une
partition.
Le problème de recouvrement (resp. pavage, partition) consiste à déterminer un recouvrement (resp.
pavage, partition) dont la somme des poids des ensembles qui le forment est de poids minimum (resp.
maximum, minimum, minimum/maximum).
Ces problèmes peuvent se modéliser en utilisant des variables binaires x1 , · · · , xm associées aux sous-
ensembles E1 , · · · , Em . Pour cela, on considère A la matrice en 0 − 1 dont les lignes correspondent aux
éléments 1, · · · , n et les colonnes aux sous-ensembles E1 , · · · , Em et dont les coefficients sont aij = 1 si
i ∈ Ej et 0 sinon. Ainsi les trois problèmes peuvent s’écrire :
Recouvrement
∑ Pavage ∑ Partition ∑
min Z = m j=1 cj xj max Z = m j=1 cj xj max(min) Z = m j=1 cj xj
{ { {
Ax ≥ e Ax ≤ e Ax = e
x ∈ {0, 1}m x ∈ {0, 1}m x ∈ {0, 1}m
où e est le vecteur dont chaque composante est 1.
On peut interpréter les contraintes du problème de recouvrement (resp. pavage, partition) comme le
fait qu’un élément de E doit être pris au moins une fois (resp. au plus une fois, exactement une fois).
Ces problèmes ont de multiples applications. Par exemple, considèrons une région où l’on désire
implanter des casernes de pompiers afin de couvrir toutes les villes. Pour chaque caserne potentielle, on
détermine les communes desservies et le coût d’installation de la caserne. Comme l’on veut couvrir toutes
les communes, il s’agit clairement d’un problème de recouvrement.
6) Problème d’affectation : Il consiste à affecter à coût minimum, n ressources (personnes, lo-
calisations, équipements,...) à n activités (travaux, services,... ), par exemple : affecter des ouvriers à
des travaux, des professeurs à des classes, des équipages à des vols aériens, des symboles d’une machine
à écrire aux différentes positions d’un clavier, les différents services d’un hôpital aux différents empla-
cements disponibles, sachant qu’une ressource doit être affectée à une et une seule activité et qu’une
activité ne peut être affectée qu’à une et une seule ressource et que le coût d’affectation de la ressource i
à l’activité j est de cij unités monétaires. La modélisation de ce problème en PLNE est :
∑ ∑
min Z = ni=1 nj=1 cij xij
∑n
∑j=1 xij = 1 pour tout i = 1 · · · , n
n
i=1 xij = 1 pour tout j = 1 · · · , n
xij ∈ {0, 1} pour tout i, j
où {
1 si la ressource i est affectée à l’ativité j
xij =
0 sinon
7) Problème du voyageur de commerce : Soit n villes et cij le coût ou la distance correspondant
au trajet i → j. Le problème consiste à déterminer un circuit (ou un tour) hamiltonien c’est-à-dire un
circuit d’un seul tenant ne comportant aucun sous-tour et passant une et une seule fois par les n villes
et qui soit de coût minimum.
61
Chapitre 7
Z ∗
{ = min Z = cx
Ax = b (P LN E)
x ≥ 0, xj entiers
où A ∈ Mm,n (Z), b ∈ Mm,1 (Z), c ∈ M1,n (Z) et rang(A) = m < n.
On a la proposition suivante.
Proposition 7.1.1 - Si x∗ est optimal pour (P L) et est à coordonnées entières alors x∗ est une solution
optimale du (P LN E).
- La valeur optimale de (P L) fournit une borne inférieure de celle de (P LN E).
Remarque 7.1.1 Les coefficients d’une matrice totalement unimodulaire sont soient −1, 0 ou 1.
La condition ci-dessous est une condition suffisante pour qu’une matrice soit totalement unimodulaire.
Proposition 7.1.2 ( Condition suffisante de totale unimodularité) Soit A une matrice contenant
seulement les éléments −1, 0 ou 1 et qui satisfait les 2 conditions suivantes :
1) Chaque colonne contient au plus 2 éléments non nuls ;
2) Les lignes de A peuvent être partitionnées en deux sous-ensembles I1 et I2 tels que pour chaque
colonne contenant 2 éléments non nuls :
- si les 2 éléments non nuls ont le même signe alors l’un est dans I1 et l’autre dans I2 .
- si les deux élément non nuls sont de signes différents alors ils sont tous les deux dans I1 ou
tous les deux dans I2 .
alors A est totalement unimodulaire.
On montre que :
62
Proposition 7.1.3 Etant donné (P L), si A est totalement unimodulaire et si (P L) admet une solution
de base réalisable optimale, alors cette dernière est à coefficient entiers.
Ce résultat reste vrai si dans (P L), on remplace la contrainte Ax = b par Ax ≤ b.
{ Z = −10x1 − 11x2
min
10x1 + 12x2 ≤ 59
xi ≥ 0, xi entiers
{ Z = −10x1 − 11x2
min
10x1 + 12x2 ≤ 59
x1 , x2 ≥ 0.
{ Z = −10x1 − 11x2
min
10x1 + 12x2 + x3 = 59
x1 , x2 , x3 ≥ 0.
et I={x3 } est une base réalisable évidente. Le problème (P L) est aussi sous forme canonique par rapport
à I. On a les tableaux simplexes :
63
est appelée une coupe ou une troncature. Beaucoup de coupes sont possibles, en principe et il en existe
une infinité.
• Après avoir ajouté une coupe ou éventuellement plusieurs, le programme linéaire augmenté des
contraintes correspondantes est à nouveau résolu (en continu, par la méthode du simplexe).
• Si la solution optimale de ce nouveau programme est entière, c’est terminé : on a obtenu une solu-
tion optimale du (PLNE). Sinon le raisonnement précédent peut être répété. On recherchera une coupe,
éventuellement plusieurs que l’on rajoutera à l’ensemble des contraintes puis le programme ainsi aug-
menté sera optimisé à nouveau.
• Si les coupes sont correctement choisies à chaque étape, le polyèdre des solutions réalisables du pro-
gramme initial sera ainsi progressivement réduit jusqu’à coı̈ncider avec l’enveloppe convexe des solutions
entières au voisinage de la solution optimale. La solution optimale continue du programme augmenté
deviendra alors entière et le problème sera résolu. La convergence de la méthode dépend du choix des
coupes.
64
2. La solution optimale de (PL) n’est pas optimale pour (PLNE).
Soit x∗λ une composante non entière de cette solution. Définir et ajouter à (PLNE) et à (PL) la
contrainte de Gomory associée à la variable xλ :
∑
sλ − fλj xj = −fλ
j∈J
(sλ entier dans (PLNE) et seulement ≥ 0 dans (P L) où fλj est la partie fractionnaire de b
aλj et fλ
celle de bbλ .
Recommencer la procédure à l’étape (1) avec cette fois les programmes (PLNE) et (PL) complétés
avec la contrainte de Gomory.
3. Fin
Exemple 7.3.1
min Z = 2x1 + x2
4x1 + 3x2 ≥ 5
x1 + 2x2 ≥ 2 (P LN E)
xi ≥ 0 entiers
65
Le programme linéaire relaxé (P L) est :
min Z = 2x1 + x2
4x1 + 3x2 ≥ 5
x1 + 2x2 ≥ 2
xi ≥ 0
min Z = 2x1 + x2
4x1 + 3x2 − x3 = 5
x1 + 2x2 − x4 = 2
xi ≥ 0
I = {x3 , x4 } est une base duale réalisable ; le programme est sous forme canonique par rapport à I.
TS1 x1 x2 TS2 x1 x3 fα
x3 -4 -3 -5 x2 4/3 -1/3 5/3 2/3
x4 -1 -2 -2 x4 5/3 -2/3 4/3 1/3
2 1 0 2/3 1/3 -5/3
la coupe)
TS3 x1 x3 TS4 x1 s2
x2 4/3 -1/3 5/3 x2 3/2 −1/2 2
x4 5/3 -2/3 4/3 x4 2 −1 2
s2 −1/3 −2/3 −2/3 x3 1/2 −3/2 1
2/3 1/3 -5/3 1/2 1/2 −2
On est à l’optimum, x∗ = (0, 2)T et Z ∗ = 2. La solution optimale de (P L) est entière. Elle est donc
solution optimale de (P LN E).
Exemple 7.3.2
max Z = 4x1 + 6x2 + 2x3
4x1 − 4x2 ≤ 5
−x + 6x ≤ 5
1 2
(P LN E)
−x + x2 + x3 ≤ 5
1
xi ≥ 0 entiers
La forme standard du programme relaxé est :
66
I = {x4 , x5 , x6 } est une base réalisable évidente et le programme est sous forme canonique par rapport à
I.
TS1 x1 x2 x3 TS2 x1 x5 x3
x4 4 −4 0 5 x4 10/3 2/3 0 25/3
x5 −1 6 0 5 x2 −1/6 1/6 0 5/6
x6 −1 1 1 5 x6 −5/6 −1/6 1 25/6
4 6 2 0 5 −1 2 −5
TS3 x4 x5 x3 TS4 x4 x5 x6 fα
x1 3/10 1/5 0 5/2 x1 3/10 1/5 0 5/2 1/2
x2 1/20 1/5 0 5/4 x2 1/10 1/5 0 5/4 1/4
x6 1/4 0 1 25/4 x5 1/4 0 1 25/4 1/4
−3/2 −2 2 −35/2 −2 −2 −2 −30
La coupe associée à la variable x1 est : 103
x4 + 15 x5 ≥ 12
⇒ s1 − 10
3
x4 − 15 x5 = − 12 où s1 est la variable d’écart associé à cette coupe.
TS5 x4 x5 x6 TS6 s1 x5 x6 fα
x1 3/10 1/5 0 5/2 x1 1 0 0 2 .
x2 1/10 1/5 0 5/4 x2 1/6 1/6 0 7/6 1/6
x3 1/4 0 1 25/4 x3 5/6 −1/6 1 35/6 5/6
s1 -3/10 −1/5 0 −1/2 x4 −10/3 2/3 0 5/3 2/3
−2 −2 −2 −30 −20/3 −2/3 −2 −80/3
TS7 s1 x5 x6 TS8 s1 s3 x6
x1 1 0 0 2 x1 1 0 0 2
x2 1/6 1/6 0 7/6 x2 0 1/5 0 1
x3 5/6 −1/6 1 35/6 x3 1 −1/5 1 6
x4 −10/3 2/3 0 5/3 x4 −4 4/5 0 1
s3 −5/6 -5/6 0 −5/6 x5 1 −6/5 0 1
−20/3 −2/3 −2 −80/3 −19/3 −4/5 −2 −26
On est à l’optimum et on a : x∗ = (2; 1; 6)T et Z ∗ = 26.
La solution est entière. Donc cette solution du (P L) est aussi solution de (P LN E).
67
des solutions réalisables en un nombre fini p de sous-ensembles ou nœuds S (i) en veillant à ce que
∪p
S= S (i) . On étudie ensuite les p problèmes P (i) plus restreints :
i=1
Z ∗i = min[Z = cx : x ∈ S (i) ].
Il est conseillé de choisir une subdivision qui correspond à une partition de S : S (i) ∩ S (j) = ∅ ∀i ̸= j.
Une méthode de ”Branch and Bound” est constituée de 3 éléments principaux :
- une procédure de séparation ;
- une procédure d’évaluation ;
- une procédure de cheminement.
Le principe de la séparation consiste, pour tout nœud S (i) non terminal à le décomposer en un nombre
fini l de nœuds S (ik) , k = 1, · · · , l avec
∪
l
(i)
S = S (ik)
k=1
Définition 7.4.2 Une fonction d’évaluation est une fonction v qui à chaque nœud S (i) associe une valeur
vi vérifiant :
- La règle de minoration : vi est la borne inférieure de
Z ∗i = min[Z = cx : x ∈ S (i) ]
on a alors : vi ≤ Z ∗i ;
- la règle de coı̈ncidence : pour un nœud terminal S (t) , on a :
vt = Z ∗t = min[Z = cx : x ∈ S (t) ].
Remarque 7.4.1 Dans le cas d’un problème de maximisation, la règle de minoration est remplacée par
la règle de majoration : vi est la borne supérieure de :
Z ∗i = max[Z = cx : x ∈ S (i) ].
68
On a la propriété suivante :
Proposition 7.4.1 Si S ik , k = 1, ..., l sont les sous-ensembles, obtenus par la séparation de S (i) , alors :
vi ≤ vik , ∀k
de sorte que vi = ZR ∗ .
i
Bien évidemment, il faut définir D(i) de façon à ce qu’il soit possible et de préférence assez simple de
résoudre le problème relaxé. On peut prendre la relaxation linéaire c’est-à-dire en relaxant les contraintes
d’intégrité. Dans ce cas, D(i) est un polyèdre convexe de Rn tel que : S (i) = D(i) ∩ Zn+ .
Définition 7.4.3 Le nœud S (i) est dit sondé si l’une des trois conditions suivantes est vérifiée :
i) [Condition d’impossibilité] Le problème relaxé (RP (i) ) est impossible :
∗
ii) [Condition d’optimalité] La solution optimale de RP (i) appartient à S (i) ; on a donc vi = Z i .
iii) [Condition de dominance] Il existe une solution réalisable x x) = Zb ≤ vi .
b de (P LN E) telle que Z(b
1) la règle qui détermine le nœud suivant à examiner est fixée a priori c’est-à-dire sans tenir compte
en particulier de la valeur de la fonction d’évaluation si ce n’est pour sonder un nœud de l’arborescence.
69
solution. Traditionnellement, on situe systématiquement ce nœud suivant comme celui le plus à gauche
dans la subdivision.
- quand un nœud est sondé grâce à un des tests de sondage, on remonte dans l’arborescence jusqu’au
premier nœud que l’on rencontre dont les sous-nœuds n’ont pas encore été examinés ; parmi ceux-ci, le
nœud le plus à gauche est sélectionné.
La procédure se termine lorsqu’il n’est plus possible de sélectionner un tel nœud.
Remarque 7.4.2 i) Pour concrétiser une telle procédure en profondeur d’abord, il convient de préciser
quel noeud sélectionner lorsqu’on descend dans l’arborescence.
ii) On parle de procédure en largeur d’abord si systématiquement tous les noeuds d’un même niveau
de l’arborescence sont examinés avant de considérer le niveau suivant.
2) une règle adaptative en ce sens que la sélection du nœud suivant à examiner dépend de l’informa-
tion recueillie lors de l’analyse des nœuds précédents et tout particulièrement des valeurs de la fonction
d’évaluation.
Lorsqu’un nœud est séparé, tous ses descendants sont analysés et leur fonction d’évaluation est cal-
culée. L’analyse faite permet de sonder certains des nœuds crées, à cette étape ou aux étapes précédentes.
Tous les nœuds crées depuis le début de la procédure et qui n’ont été ni séparés ni sondés sont ap-
pelés nœuds pendants ou actifs. Soit A cette liste de nœuds actifs à une étape de la procédure. Le
nœud sélectionné est alors le nœud correspondant à la plus petite valeur de la fonction d’évaluation
soit v ∗ = vi∗ = mini∈A vi . C’est ce nœud qui est séparé et dont les descendants directs sont examinés ;
une analyse en largeur est effectuée, mais limitée aux sous-nœuds du nœud i∗ .
La procédure se termine quand tous les nœud sont sondés donc il y a plus de nœuds actifs.
b on pose x
∗i = Z(x∗i ) < Z,
• Si ZR b = x∗i et Z b = Z ∗i
R
b on garde les solutions précédentes.
∗i ≥ Z,
• Si ZR
70
2) Processus de séparation
Soit un nœud i non sondé, donc il existe au moins une variable (une composante) non entière de la
solution optimale x∗i du problème relaxé (RP (i) ). Soit x∗i b
l = bl ̸= entier ; le nœud i est séparé en deux
sous-ensembles en imposant la contrainte supplémentaire :
(a) xl ≤ E(bbl )
(b) xl ≥ E(bbl ) + 1
où E(bbl ) est le plus grand entier inférieur ou égal à bbl
base optimale associée avec I (respectivement J) l’ensemble des indices des variables de base (respecti-
vement hors base), l’équation associée à xl dans le tableau optimal est :
∑
xl + alj xj = bbl .
b
j∈J
xel −b
aij −fl
b
cj ∗i
−ZR
′
xl ≥ 0
Comme précédemment l’équation associée dans le tableau optimal est :
∑
xl + alj xj = bbl .
b
j∈J
′
xl b
aij −(1 − fl )
b
cj ∗
−ZR
i
Remarque 7.4.3 Si lors de la ré-optimisation par l’algorithme duale simplexe, il apparait que la va-
b cela signifie que le nœud S (i+1) sera sondé et
leur de la fonction-objectif est supérieure ou égale à Z,
l’application de l’algorithme dual peut être arrêtée.
71
3) Processus de cheminement
Il s’agit d’une procédure en profondeur d’abord avec un principe de Backracking. Il reste cependant
à définir quelle variable xl sélectionner parmi les variables non entières de la solution optimale x∗i du
problème RP (i) et quelle branche choisir entre (a) et (b) pour déterminer le nœud (i + 1) à examiner lors
d’une application du processus de séparation.
(a) (b)
Définition 7.4.4 On appelle pénalité pl et pl pour chacune des branches (a) et (b) relativement
∗i . C’est-à-dire :
à une variable xl non entière, les bornes inférieures de l’augmentation de la valeur ZR
(δ) ∗(i+1) ∗i avec δ=(a) ou (b) selon le cas
pl ≤ Z R − ZR
(δ)
On a pl ≥ 0 et on montre que :
Proposition 7.4.2 [ ]
(a) fl .b
cj
pl = min : j ∈ J, b
alj > 0
b
alj
[ ]
(b) −(1 − fl )b
cj
pl = min : j ∈ J, b
alj < 0
b
alj
Remarque 7.4.4 On a :
(a)
(⋆) Si {j ∈ J : b
alj > 0} = ∅ alors pl = +∞. ⇒ problème impossible
(b)
(⋆) Si {j ∈ J : b
alj < 0} = ∅ alors pl = +∞ ⇒ problème impossible.
Cette règle consiste à descendre dans l’arborescence en suivant la direction la meilleure c’est-à-dire pour
laquelle l’estimation de l’augmentation de la fonction objectif est la plus petite.
72
Remarque 7.4.5 : Dans le cas d’un problème de maximisation, les pénalités correspondent à une borne
∗i , c’est-à-dire p(δ) ≤ Z ∗(i) − Z ∗(i+1)
inférieure de la diminution de la valeur optimale ZR l R R
(δ)
On aura vi+1 ≤ vi − pl
[ ]
(a) fl b
cj
pl = min : j ∈ J; b
alj > 0
b
alj
[ ]
(b) (1 − fl ) b
cj
pl = min : j ∈ J; b
alj < 0
b
alj
Exemple 7.4.1
min
Z = 2x1 + x2
4x1 + 3x2 ≥ 5
(5) x1 + 2x2 ≥ 2
xi ≥ 0 entiers
73
Bibliographie
[1] Bazaraa, Mokhtar S. and Shetty, C. M., 1979. Nonlinear Programming Theory and Algorithms,
John Wiley and Sons.
[2] Bazaraa, Mokhtar S. and Shetty, C. M., 1976. Foundations of Optimization, Lecture Notes in
Economic and Mathematical Systems, No 122, Springer-Verlag New-York.
[3] Bergounioux Maı̈tine, 2001. Optimisation et Contrôle des systèmes linéaires, Donod.
[4] Bertsimas, Dimitris and Tsitsiklis John N. 1997. Introduction to Linear Optmization, Athena
Scientific.
[5] Culioli, Jean-Christophe, 1994. Introduction à l’optimisation, Ellipses.
[6] Christelle Guéret, Christian Prins, Marc Sevaux, 2000. Programmation linéaire, Eyrolles.
[7] F. Droesbeke, M. Hallin, CL. Lefevre, 1986. Programmation linéaire par l’exemple, Ellipses.
[8] Hiriart-Urruty, Jean-Baptiste, 1998. Optimisation et Analyse Convexe, Presse Universitaire de
France.
[9] Hiriart-Urruty, Jean-Baptiste and Lemaréchal, Claude, 1993. Convex Analysis and Minimization
algorithms, Vol I et II Grundlehren der mathematichen Wissenschaften 305 and 306, Springer-
Verlag.
[10] Hiriart-Urruty, Jean-Baptiste, 1996. L’Optimisation, in collection ”Que sais-je ?”, Presse Universi-
taire de France.
[11] Michel Minoux, 1983. Programmation mathématique : Théorie et Algorithmes, Vol I, Dunod.
[12] Rockafellar, R. Tyrrel, 1970. Convex Analysis, Princeton University Press, Princeton N. J..
[13] Roseaux, 1985. T.3. Programmation linéaire et extensions ; problèmes classiques, Masson
[14] Michel Sakarovitch, 1984. Optimisation Combinatoire Graphes et Programmation linéaire, Hermann
[15] Jacques Teghem, 1996. Programmation linéaire, Editions Ellipses
74