BELLAL Samir

Introduction à la Recherche
Opérationnelle

0
 AVANT- PROPOS

Le présent manuel est, comme son titre l’indique, une introduction à la

Recherche Opérationnelle. Cette dernière prend une importance de plus en plus
considérable dans différentes disciplines, dont les disciplines économiques et de
gestion.

Cet ouvrage est particulièrement destiné aux étudiants des Facultés de

Sciences Economiques, Commerciales et de Gestion ainsi qu’aux étudiants des
grandes écoles (ENSSEA, ENSM, HEC, …) dispensant une formation
économique étendue. Le contenu de l’ouvrage est spécifiquement conforme au
programme officiel du module « Mathématiques de l’entreprise » prévu en
deuxième année Licence en sciences économiques, commerciales et sciences de
gestion. L’ouvrage s’adresse également aux étudiants de spécialités diverses qui
utilisent les techniques d’optimisation en général, et la programmation linéaire
en particulier.

Dans cet ouvrage, chaque chapitre comprend un rappel de cours, suivi d’un
certain nombre d’exercices, souvent corrigés. Les exercices sont souvent
empruntés au domaine de l’économie et de la gestion.

Ce travail est naturellement susceptible de comporter quelques erreurs de

calcul. Leur détection constituerait cependant un exercice profitable pour le
lecteur.

Samir BELLAL
Maître de Conférences
Université de Tizi-Ouzou

1
 Sommaire

Chapitre 1. Introduction – Généralités – Rappels

Chapitre 2. La méthode du simplexe

Chapitre 3. La dualité

Chapitre 4. La paramétrisation

Chapitre 5. Le problème de transport

Chapitre 6. La programmation linéaire en nombres entiers

Chapitre 7. La théorie des graphes

2
 Chapitre 1
Introduction- Généralités- Rappels

La Recherche Opérationnelle a pour objet l’élaboration des méthodes

scientifiques de résolution des problèmes liés à la planification, à la gestion et à
la production.

I. Présentation et caractéristiques d’un problème de programmation

linéaire
Un problème de programmation linéaire est constitué de trois éléments :
1. Une fonction objective ; fonction linéaire.
2. Un ensemble de relations linéaires liant les variables entre elles ; ces relations
constituent les contraintes du problème.
3. Les variables du problème sont généralement positives ou nulles.

Résolution d’un problème de programmation linéaire :

Pour résoudre un problème de programmation linéaire, on utilise l’une des trois
méthodes suivantes :
1. La méthode algébrique ;
2. La méthode graphique ;
3. La méthode du simplexe.

Présentation et exemple :
Maximiser Z = 2 X1 + 4 X2 + 0,5 X3
Sous les contraintes :

3
 4 X1 + 2 X2 + 0 X3 ≤ 100
2 X1 + X2 + X3 ≤ 100
X1 + 3 X2 + X3 ≤ 100
X1, X2, X3 ≥ 0

Notation :
Max CX
AX ≤ b
X≥0
avec :

C= ; X= ;

A= ; b=

Forme standard :
A X = b ; X ≥ 0, b ≥ 0
On obtient la forme standard en introduisant des variables supplémentaires
appelées variables d’écart
Max CX Max CX
AX ≤ b → AX – X’ = b
X≥0 X, X’ ≥ 0

La matrice A est de dimension (m×n). La solution de base possède alors au

moins (n – m) coordonnées nulles. Dans l’ensemble des solutions réalisables,
certains points jouent un rôle particulier. Ce sont les sommets ou les points
extrêmes de l’ensemble.

4
II. Caractérisation algébrique des points extrêmes
1) Interprétation géométrique de la solution de base

La solution se trouve ou bien sur un des points extrêmes ou sur une arrête dans
certains cas.

2. Théorème
L’ensemble des points extrêmes d’un polytope E correspond à l’ensemble des
solutions de base réalisables.
Corollaire : L’ensemble convexe E = {x / xϵ Rn+ / AX = b} a un nombre fini k
de points extrêmes où k ≤ Cmn

5
III. Solution optimale d’un problème de programmation linéaire
1) Théorème
L’optimum de la fonction objective Z fonction linéaire sur E qui est inclus dans
Rn est atteint en au moins un point extrême. S’il est atteint en plusieurs points
extrêmes, il est atteint en tout point et combinaison convexe des points extrêmes.

2) Résumé
Les programmes linéaires sont résolubles grâce à certaines propriétés. Ces
propriétés sont les suivantes :
a) L’objectif est représenté par un hyperplan se déplaçant parallèlement à lui-
même.
b) Si la fonction objective Z est bornée dans E, la solution optimale se trouve en
un point extrême du polytope et on peut l’atteindre en un nombre fini d’étapes
par inspection d’un nombre fini de points extrêmes en passant d’un sommet à un
autre adjacent.

IV. Exercices

1. Résoudre par la méthode graphique le problème suivant :

Max M = 40 x1 + 60 x2
2 x1 + x2 ≤ 70
x1 + x2 ≤ 40
x1 + 3 x2 ≤ 90
x1 , x2 ≥ 0

6
Solution :

2. Résoudre par la méthode graphique les programmes linéaires suivants :

1) Max Z = X + Y
2X + Y ≤ 1
X + 2Y ≤ 3/2
X, Y ≥ 0

2) Max Z = 3X + Y
6X + 2Y ≤ 4
X, Y ≥ 0

3) Min Z = X + 2Y
2X + 3Y ≥ 1
4X + 9Y ≥ 2
X, Y ≥ 0

7
4) Min Z = X + 2Y
2X + 3Y ≥ 1
2X + 9/2 Y ≥ 2
3X + 6Y ≥ ½
X, Y ≥ 0

3. Une usine de textile fabrique 3 variétés de tissu T1, T2 et T3 à partir de 3

laines L1, L2 et L3. Le tableau suivant recense les poids (en kg) des laines
intervenant dans la composition d’un mètre des tissus :

T1 T2 T3
L1 0.375 0.125 0.1
L2 0.5 0.05 0.2
L3 0.5 0.2 0.15

On dispose d’un stock de 4000 kg de laine L1, 800 kg de laine L2 et 1500 kg de

laine L3. Les métiers à tisser ne peuvent fabriquer que 8000m de tissu. Les
profits nets résultant de la vente d’un mètre de tissu sont respectivement de 2.6
DA, 4 DA et 3.6 DA pour T1, T2 et T3.
Ecrire le problème de maximisation du profit sous la forme d’un programme
linéaire.

4. Un constructeur de postes de télévision possède 4 modèles à son catalogue : le

portatif Noir&Blanc (M1), le standard Noir&Blanc (M2), le standard couleur
(M3) et le couleur de luxe (M4). L’entreprise comporte un atelier de montage et
un de tests. Les durées nécessaires pour le montage et test des différents modèles
sont (en heures) :

M1 M2 M3 M4
Montage 8 10 12 15
Tests 2 2 4 5

8
La force de travail de l’atelier de montage est de 6000 heures/mois, celle de
l’atelier de tests est de 1500 heures/mois et les profits des postes M1, M2, M3 et
M4 sont respectivement de 4000 DA, 6000 DA, 8000 DA et 10000 DA.
L’entreprise dispose chaque mois de 450 transformateurs et de 300 tubes
cathodiques couleur. On a besoin d’un transformateur dans chaque poste
(Noir&Blanc ou couleur). La quantité disponible de tubes cathodiques
Noir&Blanc n’est pas limitée.
Ecrire le problème de maximisation du profit de cette entreprise sous la forme
d’un programme linéaire.

5. Une entreprise de relations publiques veut faire un sondage d’opinions.

Chaque employé fait par jour 80 interviews par téléphone ou bien 40 interviews
en direct. Un employé ne peut faire qu’un seul type d’interviews pendant une
journée.
Afin d’avoir un échantillon représentatif, on doit satisfaire les 3 critères
suivants :
- Au moins 3000 interviews ;
- Au moins 1000 interviews par téléphone ;
- Au moins 800 interviews en direct.
L’employé qui conduit l’interview par téléphone est payé 500 DA par jour ;
L’employé qui conduit l’interview en direct est payé 700 DA par jour.
Déterminer le programme linéaire associé à ce problème.

9
Solution :
Min C = 500 X + 700 Y
80 X + 40 Y ≥ 3000
80 X ≥ 1000
40 Y ≥ 800
X, Y ≥ 0

6. Un fabricant de raquettes de tennis fait un bénéfice de 8 euros sur chaque

raquette ordinaire et de 15 euros sur chaque grande raquette. Pour satisfaire à la
demande des vendeurs, la production journalière de raquettes ordinaires devrait
se situer entre 30 et 80, et la production journalière de grandes raquettes entre 10
et 30. Pour maintenir une bonne qualité, le nombre de raquettes produites ne
devrait dépasser 80 par jour. Combien de raquettes de chaque type faudrait-il
fabriquer quotidiennement pour réaliser un bénéfice maximum?

7. La fabrication d’une pièce P1 coûte 150 DA, celle d’une pièce P2 100 DA.
Chaque pièce est traitée successivement dans 3 ateliers. Le nombre d’heures-
machines par pièce est indiqué dans le tableau suivant:

Pour éviter le chômage technique, l’atelier A doit obligatoirement fournir 1200

heures machines, l’atelier B 3000 heures machines et l’atelier C 1800 heures
machines. Combien faut-il fabriquer de pièces P1 et P2 pour minimiser le coût
de revient de l’ensemble de la production et pour assurer le fonctionnement des
trois ateliers excluant tout chômage technique ?

10
8. Trois machines M1, M2, M3 peuvent produire chacune deux types de pièces
P1 et P2. Le temps de fabrication d’une pièce P i sur la machine M j est reporté
dans le tableau suivant (temps en heures)

On veut fabriquer au moindre coût 6 pièces P1 et 8 pièces P2. La machine M1

est disponible 14 heures, les deux autres machines sont disponibles 24 heures.
Le coût horaire de M1 est 7, celui de M2 est 5 et celui de M3, 6.
1) Ecrire le programme linéaire associé ;
2) Résoudre ce problème en énumérant toutes les solutions entières possibles.

11
 Chapitre 2
La méthode du simplexe

La méthode du simplexe est, dans la programmation linéaire, un procédé

mathématique permettant de tendre progressivement vers la solution optimale en
un nombre fini d’étapes.

I. Résolution des programmes linéaires

1) Passage d’une base à une base adjacente – Algorithme de base

On représente le problème dans le premier tableau du simplexe.
La méthode de résolution à suivre est la suivante :

Etape 1 : Localisation d’un élément pivot qui se fait en deux temps :

- Choisir dans la ligne de Z le plus grand coefficient négatif (pour un problème
de maximisation) ; à ce coefficient correspond la colonne de l’élément pivot ;
- Considérer les éléments positifs de la colonne choisie. Etablir les rapports entre
la constante bi et l’élément positif. La ligne de l’élément pivot correspond au
rapport dont la valeur est minimale. L’élément pivot se situe à l’intersection de
la colonne et de la ligne pivot.

Etape 2 : Les variables identifiant la ligne et colonne de l’élément pivot se

remplacent mutuellement.

Etape 3 : On applique l’une des méthodes pour passer au tableau suivant :

Nouvelle ligne pivot = Ligne pivot / Pivot ;
Autre nouvelle ligne = Ancienne ligne – (Coefficient pivot) × Ligne pivot

12
 Illustration :
Soit le tableau du simplexe dans lequel l’élément pivot est « a »

a1 a2 a3 a a4 a5 a6
b1 b2 b2 b b4 b5 b6

En application de la règle de l’étape 3, le passage au tableau suivant se fera

comme suit :
=1

- - - - -

: Coefficient pivot.

Etape 4 : On vérifie si la solution obtenue est réalisable (les valeurs obtenues

doivent être positives) ;

Etape 5 : On vérifie si la solution est optimale (Les coefficients de Z doivent être

positifs pour un problème de maximisation) ;

Etape 6 : On répète les cinq étapes précédentes jusqu’à l’obtention de la solution

optimale.

2) Exemple pratique

13
Max Z = 4 X1 + 3 X2 Max Z – 4 X1 – 3 X2
X1 ≤ 8 X1 + X’1 = 8
X2 ≤ 6 → X2 + X’2 = 6
X1 + 2 X2 ≤ 15 X1 + 2 X2 + X’3 = 15
2 X1 + X2 ≤ 18 2 X1 + X2 + X’4 = 18
X1, X2 ≥ 0 X1, X2 ≥ 0
X’1, X’2, X’3, X’4 ≥ 0

