1

Cours d’optimisation
 2

Chapitre I. Programmation linéaire

 3

Introduction à la programmation linéaire

I: Introduction

I.1 Un exemple de problème de régime alimentaire

Ali se demande comment gérer au mieux ses dépenses alimentaires tout en respectant ses
besoins quotidiens en énergie (2000 kcal), protéines (55g) et calcium (800 mg). Il sélectionne
six produits qui semblent être des sources nutritionnelles bon marché.
Maintenant, Ali se demande comment composer ses menus? Il décide donc d’imposer les
limites suivantes sur le nombre de services par jour pour chacun des aliments:
Céréales: au plus 4 services par jour,
Poulet : au plus 3 services par jour,
Oeufs : au plus 2 services par jour,
Lait entier : au plus 8 services par jour,
Tarte aux pommes : au plus 2 services par jour,
Poissons et haricots : au plus 2 services par jour.
 4

Aliment Quantité Energie (kcal) Protéines (g) Calcuim (mg) Prix

Céréales 28 g 110 4 2 3
Poulet 100g 205 32 12 24
Oeufs 2 160 13 54 13
Lait entier 25 cl 160 8 285 9
Tartes aux pommes 170g 420 4 22 20
Poissons et haricots 260g 260 14 80 19

Nous proposons de formaliser ce probléme comme celui de la recherche d’un menu composé
de :
x1 services de Céréales,
x2 services de poulet,
x3 services d’oeufs,
x4 services de lait entier,
x5 services de tarte aux pommes,
x6 services de poissons et haricots.
Afin de respecter les limites imposées, le menu doit satisfaire :

0 x1 4

0 x2 3

0 x3 2

0 x4 8

0 x5 2

0 x6 2.

Le menu doit satisfaire aussi les contraintes sur les besoins en:
Energie:
110x1 + 205x2 + 160x3 + 160x4 + 420x5 + 260x6 2000
 5

Protéines:
4x1 + 32x2 + 13x3 + 8x4 + 4x5 + 14x6 55

Calcium:
2x1 + 12x2 + 54x3 + 285x4 + 22x5 + 80x6 800.

Le coût quotidien du menu est :

3x1 + 24x2 + 13x3 + 9x4 + 20x5 + 19x6

Pour composer le menu le moins cher, Ali cherche les valeurs de x1 , x2 , ..., x6 qui satisfont les
inégalitès précédentes et qui rendent la valeur du coût très petite que possible. La formulation
mathématique de ce problème de régime est donc :
Minimiser 3x1 + 24x2 + 13x3 + 9x4 + 20x5 + 19x6
Sous les contraintes :


 0 x1 4







 0 x2 3





 0 x3 2





 0 x4 8


0 x5 2 (0.1)





 0 x6 2.





 110x1 + 205x2 + 160x3 + 160x4 + 420x5 + 260x6 2000





 4x1 + 32x2 + 13x3 + 8x4 + 4x5 + 14x6 55





 2x1 + 12x2 + 54x3 + 285x4 + 22x5 + 80x6 800

II. Les programmes linéaires

Les problèmes comme celui du régime sont appelés problèmes de programmation linéaire
ou PL. La programmation linéaire est la branche des mathématiques appliquées qui traite ces
problèmes.
 6

Exemple de PL :
Maximiser 5x1 + 4x2 + 3x3 Sous les contraintes :



 2x1 + 3x2 + x3 5





 4x1 + x2 + 2x3 11
(0.2)

 3x1 + 4x2 + 2x3 8





 x1 , x 2 , x 3 0
Un autre problème pourrait être:
Minimiser 3x1 + x2
Sous les contraintes : 

 x1 + 6x2 x3 + x4 3







 7x2 + 2x4 = 5

x1 + x2 + x3 = 1 (0.3)





 x3 + x4 2




 x2 , x 3 0

II.2 Fonctions, équations et inéquations linéaires

Définition1 : Soient c1 , c2 , ..., cn des nombres réels. La fonction f définie sur les variables
réelles x1 , x2 , ..., xn par :

f (x1 , x2 ..., xn ) = c1 x1 + c2 x2 + ... + cn xn

est appelée fonction linéaire.

Définition2 : Soient f une fonction linéaire et b un nombre réel, alors l’équation
f (x1 , x2 , ..., xn ) = b est appelée l’équation linéaire et les inégalités

f (x1 , x2 , ..., xn ) b

f (x1 , x2 , ..., xn ) b

sont appellées des inéquations linéaires. Les équations et inéquations linéaires sont appelées
ici des contraintes linéaires.
 7

Définition3 : Un programme linéaire est un problème qui consiste à maximiser ou minimiser

une fonction linéaire tout en respectant un ensemble fini de contraintes linéaires.
La fonction linéaire que l’on doit maximiser ou minimiser dans un problme PL est dite
fonction objectif du problème.
Exemple :
La fonction f des variables x1 , x2 , x3 , x4 , x5 , x6 définie par:

f (x1 , ..., x6 ) = 3x1 + 24x2 + 13x3 + 9x4 + 20x5 + 19x6

est la fonction objective du problème de régime d’Ali.

Les nombres x1 , x2 , ..., xn qui satisfont toutes les contraintes d’un problème PL donné
constituent une solution réalisable ou admissible de ce problème.
Par exemple nous avons vu que x1 = 0, x2 = 0, x3 = 0, x4 = 8, x5 = 2, x6 = 0 est une solution
réalisable de (0.1).

II.3 Solution réalisable, Solution optimale

Définition 4 :
Une solution réalisable qui maximise la fonction objective d’un problème PL (sous la forme
standard) est appelée solution optimale.
La valeur associée à une solution optimale est appelée valeur optimale du problème.
Par exemple x1 = 4, x2 = 0, x3 = 0, x4 = 9/2, x5 = 2, x6 = 0 est la solution optimale de
(0.1). Ainsi la valeur optimale correspondante est 92.5.

Remarque : Attention, tous les problèmes PL n’admettent pas une solution optimale unique ;
certains problèmes peuvent avoir de nombreuses solutions optimales alors que d’autres peuvent
n’en avoir aucune. Ce dernier cas peut se produire pour des raisons radicalement opposées :

Soit il n’existe pas de solution réalisable.

Soit, dans un certain sens, il en existe trop.

 8

Exemple : On peut illustrer le premier cas sur le problème

Maximiser 3x1 + x2
Sous les contraintes: 

 x1 + x2 2


2x1 2x2 10 (0.4)




x1 , x 2 0
Maximiser x + y
Sous les contraintes: 
 x+y 1
 x, y 0

Ce problème admet une infinité de solutions optimales.

III. Ecriture Matricielle

Soit A = (aij ) une matrice de rèels de taille m n, b = (b1 , ...., bm ) et c = (c1 , ..., cn ) deux
vecteurs de rèels de taille m et n respectivement. Résoudre le problème linéaire défini par
A, b, c consiste à trouver des réels x1 , x2 , ..., xn satisfaisant les m inéquations (une pour chaque
i entre 1 et m ) :
n
X
aij xj bi , Ax b
j=1
n
X
aij xj bi , Ax b
j=1
n
X
aij xj < bi , Ax < b
j=1
n
X
aij xj > bi , Ax > b
j=1
n
X
aij xj = bi , Ax = b
j=1

Parmi ceux-ci, il faut trouver ceux qui rendent maximal:

n
X
cj xj
j=1
 9

Exemple: 

 x1 + 3x2 + x3 2





 2x1 + 5x2 + x3 8
(0.6)

 x1 x2 + x3 5





 max(2x1 + x2 x3 )

    
1 3 1 x1 2
    
    
 2 5 1   x2   8 
    
1 1 1 x3 5

IV. Mise sous forme standard

Maximiser
n
X
cj xj
j=1

Sous conditions: 

 Ax b


Cx = d (0.7)




x 0
est appelé forme standard d’une PL. On peut se ramener toujours à cette forme quitte à
remplacer :

Minimiser f est équivalent à maximiser -f

