Prog Linéaire 2018

Télécharger au format pdf ou txt
Télécharger au format pdf ou txt
Vous êtes sur la page 1sur 75

PROGRAMMATION LINEAIRE

Prof Adama COULIBALY


UFR de Mathématiques et Informatique,
Université FHB, 22 BP 582 Abidjan 22, Côte d’Ivoire.

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

2 Formulation d’un programme linéaire 7


2.1 Programmes linéaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2 Quelques exemples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.3 Forme standard, forme canonique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

3 Résolution des programmes linéaires 12


3.1 Résultats théoriques fondamentaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
3.2 Méthode graphique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3.3 Méthode du simplexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3.3.1 Base, solutions de base . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3.3.2 Forme canonique par rapport à une base réalisable . . . . . . . . . . . . . . . . . . 17
3.3.3 Caractérisation des solutions de base réalisables optimales . . . . . . . . . . . . . . 18
3.3.4 Algorithme primal du simplexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.3.5 Convergence de l’algorithme du simplexe . . . . . . . . . . . . . . . . . . . . . . . 22
3.3.6 Méthode des tableaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3.3.7 Initialisation de l’algorithme du simplexe . . . . . . . . . . . . . . . . . . . . . . . 26
3.3.8 Méthode du grand M . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

4 Dualité en programmation linéaire 37


4.1 Définitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
4.2 Propriétés de la dualité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
4.3 Théorèmes des écarts complémentaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
4.4 Algorithme dual Simplexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
4.5 Convergence de l’algorithme dual Simplexe . . . . . . . . . . . . . . . . . . . . . . . . . . 47

5 Programmation linéaire paramétrique 48


5.1 Paramétrisation de la fonction-objectif . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
5.2 Paramétrisation du second membre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
5.3 Analyse de sensibilité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
5.3.1 Sensibilité d’un coefficient de la fonction-objectif . . . . . . . . . . . . . . . . . . . 53
5.3.2 Sensibilité d’un coefficient du second membre b . . . . . . . . . . . . . . . . . . . . 54
5.3.3 Changement continu de c . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
5.3.4 Changement continu de b . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
5.4 Post-optimisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

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

6 Formulation des programmes linéaires en nombres entiers 57


6.1 Définitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
6.2 Modélisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

7 Résolution des programmes linéaires en nombres entiers 62


7.1 Faux problèmes en nombres entiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
7.2 Problème des solutions arrondies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
7.3 Méthode des coupes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
7.3.1 Principes des méthodes de coupes . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
7.3.2 Les coupes de Gomory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
7.3.3 Principe de l’algorithme de Gomory . . . . . . . . . . . . . . . . . . . . . . . . . . 64
7.3.4 Algorithme des coupes de Gomory . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
7.4 Méthode de ”Branch and Bound” . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
7.4.1 Procédure de séparation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
7.4.2 Procédure d’évaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
7.4.3 Procédure de cheminement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
7.4.4 Un algorithme de type Branch and Bound pour la PLNE . . . . . . . . . . . . . . 70

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 .

1.1 Sous espaces vectoriels et applications linéaires


Définition 1.1.1 On appelle combinaison linéaire de xi : i = 1, · · · , k des points de Rn , toute combinai-

son linéaire x = ki=1 λi xi , avec λi ∈ R ∀ i = 1, · · · , k.

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).

1.2 Sous espaces affines et applications affines


Définition 1.2.1 On appelle combinaison linéaire affine de xi : i = 1, · · · , k des points de Rn , toute
∑ ∑
combinaison linéaire x = ki=1 λi xi , avec λi ∈ R ∀ i = 1, · · · , k et ki=1 λi = 1.

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 }.

(Tout translaté de V par un élément de M est un élément de M .

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 .

Exemple 1.2.1 a) Soit a ∈ Rn et d un élément non nul de Rn . D = a + Rd est la droite affine de Rn


passant par a et de vecteur directeur d.

b) Soit f un endomorphisme de Rn et (a, b) ∈ Rn2 tel que f (a) = b. M = {x ∈ Rn : f (x) = b} est le


sous espace affine de Rn passant a et de direction V = ker f .

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.4 Un hyperplan est un sous espace affine de codimension 1.

H est un hyperplan ⇐⇒ H = a + V et codimV = 1.

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⟩ = α}.

Dans Rn tout hyperplan H = {x ∈ Rn : ⟨a, x⟩ = α} divise l’espace en deux demi-espaces fermés de


frontière H. Ce sont :
H − = {x ∈ Rn : ⟨a, x⟩ ≤ α}
et
H + = {x ∈ Rn : ⟨a, x⟩ ≥ α}.
Les ensembles {x ∈ Rn : ⟨a, x⟩ < α} et {x ∈ Rn : ⟨a, x⟩ > α} sont des demi-espaces ouverts de
frontière H.

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.

On a aussi la caractérisation suivante :

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

∀x, y ∈ Rn , f ((1 − λ)x + λy) = (1 − λ)f (x) + λf (y)∀λ ∈ R.

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

Notons A ∈ Mm,n (R) la matrice du système et b ∈ Rm le second membre.


On sait que :
Etant donné une matrice, le nombre maximal de ses vecteurs lignes linéairement indépendants est
égal au nombre maximal de ses vecteurs colonnes linéairement indépendants. Ce nombre est le rang de
la matrice.

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 :

Proposition 1.3.1 Etant donné le système (1.1), 1) Si


- rang(A) < rang(A, b), le système est impossible et ne possède aucune solution.
- rang(A = rang(A, b) = n, le système possède une solution unique.
- rang(A) = rang(A, b) < n, le système possède une infinité de solutions.
2) Si rang(A) = m (ce qui implique m ≤ n), le système possède :
- une solution unique si m = n et cette solution est x = A−1 b.
- une infinité de solutions si m < n.
3) Si B est une matrice régulière de dimension m, les systèmes Ax = b et BAx = Bb sont équivalents
en ce sens qu’ils possèdent le même ensemble de solutions : c’est-à-dire :

{x ∈ Rn : Ax = b} = {x ∈ Rn : BAx = Bb}.

1.4 Ensembles convexes


Définition 1.4.1 Soient xi : i = 1, · · · , k des points de Rn . On appelle combinaison linéaire convexe de
∑ ∑
ces points, tout élément x = ki=1 λi xi avec λi ≥ 0 pour tout i et ni=1 λi = 1.

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]} .

C’est l’ensemble de toutes les combinaisons linéaires convexes des points x et y.

De façon analogue, on définit :

Définition 1.4.3 On appelle segment ”ouvert” d’extrémités x et y, et on le note ]x, y[, l’ensemble

]x, y[ = {z ∈ Rn : z = (1 − λ) x + λy : λ ∈ ]0, 1[} .

5
On définit aussi ]x, y] et [x, y[ qui sont appelés segments semi ouvert en x respectivement en y.

]x, y] = {z ∈ Rn : z = (1 − λ) x + λy, λ ∈ ]0, 1]} .