(X’1, X’2, X’3, X’4, X1, X2) = (8, 6, 15, 18, 0, 0) est une solution de base de
départ réalisable.

Tableau 1 :
X1 X2 X’1 X’2 X’3 X’4 b
X’1 1 0 1 0 0 0 8
X’2 0 1 0 1 0 0 6
X’3 1 2 0 0 1 0 15
X’4 2 1 0 0 0 1 18
Z -4 -3 0 0 0 0 0

X1 entre dans la base en remplacement de X’1

14
Tableau 2 :
X1 X2 X’1 X’2 X’3 X’4 b
X1 1 0 1 0 0 0 8
X’2 0 1 0 1 0 0 6
X’3 0 2 -1 0 1 0 7
X’4 0 1 -2 0 0 1 2
Z 0 -3 +4 0 0 0 32

X2 entre dans la base en remplacement de X’4

Tableau 3 :
X1 X2 X’1 X’2 X’3 X’4 b
X1 1 0 1 0 0 0 8
X’2 0 0 2 1 0 -1 4
X’3 0 0 3 0 1 -2 3
X2 0 1 -2 0 0 1 2
Z 0 0 -2 0 0 3 38

X’1 entre dans la base en remplacement de X’3

Tableau 4 :
X1 X2 X’1 X’2 X’3 X’4 b
X1 1 0 0 0 - 1/3 2/3 7
X’2 0 0 0 1 - 2/3 1/3 2
X’1 0 0 1 0 1/3 - 2/3 1
X2 0 1 0 0 2/3 - 1/3 4
Z 0 0 0 0 2/3 5/4 40

15
La solution (X1 = 7, X2 = 4) est réalisable et optimale.
La valeur maximale de Z est égale à 40.

II. Détermination d’une base de départ :

En pratique, il n’est pas toujours possible de mettre en évidence une base de
départ réalisable.
La méthode générale à suivre consiste à introduire des variables supplémentaires
appelées variables artificielles et variables d’écart permettant d’obtenir une
solution de départ réalisable, c’est-à-dire une solution qui vérifie les deux
propriétés suivantes :
- Chaque contrainte s’écrit en fonction d’une seule variable de base (nombre de
variables de base = nombre de contraintes) ;
- La fonction objective Z s’écrit en fonction des variables hors base.
Plusieurs méthodes peuvent être utilisées. Nous en exposerons deux : la méthode
des pénalités et la méthode des deux phases.

1) Méthode des pénalités (Méthode en M) :

Exemple :
Max Z = 3 X1 + 3 X2 + X3 Max Z – 3 X1 – 3 X2 – X3
X1 + 4 X2 ≤ 10 X1 + 4 X2 + X’1 = 10
X1 + X2 + X3 ≤ 12 → X1 + X2 + X3 + X’2 = 12
2X1 + X3 ≥ 8 2 X1 + X3 – X’3 = 8
X1, X2, X3 ≥ 0 X1, X2, X3 ≥ 0
X’1, X’2, X’3 ≥ 0

On obtient une solution de base qui n’est pas réalisable (car X’3 = - 8)
On introduit une variable artificielle t de la manière suivante :

16
Max Z = 3 X1 + 3 X2 + X3 – M t (+ M t pour Min)
X1 + 4 X2 + X’1 = 10
X1 + X2 + X3 + X’2 = 12
2 X1 + X3 – X’3 + t = 8 (3)
X1, X2, X3 ≥ 0
X’1, X’2, X’3, t ≥ 0

On vérifie les deux conditions précédentes :

1) Solution de base réalisable :
X’1 = 10 ; X’2 = 12 ; t = 8 ; on remarque qu’à chaque contrainte on associe une
et une seule variable de base.
X1 = X2 = X3 = X’3 = 0.
2) On exprime Z en fonction des variables hors bases (ici X1, X2, X3 et X’3).
- De la contrainte (3) on fait sortir t en fonction de X1, X2, X3 et X’3 ;
- Dans la fonction objective Z, on remplace t par sa valeur ;
- On obtient la forme définitive du problème :
Max Z = (3+2M) X1 + 3 X2 + (1+M) X3 – M X’3 – 8M
X1 + 4 X2 + X’1 = 10
X1 + X2 + X3 + X’2 = 12
2 X1 + X3 – X’3 + t = 8
X1, X2, X3, X’1, X’2, X’3 ≥ 0
- On applique la méthode du simplexe à ce problème. Le premier tableau du
simplexe se présente comme suit :
X1 X2 X3 X’1 X’2 X’3 t b
X’1 1 4 0 1 0 0 0 10
X’2 1 1 1 0 1 0 0 12
t 2 1 0 0 0 -1 1 8
Z -(3+2M) - 3 - (1+M) 0 0 +M 0 - 8M

17
On supprime la colonne de t une fois que le coefficient M disparait de la valeur
de Z.
On obtient la solution optimale suivante :
(X1 = 10 ; X3 = 2 ; X2 = 0) ; Z = 32.

2) La méthode des deux phases :

Exemple :
Min Z = 4 X1 + X2
3 X1 + X2 = 3 3 X1 + X2 + t1 = 3
4 X1 + 3 X2 – X3 = 6 → 4 X1 + 3 X2 – X3 + t2 = 6 ( I’)
X1 + 2 X2 + X4 = 4 X1 + 2 X2 + X4 = 4
X1, X2, X3, X4 ≥ 0 X1, X2, X3, X4, t1, t2 ≥ 0

La base de départ réalisable est ( t1 = 3 ; t2 = 6 ; X4 = 4 ).

Première phase :
Résoudre le problème intermédiaire Min T = t1 + t2 sous les contraintes I’
En écrivant T en fonction des variables hors base, cela revient à résoudre :
Min T = – 7 X1 – 4 X2 + X3 + 9
par la méthode du simplexe.
La solution optimale de ce problème est la suivante :
X1 = 3/5 ; X2 = 6/5 ; X3 = 0 ; X4 = 1.
Cette solution peut être prise comme solution de départ pour le problème initial.

Deuxième phase :
Le dernier tableau du simplexe (tableau optimal) étant :

18
 X1 X2 X3 X4 t1 t2 b
X1 1 0 1/5 0 3/5 - 1/5 3/5
X2 0 1 - 3/5 0 - 4/5 3/5 6/5
X4 0 0 1 1 1 -1 1
T 0 0 0 0 -1 -1 0

Min Z = 4 X1 + X2
X1 + 1/5 X3 = 3/5
X2 – 3/5 X3 = 6/5 (II)
X3 + X4 = 1

On écrit Z en fonction des variables hors base. On obtient :

Z = 18/5 – 1/5 X3
Le problème devient :
Min Z = 18/5 – 1/5 X3
X1 + 1/5 X3 = 3/5
X2 – 3/5 X3 = 6/5
X3 + X4 = 1
Par la méthode du simplexe, on obtient la solution optimale suivante :
(X1 = 2/5 ; X2 = 9/5 ; X3 = 1 ; X4 = 0) ; Z = 17/5
Il y a lieu de remarquer que le problème initial n’admet de solution de départ
que si l’on trouve, lors de la première phase, que Min T = 0.

III. Exercices
1. Soit deux machines M1 et M2 traitant chacune deux produits X et Y. Les
deux machines ne peuvent fonctionner que 3000 heures/ an. Nous savons d’autre
part qu’une unité de X requiert une heure de M1 et deux heures de M2 tandis
qu’une unité de Y requiert deux heures de M1 et une heure de M2. La marge sur

19
coût variable d’un X est de dix dinars, la marge sur coût variable d’un Y est de
douze dinars.
Déterminer graphiquement le programme optimal de production.

Solution :
Max (10 x + 12 y)
x + 2 y ≤ 3000
2x + y ≤ 3000
x, y ≥ 0
Graphiquement, la solution sera donnée par les coordonnées du point E,
intersection des deux droites dont les équations sont respectivement x + 2 y =
3000 et 2 x + y = 3000.
E (1000 ; 1000)
La fonction objective aura, à l’optimum, la valeur de 22000 dinars.

2. Une entreprise fabrique deux produits A et B à l’aide de trois (03) matières

premières I, II et III selon le tableau suivant :
Produit A Produit B Disponibilités
I 2 1 8 unités
II 1 2 7 unités
III 0 1 3 unités
Profit unitaire 4 DA 5 DA

Ce qui signifie : pour produire une (01) unité de A et une (01) unité de B, on
utilise deux (02) unités de I pour A et une (01) unité de I pour B, etc.
Déterminer le programme optimal de production.

20
Solution :
Max Z = 4 X1 + 5 X2
2 X1 + X2 ≤ 8
X1 + 2 X2 ≤ 7
X2 ≤ 3
X1, X2 ≥ 0

3. Problème de nutrition : On se propose de fournir quotidiennement à chaque

individu un minimum de 70 gr de protéines, 0,8 gr de calcium, 0,012 gr de fer et
3000 calories. Les produits disponibles sont le pain, le beurre, le fromage, les
petits pois et les épinards. Les prix par 100 gr de ces aliments sont de 3, 7, 7, 5
et 5 DA respectivement. Les quantités de protéines (en gr), de calories, de
calcium (en gr) et de fer (en gr) par 100 gr de ces aliments sont données par le
tableau suivant :

Protéines Calories Calcium Fer

Pain 10 300 0,05 0,004
Beurre 30 1800 0,4 0
Fromage 35 800 0,45 0
Petits pois 20 1500 0,75 0,004
Epinards 25 300 0,12 0,015

Donner un modèle mathématique, constituant aux moindres frais, les rations

journalières respectant les exigences de départ.

21
Solution :
Min Z = 3 X1 + 7 X2 + 7 X3 + 5 X4 + 5 X5
10 X1 + 30 X2 + 35 X3 + 20 X4 + 25 X5 ≥ 70
300 X1 + 1800 X2 + 800 X3 + 1500 X4 + 300 X5 ≥ 3000
0,05 X1 + 0,4 X2 + 0,45 X3 + 0,75 X4 + 0,12 X5 ≥ 0,8
0,004 X1 + 0,004 X4 + 0,015 X5 ≥ 0,012
X1, X2, X3, X4, X5 ≥ 0

4. Une entreprise a la faculté de fabriquer, sur une machine donnée, travaillant

45 heures par semaine, trois produits différents P1, P2 et P3. L’article P1 laisse
un profit net de 04 DA, l’article P2, de 12 DA, et, enfin, l’article P3, de 03 DA.
Les rendements de la machine sont, respectivement pour les trois produits, et
dans le même ordre : 50, 25 et 75 articles par heure. On sait, d’autre part, grâce à
une étude de marché, que les possibilités de vente ne dépassent pas : 1000 objets
P1, 500 objets P2 et 1500 objets P3, par semaine. On se pose le problème de
répartir la capacité de production entre les trois produits, de manière à
maximiser le profit.

Solution :
Max Z = 4 X1 + 12 X2 + 3 X3
X1 ≤ 1000
X2 ≤ 500
X3 ≤ 1500
1/50 X1 + 1/25 X2 + 1/75 X3 ≤ 45
X1, X2, X3 ≥ 0
La solution optimale de ce programme est :
( X1 = 250 ; X2 = 500 ; X3 = 1500 )
La valeur optimale de Z (Profit total) est de 11500 DA.

22
5. Une entreprise fabrique deux produits qu’elle désire vendre dans un pays
lointain. Le produit A rapporte 4 DA par kg et le produit B rapporte 6 DA par
kg. Ayant des moyens financiers limités, la société ne peut affréter qu’un seul
avion. Celui-ci ne peut transporter que 50 tonnes et un volume de 2100 m3. Le
produit A a un volume de 30 m3 par tonne, le produit B a un volume de 70 m3
par tonne.
Combien de kg de chaque produit l’entreprise doit-elle mettre dans l’avion afin
de maximiser ses gains ?

6. Résoudre le programme linéaire suivant :

Max ( 5 X1 + 4 X2 + 3 X3 + X4 )
sous les contraintes :
X1 + X2 + X3 + X4 ≤ 12
3 X1 + 2 X2 + 3 X3 + X4 ≤ 5
2 X1 + X2 + X3 + 4 X4 ≤ 7
X1, X2, X3, X4 ≥ 0

7. Résoudre le programme linéaire :