quitte à multiplier par -1 on se ramène à

x = x+ x− avec x+ 0 et x− 0

a = b est équivalent à a b et b a
 10

V. Définitions
Définition 1:
L’ensemble fx 2 Rn /Ax b, Cx = dg : l’ensemble des solutions réalisables (admissibles),
est appelé polyèdre. Cet ensemble est convexe.
Définition 2 :

Un sommet du polyèdre P = fx 2 Rn /Ax b, Cx = dg est un point x qui ne peut pas

s’écrire comme combinaison convexe de deux points de P distincts de x.

Le maximum de la fonction objectif, s’il existe, est atteint au moins en un sommet de

P.

Exemple: max(4x + 5y) sous conditions:



 x+y 5





 2x + y 8

 x + 2y 8





 x, y 0

VI. Principales conditions suivre dans PL

Les modèles de programmation linéaire doivent respecter certaines conditions fondamen-

tales pour qu’ils soient valides. Ces conditions sont en nombre de quatre :

Compréhension du problème.

Identification des variables de décision.

Fixation des objectifs à atteindre.

Mise en équation des ses contraintes.

 11

VII. Modélisation de certains problèmes économiques

VII.1 Problème d’optimisation en économie

Les problèmes que l’on étudie dans ce paragraphe consistent à trouver les optimums d’une
fonction, qu’on appelle fonction économique, donnée f (x1 , ..., xn ) = c1 x1 + ... + xn où les ci
sont des constantes, les variables étant liées par certaines relations qui sont des équations ou
des inéquations linéaires gi (x1 , ..., xn ) 0 pour tout i = 1, ..., p.
L’optimisation de telles fonctions offre des possibilités de modélisation est un ensemble de
méthodes permettent d’aboutir à des solutions cohérentes des modèles. Le champ actuel des
applications de l’optimisation à l’économie est très vaste. Un domaine important concerne
la gestion et l’utilisation des ressources rares pour accroître la productivité. Ces applications
incluent des problèmes opérationnels tels que la distribution de biens, l’ordonnancement de
la production, la sélection de portefeuilles, la conception et l’analyse de réseaux de transport.

Les étapes à suivre dans le processus de modélisation

La structure d’un modèle de programmation linéaire comporte trois élèments importants:

Les variables de décision.

Les contraintes linéaires.

La fonction économique où fonction objectif.

Les étapes à suivre dans le processus de modélisation sont:

Identification d’une situation problématique de gestion.

Formalisation de la situation problématique.

Identification des objectifs.

Construction du modéle.
 12

VII.2 Exemples de problèmes se ramenant à une programmation

linéaire

VII.2.1 Problème de transport

Une usine stocke un produit dans trois sites S1 , S2 et S3 . Les quantités stockées dans
chaque site sont respectivement 40, 50 et 30 tonnes. Les dépôts doivent alimenter quatre
magasins B1 , B2 , B3 et B4 . Les quantités nécessaires minimum au point de vente B1 sont de
10 tonnes, 12 tonnes au point B2 , 14 tonnes au point B3 et 9 tonnes au point B4 .
Question: Comment l’entreprise doit-elle répartir les stocks du produit entre les points de
vente ?
Modélisation du problème
Notons xij la quantité du produit que le dépôt Si livre au magasin Bj . Ces inconnues:

x11 , x12 , x13 , x14 , x21 , x22 , x23 , x24 , x31 , x32 x33 , x34

sont donc positives ou nulles.

Comme les dépôts S1 , S2 et S3 ne peuvent livrer respectivement que 40 tonnes, 50 tonnes et
30 tonnes au maximum, alors on a:


 x + x12 + x13 + x14 40

 11
x21 + x22 + x23 + x24 50




x31 + x32 + x33 + x34 30

Comme la quantité minimum à livrer aux magasins B1 , B2 , B3 et B4 respectivement étant

de 10 tonnes, 12 tonnes, 14 tonnes et 9 tonnes, alors on a :


 x11 + x21 + x31 10





 x12 + x22 + x32 12

 x13 + x23 + x33 14





 x14 + x24 + x34 9

Toute solution à ce système d’inéquation est une solution, c’est-à-dire est une répartition
réalisable des produits stockés entre les points de vente. Parmi toutes ces solutions, nous
allons chercher les plus économiques. Supposons que cij soit le coût du transport du dépôt
 13

Si au magasin Bj . Pour une solution donnée du système d’inéquation, le coût correspondant

est:
i=3,j=4
X
c11 x11 + c12 x12 + ... + c34 x34 = cij xij
i=1,j=1

Nous devons donc chercher à minimiser cette fonction. Nous avons donc le modèle mathématique
suivant: 

 xij 0







 x11 + x21 + x31 10





 x12 + x22 + x32 12





 x13 + x23 + x33 14


x14 + x24 + x34 9





 x11 + x12 + x13 + x14 40





 x21 + x22 + x23 + x24 50





 x31 + x32 + x33 + x34 30





 min(c11 x11 + c12 x12 + ... + c34 x34 )
Nous verrons, dans les paragraphes suivants, comment résoudre un tel problème.

Exercice: Un chocolatier-confisseur confectionne des assortiments de chocolats. Dans

ceux-ci, il a convenu d’y placer 3 sortes de chocolats, dénotés chocolats 1,2 et 3, dont chaque
kg lui coûte respectivement 4 DH, 1,45 DH et 2,40 DH. Chaque assortiment doit peser un kg
et se vendra 8 DH. Le chocolat 1 doit représenter entre 0.1 et 0.2 du poids d’un assortiment.
Les chocolats 1 et 2 présents dans un assortiment ne doivent pas peser plus de 800g. Au moins
la moitié du poids d’un assortiment doit provenir des chocolats 1 et 3. Quelle proportion de
chaque sorte de chocolats, le chocolatier-confisseur doit-il utiliser pour maximiser les revenus
nets qu’il tirera de la vente de ses assortiments ?
Un problème de production
Soit une entreprise produisant deux biens A et B à l’aide de quatre procédés de fabrication
(ou activités). Les activités 1 et 2 sont réservées à la production du bien A et les activités
3 et 4 la production du bien B. Les données de production sont regroupées dans le tableau
suivant:
 14

Facteur de Bornes de Bien A Bien A Bien B Bien B

production ressources Activité1 Activité2 Activité3 Activité4
Equipement (heure-machine) 70 3 2 4 3
Main d’ouvre (heure) 120 7 8 10 12
Matière première (Kg) 15 1 1 1 1
Coût de production unitaire 2 5/2 4 3

On suppose en outre que l’entreprise écoule toute sa production de A et B aux prix de

vente unitaire respectifs 8 et 11.
Le problème initial de l’entreprise est repartie sa production entre les activités 1, 2, 3 et 4
de façon à maximiser sa marge brute totale à l’aide des ressources en facteurs de production
dont elle dispose.
Soient x1 , x2 , x3 , x4 0 des niveaux d’activités donnés respectifs aux activités 1, 2, 3 et 4.
Les contraintes de limitations des ressources s’écrivent pour les trois facteurs de production:
Pour l’équipement:
3x1 + 2x2 + 4x3 + 3x4 70

Pour la main d’ouvre:

7x1 + 8x2 + 10x3 + 12x4 120

Pour la matière première :

x1 + x2 + x3 + x4 15

Ces inégalités peuvent être transformées en égalités par l’adjonction de variables dites d’écart
mesurant les excédents des facteurs. Soient x5 , x6 , x7 les variables d’écart pour les contraintes
respectives à l’équipement, la main d’ouvre et la matière première.
L’excédent en ressource d’équipement est:

x5 = 70 (3x1 + 2x2 + 4x3 + 3x4 )

L’excédent en ressource de la main d’ouvre:

x6 = 120 (7x1 + 8x2 + 10x3 + 12x4 )

 15

L’excédent en ressource de la main d’ouvre:

x6 = 120 (7x1 + 8x2 + 10x3 + 12x4 )

L’excédent en ressource de la matière première:

x7 = 15 (x1 + x2 + x3 + x4 )

La contrainte correspondante de limitation de ressource peut aussi bien s’exprimer par un

excédent non négatif.
La variable x5 peut être considéré comme le niveau d’une activité 5 fictives qui consomme de
l’équipement et ne produit rien.
La variable x6 peut être considéré comme le niveau d’une activité 6 fictives qui consomme de
la main d’ouvre et ne produit rien.
La variable x7 peut être considéré comme le niveau d’une activité 7 fictives qui consomme de
la matière première et ne produit rien.
Les contraintes de limitations des ressources par le système de trois équations linéaires à 7
inconnues (équations d’équilibre) :


 xi 0







 3x1 + 2x2 + 4x3 + 3x4 + x5 + 0x6 + 0x7 = 70

7x1 + 8x2 + 10x3 + 12x4 + 0x5 + 0x6 + 0x7 = 120





 x1 + x2 + x3 + x4 + 0x5 + 0x6 + x7 = 15






Un calcul élémentaire des marges brutes unitaires permet d’exprimer la marge brute totale
en fonction des niveaux d’activités :

11
6x1 + x2 + 7x3 + 8x4
2

On cherche donc à maximiser cette fonction.

 16

VIII. Problème général de programmation linéaire

VIII.1 Problème général

Définition : Tout problème de programmation linéaire peut se mettre sous la forme suivante:
Trouver les nombres x1 , ..., xn soumis aux conditions suivantes:



 xi 0





 ≤

 a x + a12 x2 + ... + a1n xn b1
 11 1
..
.





 am1 x1 + am2 x2 + ... + amn xn ≤
bm






et qui optimisent (maximisent ou minimisent) la fonction linéaire :

c1 x1 + ... + cn xn .

VIII.2 Problème canonique

Nous allons intéresser à un type particulier de programmation linéaire, appellé program-

mation canonique, et décrire une méthode algorithmique de résolutions.
Définition: On appelle programme linéaire canonique un programme du type:


 xi 0







 a11 x1 + a12 x2 + ... + a1n xn b1



 ..

 .





 am1 x1 + am2 x2 + ... + amn xn bm




 u11 x1 + u12 x2 + ... + u1n xn = d1
 ..

 .





 um1 x1 + um2 x2 + ... + umn xn = dm





 bi , d i 0







 max(c1 x1 + ... + cn xn )




 17

VIII.3 Tableau initial d’un programme canonique

La résolution des programmes linéaires a plus de deux variables ne pourra se faire par
des méthodes géométriques. Comme la résolution des systèmes d’inéquations linéaires pose
de nombreux problèmes, nous allons nous ramener en introduisant des variables d’écart à un
système d’équations linéaires.
Afin de schématiser à l’extrême les procédures algébriques de résolution, nous allons convertir
notre programme en un tableau et mettre en évidence les propriétés de ce tableau ici d’un
programme canonique.
Dans le paragraphe suivant, nous verrons, comment à partir d’un programme linéaire quel-
conque, nous ramenons à un tableau analogue à un tableau d’un programme canonique.
Considérons un programme canonique :


 xi 0





 a11 x1 + a12 x2 + ... + a1n xn b1



 ..



 .

am1 x1 + am2 x2 + ... + amn xn bm





 bi 0





 max(c1 x1 + ... + cn xn )






Introduisons les variables d’écart. Nous obtenons le système suivant:



 xi 0





 a11 x1 + a12 x2 + ... + a1n xn + e1 = b1



 ..



 .

am1 x1 + am2 x2 + ... + amn xn + em = bm





 bi , e i 0





 max(c1 x1 + ... + cn xn )






Le tableau associé à ce programme est:

 18

x1 x2 xn e1 e2 em
a11 a12 a1n 1 0 0 b1
a21 a22 a2n 0 1 0 b2
.. .. .. .. .. .. ..
. . . . . . .
am1 am2 amn 0 0 1 bm
c1 c2 cn 0 0 0 0

Remarque: Nous remarquons que les m dernières colonnes et m premières lignes de ce

tableau constituent une matrice carrée d’ordre m, appelée matrice de l’identité et les coeffi-
cients correspondant dans la fonction économique sont nuls.
Définition: On dit qu’un tableau est initialisé si les coefficients, dans les m dernières colonnes
de ce tableau, correspondant dans la fonction économique sont nuls.
Dans cet exemple, le tableau est initialisé. D’un tel tableau initialisé se dégage une solution
évidente. En l’occurrence:

x1 = 0, , xn = 0, e1 = b1 , , e m = bm

et
c1 x1 + + cn xn = 0.

Cette solution n’est pas évidement la solution maximale. Le fait remarquable que nous venons
de décrire est tout tableau initialisé donne directement une solution au programme considéré.
Exemple
Trois machines M1 , M2 etM3 peuvent produire chacune deux types de pièces P1 et P2 . Le
temps de fabrication d’une pièce de type Pi sur la machine Mj est donné dans le tableau
suivant en heures:

M1 M2 M3
P1 3 4 4
P2 4 6 5
 19

On veut fabriquer au moindre coût 6 pièces de type P1 , 8 pièces de type P2 . La machine

M1 est disponible 14 heures, les machines M2 et M3 sont disponibles chacunes 24 heures. Le
coût horaires respectivement de M1 , M2 et M3 sont 7, 5 et 6.

1) Ecrire le programme linéaire modélisant ce problème.

2) Ce problème est-t-il canonique? sinon érire un programme canonique équivalent.

3) Ecrire le tableau correspondant.

4) Ce tableau est-t-il initialisé? Justifier votre réponse. Sinon initialisé ce tableau.

Solution
1) Le programme est le suivant :


 xij 0





 x11 + x12 + x13 = 6







 x21 + x22 + x23 = 8

3x11 + 4x21 14





 4x12 + 5x22 24





 4x13 + 6x23 24




 min(z = 21x + 28x + 20x + 30x + 24x + 30x )
11 21 12 22 13 23

2) Ce programme n’est pas canonique, sa forme canonique est:



 xij 0





 x11 + x12 + x13 = 6







 x21 + x22 + x23 = 8

3x11 + 4x21 14





 4x21 + 5x23 24





 4x31 + 6x32 24




 max(z = 21x 28x 20x 30x 24x 30x23 )
11 21 12 22 13
 20

3) Introduisant les variables d’écart dans les inéquations. Le système s’écrit:



 xij 0





 x11 + x12 + x13 = 6







 x21 + x22 + x23 = 8

3x11 + 4x21 + e1 = 14





 4x21 + 5x23 + e2 = 24





 4x31 + 6x32 + e3 = 24




 max(z = 21x 28x21 20x12 30x22 24x13 30x23 )
11

Le tableau correspondant est:

x11 x12 x13 x21 x22 x23 x31 x32 e1 e2 e3

1 1 1 0 0 0 0 0 0 0 0 6
0 0 0 1 1 1 0 0 0 0 0 8
3 0 0 4 0 0 0 0 1 0 0 14
0 4 0 0 0 5 0 0 0 1 0 24
0 0 0 0 0 0 4 6 0 0 1 24
21 20 24 28 30 30 0 0 0 0 0 0

Ce tableau n’est pas initialisé. Pour cela on procède comme suit:

Introduisant d’autres variables x et y dans les deux premières équations.
Considérons la nouvelle fonction:

max( 21x11 28x21 20x12 30x22 24x13 30x23 Mx M y)

Le tableau associé s’écrit donc:

x11 x12 x13 x21 x22 x23 x31 x32 x y e1 e2 e3

1 1 1 0 0 0 0 0 1 0 0 0 0 6
0 0 0 1 1 1 0 0 0 1 0 0 0 8
3 0 0 4 0 0 0 0 0 0 1 0 0 14
0 4 0 0 0 5 0 0 0 0 0 1 0 24
0 0 0 0 0 0 4 6 0 0 0 0 1 24
21 20 24 28 30 30 0 0 M M 0 0 0 0
 21

Qui est équivalent à:

x11 x12 x13 x21 x22 x23 x31 x32 x y e1 e2 e3

1 1 1 0 0 0 0 0 1 0 0 0 0 6
0 0 0 1 1 1 0 0 0 1 0 0 0 8
3 0 0 4 0 0 0 0 0 0 1 0 0 14
0 4 0 0 0 5 0 0 0 0 0 1 0 24
0 0 0 0 0 0 4 6 0 0 0 0 1 24
21 + M 20 + M 24 + M 28 + M 30 + M 30 + M 0 0 0 0 0 0 0 14M

Ce dernier tableau s’obtient en ajoutant à la dernière ligne M fois la première et M fois la

seconde. Ce tableau est initialisé.
Exemple:
Une entreprise dispose de deux usines de fabrications U1 et U2 et de trois dépôts D1 , D2
et D3 . Les usines, qui ont des disponibilités limitées doivent fournir au dépôt les quantités
demandées. L’acheminement des marchandises a un coût (frais de transport, de carburant,
taxes,...) et ce coût varie suivant les destinations. Le problème qui se pose est celui de
l’acheminement au moindre coût. Les disponibilités de l’usine U1 sont de 18, de U2 de 32. Les
demandes des dépôts D1 , D2 et D3 sont respectivement de 9, 21 et 20. Les coûts de transports
de l’usine U1 à chacun des dépôts D1 , D2 et D3 sont respectivement de 13, 9 et 15 et ceux de
l’usine U2 sont respectivement de 11, 10 et 18 par quantité transportée.
1) Ecrire le programme linéaire modélisant ce problème.
2) Ce problème est-t-il canonique? sinon érire un programme canonique équivalent.
3) Ecrire le tableau correspondant.
4) Ce tableau est il initialisé? Justifier votre réponse. Sinon initialisé ce tableau.
 22

IX. Cas où les contraintes sont des inéquations dans les deux sens ou des
équations
Supposons que l’on ait un programme du type:



 xi 0







 a11 x1 + a12 x2 + ... + a1n xn b1



 ..

 .





 ar1 x1 + ar2 x2 + ... + arn xn br


ar+11 x1 + ar+12 x2 + ... + ar+1n xn br+1



 ..

 .





 am1 x1 + am2 x2 + ... + amn xn bm





 max(c1 x1 + ... + cn xn )







Nous introduisons les variables d’écarts positives, en les ajoutant lorsque le seconde mem-
bre est supérieur au premier et en les retranchant dans le cas contraire. Nous obtenons le
programme suivant:


 xi , ej 0







 a11 x1 + a12 x2 + ... + a1n xn + e1 = b1



 ..

 .





 ar1 x1 + ar2 x2 + ... + arn xn + er = br


ar+11 x1 + ar+12 x2 + ... + ar+1n xn er+1 = br+1



 ..

 .





 am1 x1 + am2 x2 + ... + amn xn em = bm





 max(c1 x1 + ... + cn xn )






 23

Le tableau correspondant à un tel système est le suivant:

x1 x2 xn e1 er er+1 em
a11 a12 a1n 1 0 0 0 0 b1
.. .. .. .. .. .. .. ..
. . . . 0 . . . .
ar1 ar2 arn 0 0 1 0 0 br
..
ar+11 ar+12 ar+1n 0 0 0 1 . br+1
.. .. .. .. .. .. .. ..
. . . . . . 0 0 . 0 .
am1 am2 amn 0 0 0 0 1 bm
c1 c2 cn 0 0 0 0 0

Ce tableau n’est pas initialisé: En effet, nous n’avons qu’une partie des vecteurs constituant
la matrice identité. Les contraintes bi 0 nous empêchent de remplacer les vecteurs colonnes
du type    
0 0
   
 ..   .. 
 .   . 
   
   
 0   0 
   
   
 1  par des vecteurs de types  1 .
   
   
   
 0   0 
   
 ..   .. 
 .   . 
   
0 0
D’après le tableau précédent, il manque m-r vecteurs colonnes de la matrice identité.

IX.1 Initialisation du tableau

1) On introduit m-r variables artificielles η1 , ...ηm−r et on affectue à la fonction économique

des coefficients w négatifs. Ainsi nous sommes amenés à maximiser la fonction:

c1 x1 + c2 x2 + ... + cn xn + wη1 + ... + wηm−r .

 24

Le tableau devient:

x1 x2 xn e1 er er+1 em η1 ηm−r
a11 a12 a1n 1 0 0 0 0 0 0 b1
.. .. .. .. ... .. .. .. .. ..
. . . . 0 . . . . 0 .
ar1 ar2 arn 0 0 1 0 0 0 0 br
..
ar+11 ar+12 ar+1n 0 0 0 1 . 1 0 0 br+1
.. .. .. .. .. .. .. .. .. ..
. . . . . . 0 0 . 0 . . .
am1 am2 amn 0 0 0 0 1 0 0 1 bm
c1 c2 cn 0 0 0 0 0 w w

Tous les vecteurs colonnes de la matrice identité figure dans le tableau.

2) Afin que le tableau précédent soit initialisé, il est nécessaire de rendre nul les coefficients
de la fonction économique située sous les colonnes de la matrice identité. Ainsi pour éliminer
le premier coefficient w correspondant à la colonne associée à η1 , on remplace la dernière ligne
par la dernière mois w fois la ligne r+1; on opère de même pour les autres coefficients. Et on
obtient le tableau initialisé suivant:

x1 x2 xn e1 er er+1 em η1 ηm−r
a11 a12 a1n 1 0 0 0 0 0 0 b1
.. .. .. .. .. .. .. .. .. ..
. . . . 0 . . . . . 0 .
ar1 ar2 arn 0 0 1 0 0 0 0 br
..
ar+11 ar+12 ar+1n 0 0 0 1 . 1 0 0 br+1
.. .. .. .. .. .. .. .. .. ..
. . . . . . 0 0 . 0 . . .
am1 am2 amn 0 0 0 0 1 0 0 1 bm
Pm
c01 c02 c0n 0 0 0 0 0 0 0 j=r+1 wbj

Avec
c0i = ci w(ar+1i + + am1 ), 1 i n
 25

Un tel tableau est initialisé. Les colonnes de référence sont ici les colonnes associées
aux variables e1 , e2 , , er , η 1 , , ηm−r . Les coefficients de la fonction économique sont, au
dessus de ces colonnes, tous égaux à 0.
Exemple: Soit à résoudre le système suivant:


 x + y + 3z 15







 2x + y + 5z 20

x + 2y + z 10





 max(x + 3y + z)




 x, y, z 0
On introduit les variables d’écart:



 x + y + 3z e1 = 15







 2x + y + 5z e2 = 20

x + 2y + z + e3 = 10





 max(x + 3y + z)




 x, y, z, e1 , e2 , e3 0
Le tableau associe est:
x y z e1 e2 e3
1 1 3 1 0 0 15
2 1 5 0 1 0 20
1 2 1 0 0 1 10
1 3 1 0 0 0

On introduit les variables artificielles:

x y z e1 e2 e3 η1 η2
1 1 3 1 0 0 1 0 15
2 1 5 0 1 0 0 1 20
1 2 1 0 0 1 0 0 10
1 3 1 0 0 0 w w
 26

Initialisons le tableau:

x y z e1 e2 e3 η1 η2
1 1 3 1 0 0 1 0 15
2 1 5 0 1 0 0 1 20
1 2 1 0 0 1 0 0 10
1 3w 3 2w 1 8w w w 0 0 0 35w

La valeur de la nouvelle fonction économique est:

x + 3y + z + wη1 + η2

est initialisée par la valeur 35w pour la solution de base

x = y = z = 0, e1 = e2 = 0, e3 = 10, η1 = 15, η2 = 20.

 27

Chapitre II. Méthode de simplexe

 28

Méthode de simplexe