[x, y[ = {z ∈ Rn : z = (1 − λ) x + λy, λ ∈ [0, 1[} .

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.

1.5 Polyèdres convexes


Définition 1.5.1 Un polyèdre convexe P de Rn est l’intersection
(éventuellement vide) d’un nombre fini de demi-espaces fermés et/ou d’hyperplans.
C’est-à-dire :  

 ai x ≤ bi , i = 1, · · · , p1 , 

P = x ∈ R : ai x ≥ bi , i = p1 + 1, · · · , p2 ,
n

 

ai x = bi , i = p2 + 1, · · · , m
où les ai sont dans M1,n (R) et les bi , dans R, i = 1, · · · , m.

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.

On montre que si le polyèdre est de la forme

P = {x ∈ Rn : ai x ≤ (≥)bi , i = 1, · · · , m} ,

un point x ∈ P est un sommet si et seulement si il est intersection de n hyperplans frontières linéairement


indépendants.

6
Chapitre 2

Formulation d’un programme linéaire

2.1 Programmes linéaires


Définition 2.1.1 Un programme linéaire dans Rn est un problème qui consiste à déterminer l’optimum
(le minimum ou le maximum) d’une application linéaire de variables x ∈ Rn étant donné que celles-ci
doivent vérifier un certain nombre d’équations et/ou d’inéquations linéaires appelées contraintes.

Si Z est l’application linéaire avec Z(x) = nj=1 cj xj et l’ensemble des contraintes est :
 ∑n

 j=1 aij xj ≥ bi , i = 1, · · · , m1

 ∑n a x ≤ b ,
ij j i i = m1 + 1, · · · , m2
∑j=1


n
j=1 aij xj = bi , i = m2 + 1, · · · , m


xj ∈ R j = 1, · · · ,n
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 (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.

On a les remarques suivantes :

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.

2.2 Quelques exemples


Exemple 1 : Problème de production
Soient m machines Mi (i = 1, · · · , m) qui fabriquent en série n types de produits Pj (j = 1, · · · , n).
La machine Mi a une capacité maximum de bi unités de temps. La fabrication d’une unité du produit
Pj nécessite l’utilisation de la machine Mi durant aij unités de temps. Si cj représente le gain relatif à la
production d’une unité du produit Pj , quelle doit être la politique de production pour maximiser le gain
total ?

Exemple 2 : Problème de transport


Soient r centres de production d’un bien donné possédant des stocks disponibles en quantités respec-
tives q1 , · · · , qr . Dans s centres de consommation, la demande de ce bien est respectivement de d1 , · · · , ds .
Les frais de transport d’une unité de bien du centre de production i au centre de consommation j est cij
unités monétaires. Il s’agit de déterminer comment approvisionner les centres de consommation à partir
des centres de production de manière à minimiser le coût total de transport. Formuler ce problème sous
forme d’un programme linéaire.

Exemple 3 : Problème de la ration alimentaire


On dispose de n aliments Aj (j = 1, · · · , n) aux prix respectifs par unité de cj (j = 1, · · · , n).
Soient m éléments nutritifs ei (i = 1, · · · , m). La quantité du ième élément nutritif contenue dans une
unité de l’aliment Aj est aij . Les besoins respectifs en les m éléments nutritifs sont bi (i = 1, · · · , m).
On se propose de déterminer la ration alimentaire qui tout en étant de meilleur marché possible
garantisse un apport suffisant en éléments nutritifs.

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 :

Coûts variables de production en unité monétaire (u. m.)

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.

2.3 Forme standard, forme canonique


Dans cette partie on considère la relation suivante.
Pour u et v dans Rn on note

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

Si on pose A = (aij ) ∈ Mm,n (R), c = (cj ) ∈ M1,n (R), et


b = (bi ) ∈ Mm,1 (R), on a la notation matricielle

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

et pour les problèmes de maximisation on a



max Z = nj=1 cj xj
{ ∑n
j=1 aij xj ≤ bi , i = 1, · · · , m
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

Résolution des programmes linéaires

3.1 Résultats théoriques fondamentaux


On définit d’abord les notions d’infimum de supremum, minimum et de maximum qui sont des
prérequis nécessaires pour ce chapitre.

Définition 3.1.1 (Minorant/Majorant) Soit X une partie de R.


m ∈ R ∪ {−∞, +∞} est un minorant de X si et seulement si

∀ x ∈ X, m ≤ x.

M ∈ R ∪ {−∞, +∞} est un majorant de X si et seulement si

∀ x ∈ X, x ≤ M.

Définition 3.1.2 (Infimum/Supremum) Soit X une partie de R.


1) Si X est non vide et admet des minorants, par définition l’infimum de X est le plus grand des
minorants de X. On le note inf(X) ou inf x∈X (x).
Si X est non vide et n’admet pas de minorants, par convention, l’infimum de X est égal à −∞.
Si X = ∅, par convention son infimum est égal à +∞ : inf(∅) = +∞
2) Si X est non vide et admet des majorants, par définition le supremum de X noté sup(X) ou
supx∈X (x) est le plus petit des majorants de X.
Si X est non vide et n’admet pas de majorants, par convention, le supremum de X est égal à +∞.
Si X = ∅, par convention sup(∅) = −∞.

Ces notions sont aussi caractérisées par :

Proposition 3.1.1 1) Si X est non vide et admet des minorants,


{
m ≤ x ∀x ∈ X
m = inf(X) ⇔
∀ε > 0, ∃xε ∈ X : m ≤ xε < m + ε.

2) Si X est non vide et admet des majorants,


{
x ≤ M ∀x ∈ X
M = sup(X) ⇔
∀ε > 0, ∃xε ∈ X : M − ε < xε ≤ M.

On a le résultat suivant qui lie un problème de supremum à celui d’infimum.

12
Proposition 3.1.2 Pour tout X ⊂ R, on a supx∈X (x) = − inf x∈X (−x)

Définition 3.1.3 (Minimum/Maximum) Soit X une partie de R.


On dit que X a un minimum si inf(X) ∈ X. Dans ce cas, on note min(X) = inf(X).
On dit que X a un maximum si sup(X) ∈ X. Dans ce cas, on note max(X) = sup(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é.

Proposition 3.1.5 Etant donné le programme linéaire (P ), on définit :


- une solution optimale est un élément x∗ de D vérifiant :

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.

Etant donné le programme linéaire (P ), on a les trois situations suivantes :


- D = ∅, dans ce cas on dit que le programme est impossible,
- D ̸= ∅, mais la fonction-objectif n’est pas minorée sur D. Le minimum vaut alors Z ∗ = −∞ (si D
est borné, ce cas est exclu) ; on dit que le programme est non borné.
-D= ̸ ∅, et la fonction-objectif est minorée sur D. Alors (P ) a une solution optimale (pas forcément
unique). En d’autres termes, on a le théorème suivant :

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.

3.3 Méthode du simplexe


On considère le programme linéaire sous la forme standard suivant.
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) avec rangA = m < n.
Notons C le polyèdre convexe fermé des solutions réalisables de (P L).

3.3.1 Base, solutions de base


Etant donné le programme linéaire (P L), on a les définitions suivantes.
Définition 3.3.1 On appelle base de (P L), toute sous matrice B, carrée d’ordre m, régulière extraite
de A.

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)

On obtient donc : xB = B −1 b − B −1 N xN ). Par suite l’ensemble des solutions réalisables du programme


linéaire est : { ( −1 ) }
B b − B −1 N xN )
C = x ∈ R+ : x =
n
, xN ∈ R n−m
.
xN

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

La matrice des vraies contraintes est :


( )
1 −1 1 0
A=
0 1 0 1

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.2 Dans l’exemple (3.3.1), les bases I1 , I2 , I3 et I5 sont réalisables.

Exemple 3.3.3

Considérons le programme linéaire suivant :

 Z = 2x1 − 9x2 + 4x3 + 10x4 − 3x5


min
 7x1 + 3x2 + 10x3 + 5x4 + 8x5 = 37
5x1 + 4x2 + 7x3 + 10x4 + 3x5 = 26

x ∈ R5 , x ≥ 0

I = {x1 , x3 } est une base réalisable. En effet, si on note B la matrice associée à I, on a :


( ) ( ) ( )
7 10 −1 −7 10 −1 1
B= , B = et B b = ≥ 0.
5 7 5 −7 3

La solution de base réalisable associée est x(B) = (1, 0, 3, 0, 0)T .

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

Considérons le programme linéaire suivant :

 Z = −3x1 − 2x2
min

 4x1 + 3x2 + x3 = 18

4x1 + x2 + x4 = 8

 4x1 − x2 + x5 = 8

x ∈ R5 , x ≥ 0

Soit I = {1, 3, 5}. La matrice associée à I est


 
4 1 0
B= 4 0 0 
4 0 1
On a det B = −4 ̸= 0 ; donc I est une base.
  
0 14 0 2
B −1 =  1 −1 0  et B −1 b =  10  ≥ 0.
0 −1 1 0
La base est alors réalisable ; mais le vecteur B −1 b a une composante nulle. Donc la base I est dégénérée.

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.

Exemple 3.3.5 Dans l’exemple (3.3.1), les bases I1 et I2 sont adjacentes.

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.

3.3.2 Forme canonique par rapport à une base réalisable


On vient de voir que si (P L) possède un optimum fini, il existe au moins une base réalisable optimale.
C’est pour cela qu’on s’intéresse dans ce qui suit aux conditions d’optimalité des solutions de base
réalisables.

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 .

En remplaçant xB par sa valeur (xB = B −1 b − B −1 N xN ), on a :

Z(x) = cB B −1 b + (cN − cB B −1 N )xN . (3.3)

Posons
 = B −1 A, ĉ = c − cB B −1 A, Ẑ = cB B −1 b (3.4)

Donc ĉB = 0 et ĉN = cN − cB B −1 N .


On remarque qu’on a Z(x(B)) = cB B −1 b = Ẑ.

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.

Définition 3.3.9 Le programme linéaire (P L) est équivalent au programme linéaire :

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 :

 Z = 14 + 5x2 + 60x4 − 27x5


min
 x1 + 19x2 + 65x4 − 26x5 = 1
x3 − 13x2 − 45x4 + 19x5 = 3

x≥0

3.3.3 Caractérisation des solutions de base réalisables optimales


On peut à présent donner les conditions d’optimalité pour une solution de base réalisable.

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 :

Z(x) = cB B −1 b + (cN − cB B −1 N )xN ≥ cB B −1 b = Z(x(B)).

Par suite x(B) est une solution optimale de (P L). 

Remarque 3.3.4 Pour un problème de maximisation la condition suffisante d’optimalité est ĉ ≤ 0.

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

Considérons le programme linéaire suivant :

 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α

est réalisable quel que soit α ≥ 0 et Z(x(α)) = − 17


3 − 3 α qui tend vers −∞ quand α tend vers +∞. Le
4

problème est alors non borné.

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

les ei étant les vecteurs de la base canonique de Rm .


On a
det(B ′ ) = det B det M = âlk det B ̸= 0.
Donc I ′ est une base.
En considérant la forme canonique du programme (P L) par rapport à la base B, on constate que le
système Ax = b est équivalent à :
{ ∑
xi + j∈J−k âij xj + âik xk = b̂i ∀ i ∈ I − l

xl + j∈J−k âlj xj + âlk xk = b̂l
La solution de base associée à I ′ = I − l + k est :

 xj = 0 ∀ j ∈ J − k + l

xk = âb̂lkl


xi = b̂i − âik âb̂lkl ∀ i ∈ I − l

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.

3.3.4 Algorithme primal du simplexe


L’algorithme du simplexe contient deux phases : la phase 1 et la phase 2.

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.

Phase 2 de l’algorithme du simplexe


Dans une itération de la phase 2 de l’algorithme du simplexe appliqué au problème (P L) on procède
comme suit.

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

ĉk = min [ĉj : j ∈ J, ĉj < 0] .

La variable correspondante xk rentre dans la base on l’appelle variable rentrante.


b) Test de sortie : Soit l tel que
[ ]
b̂l b̂i
= min : i ∈ I, âik > 0 .
âlk âik

La variable xl sort de la base on l’appelle variable sortante.


c) On considère la nouvelle base réalisable encore notée B dont les ensembles des indices de variables
de base et hors base sont respectivement

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 :