Max W = X + Y + 1/3 Z
2X + 8Y ≤ 20
½X+½Y+½Z≤6
X+½Z≥4
X, Y, Z ≥ 0

Solution :
En utilisant la méthode en M, on obtient le premier tableau du simplexe
suivant :

23
 X Y Z X’1 X’2 X’3 t b
X’1 2 8 0 1 0 0 0 20
X’2 1/2 1/2 1/2 0 1 0 0 6
t 1 0 1/2 0 0 -1 1 4
W - (1+M) - 1 - (1/3 +1/2 M) 0 0 + M 0 - 4M

En appliquant l’algorithme du simplexe à ce tableau, on obtient la solution

suivante :
( X = 10 ; Y = 0 ; Z = 2 ) ; W = 10 + 2/3

8. Résoudre le programme linéaire suivant :

Min Z = X1 + X2
2 X1 + X2 ≥ 4
X1 + 3 X2 ≥ 3
X1, X2 ≥ 0

Solution :
On applique la méthode en M en introduisant deux variables artificielles t1 et
t2.
Après transformation, on obtient :
Min Z = (1-3M) X1 + (1- 4M) X2 + M X’1 + M X’2 + 7M
2X1 + X2 – X’1 + t1 = 4
X1 + 3 X2 – X’2 + t2 =3
X1, X2, X’1, X’2, t1, t2 ≥ 0
Le dernier tableau du simplexe (tableau optimal) se présente comme suit :

24
 X1 X2 X’1 X’2 t1 t2 b
X1 1 0 - 3/5 1/5 3/5 - 1/5 9/5
X2 0 1 1/5 - 2/5 - 1/5 2/5 2/5
Z 0 0 - 2/5 - 1/5 11/5

La solution optimale est :

( X1 = 9/5 ; X2 = 2/5 ) ; Z = 11/5.

9. Trouver, en utilisant la méthode des deux phases, la solution du programme

linéaire :

Max ( 2 X1 + 3 X2 – X3 + X4 – 3 X5 )
sous les contraintes :
X1 – X2 + X4 – X5 = 100
X2 – X3 + 2 X4 = 20
X3 – X4 ≤ 50
X1, X2, X3, X4, X5 ≥ 0

Solution :
( X1 = 170 ; X2 = 70 ; X3 = 50 ) ; Z = 500.

10. Trois machines M1, M2 et M3 peuvent prendre chacune deux types de

pièces P1 et P2. Le temps de fabrication (en heures) est donné dans le tableau
suivant :
M1 M2 M3
P1 3 4 4
P2 4 6 5

25
On veut fabriquer au moindre coût six (06) pièces P1 et huit (08) pièces P2. La
machine M1 est disponible 14h, les deux autres machines sont disponibles 24h.
Le coût horaire de M1 est 7 DA, celui de M2 est de 5 DA et celui de M3 est de 6
DA.
- Ecrire le programme linéaire associé ;
- Résoudre le problème.

11. Une baguette de pain vaut 10 DA. Elle contient 900 calories et 20 gr de
protéines. Un camembert vaut 50 DA. Il contient 1800 calories et 80 gr de
protéines. Une personne en convalescence doit absorber au minimum 3600
calories et 120 gr de protéines par jour en ne consommant que du camembert et
du pain en baguette. Déterminer la ration alimentaire la moins chère satisfaisant
au régime indiqué.

12. Résoudre par la méthode des deux phases le programme linéaire suivant :
Max Z = – 3 x1 + 2 x2 – 2 x3 – x4
4 x1 – 2 x2 + x 3 – x4 ≤ – 2
– x1 – x3 ≤ – 10
x1 x 2 x3 x4 ≥ 0

13. Un investisseur désire placer une somme de 50000 $ en actions. Trois

catégories d’actions sont envisageables :
Des valeurs sûres (1) donnent un rendement de 5 %, des valeurs de croissance
(2) un rendement de 8 %, tandis que des valeurs spéculatives à haut risque (3)
atteignent 16 %.
Déterminer le placement maximisant le rapport annuel, sachant que
l’investisseur souhaite prudemment limiter à 25000 $ au plus le placement 3

26
(haut risque), et à 30000 $ au plus la somme des placements 2 et 3 (croissance et
haut risque)

Solution :
Max Z = 5 X1 + 8 X2 + 16 X3 (X1, X2, X3 : sommes en milliers de $)
X1 + X2 + X3 ≤ 50
X2 + X3 ≤ 30
X3 ≤ 25
X1 X2 X3 ≥ 0
La solution consiste à investir respectivement 20000 $, 5000 $ et 25000 $ dans
les placements proposés, pour un rapport annuel global de 540 x 1000/100 =
5400 $.

27
 Chapitre 3
La dualité

Chaque programme linéaire comporte un programme dual.

I. Forme canonique du programme linéaire dual

On considère un Programme linéaire sous la forme canonique :
(I) Max Z = C X
AX≤b
X≥0
Le problème dual associé à ce programme linéaire est défini de manière
suivante :
(II) Min Z = λt b
At λ ≥ Ct
λ≥0

Les programmes primal et dual sont étroitement liés l’un à l’autre, comme le
montre cet exemple :

I. Primal II. Dual

Max Z = C1 X1 + C2 X2 Min Z = b1 λ1 + b2 λ2
a 11 X1 + a 12 X2 ≤ b1 a 11 λ1 + a 21 λ2 ≥ C1
a 21 X1 + a 22 X2 ≤ b2 a 12 λ1 + a 22 λ2 ≥ C2

Règles de passage de I à II :
- Si les contraintes du primal sont des égalités, alors les variables duales (λ)
associées à ces égalités sont de signes quelconques ;

28
- Si les contraintes du primal sont incompatibles, alors :
ou bien les contraintes du dual sont incompatibles ;
ou bien les contraintes du dual n’admettent pas de solutions bornées.
- Si (I) n’admet pas de solution bornée bien que les contraintes soient
compatibles, alors les contraintes de (II) sont incompatibles.

Maximisation Minimisation
= Variable quelconque
Contraintes ≤ Variable ≥ 0
≥ Variable ≤ 0
Quelconque Contrainte =
Variables ≥0 Contrainte ≥
≤0 Contrainte ≤

Les solutions optimales d’un problème et de son dual sont liées par les
propriétés suivantes :
- Si une variable Xi est strictement positive dans la solution optimale (Xi   0),
la contrainte duale correspondante doit être, à l’optimum, satisfaite en tant
qu’égalité ;
- Si une contrainte du problème direct (primal) est, pour la solution optimale,
satisfaite en tant qu’inégalité stricte, la variable duale associée est nulle à
l’optimum ;
- Si une variable λs est strictement positive dans la solution optimale (λs  0), la
contrainte du problème direct (primal) à laquelle elle est associée, est satisfaite,
à l’optimum, en tant qu’égalité ;
- Si une contrainte du problème dual est, pour la solution optimale, satisfaite en
tant qu’inégalité stricte, la variable du problème direct qui lui correspond est
nulle à l’optimum.

29
II. La méthode duale du simplexe

Exemple :
Min t = 6 X1 + 4 X2
3 X1 – X2 ≥ 3 → 3 X1 – X2 – X’1 = 3
2 X1 – 2 X2 ≥ 4 2 X1 – 2 X2 – X’2 = 4

En utilisant la méthode duale du simplexe, on n’est pas tenu d’introduire les t i

3 X1 – X2 – X’1 + t1 = 3
2 X1 – 2 X2 – X’2 + t2 = 4
Ici, la solution (X’1 = -3 ; X’2 = - 4) est une solution non réalisable.

1) Présentation
L’algorithme dual du simplexe est une méthode très proche de la méthode du
simplexe et tout aussi fondamentale.
Dans cette méthode, contrairement à la méthode du simplexe, on part d’une
solution non réalisable et d’une fonction trop avantageuse.
- La solution est non réalisable car il existe des bi négatifs ;
- La fonction est trop avantageuse en ce sens que l’on ne va pouvoir que la
détériorer. Dans ce cas, on parle de solution pseudo-optimale.
La méthode duale consiste à partir d’une solution non réalisable que l’on
cherche à rendre réalisable en éliminant une à une les variables basiques tout en
conservant l’optimalité de la solution.

2) Algorithme dual du simplexe et exemple pratique

- Si les contraintes du programme dual sont compatibles, on détermine un
programme principal de départ pseudo-optimal.
- Pour un problème de minimisation, les différentes étapes de l’algorithme sont
les suivantes :

30
Etape 1 :
On commence avec un tableau dans lequel tous les coefficients de la fonction
objective sont négatifs ou nuls, i.e
Cj ≤ 0 j

Etape 2 :
Si bi ≥ 0 i, le problème est résolu.
Sinon on choisit max .
On essaye d’échanger la variable de base Xi avec une variable hors base pour
obtenir un programme pseudo-optimal. Si tous les a i, j+m de la ligne i sont ≥ 0, le
problème n’a pas de solution.
S’il existe a i, j+m ˂ 0, on prend :

C j / a i, j = min j

Dans le cas d’une maximisation, on prend :

max j

Etape 3 :
Effectuer le pivotage de Xi Xj autour du pivot. Cet échange conduit à un
programme pseudo-optimal donnant à la fonction une valeur moins avantageuse.
Ensuite retourner à l’étape 2.

Exemple :
Soit le programme linéaire suivant :

31
Min Z = 468 X1 +540 X2 + 648 X3
9 X1 + 6 X2 ≥ 54
9 X2 + 12 X3 ≥ 45
3 X1 + 3 X2 ≥ 18
3 X1 + 3 X2 + 3 X3 ≥ 36
6 X1 + 3 X2 + 9 X3 ≥ 90

On introduit les variables d’écart de la manière suivante :

– 9 X1 – 6 X2 + X’1 = – 54
– 9 X2 – 12 X3 + X’2 = – 45
– 3 X1 – 3 X2 + X’3 = – 18
– 3 X1 – 3 X2 – 3 X3 + X’4 = – 36
– 6 X1 – 6 X2 – 9 X3 + X’5 = – 90

Tableau 1 :
X1 X2 X3 X’1 X’2 X’3 X’4 X’5 b
X’1 -9 -6 0 1 0 0 0 0 - 54
X’2 0 -9 - 12 0 1 0 0 0 - 45
X’3 -3 -3 0 0 0 1 0 0 - 18
X’4 -3 -3 -3 0 0 0 1 0 - 36
X’5 -6 -6 -9 0 0 0 0 1 - 90
Z - 468 - 540 - 648 0 0 0 0 0 0

32
Tableau 2:
X1 X2 X3 X’1 X’2 X’3 X’4 X’5 b
X’1 -9 -6 0 1 0 0 0 0 - 54
X’2 8 -1 0 0 1 0 0 - 4/3 75
X’3 -3 -3 0 0 0 1 0 0 - 18
X’4 -1 -1 0 0 0 1 1 - 1/3 -6
X3 2/3 2/3 1 0 0 0 0 - 1/9 10
Z - 36 - 108 0 0 0 0 0 - 72 +6480

Tableau 3 :
X1 X2 X3 X’1 X’2 X’3 X’4 X’5 b
X1 1 2/3 0 - 1/9 0 0 0 0 6
X’2 0 - 19/3 0 8/9 1 0 0 - 4/3 27
X’3 0 -1 0 - 1/3 0 1 0 0 0
X’4 0 - 1/3 0 - 1/9 0 0 1 - 1/3 0
X3 0 2/9 1 2/27 0 0 0 - 1/9 6
Z 0 - 84 0 -4 0 0 0 - 72 +6696

La solution à ce problème est :

(X1 = 6 ; X2 = 0 ; X3 = 6) ; Z = 6696

III. Exercices

1. Donner les problèmes duaux pour les problèmes suivants :

33
a) Min Z = x1 – 2 x2 + x3 – x4 + x5
x1 – 2 x2 + x3 – 3 x4 – 2 x5 = 6
2 x1 + 3 x2 – 2 x3 – x4 + x5 ≤ 4
x1 + 3 x3 – 4 x5 ≥ 8
x1 ≥ 0, x2 ≥ 0, x3 et x4 sont quelconques.

b) Max z = 2 x1 – x3
x1 + x2 + x3 ≤ 4
3 x2 + 5 x3 = 5
– x1 + x2 ≥ 0
x2 – x3 = 2
x1 – x2 – x3 ≤ – 2
x1 ≥ 0, x3 ≥ 0, x2 est quelconque.