On sait la solution, si elle existe, se trouve au moins sur un sommet du domaine des solu-
tions réalisables, la recherche de la solution optimale s’effectue uniquement sur ces sommets.
L’algorithme du simplexe examine comme première solution un des sommets (en général
l’origine), qui constitue la solution de base de l’algorithme, puis il se déplace de sommet
en sommet, afin d’améliorer la fonction économique à chaque étape. Après un nombre fini
d’itérations, il arrive à un sommet à partir duquel tout déplacement vers un autre sommet
n’améliore plus cette valeur. On est alors au sommet optimal.
L’algorithme du simplexe consiste à parcourir le polyèdre des points réalisables de sommet
en sommet jusqu’à ce qu’on ne puisse plus améliorer la solution. Au point de départ, la fonc-
tion objectif est nulle, et il s’agit de l’augmenter. Si certains de ses coefficients sont positifs,
il apparaît clairement qu’en augmentant l’une des variables correspondant à un coefficient
positif, on augmente cette fonction objectif. On a donc un critère d’obtention de l’optimum:
tant que la dernière ligne d’un tableau du simplexe contient au moins un coefficient positif,
la solution examinée peut être améliorée.
Remarques et définitions:
1) L’ajout des variables d’ecart dans un système de contraintes AX b permet d’obtenir
facilement une solution de départ réalisable, puisque les coefficients de ces variables constituent
une matrice unité et un ensemble de m-vecteurs unités est linéairement indépendant.
2) Considérons un système de m équations linéaires AX = b comportant n variables
(m < n).

Une solution de base au système d’équations AX = b s’obtient en égalant n-m variables

à zéro et en résolvant le système pour les m variables restantes.

Les n-m variables qui sont annulées sont dites des variables hors base alors que les m
variables restantes sont appelées variables de base.

Lorsque la solution de base satisfait les contraintes de non négativité, la solution est
alors appelée solution de base réalisable.
 29

Les solutions de base réalisables sont la caractéristique algébrique des points extrêmes
de la région des solutions réalisables.

Une solution de base réalisable n’ a jamais plus de m variables positives.

3) Chaque solution de base réalisable est équivalente à un point extrême. Il peut exister plus
d’une solution réalisable correspondant au même point extrême.
4) Une solution de base réalisable est dite dégénérée lorsque une ou plusieurs variables de
base prend une valeur 0.
5) Une solution de base réalisable dont les m variables de base sont positives est dite solution
de base réalisable non dégénérée.
6) Dans un programme linéaire comportant m contraintes, deux solutions de base réalisables
sont dites adjacentes si l’ensemble respectif des variables de base de chaque solution a m-1
variables de base en commun.
Principe du processus itératif
A partir d’une solution de base réalisable, on obtient une nouvelle solution de base
réalisable adjacente, meilleure ou aussi bonne, en transformant une variable hors base en une
variable de base dite variable entrante et en même temps, rendre une variable de base actuelle
en variable hors base dite variable sortante. Cette opération algébrique permet d’obtenir une
nouvelle solution réalisable.

II. Description de l’algorithme du Simplexe

Première étape: Recherche du pivot:

Le pivot est un coefficient du tableau qui permet, grâce à la méthode du pivot, d’annuler
tous les coefficients de la colonne contenant ce pivot, excepté cet élément qui est ramené à 1
après la division de la ligne le contenant par ce nombre.
Choix de la colonne pivot
La colonne pivot est définie à partir des coefficients de la fonction économique. On cherche
à se focaliser sur la variable qui, en augmentant, augmentera le plus possible la fonction
objectif. Cette variable correspond au plus grand coefficient positif de la fonction objectif.
Considérons les coefficients c1 , ..., cn de la fonction économique. Parmi tous les coefficients
 30

positifs, on considère le plus grand. La colonne pivot est la colonne qui le contient. La variable
correspondante sera la variable entrante car elle ne va plus s’annuler.
Remarque: S’il existe plusieurs coefficients correspondant à cette valeur positive maximale,
on peut choisir celui que l’on veut.
Choix de la ligne pivot
La variable entrante va prendre la place d’une des variables de base, appelé variable
sortante. Il faut maintenant trouver quelle valeur maximum peut prendre cette variable
entrante afin de maximiser la fonction objectif. Pour cela, chaque coefficient de la dernière
colonne est divisé par le coefficient correspondant de la colonne pivot. Si la colonne pivot est:

 
a1j
 
 
 a2j 
 
 
 a3j 
 
 .. 
 . 
 
 
 
 anj 
 
cj
bi
On calcule les rapports aij
pour 1 i n lorsque aij > 0. On obtient de cette façon, pour
chaque contrainte prise séparément, la valeur maximale que peut prendre la variable entrante.
bk bi
On sélectionne le plus petit rapport positif: Oncherche l’indice k tel que 0 akj aij
, en ne
considrant les i que si aij > 0.
bk
La k-ième ligne est la ligne pivot, et akj est le pivot: la ligne pivot est la ligne k telle que akj

soit positif et minimal. La variable correspondant à cette ligne est la variable sortante.
Troisième étape: Itération
S’il existe un coefficient ci positif dans le nouveau tableau, on retourne à la première étape
(choix du pivot) puis à la deuxième (réduction du tableau). On réitère ce processus jusqu’à ce
que tous les coefficients de la fonction économique soient négatifs. Cela se produira forcément.
 31

III. Exemple d’apprentissage: Détermination de la solution

optimale

Exemple 1: Si on considère le programme linéaire suivant:



 x1 + x2 1





 x2 2





 3x1 + 4x2 12

 x1 + x3 3







 max(3x1 x2 + x3 )



 xi 0

En introduisant les variables d’écart, on obtient:



 x1 + x2 + e1 = 1





 x2 + e2 = 2





 3x1 + 4x2 + e3 = 12

 x1 + x3 + e4 = 3







 max(3x1 x2 + x3 )



 xi , ei 0
Le premier tableau se présente donc ainsi:

x1 x2 x3 e1 e2 e3 e4
e1 1 1 0 1 0 0 0 1
e2 0 1 0 0 1 0 0 2
e3 3 4 0 0 0 1 0 12
e4 1 0 1 0 0 0 1 3
Z 3 -1 1 0 0 0 0 0

Le plus grand coefficient positif de la fonction économique est c1 = 3. La colonne pivot est
donc la première colonne. La variable x1 est donc entrante.
 32

La première ligne est la ligne pivot. Les seuls coefficients positifs non nuls de cette colonne
bi b1
sont a11 = 1, a31 = 3 et a41 = 1. Calculons les rapports ai1
correspondants. On a a11
= 1,
b3 b4
a31
= 4, a41
= 3.
Le plus petit rapport est le premier, donc la ligne pivot est la première. Le pivot associé
est a11 = 1. La variable entrante est x1 et la variable sortante est e1 .
Deuxième étape : Réduction du tableau
On divise la ligne pivot par le pivot puis on annule ensuite les coefficients du tableau
situées au-dessus et au-dessous du pivot, en soustrayant la ligne pivot aux autres lignes.

x1 x2 x3 e1 e2 e3 e4
x1 1 1 0 1 0 0 0 1
e2 0 1 0 0 1 0 0 2
e3 0 1 0 -3 0 1 0 9 L3 L3 3L1
e4 0 -1 1 -1 0 0 1 2 L4 L4 3L1
Z 0 -4 1 -3 0 0 0 -3 L5 L5 3L1

La solution correspondante est définie par x1 = 1, x2 = x3 = 0, e1 = 0, e2 = 2, e3 = 9 et

e4 = 2. La fonction économique vaut 3 en ce point.
On a un coefficient positif, à savoir c3 = 1. La troisième colonne est donc la colonne pivot.
Le seul coefficient positif de cette colonne est a43 = 1, c’est donc le pivot. On réduit le tableau
et on obtient:

x1 x2 x3 e1 e2 e3 e4
x1 1 1 0 1 0 0 0 1
e2 0 1 0 0 1 0 0 2
e3 0 1 0 -3 0 1 0 9
x3 0 -1 1 -1 0 0 1 2
Z 0 -3 0 -2 0 0 -1 -5 L5 L5 L4
 33