2 − a) Si ĉ ≤ 0 stop : ”la base B est optimale.”


2 − 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.”

3 − a) Test d’entrée : Soit k ∈ J tel que

ĉk = max [ĉj : j ∈ J, ĉj > 0] .

La variable correspondante xk rentre dans la base.


Les autres instructions restent valables.

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.

Ce théorème montre la convergence de l’algorithme du simplexe en l’absence de dégénérescence.


On montre que

Proposition 3.3.2 Si à une itération de l’algorithme du simplexe l’ensemble


{ [ ]}
b̂l b̂i
L= l: = min : i ∈ I, âik > 0
âlk âik

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.

3.3.6 Méthode des tableaux


C’est une mise en œuvre manuelle de l’algorithme du simplexe.
Soit à résoudre le programme linéaire (P 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

On sait que  = (Im , B −1 N ), ĉ = (0, cN − cB B −1 N ), b̂ = B −1 b.


On définit :

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.

1) Permuter les variables sortante et rentrante ;


2) Remplacer le pivot par son inverse ;
3) Diviser les autres éléments de la ligne du pivot par le pivot ;
4) Diviser les autres éléments de la colonne du pivot par le pivot ; et changer de signe ;
5) Pour les autres éléments du tableau, appliquer la règle du rectangle suivante :

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

Cette règle s’applique à tous les éléments du tableau.

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

On est à l’optimum car la condition d’arrêt de l’algorithme est vérifiée.


Une solution optimale du problème initial est x∗ = ( 53 , 32 )T et la valeur optimale est Z ∗ = − 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 −∞.

Exemple 3.3.11 (Problème dégénéré)

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.

3.3.7 Initialisation de l’algorithme du simplexe


Dans cette phase d’initialisation, qu’on appelle aussi la phase 1 du simplexe, on y détermine une
première base réalisable du programme (P L).

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.

On considère le problème auxiliaire défini de la façon suivante :


- Les vraies contraintes :
On considère chaque vraie contrainte de (P L) et on ajoute au premier membre une variable artificielle
non-négative.
- La fonction-objectif :
La fonction-objectif ξ est la somme de toutes les variables artificielles introduites.
Dans ce programme toutes les variables sont non-négatives.
On a alors le programme suivant :

ξ ∗ = min ξ = m
{
a
i=1 xi
a
Ax + Im x = b (Pa )
x ≥ 0, xa ≥ 0

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.

On résout (Pa ) et on tire les conclusions suivantes.

1er cas ξ ∗ > 0 :

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

1) min Z = 2x1 + 3x2 + x3


 x1 + x2 + x3 = 5
2x1 + x2 + 3x3 ≥ 9

xi ≥ 0, i = 1, · · · , 3
La forme standard de ce problème est
min
 Z = 2x1 + 3x2 + x3
 x1 + x2 + x3 = 5
2x1 + x2 + 3x3 − x4 = 9

xi ≥ 0, i = 1, · · · , 4
On n’a pas de base réalisable évidente. Utilisons la phase 1.
Considérons le programme auxiliaire :

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 .

3.3.8 Méthode du grand M


Pour résoudre le programme linéaire (P L) par la méthode du grand M , on considère l’hypothèse que
b ≥ 0 et on procède comme suit.

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

1) Si ZM∗ = −∞, il en est de même pour Z ∗ .

2) Si (PM ) possède une solution optimale, on a les cas suivants :


a) Si dans cette solution il reste encore des variables artificielles non nulles dans la base (elles sont
donc de base) alors le problème initial (P L) est impossible c’est-à-dire qu’il ne possède pas de solutions
réalisables.
b) Si dans cette solution toutes les variables artificielles sont nulles, la partie formée des variables
structurelles est une solution de base réalisable optimale de (P L).

Remarque 3.3.10 Pour un problème de maximisation, la fonction-objectif de (PM ) est ZM = cx −



M m a
i=1 xi .

Comme dans la phase 1, on a les remarques suivantes :

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

1) min Z = 8x1 + 7x2 + 3x3


 2x1 + x2 ≥ 1
x1 + 2x2 + x3 ≥ 1

xi ≥ 0, i = 1, · · · , 3
La forme standard de ce problème est
min
 Z = 8x1 + 7x2 + 3x3
 2x1 + x2 − x4 = 1
x1 + 2x2 + x3 − x5 = 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 :

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 :

 ZM = (5 − 2M )x1 + (1 − M )x2 + M x4 + 3x5 + M + 3