c) Min Z = c x + d y
A1 x + A2 y ≥ a
B1 x + B2 y = b
x ≥ 0, y quelconque.

2. Une entreprise produit trois (03) articles X, Y, Z. Ces articles sont

successivement traités par les machine A et B.
La marge unitaire sur coûts variables de X est de 5 DA ;
La marge unitaire sur coûts variables de Y est de 7 DA ;
La marge unitaire sur coûts variables de Z est de 9 DA.
Nous savons également que les temps de traitement de X, Y et Z par les
machines A et B sont les suivants :
X nécessite 2 heures de A et 5 heures de B ;
Y nécessite 4 heures de A et 2 heures de B ;
Z nécessite 6 heures de A et 3 heures de B.

34
Les machines A et B ne peuvent fonctionner plus de 24 heures par semaine.
1) Déterminer le programme hebdomadaire optimal.
2) L’entreprise peut louer les machines. Quel est le prix horaire le plus élevé
auquel elle peut louer les machines A et B ?

Solution :
1) Max W = 5x + 7y + 9z
2x + 4y + 6z ≤ 24
5x + 2y + 3z ≤ 24
x, y, z ≥ 0
En appliquant l’algorithme du simplexe, on obtient la solution :
( x = 3, y = 9/2 ) ; W = 93/2
Tableau optimal du programme primal
x y z a1 a2 b
y 0 1 3/2 5/16 - 1/8 9/2
x 1 0 0 - 1/8 1/4 3
W 0 0 3/2 25/16 3/8 93/2

2) Min (24 u + 24 v)
2u + 5v ≥ 5
4u + 2v ≥ 7
6u + 3v ≥ 9
u, v ≥ 0
Ce programme est le dual du précédent.
Par la méthode graphique, on obtient la solution : u = 25/16 ; v = 3/8.

35
En utilisant l’algorithme dual du simplexe, nous obtenons le tableau optimal
suivant :
u v a’1 a’2 a’3 b
u 1 0 1/8 - 5/16 0 25/16
v 0 1 - 1/4 1/8 0 3/8
a’3 0 0 0 3/2 -1 - 3/2
W 0 0 -3 - 9/2 0 93/2

3. Résoudre graphiquement le programme linéaire suivant :

Max (10x + 20y)
2x + y ≤ 9
x + 4y ≤ 8
Résoudre graphiquement le dual du problème.
Commentez.

4. Soit à maximiser la fonction :

Max (5 X1 + 4 X2 + 3 X3 + X4)
sous les contraintes :
X1 + X2 + X3 + X4 ≤ 12
3X1 + 2X2 + 3X3 + X4 ≤ 5
2X1 + X2 + X3 + 4X4 ≤ 7
X1, X2, X3, X4 ≥ 0
- Résoudre ce programme par la méthode du simplexe ;
- Donner, sans calcul, les résultats du programme dual correspondant.

Solution :
1) X1 = 0 ; X2 = 5/2 ; X3 = 0 ; X4 = 0 ; X5 = 19/2 ; X6 = 0 ; X7 = 9/2

36
2) On utilise les propriétés liant les solutions du primal avec celles du dual.
3) La première contrainte est redondante.

5. Soit le programme linéaire suivant :

Max Z = X1 – X2
2 X1 + 4 X2 ≤ 4
3 X1 + 5 X2 ≤ 15
X1, X2 ≥ 0
- Déterminer la solution optimale du problème.
- Ecrire le programme dual. Déduire sa solution à partir de la solution du primal.

Solution :
- La solution optimale du primal est :
(X1 = 2 ; X2 = 0) ; Z = 2.
- Programme dual :
Min W = 4 Y1 + 15 Y2
2 Y1 + 3 Y2 ≥ 1
4 Y1 + 5 Y2 ≥ -1
Y1, Y2 ≥ 0
En utilisant les propriétés liant les solutions du primal et celles du dual, on
obtient : (Y1 = ½ ; Y2 = 0) ; W = 2.

37
 Chapitre 4

La paramétrisation

Toute modification de la valeur des coefficients de la fonction objective (c j), des

seconds membres (b i) ou de la matrice A est susceptible de provoquer un
changement de solution. Les coefficients qui proviennent des documents
d’analyse sont sujet à caution ; ils ne peuvent être comme suffisamment exacts
pour garantir une solution idéale du problème.
Ces critiques ont conduit les mathématiciens à fournir un tableau plus complet
des solutions optimales admissibles en fonction des variables qui peuvent être
introduites grâce aux techniques de paramétrisation.

I. Paramétrisation des coefficients de la fonction objective

1) Exemple
Résoudre par la méthode du simplexe
Max Z = 3 X1 + 2 X2 + X3
X1 + 4 X2 ≤ 5
2 X1 + X2 + X3 ≤ 6
2 X1 + X3 ≥ 4
X1, X2, X3 ≥ 0

Après introduction des variables d’écart et d’une variable artificielle, on utilise

la méthode en M pour la résolution. Le programme linéaire s’écrit :

38
 Max Z = (3+2M) X1 + 2 X2 + (1+M) X3 – M X’3 – 4M
X1 + 4 X2 + X’1 = 5
2 X1 + X2 + X3 + X’2 = 6
2 X1 + X3 – X’3 + t = 4
X1, X2, X3, X’1, X’2, X’3, t ≥ 0

On obtient le tableau optimal suivant :

X1 X2 X3 X’1 X’2 X’3 b
X’3 0 5 0 1 1 1 7
X3 0 -3 1 -1 1 0 1
X1 1 4 0 1 0 0 5
j 0 7 0 2 1 0 16

La solution optimale est : (X1 = 5 ; X3 = 1 ; X’3 = 7) ; Z = 16.

2) Paramétrisation de la fonction objective

Rechercher suivant les valeurs de  comment varie la solution optimale lorsque
la fonction objective s’écrit :
Max Z = 3 (1+) X1 + 2 X2 + X3

On part de la solution optimale obtenue précédemment. La base étant constituée

de (X1, X3, X’3), on exprime Z en fonction des variables hors base.
X3 = 1 + 3 X2 + X’1 – X’2
X1 = 5 – 4 X2 – X’1
D’où :
Z = (7+12) X2 – (2+3) X’1 – X’2 + 16 + 15

39
La ligne des j devient :
0 7+12 0 2+3 1 0 16+15

Ce tableau est optimal si :

 (7+12) ≥ 0 et
 (2+3) ≥ 0.

II. Paramétrisation des coefficients des seconds membres des contraintes

On considère le programme linéaire précédent :

Max Z = 3 X1 + 2 X2 + X3
X1 + 4 X2 ≤ 5 (1+)
2 X1 + X2 + X3 ≤ 6
2 X1 + X3 ≥ 4
X1, X2, X3 ≥ 0

On peut soit résoudre ce problème directement, soit résoudre le programme

dual.
Pour éviter une longue discussion sur la valeur des paramètres, on préfère
résoudre le problème dual. En effet, dans le problème dual, ce sont les
coefficients de la fonction objective qui sont paramétrés.

Première méthode : Programme dual

Ecriture du programme dual :

40
 Min 5 (1+) λ1 + 6 λ2 – 4 λ3
λ1 + 2 λ2 – 2 λ3 ≥ 3
4 λ1 + λ2 ≥ 2
λ2 – λ3 ≥ 1
λ1, λ2, λ3 ≥ 0

A partir du tableau optimal précédent, on obtient la solution optimale du

programme dual :
λ’2 = 7 ; λ1 = 2 ; λ2 = 1 ;
Z = 16.
La base est fondée par (λ’2 , λ1 , λ2).
A partir du tableau optimal, on écrit les variables de base en fonction des
variables hors base :
λ’2 – 5 λ3 + 3 λ’3 – 4 λ’1 = 7
λ1 – λ3 + λ’3 – λ1 = 2
λ2 – λ3 – λ’3 = 1
Ecriture de Z en fonction des variables hors base :
Z = (7+5) λ3 + 5(1+) λ’1 + (1-5) λ’3 + 10  + 16.

41
Le tableau optimal du programme dual :
λ1 λ2 λ3 λ’1 λ’2 λ’3 b

λ2 0 1 -1 0 0 -1 1

λ1 1 0 -1 -1 0 1 2

λ’2 0 0 -5 -4 1 3 7
Z 0 0 -(7+5) -5(1+) 0 -(1-5) 10+16

La solution est optimale si :

 (7+5) ≥ 0 et,
 5(1+) ≥ 0 et,
 (1-5) ≥ 0.

Deuxième méthode : Résolution du programme primal

La solution optimale du problème sans paramètres :
X1 = 5 ; X3 = 1 ; X’3 = 7 ; et Z = 16.
On transforme les contraintes du problème initial de sorte qu’il n’y ait qu’une
variable de base par contrainte.
On obtient à partir de là un tableau « pseudo-optimal » pour lequel on applique
la méthode duale du simplexe.

III. Exercices

1. On considère le problème de la programmation linéaire :

Max z = ( 3 – m ) x1 + ( m – 3 ) x2 + x3
x1 + 2 x2 + 3 x3 ≤ 5
2 x1 + x2 + x3 ≤ 7
xi ≥ 0, i = 1,…,3.

42
a) Résoudre ce problème selon les valeurs de « m » ;
b) Pour m = 0, déterminer une solution optimale du problème dual si elle existe.

2. Une industrie dispose de trois machines M1¸ M2 et M3 pour produire trois

biens X1, X2 et X3. La production d’une unité du bien X1 exige 2h de
traitement dans la machine M1, 3h dans M2 et 1h dans M3. La production d’une
unité du bien X2 exige 1h dans M1, 3h dans M2 et 2h dans M3. Enfin, celle de
X3 : 1h dans M2 et 2h dans M3. Les heures disponibles sont respectivement :
6000, 9000 et 4000 pour M1, M2 et M3. Les profits unitaires sont de 10 DA
pour X1, 15 DA pour X2 et 5 DA pour X3. On vous demande d’étudier l’impact
des opérations suivantes sur la solution du programme :
1) De combien accroître le profit de X3 pour que cette activité devienne
rentable ?
2) Quelle activité entre dans la base si le profit de X1 s’accroît de 8 DA ?
3) De combien peut-on faire varier les heures disponibles de M3 sans changer la
solution optimale ?
4) De combien réduire le nombre d’heures de M3 consacrées à la fabrication du
bien X3 pour que cette activité devienne rentable ?

3. Résoudre le programme linéaire suivant :

Min C = 20 y1 + 30 y2
S/C
y1 + 2 y2 ≥ (7 + 2θ)
y1 + 2 y2 ≥ (12 + θ)
y1 + y2 ≥ (10 - θ)
y1, y2 ≥ 0

43
 Chapitre 5
Le problème de transport

I. Exemple de problème de transport

M1 M2 M3 M4 M5 b
U1 4 1 2 6 9 100
U2 6 4 3 5 7 120
U3 5 2 5 4 8 120
C 40 50 70 90 90

où :
U i : Usine i (source i);
M j : Magasin j (destination j) ;
C : Demandes des magasins en produit A ;
b : Quantités de ce produit disponibles pour chacune de ces usines ;
a i j : Coûts de transport unitaires de chacune des usines à chacun des magasins.

Enoncé du problème :
Quel est le programme de transport (c'est-à-dire l’ensemble des quantités
transportées de Ui à Mj ) qui minimise le coût total de l’opération en respectant
toutefois les contraintes liées à l’offre des usines et à la demande des magasins ?

II. Formulation et modélisation d’un problème de transport

Dans l’énoncé général d’un problème de transport (de quantités de mêmes
biens) de certaines sources à certaines destinations, trois (03) cas de figure
peuvent se présenter :
1) L’offre totale des sources ( ) est égale à la demande totale des
destinations ( );

44
2) L’offre totale excède la demande totale ;
3) La demande totale excède l’offre totale.
Compte tenu de ce que le premier cas se prête à un calcul simple, on peut
montrer :
- que l’expression générale du problème de transport se modifie quand il y a
égalité de l’offre et de la demande totales ;
- que les cas (2) et (3) peuvent se ramener au cas (1) par un procédé assez
simple.

1) Formulation du problème de transport général

Min
(1) ≤ Oi
(2) ≥ Dj

2) Cas où la demande totale est égale à l’offre totale :

L’hypothèse de l’égalité de l’offre et de la demande totales permet d’affirmer
que toutes les inégalités (1) et (2) sont en fait des égalités. Le problème primal
s’écrit :
Min
= Oi i
= Dj
yij ≥ 0