Tous les coefficients de la fonction économique sont négatifs, on a donc la solution optimale.
Elle est définie par x1 = 1, x2 = 0, x3 = 2, e1 = 0, e2 = 2, e3 = 9 et e4 = 0. Dans ce cas,
max(3x1 + x2 + x3 ) = 5.

Exemple 2:
On considère le programme linéaire suivant:


 3x1 + 2x2 + 4x3 + 3x4 70







 7x + 8x2 + 10x3 + 12x4 120
 1
x1 + x2 + x3 + x4 15





 max(6x1 + 11 x + 7x3 + 8x4 )

 2 2


 x 0 i

La résolution de ce programme nous donne ces tableaux successifs:

x1 x2 x3 x4 e1 e2 e3
e1 3 2 4 3 1 0 0 70
e2 7 8 10 12 0 1 0 120
e3 1 1 1 1 0 0 1 15
Z 6 11/2 7 8 0 0 0 0

La solution correspondante est x1 = x2 = x3 = x4 = 0 et e1 = 70, e2 = 120, e3 = 15. La

variable entrante est x4 et la variable sortante est e2 .

x1 x2 x3 x4 e1 e2 e3
e1 5/4 0 3/2 0 1 -1/4 0 40 L1 L1 1/4L2
x4 7/12 2/3 5/6 1 0 1/12 0 10 L2 1/12L2
e3 5/12 1/3 1/6 0 0 -1/12 1 5 L3 L3 1/12L2
Z 4/3 1/6 1/3 0 0 -2/3 0 -80 L4 L4 2/3L2

La solution correspondante est x4 = 10, e1 = 40 et e3 = 5, les autres variables étant nulles.

La fonction économique vaut 80.
 34

On cherche le pivot, et on le trouve sur la première colonne et troisième ligne. La variable

entrante est donc x1 et la variable sortante est e3 :

x1 x2 x3 x4 e1 e2 e3
e1 0 -1 1 0 1 0 -3 25 L1 L1 3L3
x4 0 -53/3 3/5 1 0 1/5 -7/5 3 L2 L2 7/5L3
x1 1 4/5 2/5 0 0 -1/5 12/5 12 L3 12/5L3
Z 0 -9/10 -6/5 0 0 -2/5 -36/15 -96 L4 L4 16/5L3

Ce tableau est le dernier car tous les coefficients de la dernière ligne sont négatifs. La
solution optimale correspondante est x1 = 12, x4 = 3, e1 = 25. La fonction économique vaut
en ce point 96.

IV. Variable entrante, variable sortante

L’idée de la méhode du simplexe est, partant d’une solution de base réalisable, d’augmenter
la valeur d’une des variables hors base, la variable entrante, de façon à diminuer (si on
minimise) ou à augmenter (si on maximise) la valeur du critère. L’expression du coût réduit
en fonction des variables hors base qui apparaît dans la première ligne du dictionnaire, permet
de choisir la variable entrante.
Exemple 3:
Résoudre le système suivant en utilisant la méthode du dictionnaire:



 2x1 + 4x2 + 5x3 + 7x4 42







 x1 + x2 + 2x3 + 2x4 17

x1 + 2x2 + 3x3 + 3x4 24





 max(7x1 + 9x2 + 18x3 + 17x4 )




 xi 0
 35

Solution: On introduit les variables décart:

e1 = 42 2x1 4x2 5x3 7x4

e2 = 17 x1 x2 2x3 2x4

e3 = 24 x1 2x2 3x3 3x4 Dictionnaire I

Z = 7x1 + 9x2 + 18x3 + 17x4

Le problème s’écrit maintenant : Maximiser Z sous les conditions x1 , x2 , , e3 0.

Les variables e1 , e2 et e3 dites variables de base sont exprimées en fonction des variables
x1 , x2 , x3 , x4 dites variables hors base.

Une solution de base est une solution dans laquelle toute les variables hors base sont
nulles. Dans ce cas, x1 = x2 = x3 = x4 = 0 implique e1 = 42, e2 = 17 et e3 = 24.

Cette solution est dite réalisable car les valeurs des variables sont strictement positives.

Pour faire croître Z, on augmente la valeur d’une variable dont le coefficient dans la
ligne de Z est plus grande positive. Disons x3 .

e1 0 ce qui impose x3 8.4,

e2 0 ce qui impose x3 8.5,

e3 0 ce qui impose x3 8,

Cette opération revient à se déplacer d’un sommet de polyèdre (0, 0, 0, 0) à un autre sommet
(0, 0, 8, 0) le long d’une arrête jusqu’à rencontrer un nouvel hyperplan (e3 = 0).
Pour pouvoir itérer cette opération, il faut obtenir un nouveau dictionnaire en échangeant
les rôles de x3 et e3 .
1 2 5
e1 = 2 x1 x2 2x4 e3
3 3 3
1 1 2
e2 = 1 x1 + x2 + e3
3 3 3
1 2 1
x3 = 8 x1 x2 x4 e3 Dictionnaire II
3 3 3
Z = 144 + x1 3x2 x4 6e3
 36

On doit choisir x1 comme variable entrante. Limite sur l’argumentation de x1 :

x3 0 ce qui impose x1 24,

e1 0 ce qui impose x1 6,

e2 0 ce qui impose x1 3,

Donc la variable e2 sort de la base.

x1 = 3 + x2 3e2 + 2e3

e1 = 1 x2 2x4 + e2 + e3

x3 = 7 x2 x4 + e2 x7 Dictionnaire III

Z = 147 2x2 x4 3e2 4e3

Cette opération revient à se déplacer d’un sommet de polyèdre (0, 0, 8, 0) à un autre

sommet (3, 0, 7, 0) le long d’une arrête jusqu’à rencontrer un nouvel hyperplan (e2 = 0).
Tous les coefficients dans la ligne de la fonction objectif sont négatifs, donc la solution
courante est x1 = 3, x2 = x4 = e2 = e3 = 0 et x3 = 7 est optimale et sa valeur est 147.
Exemple 4:
On considère le programme linéaire suivant.


 2x1 + 2x2 + 8x3 + 7x4 40







 2x1 + 3x2 + 6x3 + 4x4 10

x1 + 2x2 + x3 + 3x4 80





 max(6x1 + 8x2 + 5x3 + 8x4 )




 xi 0

Résoudre ce problème en utilisant la méthode de simplexe.

 37

Exemple 5:
On considère le programme linéaire suivant.


 x1 + 2x2 + 7x3 + 2x4 50







 x + 3x2 + 5x3 + 2x4 30
 1
2x1 + 6x2 + 4x3 + 3x4 10





 max(x1 + 2x2 5x3 + 2x4 )




 xi 0

Résoudre ce problème en utilisant la méthode de simplexe et la méthode de dictionnaire.

VI.1 Dégénérescence
La présence de plusieurs candidats pour quitter la base a des conséquences intéressantes.
Pour illustrer ce fait, regardons l’exemple suivant:
Exemple: Résoudre le système suivant en utilisant les dictionnaires:


 2x3 1







 2x1 4x2 + 6x3 3

x1 + 3x2 + 4x3 2





 max(2x1 x2 + 8x3 )




 xi 0

Solution: On introduit les variables décart:

e1 = 1 2x3

e2 = 3 2x1 + 4x2 6x3

e3 = 2 + x1 3x2 4x3

Z = 2x1 x2 + 8x3

Après avoir choisi x3 comme variable entrante en base, on trouve que les trois variables de
base e1 , e2 , e3 limitent la croissance de x3 à 12 . Ainsi chacune de ces trois variables peut être
 38

choisie pour quitter la base. Nous choisissons e1 . Après avoir pivoté, on obtient le dictionnaire:

1 1
x3 = e1
2 2
e2 = 2x1 + 4x2 + 3e1

e3 = x1 3x2 + 2e1

Z = 4 + 2x1 x2 + 4e1