min
 2x1 + x2 − x4 + x6 = 1
x1 + 2x2 + x3 − x5 = 1

xi ≥ 0, i = 1, · · · , 5
On a les tableaux simplexes suivants :
x1 x2 x4 x5
x6 2 ∗ 1 -1 0 1 ←
TS1 x3 1 2 0 -1 1
5-2M 1-M M 3 -3-M

x6 x2 x4 x5
..
x1 . 1/2 -1/2 0 1/2
TS2 ..
x3 . 3/2 1/2 -1 1/2 ←
..
. -3/2 5/2 3 -11/2

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

On est à l’optimum pour PM et une solution optimale du problème initial est x∗ = ( 31 , 1


3, 0)T et la
valeur optimale est Z ∗ = 5.
2) 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 utiliser la méthode du grand M .
Considérons le programme auxiliaire
min
 ZM = x1 + x2 + x3 + M (x5 + x6 + x7 )

 x1 + 2x2 + 3x3 + x5 = 3


 −x 1 + 2x2 + 6x3 + x6 = 2
4x2 + 9x3 + x7 = 5



 3x 3 + x4 = 1

xi ≥ 0, i = 1, · · · , 7
I = {x5 , x6 , x7 , x4 } est une base réalisable évidente pour ce problème. Déterminons la forme
canonique par rapport à cette base. Les variables de base sont déjà exprimées en fonction des variables
hors base. Il reste à exprimer la fonction-objectif en fonction des variables hors base.

34
On a : ZM = −10M + x1 + (1 − 8M )x2 + (1 − 18M )x3
Donc la forme canonique du programme par rapport à la base I est :

 ZM = −10M + x1 + (1 − 8M )x2 + (1 − 18M )x3


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 x3
x5 1 2 3 3
x6 -1 2 6 2
TS1 x7 0 4 9 5
x4 0 0 3∗ 1 ←
1 1-8M 1-18M -10M

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

On est à l’optimum pour PM et une solution optimale du problème initial est x∗ = ( 12 , 5


4, 0, 1)T et
la valeur optimale est Z ∗ = 47 .

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 :

 ZM = (1 + M )x1 + (−1 − 2M )x2 + M x4 + 8M


min

 −2x1 + x2 + x3 = 2

−x1 + 2x2 + x3 − x4 + x6 = 8
 x1 + x2 + x5 = 5


xi ≥ 0, i = 1, · · · , 6
On a les tableaux simplexes suivants :
x1 x2 x4
x3 −2 1 0 2 ←
x6 -1 2 -1 8
TS1
x5 1 1 0 5
1+M -1-2M M -8M

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

Dualité en programmation linéaire

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

1) Soit à déterminer le dual du programme linéaire ci-dessous.

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.

2) Soit à déterminer le dual du programme linéaire ci-dessous.

 Z = 8x1 − 4x2 + 2x3


max

 3x1 + 5x2 + 2x3 ≤ 4

x1 − 2x2 + 6x3 ≥ −7

 4x1 + 3x2 + x3 = 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 :

 W = 4y1 − 7y2 + 3y3


min

 5y1 + y2 + 4y3 ≤ 8

5y1 − 2y2 + 3y3 ≥ −4

 2y + 6y2 + y3 = 2
 1
y1 ≥ 0, y2 ≤ 0, y3 ∈ R

38
Exemple 4.1.2

Considérons le programme linéaire


min Z = cx
{
Ax ≥ b
x ≥ 0.
Son dual est :

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).

4.2 Propriétés de la dualité


Considérons le programme linéaire :