3) Exemple pratique
On va formaliser sous forme de programme linéaire le problème de transport
précédent en appelant yi j le nombre d’unités transportées de la source i à la
destination j. On voit que le problème comporte 15 inconnues positives ou

45
nulles, de façon à minimiser le coût global de transport en satisfaisant la
demande minimale de chaque magasin sans dépasser les offres des usines.
La traduction du problème de transport considéré est :

Min (4y11 + y12 + 2y13 + 6y14 + 9y15 + … + 4y34 + 8y35)

– y11 – y12 – y13 – y14 – y15 ≥ – 100
– y21 – y22 – y23 – y24 – y25 ≥ – 120
– y31 – y32 – y33 – y34 – y 35 ≥ – 120
y11 + y21 + y31 ≥ 40
y12 + y22 + y32 ≥ 50
y13 + y23 + y33 ≥ 70
y14 + y24 + y34 ≥ 90
y15 + y25 + y35 ≥ 90

On détermine le programme dual. La résolution de ce programme dual et

l’utilisation des relations entre solutions du primal et solutions du dual permet de
résoudre le programme primal.
Remarque : si on utilise l’algorithme dual du simplexe, le premier tableau
contiendra huit (08) variables de base et 23 colonnes.

III. La méthode « STEPPING STONE »

La solution du problème précédent peut s’obtenir par la méthode du simplexe,
mais étant donné l’aspect particulier du problème, on lui préfère une méthode
plus simple qui consiste à rechercher une solution de départ admissible qui sera
améliorée pour atteindre la valeur optimale de la fonction objective. C’est cette
méthode qu’on va utiliser, méthode appelée « stepping stone ».

46
La procédure commence par la recherche d’une solution de base. Il existe de
nombreuses méthodes pour trouver cette solution.
- Règle du Coin Nord Ouest (utilisée ici) ;
- Règle du meilleur CNO ;
- Règle du minimum de ligne.
Règle du CNO :
On prend le tableau initial des coûts, on le vide de ses coûts.
40 50 10 100
60 60 120
30 90 120
40 50 70 90 90

La solution de base est :

y11 = 40 ; y12 = 50 ; y13 = 10 ;
y23 = 60 ; y24 = 60 ;
y34 = 30 ; y35 = 90.
Z = 1550

Le tableau ci-dessus s’obtient comme suit : On considère le tableau des coûts, on

part du coin nord ouest de ce tableau. On affecte à cette case le plus petit
nombre représentant la disponibilité (100) et la demande (40). On porte donc 40
dans cette case. On complètera la première ligne jusqu’à la saturation de la
disponibilité. Quand la ligne est saturée, on passe à la ligne suivante, en restant
dans la même colonne et on recommence l’affectation … ainsi de suite. Nous
obtenons à la fin la solution de départ réalisable.
En partant de cette solution de base, on va chercher une nouvelle qui va donner
un coût global moindre mais qui contienne au moins (08) variables nulles.
Pour trouver cette solution, on va supposer que l’on affecte une unité dans la
case (1,4), il faut alors en retirer une de la case (1,3). On rajoute une dans (2,3),
47
on retranche une de la case (2,4). Cet échange circulaire d’une unité fait varier le
coût total d’une quantité 1,4. Cette quantité est évaluée à partir du tableau des
coûts unitaires.
On répète la même opération pour les autres ij. On obtient :
14 = 2 ; 22 = 2 ; 32 = 1 ;
15 = 1 ; 25 = -2 ; 33 = 4 ;
21 = 1 ; 31 = 1.
Les échanges qui font diminuer les coûts sont ceux pour lesquels les  sont
négatifs (dans ce cas 25). Au lieu de déplacer une seule unité, on déplace le plus
grand nombre possible. On considère pour cela dans le chemin la plus petite
quantité correspondant à une case où se trouve une quantité (-1). Le tableau
correspondant montre que c’est la case (2,4).
On porte 60 dans (2,5) qu’on va ôter de (2,4). On rétablit les disponibilités et les
demandes imposées. On obtient le tableau suivant :

40 50 10 100
60 120
90 30 120
40 50 70 90 90
Z = 1430
14 = 4 ; 15 = 3 ; 21 = 1 ; 22 = 2 ;
24 = 2 ; 31 = -1 ; 32 = -1 ; 33 = 2

10 50 40 100
30 90 120
90 120
40 50 70 90 90
14 = 3 ; 24 = 1 ;

48
15 = 3 ; 32 = 0 ;
21 = 1 ; 33 = 3 ;
22 = 2 ; 35 = 1.

Tous les ij sont positifs, le tableau est donc optimal.

Z = 1400 est une solution optimale dégénérée (car 32 = 0). Cette solution n’est
pas unique.

IV. Exercices

1. Résoudre le problème de transport donné par le tableau suivant :

b1 b2 b3 b4 ai
a1 1 2 3 4 12
a2 4 5 2 3 10
a3 1 3 2 1 10
bj 10 8 8 6

Où ai et bj représentent respectivement les quantités d’un produit disponible au

site i et la quantité demandée par le lieu de vente j. Les éléments du tableau sont
les coûts de transport du site i au lieu de vente j. Ecrire le problème dual
correspondant.

2. Résoudre le problème de transport donné par le tableau suivant :

b1 b2 b3 b4 ai
a1 4 2 3 5 14
a2 4 5 2 3 11
a3 1 3 2 1 10
bj 10 8 8 6

49
Où a i et b j représentent respectivement les quantités d’un produit disponible au
site i et les quantités demandées par le lieu de vente j. Les éléments du tableau
sont les coûts de transport du site i au lieu de vente j.

3. On considère trois centrales électriques de capacité de production respectives

700, 400 et 500 mégawatt. Ces centrales desservent deux villes dont les besoins
en électricité sont de 800 mégawatt chacune. Chaque centrale peut fournir tout
ou partie de sa production à chacune des villes.
Les coûts d’acheminement (par mégawatt) dans le réseau électrique sont donnés
par le tableau suivant :

Ville 1 Ville 2
Centrale 1 20 25
Centrale 2 15 10
Centrale 3 10 15

Le problème est de subvenir aux besoins des villes à moindre coût. Modéliser le
problème sous forme d’un programme linéaire.

4. Une entreprise de construction d’automobiles possède 3 usines U1, U2 et U3.

Elle a besoin d’acheminer les métaux nécessaires à partir des ports P1 et P2.
Les usines U1, U2 et U3 nécessitent hebdomadairement 400 tonnes, 300 tonnes
et 200 tonnes respectivement. Les ports P1 et P2 peuvent fournir respectivement
550 tonnes et 350 tonnes.
Les coûts de transport sont donnés (en kilo-$ par tonne) dans le tableau suivant :
Usine 1 Usine 2 Usine 3
Port 1 5 6 3
Port 2 3 5 4

50
Donner une modélisation de ce problème de transport de manière à satisfaire la
demande à partir des quantités disponibles et en minimisant les coûts de
transport.

5. Soit le problème de transport suivant :

1) Utiliser la méthode du coin nord-ouest (CNO) afin de proposer un plan de

transport réalisable à ce problème ;
2) Le plan de transport proposé est-il optimal ? (Utiliser l’algorithme du
Stepping Stone pour répondre à la question) ;
3) Si la réponse à la question (2) est non, proposer un plan de transport optimal.

6. Soit le plan de transport suivant, obtenu par la méthode du Coin Nord-Ouest :

1) Cette solution est-elle optimale ?

2) Si la réponse à la question (1) est non, quel doit être le plan de transport à
moindre frais ?

51
 Chapitre 6
La programmation linéaire en nombres
entiers

I. Introduction
Soit le problème de programmation linéaire suivant :
I. Max C X
AX≤b
X≥0

Un problème de programmation linéaire en nombres entiers s’écrit :

II. Max C X
AX≤ b
XϵN

On parle d’un programme linéaire mixte en variables mixtes si parmi les

variables, certaines sont entières et les autres non.

Exemple :
Max
≤ bi
X1, X2 ≥ 0 ; X3, X4 ϵ N

Pour un problème de maximisation, la solution du programme linéaire est

supérieure à la solution du programme linéaire en nombres entiers.
Lors de la résolution d’un programme linéaire en nombres entiers (PLE), on
commence d’abord par résoudre le programme sans tenir compte des conditions
d’intégrité. Il se peut que la solution obtenue soit entière. Si elle n’est pas
entière, on est assuré que la valeur de la fonction objective associée à cette

52
solution (non entière) est une borne supérieure pour la valeur de la fonction à
l’optimum du problème posé.
Pour déterminer cette solution, on peut utiliser l’une des deux méthodes
suivantes :
- Méthode des troncatures ;
- Méthode Branch and Bound.

II. Méthode des troncatures

Après introduction des variables d’écart, le problème (II) va s’écrire :
Max
+ = bi

Remarque :
Il faudrait rendre entiers avant l’utilisation de l’algorithme et surtout
avant l’introduction des variables d’écart (pour les rendre entiers).
Pour cela, il suffirait quand c’est nécessaire de multiplier les deux membres des
contraintes par des nombres suffisamment grands.

Exemple :
Le principe et l’appellation seront développés sur le problème suivant :
Max C1 X1 + C2 X2
a11 X1 + a12 X2 + X’1 = b1
a21 X1 + a22 X2 + X’2 = b2 (aij, bi )
X1, X2, X’1, X’2 ϵ N
Supposons que la résolution sans tenir compte des conditions d’intégrité est
résumée dans le tableau – optimal – suivant :

53
 X1 X2 X’1 X’2 b
X1 1 0 a’11 a’12 B1 (1)
X2 0 1 a’21 a’22 B2 (2)
0 0 y1 y2 Z

Deux cas se présentent :

1) Si B1 et B2 sont entiers alors c’est la solution optimale ;
2) On suppose que B1 n’est pas entier, par exemple :
B1 = I + F
avec :
I : partie entière ;
F : partie fractionnelle et F ≥ 0
(exemple : 17/5 = 5 + 2/3)
On considère la première contrainte du tableau final :
(1) X1 + a’11 X’1 + a’12 X’2 = B1 = I + F
On décompose a’ i j en I et F :
a’ i j = I’ i j + F’ i j avec F’ i j ≥ 0
(1) va s’écrire :
F’11 X’1 + F’12 X’2 = (I – I’11 X’1 – I’12 X’2 – X1) + F (2)
I’’ ϵ N
(2) s’écrit:
F’11 X’1 + F’12 X’2 = I’’ + F
F’11 X’1 + F’12 X’2 ≥ F (3)

(1) se transforme en (3), qui est l’expression de la troncature déduite du

caractère non entier de B1.
On introduit dans la relation (3) (devenue une contrainte ajoutée au problème
initial) une variable d’écart X’3.

54
Puis on l’introduit dans le tableau optimal précédent et on utilise la méthode
duale du simplexe pour résoudre le problème.

X1 X2 X’1 X’2 X’3

X1 1 0 a’11 a’12 0 B1
X2 0 1 a’21 a’22 0 B2
X’3 0 0 - F’11 - F’12 1 -F
0 0 y1 y2 0 Z

Exemple pratique :
Max (5X1 + X2)
4 X1 + X2 ≤ 14
X1, X2 ϵ N
Les coefficients aij et bi sont entiers, on résout le problème sans tenir compte
des conditions d’intégrité.
Tableau 1 :
X1 X2 X’1 b
X’1 4 1 1 14
-5 -1 0 0

Tableau 2 :
X1 X2 X’1 b
X1 1 1/4 1/4 7/2
0 1/4 5/4 17,5

La solution obtenue n’est pas optimale (X1 = 7/2) car elle n’est pas entière.
X1 + ¼ X2 + ¼ X’1 = 7/2 = 3 + ½ .
¼ X2 + ¼ X’1 = (3 – X1) + ½ .
¼ X2 + ¼ X’1 ≥ ½ ⇒ X2 + X’1 ≥ 2 (1)
55
(1) ⇒ – X2 – X’1 + X’2 = – 2

X1 X2 X’1 X’2 b
X1 1 1/4 1/4 0 7/2
X’2 0 -1 -1 1 -2
Z 0 1/4 5/4 0 35/2

Max j [ ; ˂ 0] = – ¼

X2 va entrer dans la base en remplacement de X’2

X1 X2 X’1 X’2 b
X1 1 0 0 1/4 3
X2 0 1 1 -1 2
Z 0 0 1 1/4 17