Ce dictionnaire diffère de tous les autres rencontrés jusqu’à présent. En effet, dans la
solution réalisable associée à ce dictionnaire, les variables de base e2 et e3 sont nulles. Les
solutions de base ayant une (ou plusieurs) variable(s) de base nulle(s) sont dites dégénérées.
La dégénérescence peut avoir des effets de bord ennuyeux. Ce fait est illustré par les
itérations suivantes de l’exemple précédent. En effet, x1 entre en base et e2 quitte la base.
A cause de la dégénérescence, la contrainte e2 0 limite l’incrément de x1 à zéro. Ainsi la
valeur de x1 reste inchangée, de même que les valeurs des autres variables et de la fonction
objectif Z. C’est ennuyeux, puisque la motivation première de l’algorithme du simplexe est
d’augmenter la valeur de la fonction objectif à chaque itération. Pour cette itération, notre
désir reste insatisfait et le pivot nous donne le dictionnaire suivant:

11
x3 = e1
22
3 1
x1 = 2x2 + e1 e2
2 2
7 1
e3 = x2 + e1 e2
2 2
Z = 4 + 3x2 e1 e2

Cela n’affecte pas la solution associée. Les itérations du simplexe qui ne modifient pas la
solution de base sont dites dégénées. Vous pourrez vérifier que l’itération suivante est à
nouveau dégénérée, mais celle d’après ne l’est pas et fournit la solution optimale.
 39

Le pivot est donc le coefficient de x2 et on obtient le système suivant:

1 1
x3 = e1
2 2
17 3
x1 = e1 e2 2e3
2 2
7 1
x2 = e1 e2 e3
2 2
19 5
Z = 4 + e1 e2 3e3
2 2

Le pivot est donc le coefficient de e1 et on obtient le système suivant:

e1 = 1 2x3
17 3
x1 = 17e1 e2 2e3
2 2
7 1
x2 = 7x3 e2 e3
2 2
27 5
Z = 19x3 e2 3e3
2 2

Dans un sens, la dégénérescence est accidentelle. En effet, une variable de base ne peut
disparaître (i.e valoir zéro) que si les opérations successives du pivot mènent exactement à
la suppression dans chaque ligne d’une même variable. Pourtant la dégénérescence dit que
presque tous les problèmes pratiques mènent à une solution de base réalisable dégénérée à une
certaine itération de l’algorithme du simplexe. Quoi qu’il se passe, la méthode du simplexe
peut stagner en passant par quelques itérations (parfois nombreuses) dégénérées sur une ligne.
En règle générale, un tel bloc d’itérations se termine par la découverte d’une itération non
dégénérée. Mais ce n’est pas toujours le cas et nous allons vous présenter un contre-exemple.
V.2 Les cycles
Est-ce que la méthode du simplexe peut engendrer un nombre infini d’itérations sans
jamais trouver la solution optimale ? La réponse est OUI. Pour justifier ce fait, considérons
le dictionnaire suivant:
Exemple:
 40

Résoudre le système suivant en utilisant les dictionnaires:



 1
x 11
x 5
x + 9x4 0

 2 1 2 2 2 3



 1 3 1

 x
2 1
x
2 2
x + x4 0
2 3

x1 1





 max(10x1 57x2 9x3 24x4 )




 xi 0

Solution:
Introduction des variables d’écart:

1 11 5
e1 = x1 + x2 + x3 9x4
2 2 2
e2 = 1 x1
1 3 1
e3 = x1 + x2 + x3 x4
2 2 2
Z = 10x1 57x2 9x3 24x4

On pose les règles suivantes:

La variable entrante sera toujours la variable hors base ayant le plus grand coefficient
dans la ligne du dictionnaire associée à la fonction objectif Z.

Si plusieurs variables peuvent être choisies pour quitter la base, on prendra celle de plus
petit indice. Ainsi, nous obtenons pour les six prochaines itérations, les dictionnaires
suivants:

La première itération: x1 entrante et e1 par exemple sortante

x1 = 11x2 + 5x3 18x4 2e1

e2 = 4x2 2x3 + 8x4 + e1

e3 = 1 11x2 5x3 + 18x4 + 2e1

Z = 53x2 + 41x3 204x4 20e1

 41

La deuxième itération: x2 entrante et e2 par exemple sortante

1 1 1
x2 = x3 + 2x4 + e1 e2
2 4 4
1 3 11
x1 = x3 + 4x4 + e1 e2
2 4 4
1 3 11
e3 = 1 + x3 4x4 e1 + e2
2 4 4
29 27 53
Z = x3 98x4 e1 e2
2 4 4

La troisiéme itération: x3 entrante et x1 par exemple sortante

1 5
x2 = x1 2x4 e1 e2
2 2
3 11
x3 = 2x1 8x4 + e1 e2
2 2
e3 = 1 x1

Z = 29x1 + 18x4 + 15e1 93e2

La quatrième itération: x4 entrante et x2 par exemple sortante

1 1 1 5
x4 = x1 x2 e1 + e2
2 2 4 4
1 9
x3 = 2x1 4x2 e1 + e2
2 2
e3 = 1 x1
21 141
Z = 20x1 9x2 + e1 e2
2 2

La cinquième itération: e1 entrante et x3 par exemple sortante

1 3 1
x4 = x1 + x2 + x3 e2
2 2 2
e1 = 4x1 8x2 2x3 + 9e2

e3 = 1 x1

Z = 22x1 93x2 21x3 + 24e2

 42

La sixième itération: e2 entrante et x4 par exemple sortante

1 3 1
e2 = x1 + x2 + x3 x4
2 2 2
1 11 5
e1 = x1 + x2 + x3 9x4
2 2 2
e3 = 1 x1

Z = 10x1 57x2 9x3 24x4

On retrouve donc le premiér dictionnaire après avoir introduire les variables d’ecart.
Puisque le dictionnaire construit après la sixième itération est identique au dictionnaire
initial, la méthode bouclera sur les mêmes itérations indéfiniment, sans jamais trouver la
solution optimale (laquelle, comme nous le verrons plus tard, vaut 1). Ce phénomène est
connu sous le nom de cycle. Plus précisément, nous disons que la méthode du simplexe cycle
si un dictionnaire apparaît dans deux itérations différentes (et donc la séquence d’itérations
menant de ce dictionnaire à lui-même peut être répétée sans fini). Il faut noter que les cycles
ne peuvent apparaître qu’en présence de dégénérescence: puisque la valeur de la fonction
objectif augmente avec chaque itération non dégénérée et reste inchangée après celles qui le
sont, toutes les itérations dans une séquence menant d’un dictionnaire à lui-même doivent
être dégénérées. Les cycles sont la raison pour laquelle la méthode du simplexe peut ne pas
terminer; le théorème suivant montre que c’est l’unique raison.
Théorème 1 : Si la méthode du simplexe ne termine pas, alors elle doit cycler.
C’esst pourquoi, dans la plupart des implémentations de l’algorithme du simplexe, le
problème du cycle n’est pas pris en compte.
Plusieurs méthodes existent pour prévenir le phénomène de cycle. La méthode classique
de perturbation et la mèthode lexicographique évitent de cycler par un choix judicieux de la
variable sortante à chaque itération du simplexe. La règle du plus petit indice, méthode plus
récente, se base sur le choix de la variable entrante et aussi de celle sortante. Cette dernière
méthode, quant à elle, ne nécessite pas de calcul supplémentaire, mais elle ne laisse pas le
choix des variables entrantes et sortantes.
La règle du plus petit indice: Lorsque plusieurs variables sont candidates pour entrer
(resp. sortir) de la base, on prend toujours celle ayant le plus petit indice. La motivation
 43

pour adopter cette règle provient du résultat suivant:

Théorème 2: La méhode du simplexe s’arrête dès lors que les variables en-
trantes et sortantes sont sélectionnéss via la rèlge du plus petit indice, à chaque
itération.
 44

Chapitre III. Dualité en programmation linéaire

 45

Dualité en programmation linéaire