Z ∗ ={min Z = cx
Ax ≥ b (P )
x≥0

(où A ∈ Mm,n (R), c ∈ M1,n (R), b ∈ Mm,1 (R)) et son dual :

W∗ =
{ max W = yb
yA ≤ c (D)
y≥0

Proposition 4.2.1 (Propriété de la dualité faible)


Si x et y sont respectivement des solutions réalisables de (P ) et (D) alors on a : cx ≥ yb

Corollaire 4.2.1 On a : Z ∗ ≥ yb pour tout y : solution réalisable de (D).


W ∗ ≤ cx pour tout ∀x solution réalisable de (P ).

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.

Corollaire 4.2.3 Si x∗ et y ∗ sont respectivement solution réalisable (P ) et (D) vérifiant cx∗ = y ∗ b,


alors, x∗ et y ∗ sont des solutions optimales de (P ) et (D) respectivement.

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. 

Proposition 4.2.2 (Propriété de la dualité forte)


Si (P ) (respectivement (D)) possède une solution optimale finie alors il en de même pour (D) (respecti-
vement (P )) et de plus Z ∗ = W ∗
En d’autres termes étant donné deux problèmes en dualité si l’un possède une solution optimale finie,
alors il en est de même pour l’autre et de plus les valeurs optimales sont égales.
Preuve : Considérons le programme (P ) sous forme standard
Z ∗ ={min Z = cx
Ax − Im s = b (Pe)
x, s ≥ 0

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 ∗

On a les corollaires suivants.

Corollaire 4.2.4 Soit x∗ et y ∗ respectivement des solutions réalisables de (P ) et (D).


{
x∗ est solution optimale de(P )
cx∗ = y ∗ b ⇐⇒
y ∗ est solution optimale de(D).

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

4.3 Théorèmes des écarts complémentaires


On considère toujours les programmes linéaires en dualité :
Z ∗ ={min Z = cx W∗ =
{ max W = yb
Ax ≥ b (P ) yA ≤ c (D)
x≥0 y≥0
On a le théorème suivant :
Théorème 4.3.1 (Théorème faible des écarts complémentaires)
Soit x∗ et y ∗ deux solutions respectivement réalisables de (P ) et (D).
Une condition nécessaire et suffisante pour que x∗ et y ∗ soient solutions optimales est qu’elles vérifient :
{
y ∗ (Ax∗ − b) = 0 (1)
(c − y ∗ A)x∗ = 0 (2)
Preuve : Posons α = y ∗ (Ax∗ − b) et β = (c − y ∗ A)x∗ ; comme x∗ et y ∗ sont des solutions réalisables de
(P ) et (D), on a α ≥ 0, β ≥ 0 et
α + β = y ∗ Ax∗ − y ∗ b + cx∗ − y ∗ Ax∗ = cx∗ − y ∗ b.
Or une condition nécessaire et suffisante d’optimalité de deux solutions réalisables x∗ et y ∗ respectivement
de (P ) et (D) est cx∗ − y ∗ b = 0. Ce qui est équivalent à α + β = 0. Comme α et β sont non négatifs,
cette condition est encore équivalente à
{ { ∗
α=0 y (Ax∗ − b) = 0
⇐⇒
β=0 (c − y ∗ A)x∗ = 0
D’où le théorème. 

Si ai et Aj désignent respectivement les matrices lignes et colonnes correspondant à la ligne i et la


colonne j de A, on a

m
y(Ax − b) = 0 ⇔ yi (ai x − bi ) = 0 ⇔ yi (ai x − bi ) = 0 ∀i = 1, ..., m,
i=1
et

n
(c − yA)x = 0 ⇔ (cj − yAj )xj = 0 ⇔ xj (cj − yAj ) = 0 ∀j = 1, ..., n.
j=1
On peut dire alors qu’une condition nécessaire et suffisante pour que deux solutions réalisables x et
y respectivement de (P ) et (D) soient solutions optimales est qu’elles vérifient :
{
yi (ai x − bi ) = 0 ∀i = 1, ..., m
(cj − yAj )xj = 0 ∀j = 1, ..., n
Il existe une autre version dite version forte du théorème des écarts complémentaires.

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

a) Considérons le programme linéaire ci-dessous.

min
 Z = x1 + x2
 3x1 + x2 ≥ 4
x1 + 4x2 ≥ 5

x 1 , x2 ≥ 0

Montrons que le point x = (1, 1)T est une solution optimale.


On vérifie facilement que ce point est une solution réalisable.
donc d’après le théorème des écarts complémentaires x est solution optimale si et seulement si il existe
une solution réalisable y du dual telle que


 (3x1 + x2 − 4)y1 = 0

(x1 + 4x2 − 5)y2 = 0

 (3y1 + y2 − 1)x1 = 0

(y1 + 4y2 − 1)x2 = 0

En remplaçant x par sa valeur dans ce système, on obtient :


{
3y1 + y2 = 1
y1 + 4y2 = 1
3 2 T
Soit alors le point y = ( 11 , 11 ) . Cette solution est bien réalisable du dual par suite x est solution
optimale.

b) Considérons le programme linéaire ci-dessous.

min
 Z = 2x1 + 3x2

 2x1 + x2 ≥ 3

2x1 − x2 ≥ 5

 x + 4x2 ≥ 6
 1
x 1 , x2 ≥ 0

i) Le point x = (3, 1)T est-il une solution optimale ?


ii) Le point x = ( 26 7 T
9 , 9 ) est-il une solution optimale ?
i) 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


 (2x 1 − x2 − 5)y2 = 0
(x1 + 4x2 − 6)y3 = 0



 (2y1 + 2y2 + y3 − 2)x1 = 0

(y1 − y2 + 4y3 − 3)x2 = 0

On remplace x par sa valeur dans ce système, on obtient :

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

On remplace x par sa valeur dans ce système, on obtient :



 y1 = 0
2y2 + y3 = 2

−y2 + 4y3 = 3

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.

4.4 Algorithme dual Simplexe


On considère le programme linéaire :

Z ∗ ={min Z = cx
Ax = b (P L)
x≥0

A ∈ Mm,n (R) ; c ∈ M1,n (R) et b ∈ Mm,1 (R)


On suppose que rg(A) = m < n.

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.

L’algorithme dual simplexe contient deux phases :

Phase 1 : Procédure d’initialisation


On détermine une première base duale réalisable. Si cette procédure échoue, cela signifie qu’une telle
base n’existe pas. C’est-à-dire que le polyèdre de la solution réalisable du dual est, vide, et donc (P.L)
est impossible soit non borné Z ∗ = −∞.

Phase 2 : Procédure itérative


1) On considère B une base, on note I (resp. J) l’ensemble des indices des variables de base (resp.
hors-base). On écrit le programme linéaire sous forme canonique par rapport à B. On dispose donc

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

La variable correspondante xl sort de la base.


b) Test d’entrée : Soit k ∈ J telle que
[ ]
ĉk ĉj
= min : j ∈ J, âlj < 0 .
âlk âlj
La variable xk rentre dans la base.
c) On pose I := I − l + k et J := J − k + l ; aller à 1).

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 .

Phase 1 : Initialisation de l’algorithme dual simplexe : Méthode de la contrainte artifi-


cielle

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

 Z = 6x1 + 3x2 − 2x3


min
 x1 + x2 + x3 ≥ 6
2x1 − 2x3 ≥ 9

x1 , x2 , x3 ≥ 0.
La forme standard est :
 Z = 6x1 + 3x2 − 2x3
min
 x1 + x2 + x3 − x4 = 6
2x1 − 2x3 − x5 = 9

xi ≥ 0, i = 1, · · · , 5.
L’ensemble I = {4, 5} est une base évidente. La forme canonique par rapport à I est :

 Z = 6x1 + 3x2 − 2x3


min
 −x1 − x2 − x3 + x4 = −6
−2x1 + 2x3 + x5 = −9

xi ≥ 0, i = 1, · · · , 5
On n’ a pas ĉ ≥ 0 donc I n’est pas une base duale réalisable.
On va utiliser la méthode de la contrainte artificielle.

46
Ici on a K = {x3 }. Donc le programme auxiliaire est :

 Z = 6x1 + 3x2 − 2x3


min

 −x1 − x2 − x3 + x4 = −6

−2x1 + 2x3 + x5 = −9

 x +v =M
 3
v, xi ≥ 0, i = 1, · · · , 5.

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.

4.5 Convergence de l’algorithme dual Simplexe


L’algorithme dual Simplexe converge si à chaque itération les coefficients b cj , sont strictement positifs
pour tout j ∈ J.
Par contre s’il existe j ∈ J tel que b cj = 0, il y a dégénérescence du problème dual. La fonction-
objectif peut ne pas varier lors d’une itération, et un cyclage peut se produire. Pour éliminer un éventuel
cyclage, et assurer la convergence finie de l’algorithme dual simplexe, on peut utiliser les règles de Bland
ci-dessous.

Règles de Bland
Test de sortie : La variable sortante est xl qui vérifie :
[ ]
l = min i ∈ I : bbi < 0 .

Test de rentrée : La variable rentrante est xk qui vérifie :


[ [ ]]
b
cs b
cj
k = min s ∈ J : = min :b
alj < 0
b
cls b
alj
.

47
Chapitre 5

Programmation linéaire paramétrique

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.

5.1 Paramétrisation de la fonction-objectif


Soit le problème ∑
min Z(λ) = nj=1 (c1j + λc2j )xj
{
Ax = b (P L(λ))
x ∈ Rn , x ≥ 0
où A ∈ Mm,n (R), c ∈ M1,n (R), et b ∈ Mm,1 (R) avec rangA = m < n.

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 considère la forme canonique de (P L(λ)) par rapport à B :



min Z(λ) = Ẑ + nj∈J (ĉ1j + λĉ2j )xj
{ ∑
xi + j∈J âij xj = b̂i i ∈ I
x≥0

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

Résoudre le programme linéaire paramétrique suivant.

min
 Z = (8 + 2λ)x1 + (7 + 7λ)x2 + (3 + 2λ)x3
 2x1 + x2 ≥ 1
x1 + 2x2 + x3 ≥ 1

x 1 , x 2 , x3 ≥ 0

La forme standard de ce programme est :

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 :

min Z = M + 3 + 2λ + (5 − 2M )x1 + (1 − M + 3λ)x2


 +M x4 + (3 + 2λ)x5
 2x 1 + x 2 − x4 + x6 = 1
x1 + 2x2 + x3 − x5 = 1

xi ≥ 0, i = 1, · · · , 6.
x1 x2 x4 x5
x6 2 1 -1 0 1 ←
TS1 x3 1 2 0 -1 1
5 − 2M 1 − M + 3λ M 3 + 2λ −3 − M − 2λ

Cette base n’est optimale pour aucune valeur de λ. On choisit une variable hors base ayant de
préférence le coefficient le plus négatif comme variable rentrante.
x6 x2 x4 x5
..
x1 . 1/2 -1/2 0 1/2
.
..
TS2 x3 3/2 1/2 -1 1/2 ←
..
. −3/2 + 3λ 5/2 3 + 2λ −11/2 − 2λ

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λ

Pour la base I = {x1 , x2 } l’intervalle de stabilité est [− 21 , 21 ].


La solution optimale est x∗ = ( 13 , 13 , 0)T et la valeur optimale est Z ∗ (λ) = 5 + 3λ.

x3 x4 x1
x5 -1 -2 3 1
TS4 x2 0 -1 2 1
3 − 2λ 7 + 7λ −6 − 12λ −7 − 7λ

Pour la base I = {x5 , x2 } l’intervalle de stabilité est [−1, − 21 ].


La solution optimale est x∗ = (0, 1, 0)T et la valeur optimale est Z ∗ (λ) = 7 + 7λ.
Le coefficient qui s’annule pour λ = −1 ne permet pas d’obtenir un pivot. Donc pour λ ∈] − ∞, −1[
le problème est non borné ; ce qui achève la résolution du problème.

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 :

Proposition 5.2.1 L’intervalle de stabilité associé à B est [λ, λ] avec


{ } { }
b̂1i b̂1i
λ = max − : i ∈ I, b̂i > 0 et λ = min − : i ∈ I, b̂i < 0 .
2 2
b̂2i b̂2i

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

Résoudre le programme linéaire paramétrique suivant.

max
 Z = 6x1 + 5x2

 x1 + x2 ≤ 8 − 2λ

−2x1 + 3x2 ≤ 6 − λ

 x − x2 ≤ 2 + λ
 1
x1 , x2 ≥ 0.

La forme standard de ce programme est :

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

La base duale réalisable I = {v, x4 , x2 , x1 } est optimale pour λ ∈ [− 14


5 , 2]. La solution optimale est
∗ 1 3 T ∗
x (λ) = (5 − 2 λ, 3 − 2 λ) et la valeur optimale est Z (λ) = 45 − 2 λ.21

x4 x5
x3 -2 -5 −14 − 5λ
TS5 x2 1 2 10 + λ
x1 1 3 12 + 2λ
-11 -28 −122 − 17λ

La base duale réalisable I = {v, x3 , x2 , x1 } est optimale pour λ ∈ [−6, − 14


5 ]. La solution optimale est
x∗ (λ)
= (12 + 2λ, 10 + λ)T et la valeur optimale est Z ∗ (λ) = 122 + 17λ.
Pour λ ∈] − ∞, −6[ le problème est impossible. Ce qui termine la résolution du problème.

5.3 Analyse de sensibilité


Etant donné un programme linéaire et x∗ une solution optimale, une analyse de sensibilité consiste à
déterminer, séparement pour chaque coefficient de la fonction objectif et du second membre du problème,
quel est l’intervalle des variations de ces coefficients pour lesquelles x∗ reste solution optimale.
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.

5.3.1 Sensibilité d’un coefficient de la fonction-objectif


La solution de base réalisable associée à la base B restera optimale quelle que soit la variation d’un
coeffient de c, tant que : ∑
ĉj = cj − ci âij ≥ 0 ∀ j ∈ J.
i∈I

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

pour obtenir l’intervalle ∆ ∈ [∆, ∆]. L’adaptation des formules donne :


a) ∆ = −ĉk et ∆ = +∞.
b) { ĉ
∆ = max[ âljj : j ∈ J, âlj > 0] ≤ 0

∆ = min[ âljj : j ∈ J, âlj < 0] ≥ 0.

5.3.2 Sensibilité d’un coefficient du second membre b


La solution restera réalisable et optimale quelle que soit la variation d’un coeffcient de b tant que :
b̂i ≥ 0 pour tout i ∈ I.
Notons
B −1 = (βij )
alors ∑
b̂ = B −1 b ⇔ b̂i = βij bj ∀i ∈ I
j∈J

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.

5.3.3 Changement continu de c


On suppose que le vecteur des coefficients de la fonction-objectif c est transformé en c∗ = c + θd où
d est un vecteur de changement et θ un facteur d’échelle, θ ≥ 0.
Pour que la base B reste optimale il suffit que :

cb∗ = c∗ − c∗B B −1 A ≥ 0.
Si on on partitionne d comme suit d = (dB dN ), la condition ci-dessus devient :

(cB + θdB cN + θdN ) − (cB + θdB )B −1 A = (0 ĉN + θ(dN − dB ÂN )) ≥ 0


c’est-à-dire :
ĉj + θ(dj − ⟨dB Âj ⟩) ≥ 0 ∀ j ∈ J.
Si dj − ⟨dB Âj ⟩ ≥ 0 alors comme θ ≥ 0, on aura

ĉj + θ(dj − ⟨dB Âj ⟩) ≥ ĉj ≥ 0

car la base B est otimale.

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

5.3.4 Changement continu de b


Il s’agit ici d’évaluer le domaine de variation des coefficients de b de sorte que la base B reste optimale.
On utilisera alors l’algorithme dual simplexe.
Supposons que le second membre b est transformé en b∗ = b + θd où d est un vecteur de changement
et θ un facteur d’échelle, θ ≥ 0.
La base B reste optimale si B −1 b∗ = B −1 b + θB −1 d ≥ 0.
Notons dˆ = B −1 d. Alors la base B restera optimale si θ ∈ [0, θ] avec

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.

5.4.1 Modification d’un coefficient de c


Supposons qu’un coefficient cj de c devient cj + ∆.
On sait que la base reste optimale si ∆ ∈ [∆, ∆] d’après le paragraphe (5.3.1). Autrement, la solution
est encore primale réalisable et peut être réoptimisée par l’algorithme primal simplexe.

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.

5.4.3 Ajout d’une variable


Supposons qu’une variable xn+1 (caractérisée par An+1 (sa colonne dans la matrice des contraintes)
et cn+1 (son coefficient dans la fonction-ojectif)) est ajoutée au problème.
On calcule ĉn+1 = cn+1 − cB B −1 An+1 .
Si ĉn+1 ≥ 0, la solution précédente reste optimale. Dans le cas contraire, la variable xn+1 rentre dans
la base par application de l’algorithme primal simplexe.

5.4.4 Ajout d’une contrainte


Supposons qu’une contrainte m + 1 est ajoutée au problème.
La solution est complétée par la variable d’écart xem+1 de cette contrainte (ou par une variable
artificielle xam+1 si la contarinte supplementaire est une égalité).
Si xem+1 ≥ 0 (ou xam+1 = 0), la solution reste réalisable et optimale.
Dans le cas contraire, xem+1 (ou xam+1 ) sort de la base par application de l’algorithme dual simplexe.

5.4.5 Suppression d’une variable


Supposons qu’on supprime la variable xj .
Si xj est une variable hors base, elle prend dès lors une valeur nulle. Par conséquent, aucune opération
n’est à effectuer puisque la région des solution réalisables optimales reste la même.
Si par contre xj est une variable de base, il est nécessaire de forcer pour la rendre nulle (à moins
qu’elle ne le soit déjà). Pour ce faire, il faut la sortir de la base en utilisant le critère de la méthode duale
du simplexe.
La variable est ignorée dans la suite de la résolution toujours suivant la méthode duale du simplexe.

56
Chapitre 6

Formulation des programmes linéaires


en nombres entiers

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.

Ce programme peut toujours se mettre sous la forme standard :



min (max) Z = nj=1 cj xj
{ ∑n
j=1 aij xj = bi , i = 1, · · · , m
xj ≥ 0, j = 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

et pour les problèmes de maximisation :



max Z = nj=1 cj xj
{ ∑n
j=1 aij xj ≤ bi , i = 1, · · · , m
xj ≥ 0, j = 1, · · · , n

La forme matricielle est :


min Z = cx
{ max
{ Z = cx
Ax ≥ b Ax ≤ b
x ∈ Rn , x ≥ 0 x ∈ Rn , x ≥ 0

Considérons le programme Linéaire continu : c’est-à-dire le problème sous la forme

Z ∗
 =1 min(max)1
Z = cx
 A x = b
(P L)
A2 x ≥ (≤)b2

x ∈ Rn , x ≥ 0.

où A1 , A2 ∈ Mm,n (R), c ∈ M1,n (R), et b1 , b2 ∈ Mm,1 (R).


Ce programme peut être le modèle d’un problème dans lequel les variables xj représentent physi-
quement de nombres d’objets indivisibles. Il n’est donc pas admissible d’avoir une solution optimale
fractionnaire. On devra dans ce cas imposer aux variables des contraintes supplémentaires ”xj entier
∀j ∈ {1, · · · , n}”. Dans ce cas, on parle de programme linéaire en nombres entiers. On définit :

Définition 6.1.2 Un programme linéaire en nombres entiers est un problème du type :

Z ∗
 = min(max) Z = cx
 1
 A x=b
1
(P L)
A2 x ≥ (≤)b2


x ≥ 0, xj entiers ∀j ∈ {1, · · · , n}

où A1 , A2 ∈ Mm,n (Q), c ∈ M1,n (R), et b1 , b2 ∈ Mm,1 (Q).


Dans ce problème les contraintes ”xj entiers ∀j ∈ {1, · · · , n}” sont appelées contraintes d’intégrité.

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}.

où A ∈ Mm,n (Q), c ∈ M1,n (R), et b ∈ Mm,1 (Q).

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.

Par exemple s’il convient de :


- prendre ou non une route ;
- réaliser ou non un investissement ;
- acheter ou non un équipement ;
- ouvrir ou non un entrepôt à tel emplacement.
Cette famille de problème se rencontre dans l’optimisation combinatoire.

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.

janvier février mars avril mai juin


430 410 440 390 425 450

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

et la fonction-objectif à maximiser est :



n
Z= pj xj .
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 .

Remarque 6.2.2 Ce problème correspond à deux autres applications classiques :


- le chargement d’un bateau, d’un satellite, d’un camion, ...
- la sélection d’investissements de manière à maximiser le rendement sans bien sûr dépasser la somme
disponible (budget).

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

Résolution des programmes linéaires en


nombres entiers

7.1 Faux problèmes en nombres entiers


On considère le programme linéaire en nombres entiers

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).

Définition 7.1.1 Soit A ∈ Mm;n (Z) ;


A est dite totalement unimodulaire si les déterminants de toutes ses sous-matrices carrées sont -1,0 ou
1.

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.

7.2 Problème des solutions arrondies


La première idée qui vient à l’esprit, lorsqu’on se trouve confronté à un problème en nombres entiers,
est d’utiliser la méthode d’arrondi, par exemple en remplaçant dans la solution optimale continue, chaque
composante fractionnaire par l’entier le plus proche. De telles méthodes sont inefficaces comme le montre
l’exemple ci-dessous.
Soit le programme linéaire en nombres entiers :

{ Z = −10x1 − 11x2
min
10x1 + 12x2 ≤ 59
xi ≥ 0, xi entiers

Le programme relaxé continu P L est :

{ Z = −10x1 − 11x2
min
10x1 + 12x2 ≤ 59
x1 , x2 ≥ 0.

On résout (P L) par la méthode du simplexe : La forme standard de (P L) est :

{ 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 :

TS1 x1 x2 TS2 x1 x3 TS3 x2 x3


x3 10 12 59 x2 5/6 1/12 59/12 x1 6/5 1/10 5,9
-10 -11 0 -5/6 11/12 -649/12 1 1 59

La condition d’arrêt du simplexe est vérifiée. On est à l’optimum et la solution est x∗ = ( 59 T


10 ; 0) =
T T
(5, 9; 0) . Une méthode d’arrondi conduirait à La solution (6; 0) laquelle ne satisfait pas les contraintes.
Si on arrondit l’optimum continu à l’entier inférieur, on aurait la solution (5; 0)T et donc de valeur
optimale Z ∗ = −50. Ce qui n’est pas car le point (1, 4)T est réalisable avec un coût de −54.

7.3 Méthode des coupes


Définition 7.3.1 Une coupe de (P LN E) est une inéquation qui est vérifiée par toute solution réalisable
de (P LN E) et qui n’est pas vérifiée par toutes les solutions réalisables du (P L). Elle est aussi appelée
une troncature.

7.3.1 Principes des méthodes de coupes


L’idée de base sur laquelle se fonde les méthodes de coupes est la suivante :
• On commence par résoudre le problème (P L).
Si la solution optimale obtenue est un point extrême à coordonnées entières, c’est terminé. Sinon, on
tronque le domaine des solutions réalisables (en rajoutant une contrainte supplémentaire au problème de
façon à exclure ce point extrême sans exclure aucune solution entière). Une telle contrainte, on rappelle,

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.

7.3.2 Les coupes de Gomory


Considérons le programme linéaire relaxé continu (P L) associé à (P LN E). On suppose que (P L)
admet une solution réalisable de base. Soit B une base réalisable optimale obtenue par la méthode de
simplexe. On note I (respectivement J) l’ensemble des indices des variables de base (resp. hors-base)
associées à B.
Le programme sous forme canonique par rapport à B est :

min Z = Z b+ b
cj xj
 ∑ j∈J
 xi + aij xj = bbi , ∀i ∈ I;
b
j∈J

xi ≥ 0, ∀i ∈ I; xj ≥ 0, ∀j ∈ J

Une solution optimale est x∗ avec x∗i = bbi ∀i ∈ I, et x∗i = 0 ∀j ∈ J.


On note : pour α ∈ R, E(α), le plus grand entier inférieur ou égal à α et fα , la partie fractionnaire
de α : c’est-à-dire α = E(α) + fα avec E(α) ∈ Z et 0 ≤ fα < 1.
On montre que :

Proposition 7.3.1 Si bbi est non entier pour i ∈ I, alors la condition



fij xj ≥ fi
j∈J

aij et fi celle de bbi , est une coupe du (P LN E). C’est la coupe


où fij désigne la partie fractionnaire de b
de Gomory associée à la variable xi .

7.3.3 Principe de l’algorithme de Gomory


On considère le problème (PLNE) et(PL) programme continu relaxé associé :
1. Résoudre le programme (PL) par l’algorithme du simplexe. On obtient une solution optimale x∗
avec x∗i = bbi si i ∈ I, et x∗i = 0 si j ∈ J. Deux cas sont à envisager :
(a) si toutes les composantes de x∗ sont entières, aller à l’étape (3).
(b) si l’une au moins des composantes n’est pas entière, aller à l’étape (2)

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

7.3.4 Algorithme des coupes de Gomory


min
{ Z = cx
On veut résoudre le problème (P LN E) : Ax = b
x ≥ 0 xj entiers
où A ∈ Mm,n (Z), b ∈ Mm,1 (Z), rg(A) = m < n.

1. On considère le programme relaxé (PL)


 ∗
 Z = min Z = cx
Ax = b

x≥0

2. On pose (PLC)= (PL)

3. Résoudre (PLC) (éventuellement par la méthode du simplexe)


(a) Si (PLC) n’admet pas de solutions réalisables, STOP : le problème (P LN E) n’admet pas non
plus de solutions réalisables.
(b) Si la solution optimale de (PLC) est entière, STOP : cette solution optimale est une solution
optimale de (PLNE).
(c) Si la solution optimale n’est pas entière, aller à l’étape (4).
4. Éliminer dans le tableau simplexe final, les lignes correspondant aux variables sλ dans la base
optimale, s’il en existe (les sλ sont les variables d’écarts associées aux coupes de Gomory).
5. (a) Soit x∗λ la variable ayant la plus grande partie fractionnaire de la solution optimale de (PLC).
(b) Construire la contrainte de Gomory relative à x∗λ .
(c) Compléter le problème (PLC) en ajoutant la contrainte de Gomory.
On obtient ainsi un nouveau problème complété (PLC) et aller à l’étape (3).

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

La forme standard de (P L) est :

 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

On a f (5/3) > f (4/3), on considère alors la coupe associée à x2 qui est : 31 x1 + 32 x3 ≥ 23 =⇒ s2 − 13 x1 −


3 x3 = − 3 où s2 est la variable d’écart associé à cette coupe. Ainsi on a le tableau suivant (complété avec
2 2

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 :

max Z = 4x1 + 6x2 + 2x3




 4x1 − 4x2 + x4 = 5

 −x + 6x + x = 5
1 2 5
 −x1 + x2 + x3 + x6 = 5



xi ≥ 0

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

La coupe associée a la variable x3 est : 56 s1 + 56 x5 ≥ 56


⇒ s3 − 65 s1 − 56 x5 = − 65 où s3 est la variable d’écart associée a cette coupe.

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).

7.4 Méthode de ”Branch and Bound”


On considère le programme (P LN E).
Z ∗
{ = min Z = cx
Ax = b
x ≥ 0, xj entiers j = 1, ..., n
où A ∈ Mm,n (Z), b ∈ Mm,1 (Z), rg(A) = m < n.
Une méthode de ”Branch and Bound” (B&B) est une méthode itérative qui consiste à chaque étape
à subdiviser l’ensemble
S = D ∩ Zn+ , où D = {x ∈ Rn : Ax = b, x ≥ 0}

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.

7.4.1 Procédure de séparation


Définition 7.4.1 Un nœud S (t) est dit terminal si :
- soit S (t) = ∅ ;
- soit le programme (P (t) )
Z ∗t = min[Z = cx : x ∈ S (t) ]
peut être résolu c’est-à-dire qu’il est possible d’en déterminer une solution optimale.

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

et S (ik1 ) ∩ S (ik2 ) = ∅, ∀k1 ̸= k2 .


Ce principe peut être basé sur :
- Le signe ou la valeur prise par une fonction
- la présence ou non de certains éléments
- l’ordre relatif de certains éléments
- les valeurs possibles d’une ou de plusieurs variables discrètes.

7.4.2 Procédure d’évaluation


a) Définition et Propriétés

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

b) Détermination d’une fonction d’évaluation


Pour obtenir la borne inférieure vi de Z ∗i , la technique la plus utilisée est de procéder à une relaxation
du problème P (i) . Une telle relaxation consiste à elargir l’ensemble S (i) en un ensemble D(i) tel que
S (i) ⊂ D(i) et à résoudre le problème relaxé (RP (i) ) :
∗ i
ZR = min[ Z = cx : x ∈ D(i) ]

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+ .

c) Utilisation de la fonction d’évaluation


Supposons connaitre des solutions réalisables de (P LN E). Ces solutions peuvent être :
- soit des solutions réalisables évidentes
- soit des solutions réalisables déterminées par l’application d’une heuristique
- soit des solutions réalisables générées en cours de procédure lors de la résolution de certains problèmes
relaxés.
Notons x b la meilleure d’entre elle et Z b = Z(b b
x) : on sait que Z ∗ ≤ Z.
A chaque étape, x b
b et Z sont actualisés si une meilleure solution réalisable a été obtenue.
Soit S un nœud. S’il apparait que Zb ≤ vi , on a nécessairement Z
(i) b ≤ Z ∗i . On peut donc affirmer
qu’il n’y a dans S (i) aucune autre solution meilleure que x b. Dans ce cas le nœud S (i) est dit sondé.
Plus généralement :

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

7.4.3 Procédure de cheminement


La procédure de séparation permet d’obtenir une arborescence de sous problèmes. Il est totalement
exclu d’examiner la totalité des nœuds de l’arborescence. Pour réaliser une énumération implicite et ef-
ficace, il convient de définir la façon de cheminer dans l’arborescence. On peut distinguer deux grandes
façons de procéder :

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.

Exemple : la procédure en profondeur d’abord ou procédure par séparation et évaluation séquentielle


Cette règle consiste :
- chaque fois qu’un nœud analysé n’est pas sondé, à sélectionner un seul des sous-ensembles de sa sub-
division et toujours le même. Il s’agit de celui dont à priori, on estime qu’il devrait contenir la meilleur

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.

Exemple : la procédure de la meilleure évaluation d’abord ou procédure de la séparation et évaluation


progressive.

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.

7.4.4 Un algorithme de type Branch and Bound pour la PLNE


Considérons le (P LN E)
Z ∗ = min[Z = cx : x ∈ S]
où S = D ∩ Zn+ avec D = {x ∈ Rn : Ax = b, x ≥ 0}.
Ce problème est associé au nœud initial S (0) de l’arborescence. Au nœud i de l’arborescence sera
associé un problème P (i) en nombres entiers dont l’ensemble des solutions réalisables S (i) sera défini en
ajoutant à S c’est-à-dire à D des contraintes supplémentaires : S (i) = D(i) ∩ Zn+ .
Si le nœud i est un descendant du nœud (i − 1), on aura D(i) ⊂ D(i−1) . On notera x b la meilleure
b = Z(b
des solutions réalisables du problème (P LN E) déjà trouvées et Z b = +∞.
x). Initialement on pose : Z

1) Processus d’évaluation et de sondage


Soit (P (i) ) le problème correspondant au nœud i. La valeur vi de la fonction d’évaluation sera la valeur
optimale de la relaxation linéaire (RP(i) ) du problème (P (i) ) c’est-à-dire vi = Z∗i
R = minx∈D(i) Z = cx.
(i)
Le nœud S sera sondé si soit :
- le problème (P (i) ) est impossible ⇒ D(i) = ∅
- la résolution de (RP (i) ) fournit une solution optimale entière c’est-à-dire x∗i ∈ S (i) .

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

• Pour (a) On aura D(i+1) = D(i) ∩ {x : xl ≤ E(bbl )}


Soit xel la variable d’écart de la contrainte supplémentaire ; on a donc :
{
xl + xel = E(bbl )
xel ≥ 0
Supposons que la solution optimale x∗l est obtenue à l’aide de la méthode du simplexe. Si B est une
i

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

En remplaçant xl par sa valeur, on obtient



xel − b
alj xj = −fl
j∈J

où fl est la partie fractionnaire de bbl , 0 ≤ fl ≤ 1.


I − {xl } ∪ {xel } est une base duale réalisable de (RP (i+1) ) et le tableau simplexe associé est :
xi , i ̸= l b
aij bbi

xel −b
aij −fl
b
cj ∗i
−ZR

• Pour (b) on aura D(i+1) = D(i) ∩ {x : xl ≥ E(bbl ) + 1}.



Soit xl la variable d’écart supplémentaire associée : on a donc :
{
xl − xl = E(bbl ) + 1


xl ≥ 0
Comme précédemment l’équation associée dans le tableau optimal est :

xl + alj xj = bbl .
b
j∈J

En remplaçant xl par sa valeur, on a :




xl + b
alj xj = −(1 − fl )
j∈J

où fl est la partie fractionnaire de bbl , 0 ≤ fl ≤ 1.



I − {xl } ∪ {xl } est une base réalisable de (RP (i+1) ) et le tableau simplexe associé est :
xi , i ̸= l b
aij bbi


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.

~ Règle 1 [Règle de la plus petite pénalité]


On choisit l et la branche δ telle que :
(δ) (a) (b)
pl ∗ = min (pl , pl )
l tel que
b
bl ̸=entier

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.

~ Règle 2 [Règle de la plus grande pénalité]


Si
(δ) (a) (b)
pl ∗ = max (pl , pl )
l tel que
b
bl ̸=entier

alors on sélectionne la variable x∗l et la branche δ pour définir le nœud (i + 1) avec


{
a si δ = b
δ=
b si δ = a

~ Règle 3 [Règle du Max Min]


On considère :
(δ) (a) (b)
pl ∗ = max min (pl , pl )
l tel que (a,b)
b
bl ̸=entier

et on sélectionne la variable x∗l et la branche δ pour définir le nœud (i + 1).

~ Règle 4 [Règle du max de non intégrité]


On considère :
(a) (b) (δ) (a) (b)
pl = fl , pl = 1 − fl , et pl∗ = max min(pl , pl )
l tel que
b
bl ̸=entier

et on sélectionne la variable x∗l et la branche δ pour définir le nœud (i + 1).

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

max Z = 5x1 − 2x2 + 3x3


max 
 Z = 4x1 + 3x2  2x1 + 2x2 − x3 ≥ 2
 

 3x1 + 4x2 ≤ 12  3x − 4x ≤ 3
1 2
(1) 4x1 + 2x2 ≤ 9 (2)

 
 x2 + 3x3 ≤ 5
xi ≥ 0 entiers 

xi ≥ 0 entiers

min Z = 4x1 + 5x2 + 4x3 min Z = −x1 + 9x2 − 6x3


 

 x1 + 2x2 − x3 ≥ 5 
 3x1 + 3x2 − x3 ≤ 15

 −x − x + 2x ≥ 1 

1 2 3 −5x1 + x2 + 2x3 ≤ 10
(3) (4)

 2x + x ≥ 1 
 x1 − 3x2 + 6x3 ≤ 3


2 3 

xi ≥ 0 entiers xi ≥ 0 entiers

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

Vous aimerez peut-être aussi