Ce tableau est optimal.

La solution est : (X1 = 3 ; X2 = 2) ; Z = 17.

III. Méthode de BRANCH and BOUND

Les algorithmes de Branch and Bound sont des procédures d’énumération
partielle pour résoudre des problèmes en variables entières et variables mixtes.
Ils consistent en des méthodes de résolution itératives.

Exemple :
Max Z = 8 X1 + 5 X2 + 7X3
1,5 X1 + 3 X2 ≤5
X1 + 7 X2 + 2 X3 ≤ 24
X1 ϵ N, X2, X3 ≥ 0

56
La résolution de ce problème sans tenir compte de la condition d’intégrité nous
donne la solution suivante :
X1 = 10/3 ; X2 = 0 ; X3 = 31/3 ; Zs = 99.
Compte tenu de la condition d’intégrité de X1, on va chercher une autre solution
(Z I) telle que X1 ϵ N.
X1 est la variable qui pose problème car elle n’est pas entière.
On commence à effectuer les branchements.
X1 ≤ 10/3 ⇒ X1 ϵ {1, 2, 3}
X1 ≤ 3
X1 ≥ 4 i.e. X1 ∉ ] 3, 4 [
On aura donc deux nouvelles contraintes dans le problème initial et comme
celles-ci sont incompatibles, elles vont générer chacune un problème.

Problème initial
I. Problème nouveau (X1 ≥ 4) II. Problème nouveau (X1 ≤ 3)
Max (8 X1 + 5 X2 + 7 X3) Max (8 X1 + 5 X2 + 7 X3)
1,5 X1 + 3 X2 ≤ 5 1,5 X1 + 3 X2 ≤ 5
X1 + 7 X2 + 2 X3 ≤ 24 X1 + 7 X2 + 2 X3 ≤ 24
X1 ≥ 4 X1 ≤ 3
X1 ϵ N, X2, X3 ≥ 0 X1 ϵ N, X2, X3 ≥ 0
Règle d’arrêt : Z S ≤ Z I Règle d’arrêt : Z S ≤ Z I

Remarque : Dans un problème de minimisation, la règle d’arrêt est : Z S ≥ Z I

Dans cet exemple, le problème (I) n’a pas de solution car les contraintes (1) et
(3) sont incompatibles. On passe alors à la résolution du problème (2).

57
On part du tableau optimal du problème initial auquel on ajoute la contrainte
X1 ≤ 3.
X1 X2 X3 X’1 X’2 b
X1 1 2 0 2/3 0 10/3
X3 0 5/2 0 - 1/3 1/2 31/3
Z 0 57/2 0 3 7/2 99

X1≤ 3 ⇒ X1 + Y1 = 3 ; Y1 est une variable d’écart.

On introduit cette nouvelle contrainte.
X1 = 10/3 – 2 X2 – 2/3 X’1
X1 + Y1 = 10/3 – 2 X2 – 2/3 X’1 + Y1 = 3 ⇒
– 2 X2 – 2/3 X’1 + Y1 = – 1/3.

On obtient le tableau suivant :

X1 X2 X3 X’1 X’2 Y b
X1 1 2 0 2/3 0 0 10/3
X3 0 5/2 1 - 1/3 1/2 0 31/3
Y1 0 -2 0 - 2/3 0 1 - 1/3
Z 0 57/2 0 3 7/2 0 99

X1 X2 X3 X’1 X’2 Y b
X1 1 0 0 0 0 1 3
X3 0 7/2 1 0 1/2 - 1/2 21/2
X’1 0 3 0 1 0 - 3/2 1/2
Z 0 39/2 0 0 7/2 9/2 195/2

On obtient la solution suivante :

58
X1 = 3 ; X2 = 0, X3 = 21/2
Z = 195/2.
C’est donc la solution optimale de sorte qu’il n’est pas nécessaire d’effectuer
d’autres branchements.
Remarque : Le choix entre la méthode des troncatures et la méthode de Branch
and Bound dépend des cas étudiés.

IV. Exercices
1. En appliquant la méthode appropriée, résoudre le programme linéaire en
nombre entiers suivant :
Max Z = 3 x1 + 2 x2
- x1 + x2 ≤ 1
x1 + 2 x2 ≤ 10
7 x1 + 2 x2 ≤ 28.
x1 ∈ N, x2 ∈ N

Solution :
x1* = x2* = 3 et Z* = 15.

2. Montrer que le programme linéaire suivant n'a pas de solutions :

Min Z = 3 x1 + 2 x2
x1 ≤ 3/2
2 x2 ≤ 5/3
5 x1 + 6 x2 ≥ 15.
x1 ∈ N, x2 ∈ N

59
 Chapitre 7
Théorie des graphes

La théorie des graphes est une branche de la théorie des ensembles. Elle
constitue une méthode de la recherche opérationnelle qui permet de résoudre
certains problèmes de nature combinatoire apparaissant dans les domaines
économiques, sociologiques…

I. Définitions principales de la Théorie Générale des Graphes (TDG)

1) Notion de graphe
X = (x1…xn), ensemble dénombrable ;
Γ : application multivoque.
Le couple G=(X, Γ) constitue un graphe d’ordre n.
Un graphe G peut être représenté à l’aide d’une représentation sagitale.

Les éléments xi (i = 1,3) sont les sommets du graphe ;

La flèche reliant deux sommets forme un arc ;
L’ensemble des arcs détermine l’application du graphe
G =(X, Γ) = (X, U).
On représente souvent les graphes sous la forme de matrice.

60
M = (a i j) i = 1, n
J = 1, n

avec a i j =

Exemple :
1 2 3
1 0 1 1
2 1 0 0
3 0 1 1

Cette matrice M définit entièrement le graphe

2) Concepts orientés
Soit U = (x i, x j) un arc du graphe alors :
x i : extrémité initiale ;
y j : extrémité terminale.

a) Chemin :
On appelle chemin dans un graphe, une succession d’arcs  = (u1, u2, …up) où
l’origine d’un arc est l’extrémité du précédent.
Désignation :  = (x1, x2… xp)
La longueur du chemin  est la quantité l () telle que l() est égale au nombre
d’arcs formant le chemin .
Un chemin peut être fini ou infini.
Chemin simple : un chemin est dit simple s’il n’emprunte jamais deux fois le
même arc.

61
Chemin élémentaire : un chemin est dit élémentaire s’il ne passe jamais deux
fois par le même sommet.

b) Circuit :
Le circuit est un chemin fini  = (x1… x k) dont le sommet initial x1 se confond
avec le sommet terminal x k.
Un circuit est dit élémentaire s’il ne passe jamais deux fois par le même point (à
l’exception de l’origine et de l’extrémité qui coïncident) ;
Un circuit de longueur unité formé par un arc (xi xi) est une boucle.

c) Un chemin ou circuit qui passe une fois et une seule par chaque sommet du
graphe est appelé Hamiltonien.

d) Sous graphe d’un graphe G = (X, U) : est un graphe de la forme (A, V) où :

A : partie de X.
V : ensemble des arcs de U ayant les deux extrémités dans A.

e) Graphe partiel :
Un graphe partiel G0 par rapport au graphe G est un graphe ne contenant qu’une
partie des arcs du graphe G.
Exemple :
Le réseau routier constitué par les routes nationales est un graphe partiel du
graphe G ; G représentant le réseau routier du territoire algérien.

f) Graphe complet :
Un graphe est complet si tout couple de sommets est relié dans au moins une des
deux directions.
xi xj i≠j (xi xj) ∉ U ⇒ (xj xi) ∈ U.

62
g) Graphe symétrique et graphe antisymétrique :
Un graphe G est symétrique si : xi, xj,
(xi, xj) ∈ U ⇒ (xj, xi) ∈ U.
Un graphe G est antisymétrique si : xi, xj,
(xi, xj) ∈ U ⇒ (xj, xi) ∉ U.
Un graphe antisymétrique ne peut contenir une boucle.

h) Graphe fortement connexe :

Un graphe est fortement connexe si xi, xj, , il existe un chemin de
xi à xj.
Une condition pour qu’il existe un chemin Hamiltonien est que le graphe soit
fortement connexe.

3) Concepts non orientés

Il y a des cas où considérant un graphe, on fait abstraction de l’orientation des
arcs. On parle alors de graphe non orienté.
Pour un graphe non orienté, les notions d’arcs, de chemin ou de circuit cèdent la
place à celles d’arrête, de chaîne et de cycle.

a) Arrête :
On appelle arrête d’un graphe un ensemble de deux éléments (xi, xj) tels que :
(xi, xj) ∈ U et/ou (xj, xi) ∈ U. xi xj

b) Chaîne :
Une chaîne est une succession d’arrêtes u1, u2… un. Chaque arrête uk est
rattachée à uk-1 par une de ses extrémités et à uk+1 par l’autre.

63
Une chaîne simple est une chaîne où les arrêtes utilisées sont toutes différentes.
Dans le cas contraire, la chaîne est dite composée.
Une chaîne est élémentaire si elle ne rencontre pas deux fois le même sommet.

c) Cycle :
Un cycle est une chaîne finie qui part d’un sommet et finit dans ce sommet.
Un cycle est élémentaire si tout sommet se trouvant sur ce cycle n’est rencontré
qu’une seule fois (sauf l’origine et l’extrémité).

d) Graphe connexe :
Un graphe est connexe si deux quelconques de ses sommets sont reliés par une
même chaîne. i.e. :
xi xj (xi ≠ xj), il existe une chaîne allant de xi vers xj.

II. Problème du chemin de valeur optimale

1) Position du problème
Dans sa forme générale, le problème de valeur optimale sur un graphe s’énonce
comme suit : Etant donné un graphe G où à chaque arc U est associé un nombre
l(u) appelé valeur de l’arc U ou longueur de U. On cherche un chemin  allant
de x0 à xn tel que la valeur totale ∈ soit :
 Aussi petite que possible dans le cas d’un problème de chemin de valeur
minimale ;
 La plus grande possible dans le cas d’un chemin de valeur maximale.
Suivant le cas, cette valeur l(u) peut être un coût, un temps, une longueur.

2) Algorithme de Ford.
Pour résoudre ce problème, il existe plusieurs algorithmes (FORD, DANZIG,
BELLMAN, KELLABA…).

64
L’algorithme de Ford consiste en ces étapes :

1ère étape :
On associe à chaque sommet xi un indice λi.
Pour le chemin de valeur minimale, on pose :
λ0 = 0 (le point de départ)
et λi = + (pour les autres sommets).
Pour le chemin de valeur maximale, on pose :
λ0 = 0
et λi = 0

2e étape :
On modifie successivement les nombres de départ λi. Cette modification
s’effectuant en choisissant un arc (xi, xj) tel que :
λj - λi pour le chemin de valeur minimale (C. V. Min).
λj - λi pour le chemin de valeur maximale (C.V. max).
On remplace ensuite λj par la nouvelle valeur λ’j= λi + l (xi xj)

3e étape :
Quand, après un certain nombre d’ajustements, il n’est plus possible de modifier
les λi,, les valeurs inscrites sur chaque sommet xi donnent la longueur extrême
entre l’origine x0 et xh.
λh : longueur du chemin x0 xh

4e étape :
Pour retrouver le chemin allant de x0 à xh, on relève le sommet xi1 tel que :
λh – λi1 = l(xi1, xh).

65
xi1 est le dernier sommet utilisé pour déterminer λh … puis xi2 tel que :
λi1 – λi2 = l(xi2, xi1) ;
De proche en proche, on obtient x0 = xi k+1 et le chemin cherché est :
 = (x0, xik, … xi1, xh).

Exemple :
Rechercher sur le graphique suivant le chemin de valeur optimale.

1. Le chemin de valeur minimale

 = (x0 x1 x2 x3 x5)
l() = 2+1+3+1 = 7
2. Le chemin de valeur maximale
 = (x0 x1 x3 x4 x5)
l() = 18

3) Algorithme de DANTZIG
On numérote d’abord les sommets de x0 à xn-1 (x0 étant l’origine et xn-1
l’extrémité du chemin cherché) et l’on appelle λj la valeur minimale du chemin
entre x0 et xj.
1) Poser : λ0 = 0 et E1 = {x0};

66
2) A toute étape k 2 du problème, associer à chacun des sommets x i des k
sommets marqués (i.e. les sommets dont les λi sont déterminés), le sommet
xi*∉ Ek, tel que l(xi, xi*) soit minimale.
3) Déterminer le sommet xp ∈ Ek, tel que :