I. Introduction
Définition 1:
On appelle un programme primal un modèle de programmation linéaire associé à un
problème donné ou encore modèle original.
Pour chaque modèle de programmation linéaire, il existe un et un seul autre modèle de
programmation linéaire appelé un programme dual (ou bien son dual).
Comme le modèle original a deux formes importantes qui sont la forme canonique et la
forme standard, alors le modè le dual aussi a ces deux formes.
Définition 2:
On dit qu’un programme linéaire est dans sa forme symétrique si les variables sont toutes
non négatives et que toutes les contraintes de type dans le cas d’une maximisation où
toutes les contraintes de type dans le cas de minimisation de la fonction objectif.

II. Le dual d’une forme linéaire canonique

La forme canonique d’un programme primal consiste en un modèle de programmation
linéaire dont l’optimisation en est une de maximisation avec des contraintes de type inférieure
ou égal et des variables toutes positives, on lui associe un programme canonique dual dont
l’optimisation en est une de minimisation avec des contraintes de type supérieur ou égal et
des variables toutes positives.
Tout programme primal canonique de type :


 maximiserZ = C T X


AX B




X, B 0

On lui associe son dual canonique de la forme:



 minimiserW = B T Y


Y TA C




Y 0
 46

Autrement:
 Pn  Pm
 maximiserZ = 

 i=1 ci xi 
 minimiserW = i=1 bi yi
 
Pn Pn
Primal : i=1 aij xj bi , 81 i m Dual : aij yi ci , 81 j m

 

i=1

 

xj 0 yi 0

Remarque:

1) Si la fonction objectif du primal doit être maximiser, celle du dual doit être minimiser
et inversement.

2) Les coefficients cj de la fonction objectif du primal oû les composantes de C deviennent

les seconds membres des contraintes du dual alors que les seconds membres des con-
traintes du primal où composantes de B deviennent les coefficients des variables duales
dans la fonction objectif.

3) Les coefficients des variables dans les contraintes du dual sont ceux du primal mais
transposés: les coefficients de la ième ligne du primal deviennent les coefficients de la
ième colonne du son dual.

4) A chaque contrainte du primal de type , lui associe une variable du dual positive.

5) A chaque variable de décision non négative dans le primal, lui correspond une contrainte
non négative dans son dual.

6) La dualité est une notion symétrique: L’un des programmes au choix est appelé le
programme primal et l’autre le programme dual.

7) Le dual du dual est le programme primal.

III. Le dual d’une forme linéaire standard

Tout programme primal standart de type :


 maximiserZ = C T X


AX B




X 0
 47

On lui associe son dual canonique de la forme:



 minimiserW = B T Y


Y TA C




Y 0

Autrement:
 P  Pm
 maximiserZ = ni=1 ci xi  minimiserW =

 
 i=1 bi yi
 
Pn Pn
Primal : i=1 aij xj bi , 81 i m Dual : aij yi ci , 81 j m

 

i=1

 

xj 0 yi 0

Tout programme primal standart de type :



 maximiserZ = C T X


AX = B




X 0

On lui associe son dual canonique de la forme:



 minimiserW = B T Y


Y TA C




Y sans restriction de signe

Autrement:
 Pn  Pm
 maximiserZ = 

 i=1 ci xi 
 minimiserW = i=1 bi yi
 
Pn Pn
Primal : i=1 aij xj = bi , 81 i m Dual : aij yi ci , 81 j m

 

i=1

 

xj 0 yi sans restriction de signe

En utilisant la symétrie de la dualité on déduit :

Tout programme primal standart de type :


 minimiserZ = C T X


AX B




X 0
 48

On lui associe son dual canonique de la forme:



 maximiserW = B T Y


Y TA C




Y 0

Autrement:
 P  Pm
 minimiserZ = ni=1 ci xi  maximiserW =

 
 i=1 bi yi
 
Pn Pn
Primal : a x bi , 81 i m Dual : aij yi ci , 81 j m
 i=1 ij j
 

i=1

 

xj 0 yi 0

Exemple: Formuler le dual des programmes linéaires suivant:

 

 maximiserZ = 3x1 + 5x2 + 6x3 
 maximiserZ = 2x1 + 4x2

 


 


 


 x 1 2x 2 + 6x 3 = 20 
 2x1 2x2 + 3x3 = 250
 
2x1 + 8x2 + x3 15 2x1 + 8x2 9x3 = 150

 


 


 x + 10x + 5x 120 
 x1 + 10x2 + 5x3 12


1 2 3 


 

 xi 0  xi 0
 

 maximiserZ = 2x1 + 4x2 + 8x3 + 5x4 
 maximiserZ = 3x1 + 5x2 + 2x3

 


 


 


 2x 1 2x 2 + 3x 3 = 250 
 x1 2x2 + 6x3 = 20
 
2x1 + 8x2 9x3 = 150 2x1 + 8x2 + x3 = 15

 


 


 x1 + 10x2 + 5x3 = 120 
 x1 + 10x2 + 5x3 12

 


 

 xi 0  xi 0
 

 minimiserZ = 2x1 + 4x2 
 minimiserZ = 2x1 + 4x2 + 8x3 + 5x4

 


 


 


 2x1 2x2 + 3x3 = 250 
 2x1 2x2 + 3x3 = 250
 
2x1 + 8x2 9x3 15 2x1 + 8x2 9x3 = 150

 


 


 x1 + 10x2 + 5x3 120 
 x1 + 10x2 + 5x3 = 12

 


 

 x 0  xi 0
i

IV. Le dual d’unne forme linéaire quelconque

Le modèle de programmation linéaire ne se présente pas toujours dans la forme canonique.
Comme nous le savons, un modèle peut se présenter avec des contraintes comportant les
symboles , ou = .
 49

IV.1. Rèles générales pour formuler le dual

Pour obtenir le dual d’un programme primal comportant les équations qui n’ont pas un
même sens on procède comme suit:

1) On cherche à standardiser le programme linéaire: soit trouvé sa forme canonique ou sa

forme standard.

2) Puis on utilise l’une des méthodes précédentes: formulation du dual.

IV.2. Description générale du dual-primal

Maximiser Z où W dans l’ordre () Minimiser Z où W dans l’ordre

 

 Nombre de contraintes 
 Nombre de variables duales

 


 


 


 A la contrainte i 
 Correspond la variable yi
 
Contrainte de type () yi 0

 


 


 Contrainte de type 
 yi 0

 


 

 Contrainte de type =  y sans restriction de signe
i

 

 Nombre de variables(décisions) 
 Nombre de contraintes

 


 


 
 Contrainte de type
xi 0
()

 x 0 
 Contrainte de type

 i 


 


 xi sans restriction de signe 
 Contrainte de type =

IV.3. Relation entre les valeurs numériques des fonctions objectifs

Soient un programme linéaire dans sa forme standard et son dual. Pour toute solution
réalisable X au programme linéaire et toute solution réalisable Y au son programme dual, on
a:

Dans le cas de maximiser la fonction objectif; la valeur maximale de la fonction objectif

du primal pour toute solution réalisable au primal sera toujours inférieure ou égale à la
valeur de la fonction objectif du son dual et on écrit:

CT X BT Y
 50

Dans le cas de minimiser la fonction objectif; la valeur minimale de la fonction objectif

du primal pour toute solution réalisable au primal sera toujours supérieure ou égale à
la valeur de la fonction objectif du son dual et on érit:

CT X BT Y

On déduit donc que C T X inf(B T Y ) pour toute solution réalisable Y du son dual et
que sup(C T X) B T Y pour toute solution réalisable X du primal. Par suite sup(C T X)
inf(B T Y ) pour toute solution réalisable X et Y du primal et du son dual respectivement.
Etant donné un programme primal de programmation linéaire et son dual, on a exactement
l’un des trois cas suivant:

Si X et Y sont deux solutions optimales du primal respectivement du son dual, alors

C T X = B T Y.

Si un programme présente des solutions réalisables mais pas de solution optimale finie,
l’autre programme n’admet pas de solution réalisable.

Aucun des deux programmes n’a pas de solution réalisable.