λp + l(xp, xp* ) = mini [λi + l(xi, xi )]

4) Poser : Ek+1 = Ek {xp*} = Ek {xq}

et λq = λp + V( xp, xq).
Revenir à l’étape 2, jusqu’à ce que λn-1 soit déterminé.

Revenir à 2, jusqu’à ce que λn-1 soit déterminé.

Exemple :

1) λ0 = 0 et E1 = }x0{


2) min x0 ϵ {x-E1} l(x0 x0) = l(x0 x1) = 3,
d’où λ1 = 0 + 3 = 3 et E2 = {x0, x1} ;


3) min x0 ϵ {x-E2} l(x0 x0) = l(x0 x3) = 6,

min x1 ϵ {x-E2} l(x1 x1) = l(x1 x3) = 2,

67
puis : min { λ0 + l(xo x3) ; λ1 + l(x1 x3) } = min {6, 5} = 5
d’où :
λ3 = 5 et E3 = {x0 x1 x3}.


4) min x0 ϵ {x-E3} l(x0 x0) = l(x0 x2) = 8,

min x1 ϵ {x-E3} l(x1 x1) = l(x1 x4) = 6,

min x3 ϵ {x-E3} l(x3 x3) = l(x3 x2) = 2,

puis : min { λ0 + l(x0 x2) ; λ1 + l(x1 x4) ; λ3 + l(x3 x2) } = min {8, 9, 7} = 7
d’où : λ2 = 7 et E4 = { x0 x1 x3 x2}.


5) min x1 ϵ {x-E4} l(x1 x1) = l(x1 x4) = 6,

min x2 ϵ {x-E4} l(x2 x2) = l(x2 x4) = 1,

min x3 ϵ {x-E4} l(x3 x3) = l(x3 x5) = 7,

puis : min { λ1 + l(x1 x4) ; λ2 + l(x2 x4) ; λ3 + l(x3 x5) } = min {9, 8, 12} = 8
d’où : λ4 = 8 et E5 = { x0 x1 x3 x2 x4}.

6) Enfin :

min x3 ϵ {x-E5} l(x3 x3) = l(x3 x5) = 7,

min x4 ϵ {x-E5} l(x4 x4) = l(x4 x5) = 1,

puis : min { λ3 + l(x3 x5) ; λ4 + l(x4 x5) } = min {12, 10} = 10

d’où : λ5 = 10.

L’algorithme de DANTZIG est évidemment fini ; il procède par sous-chemins

optimaux et assure l’obtention du chemin de valeur minimale cherché lorsqu’on
arrive à xn-1.

68
Question : Comment appliquer l’algorithme de DANTZIG au problème du
chemin de valeur maximale ?

III. Problèmes d’ordonnancement

1) Introduction
On dit qu’on a affaire à un problème d’ordonnancement lorsqu’en vue de la
réalisation d’un objectif quelconque, il faut accomplir de multiples tâche, elles
mêmes soumises à un ensemble de contraintes.
Les contraintes auxquelles sont soumises les diverses tâches qui concourent à la
réalisation de l’objectif sont de divers types. On distingue :
 Les contraintes du type potentiel
o Contraintes de localisation temporelle (La tâche i ne doit pas
commencer avant telle date…)
o Contraintes de succession.
 Les contraintes du type disjonctif (Exemple : les deux tâches i et j ne
peuvent être réalisées simultanément) ;
 Les contraintes du type cumulatif. Elles concernent l’évolution dans le
temps du volume total des moyens humains et matériels consacrés à
l’exécution des tâches (Il est difficile de tenir compte de telles
contraintes).
Au sens mathématique, résoudre un problème d’ordonnancement, c’est en
déterminer une solution quelconque ; au sens de la recherche opérationnelle,
c’est choisir, parmi toutes les solutions, la solution optimale, par rapport à un
critère fixé à l’avance.
Méthodes de résolution :
Les méthodes de résolution sont nombreuses et diverses. On peut citer :
- Planning à barres, dit graphique de GANTT (utilisé jusqu’en 1958).
- Méthodes fondées sur la théorie des graphes :

69
 o La méthode Américaine CPM (Critical Path Method), avec sa
variante, incluant d’éventuelles données aléatoires, PERT (Program
Evaluation and Review Technique ou Program Evaluation Research
Task);
o La méthode française des potentiels

Ces méthodes permettent :

1/ d’établir un ordonnancement, dès l’instant qu’aucune contrainte n’est
contradictoire avec une autre ;
2/ de déterminer le meilleur temps total nécessaire à la réalisation de l’objectif ;
3/ de déterminer les tâches critiques, i.e. celles dont l’exécution ne peut être ni
retardée ni ralentie, sans que la fin de l’ensemble des travaux ne soit décalée du
temps correspondant.

2) Méthode Américaine
Pour utiliser la méthode américaine, on construit un graphe orienté, sans boucle,
dont les sommets constituent les évènements (étapes de la réalisation où
objectifs intermédiaires) et les arcs représentent les opérations (tâches
élémentaires en lesquelles on a décomposé le processus de réalisation de
l’objectif final).
Les arcs étant valués par les délais d’exécution, il sera aisé, au moyen d’un
algorithme approprié, de rechercher le chemin de valeur maximale dans le
graphe et d’obtenir ainsi le chemin critique.

Exemple :
Un éditeur veut passer commande d’un ouvrage technique à un écrivain
scientifique. Les opérations à accomplir sont indiquées dans le tableau ci-après,
avec leurs durées et la mention des opérations qui doivent précéder chacune
d’entre elles.

70
 Opérations Durée en Opérations
15 jours antérieurs
a Approbation du plan de l’ouvrage 1 Néant
b Signature du contrat 1 a
c Remise du manuscrit 12 b
d Approbation du comité de lecture 2 c
e Composition du texte 3 d
f Correction par les correcteurs de l’imprimerie 1 e
g Clichage et tirage des hors textes 3 d
h Exécution des dessins des figures 4 d
i Révision des dessins par l’auteur 1 h
j Correction des dessins clichage des figures 2 i
k Première correction des épreuves par l’auteur 2 f
l Exécution des premières corrections à l’imprimerie 1 k
m Seconde correction des épreuves par l’auteur, indication de
l’emplacement des clichés, approbation des hors textes 2 g, j, l
n Exécution des secondes corrections à l’imprimerie, mise en
pages 1 m
o Tirage du livre 2 n
p Etablissement de la prière d’insérer, des listes d’exemplaires
de presse et d’hommage 1 m
q Pliage 1 o
r Brochage 1 q
s Reliure de certains exemplaires 2 q
t Impression de la prière d’insérer 1/2 p
u Envoi des exemplaires de presse 1/4 r et t
v Envoi des hommages 1/8 s et t
w Envoi des contingents aux libraires. 1/2 r et s

71
Pour établir le diagramme de la méthode, il convient de définir les évènements
qui en formeront les sommets :
0 : début des opérations ;
1 : plan approuvé ;
2 : contrat signé ;
3 : manuscrit remis ;
4 : manuscrit approuvé ;
5 : texte composé ;
6 : texte corrigé par l’imprimerie ;
7 : premières épreuves corrigées par l’auteur ;
8 : dessins exécutés ;
9 : dessins revus par l’auteur ;
10 : premières corrections exécutées par l’imprimerie, secondes épreuves tirées,
clichage terminé pour les figures, impression pour les hors textes…
…
22 : achèvement des opérations.

On obtient le diagramme ci-après :

72
73
Le diagramme obtenu, sans boucle, est aussi sans circuit ; il réalise donc un
ordonnancement dans lequel les contraintes de succession ne sont pas
contradictoires.
Pour déterminer les dates attendues des divers évènements, il suffit d’examiner
pour tout sommet (évènement) la date la plus proche de réalisation (date
attendue). Lorsqu’il existe plusieurs chemins entre deux points, la date attendue
est évidemment celle qui est obtenue en suivant le chemin de valeur la plus
grande.

Exemple :
L’impression des hors textes (g) peut être achevée à 16+3=19, mais l’évènement
n° 10 n’aura lieu que lorsque les opérations (h, i et j) ainsi que (e, f, k, l) seront
accomplies.
L’exemple étant particulièrement simple, il est facile d’obtenir la date attendue
de l’achèvement des opérations, soit 31 ½.
Le chemin critique est le chemin jalonné par les évènements (dits critiques) dont
la date attendue est égale à la différence entre la date attendue de l’évènement
suivant, sur le chemin critique, et la valeur de l’arc qui les relie (voir exemple).
Tout arc dont la suppression rendrait le graphe de la méthode américaine non
connexe fait partie du chemin critique (exemple : l’une quelconque des
opérations « a » à « d », l’opération « m »).

3) Méthode française des potentiels

La méthode des potentiels ne nécessite aucune définition d’évènement, ni aucun
tracé de graphe.
La méthode consiste à dresser un tableau, dans lequel chaque opération (prise
dans un ordre quelconque) est dotée d’une colonne et d’une sous-colonne et à
considérer deux évènements : le début, D, et l’achèvement f, des opérations.

74
Dans chacune des colonnes, on écrit les opérations qui doivent précéder celle
qui est indiquée en tête de colonne ; on indique aussi la durée de ces opérations
préalables. Quand une opération n’est précédée par aucune autre, et si elle peut
commencer dès le démarrage de l’ensemble, on écrit D et l’on indique alors 0, à
côté de D.
Une fois cette opération effectuée, on écrit 0, en face de D, dans la sous colonne
correspondant aux opérations qui comportent un D. Comme il y a surement au
moins une opération qui comporte un D et seulement un D dans sa colonne, on a
immédiatement une colonne « complète », i.e. dont la colonne et la sous-colonne
sont remplies : on fait la somme des chiffres inscrits dans la colonne et la sous
colonne et l’on obtient : 0 + 0 = 0 ; on en déduit que la date de début de
l’opération « a » est 0 et l’on écrit cette valeur en tête de colonne. Ensuite,
partout où apparait un « a », on marquera 0 dans la sous-colonne
correspondante. Ici, dans la colonne b. On a une nouvelle colonne « complète »
et l’on inscrit 0 + 1 = 1 en tête de colonne, et ainsi de suite (voir tableau ci-
après)

75
Tableau

Op 0 a 1 b 2 c 14 d 16 e 19 f 16 g 16 h 20 i 21 j 20 k 22 l
pré 0 D :0 0 a :1 1 b :1 2 c :12 14 d :2 16 e :3 14 d :2 14 d :2 16 h :4 20 i :1 19 f :1 20 k :2

23 m 25 n 26 o 25 p 28 q 29 r 29 s 26 t 30 u 31 v 31 w 31 1/2f
16 g :3 23 m :2 25 n :1 23 m :2 26 o :2 28 q :1 28 q :1 25 p:1 29 r :1 26 t :1/2 29 r :1 30 u :1/4
21 j :2 26 t :1/2 29 s :2 29 s :2 31 v :1/8
22 l :1 31 w :1/2

76
On arrive, fatalement, à une colonne où figurent plusieurs opérations préalables.
Lorsque la colonne est « complète », au sens ci-dessus, on fait les additions des
nombres inscrits sur la même ligne dans la colonne et la sous colonne et l’on
inscrit, on tête de colonne, le maximum des résultats obtenus. Ainsi, pour la
colonne m, on a, sur la ligne g : 16 + 3 = 19, sur la ligne j : 21 + 2 = 23 et sur la
ligne l : 22 + 1 = 23. On inscrit donc 23 en tête de colonne. 23 est la date la plus
proche à laquelle peut commencer l’opération « m ».
En continuant ainsi, on arrive à marquer la colonne f ; le nombre qui est indiqué
en tête de cette colonne indique la date la plus proche d’achèvement de
l’ensemble des opérations. Pour trouver le chemin critique, il suffit de reprendre
dans le tableau, et en partant de la fin, les opérations enchaînées dont la ligne a
fourni le nombre indiqué en tête de colonne. Ainsi, dans la colonne f, c’est w ;
dans la colonne w, c’est s ; dans la colonne s, c’est q … etc.

IV. Autres applications de la Théorie des graphes

La théorie des graphes comporte de nombreuses autres applications. Nous en
exposons brièvement les plus connues.

1) Problèmes de flot maximal à travers un réseau

On appelle réseau de transport un graphe sans boucle, comportant une
entrée X0 et une sortie Xn, dont les arcs sont valués par des nombres
représentant la capacité de transport de chaque arc.
Le problème à résoudre, dans un réseau de transport, consiste, en général, étant
données des quantités disponibles en X0, à en acheminer le maximum jusqu’à
Xn , compte tenu des capacités de transport.
Les capacités de transport peuvent représenter des tonnages disponibles sur des
bateaux, des camions, des wagons, ou encore des débits dans des oléoducs,
canalisations, voies de transmission…

77
Exemple :
Soient A, B, C, trois châteaux d’eau alimentant 4 villages D, E, F et G. Les
capacités respectives des châteaux sont 45 l/s, 25 l/s, 20 l/s. Les débits (ou
capacités) respectifs de chaque canalisation, en l/s, est mentionné sur la figure.
Les besoins respectifs de chaque village sont en l/s : 30 l/s, 10 l/s 20 l/s, 30 l/s.
Le problème consiste à établir la meilleure alimentation possible et déterminer,
s’il y a lieu, entre quels points il importe de construire des canalisations
supplémentaires.

l(OA, OB, OC) : disponibilités respectives de A, B, C.

l(DS, ES, FS, GS) : besoins respectifs en D, E, F et G
Le problème est de faire passer le flot maximal entre O et S.
Pour résoudre ce problème, on peut employer l’algorithme de FORD-
FULKERSON.

2) Problèmes d’affectation
Une administration désire procéder aux mutations des fonctionnaires A, B, C, D
et E et leur offre les postes a, b, c, d, e. Ces fonctionnaires désirant maximiser
leurs satisfaction générale, décident d’effectuer chacun un classement des postes
offerts et obtiennent le tableau suivant regroupant leurs avis.

78
 a b c d e
A 1 2 3 4 5
B 1 4 2 5 3
C 3 2 1 5 4
D 1 2 3 5 4
E 2 1 4 3 5

Pour maximiser la satisfaction générale, il faut choisir un chiffre et un seul par

ligne et par colonne, de manière que la somme des cinq chiffres choisis soit
minimale (min 5).

3) Problème du voyageur de commerce (Recherche arborescente)

Un voyageur de commerce doit visiter de nombreuses villes et revenir à son
point de départ. Si l’on dispose de la matrice des coûts de transport de ville à
ville (qu’on pourra supposer non symétrique pour corser le problème), le
voyageur de commerce cherche le circuit Hamiltonien de valeur minimale.

Exemple :
Un voyageur de commerce demeurant dans la ville A désire se rendre une fois et
une seule fois dans les villes B, C, D, E et F, avant de revenir chez lui. La
matrice des coûts (parfois de longueur) est donnée ci-après (les tirets remplacent
des valeurs infinies), il s’agit évidemment de déterminer, parmi les 120 circuits
Hamiltoniens, celui de valeur minimale.

79
 A B C D E F
A - 6 7 3 1 3
B 7 - 8 2 9 7
C 5 10 - 10 1 7
D 8 6 5 - 5 1
E 7 7 6 7 - 4
F 9 8 8 5 3 -

V. Exercices

1. Trouver dans le graphe ci-dessous : les chemins, les circuits Hamiltoniens.

A B

2. On donne le graphe ci-dessous et l’on demande d’appliquer l’organigramme

correspondant à la recherche du chemin minimal, par l’algorithme de Ford, entre
X0 et X5.
Détailler, sous forme de tableau, les opérations logiques et numériques
impliquées par l’organigramme.

80
Solution :
Organigramme

81
 λ0 = 0
λi = (i > 0)
i=0
j=1

Non
L’arc xi xj existe-t-il ?

Oui

λj – λi > l(xi xj) ?

Oui

λi + l(xi xj) → λj

Oui
i>j?
i

i=j j+1→ j
Raz j

Non
j > n?
i Oui

Raz j
i + 1→ i
i

Non Oui
i > n? Arrêt
i

82
Tableau des opérations logiques et numériques :

i j (xi,xj) ? λj – λi > l(xi, xj) ? λi + l(xi xj) λj i>j? i=j j+1 j j>n? Raz j i+1 i i > n? Arrêt
j=0
0 1 Oui Oui λ1 = 3 Non 2 Non
0 2 Oui Oui λ2 = 8 Non 3 Non
0 3 Oui Oui λ3 = 6 Non 4 Non
0 4 Non 5 Non
0 5 Non 6 Oui 0 1 Non
1 0 Non 1 Non
1 1 Non 2 Non
1 2 Non 3 Non
1 3 Oui Oui λ3 = 5 Non 4 Non
1 4 Oui Oui λ4 = 9 Non 5 Non
1 5 Non 6 Oui 0 2 Non
. . . .
. . . .
. . . .
4 5 Oui Oui λ5 = 10 Non 6 Oui 0 5 Non
5 0 Non 1 Non
5 1 Non 2 Non
5 2 Non 3 Non
5 3 Non 4 Non
5 4 Non 5 Non
5 5 Non 6 Oui 0 6 Oui Arrêt

83
 Le chemin de valeur minimal est :
 = (X0 X1 X3 X2 X4 X5)
l ()=10.

3. Soit le graphe suivant :

Déterminer, en utilisant l’algorithme de FORD, le chemin de valeur minimale.

Solution :

84
Tableau des opérations logiques et numériques associées à l’algorithme de
FORD :
i j (xi xj) ? λj – λi > ? λj  i>j ? i=j j  j+1 j>n ? i  i+1
j=0
1 2 Oui Oui λ2 = 5 N 3 N
1 3 Oui Oui λ3 = 1 N 4 N
1 4 N 5 Oui
2 1 N 2 N
2 2 N 3 N 2
2 3 N 4 N
2 4 Oui Oui λ4 = 7 N 5 Oui 3
3 1 N 2
3 2 Oui Oui λ2 = 4 Oui 2
2 1 N
2 2 N
2 3 N
2 4 Oui Oui λ4 = 6 N 5 Oui 3
3 1 N
3 2 Oui N 3
3 3
3 4 Oui N 5 Oui
4 1 N
4 2 N
4 3 N
4 4 N Oui 5

Le chemin de valeur minimale est :  = (X1 X3 X2 X4) ; l () = 6.

4. On donne le graphe valué représenté ci-dessous et l’on demande de

déterminer le chemin de valeur minimale entre A et P par la méthode de
DANTZIG.

85
Solution :
Le chemin de valeur minimale entre A et P, de valeur 18, est : (A B F G L P).

5. Pour mettre en exploitation un nouveau gisement minier, les opérations

suivantes doivent être réalisées :

Durée
1/ Obtention d’un permis d’exploitation 6 mois
2/ Construction d’une piste entre route et site 4 mois
3/ Installation de deux sondeuses 1 semaine
4/ Erection de baraques provisoires 3 semaines
5/ Asphaltage de la piste 1 mois
6/ Adduction d’eau 2 mois
7/ Campagne de sondage 7 mois
8/ Fonçage 7 mois
9/ Installation au fond du matériel d’exploitation 6 semaines

86
 10/ Construction de logements pour le personnel 5 mois
11/ Traçage et aménagement du fond 11 mois
12/ Construction d’une laverie 7 mois

En étudiant les possibilités de réalisation de ces opérations, on a constaté que

l’opération 1 précède nécessairement l’opération 2, laquelle précède 3, 4, 5 et 6.
Les opérations 3 et 4 précèdent 7 ; les opérations 5, 6 et 7, les opérations 8 et
10 ; les opérations 8 et 10, les opérations 9, 11 et 12.
1) Tracer le diagramme évènements-opérations, relatif à l’ensemble des
opérations.
2) Rechercher le chemin critique
3) Calculer les dates attendues, dates limites, intervalles de flottement, marge
libre.

Solution :

Le chemin critique passe par les opérations a, b, d, g, j, k.

Les marges libres :
Opérations c e f h i l
Marges
libres 14 201 171 30 288 120

87
Diagramme de Gantt :

6. La mise en exploitation d’un nouveau gisement minier, nécessite la réalisation

des opérations ci-dessous :
Durée
a/ Obtention d’un permis d’exploitation 8 m*
b/ Construction d’une piste entre route et site 3m
c/ Installation de deux sondeuses 3s
d/ édification de baraques provisoires 1m
e/ Asphaltage de la piste 3s
f/ Adduction d’eau 6s
g/ Campagne de sondage 8m
h/ Fonçage et équipement des puits 5m
i/ Installation au fond du matériel d’exploitation 2m
j/ Construction de logements pour le personnel 13 s
k/ Traçage et aménagement du fond 38 s
l/ Construction d’une laverie 42 s

*1m (mois) = 4s (semaines)

On a constaté que l’opération b devait être précédée de l’opération a et suivie
des opérations c, d, e et f ; que les opérations c et d devaient précéder l’opération
g ; que les opérations h et j, enfin, devaient être précédées par les opérations e,
f, g et suivies par les opérations i, k et l.
88
Rechercher le chemin critique en utilisant la méthode des potentiels.
Calculer les intervalles de flottement, les marges libres.
Solution :
142 s

6. On donne le graphe ci-dessous et l’on demande de rechercher le chemin

critique.
1) Par l’algorithme de FORD.
2) Par le tableau des potentiels.
On introduit alors les modifications suivantes :
 L’opération b ne peut débuter que lorsque les 2/3 de l’opération c ont
été achevés ;
 L’opération c ne peut débuter qu’une période après le début général
des opérations ;
 L’opération k ne peut commencer que lorsque le premier tiers de
l’opération j a été exécuté ;
 L’opération h ne peut débuter qu’après l’exécution au 2/3 de
l’opération e ;
 Le début de l’opération m ne peut avoir lieu que deux périodes après
l’achèvement de l’opération f.
Calculer le nouveau chemin crique en modifiant le tableau des potentiels.

89
Solution :
28F
28F

7. Un étudiant en Master 2 a pu planifier son projet de rédaction du travail de fin

de cycle en 9 tâches élémentaires reprises dans le tableau suivant :

1) Sans tracer le graphe, déterminez le chemin critique ;

2) Si l’année académique démarre le 24 octobre, à quelle date cet étudiant peut
espérer commencer la saisie de son travail, toute chose égale par ailleurs ?
3) Quelles sont les tâches que cet étudiant devra gérer avec prudence pour ne pas
dépasser la date de fin de travail ?

8. On donne le graphe orienté valué ci-dessous, et l’on demande de déterminer

les chemins de valeur optimale allant de A à P [méthode au choix] :

90
Bibliographie indicative
Acher, J et Gardelle, J. Programmation linéaire. Dunod décision, 1978.
Billionnet A. Optimisation discrète. Dunod, Paris, France, 2007.
Cogis O., Robert Cl., Théorie des graphes, Vuibert, 2003.
Dantzig G. B. Applications et prolongements de la programmation linéaire.
Dunod, Dunod, Paris, 1966.
Droesbeke, F ; Hallin, M et Lefevre, Cl. Programmation linéaire par l’exemple.
Ellipses, 1986.
Ecoto, F., Initiation à la Recherche Opérationnelle, Ellipses, Paris, 1986.
Faure, R., Kaufmann, A., Invitation à la recherche opérationnelle, Dunod, 1979.
Faure, R., Précis de recherche opérationnelle, Dunod, Liège, 1999.
Faure, R., Lemaire, B. et Picouleau, C., Précis de Recherche Opérationnelle,
5ème Edition, Dunod, Paris, 2000.
Gondran M., et Minoux M., Graphes et algorithmes, 2e édition, Eyrolles, 1986.
Helary, J.M. et Pedrono, R., Recherche opérationnelle. Exercices corrigés,
Hermann, Paris, 1983.
Henry-Labordère, A et Grojnowski, M. Recherche opérationnelle.
Programmation linéaire et combinatoire. Exercices et problèmes avancés.
Masson 1976.
Maurras J. F. Programmation linéaire, complexité. Springer, Heiderlberg,
Germany, 2002.
Maurin, H. Programmation linéaire. Editions Technip 1967.
Minoux M. Programmation mathématique. Dunod, Paris, France, 1983.
Opris, Ch. Programmation linéaire. Bases algébriques, Algorithmiques,
Programmes, OPU 1983.
Roseaux, Exercices et Problèmes résolus de Recherche Opérationnelle, Tome 1,
Masson, Paris, 1996.
Sakarovitch, M. Techniques mathématiques de la recherche opérationnelle. 1.
Programmation linéaire. ENSIMAG Grenoble 1979.

91