0% ont trouvé ce document utile (0 vote)

15 vues163 pages

Info H 3000

Le document traite de la programmation linéaire, incluant la modélisation de problèmes, les types de programmes linéaires, et les algorithmes associés tels que le simplexe et la dualité. Il aborde également des applications dans les graphes, les problèmes d'ordonnancement, et la théorie des réseaux de transport. Enfin, il présente des problèmes spécifiques comme le problème de Hitchcock et le problème d'affectation, avec des exemples numériques et des méthodes de résolution.

Transféré par

ibrahima

Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.

Formats disponibles

Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

0% ont trouvé ce document utile (0 vote)

15 vues163 pages

Info H 3000

Transféré par

ibrahima

Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.

Formats disponibles

Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

TABLE DES MATIÈRES 3

Table des matières

I Programmation linéaire 7

1 Modélisation de problèmes 9

2 Différents types de programmes linéaires 29

2.1 Définitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.2 Passage d’un type de P.L. à un autre . . . . . . . . . . . . . . . . 32
2.3 Expression de contraintes logiques . . . . . . . . . . . . . . . . . . 32

3 Définitions – Notations 35

4 Résultats fondamentaux 39

5 Algorithme de dénombrement 45

6 Algorithme du simplexe 47
6.1 Principe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
6.2 Hypothèses de départ . . . . . . . . . . . . . . . . . . . . . . . . . 47
6.3 Passage d’une solution de base à une autre solution de base . . . . 47
6.4 Variation de la fonction économique lors d’un changement de base 49
6.5 Choix des indices r et k. . . . . . . . . . . . . . . . . . . . . . . . 50
6.6 Expression de la valeur de la fonction économique en un point
quelconque admissible, en fonction de sa valeur en une solution de
base admissible explicitée . . . . . . . . . . . . . . . . . . . . . . . 50
6.7 Critère d’optimabilité . . . . . . . . . . . . . . . . . . . . . . . . . 51
6.8 Critère pour le cas où la solution est infinie . . . . . . . . . . . . . 51
6.9 Résumé de l’algorithme du Simplexe pour un problème à minimum 52
6.10 Exemple numérique et disposition pratique . . . . . . . . . . . . . 52
4 TABLE DES MATIÈRES

6.11 Remarques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
6.12 Méthode de la base artificielle . . . . . . . . . . . . . . . . . . . . 54
6.13 Convergence de l’algorithme du Simplexe . . . . . . . . . . . . . . 57
6.14 Annexe : démonstrations des formules du changement de base . . 61

7 La dualité 63
7.1 Définition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
7.2 Propriétés fondamentale de la dualité . . . . . . . . . . . . . . . . 64
7.3 Exemple numérique . . . . . . . . . . . . . . . . . . . . . . . . . . 66
7.4 Interprétation économique de quelques coefficients . . . . . . . . . 67
7.5 Conditions de Kuhn et Tucker . . . . . . . . . . . . . . . . . . . . 68

8 L’algorithme dual simplexe 71

8.1 Principe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
8.2 Hypothèses de départ . . . . . . . . . . . . . . . . . . . . . . . . . 71
8.3 Changement de base . . . . . . . . . . . . . . . . . . . . . . . . . 71
8.4 Choix des indices r et k . . . . . . . . . . . . . . . . . . . . . . . 72
8.5 Convergence de l’algorithme . . . . . . . . . . . . . . . . . . . . . 72
8.6 Intérêt de l’algorithme . . . . . . . . . . . . . . . . . . . . . . . . 72
8.7 Méthode de la contrainte artificielle . . . . . . . . . . . . . . . . . 73
8.8 Exemples numériques . . . . . . . . . . . . . . . . . . . . . . . . . 74
8.9 Adjontion d’une contrainte . . . . . . . . . . . . . . . . . . . . . . 76

II Applications dans les graphes 79

1 Quelques problèmes de la théorie des graphes 81

1.1 Définitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
1.2 Niveaux, rangs et circuits dans les graphes orientés . . . . . . . . 85
1.3 L’arbre partiel minimum . . . . . . . . . . . . . . . . . . . . . . . 89
1.4 Problèmes de coloration . . . . . . . . . . . . . . . . . . . . . . . 93
1.5 Graphes planaires . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
1.6 Recherche de chemins de valeur extremum dans un graphe valué . 97
1.6.1 Définition du problème . . . . . . . . . . . . . . . . . . . . 97
TABLE DES MATIÈRES 5

1.6.2 Algorithme de FORD . . . . . . . . . . . . . . . . . . . . . 97

1.6.3 Algorithme de BELLMAN-KALABA . . . . . . . . . . . . 101
1.6.4 Algorithme de DIJKSTRA . . . . . . . . . . . . . . . . . . 104

2 Les problèmes d’ordonnancement 109

2.1 Définition du problème . . . . . . . . . . . . . . . . . . . . . . . . 109
2.1.1 Contraintes temporelles . . . . . . . . . . . . . . . . . . . 109
2.1.2 Contraintes sur les moyens mis en oeuvre . . . . . . . . . . 110
2.2 La méthode du chemin critique . . . . . . . . . . . . . . . . . . . 111
2.2.1 Représentation du problème par un graphe valué . . . . . 111
2.2.2 Simplification du graphe . . . . . . . . . . . . . . . . . . . 114
2.2.3 Ordonnancements au plus tôt et au plus tard . . . . . . . 115
2.2.4 Remarques concernant l’algorithme . . . . . . . . . . . . . 115
2.2.5 Tâches critiques, marges totales et marges libres . . . . . . 115
2.2.6 Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
2.2.7 Présentation des résultats . . . . . . . . . . . . . . . . . . 118
2.3 La méthodes des potentiels . . . . . . . . . . . . . . . . . . . . . . 120
2.3.1 Représentation du problème par un graphe . . . . . . . . . 120
2.3.2 Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
2.3.3 Résolution du problème . . . . . . . . . . . . . . . . . . . 122
2.4 La prise en compte des contraintes cumulatives . . . . . . . . . . 123
2.5 La méthode P.E.R.T. . . . . . . . . . . . . . . . . . . . . . . . . . 126
2.5.1 Description de la méthode . . . . . . . . . . . . . . . . . . 126
2.5.2 Note sur la distribution β . . . . . . . . . . . . . . . . . . 127

3 Théorie des réseaux de transport 129

3.1 Définitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
3.2 Problèmes du flot maximum et de la coupe minimum . . . . . . . 131
3.3 Résolution du problème de flot maximum . . . . . . . . . . . . . . 132
3.3.1 Algorithme de marquage de FORD-FULKERSON . . . . . 132
3.3.2 Convergence de l’algorithme . . . . . . . . . . . . . . . . . 134
3.3.3 Exemple numérique . . . . . . . . . . . . . . . . . . . . . . 135
3.3.4 Autre exemple numérique . . . . . . . . . . . . . . . . . . 138
6 TABLE DES MATIÈRES

3.3.5 Rangement des opérations en tableau . . . . . . . . . . . . 140

3.4 Cas particuliers et variantes du problème de flot maximum . . . . 142
3.4.1 Cas où les sommets ont des capacités limitées . . . . . . . 142
3.4.2 Le problème du flot maximum dans un graphe orienté quel-
conque . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
3.4.3 Le problème du flot maximum avec plusieurs entrées et sorties143
3.4.4 Le problème du flot maximum avec bornes inférieures . . . 143
3.4.5 Le problème du flot maximum dans un graphe non orienté 144
3.4.6 Le problème du flot minimum . . . . . . . . . . . . . . . . 144
3.4.7 Le problème du couplage maximal . . . . . . . . . . . . . . 145
3.4.8 Le problème d’Hitchcock . . . . . . . . . . . . . . . . . . . 146
3.4.9 Le problème général du flot à coût minimal . . . . . . . . . 146
3.4.10 Le problème général de transport . . . . . . . . . . . . . . 146
3.4.11 Le problème de l’affectation optimale . . . . . . . . . . . . 147
3.4.12 Le problème du plus court chemin . . . . . . . . . . . . . . 147

4 Le problème de Hitchcock 149

4.1 Enoncé du problème . . . . . . . . . . . . . . . . . . . . . . . . . 149
4.2 Programmes linéaires primal et dual associés . . . . . . . . . . . . 150
4.3 Une condition nécessaire et suffisante d’optimalité . . . . . . . . . 150
4.4 Algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
4.5 Convergence de l’algorithme . . . . . . . . . . . . . . . . . . . . . 152
4.6 ¯ i ,δ̄¯j } . . . . . . . . . . . . . . 152
Démonstrations des propriétés de {ᾱ
4.7 Remarque importante . . . . . . . . . . . . . . . . . . . . . . . . . 153
4.8 Disposition des calculs . . . . . . . . . . . . . . . . . . . . . . . . 154
4.9 Exemple numérique . . . . . . . . . . . . . . . . . . . . . . . . . . 156

5 Le problème d’affectation 161

5.1 Généralités . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
5.2 Cas particulier : le problème du couplage maximal . . . . . . . . . 161
5.3 La méthode hongroise . . . . . . . . . . . . . . . . . . . . . . . . 162
5.4 Remarque . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
5.5 Exemple numérique . . . . . . . . . . . . . . . . . . . . . . . . . . 164
7

Première partie

Programmation linéaire
9

Chapitre 1

Modélisation de problèmes

PROBLEME 1 : un problème de placement

Une entreprise veut placer un capital K. Six modalités de placement sont of-
fertes sur le marché, les taux d’intérêt étant respectivement 3%, 2,5%, 3,5%, 4%, 5%
et 4,5%.

Pour satisfaire aux contraintes légales, l’entreprise doit placer au moins 40%
de son capital suivant les deux premières modalités, au plus 35% suivant les deux
suivantes et au plus 35% suivant les deux dernières.

Combien l’entreprise doit-elle placer dans chaque modalité de façon à maxi-

miser son intérêt total?
10 CHAPITRE 1. MODÉLISATION DE PROBLÈMES

PROBLEME 2 : composition d’aliments pour le

bétail
On désire déterminer la composition, à coût minimal, d’un aliment pour bétail
qui est obtenu en mélangeant au plus trois produits bruts : orge, arachide, sésame.
L’aliment ainsi fabriqué devra comporter au moins 22% de protéines et 3,5% de
graisses, pour se conformer aux exigences de la clientèle.

On a indiqué ci-dessous les pourcentages de protéines et de graisses contenus,

respectivement, dans l’orge, l’arachide et le sésame, ainsi que le coût par tonne
de chacun des produits bruts.

Orge Arachide Sésame

Protéines 12% 52% 42%
Graisses 2% 2% 10%
Coût 25 41 39
11

PROBLEME 3 : fabrication de crème glacée

Un fabriquant désire produire 100 kg d’une préparation de base pour crème
glacée. Cette préparation doit contenir 21,5 kg de matières grasses, 21 kg de sucre,
1,2 kg d’oeufs et 56,3 kg d’eau. Les ingrédients dont il dispose figurent ci-dessous,
avec les pourcentages (en poids) de chaque constituant, et le coût au kg.

Matières grasses Sucre Oeufs Eau Coût

Crème 40 60 3
Jaune d’oeuf frais 50 40 10 4
Lait 12 88 1
Jaune d’oeuf surgelé 30 14 40 16 2
Sirop 70 30 0,8
Eau 100 0

Le fabriquant désire déterminer la composition du mélange de coût minimal.

12 CHAPITRE 1. MODÉLISATION DE PROBLÈMES

PROBLEME 4 : problème de production

Une usine fabrique 2 produits P1 et P2 .

Chacun de ces produits demande, pour son usinage, des heures de fabrication
unitaires sur les machines A,B,C,D,E comme indiqué ci-dessous (tableau 1).

Les produits utilisent 3 fournitures F1 ,F2 ,F3 comme indiqué dans le tableau
2.

Quelle est la production optimale, sachant que les marges brutes des produits
sont 1.7 pour P1 et 3.2 pour P2 ?

Tableau 1 A B C D E
P1 0 1,5 2 3 3
P2 3 4 3 2 0
Disponibilité totale 39 60 57 70 57

Tableau 2 F1 F2 F3
P1 0 12 8
P2 5 36 0
3
Unités kg m m2
Stock disponible 55 432 136
13

PROBLEME 5 : choix de pétroles bruts pour une

raffinerie
Une raffinerie peut traiter 3 types de pétroles bruts, en vue de la fabrication
de 5 produits finis. Le tableau ci-dessous reprend les quantités produites et les
bénéfices réalisés.

D’autre part, la production est limitée par la capacité des unités de traitement,
les possibilités de vente et les stockages disponibles (cf. tableau).

Quelles quantités de pétroles bruts doit-elle traiter pour réaliser un bénéfice

total maximum?

Bruts n0 1 Bruts n0 2 Bruts n0 3 Limites

Produits finis Afrique Moyen-Orient Amérique Product.

Gaz et gaz liquéfiés 0,02 - 0,06 300.000 T.

Essences 0,20 0,25 0,30 1.050.000 T.
Pétroles 0,08 - 0,04 180.000 T.
Gasoil 0,40 0,25 0,30 1.350.000 T.
Fuel-oil 0,30 0,50 0,30 1.800.000 T.

Bénéfices/T 4 5 5
14 CHAPITRE 1. MODÉLISATION DE PROBLÈMES

PROBLEME 6 : un problème de production

La société Z produit 2 types d’ordinateurs : un PC grand public et un PC
professionnel. La marge bénéficiaire est de 300 par unité pour le premier et de
500 pour le second. Trois composants essentiels interviennent dans le montage. Le
tableau ci-dessous indique combien de composants de chaque type interviennent
dans chaque PC et quelles sont les disponibilités mensuelles des différents com-
posants.

Type de Disponibilités PC PC
composants mensuelles grand public professionnel
Châssis standard 60 1 0
Châssis professionnel 50 0 1
Disk drive 120 1 2

En supposant que l’écoulement de la production ne pose pas de problème,

quel est le meilleur “product mix”, c’est-à-dire combien de PC de chaque type
a-t-on intérêt à fabriquer?
15

PROBLEME 7 : production d’un atelier

Un atelier peut fabriquer trois types d’articles : l’article A1 (cadence : 35 objets
à l’heure), l’article A2 (cadence : 45 objets à l’heure) et l’article A3 (cadence : 20
objets à l’heure). Cette fabrication utilise une machine-outil unique, disponible
200 heures par mois.

Les bénéfices unitaires sont respectivement de 60 par objet pour A1 , 40 par

objet pour A2 et 80 par objet pour A3 .

Chaque objet est vérifié par un des 3 techniciens de l’équipe de contrôle:

chaque technicien travaille 170 heures par mois et la vérification d’un objet prend
4 minutes pour A1 , 3 minutes pour A2 et 2 minutes pour A3 .

Le nombre maximum d’objets qu’on peut écouler par mois est de 4900 pour
A1 , 5400 pour A2 et 2000 pour A3 .

Quelle est la production optimale?

16 CHAPITRE 1. MODÉLISATION DE PROBLÈMES

PROBLEME 8: problème de découpe de bobines

On découpe longitudinalement des bobines en ”bobineaux“ de largeurs plus
petites (et de même longueur).

chute
bobineau

bobine

On dispose d’une bobine B1 de largeur 9 et de longueur 20 et d’une bobine

B2 de largeur 7 et de longueur 30. Les bobineaux commandés sont de 2 largeurs
différentes: l1 = 3 et l2 = 5.

Ceux de largeur 3 doivent représenter, ensemble, une longueur totale au moins

égale à 40 et ceux de largeur 5, une longueur totale au moins égale à 20.

On désire maximiser la surface totale découpée.

PROBLEME 9: problème de découpe de barres

On veut découper un stock de barres d’acier de 1 m de long en barreaux de
28 et 45 cm. Trois types de découpes d’une barre donnée sont possibles:
* 3 barreaux de 28 cm
* 2 barreaux de 45 cm
* 1 barreau de 45 cm et 1 barreau de 28 cm.

On veut découper 36 barreaux de 28 cm et 24 barreaux de 45 cm, commandés

par un client, en minimisant le total des chutes.

Considérer deux cas :

a) Les barreaux éventuellement découpés en excédent ne sont pas considérés

comme des chutes
b) Les barreaux éventuellement découpés en excédent sont considérés comme
des chutes
18 CHAPITRE 1. MODÉLISATION DE PROBLÈMES

PROBLEME 10: transport d’appareils photographi-

ques
Une compagnie japonaise exporte par avion des appareils photos. Le charge-
ment total ne peut peser plus de 330 kg et comporte 4 types de caisses. Dans les
plus grosses, on peut ranger 180 appareils et le poids total de la caisse est alors
de 150 kg. Dans les autres, on peut placer 140, 80 ou 40 appareils pour des poids
de 120, 70 tet 40 kg. On n’expédie que des caisses pleines.

On demande le nombre de caisses de chaque type à expédier pour que le

nombre total d’appareils photos livrés soit maximal.
19

PROBLEME 11: un problème d’investissement

Six projets d’investissement, s’étalant chacun sur 4 périodes, sont proposés. Le
tableau ci-dessous indique, par période, le capital nécessaire pour chaque projet,
ainsi que le capital total disponible. Les gains attendus pour ces projets sont
respectivement de 150, 120, 110, 80, 100 et 90 unités monétaires.

Quel(s) projet(s) faut-il choisir de façon à maximiser les gains?

Projets 1 2 3 4 5 6 Capital
Périodes disponible
1 7 2 3 0 1 4 10
2 6 3 2 1 0 1 10
3 1 2 3 3 2 1 8
4 10 8 6 4 2 1 20
20 CHAPITRE 1. MODÉLISATION DE PROBLÈMES

PROBLEME 12: localisation d’émetteurs de télévision

Cinq sites ont été retenus pour construire des émetteurs de télévision destinés
à desservir 10 localités. Le tableau ci-dessous donne, pour chaque site, le coût de
construction d’un émetteur sur ce site et les localités desservies par cet émetteur.
Site Coût Localités desservies
1 4 1, 3, 5, 7, 8, 10
2 7 2, 4
3 11 1, 6, 8, 9, 10
4 6 1, 2, 4, 8, 10
5 10 3, 5, 6, 7, 9

On cherche à déterminer les sites sur lesquels il faut construire un émetteur

de façon à pouvoir desservir toutes les localités au moindre coût.
21

PROBLEME 13: un problème de localisation

Une société de distribution désire construire un ou plusieurs entrepôts à partir
desquels elle servira 6 clients importants. Quatre terrains appartenant à la société
sont disponibles. Le tableau ci-dessous reprend, pour chacun d’eux, la capacité
maximum de l’entrepôt qui pourrait y être construit, le coût de construction et
le coût unitaire de transport de cet éventuel entrepôt vers chaque client. Sachant
que les quantités demandées par les clients sont respectivement de 200, 250, 300,
100, 150, et 175, où faut-il construire un (des) entrepôt(s) et comment faut-il
organiser la distribution de façon à minimiser le coût total de l’opération?

Clients 1 2 3 4 5 6 Capacité Coût

Entrepôts maximum construction
1 2 3 1 4 5 2 500 100
2 3 1 1 2 2 1 400 120
3 4 1 2 3 2 5 600 150
4 6 1 1 1 2 0 1000 80
22 CHAPITRE 1. MODÉLISATION DE PROBLÈMES

PROBLEME 14: un problème de planning

Un atelier, comportant m machines, fabrique n produits différents. Chaque
produit doit passer sur chaque machine, dans un ordre donné et qui diffère selon
le produit.

Soient
1 si la j e opération sur le produit i nécessite la machine k
rijk =
0 sinon
tik le temps que passe le produit i sur la machine k.

Comment organiser les opérations de façon à minimiser le temps total de

fabrication?
23

PROBLEME 15: un problème d’affectation de

moyens
On désire affecter un budget et une équipe d’hommes à chacun des n projets
acceptés par la direction de l’entreprise.
Chaque projet doit recevoir un nombre d’hommes compris entre h1 et h2 et un
budget compris entre S1 et S2 .

Le budget global disponible est égal à M et nombre total d’hommes est égal à
H. La durée de réalisation de chaque projet est une fonction linéaire (décroissante)
donnée du budget et du nombre d’hommes affectés à ce projet.

On désire minimiser la durée de réalisation des n projets.

24 CHAPITRE 1. MODÉLISATION DE PROBLÈMES

PROBLEME 16: le problème du flot maximum

Faire passer une quantité maximum de marchandises d’un point (source) à
un autre (puits), à travers un réseau de communication à capacités limitées.

8
x2 x4
10
9
5
SOURCE x1 PUITS
xn

12
x3 xi xj
k ij
(capacite)
25

PROBLEME 17: le problème de Hitchcock

Étant donné m entrepôts contenant des quantités ai (i = 1, 2, . . . m) de mar-
chandises et n clients demandant des quantités dj , et sachant que le coût unitaire
de transport de l’entrepôt i vers le client j est cij , comment servir les clients en
minimisant le coût total?
26 CHAPITRE 1. MODÉLISATION DE PROBLÈMES

PROBLEME 18: le problème du “sac à dos”

Des marchandises de k types différents doivent être transportées dans un “sac”
de volume V . Chaque unité de la marchandise j prend un volume vj et rapporte
un gain cj (j = 1, 2, . . . k).

Comment remplir le sac de façon à maximiser le gain total?

PROBLEME 19: le problème d’affectation

Affecter m ingénieurs à m projets (un ingénieur par projet) de façon à mi-
nimiser le coût total, sachant que l’affectation de l’ingénieur i au projet j coûte
cij .
28 CHAPITRE 1. MODÉLISATION DE PROBLÈMES

PROBLEME 20: un exemple de programme qua-

dratique en variables booléennes
Une entreprise veut construire m centres de production et dispose pour cela
de n endroits possibles (n > m).

Le coût unitaire de transport de l’endroit i à l’endroit j est cij .

Le volume de marchandises à transporter du centre de production k au centre

de production ` est dk` .

Où faut-il construire les m centres de production de façon à minimiser le coût

total du transport?
29

Chapitre 2

Différents types de programmes

linéaires

2.1 Définitions
Un programme linéaire est un problème d’optimisation d’une fonction linéaire
sous des contraintes linéaires.
Un tel problème peut toujours s’exprimer de la façon suivante :

minimiser c 1 x1 + c 2 x2 + . . . + c n xn



 a11 x1 + . . . + a1n xn ≤ b1 ,

 a x + ... + a x
i1 1 in n ≤ bi ,
sous les contraintes (1)

 am1 x1 + . . . + amn xn ≤ bm ,


x1 ,x2 , . . . xn ≥ 0.

En effet, maximiser une fonction revient à minimiser cette fonction changée

de signe; d’autre part, toute contrainte contenant le signe ≥ se ramène à une
contrainte contenant le signe ≤ en la multipliant par −1; enfin, toute égalité
peut être remplacée par deux inégalités (une dans chaque sens).

Les inégalités {xi ≥ 0, ∀i} sont justifiées par le fait que dans les problèmes
concrets, les xi représentent en général des quantités économiques qui ne peuvent
pas être négatives. On peut de toute façon se ramener à ces inégalités, soit en
posant x0 i = xi − Mi (où Mi est une borne inférieure connue de xi ), soit en
remplaçant xi par yi − zi , où yi ≥ 0 et zi ≥ 0.
30 CHAPITRE 2. DIFFÉRENTS TYPES DE PROGRAMMES LINÉAIRES

La nature d’un programme linéaire ne dépend donc pas de la forme particulière

qu’on lui donne; par contre, elle dépend de la nature des variables qu’il contient.

* Un programme linéaire (P.L.) est un problème qui peut se mettre sous

la forme (1).
* Un P.L. est continu si les variables xi peuvent prendre n’importe quelle
valeur réelle.
* Un P.L. est booléen si les variables xi ne peuvent prendre que les valeurs
0 ou 1.
* Un P.L. est entier si les variables xi ne peuvent prendre que des valeurs
entières.
* Un P.L. est mixte-booléen si certaines variables xi sont réelles et d’autres
booléennes.
* Un P.L. est mixte-entier si certaines variables xi sont réelles et d’autres
entières.

Le schéma suivant résume les liens qui existent entre les différents types de P.L.
Une flèche d’un type vers un autre signifie “contient comme cas particulier”.
Nous donnons ensuite un exemple numérique à 2 variables et la représentation
graphique associée à chaque type de P.L.

Schéma récapitulatif

!() *,#+#"%* $ &*- "'" 2 $1*4365
.0// 1*$
2.1. DÉFINITIONS 31

x ≤4
 1

Soit x1 + x 2 ≤6


−x1 + x2 ≤ 3

1
maximiser − x1 + x2
2

Si x1 et x2 ≥ 0 ⇒ (1) continu

Si x1 et x2 = 0 ou 1 ⇒ (2) booléen

Si x1 et x2 entiers ≥ 0 ⇒ (3) entier

Si x1 ≥ 0 et x2 = 0 ou 1 ⇒ (4) mixte-booléen

Si x1 ≥ 0 et x2 entier ≥ 0 ⇒ (5) mixte-entier

(Le point encadré est la solution optimale)

x x x
2 2 2

6 6 6

3 3 3

x x x
1 1 1
0 4 6 0 4 6
0 4 6
(1) (2) (3)

x x
2 2

6 6

3 3

x x
1 1
0 4 6 0 4 6

(4) (5)
32 CHAPITRE 2. DIFFÉRENTS TYPES DE PROGRAMMES LINÉAIRES

2.2 Passage d’un type de P.L. à un autre

– Dans certains cas, la solution optimale d’un programme lineáire continu
peut être entière. Des résultats théoriques ont été établis en vue de ca-
ractériser ces cas.

– Un programme linéaire booléen peut toujours s’exprimer comme un pro-

gramme linéaire entier : (
xi ≤ 1, ∀i
il suffit de remplacer xi = 0 ou 1, ∀i par .
xi entier ≥ 0, ∀i

– Réciproquement, un programme linéaire entier peut toujours s’exprimer

comme un programme linéaire booléen : 
p
 X
 x =
i 2j yji , ∀i
il suffit de remplacer xi entier ≥ 0,∀i par j=0
où p est


yji = 0 ou 1, ∀j,∀i
choisi suffisamment grand.

2.3 Expression de contraintes logiques

L’introduction de variables booléennes est souvent pratique pour traduire des
contraintes particulières, comme l’illustrent les deux exemples ci-dessous.

a) Pour exprimer que (x1 ,x2 , . . . ,xn ) doit satisfaire au moins k égalités parmi
les m suivantes :

gi (x1 ,x2 , . . . ,xn ) ≥ 0, i = 1,2, . . . ,m,

on écrira 

 gi (x1 ,x2 , . . . ,xn ) ≥ δi g i , ∀i


 Xm

 δi ≤ m − k


 i=1

δi = 0 ou 1, ∀i,
où g i est une borne inférieure de la fonction gi .
b) Pour exprimer que g(x1 ,x2 , . . . ,xn ) ≥ 0 chaque fois que f (x1 ,x2 , . . . ,xn ) ≥ 0,
on exprimera que (x1 ,x2 , . . . ,xn ) doit satisfaire au moins 1 inégalité parmi
2.3. EXPRESSION DE CONTRAINTES LOGIQUES 33

les 2 suivantes : (
f (x1 ,x2 , . . . ,xn ) ≤ 0
g(x1 ,x2 , . . . ,xn ) ≥ 0.
34 CHAPITRE 2. DIFFÉRENTS TYPES DE PROGRAMMES LINÉAIRES
35

Chapitre 3

Définitions – Notations

Un programme linéaire continu est un problème qui peut, moyennant une

éventuelle transformation (cf. chapitre 2), s’énoncer comme suit : trouver les va-
leurs des n variables x1 ,x2 , . . . ,xn qui minimisent l’expression

c 1 x1 + c 2 x2 + . . . + c n xn ,

appelée fonction économique, et qui vérifient les contraintes :

a11 x1 + a12 x2 + . . . + a1n xn ≤ b1 ,

...
ai1 x1 + ai2 x2 + . . . + ain xn ≤ bi ,
...
am1 x1 + am2 x2 + . . . + amn xn ≤ bm ,
x1 ≥ 0,x2 ≥ 0, . . . ,xn ≥ 0,

où c1 ,c2 , . . . ,cn ,a11 ,a12 , . . . ,amn ,b1 ,b2 , . . . ,bm sont des nombres réels donnés.
Les notations suivantes seront également utilisées:
 n
 X



 min c j xj ,

 j=1
Xn


 aij xj ≤ bi , i = 1,2, . . . ,m,

 j=1


xj ≥ 0, ∀j,

ou encore
36 CHAPITRE 3. DÉFINITIONS – NOTATIONS

 n
 X



 min c j xj ,

 j=1
X n


 xj P j ≤ P 0 ,

 j=1


xj ≥ 0, ∀j,
   
a1j b1
 ..   .. 
 .   . 
   
Pj =  aij  , ∀j et P0 =  bi  ;
 .   . 
 ..   .. 
amj bm
ou encore
min{CX : AX ≤ b, X ≥ 0},

où A,b,C et X sont des matrices de dimensions respectives (m × n), (m × 1),

(1 × n), (n × 1).

Convention : dans la suite, l’expression “programme linéaire” désignera tou-

jours un programme linéaire continu.

Variables d’écarts
Un programme linéaire peut toujours être transformé de telle sorte que les
contraintes soient des égalités, moyennant l’introduction de variables supplémentaires
appelées variables d’écarts (qui n’interviennent pas dans la fonction économique).
Ainsi, toute inégalité du type

≤
ai1 x1 + ai2 x2 + . . . + ain xn bi
≥
peut s’écrire

+
ai1 x1 + ai2 x2 + . . . + ain xn ti = bi , où ti ≥ 0.
−

Solutions de base
Etant donné un programme linéaire mis sous la forme

min{CX : AX = b, X ≥ 0},
37

on appellera solution tout vecteur X tel que AX = b et solution admissible tout

vecteur X tel que AX = b et X ≥ 0.

Une base sera une matrice B(m × n), extraite de A, et dont le déterminant
est 6= 0 : cette notion n’a évidemment de sens que si A est de rang m.

Si
B = (Pj1 Pj2 . . . Pjm ) ,

l’ensemble I(B) = {j1 ,j2 , . . . ,jm } sera appelé l’ensemble des indices de base et
l’ensemble complémentaire, noté J(B), sera appelé l’ensemble des indices hors-
base.

A toute base B, on peut associer une solution de base X obtenue en résolvant

le système AX = b, après avoir annulé les composantes de X correspondant aux
indices hors-base. Le sous-vecteur XB de X, correspondant aux indices de base
est évidemment donné par XB = B −1 b.

La solution de base ainsi obtenue est admissible si XB ≥ 0.

La solution de base est dite explicitée lorsque B est une matrice unité.

Les variables xi , ∀i ∈ I(B), et xj , ∀j ∈ J(B) sont appelées respectivement

variables en base et variables hors-base.

Une solution de base est dite dégénérée si certaines variables en base sont
nulles pour cette solution.
38 CHAPITRE 3. DÉFINITIONS – NOTATIONS
39

Chapitre 4

Résultats fondamentaux

Théorème 1 :
L’ensemble P = {X : AX ≤ b, X ≥ 0} est convexe.

Démonstration :
Si X1 et X2 sont des éléments de P , alors ∀λ ∈ [0,1], λX1 + (1 − λ)X2 est aussi
un élément de P ; en effet
(
A (λX1 + (1 − λ)X2 ) = λAX1 + (1 − λ)AX2 ≤ λb + (1 − λ)b = b,
λX1 + (1 − λ)X2 ≥ 0.

Théorème 2 :
(sans démonstration)
L’ensemble P = {X : AX ≤ b,X ≥ 0} est soit vide, soit un polyèdre convexe,
soit un ensemble polyédrique convexe non borné.
Exemples :

  x1 ≤ 2 
−x1 + x2 ≥ 1 
 x − x2 ≤ 0

 
 x1 + x 2 ≤ 3  1

x1 − x 2 ≥ 1 −2x1 + x2 ≤ 0

 
 −x1 + x2 ≤ 1 

x1 ≥ 0, x2 ≥ 0 

 x1 ≥ 0, x2 ≥ 0
x1 ≥ 0, x2 ≥ 0

x2 x2 x2
P

P=0 P

x1 x1 x1
40 CHAPITRE 4. RÉSULTATS FONDAMENTAUX

Théorème 3 :
Lorsque P est un polyèdre convexe, l’ensemble des solutions optimales du pro-
gramme linéaire min{CX : X ∈ P } contient au moins un sommet de P .

Rappel : un point d’un polyèdre est un sommet s’il ne peut être vu comme la
combinaison linéaire convexe de deux autres points du polyèdre; tout point d’un
polyèdre peut être vu comme une combinaison linéaire convexe des sommets du
polyèdre.

Démonstration :
soit S1 ,S2 , . . . ,Sk les sommets de P et soit cSm = mincSi . Pour tout point X du
i
polyèdre, on a
Xk
X= α i Si ,
i=1

d’où
k
X
CX = αi CSi ≥ CSm ,
i=1

ce qui prouve que Sm est une solution optimale.

Remarque : les théorèmes précédents restent évidemment valables si

P = {X : AX = b,X ≥ 0}.
41

Théorème 4 :
Si A est de rang m, alors tout sommet de P = {X : AX = b,X ≥ 0} est une
solution de base admissible.

Démonstration :
soit S = (s1 ,s2 , . . . ,sk ,0, . . . ,0) un sommet de P , où si > 0, i = 1,2, . . . ,k : on a
donc
X k
sj P j = P 0 (cf. chapitre 3).
j=1

Montrons que P1 ,P2 , . . . ,Pk sont linéairement indépendants. Si ce n’est pas le cas,
il existe α1 ,α2 , . . . ,αk non tous nuls, tels que
k
X
αi Pj = 0.
j=1

En choisissant un nombre tel que |αi | < si , ∀i, on obtient

 k
 X



 (sj + αj )Pj = P0
j=1
k
X




 (sj − αj )Pj = P0
j=1

c’est-à-dire que les points X1 = (s1 + α1 , . . . ,sk + αk ,0, . . . ,0) et X2 = (s1 −
α1 , . . . ,sk − αk ,0, . . . ,0) sont des éléments de P .
Comme
1 1
S = X1 + X2 ,
2 2
on obtient une contradiction avec le fait que S est un sommet: P1 ,P2 , . . . ,Pk sont
donc bien linéairement indépendants (et par conséquent, k ≤ m).
Si k = m, alors S est la solution de base (admissible) correspondant à la base
B = (P1 · P2 . . . Pk ).
Si k < m, alors S est la solution de base (admissible) correspondant à la base
B = (P1 · P2 . . . Pk · Pi1 . . . Pim−k ) obtenue en choisissant, dans A, (m − k) colonnes
formant avec (P1 . . . Pk ) une matrice à déterminant 6= 0, ce qui est toujours pos-
sible puisque A est de rang m.
42 CHAPITRE 4. RÉSULTATS FONDAMENTAUX

Théorème 5 :
Si A est de rang m, alors toute solution de base admissible est un sommet de P
(Réciproque du théorème précédent).

Démonstration :
soit S = (s1 ,s2 , . . . ,sm , 0, . . . ,0) une solution de base admissible : cela signifie que
la matrice B = (P1 P2 . . . Pm ) a un déterminant 6= 0 et que si ≥ 0, i = 1,2, . . . ,m.
Si si = 0, ∀i, alors S ne peut pas être combinaison linéaire convexe de deux autres
points du polyèdre, et est donc un sommet. Sinon, supposons que S ne soit pas
un sommet de P : on a donc

S = λX1 + (1 − λ)X2

où
0 ≤ λ ≤ 1, X1 P, X2 P.
On en déduit
x1i = x2i = 0, ∀i > m,
d’où
BX1 = BX2 = b,
ce qui n’est possible que si X1 = X2 = S.
43

CONCLUSIONS
Il résulte des théorèmes précédents que la recherche d’une solution opti-
male d’un programme linéaire peut se limiter à la considération des sommets
du polyèdre P , c’est-à-dire des solutions de base admissibles. Bien entendu, il
peut arriver qu’il y ait plusieurs solutions optimales ou que la solution optimale
soit infinie, comme illustré dans les exemples ci-dessous. Rappelons également
que les programmes linéaires ne contenant que 2 variables peuvent aisément être
résolus graphiquement.

Solution optimale unique Infinité de solutions optimales

Ensemble non borné Ensemble non borné

Solution optimale finie Solution optimale infinie
44 CHAPITRE 4. RÉSULTATS FONDAMENTAUX
45

Chapitre 5

Algorithme de dénombrement

Il résulte des théorèmes précédents que, lorsque A est de rang m, une solution
optimale du programme linéaire opt {CX : AX = b, X ≥ 0} peut être obtenue
par application de l’algorithme suivant, appelé algorithme de dénombrement.

1. Rechercher toutes les solutions de base (une solution de base s’obtient en

annulant n − m variables et en résolvant le système de m équations à m
inconnues restant).
2. Retenir les solutions de base admissibles (c’est-à-dire ayant toutes leurs
composantes positive ou nulles).
3. Sélectionner la solution de base admissible qui donne à la fonction économique
la valeur optimum.

Exemple “de la petite maison”.

Considérons le programme linéaire suivant :



 x1 ≤ 2,



 x + x2 ≤ 3,
 1

−x1 + x2 ≤ 1,





 x1 ≥ 0,x2 ≥ 0,


max 1/2x1 + x2 .

Pour appliquer l’algorithme de dénombrement, il faut que les contraintes

soient des égalités. Nous ajoutons donc des variables d’écart, ce qui nous donne
46 CHAPITRE 5. ALGORITHME DE DÉNOMBREMENT

par la même occasion une matrice A de rang m (m = 3).


 x1 +t1 = 2,



 x1 + x 2 +t2 = 3,




−x1 + x2 +t3 = 1,

 x1 ≥ 0, x2 ≥ 0, t1 ≥ 0, t2 ≥ 0, t3 ≥

 0,


 max 1 x + x .


1 2
2
L’application de l’algorithme de dénombrement donne le tableau suivant (on
annule 2 variables parmi les 5) :
x1 x2 t1 t2 t3 Système Solution Sommet Fonct.
compatible admissible (fig. 1) écon.

0 0 2 3 1 oui oui A 0
0 0 non
0 3 2 0 −2 oui non
0 1 2 2 0 oui oui B 1
2 0 0 2 3 oui oui E 1
3 0 −1 0 4 oui non
−1 0 3 4 0 oui non
2 1 0 0 2 oui oui D 2
2 3 0 −2 0 oui non
1 2 1 0 0 oui oui C 5/2

B D

A E X2
47

Chapitre 6

Algorithme du simplexe

6.1 Principe
Cet algorithme consiste à partir d’une première solution de base admissible
explicitée et à se déplacer de solution de base admissible en solution de base
admissible en améliorant toujours la fonction économique.

6.2 Hypothèses de départ

Pour disposer, au départ, d’une solution de base admissible explicitée, il faut
et il suffit que :

le système des contraintes soit mis sous la forme AX = b;

la matrice A contienne une matrice unité;
le vecteur b ait toutes ses composantes positives ou nulles.

Nous supposerons momentanément que ces hypothèses sont satisfaites; dans

la section 6.12, nous montrerons qu’il est toujours possible de les satisfaire.

6.3 Passage d’une solution de base à une autre

solution de base
Considérons le système sous la forme AX = b, où b ≥ 0 et A contient une
matrice unité B, c’est-à-dire une base; soit I(B) l’ensemble des indices de base
et J(B) l’ensemble des indices hors-base. La solution de base correspondante est
évidemment
48 CHAPITRE 6. ALGORITHME DU SIMPLEXE

(
xi = bi , ∀i ∈ I(B),
xj = 0, ∀j ∈ J(B),

et la valeur de la fonction économique, pour cette solution, est

X
Z0 = c i bi .
i∈I(B)

Pour obtenir une autre solution de base explicitée admissible, il suffit de réécrire
le système des contraintes sous une forme A0 X = b0 où b0 ≥ 0 et où A0 contient
une matrice unité B 0 . La nouvelle solution sera

(
xi = b0i , ∀i ∈ I(B 0 ),
xj = 0, ∀j ∈ J(B 0 ),

et la valeur de la fonction économique, pour cette solution, sera

X
Z00 = ci b0i .
i∈I(B 0 )

Dans la méthode du Simplexe, on considère des changements de base dans lesquels

un seul indice de base change. Autrement dit, ∃r ∈ I(B) et k ∈ J(B) tels que

I(B 0 ) = [I(B) ∪ {k}] \ {r}.

En exprimant que les systèmes AX = b et A0 X = b0 sont équivalents, on obtient

alors les relations ci-dessous entre leurs éléments (voir démonstration en annexe);
dans ces relations, aij désigne le coefficient de xj dans la contrainte où la variable
en base est xi (pour la base B) et bi désigne le second membre de cette même
contrainte; de même pour a0ij et b0i vis-à-vis de la base B 0 .
6.4. VARIATION DE LA FONCTION ÉCONOMIQUE LORS D’UN CHANGEMENT DE BASE49

aik
a0ij = aij − arj , ∀i ∈ I(B) ∩ I(B 0 ),
ark
arj
a0kj = ,
ark
aik
b0i = bi − br , ∀i ∈ I(B) ∩ I(B 0 ),
ark
br
b0k = .
ark

6.4 Variation de la fonction économique lors d’un

changement de base

Il résulte des relations ci-dessus que

X X
Z00 = ci b0i = ci b0i + ck b0k
i∈I(B 0 ) i∈I(B 0 )∩I(B)

X aik br
= ci bi − b r + ck
ark ark
i∈I(B 0 )∩I(B)

X aik br
= ci bi − b r + ck
ark ark
i∈I(B)
 
X br  X
= c i bi − ci aik − ck 
ark
i∈I(B) i∈I(B)

br
= Z0 − (Zk − ck ) ,
ark

où on a posé
X
Zk = ci aik .
i∈I(B)
50 CHAPITRE 6. ALGORITHME DU SIMPLEXE

6.5 Choix des indices r et k.

Pour que la nouvelle solution de base soit admissible et meilleure que la
précédente, il faut et il suffit que
 0
Z < Z0 dans un problème à minimum
 0

Z 0 0 > Z0 dans un probème à maximum

 0
bi ≥ 0, ∀i ∈ I(B 0 ).
Il en résulte que r et k doivent être choisis de telle sorte que

 Zk − ck > 0 dans un problème à minimum



 Zk − ck < 0 dans un probème à maximum



 ark > 0 (ark est appelé le pivot du changement de base)

 bi − br aik ≥ 0, ∀i ∈ I(B) ∩ I(B 0 ).


ark
Les deux dernières conditions peuvent se résumer comme suit :
br bi
= min . (∗)
ark aik >0 aik
En pratique, on choisit, dans un problème à minimum (resp. maximum) l’indice
k correspondant à la quantité Zk − ck la plus positive (resp. négative) et on
détermine ensuite l’indice r sur base de la relation (*).

Dans la section 6.7, nous considérerons le cas où il n’existe pas d’indice k
satisfaisant la condition voulue; dans la section 6.8, nous considérerons le cas où
il n’existe pas d’indice r tel que ark > 0. L’étude de ces deux cas repose sur le
résultat établi dans la section 6.6.

6.6 Expression de la valeur de la fonction économique

en un point quelconque admissible, en fonc-
tion de sa valeur en une solution de base
admissible explicitée
Considérons toujours le système sous la forme AX = b, où A contient une
matrice unité B; le système s’écrit donc
P
xi + j∈J(B) aij xj = bi , ∀i ∈ I(B).
6.7. CRITÈRE D’OPTIMABILITÉ 51

Soit Q un point quelconque admissible (c’est-à-dire vérifiant ce système et de

coordonnées non négatives) et Z0 (Q) la valeur de la fonction économique en ce
point.

Il vient
n
X
Z0 (Q) = cj xj (Q)
j=1
X X
= ci xi (Q) + cj xj (Q)
i∈I(B) j∈J(B)
 
X X X
= c i  bi − aij xj (Q) + cj xj (Q)
i∈I(B) j∈J(B) j∈J(B)
 
X X X
= c i bi −  ci aij − cj  xj (Q)
i∈I(B) j∈J(B) i∈I(B)
X
= Z0 − (Zj − cj ) xj (Q).
j∈J(B)

6.7 Critère d’optimabilité

Il résulte de la formule précédente que si, dans un problème à minimum (resp.
maximum),
Zj − cj ≤ 0 (resp. ≥ 0), ∀j ∈ J(B),
alors, ∀Q admissible,
Z0 (Q) ≥ Z0 (resp. ≤ Z0 ),
c’est-à-dire que la solution de base correspondant à B est une solution optimale.
L’absence d’indice k satisfaisant la condition énoncée dans la section 5.5 est donc
le critère d’optimalité.

6.8 Critère pour le cas où la solution est infinie

Supposons que, dans un problème à minimum (resp. à maximum), on ait

 Zk − ck > 0 (resp. < 0)

aik ≤ 0,∀i,
52 CHAPITRE 6. ALGORITHME DU SIMPLEXE

c’est-à-dire que l’on ne trouve pas de pivot positif.

En prenant un point Q tel que



 xj (Q) = 0, ∀j ∈ J(B), j =6 k,



xk (Q) > 0,





xi (Q) = bi − aik xk (Q), ∀i ∈ I(B),
on obtient un point admissible et, en vertu de la formule établie dans la section
6.6, on a
Z0 (Q) = Z0 − (Zk − ck )xk (Q) < Z0 (resp. > Z0 ).
Cette propriété reste vraie, quelle que soit la valeur de xk (Q) : par conséquent, le
domaine admissible est non borné et la valeur optimale de la fonction économique
est −∞ (resp. +∞).

6.9 Résumé de l’algorithme du Simplexe pour

un problème à minimum
a) Ecrire le P.L. sous la forme min{CX : AX = b, X ≥ 0} où b ≥ 0 et A
contient une matrice unité; on en déduit une première solution de base
admissible.
b) Si Zj − cj ≤ 0, ∀j, alors la solution de base considérée est optimale. Sinon,
soit k tel que Zk − ck = maxj (Zj − cj ).
c) Si aik ≤ 0, ∀i, alors la solution est infinie. Sinon, soit r tel que
br bi
= min .
ark aik >0 aik
d) Effectuer le changement de base (formules de la section 6.3).
e) Retourner en b)

Exercice : résumer l’algorithme du Simplexe pour un problème à maximum.

6.10 Exemple numérique et disposition pratique

Reprenons l’exemple de la petite maison défini au chapitre 5. L’introduction
des variables d’écart nous conduit à un P.L. qui vérifie les conditions de départ
6.11. REMARQUES 53

de l’algorithme du Simplexe.


 x1 +t1 = 2,





 x1 + x 2 +t2 = 3,






−x1 + x2 +t3 = 1,






 x1 ≥ 0, x2 ≥ 0, t1 ≥ 0, t2 ≥ 0, t3 ≥ 0,




 max 1 x1 + x2 .


2
L’application de l’algorithme du Simplexe fournit la suite de tableaux qui suit.

1/2 1 0 0 0 → (cj )
CB Base b x1 x2 t1 t2 t3
0 t1 2 1 0 1 0 0
0 t2 3 1 1 0 1 0
0 t3 1 −1 1 0 0 1
0 −1/2 −1 0 0 0 → (Zj − cj )
0 t1 2 1 0 1 0 0
0 t2 2 2 0 0 1 −1
1 x2 1 −1 1 0 0 1
1 −3/2 0 0 0 1
0 t1 1 0 0 1 −1/2 1/2
1/2 x1 1 1 0 0 1/2 −1/2
1 x2 2 0 1 0 1/2 1/2
5/2 0 0 0 3/4 1/4

Solution optimale

6.11 Remarques
La colonne CB contient les ci des variables en base qui sont indiquées, dans
le bon ordre, dans la colonne “Base”.
54 CHAPITRE 6. ALGORITHME DU SIMPLEXE

La valeur Zj d’une variable s’obtient en effectuant le produit scalaire de la

colonne CB par la colonne de cette variable. Il est clair que les Zj −cj des variables
en base sont toujours nulles.

Tout tableau Simplexe définit une solution de base admissible : les coordonnées
en base de cette solution se lisent dans la colonne b (les coordonnées hors-base
sont nulles) et la valeur de la fonction économique est le produit scalaire des
colonnes CB et b.

Les éléments d’un tableau Simplexe se calculent à partir du tableau précédent

par la “règle du rectangle”.

On démontre aisément que cette règle s’applique non seulement aux aij et aux
bi , mais aussi aux Zj − cj et à Z0 .

6.12 Méthode de la base artificielle

Il est évidemment toujours possible d’écrire les contraintes d’un P.L. sous
la forme AX = b, où b ≥ 0, mais il n’est pas évident que la matrice A ainsi
obtenue contiendra une matrice unité. La méthode de la base artificielle permet
de satisfaire cette condition.

Soit le programme linéaire

 n
 X


 aij xj = bi ≥ 0, i = 1,2, . . . ,m.



 j=1

xj ≥ 0, j = 1,2, . . . ,n,



 X n


 min c j xj .


j=1

Nous le remplaçerons par le programme linéaire suivant :

 n
 X


 aij xj + vi = bi , ∀i,



 j=1

xj ≥ 0, vi ≥ 0 ∀j, ∀i,



 X n




 min c j xj + M v 1 + M v 2 + . . . + M v m .
j=1
6.12. MÉTHODE DE LA BASE ARTIFICIELLE 55

Ce nouveau P.L. contient une matrice unité et peut donc être résolu par l’algo-
rithme du Simplexe. Pour que ce programme soit équivalent au précédent, il faut
que, dans sa solution, toutes les variables vi (appelées variables artificielles)
soient nulles.

C’est la raison pour laquelle elles ont été introduites dans la fonction économique
avec un coefficient M supposé arbitrairement grand (dans un problème à maxi-
mum, on les introduira avec un coefficient −M ) : pour réaliser le minimum, l’al-
gorithme du Simplexe va rejeter les variables artificielles hors-base. De façon
précise :

– si, dans la solution optimale du nouveau P.L., toutes les variables artificielles
sont nulles, alors cette solution est optimale pour le P.L. initial;

– sinon, le P.L. initial n’admet aucune solution admissible (contraintes contra-

dictoires).

Exemple numérique et disposition pratique



 2x1 + x2 ≥ 8,



 x + x2 ≥ 6,
 1

x1 + 5x2 ≥ 10,





 x1 ,x2 ≥ 0,


min x1 + 2x2

L’application de la méthode de la base artificielle donne les tableaux suivants

(rappel : Po = b)
56 CHAPITRE 6. ALGORITHME DU SIMPLEXE

1 2 0 0 0 M M M
Base cB P0 P1 P2 Pt1 Pt2 Pt3 P v1 P v2 P v3
v1 M 8 2 1 −1 0 0 1 0 0
v2 M 6 1 1 0 −1 0 0 1 0
v3 M 10 1 5 0 0 −1 0 0 1
0 −1 −2 0 0 0 0 0 0
24M 4M 7M −M −M −M 0 0 0
v1 M 6 9/5 0 −1 0 1/5 1 0
v2 M 4 4/5 0 0 −1 1/5 0 1
x2 2 2 1/5 1 0 0 −1/5 0 0
4 −3/5 0 0 0 −2/5 0 0
10M 13/5M 0 −M −M 2/5M 0 0
x1 1 10/3 1 0 −5/9 0 1/9 0
v2 M 4/3 0 0 4/9 −1 1/9 1
x2 2 4/3 0 1 1/9 0 −2/9 0
6 0 0 −1/3 0 −1/3 0
4/3M 0 0 4/9M −M 1/9M 0
x1 1 5 1 0 0 −5/4 1/4
t1 0 3 0 0 1 −9/4 1/4
x2 2 1 0 1 0 1/4 −1/4
7 0 0 0 −3/4 −1/4
0 0 0 0 0 0

La solution optimale de ce programme est donc :

x1 = 5, x2 = 1, t1 = 3, t2 = t3 = 0;

la valeur optimale de la fonction économique est 7.

6.13. CONVERGENCE DE L’ALGORITHME DU SIMPLEXE 57

6.13 Convergence de l’algorithme du Simplexe

Comme l’algorithme se déplace de solution de base admissible en solution
de base admissible en améliorant la fonction économique et que le nombre de
solutions de base est fini, l’algorithme aboutira à la solution optimale en un
nombre fini d’étapes.

Théoriquement, il peut cependant arriver que l’amélioration de la fonction

économique soit nulle et que l’algorithme cycle en restant bloqué au même point.
Bien que cette situation soit rarissime en pratique (ne fût-ce qu’à cause des erreurs
d’arrondis), nous présentons ci-dessous un exemple numérique conduisant à un
tel cyclage.

Ce cyclage est dû au fait qu’à certaines étapes, on peut choisir arbitraire-
ment la variable qui sort, entre plusieurs candidates (plusieurs bi /aik minimaux).
Nous présentons ensuite une technique de perturbation qui, grâce à un choix plus
systématique de la variable qui sort, évite le cyclage.

Soit le programme linéaire


1 1

 x −60x2 − x3 +9x4 +x5 = 0
 4 1
 25
1 1
 x 1 −90x2 − x3 +3x4 +x6 = 1
 2 50


x3 +x7 =1

x1 ,x2 ,x3 ,x4 ,x5 ,x6 ,x7 ≥ 0

3 1
min − x1 + 150x2 − x3 + 6x4
4 50
58 CHAPITRE 6. ALGORITHME DU SIMPLEXE

Base cB P0 P1 P2 P3 P4 P5 P6 P7
−3/4 150 −1/50 6 0 0 0
P5 0 0 1/4 −60 −1/25 9 1 0 0
P6 0 0 1/2 −90 −1/50 3 0 1 0 choix
P7 0 1 0 0 1 0 0 0 1
0 3/4 −150 1/50 −6 0 0 0
P1 −3/4 0 1 −240 −4/25 36 4 0 0
P6 0 0 0 30 3/50 −15 −2 1 0 pas choix
P7 0 1 0 0 1 0 0 0 1
0 0 30 7/50 −33 −3 0 0
P1 −3/4 0 1 0 8/25 −84 −12 8 0
P2 150 0 0 1 1/500 −1/2 −1/15 1/30 0 choix
P7 0 1 0 0 1 0 0 0 1
0 0 0 2/25 −18 −1 −1 0
P3 −1/50 0 25/8 0 1 −525/2 −75/2 25 0
P2 150 0 −1/160 1 0 1/40 1/120 −1/60 0 pas choix
P7 0 1 −25/8 0 0 525/2 72/2 −25 1
0 −1/4 0 0 3 2 −3 0
P3 −1/50 0 −125/2 10.500 1 0 50 −150 0
P4 6 0 −1/4 40 0 1 1/3 −2/3 0 choix
P7 0 1 125/2 −10.500 0 0 −50 150 1
0 1/2 −120 0 0 1 −1 0
P5 0 0 −5/4 210 1/50 0 1 −3 0
P4 6 0 1/6 −30 −1/50 1 0 1/3 0 pas choix
P7 0 1 0 0 1 0 0 0 1
0 7/4 −330 −1/50 0 0 2 0
P5 0 0 1/4 −60 −1/25 9 1 0 0
P6 0 0 1/2 −90 −1/50 3 0 1 0
P7 0 1 0 0 1 0 0 0 1
0 3/4 −150 1/50 −6 0 0 0
6.13. CONVERGENCE DE L’ALGORITHME DU SIMPLEXE 59

Technique de perturbation

Cette technique revient en fait à considérer le programme linéaire perturbé :

 n n
 X X



 aij xj = bi + j aij = bi ()

 j=1 j=1
xj ≥ 0

 X



 min c j xj ,

j

bi ()
où est une quantité positive arbitrariement petite. Il est évident que les
aik
seront tous différents (puisque la matrice A contient une matrice unité) et tous
différents de 0 (ce qui assure que la fonction économique sera strictement meilleure
à chaque étape).

Pratiquement, pour déterminer la variable qui sort de la base, on comparera

bi
les . Si plusieurs d’entre eux sont minimaux, on les départagera au moyen
aik
ai1 ai2
des . S’il reste des ex aequo, on les départagera au moyen des , et ainsi de
aik aik
suite jusqu’à ce qu’il n’y ait plus qu’une seule variable candidate pour sortir de
la base.

Dans les tableaux suivants, l’exemple numérique précédent a été traité par
cette technique de perturbation.

En appliquant la technique de perturbation, on évite le cyclage et l’on obtient

la solution optimale après 6 itérations.
60 CHAPITRE 6. ALGORITHME DU SIMPLEXE

Base cB P0 P1 P2 P3 P4 P5 P6 P7
−3/4 150 −1/50 6 0 0 0
P5 0 0 1/4 −60 −1/25 9 1 0 0
P6 0 0 1/2 −90 −1/50 3 0 1 0
P7 0 1 0 0 1 0 0 0 1
0 3/4 −150 1/50 −6 0 0 0
P1 −3/4 0 1 −240 −4/25 36 4 0 0
P6 0 0 0 30 3/50 −15 −2 1 0
P7 0 1 0 0 1 0 0 0 1
0 0 30 7/50 −33 −3 0 0
P1 −3/4 0 1 0 8/25 −84 −12 8 0
P2 150 0 0 1 1/500 −1/2 −1/15 1/30 0
P7 0 1 0 0 1 0 0 0 1
0 0 0 2/25 −18 −1 −1 0
P1 −3/4 0 1 −160 0 −4 −4/3 8/3 0
P3 −1/50 0 0 500 1 −250 −100/3 50/3 0
P7 0 1 0 −500 0 250 100/3 −50/3 1
0 0 −40 0 2 5/3 −7/3 0
P1 −3/4 2/125 1 −168 0 0 −4/5 12/5 2/125
P3 −1/50 1 0 0 1 0 0 0 1
P4 6 1/250 0 −2 0 1 2/15 −1/15 1/250
−1/125 0 −36 0 0 7/5 −11/5 −1/125
P1 −3/4 1/25 1 −180 0 6 0 2 1/25
P3 −1/50 1 0 0 1 0 0 0 1
P5 0 3/100 0 −15 0 15/2 1 −1/2 3/100
−1/20 0 −15 0 −21/2 0 −3/2 −1/20
6.14. ANNEXE : DÉMONSTRATIONS DES FORMULES DU CHANGEMENT DE BASE61

6.14 Annexe : démonstrations des formules du

changement de base
1e démonstration
Avant le changement de base, les vecteurs Pi , i ∈ I(B) forment une base de
Rm et nous avons  X
P = aij Pi , ∀j
 j


i∈I(B)
X


 P 0 = bi P i.
i∈I(b)

En particulier
P
Pk = aik Pi + ark Pr ,
i∈I(B)
i6=r

d’où
1 P aik
Pr = Pk − Pi ,
ark i∈I(B) ark
i6=r

et par conséquent

 P arj aik arj

 Pj = aij − Pi + Pk ,

 i∈I(B) ark ark
i6=r
(1)
 P br aik bk p k
 P = bI − Pi +
 0

 i∈I(B) ark ark
i6=r

Après le changement de base, les vecteurs Pi , i ∈ I(B 0 ) forment aussi une base
de Rm et nous avons
 X

 Pj = a0ij Pi ,

i∈I(B 0 )
(2) X


 P 0 = b0i Pi .
i∈I(B 0 )

En identifiant (1) et (2), on trouve les formules du changement de base.

2e démonstration
Avant le changement de base, le système est sous la forme

 X
xi + aij xj = bi , i ∈ I(B).

j∈J(B)
62 CHAPITRE 6. ALGORITHME DU SIMPLEXE

En extrayant xk de l’équation où i = r, on obtient

br xr P arj
xk = − − xj .
ark ark j∈J(B) ark
j6=k

En remplaçant xk par cette expression dans les autres équations, nous obtenons
le système suivant :

 aik P aik arj

 xi − xr + aij − xj


 ark j∈J(B) ark

 j6=k

 aik br i ∈ I(B)
(1) = bi − avec
 ark i 6= r



 xr P arj br


 xk + + xj = .

 ark j∈J(B) ark ark
j6=k

Après le changement de base, le système est sous la forme

 
 X 
0 0 0
xi + aij xj = bi , i ∈ I(B ) ,
 
j∈J(B )
0

c’est-à-dire
 P

 xi + a0ir xr + a0ij xj = b0i i ∈ I(B), i 6= r
 j∈J(B)
j6=
Pk

 xk + a0kr xr + a0kj xj = b0k .
 j∈J(B)
j6=k

En identifiant les systèmes (1) et (2), on obtient les formules du changement de

base.
63

Chapitre 7

La dualité

7.1 Définition
Etant donné un programme linéaire mis sous la forme

 AX ≥ b,

X ≥ 0,


min cX,

on appelle programme dual le programme linéaire


 Y A ≤ c,

Y ≥ 0,


max Y b,

où Y est une matrice (1 × m).

Le lecteur vérifiera, à titre d’exercice, que les propriétés suivantes en résultent :
 
 AX ≤ b,  Y A ≥ c,
 
– le dual de X ≥ 0, est Y ≥ 0,

 

max cX, min Y b;
 
 AX ≥ b,  Y A ≤ −c,
 
– le dual de X ≥ 0, est Y ≥ 0,

 

max cX, max Y b;
 
 AX ≤ b,  Y A ≥ −c,
 
– le dual de X ≥ 0, est Y ≥ 0,

 

min cX, min Y b;
– le dual du dual est le programme initial (appelé programme primal);
64 CHAPITRE 7. LA DUALITÉ

– si la ie contrainte du programme primal est une égalité, alors la ie variable

du programme dual est sans restriction de signe (s.r.s).

Exemple:


 x1 ≤2 
1
 y1 + y 2 − y 3 ≥ 2

 

 x1 + x 2 ≤ 3,
Le dual de est y2 + y 3 ≥ 1


 −x1 + x2 ≤ 1, 



 y1 ,y2 ,y3 ≥ 0,
x1 , x2 ≥ 0,

1
max x1 + x 2 min (2y1 + 3y2 + y3 ) .
2

7.2 Propriétés fondamentale de la dualité

Dans ce paragraphe, nous considérons le programme primal et son dual mis

sous la forme suivante :
 
 AX = b,  Y A ≤ c,
 
X ≥ 0, Y s.r.s.,

 

min cX, max Y b.

Théorème
Si X et Y sont des solutions admissibles respectivement du primal et du dual,
alors la valeur de la fonction économique du primal en X est supérieure ou égale
à la valeur de la fonction économique du dual en Y .

Démonstration:
cX ≥ Y AX = Y b.

Théorème
Si X̃ et Ỹ sont des solutions admissibles respectivement du primal et du dual et
si cX̃ = Ỹ b, alors X̃ et Ỹ sont des solutions optimales respectivement du primal
et du dual.
7.2. PROPRIÉTÉS FONDAMENTALE DE LA DUALITÉ 65

Démonstration:
corollaire immédiat du théorème précédent.

Théorème

a) si la solution optimale du programme primal existe et est finie, alors celle du

programme dual existe aussi, est finie et les valeurs numériques optimales
des fonctions économiques sont égales;
b) si la solution optimale du primal est infinie, alors le système des contraintes
du programme dual est contradictoire;
c) les programmes primal et dual peuvent être simultanément contadictoires.

Démonstration:

a) Supposons que l’on ait résolu le programme primal par l’algorithme du

Simplexe. A la dernière étape, le système des contraintes est sous une forme

Af X = b f ,

où
Af = K −1 A,

bf = K −1 b,

K −1 étant la sous-matrice carrée de Af constituée des mêmes colonnes que

la matrice unité dans A. D’autre part, la condition d’optimalité peut s’écrire

cf Af − c ≤ 0,

où cf est la matrice ligne formée des coefficients de la fonction économique

correspondant aux variables en base du dernier tableau Simplexe.

Enfin, la valeur optimale de la fonction économique du primal peut s’écrire

c f bf .

Définissons alors
Ỹ = cf K −1 .

On obtient
Ỹ A = cf K −1 A = cf Af ≤ c,
66 CHAPITRE 7. LA DUALITÉ

et
Ỹ b = cf K −1 b = cf bf .
Il résulte du deuxième théorème que Ỹ est optimale pour le dual.
b) Si la solution optimale du primal est infinie, alors il résulte du premier
théorème que le programme dual n’a pas de solution admissible.
c) Le programme suivant et son dual sont tous les deux contradictoires

x − x2 ≥ 2,
 1

−x1 + x2 ≥ 1,


x1 ,x2 ≥ 0,
min(−x1 − 2x2 ).

Remarque:
Les composantes de Ỹ = cf K −1 sont en fait les quantités Zj introduites au
chapitre; par conséquent, les valeurs optimales des variables du dual se lisent
immédiatement dans le tableau Simplexe optimal du programme primal.

7.3 Exemple numérique

Le lecteur vérifiera les propriétés énoncées ci-dessus sur l’exemple traité dans
la section 6.10.

Solution du primal

1/2 1 0 0 0
c(B) v(B) P0 P x1 P x2 P t1 P t2 P t3
0 t1 2 1 0 1 0 0
0 t2 3 1 1 0 1 0
0 t3 1 -1 1 0 0 1
0 -1/2 -1 0 0 0
0 t1 2 1 0 1 0 0
0 t2 2 2 0 0 1 -1
1 x2 1 -1 1 0 0 1
1 -3/2 0 0 0 1
0 t1 1 0 0 1 -1/2 1/2
1/2 x1 1 1 0 0 1/2 -1/2
1 x2 2 0 1 0 1/2 1/2
5/2 0 0 0 3/4 1/4
7.4. INTERPRÉTATION ÉCONOMIQUE DE QUELQUES COEFFICIENTS67

Solution du dual

2 3 1 0 0 M
c(B) v(B) P0 P y1 P y2 P y3 P s1 P s2 Pv
2 y1 1/2 1 1 -1 -1 0 0
M v 1 0 1 1 0 -1 1
1 0 -1 -3 -2 0 0
M 0 M M 0 −M 0
3 y2 1/2 1 1 -1 -1 0 0
M v 1/2 -1 0 2 1 -1 1
3/2 1 0 -4 -3 0 0
M/2 −M 0 2M M −M 0
3 y2 3/4 1/2 1 0 -1/2 -1/2 1/2
1 y3 1/4 -1/2 0 1 1/2 -1/2 1/2
5/2 -1 0 0 -1 -2 2
0 0 0 0 0 0 −M

7.4 Interprétation économique de quelques coef-

ficients
Reprenons l’expression de la valeur de la fonction économique en un point Q
admissible en fonction de sa valeur en une solution de base admissible (cf. section
6.6) :
X
Z0 (Q) = Z0 − (Zj − cj )xj (Q).
j∈J(B)

Dans le cas particulier où

(
xk (Q) = 1, k ∈ J(B),
xj (Q) = 0, ∀j ∈ J(B), j 6= k,

on obtient
Z0 (Q) = Z0 − (Zk − ck ).

Par conséquent, si B est une base optimale d’un problème à minimum (resp.
maximum), Zk − ck représente la quantité que l’on gagne (resp. que l’on perd) sur
la fonction économique lorsqu’on augmente xk (variable hors-base) d’une unité,
pour autant que le point ainsi obtenu soit admissible, c’est-à-dire que

bi − aik ≥ 0, ∀i.
68 CHAPITRE 7. LA DUALITÉ

Les quantités Zj − cj sont appelées coûts marginaux (shadow costs).

D’autre part, il peut être intéressant, dans les applications, de connaı̂tre l’ef-
fet, sur la valeur optimale de la fonction économique. d’un accroissement (d’une
diminution) du second membre d’une contrainte.

Soient le programme initial et le programme perturbé suivants :

 
 AX = b,  AX = b0 ,
 
X ≥ 0, X ≥ 0,

 

min cX min cX,

où (
b0i = bi ∀i 6= î,
b0î = bî + 1.
En supposant que la base optimale soit la même pour les deux programmes, on
obtient
cf b0f = cf K −1 b0 = cf K −1 (b + eî ),

où eî est le vecteur dont toutes les composantes sont nulles sauf la composante î
qui vaut 1.

Par conséquent,
cf b0f = cf bf + Zî

Les quantités Zj sont appelées prix marginaux (shadow prices).

Dans l’exemple de la section 7.3 :

– l’augmentation d’une unité de la variable t2 provoque une augmentation de

3/4 de la fonction économique;
– l’augmentation d’une unité du second membre de la 2ème contrainte pro-
voque une augmentation de 3/4 de la fonction économique.

7.5 Conditions de Kuhn et Tucker

Les conditions de Kuhn et Tucker sont des conditions très générales d’optima-
lité pour les problèmes d’extrema liés. Dans le cas de la programmation linéaire,
7.5. CONDITIONS DE KUHN ET TUCKER 69

elles peuvent s’énoncer comme suit.

Théorème
Soit un programme linéaire et son dual exprimés sous la forme
( (
AX − t = b, Y A + s = c,
X ≥ 0, t ≥ 0, Y ≥ 0, s ≥ 0,

min cX, max Y b.

Si (X̃,t̃) et (Ỹ ,s̃) sont admissibles respectivement pour le primal et pour le dual,
alors elles sont optimales ssi (
s̃ · X̃ = 0,
Ỹ · t̃ = 0.

Démonstration:
C.S.: cX̃ = (Ỹ A + s̃) · X̃ = Ỹ AX̃ = Ỹ · (b + t̃) = Ỹ b.

C.N.: s̃X̃ + Ỹ · t̃ = (c − Ỹ A) · X̃ + Ỹ · t̃ = cX̃ − Ỹ b = 0.

Remarque:
ces conditions peuvent encore s’écrire

s̃j · x̃j = 0, ∀j,
ỹi · t̃i = 0, ∀i.
70 CHAPITRE 7. LA DUALITÉ
71

Chapitre 8

L’algorithme dual simplexe

8.1 Principe
Cet algorithme consiste à partir d’une première solution de base non admis-
sible explicitée et à se déplacer de solution de base non admissible en solution de
base non admissible en faisant des concessions sur la fonction économique.

8.2 Hypothèses de départ

On suppose que

* le système des contraintes est mis sous la forme AX = b;

* la matrice A contient une matrice unité;
* les quantités Zj − cj sont toutes négatives ou nulles si c’est un problème à
minimum (positives ou nulles si c’est un problème à maximum).

Le critère d’optimalité est donc satisfait. On va choisir les changements de

base de manière à ce qu’il reste satisfait et que les composantes de b deviennent
positives ou nulles. La première solution de base telle que b ≥ 0 sera évidemment
la solution optimale.

8.3 Changement de base

Les formules du changement de base sont évidemment les mêmes que dans
l’algorithme du Simplexe.
72 CHAPITRE 8. L’ALGORITHME DUAL SIMPLEXE

8.4 Choix des indices r et k

On choisira r de telle sorte que

br = min bi .
i

Des formules de changement de base, il résulte que, pour que b0k soit positif, il faut
que le pivot ark soit < 0. Si un tel pivot n’existe pas, le système des contraintes
est contradictoire, puisque ( P
j arj xj ≥ 0,
br < 0.
D’autre part, comme
arj
Zj0 − cj = Zj − cj − (Zk − ck ),
ark
on voit que k doit être choisi de telle sorte que

 Zk − c k Zj − c j
 ark = minarj <0 arj pour un problème à minimum




 Zk − c k Zj − c j

 = maxarj <0 pour un problème à maximum
ark arj
pour que le critère d’optimalité soit encore satisfait après le changement de base.

8.5 Convergence de l’algorithme

Comme le nombre de solutions de base est fini, l’algorithme aboutit à la
solution optimale en un nombre fini d’étapes. Les éventuels risques de cyclage sont
évités, comme dans l’algorithme du Simplexe, par une technique de perturbation.

8.6 Intérêt de l’algorithme

L’application de l’algorithme dual Simplexe est particulièrement utile lorsque
la matrice unité de départ correspond aux variables d’écart et que certains bi sont
< 0.

En effet, pour appliquer l’algorithme du Simplexe dans ce cas, il faut rendre

les bi > 0 en multipliant les contraintes par −1, ce qui détruit la matrice unité et
nécessite l’introduction de variables artificielles.
8.7. MÉTHODE DE LA CONTRAINTE ARTIFICIELLE 73

Par contre, pour appliquer l’algorithme dual Simplexe, il suffit que les Zj − cj
c’est-à-dire −cj , aient le bon signe, ce qui peut s’obtenir comme suit.

8.7 Méthode de la contrainte artificielle

Considérons un problème à minimum. Pour appliquer l’algorithme dual Sim-
plexe, il faut
Zj − cj = −cj ≤ 0, ∀j.
Soit
P = {j : cj ≥ 0},
N = {j : cj < 0}.
On a n
X X X
c j xj = c j xj + c j xj .
j=1 j∈P j∈N

Ajoutons la contrainte “artificielle”:

X (∗)
xj + xn+1 = M
j∈N

et soit
cf = min cj .
j∈N
On obtient
P
xf = M − xj − xn+1
j∈N
j6=f
et donc n
X X P
c j xj = c j xj + (cj − cf )xj − cf xn+1 + cf M.
j∈N
j=1 j∈P j6=f

En ajoutant la contrainte artificielle (*) et en remplaçant partout xf par son

expression en fonction des autres variables, on obtient un nouveau programme
linéaire contenant une matrice unité et où les Zj − cj sont tous ≤ 0. On peut
donc lui appliquer l’algorithme dual Simplexe.

Si la solution optimale de ce nouveau programme linéaire est sur la contrainte

artificielle, alors la solution du programme linéaire initial est infinie. Sinon, les
solutions optimales des deux problèmes sont identiques.
74 CHAPITRE 8. L’ALGORITHME DUAL SIMPLEXE

8.8 Exemples numériques

a) Pour appliquer l’algorithme dual Simplexe à

x1 +x3 +x4 −x5 = −2,

x2 −x3 −x4 +x5 = 1,
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0, x5 ≥ 0,

min (−x3 + x4 + x5 ) ,

on introduit la contrainte artificielle

x3 + x 6 = M

et on obtient le programme linéaire

x3 +x6 + M,
x1 +x4 −x5 −x6 = −M − 2,
x2 −x4 +x5 +x6 = M + 1,
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0, x5 ≥ 0, x6 ≥ 0,

min (−M + x4 + x5 + x6 )

0 0 0 1 1 1
v(B) c(B) P0 P1 P2 P3 P4 P5 P6
x3 0 M 0 0 1 0 0 1
x1 0 −2 − M 1 0 0 1 -1 -1
x2 0 1+M 0 1 0 -1 1 1
0 0 0 0 -1 -1 -1
x3 0 M 0 0 1 0 0 1
x5 1 2+M -1 0 0 -1 1 1
x2 0 -1 1 1 0 0 0 0
2+M -1 0 0 -2 0 0

Système contradictoire (pas de pivot < 0)

8.8. EXEMPLES NUMÉRIQUES 75

b) min(2x1 + x2 ) min(2x1 + x2 + M v1 + M v2 + M v3 )
 
3x + x2 ≥ 3 3x +x2 −t1 +v1 =3
 1
  1

4x1 + 3x2 ≥ 6 4x1 +3x2 −t2 +v2 =6

 

x1 + 2x2 ≥ 2 x1 +2x2 −t3 +v3 = 2

x1 ,x2 ≥ 0 x1 ,x2 ,t1 ,t2 ,t3 ,v1 ,v2 ,v3 ≥ 0

Résolution par le Simplexe

2 1 0 0 0 M M M
v(B) c(B) P0 P1 P2 P t1 P t2 P t3 P v1 P v2 P v3
v1 M 3 3 1 -1 0 0 1 0 0
v2 M 6 4 3 0 -1 0 0 1 0
v3 M 2 1 2 0 0 -1 0 0 1
0 -2 -1 0 0 0 0 0 0
11M 8M 6M −M −M −M 0 0 0
x1 2 1 1 1/3 -1/3 0 0 0 0
v2 M 2 0 5/3 4/3 -1 0 1 0
v3 M 1 0 5/3 1/3 0 -1 0 1
2 0 -1/3 -2/3 0 0 0 0
3M 0 10/3M 5/3M −M −M 0 0
x1 2 4/5 1 0 -2/5 0 -1/5 0
v2 M 1 0 0 1 -1 1 1
x2 1 3/5 0 1 1/5 0 -3/5 0
11/5 0 0 -3/5 0 -1/5 0
M 0 0 M −M M 0
x1 2 3/5 1 0 -3/5 1/5 0
t3 0 1 0 0 1 -1 1
x2 1 6/5 0 1 4/5 -3/5 0
12/5 0 0 -2/5 -1/5 0
0 0 0 0 0 0
76 CHAPITRE 8. L’ALGORITHME DUAL SIMPLEXE

On trouvera ci-dessous la résolution du même problème par l’algorithme

Dual Simplexe.

min(2x1 + x2 ) min(2x1 + x2 )

 −3x1 −x2 +t1 = −3
 3x1 + x2 ≥ 3 

4x1 + 3x1 ≥ 6 −4x1 −3x2 +t2 = −6
 
x1 + 2x2 ≥ 2 
−x1 −2x2 +t3 = −2
x1 ,x2 ≥ 0 x1 ,x2 ,t1 ,t2 ,t3 ≥ 0

2 1 0 0 0
v(B) c(B) P0 P x1 P x2 P t1 P t2 P t3
t1 0 -3 -3 -1 1 0 0
t2 0 -6 -4 -3 0 1 0
t3 0 -2 -1 -2 0 0 1
0 -2 -1 0 0 0
t1 0 -1 -5/3 0 1 -1/3 0
x2 1 2 4/3 1 0 -1/3 0
x3 0 2 5/3 0 0 -2/3 1
2 -2/3 0 0 -1/3 0
x1 2 3/5 1 0 -3/5 1/5 0
x2 1 6/5 0 1 4/5 -3/5 0
t3 0 1 0 0 1 -1 1
12/5 0 0 -2/5 -1/5 0

8.9 Adjontion d’une contrainte

Il peut arriver que l’on désire introduire une contrainte supplémentaire au pro-
gramme après l’avoir résolu. Grâce à l’algorithme dual Simplexe, cette opération
peut être effectuée sans devoir reprendre la résolution du problème depuis le
début.

Soit n
X
am+1,j xj ≤ bm+1 ,
j=1
8.9. ADJONTION D’UNE CONTRAINTE 77

la contrainte que l’on désire ajouter.

Si B est la base optimale obtenue avant d’ajouter cette contrainte, on a

X
xi + aij xj = bi , ∀i ∈ I(B)
j∈J(B)

et la nouvelle contrainte peut s’écrire

 
X X X
am+1,i bi − aij xj  + am+1,j xj + s = bm+1
i∈I(B) j∈J(B) j∈J(B)

ou encore
X
a0m+1,j xj + s = b0m+1 ,
j∈J(B)

où ( P
a0m+1,j = am+1,j − i∈I(B) am+1,i aij
P
b0m+1 = bm+1 − i∈I(B) am+1,i bi .
L’adjonction de cette ligne et de la colonne s au tableau Simplexe donne un
nouveau tableau contenant une matrice unité et où les Zj − cj sont inchangés
(Zj − cs étant nul).

Si b0m+1 ≥ 0, la solution optimale est inchangée : la contrainte supplémentaire

n’a pas perturbé le problème initial.

Sinon, on est dans les conditions d’application de l’algorithme dual Simplexe.

78 CHAPITRE 8. L’ALGORITHME DUAL SIMPLEXE
79

Deuxième partie

Applications dans les graphes

Chapitre 1

Quelques problèmes de la théorie des

graphes

1.1 Définitions
– Un graphe orienté est un couple (X,U ), où X est un ensemble fini d’éléments
appelés sommets et U est un sous-ensemble de X × X, dont les éléments
sont appelés arcs.
Les sommets du graphe sont représentés par des points et les arcs par des
flèches joignant ces points. Sauf mention contraire, nous supposons qu’il
existe au plus une flèche dans chaque sens entre deux points.

Exemple

x1 x3

x6
x4
x5

X = {x1 ,x2 ,x3 ,x4 ,x5 ,x6 } U = {(x1 ,x2 ),(x2 ,x1 ),(x3 ,x4 ),(x4 ,x4 ),(x5 ,x2 )}
82CHAPITRE 1. QUELQUES PROBLÈMES DE LA THÉORIE DES GRAPHES

– Un chemin dans (X,U ) est une suite de sommets telle que si xk et x` sont
deux sommets consécutifs de cette suite, alors (xk ,x` ) ∈ U . Dans l’exemple
précédent, (x5 ,x2 ,x1 ,x2 ) est un chemin.
Un circuit dans (X,U ) est un chemin dont le dernier sommet coı̈ncide avec
le premier.
Un chemin (circuit) est dit élémentaire s’il contient une et une seule fois
chacun des sommets qui le constituent (excepté le sommet initial dans le
cas du circuit).
Un chemin (circuit) est dit hamiltonien s’il contient une et une seule fois
chacun des sommets du graphe (excepté le sommet initial dans le cas du
circuit).
Un chemin (circuit) est dit eulérien s’il passe une et une seule fois par chaque
arc du graphe.
– Le sous-graphe d’un graphe (X,U ) engendré par Y ⊂ X est le graphe dont
les sommets sont les éléments de Y et dont les arcs sont les éléments de U
qui ont leurs extrémités dans Y .
– Le graphe partiel d’un graphe (X,U ) engendré par V ⊂ U , est le graphe
(X,V ).
Un sous-graphe partiel est un sous-graphe d’un graphe partiel.
– La matrice d’adjacence du graphe (X,U ) où {X = {x1 ,x2 , . . . ,xn } est la
matrice carrée A = (aij ), à n2 éléments, où
(
aij = 1 ssi (xi ,xj ) ∈ U,
aij = 0 ssi (xi ,xj ) 6= U.
La matrice d’adjacence de l’exemple ci-dessus est

x1 x2 x3 x4 x5 x6
 
0 1 0 0 0 0
x1  
 1 0 0 0 0 0 
x2 



x3  0 0 0 1 0 0 
 
 
x4  0 0 0 1 0 0 
 
x4 
 0 1 0 0 0 0 

 
x6 0 0 0 0 0 0
1.1. DÉFINITIONS 83

– Un graphe non orienté est un couple (X,E), où X est un ensemble fini
d’éléments appelés sommets et E est un ensemble de paires de sommets
appelées arêtes. Les sommets sont représentés par des points et les arêtes
par des lignes joignant ces points. Sauf mention contraire, nous consdérons
des graphes simples, c’est-à-dire où
1) entre deux sommets, il existe au plus une arête,
2) il n’existe pas d’arête du type {x,x}
Exemple

x1 x3

x6
x4
x5

X = {x1 ,x2 ,x3 ,x4 ,x5 ,x6 } E = {{x1 ,x2 },{x2 ,x4 },{x2 ,x5 },{x3 ,x4 }}

Remarque
Tout graphe orienté symétrique (i.e. où (xi ,xj ) ∈ U ⇒ (xj ,xi ) ∈ U ) et sans
boucle peut être représenté, sans perte d’information, par un graphe non
orienté, et vice-versa.
– Une chaine dans (X,E) est une suite de sommets telle que si xk et x` sont
deux sommets consécutifs de cette suite, alors {xk ,x` } ∈ E.
– Un cycle dans (X,E) est une chaı̂ne dont le dernier sommet coı̈nicide avec
le premier.
Ces notions peuvent aussi être utilisées pour les graphes orientés dans les
cas où l’orientation des arcs n’est pas prise en considération.
84CHAPITRE 1. QUELQUES PROBLÈMES DE LA THÉORIE DES GRAPHES

– Les termes “élémentaire, hamiltonien, eulérien, sous-graphe, graphe partiel”

se définissent comme précédemment.
La matrice d’adjacence d’un graphe non orienté est symétrique.
– La matrice d’incidence du graphe (X,E), où X = {x1 ,x2 , . . . ,xn } et où E =
{e1 ,e2 , . . . ,em } est la matrice B = (bij ) à n lignes et m colonnes, où
(
bij = 1 ssi xi ∈ ej ,
bij = 0 ssi xi 6∈ ej .

– Un graphe (orienté ou non) est valué si à chaque arc (ou arête) est associée
une valeur.
1.2. NIVEAUX, RANGS ET CIRCUITS DANS LES GRAPHES ORIENTÉS85

1.2 Niveaux, rangs et circuits dans les graphes

orientés
Soit (X,U ) un graphe orienté. Notons

Γ(x) = {y ∈ X : (x,y) ∈ U }

l’ensemble des “successeurs directs” de x.

Considérons les ensembles suivants :



 X(0) = {x ∈ X : Γ(x) = ∅},




 X(1) = {x ∈ X \ X(0) : Γ(x) ⊂ X(0)},



 X(2) = {x ∈ X \ (X(0) ∪ X(1)) : Γ(x) ⊂ X(0) ∪ X(1)},

..


 .




 X(k) = {x ∈ X \ (X(0) ∪ . . . ∪ X(k − 1)) : Γ(x) ⊂ X(0) ∪ . . . ∪ X(k − 1)}



 ..
.
Ces ensembles, appelés niveaux de graphe (X,U ), ont les propriétés suivantes
(à démontrer à titre d’exercice)
1) ils sont disjoints 2 à 2;
2) leur réunion donne X ssi le graphe est sans circuit
3) x ∈ X(k) ssi le plus long chemin issu de x est de longueur k (longueur =
nombre d’arcs)
Intuitivement, X(0) est l’ensemble des sommets “terminaux” du graphe, X(1)
est l’ensemble des sommets non terminaux dont tous les successeurs directs sont
terminaux (les plus longs chemins issus de X(1) sont donc de longueur 1), ...,
X(k) est l’ensemble des sommets qui n’appartiennent pas aux niveaux inférieurs
mais dont tous les successeurs directs appartiennent aux niveaux inférieurs ( de
tout sommet de X(k) est issu au moins un chemin de longueur k et aucun chemin
plus long).

L’obtention des niveaux d’un graphe est importante dans certaines applications,
notamment dans les problèmes d’ordonnancement. On peut la réaliser par l’ap-
plication de l’algorithme suivant.

1. Considérer la matrice d’adjacence du graphe et poser k = 0

86CHAPITRE 1. QUELQUES PROBLÈMES DE LA THÉORIE DES GRAPHES

2. X(k) est l’ensemble des sommets correspondant aux lignes non barrées ne
contenant que des 0 ou des 1 barrés;
si X(k) = ∅, aller en 4.;
sinon, barrer les lignes et les colonnes correspondant aux sommets de X(k),
et aller en 3.

3. Faire k = k + 1 et aller en 2.

4. X(0),X(1), . . . ,X(k − 1) sont les k niveaux du graphe.

En vertu de ce qui précède, cet algorithme permet également de tester l’absence

ou l’existence de circuits dans un graphe : le graphe sera sans circuit ssi, au terme de
l’algorithme précédent, toutes les lignes ont été barrées.

Exemple

1 2 3 4 5 6
1 0 1 1 1 1 1
2 0 0 1 0 0 0
3 0 0 0 0 0 0
4 0 0 1 0 0 0
5 1 0 0 1 0 1
6 1 0 1 1 0 0

1. On barre la ligne et la colonne 3

2. On barre les lignes et les colonnes 2 et 4

3. Il n’est plus possible de barrer une ligne.

Conclusions :

 X(0) = {3}


 X(1) = {2,4}
 Le graphe admet au moins un circuit.
1.2. NIVEAUX, RANGS ET CIRCUITS DANS LES GRAPHES ORIENTÉS87

2 3

1 4

6 5

Pour obtenir un circuit, on peut procéder comme suit :

1. A la fin de l’algorithme permettant de trouver les niveaux du graphe on

choisit une ligne non barrée; soit i1 .
2. Soit C = {i1 ,i2 , . . . ,ip } les lignes non barrées choisies jusquà présent; choisir
un l non barré dans la ligne ip (on est sûr qu’il existe puisque ip est non
barrée) : il appartient à une colonne d’indice ip+1 .
3. Si ip+1 ∈ C, on a le circuit (xip+1 ,xip+1 +1 , . . . ,xip+l ).
Sinon on ajoute ip+1 dans C et on retourne en 2.

Application à l’exemple précédent

i1 = 1
C = {1} i2 = 5
C = {1,5} i3 = 1 ⇒ circuit (1,5,1)
ou
i3 = 6
C = {1,5,6} i4 = 1 ⇒ circuit (1,5,6,1)

Les rangs d’un graphe s’obtiennent de manière analogue aux niveaux, mais on
considère les prédécesseurs des sommets au lieu de leurs successeurs (dans l’algo-
rithme, on travaille sur les colonnes au lieu de travailler sur les lignes).
Déterminer les niveaux (ou les rangs) d’un graphe offre un moyen pratique de
numéroter les sommets du graphe de telle sorte que si un sommet en précède un
autre, il reçoive un numéro supérieur (ou inférieur)
88CHAPITRE 1. QUELQUES PROBLÈMES DE LA THÉORIE DES GRAPHES

Exemple

1 2 3 4 5 6
1 0 1 0 0 1 0
2 0 0 1 0 0 0
3 0 0 0 1 0 0
4 0 0 0 0 0 0
5 0 0 0 1 0 0
6 0 0 0 0 0 0

Niveaux Rangs
0 {4,6} {1,6}
1 {5,3} {2,5}
2 {2} {3}
3 {1} {4}
1.3. L’ARBRE PARTIEL MINIMUM 89

1.3 L’arbre partiel minimum

Définition : un arbre est un graphe simple sans cycle et tel qu’il existe une chaı̂ne
entre toute paire de sommets.

Exemple

Propriétés (à démontrer à titre d’exercice)

1. Il existe au moins un sommet se trouvant sur une seule arête.

2. Si l’arbre a n sommets, alors il a exactement n − 1 arêtes.
3. L’addition d’une arête crée un et un seul cycle.
4. Chaque paire de sommets est reliée par une chaı̂ne (et une seule) et la
suppression d’une arête enlève cette propriété.

Problème de l’arbre partiel minimum dans un graphe simple valué

Etant donné un graphe simple valué, il s’agit de rechercher un graphe partiel qui
soit un arbre et dont la somme des valeurs des arêtes soit minimum.

Exemple

1 2 1 2
6 6
8
15 12
10
4 4
11 11
14 9
7 13 7
3 3
90CHAPITRE 1. QUELQUES PROBLÈMES DE LA THÉORIE DES GRAPHES

Applications

Problèmes de télécommunications, de distribution.

Résolution du problème

Dans ce qui suit, on suppose remplies les deux conditions suivantes :

– le graphe est complet (il existe une arête entre toute paire de sommets)
– toutes les arêtes ont des valeurs différentes.
Si la première condition n’est pas satisfaite, il suffit d’ajouter les arêtes man-
quantes en leur donnant une valeur très grande (en tout cas plus grande que
la somme des valeurs des arêtes existantes). Si la deuxième condition n’est pas
satisfaite, on modifie très légèrement la valeur de certaines arêtes, en veillant à
ne pas modifier l’ordre des valeurs des arêtes.

Théorème de base
Pour tout ensemble de sommets A ⊂ X, nous notons EA l’ensemble des arêtes
qui ont une extrémité dans A et une extrémité dans X \ A.
Si H = (X,F ) est un arbre partiel minimum dans G = (X,E) alors ∀A ⊂ X, F
contient l’arête de valeur minimum de EA .

Démonstration.
Soit A ⊂ X et soit e l’arête de valeur minimum de EA .
Supposons que e 6∈ F ; dans ce cas, F ∪{e} contient un cycle qui doit nécessairement
contenir une autre arête e0 de EA puisque e relie A à X \ A. Si on définit

F 0 = [F ∪ {e}] \ {e0 },

alors (X,F 0 ) est un arbre partiel dont la valeur est inférieure à celle de (X,F ).
En effet :

– le seul cycle C a été détruit par la suppression de e0 ;

– toute chaı̂ne qui joignait 2 sommets en empruntant l’arête e0 pourra encore
le faire en empruntant les autres arêtes du cycle C;
– la valeur de F 0 est inférieure à celle de F puisque e est l’arête de valeur
minimum de EA .
1.3. L’ARBRE PARTIEL MINIMUM 91

(C.Q.F.D.)

Algorithme de PRIM

1. Choisir arbitrairement un sommet et marquer l’arête de valeur minimum

issue de ce sommet;
2. Soit Â l’ensemble des sommets extrémités des arêtes marquées.
Si Â = X, aller en 4.
Sinon, aller en 3.
3. Marquer l’arête de valeur minimum joignant un sommet de Â à un sommet
de X \ Â et aller en 2.
4. L’ensemble des arêtes marquées fournit l’arbre partiel minimum.

La justification de cet algorithme résulte immédiatement du théorème précédent.

Cet algorithme est intéressant lorsque l’on doit procéder manuellement. Il en est
de même de l’algorithme suivant.

Algorithme de KRUSKAL

1. Marquer l’arête de valeur minimum.

2. Soit Ê l’ensemble des arêtes marquées.
Si Ê = |X| − 1, aller en 4.
Sinon, aller en 3.
3. Parmi les arêtes qui ne forment pas de cycle avec Ê, marquer celle de valeur
minimum et aller en 2.
4. Ê fournit l’arbre partiel minimum.

La justification de cet algorithme résulte immédiatement du théorème précédent.

Pour des graphes de grande taille, il semble que l’algorithme suivant soit l’un des
plus efficaces.

Algorithme de SOLLIN

1. Pour chaque sommet, marquer l’arête de valeur minimum issue de ce som-

met.
2. Retrécir le graphe et retourner en 1.
92CHAPITRE 1. QUELQUES PROBLÈMES DE LA THÉORIE DES GRAPHES

Retrécir le graphe consiste à remplacer chaque arbre partiel maximal (c’est-

à-dire non inclus dans un autre arbre partiel) par un sommet. Si, au cours de
cette opération, un ensemble A de sommets est remplacé par un sommet a, tout
sommet x qui était joint à un sommet de A sera joint à a par une arête dont la
valeur sera la plus petite parmi celles des arêtes entre x et les sommets de A. La
justification de cet algorithme résulte immédiatement du théorème précédent.
1.4. PROBLÈMES DE COLORATION 93

1.4 Problèmes de coloration

Colorer les sommets d’un graphe consiste à les numéroter (ou à leur attribuer
une couleur) de telle sorte que deux sommets adjacents (joints par une arête) ne
soient pas affectés d’un même nombre (d’une même couleur).
Le nombre chromatique d’un graphe est le plus petit nombre de couleurs nécessaires
pour colorer ses sommets. L’obtention du nombre chromatique γ(G) d’un graphe
G = (X,E) et d’une coloration en γ(G) couleurs sont des problèmes difficiles.
Bien qu’il existe des méthodes exactes (par exemple en utilisant une procédure
de séparation et d’évaluation), on a souvent recours, pour les graphes compre-
nant un grand nombre de sommets, à des méthodes heuristiques. Pour avoir une
idée de la valeur de la solution obtenue, on se base sur des résultats théoriques
fournissant des bornes pour le nombre chromatique.

Exemples de bornes

n2
γ(G) ≥ ,
n2 − 2m
n
γ(G) ≥ ,
n − mini di
γ(G) ≤ max di + 1,
i

où n,m et di désignent respectivement le nombre de sommets, le nombre d’arêtes

et les degrés des sommets du graphe (le degré d’un sommet est le nombre d’arêtes
issues de ce sommet).
L’algorithme heuristique suivant est basé sur la dernière borne.

Algorithme de coloration de WELSH et POWELL

1. Numéroter les sommets du graphe suivant l’ordre décroissant de leur degré
i = 1 et N = X.
2. Donner au sommet de N qui a le plus petit numéro la couleur i.
3. Soit Ni l’ensemble des sommets non colorés qui ne sont adjacents à aucun
sommet de couleur i.
Si Ni 6= ∅, faire N = Ni et aller en 2.
Si Ni = ∅, aller en 4.
94CHAPITRE 1. QUELQUES PROBLÈMES DE LA THÉORIE DES GRAPHES

4. Poser N = l’ensemble des sommets non encore colorés

Si N 6= 0, faire i = i + 1 et aller en 2.
Si N = ∅, on a une coloration en i couleurs.

Exemple : l’application de l’algorithme au graphe dont la matrice d’adjacence est

ci-dessous donne une coloration en 3 couleurs (solution non optimale)
 
0 0 1 0 0 1 1 0
 
 0 0 1 1 0 0 1 
 
 0 1 0 0 0 0 
 
 

 0 0 0 0 0 

 

 0 1 0 0 

 
 0 0 0 
 
 
 0 0 
0

Applications

Un certain nombre de problèmes concrets se ramènent naturellement à des problèmes

de coloration, comme par exemple les problèmes d’horaires, certains problèmes de
typologie, de chargements de camions, d’allocations de ressources, ... Le problème
de la coloration des cartes de géographie se ramène à la coloration des graphes
planaires et pose le “fameux problème des 4 couleurs”.
1.5. GRAPHES PLANAIRES 95

1.5 Graphes planaires

Un graphe non orienté est planaire s’il est possible de le dessiner dans le plan
de telle sorte que deux arêtes quelconques ne se rencontrent pas en dehors de
leurs extrémités.

Exemple

1 2 1 2

3
3

5 4 5 4

Ce graphe est planaire

Application : circuits imprimés.

Les arêtes d’un graphe planaire délimitent des surfaces planes qu’on appelle
faces (une des faces est infinie).

Propriétés

Soit n,m et f respectivement le nombre de sommets, le nombre d’arêtes et le

nombre de faces d’un graphe planaire. On a alors

 n − m + f = 2 (formule d’Euler)

m ≤ 3(n − 2)


f ≤ 2(n − 2)

2 graphes non planaires particuliers

96CHAPITRE 1. QUELQUES PROBLÈMES DE LA THÉORIE DES GRAPHES

Graphe complet à 5 sommets Graphe “des villas et des usines”

Reconnaissance des graphes planaires

Si l’on ajoute d’une manière quelconque des sommets sur les arêtes des 2 graphes
ci-dessus, on obtient les graphes de Kuratowski (qui ne sont évidemment pas pla-
naires).

Théorème
Une condition nécessaire et suffisante pour qu’un graphe soit planaire est qu’il
n’admette aucun sous-graphe partiel qui soit un graphe de Kuratowski.

Ce théorème est à la base d’un algorithme permettant de savoir si un graphe

est planaire ou non (voir 1 ).
On peut également caractériser les graphes planaires au moyen du concept de
graphe dual ou encore en termes de bases de cycles du graphe (voir bibliographie).

1. Picard, C. : “Graphes complémentaires et graphes planaires”, Revue Francçaise de Re-

cherche Opérationnelle, 8, 1964, p. 329-343.
1.6. RECHERCHE DE CHEMINS DE VALEUR EXTREMUM DANS UN GRAPHE VALU É97

1.6 Recherche de chemins de valeur extremum

dans un graphe valué
1.6.1 Définition du problème
Soit (X,U ) un graphe orienté tel qu’à chaque arc (xi ,xj ) soit associée une
valeur cij (représentant un coût, un délai, une longueur, une capacité, ...). On
se propose de rechercher un chemin d’un sommet x1 à un sommet xn de telle
sorte que la somme des valeurs des arcs qui composent ce chemin soit minimum
(maximum).

Afin de faciliter la présentation des algorithmes, on posera systématiquement,

pour un problème à minimum:
(
cij = +∞ si (xi ,xj ) 6∈ U et i 6= j,
cii = 0,∀i.
Pour un problème à maximum, on aura
(
cij = −∞ si (xi ,xj ) 6∈ U et i 6= j,
cii = 0,∀i.
Remarquons encore qu’un problème à maximum peut toujours se ramener à un
problème à minimum en posant

c0ij = −cij , ∀i,j.

On verra cependant que certains algorithmes exigent des cij ≥ 0 et ne sont donc
applicables que pour des problèmes à minimum.

1.6.2 Algorithme de FORD

1.6.2.1 Algorithme

– On pose λ1 = 0 et λi = +∞, ∀i 6= 1.
– On cherche un arc (xi ,xj ) tel que

λj − λi > cij

et on remplace λj par
λ0j = λi + cij .
98CHAPITRE 1. QUELQUES PROBLÈMES DE LA THÉORIE DES GRAPHES

– On continue ainsi jusqu’à ce qu’aucun arc ne permette de diminuer les λi .

– Il existe nécessairement un sommet xp1 tel que

λ n − λ p1 = c p1 n ,

un sommet xp2 tel que

λ p1 − λ p2 = c p2 p1 ,

et ainsi de suite jusqu’à ce que xpk = x1 .

Théorème
Le chemin (x1 xpk−1 xpk−2 . . . xp1 xn ) est optimal.

Démonstration : soit (x1 xq1 xq2 . . . xqr xn ) un chemin quelconque de valeur Q. Par
construction, on a
λq1 − λ1 ≤ c1q1 ,
λ q2 − λ q1 ≤ c q1 q2 ,
..
.
λ n − λ qr ≤ c qr n .
En additionnant ces égalités, on obtient, puisque λ1 = 0:

λn ≤ Q.

Or λn est la valeur du chemin (x1 xpk−1 . . . xp1 xn ).

C.Q.F.D.

1.6.2.2 Convergence de l’algorithme

L’algorithme se termine en un nombre fini d’étapes à condition que le graphe

ne contienne aucun circuit de valeur négative.

1.6.2.3 Exemple numérique

Trouver les chemins de valeur minimum entre x1 et les autres sommets du

graphe suivant
1.6. RECHERCHE DE CHEMINS DE VALEUR EXTREMUM DANS UN GRAPHE VALU É99

x2 2 x4
cij x1 x2 x3 x4 x5
3
5 x1 0 3 2 ∞ ∞
5 3
x1 x2 ∞ 0 5 2 ∞
7 x5 x3 ∞ ∞ 0 3 7
2
x4 ∞ ∞ ∞ 0 5
x3 x5 ∞ ∞ ∞ ∞ 0

L’application de l’algorithme de FORD donne successivement :

λ1 = 0 et λi = +∞, ∀i;
λ2 − λ1 > 3 ⇒ λ02 = 3;
λ3 − λ1 > 2 ⇒ λ03 = 2;
λ4 − λ02 > 2 ⇒ λ04 = 5;
λ5 − λ04 > 5 ⇒ λ05 = 10;
λ05 − λ03 > 7 ⇒ λ005 = 9.

Il n’est plus possible de diminuer un λi et on a

λ5 ” − λ03 = c35 et λ03 − λ1 = c13 :

(x1 x3 x5 ) est donc un chemin de valeur minimum de x1 à x5 ;

λ04 − λ03 = c34 et λ03 − λ1 = c13 :

(x1 x3 x4 ) est un chemin de valeur minimum de x1 à x4 .

Les autres chemins optimaux sont (x1 x1 ), (x1 x2 ), (x1 x3 ) et (x1 x2 x4 ).

1.6.2.4 Autre exemple numérique

Trouver les chemins de valeur minimum entre x1 et les autres sommets du

graphe suivant
100CHAPITRE 1. QUELQUES PROBLÈMES DE LA THÉORIE DES GRAPHES

cij x1 x2 x3 x4 x5 x6 x7
x1 0 7 3 8 ∞ ∞ ∞
x2 ∞ 0 ∞ ∞ 3 ∞ ∞
x2 3 x5 x3 ∞ 3 0 ∞ 10 8 15
7 1
x1 3
10 x6
3
8
x4 ∞ ∞ 2 0 ∞ ∞ 9
6
x3 15 x5 ∞ ∞ ∞ ∞ 0 1 ∞
8 x7
2
9 x6 ∞ ∞ ∞ ∞ ∞ 0 6
x4 x7 ∞ ∞ ∞ ∞ ∞ ∞ 0

λ1 = 0 et λi = ∞, ∀i;
λ2 − λ1 > 7 ⇒ λ02 = 7;
λ3 − λ1 > 3 ⇒ λ03 = 3;
λ4 − λ1 > 8 ⇒ λ04 = 8;
λ5 − λ02 > 3 ⇒ λ05 = 10
λ6 − λ03 > 8 ⇒ λ06 = 11;
λ7 − λ03 > 15 ⇒ λ07 = 18;
λ07 − λ06 > 6 ⇒ λ007 = 17;
λ02 − λ03 > 3 ⇒ λ002 = 6;
λ05 − λ002 > 3 ⇒ λ005 = 9;
λ06 − λ005 > 1 ⇒ λ006 = 10;
λ7 ” − λ006 > 6 ⇒ λ000
7 = 16;


λ000 00
7 − λ6 = c67  


00 00
λ6 − λ5 = c56  


00 00
 chemin optimal (x1 x3 x2 x5 x6 x7 ), ce qui donne les
λ5 − λ2 = c25 ⇒

λ002 − λ03 = c32 
 chemins optimaux de x1 à x2 ,x3 ,x5 ,x6 et x7 .




0
λ −λ =c 
3 1

13

λ04 − λ1 = c14 ⇒ (x1 x4 ) est le chemin optimal de x1 à x4 .

1.6. RECHERCHE DE CHEMINS DE VALEUR EXTREMUM DANS UN GRAPHE VALU É101

1.6.3 Algorithme de BELLMAN-KALABA

Il est basé sur le principe suivant : si le chemin (x1 ,x2 , . . . ,xi , . . . ,xr , . . . ,xj . . . ,xn )
est optimal entre x1 et xn , alors le chemin (xi . . . xr . . . xj ) est optimal entre xi et
xj (démonstration triviale).

1. Hypothèses particulières à l’algorithme : aucune

2. Algorithme : on va calculer successivement les quantités λi (1), i = 1,2, . . .
λi (2), i = 1, . . . ,n; . . . où λi (k) représentera la valeur du chemin optimal
allant de x1 à xi et composé de k arcs au plus.
Il est clair que (
λ1 (1) = 0,
λi (1) = c1i , i = 2, . . . ,n.
D’autre part, en vertu du principe énoncé ci-dessus, on aura, ∀k = 2, . . .
(
λ1 (k) = 0,
λi (k) = minj∈{1,2,...,n} , {λj (k − 1) + cji }.

L’algorithme s’arrête dès qu’on obtient une valeur k telle que

λi (k) = λi (k − 1), ∀i,

c’est-à-dire lorsqu’il n’est plus possible d’améliorer les valeurs des chemins
optimaux allant de x1 aux xi .

Ayant les valeurs de chemins optimaux à chaque étape, il est facile de

reconstituer ces chemins.
3. Convergence de l’algorithme

Si le graphe ne contient aucun circuit ayant une valeur négative, alors il

est clair que le chemin optimal ne passera jamais deux fois par le même
sommet. Par conséquent, l’algorithme s’arrêtera au bout de n − 1 étapes au
plus (ce sera en particulier le cas si cij ≥ 0, ∀i,j).

On se rendra donc compte de l’existence de circuits négatifs s’il existe i tel

que λi (n) 6= λi (n − 1). Dans ce cas, l’algorithme ne converge pas puisque
certains chemins optimaux auront comme valeur −∞ (en empruntant une
infinité de fois des circuits négatifs).
102CHAPITRE 1. QUELQUES PROBLÈMES DE LA THÉORIE DES GRAPHES

4. Remarque

L’algorithme peut être adapté à la recherche des chemins de valeur maxi-

mum. Il suffit de calculer

λi (k) = max{λj (k − 1) + cji }.

Dans ce cas-ci, ce sont les circuits positifs qui sont gênants.

5. Exemple numérique
Trouver les chemins de valeur minimum entre x1 et les autres sommets du
graphe suivant

76: : 7<;
>
= =
798 >
: 74=
@
7?>

λi (2) λi (1) x1 x2 x3 x4 x5
0 0 0 3 2 ∞ ∞
3 3 ∞ 0 5 2 ∞
2 2 ∞ ∞ 0 3 7
5 ∞ ∞ ∞ ∞ 0 5
9 ∞ ∞ ∞ ∞ ∞ 0
0(1) 3(1) 2(1) 5(2) 9(3) λi (2)
0(1) 3(1) 2(1) 5(2) 9(3) λi (3)

(le chiffre entre parenthèse désigne l’indice du sommet précédent sur le

chemin).
1.6. RECHERCHE DE CHEMINS DE VALEUR EXTREMUM DANS UN GRAPHE VALU É103

Chemins optimaux : (x1 ,x1 )

(x1 ,x2 )
(x1 ,x3 )
(x1 ,x2 ,x4 )
(x1 ,x3 ,x5 )

6. Autre exemple numérique

Trouver les chemins de valeur minimum entre x1 et les autres sommets du
graphe suivant.

x2 3 x5
7 1
x1 3
10 x6
3
8
6
x3 15
8 x7
2
9
x4

λi (5) λi (4) λi (3) λi (2) λi (1) x1 x2 x3 x4 x5 x6 x7

0 0 0 0 0 0 7 3 8 ∞ ∞ ∞
6 6 6 6 7 ∞ 0 ∞ ∞ 3 ∞ ∞
3 3 3 3 3 ∞ 3 0 ∞ 10 8 15
8 8 8 8 8 ∞ ∞ 2 0 ∞ ∞ 9
9 9 9 10 ∞ ∞ ∞ ∞ ∞ 0 1 ∞
10 10 11 11 ∞ ∞ ∞ ∞ ∞ ∞ 0 6
16 17 17 17 ∞ ∞ ∞ ∞ ∞ ∞ ∞ 0
0(1) 6(3) 3(1) 8(1) 10(2) 11(3) 17(4) λi (2)
0(1) 6(3) 3(1) 8(1) 9(2) 11(3) 17(4) λi (3)
0(1) 6(3) 3(1) 8(1) 9(2) 10(5) 17(4) λi (4)
0(1) 6(3) 3(1) 8(1) 9(2) 10(5) 16(6) λi (5)
0(1) 6(3) 3(1) 8(1) 9(2) 10(5) 16(6) λi (6)
104CHAPITRE 1. QUELQUES PROBLÈMES DE LA THÉORIE DES GRAPHES

Chemins optimaux : (x1 ,x1 ),(x1 ,x3 ,x2 ),(x1 ,x3 ),(x1 ,x4 )
(x1 ,x3 ,x2 ,x5 ),(x1 ,x3 ,x2 ,x5 ,x6 ),
(x1 ,x3 ,x2 ,x5 ,x6 ,x7 )

1.6.4 Algorithme de DIJKSTRA

1. Hypothèse : cij ≥ 0, ∀i,j
2. Algorithme

Notons

– λi (k) la marque du sommet i à l’étape k,

– λ̄i la marque définitive du sommet i,
– M (k) l’ensemble des sommets marqués définitivement à la fin de l’étape
k,
– nk le numéro du sommet marqué définitivement à l’étape k (sa marque
étant donc λnk ).

Etape 1:


 λi (1) = c1i , ∀i 6= 1


 λ1 (1) = 0 = λ̄1


 n1 = 1


M (1) = {1}
Etape k + 1:

λ (k + 1) = min{λi (k), λ̄nk + cnk i }, ∀i 6∈ M (k)
 i

λ̄nk+1 = mini λi (k + 1)


M (k + 1) = M (k) ∪ {nk+1 }.

Comme on le voit, à chaque étape, un nouveau sommet reçoit une marque

définitive : c’est celui qui, à cette étape, a la plus petite marque parmi les
sommets non encore marqués définitivement.
L’algorithme se termine lorsque xn est marqué définitivement : il comporte
donc au plus n étapes.
Pour justifier l’algorithme, nous allons démontrer la proposition suivante.
1.6. RECHERCHE DE CHEMINS DE VALEUR EXTREMUM DANS UN GRAPHE VALU É105

3. Proposition
1) λi (k) est la valeur du chemin optimal de x1 à xi parmi ceux qui ne
passent que par des sommets de M (k − 1);
2) λ̄nk est la valeur du chemin optimal de x1 à xnk et il ne passe que par
des sommets de M (k − 1).

Démontration (par récurrence)

La proposition est triviale pour k = 1 (en posant M (0) = ∅).

Supposons qu’elle soit vraie pour k et démontrons qu’alors elle est vraie
pour k + 1.
Par hypothèse λi (k) est donc la valeur du chemin optimal de x1 à xi parmi
ceux qui ne passent que par des sommets de M (k − 1); de plus λ̄nk est la
valeur du chemin optimal de x1 à xnk et ce chemin ne passe que par des
sommets de M (k − 1).
Par conséquent
λi (k + 1) = min{λi (k),λ̄nk + cnk i }
est la valeur du chemin optimal de x1 à xi parmi ceux qui ne passent que
par des sommets de M (k − 1) et éventuellement par le sommet xnk : c’est
donc bien la valeur du chemin optimal de x1 à xi parmi ceux qui ne passent
que par des sommets de M (k).
Il en résulte que
λ̄nk+1 = min λi (k + 1)
i
est la valeur du chemin optimal de x1 à xnk+1 parmi ceux qui ne passent
que par des sommets de M (k).
Il reste à démontrer que λ̄nk+1 est la valeur du chemin optimal de x1 à
xnk+1 . Si ce n’était pas le cas, il existerait un chemin de valeur inférieure
et ce chemin devrait passer par au moins un sommet n’appartenant pas à
M (k).
Appelons j le premier sommet n’appartenant pas à M (k) rencontré par ce
chemin : on aurait alors

λj (k + 1) ≤ µ < λ̄nk+1 ,

ce qui est impossible.

106CHAPITRE 1. QUELQUES PROBLÈMES DE LA THÉORIE DES GRAPHES

4. Exemple numérique
Trouver les chemins de valeur minimum entre x1 et les autres sommets du
graphe suivant.

A6C C A<D
F
E E
A9B F
C A4E
G
A?F

λ̄i x1 x2 x3 x4 x5
0 0 3 2 ∞ ∞
3 ∞ 0 5 2 ∞
2 ∞ ∞ 0 3 7
5 ∞ ∞ ∞ 0 5
9 ∞ ∞ ∞ ∞ 0
0 3(1) 2(1) ∞ ∞ λi (1)
3(1) 2(1) ∞ ∞ λi (2)
3(1) 5(3) 9(3) λi (3)
5(3) 9(3) λi (4)
9(3) λi (5)

5. Autre exemple numérique

Trouver les chemins de valeur minimum entre x1 et les autres sommets du
graphe suivant.
1.6. RECHERCHE DE CHEMINS DE VALEUR EXTREMUM DANS UN GRAPHE VALU É107

x2 3 x5
7 1
x1 3
10 x6
3
8
6
x3 15
8 x7
2
9
x4

λ̄i x1 x2 x3 x4 x5 x6 x7
0 0 7 3 8 ∞ ∞ ∞
6 ∞ 0 ∞ ∞ 3 ∞ ∞
3 ∞ 3 0 ∞ 10 8 15
8 ∞ ∞ 2 0 ∞ ∞ 9
9 ∞ ∞ ∞ ∞ 0 1 ∞
10 ∞ ∞ ∞ ∞ ∞ 0 6
16 ∞ ∞ ∞ ∞ ∞ ∞ 0
0 7(1) 3(1) 8(1) ∞ ∞ ∞ λi (1)
7(1) 3(1) 8(1) ∞ ∞ ∞ λi (2)
6(3) 8(1) 13(3) 11(3) 18(3) λi (3)
8(1) 9(2) 11(3) 18(3) λi (4)
9(2) 11(3) 17(4) λi (5)
10(5) 17(4) λi (6)
16(6) λi (7)
108CHAPITRE 1. QUELQUES PROBLÈMES DE LA THÉORIE DES GRAPHES
109

Chapitre 2

Les problèmes d’ordonnancement

2.1 Définition du problème

En vue de la réalisation d’un objectif (par exemple la construction d’une villa),
un certain nombre de tâches, d’opérations, doivent être effectuées (achat du ter-
rain, obtention du permis de construire, fondations, électricité ...). Le problème
d’ordonnancement consiste à déterminer la date de début de chaque tâche, sa-
chant que toute une série de contraintes doivent être satisfaites. Numérotons les
tâches 1,2, . . . ,i, . . . ,n et notons t(i) la date de début de la tâche i. Les contraintes
que l’on rencontre peuvent être de différents types.

2.1.1 Contraintes temporelles

2.1.1.1 Contraintes de localisation temporelle :

la tâche i doit débuter après la date a(i) :

t(i) ≥ a(i).

2.1.1.2 Contraintes de postériorité stricte :

la tâche j ne peut commencer qu’après l’achèvement de la tâche i :

t(j) ≥ t(i) + d(i),

où d(i) est la durée de la tâche i.

110 CHAPITRE 2. LES PROBLÈMES D’ORDONNANCEMENT

2.1.1.3 Contraintes de postériorité avec délai :

un délai minimum f (i,j) doit être respecté entre l’achèvement de i et le début

de j :
t(j) ≥ t(i) + d(i) + f (i,j).

2.1.1.4 Contraintes de postériorité partielle :

la tâche j ne peut commencer avant que la tâche i ait atteint un degré d’avan-
cement α(i,j) suffisant :

t(j) ≥ t(i) + α(i,j) · d(i),

où 0 ≤ α(i,j) ≤ 1.

2.1.1.5 Contraintes de continuité :

pour que la tâche j puisse débuter, il faut que le temps écoulé depuis le début
de la tâche i ne soit pas supérieur à tij :

t(j) − t(i) ≤ tij .

2.1.2 Contraintes sur les moyens mis en oeuvre

Encore appelées contraintes cumulatives, elles concernent les limitations de

matériels, financement et main d’oeuvre à un instant donné ou pendant une
période donnée.
Dans certains problèmes d’ordonnancement, les durées d(i) des tâches sont connues
avec certitude; dans d’autres, ce sont des variables aléatoires. Ce chapitre présente
quelques approches des problèmes d’ordonnancement. Une abondante littérature
est parue sur les nombreuses variantes de ces problèmes.

Remarque : nous ne traiterons pas ici du cas des contraintes disjonctives (liées
par la conjonction “ou”) pour lesquelles il vaut mieux, en général, adopter un
algorithme spécifique au problème traité.
2.2. LA MÉTHODE DU CHEMIN CRITIQUE 111

2.2 La méthode du chemin critique

Cette méthode ne prend en compte que les contraintes temporelles et suppose
les durées des tâches connues avec certitude (voir plus loin son adaptation au cas
incertain). Elle consiste à ramener la détermination du “timing” des opérations
à la recherche de chemins extrema dans un graphe valué.

2.2.1 Représentation du problème par un graphe valué

On considère un graphe contenant autant d’arcs qu’il y a de tâches à effectuer.
Le sommet initial de l’arc représente le début de la tâche et le sommet terminal
en représente la fin. Chaque arc est affecté d’un nombre traduisant la durée
de la tâche correspondante. On ajoute également à ce graphe deux sommets
supplémentaires représentant respectivement le début et la fin des travaux. Pour
représenter les contraintes temporelles du problème, on les écrit sous la forme
suivante:
t(j) ≥ [t(i) + d(i)] + α

et on trace un arc de valeur α depuis la fin de i jusqu’au début de j.

Exemples.
– La tâche j doit débuter au moins 5 semaines après le début des travaux :

t(j) ≥ [t0 + 0] + 5.

d(j)

debut des travaux

– La tâche j doit débuter au plus 5 semaines après le début des travaux :

t(j) ≤ t0 + 5,
112 CHAPITRE 2. LES PROBLÈMES D’ORDONNANCEMENT

ou
t0 ≥ [t(j) + d(j)] − d(j) − 5.

d(j)

-d(j)-5

debut des travaux

– La tâche j doit débuter exactement après 5 semaines :

t(j) ≥ [t0 + 0] + 5,
t0 ≥ [t(j) + d(j)] − d(j) − 5.

d(j)

-d(j)-5

debutdestavaux

– La tâche j ne peut débuter que lorsque la tâche i est achevée :

t(j) ≥ [t(i) + d(i)] + 0.

d(j)

d(i)
2.2. LA MÉTHODE DU CHEMIN CRITIQUE 113

– La tâche j doit débuter exactement 2 semaines après la fin de la tâche i :

t(j) = t(i) + d(i) + 2,

c’est-à-dire (
t(j) ≥ [t(i) + d(i)] + 2,
t(i) ≥ [t(j) + d(j)] − d(j) − d(i) − 2.

d(j)

2
-d(j)-d(i)-2

d(i)

– La tâche j doit débuter exactement 2 semaines après le début de la tâche

i:
t(j) = t(i) + 2,

c’est-à-dire (
t(j) ≥ [t(i) + d(i)] − d(i) + 2,
t(i) ≥ [t(j) + d(j)] − d(j) − 2.

d(j)

-d(i)+2 -d(j)-2

d(i)

– La fin de j doit suivre la fin de i d’au moins 5 semaines :

t(j) + d(j) ≥ t(i) + d(i) + 5,

ou encore
t(j) ≥ [t(i) + d(i)] + 5 − d(j).
114 CHAPITRE 2. LES PROBLÈMES D’ORDONNANCEMENT

d(j)

5-d(j)

d(i)

– La tâche j ne peut pas débuter tant que la moitié de la tâche i n’est pas
achevée :

d(i)
- 1 d(i)
2

d(j)

2.2.2 Simplification du graphe

Afin de limiter le nombre d’arcs et de sommets du graphe, on essaye autant
que possible de le simplifier. Ainsi, par exemple, deux sommets joints par un arc
de valeur 0 pourront être confondus.

0
d(i) d(j) d(i) d(j)
donne

Il faut cependant se garder d’introduire dans le graphe des contraintes qui n’y
existaient pas. Ainsi
2.2. LA MÉTHODE DU CHEMIN CRITIQUE 115

2.2.3 Ordonnancements au plus tôt et au plus tard

Il résulte de la mise en graphe que la date de début au plut tôt d’une tâche i
(notée ES(i) : Earliest Start of i) sera donnée par le chemin de valeur maximum
joignant le début des travaux au début de i.

En réalisant ce calcul pour chaque tâche, on obtient l’ordonnancement au plus

tôt et, par la même occasion, la durée totale minimum des travaux : soit T .
La date de fin au plus tôt de la tâche i (EF (i)) est évidemment égale à sa date
de début au plus tôt augmentée de sa durée.

La date de fin au plus tard de la tâche i (LF (i)) est celle dont le dépassement
provoquerait un allongement de la durée totale des travaux : elle s’obtient en
retranchant de T la valeur du chemin maximum entre la fin de i et la fin des
travaux. La date de début au plus tard de i (LS(i)) est évidemment égale à sa
date de fin au plus tard moins sa durée.

On obtient donc finalement les dates de début (et de fin) au plus tôt et au
plus tard de toutes les tâches, de manière à terminer les travaux en un temps T .

2.2.4 Remarques concernant l’algorithme

L’algorithme habituellement utilisé pour calculer les chemins de valeur maxi-
mum est celui de BELKMAN-KALABA : cela ne pose pas de problème puisqu’il
résulte de la nature du problème que le graphe ne peut pas contenir de circuit de
valeur > 0.

D’autre part, il arrive très fréquemment que le graphe obtenu ne contienne

aucun circuit; dans ce cas, on numérote les sommets (en calculant leur niveau)
et l’algorithme de BELLMAN-KALABA devient aussi rapide que l’algorithme de
DIJKSTRA (expliquer pourquoi).

2.2.5 Tâches critiques, marges totales et marges libres

Une tâche est critique si sa date de début au plut tôt coı̈ncide avec sa date
de début au plus tard : tout retard dans cette tâche fait reculer la date de fin
des travaux. Les tâches qui constituent les chemins de valeur maximum entre le
116 CHAPITRE 2. LES PROBLÈMES D’ORDONNANCEMENT

début et la fin des travaux sont évidemment critiques.

La marge totale de i est la différence enter sa date de début au plus tard et sa

date de début au plus tôt : c’est le retard que l’on peut se permettre sur i sans
perturber la durée totale des travaux.

La marge libre de i est le retard que l’on peut se permettre sur i sans perturber
les dates au plus tôt des tâches qui suivent : elle s’obtient en soustrayant la fin
au plus tôt de i du début au plus tôt des tâches qui la suivent et en prenant le
minimum des valeurs obtenues.

La connaissance des ordonnancements au plus tôt et au plus tard, des tâches

critiques et des marges est évidemment primordiale dans les problèmes de plan-
ning.

2.2.6 Exemple
En vue de l’exploitation d’une mine, on décide de construire un port sur le
canal qui passe non loin de là, une route et une voie de chemin de fer reliant la
mine au port et une cité ouvrière.
Le tableau suivant reprend les 10 tâches à effectuer, leur durée en mois et leurs
conditions de démarrage.

Tâches Durées Contraintes

PP : installation d’un port provisoire 2 -
D : déblai route et chemin de fer 3 -
MM : commande de matériel minier 5 -
MP : commande de matériel portuaire 6 -
IP : implantation du port définitif 2 après PP
R : construction de la route 4 après D
F : pose de la voie ferrée 1 après D
P : installation portuaire 8 après MP
C : construction de la cité 5 après PP, D, IP, R
M : installation minière 7 après D, MM, MP, F, P
2.2. LA MÉTHODE DU CHEMIN CRITIQUE 117

Mise en graphe

Graphe simplifié

IP(2)
PP(2)

R(4) C(5)
D(3) F(1)

MM(5) M(7)

MP(6) P(8)
118 CHAPITRE 2. LES PROBLÈMES D’ORDONNANCEMENT

Résolution du problème

Tâches Durées Tâches Début au Fin au Fin au Début Marge Marge Tâche
antérieures au plus plus tôt plus tard plus tard libre totale cri-
tôt E.S. E.F. L.F. L.S. tique
PP 2 - 0 2 14 12 0 12
D 3 - 0 3 12 9 0 9
MM 5 - 0 5 14 9 9 9
MP 6 - 0 6 6 0 0 0 *
IP 2 PP 2 4 16 14 3 12
R 4 D 3 7 16 12 0 9
F 1 D 3 4 14 13 10 10
P 8 MP 6 14 14 6 0 0 *
C 5 PP,D,IP,R 7 12 21 16 9 9
M 7 D,MM,MP, 14 21 21 14 0 0 *
F,P

durée totale minimum des travaux

2.2.7 Présentation des résultats

Indépendamment du tableau précédent, on peut présenter les résultats au

moyen du graphe simplifié à chaque sommet duquel sont associées

1. la date au plus tôt à laquelle peuvent commencer les tâches dont ce sommet
représente le début (case de gauche);

2. la date au plus tard à laquelle doivent finir les tâches dont ce sommet
représente la fin (case de droite).
2.2. LA MÉTHODE DU CHEMIN CRITIQUE 119

2 14
IP(2)
PP(2)
7 16
C(5)
D(3) R(4)
0 0 3 12 21 21
F(1)
MM(5) M(7)
MP(6) 14 14
P(8)
6 6

Ce graphe contient toute l’information du tableau précédent.

On peut aussi associer au problème traité un diagramme de GANTT où chaque

tâche est représentée par un segment qui commence au plus tôt et de longueur
proportionnelle à la durée de la tâche. Sa lecture est aisée et permet la prise
en compte des contraintes cumulatives (cf. plus loin). Par contre, il ne contient
pas toute l’information sur les contraintes temporelles. Le diagramme de GANTT
ci-dessous se rapporte à l’exemple précédent; on a prolongé chaque tâche en poin-
tillés jusqu’à sa date de fin au plus tard.

M
C
P
F
R
IP
MP
M
D
P

2 4 6 10 20
120 CHAPITRE 2. LES PROBLÈMES D’ORDONNANCEMENT

2.3 La méthodes des potentiels

Elle consiste également à ramener le problème d’ordonnancement à la re-
cherche de chemins optimaux dans un graphe, mais ce n’est plus le même graphe
que dans la méthode précédente. Il a l’avantage de permettre d’introduire de
nouvelles contraintes ou de modifier l’ordre de certaines tâches sans devoir être
complètement remanié. Sa construction est également plus simple.

2.3.1 Représentation du problème par un graphe

Les sommets du graphe sont les tâches à effectuer. Les arcs du graphe sont
associés aux contraintes du type.

t(j) − t(i) ≥ a(i,j),

appelées contraintes de potentiel; à l’arc (i,j) est associée la valeur a(i,j). On

ajoute au graphe les tâches “début” et “fin” des travaux, auxquelles on attri-
bue une durée nulle. Remarquons que toutes les contraintes temporelles sont des
contraintes de potentiel.

Exemples de contraintes traduites dans ce graphe

– Localisation temporelle : t(i) ≥ a(i).

0 a(i) i

où 0 est le sommet associé à la tâche “début des travaux”

– Postériorité stricte : t(j) ≥ t(i) + d(i)

i d(i) j
2.3. LA MÉTHODES DES POTENTIELS 121

– Postériorité avec délai : t(j) ≥ t(i) + d(i) + f (i,j)

i d(i)+f(i,j) j

– Postériorité partielle : t(j) ≥ t(i) + α(i,j) · d(i)

i (i,j) . d(i) j

– Continuité : t(j) − t(i) ≤ tij , ou encore, t(i) − t(j) ≥ tij

j -t ij i

– La tâche j doit démarrer exactement tij unités de temps après le début de

i. ( t ij
t(j) ≥ t(i) + tij
t(i) ≥ t(j) − tij i j

-tij

– La fin de j doit suivre la fin de i d’au moins tij unités de temps

t(j) + d(j) ≥ t(i) + d(i) + tij

ou
t(j) ≥ t(i) + d(i) + tij − d(j)
i d(i)+t-d(j) ij j

– La fin de j doit survenir exactement tij unités de temps après la fin de i

122 CHAPITRE 2. LES PROBLÈMES D’ORDONNANCEMENT

d(i) + t ij -d(j)

i j

d(i) - t ij-d(j)

– La tâche i doit démarrer exactement à la date a(i)

a(i)

0 i

-a(i)

La prise en compte simultanée des contraintes ne pose pas de problème.

2.3.2 Exemple
Le problème présenté au paragraphe 2.2.6 donne le graphe suivant.

2.3.3 Résolution du problème

Pour chaque sommet (tâche), on calcule le chemin de valeur maximum joi-
gnant ce sommet au début et la fin des travaux : on obtient ainsi les dates de
début au plus tôt et au plus tard de cette tâche. On en déduit les dates de fin
2.4. LA PRISE EN COMPTE DES CONTRAINTES CUMULATIVES 123

au plus tôt et au plus tard ainsi que les marges libres et totales. Les résultats se
présentent évidemment comme dans la méthode précédente.

2.4 La prise en compte des contraintes cumula-

tives
Les méthodes vues dans les paragraphes précédents ne concernent que les
contraintes temporelles. Les tâches réalisées font en général appel à des moyens
(outils, machines, matière première, hommes, ...) qui ne sont disponibles qu’en
quantités limitées. Le but de ce paragraphe est de montrer comment on tient
compte de ces contraintes en jouant sur les intervalles de flottement associés aux
tâches.

Pour un ordonnancement donné, à chaque moyen correspond une courbe de

charge représentant, au cours du temps, les quantités cumulées du moyen à
mettre en oeuvre pour réaliser les tâches en cours. Si ces quantités respectent
les contraintes relatives à ce moyen, il n’y a pas deproblème. Sinon, on détermine
des tâches responsables de surcharges, que l’on déplace dans les limites de leurs
marges totales (les marges des tâches qui les suivent étant éventuellement res-
serrées). Si ces déplacements ne permettent pas de satisfaire les contraintes, la
durée totale de l’ensemble des opérations doit être augmentée.

Aucun algorithme exact n’a été proposé jusqu’ici pour résoudre ce problème.
Par contre, de nombreux algorithmes heuristiques existent dans la littérature. A
titre d’illustration, montrons sur un exemple numérique le type de raisonnement
auquel on peut se livrer.

Reprenons l’exemple du paragraphe 2.2.6 et supposons qu’au sein d’un en-

semble d’ouvriers donnés, chaque tâche nécessite un nombre d’équipes fixé comme
suit :
PP : 1 D : 1 MM : 0 MP : 0 IP : 3
R: 2 F: 1 P: 0 C: 3 M: 1

Le diagramme de GANTT correspondant à l’ordonnancement de ces tâches

va nous permettre de visualiser le nombre total d’équipes nécessaire à chaque
124 CHAPITRE 2. LES PROBLÈMES D’ORDONNANCEMENT

instant.

6
F
5
R
4
IP R
3
IP IP C C C C C
2
D D IP IP R R R C C C C C
1
PP PP R IP R R R C C C C C M M M M M M M
0 2 4 6 14 20

Supposons que l’on ne puisse disposer, à chaque instant, que de 3 équipes. On

voit sur le diagramme que l’on peut y parvenir
– en reculant C de 2 semaines (c’est permis : voir marge libre)
– en reculant R de 2 semaines (la marge totale le permet, moyennant un recul
de C, déjà effectué)
– en reculant IP de 1 semaine (c’est permis)
– en reculant F de 2 semaines (c’est permis).

3
IP IP F C C C C C
2
D D IP IP R R R R C C C C C
1
PP PP D IP IP R R R R C C C C C M M M M M M M
0 2 4 6 14 20

Dans les problèmes concrets, la question ne se résout pas aussi facilement. On

peut songer à écrire un programme linéaire en variables 0 − 1 mais on est très
vite confronté à des problèmes de dimensions.
En pratique, on se contente d’algorithmes heuristiques tels que le suivant, appelé
MILORD.
2.4. LA PRISE EN COMPTE DES CONTRAINTES CUMULATIVES 125

Algorithme

1. Ranger les tâches par ordre croissant de leur date de début au plus tard
(les premières de la liste sont donc celles qu’on peut reculer le moins). En
cas d’ex-aequo, prendre d’abord la tâche qui a la plus petite marge libre.
2. Considérer les tâches dans l’ordre obtenu et les placer au plus tôt, compte
tenu de leur date de début au plus tôt et des contraintes cumulatives.

L’application de la première étape de cet algorithme à notre exemple donne le

rangement suivant :

Numéro 1 2 3 4 5 6 7 8 9 10
Tâche MP P D MM R PP F M IP C
Début au plus tard 0 6 9 9 12 12 13 14 14 16
Marge libre 0 0 0 9 0 0 10 0 3 9
Début au plus tôt 0 6 0 0 3 0 3 14 2 7

Deuxième étape
MP : pas d’ouvrier
P: pas d’ouvrier
D: commence en 0, durée 3, 1 équipe
MM : pas d’ouvrier
R: commence en 3, durée 4, 2 équipes
PP : commence en 0, durée 2, 1 équipe
F: commence en 3, durée 1, 1 équipe
M: commence en 14, durée 7, 1 équipe
IP : ne peut pas commencer avant 7, à cause de la contrainte cumulative;
il y a donc un recul de 5 semaines par rapport à la date de début plus tôt;
comme la marge libre est de 3, il faut reculer les tâches qui suivent IP
de 2 semaines ⇒ C peut commencer au plus tôt en 9. et sa marge libre diminue de 2.
C: commence en 9, durée 5, 3 équipes.

Solution
126 CHAPITRE 2. LES PROBLÈMES D’ORDONNANCEMENT

3
F IP IP C C C C C
2
PP PP R R R R IP IP C C C C C
1
D D D R R R R IP IP C C C C C M M M M M M M
0 2 4 6 14 20

Remarque
S’il avait été impossible de caser la tâche C entre 9 et 14, on aurait dû, en
appliquant l’algorithme, la placer après M et allonger ainsi la durée totale des
travaux de 5 semaines, alors que le recul d’une semaine de M aurait permis de
placer C entre 10 et 15 (algorithme heuristique).

2.5 La méthode P.E.R.T.

Cette méthode a été proposée pour résoudre les problèmes d’ordonnancement
dans le cas où les durées des tâches sont aléatoires. Elle repose sur de nombreuses
hypothèses qu’il est impossible de justifier théoriquement et qui peuvent d’ailleurs
différer d’un auteur à l’autre. Elles résultent de l’expérience des utilisateurs et
doivent être acceptées, faute de mieux.

2.5.1 Description de la méthode

1. On détermine la moyenne et la variance de chaque variable aléatoire d(i)
(durée de la tâche i). Cela ne pose pas de problème si la distribution de
probabilité de d(i) est connue. Si ce n’est pas le cas, on procède, en général,
de la manière suivante :
– on demande aux responsables de chaque tâche i d’estimer sa durée
minimale (ou optimiste) (soit ai ), sa durée maximale (ou pessimiste)
(soit bi ) et sa durée la plus probable (soit ci );
– on adapte à ces valeurs une distribution β (voir §suivant)
– on calcule la moyenne et la variance de cette distribution.
2.5. LA MÉTHODE P.E.R.T. 127

2. On résout le problème d’ordonnancement en traitant les valeurs moyennes

des d(i) comme des valeurs certaines (c’est-à-dire en appliquant une des
méthodes précédentes). Cela se justifie par le fait que la durée moyenne
d’un ensemble de tâches successives est la somme des durées moyennes de
ces tâches.

3. On sait que, sous certaines conditions (supposées remplies ici), la somme

réduite de variables aléatoires indépendantes converge vers une variable
N (0,1) (Théorème Central-Limite). On sait aussi que la variance d’une
somme de variables aléatoires indépendantes est égale à la somme de leurs
variances. Par conséquent, lorsque le nombre de tâches est important et que
leurs durées peuvent être considérées comme indépendantes, la distribution
de la durée totale des opérations peut être considérée comme une normale
dont la moyenne et la variance sont calculables à partir du chemin optimal
obtenu en 2. C’est également le cas des ES(i) correspondant aux tâches
i situées suffisamment loin de l’instant initial (c’est-à-dire précédées d’un
grand nombre de tâches), et des LS(i) correspondant aux tâches i situées
suffisamment loin de l’instant final.

2.5.2 Note sur la distribution β

Une variable aléatoire X a une distribution β de paramètres (a,b,α,γ) si sa

densité de probabilité est la fonction



 0 x < a,


f (x) = (x − a)α (b − x)γ
, a ≤ x ≤ b,


 (b − a)α+γ+1 · β(α + 1,γ + 1)

0 x > b,

où
Z 1
β(m,n) = um−1 (1 − u)n−1 du.
0

La figure ci-dessous montre l’allure de cette fonction.

128 CHAPITRE 2. LES PROBLÈMES D’ORDONNANCEMENT

f(x)

x
a c b

Le mode de cette distribution (c’est-à-dire la valeur la plus probable) s’obtient

en annulant f 0 (x), ce qui donne

αγ + βα
c=
α+γ
a,b,c correspondent aux ai ,bi ,ci définis dans le paragraphe précédent; “adapter”
une distribution β à ces valeurs signifie choisir α et γ de manière à satisfaire la
relation ci-dessus.
129

Chapitre 3

Théorie des réseaux de transport

3.1 Définitions
1. Réseau de transport : graphe orienté simple G(X,U ) où à chaque arc (xi ,xj )
est associé un nombre cij ≥ 0, éventuellement infini, et où il existe un
sommet x1 tel que Γ−1 (x1 ) = ∅ et un sommet xn tel que Γ(xn ) = ∅;

cij est la capacité de l’arc (xi ,xj ); x1 est l’entrée (ou source) du réseau et xn
est la sortie (ou puits).

Exemple

x2 3 x6
3 5
7 x4 3
2
2
6 x9
x1 4 5 x8
1 3
6 x5 8
1 x7
4
x3

Convention : si l’arc (xi ,xj ) n’existe pas, on pose cij = 0.

130 CHAPITRE 3. THÉORIE DES RÉSEAUX DE TRANSPORT

2. Flot dans un réseau de transport : ensemble {ϕij } de quantités définies ∀i,j

et vérifiant les conditions suivantes :


 (1) ϕij ≥ 0, ∀i,j,



 (2) ϕij ≤ cij , ∀i,j,
 n
X


 (3)

 (ϕij − ϕji ) = 0, ∀i 6= 1,n.
j=1

ϕij peut être vue comme une quantité de matière parcourant l’arc (xi ,xj );
elle est non-négative et inférieure ou égale à la capacité cij (contraintes (1)
et (2)); la contrainte (3), appelée loi de conservation, exprime que la quantité
totale de matière entrant en un sommet doit être égale à la quantité totale
de matière qui en sort (pour autant que ce sommet ne soit ni l’entrée, ni la
sortie). Elle implique que
n
X n
X
(∗) ϕ1j = ϕjn ,
j=1 j=1

c’est-à-dire que la quantité totale de matière sortant de x1 est égale à la

quantité totale de matière qui entre en xn ; cette quantité est appelée la
valeur du flot.

Démonstration de (*)
n
X n
X
(3) ⇒ ϕij = ϕji , ∀i 6= 1,n
j=1 j=1

XX X X XX X X
⇒ ϕij − ϕ1j − ϕnj = ϕji − ϕj1 − ϕjn
i j j j i j j j
| {z } | {z }
0 0
X X
⇒ ϕ1j = ϕjn
j j

3. Coupe dans un réseau de transport : partition de X en deux ensembles M et

M̄ = X \ M telle que x1 ∈ M et xn ∈ M̄ . La valeur d’une coupe {M,M̄ }
est la somme des capacités des arcs qui vont de M vers M̄ :
X X
C(M,M̄ ) = cij .
xi ∈M xj ∈M̄
3.2. PROBLÈMES DU FLOT MAXIMUM ET DE LA COUPE MINIMUM131

Les arcs (xi ,xj ) tels que xi ∈ M et xj ∈ M̄ seront appelés les arcs de la
coupe.

3.2 Problèmes du flot maximum et de la coupe

minimum

Le problème du flot maximum peut s’énoncer comme suit : étant donné un

réseau de transport, construire un flot de valeur maximum. Cela revient à résoudre
le programme linéaire

n
X n
X
max ϕ1j ( ou max ϕjn )
j=1 j=1

sous les contraintes (1), (2), (3).

La programmation linéaire permet donc de trouver la solution du problème.
Néanmoins, sa structure particulière va permettre de construire un algorithme
“sur mesure” plus efficace.

Le problème de la coupe minimum peut s’énoncer comme suit : étant donné

un réseau de transport, construire une coupe de valeur minimum. On peut montrer
que cela revient à résoudre le programme linéaire dual du précédent. Il en résulte
le théorème suivant :

Théorème (“théorème du min cut - max flow” ou théorème de FORD

et FULKERSON)
Dans tout réseau, la valeur du flot maximum est égale à la valeur de la coupe
minimum.

Nous donnerons dans le paragraphe suivant une démonstration directe de ce

théorème, basée sur un algorithme qui résout le problème du flot maximum.
132 CHAPITRE 3. THÉORIE DES RÉSEAUX DE TRANSPORT

3.3 Résolution du problème de flot maximum

3.3.1 Algorithme de marquage de FORD-FULKERSON
L’algorithme décrit ci-dessous est motivé par le théorème et le corollaire sui-
vants :

Théorème
Dans tout réseau, la valeur de tout flot est inférieure ou égale à la valeur de toute
coupe.

Démonstration intuitive : la quantité totale de matière allant de x1 à xn doit

nécessairement emprunter les arcs de la coupe (voir définition de coupe) et être
inférieure ou égale à la somme des capacités de ces arcs (contrainte (2)).

Démonstration analytique : soit le flot {ϕij } et la coupe {M,M̄ }.

n
X n
X n
X n
P X
ϕ1j = ϕ1j − ϕj1 + (ϕij − ϕji )
xi ∈M
j=1 j=1 j=1 i6=1 j=1
| {z } | {z }
0 0

n
XX
= (ϕij − ϕji )
xi ∈M j=1

X X X X
= (ϕij − ϕji ) + (ϕij − ϕji )
xi ∈M xj ∈M xi ∈M xj ∈M̄
| {z }
0

X X
≤ ϕij
xi ∈M xj ∈M̄

X X
≤ cij .
xi ∈M xj ∈M̄

C.Q.F.D.

Corollaire
Si un flot et une coupe ont même valeur, alors il s’agit d’un flot maximum et
d’une coupe minimum.
3.3. RÉSOLUTION DU PROBLÈME DE FLOT MAXIMUM 133

L’algorithme de marquage a pour but de construire un flot et une coupe

de valeurs égales. Il nécessite la connaissance d’un flot initial {ϕ0ij }. On peut
évidemment choisir le flot nul (ϕ0ij = 0, ∀i,j).

Algorithme

a. On “‘marque” le sommet x1 en lui associant la valeur ∞. Cela signifie que

la source peut engendrer une quantité infinie de matière. En effet, dans le
problème considéré ici, le flot n’est pas limité par la source mais uniquement
par les capacités des arcs du réseau.
b. On essaie de proche en proche de marquer xn en appliquant la règle sui-
vante : un sommet xj peut être marqué s’il existe un somme marqué xi qui
peut
– soit envoyer à xj de la matière supplémentaire (c’est-à-dire que la
capacité cij n’est pas atteinte par ϕ0ij );
– soit recevoir de xj de la matière en moins (c’est-à-dire que ϕ0ji n’est
pas nul).
Dans le premier cas, la marque de xj sera (+i,α), où α = cij − ϕ0ij : elle
indique que xj pourrait augmenter de α la quantité de matière qu’il reçoit
de xi .

Dans le second cas, la marque de xj sera (−i,α), où α = ϕ0ji : elle indique
que xj pourrait diminuer de α la quantité de matière qu’il envoie à xi .
c. Supposons que l’on puisse marquer ainsi une suite S = {x1 , . . . ,xn } de
sommets de telle sorte que chacun d’entre eux soit marqué avec l’indice du
sommet précédent et soit amin le plus petit α dans les marques des éléments
de S. Il est facile de vérifier que les quantités ϕ1ij telles que
 1
 ϕij = ϕ0ij + αmin si xi et xj sont deux sommets consécutifs de S





 et si la marque de xj contient +i,



ϕ1ji = ϕ0ji − αmin si xi et xj sont deux sommets consécutifs de S





 et si la marque de xj contient −i,



 1
ϕij = ϕ0ij dans les autres cas,
134 CHAPITRE 3. THÉORIE DES RÉSEAUX DE TRANSPORT

constituent un flot dont la valeur est supérieure à celle de {ϕ0ij } de la quan-

tité αmin . On efface les marques et on reprend alors l’étape a avec {ϕ1ij }
au lieu de {ϕ0ij }. Chaque étape de marquage permet donc d’augmenter la
valeur du flot.
d. Soit {ϕkij } le flot obtenu après k étapes de marquage et supposons qu’il
ne soit plus possible de marquer xn à partir de x1 . Soit M k l’ensemble
de sommets que l’on peut marquer et M̄ k l’ensemble des sommets qu’il
est impossible de marquer. Il est clair que {M k ,M̄ k } est une coupe. Soit
xr ∈ M k et xs ∈ M̄ k .
Nous avons
( k
ϕrs = crs , sinon on pourrait marquer xs par (+r,α = crs − ϕkrs );
ϕksr = 0, sinon on pourrait marquer xs par (−r,α = ϕksr ).
Il en résulte que dans la démonstration analytique du dernier théorème, où
on remplace ϕij par ϕkij , M par M k et M̄ par M̄ k , les signes ≤ deviennent
des égalités. On a donc trouvé un flot et une coupe de valeurs égales, c’est-
à-dire un flot maximum et une coupe minimum.

Remarque : en général il y aura, à chaque étape de l’algorithme, plusieurs

façons de marquer une suite de sommets aboutissants à xn . Il suffit évidemment
d’en choisir une.

3.3.2 Convergence de l’algorithme

Il est clair que l’algorithme converge lorsque les capacités cij sont des nombres
entiers. Dans ce cas, l’algorithme construit des flots entiers et la valeur du flot
augmente d’une quantité entière à chaque étape, ce qui assure la convergence.

Si les capacités sont des nombres rationnels, on se ramène au cas précédent

en les multipliant par un entier suffisamment grand; la multiplication de toutes
les capacités par un même facteur ne modifie évidemment pas la solution du
problème. Il faudra cependant prendre garde de diviser ensuite par ce facteur la
valeur du flot maximum obtenu.

On peut montrer que si les capacités sont irrationnelles, l’algorithme peut ne

pas converger. Celle limitation n’est cependant pas très restrictive puisque cette
3.3. RÉSOLUTION DU PROBLÈME DE FLOT MAXIMUM 135

situation sera plutôt rare dans les cas concrets.

3.3.3 Exemple numérique

Soit à trouver un flot maximum dans le réseau de transport suivant.

x2 8 x4
3
15
2
7 7
4
x1 6 x6
9
10 30

x3 14 x5

Remarque : lorsque plusieurs sommets peuvent être marqués à partir d’un sommet
xi , nous choisissons de marquer celui dont l’indice est le plus grand; ce choix est
purement arbitraire (on pourrait aussi choisir celui qui donnera lieu à la plus
grande quantité α).

Soit ϕ0ij = 0, ∀i,j. La marque de x1 est (∞).

1ère étape

x1 étant marqué, on peut marquer x2 et x3 : nous marquons x3 par (+1,10)

x3 étant marqué, on peut marquer x4 et x5 : nous marquons x5 par (+3,14)
x5 étant marqué, on peut marquer x4 et x6 : nous marquons x6 par (+5,30)
x6 étant marqué, on peut construire un nouveau flot {ϕ1ij } dont la valeur
sera min{10,14,30} = 10.
La situation, à la fin de cette étape, peut être représentée par le graphe
suivant
136 CHAPITRE 3. THÉORIE DES RÉSEAUX DE TRANSPORT

x2 8,0 x4
3,0
15,0
2,0
7,0 7,0
4,0
x1 6,0 x6
9,0
30,10
10,10

x3 14,10 x5

A chaque arc (xi ,xj ), nous associons deux nombres : le premier représente
sa capacité cij et le deuxième la quantité ϕ1ij obtenue à la fin de la 1ère
étape.
2ème étape

x1 étant marqué, on peut marquer x2 par (+1,15)

(x3 ne peut plus être marqué à partir de x1 puisque ϕ113 = c13 );
x2 étant marqué, on peut marquer x3 et x4 : nous marquons x4 par (+2,8);
x4 étant marqué, on marque x6 par (+4,3).

Le graphe ci-dessous donne le flot {ϕ2ij } ainsi obtenu :

x2 8,3 x4
3,3
15,3
2,0
7,0 7,0
4,0
x1 6,0 x6
9,0
30,10
10,10

x3 14,10 x5
3.3. RÉSOLUTION DU PROBLÈME DE FLOT MAXIMUM 137

3ème étape

x1 étant marqué, on peut marquer x2 par (+1,12)

x2 étant marqué, on peut marquer x3 et x4 : nous marquons x4 par (+2,5);
x4 étant marqué, on peut marquer x3 et x5 : nous marquons x5 par (+4,9);
x5 étant marqué, on marque x6 par (+5,20).

x2 8,8 x4
3,3
15,8
2,0
7,0 7,0
4,0
x1 6,0 x6
9,5
30,15
10,10

x3 14,10 x5

4ème étape

x1 étant marqué, on peut marquer x2 par (+1,7)

x2 étant marqué, on peut marquer x3 par (+2,4);
x3 étant marqué, on peut marquer x4 et x5 : nous marquons x5 par (+3,4);
x5 étant marqué, on marque x6 par (+5,15).

x2 8,8 x4
3,3
15,12
2,0
7,0 7,0
4,4
x1 6,0 x6
9,5
30,19
10,10

x3 14,14 x5
138 CHAPITRE 3. THÉORIE DES RÉSEAUX DE TRANSPORT

5ème étape

x1 étant marqué, on peut marquer x2 par (+1,3)

Aucun autre sommet ne peut être marqué.
Le flot maximum est donc celui obtenu ci-dessus;
sa valeur est 10+12=22=3+19.

La coupe minimum correspondante est

M = {1,2}

M̄ = {3,4,5,6}

Sa valeur est donc c24 + c23 + c13 = 22.

3.3.4 Autre exemple numérique

Soit à trouver un flot maximum dans le réseau de transport suivant.

x2
18 13
12
x6
15 x3 30 40
x1
x5
13 6
6

Remarque : le choix des sommets marqués, dans cet exemple, a été fait de manière
à illustrer le cas des marques négatives; il ne répond donc pas à une règle
préétablie.

1ère étape
3.3. RÉSOLUTION DU PROBLÈME DE FLOT MAXIMUM 139

x1 étant marqué, on marque x2 par (+1,18), puis x6 par (+2,2) ce qui donne
le flot ϕ112 = ϕ126 = 2, les autres ϕ1ij étant nuls.
2ème étape

on marque x2 (+1,16), puis x3 (+2,12), puis x4 (+3,6), puis x5 (+4,6), puis

x6 (+5,40), ce qui donne le flot ϕ212 = 8, ϕ223 = ϕ234 = ϕ245 = ϕ256 = 6,
ϕ226 = 2, les autres ϕ2ij étant nuls.
3ème étape

on marque x3 (+1,15), puis x5 (+3,30), puis x6 (+5,34). La situation, à la

fin de cette étape, peut être représentée par le graphe suivant.

2,2

x2
18,8 13,0
12,6
x6
15,15 x3 30,15 40,21
x1
x5
13,0 6,6
6,6

4ème étape

on marque x4 (+1,13); seul x3 peut être marqué à partir de x4 et sa marque

sera (−4,6); on marque ensuite x5 (+3,15) et x6 (+5,19). Le flot peut aug-
menter de 6.

On obtient donc ϕ414 = 6, ϕ434 = 0 , ϕ435 = 21 et ϕ456 = 27.

5ème étape

on marque x2 (+1,10), x3 (+2,6), x5 (+3,9) et x6 (5,13); le flot peut augmenter

de 6.
140 CHAPITRE 3. THÉORIE DES RÉSEAUX DE TRANSPORT

6ème étape

on peut marquer x2 et x4 à partir de x1 mais aucun autre sommet ne peut

être marqué.

Le flot maximum est donc celui qui a été obtenu à la 5ème étape; il est
représenté ci-dessous. Sa valeur est 35.

2,2

x2
18,14 13,0
12,12
x6
15,15 x3 30,27 40,33
x1
x5
13,6 6,0
6,6

3.3.5 Rangement des opérations en tableau

On construit un tableau n × n (n est le nombre de sommets du réseau) dans
lequel la case (i,j)
– contient la capacité de l’arc (xi ,xj ) et contiendra les valeurs successives de
ϕij ;
– est hachurée s’il n’existe pas d’arc (xi ,xj ).
A chaque étape de l’algorithme, on ajoute une colonne contenant, dans la
ligne j, la marque du sommet xj (la case restant vide si le sommet n’est pas
marqué). Ayant αmin , on indique les valeurs des ϕij dans le tableau initial (on
n’indique évidemment que les valeurs non nulles).

La marque de xj sera (+i,α) si on trouve dans sa colonne un sommet marqué

qui peut encore lui envoyer une quantité α de matière et (−i,α) si on trouve dans
sa ligne un sommet marqué où il envoie déjà une quantité α de matière.
3.3. RÉSOLUTION DU PROBLÈME DE FLOT MAXIMUM 141

On trouvera ci-dessous les tableaux permettant de résoudre les 2 exemples

précédents.

x x x x x x 1) 2) 3) 4)
1 2 3 4 5 6

x 15 10
1 8 12 10
8
x 4
(+1,15) (+1,15)x (+1,7)x (+1,3)
2 4 8

x 7 2 14
(+1,10)X (+2,4) (+2,4)x
3 10 14
6
x 9 3
(+2,8) (+2,8)x (+3,2)
4 8

x 7 30
(+3,14)X (+4,9)X (+3,4)X
5 10
18
22

x6 (+5,30)X (+5,20)X (+5,12)X

min 10 8 4

La règle de marquage est ici la suivante : lorsqu’un sommet peut être marqué à
partir de plusieurs autres, on choisit celui qui donne le plus grand α.
Comme on peut le voir, la solution trouvée est différente de celle obtenue précédemment
(la valeur du flot maximum étant évidemment la même).
142 CHAPITRE 3. THÉORIE DES RÉSEAUX DE TRANSPORT

x x2 x3 x4 x
5
x 6 1) 2) 3) 4)
1

x 18 15 13
1 12 14 15 6

x2 12 2
(+1,18) (+1,18)X (+1,6) (+1,6)X
12 2

x3 6 30
(+1,15)X (+2,12)X
15 27

x 6
(+1,13)X (+3,15) (+1,13)X (+1,7)
4 6
13
x 40
(+3,30)X (+3,15)X (+4,6)X
5 15
27
33

x6 (+5,40)X (+5,25)X (+5,13)X (+2,2)X

min 15 12 6 2

La règle de marquage est la même qu’à la page précédente.

La solution est la même que précédemment.

3.4 Cas particuliers et variantes du problème de

flot maximum
3.4.1 Cas où les sommets ont des capacités limitées
Supposons que l’on recherche un flot maximum dans un réseau de transport
où par chaque sommet xi peut passer une quantité de matière au plus égale à
ai . Ce problème se ramène à celui du flot maximum étudié précédemment de la
manière suivante.

Chaque sommet xi est remplacé par deux sommets x0i , x”i joints par un arc
de capacité ai . Les arcs (xi ,xj ) et (xj ,xi ) sont remplacés respectivement par des
3.4. CAS PARTICULIERS ET VARIANTES DU PROBLÈME DE FLOT MAXIMUM143

arcs (x”i ,xj ) et (xj ,x0i ) de capacités équivalentes.

La recherche d’un flot maximum dans le nouveau réseau obtenu fournit la

solution au problème posé.

3.4.2 Le problème du flot maximum dans un graphe orienté

quelconque

Soit G(X,U ) un graphe orienté quelconque où à chaque arc (xi ,xj ) est associé
un nombre cij ≥ 0. La recherche d’un flot maximum enter x1 et xn se ramène
à celle d’un flot maximum dans un réseau de transport : il suffit d’ajouter les 2
sommets x0 ,xn+1 et les 2 arcs (x0 ,x1 ), (xn ,xn+1 ) auxquels on donne des capacités
infinies.

Si plusieurs arcs vont de xi à xj (si le graphe n’est pas simple), on les remplace
par un seul auquel on attribue une capacité égale à la somme de leurs capacités.

3.4.3 Le problème du flot maximum avec plusieurs entrées

et sorties

Si le réseau comprend plusieurs entrées et plusieurs sorties et si le flot peut

aller de toute entrée à toute sortie, on se ramène au problème classique en ajoutant
un sommet x0 joint à chaque entrée par un arc de capacité infinie et un sommet
xn+1 recevant de chaque sortie un arc de capacité infinie, et en recherchant un
flot maximum de x0 à xn+1 .

3.4.4 Le problème du flot maximum avec bornes inférieures

La recherche d’un flot maximum dans un réseau de transport aux arcs duquel
sont associées, non seulement des capacités, mais aussi des bornes inférieures
positives pour les ϕij peut également se résoudre à l’aide d’un algorithme de
marquage du type FORD-FULKERSON.
144 CHAPITRE 3. THÉORIE DES RÉSEAUX DE TRANSPORT

3.4.5 Le problème du flot maximum dans un graphe non

orienté
Considérons un graphe non orienté dont les arêtes sont munies d’une capacité
non négative et recherchons le flot maximum entre deux sommets x1 et xn de
telle sorte que, pour chaque arête, le flot ne soit permis que dans un seul sens.

On remplace chaque arête par deux arcs de sens opposés auxquels on donne
la capacité de cette arête; si {ϕij } est le flot maximum dans le graphe orienté
ainsi obtenu, alors {ϕ0ij } défini par

ϕ0ij = max{0,ϕij − ϕji }

fournit la solution du problème.

3.4.6 Le problème du flot minimum

Il s’agit cette fois de trouver un ensemble de quantités {ϕij } vérifiant la loi
de conservation et telles que
ϕij ≥ cij , ∀i,j.

On peut utiliser l’algorithme de FORD-FULKERSON en le modifiant convena-

blement. Ainsi, un sommet xj sera marqué (+i,α = ϕ0ij −cij ) s’il existe un sommet
marqué xi tel que ϕ0ij > cij ; il sera marqué (−i,α = ∞) s’il existe un sommet
marqué xi tel que l’arc (xj ,xi ) existe.
Si on parviens ainsi à marquer une suite {x1 , . . . ,xn }, on construit le nouveau flot


 ϕ1ij = ϕ0ij − αmin si xi et xj sont deux sommets consécutifs de S et



 si la marque de xj contient +i,

ϕ1ji = ϕ0ji + αmin si xi et xj sont deux sommets consécutifs de S et



 si la marque de xj contient −i,


 ϕ1 = ϕ 0 dans les autres cas,
ij ij

et on recommence la procédure.

On peut aussi se ramener au problème du flot maximum de la façon suivante

1. on cherche un flot {ϕ0ij } tel que ϕ0ij ≥ cij , ∀i,j
2. on pose c0ij = ϕ0ij − cij , ∀i,j
3.4. CAS PARTICULIERS ET VARIANTES DU PROBLÈME DE FLOT MAXIMUM145

3. on construit le flot maximum ϕ0ij tel que ϕ0ij ≤ c0ij , ∀i,j

4. le flot {ϕij } défini par

ϕij = ϕ0ij − ϕ0ij , ∀i,j

est le flot minimum cherché, si le graphe est antisymétrique.

3.4.7 Le problème du couplage maximal

Soit un graphe (X,U ) tel que X puisse être partitionné en deux sous-ensembles
X1 et X2 tels que :
(
−∀x ∈ X1 , Γ−1 (x) = ∅,
−∀x ∈ X2 , Γ(x) = ∅.

Un couplage est un ensemble d’arcs du graphe tels que deux quelconques d’entre
eux n’aient pas de sommet commun.

La recherche d’un couplage maximal (c’est-à-dire contenant le plus grand

nombre possible d’arcs) se ramène au problème de flot maximum dans un réseau
de transport de la façon suivante :

– on inverse le sens des arcs du graphe initial et on leur donne une capacité
infinie;

– on ajoute un sommet y et les arcs (y,x), ∀x ∈ X2 auxquels on donne une

capacité 1;

– on ajoute un sommet z et les arcs (x,z), ∀x ∈ X1 auxquels on donne un

capacité 1;

Le lecteur vérifiera aisément que le flot maximum dans ce réseau fournit la solu-
146 CHAPITRE 3. THÉORIE DES RÉSEAUX DE TRANSPORT

tion du problème.

3.4.8 Le problème d’Hitchcock

Supposons qu’il y ait m sources x1 . . . xm offrant respectivement des quantités
a1 . . . am d’un certain bien et n puits y1 . . . yn demandant respectivement des
quantités d1 . . . dn de ce bien. Si f (xi ,yj ) est le coût unitaire de transport de xi à yj ,
il faut trouver un flot satisfaisant les demandes à partir des approvisionnements
et de coût minimum. La résolution de ce problème est basée sur la théorie de la
dualité en programmation linéaire et sur l’algorithme de FORD-FULKERSON.

3.4.9 Le problème général du flot à coût minimal

Ce problème consiste à trouve un flot à coût minimal dans un réseau dont
chaque arc est muni d’une capacité et d’un coût unitaire de transport, et qui satis-
fait des demandes en certains sommets à partir d’approvisionnement en d’autres
sommets.

On peut démontrer qu’il est équivalent à un problème de Hitchcock.

3.4.10 Le problème général de transport

La construction d’un flot à coût minimal qui, dans un réseau où chaque arc
est muni d’une capacité infinie et d’un coût unitaire de transport, satisfait des
3.4. CAS PARTICULIERS ET VARIANTES DU PROBLÈME DE FLOT MAXIMUM147

demandes en certains sommets à partir d’approvisionnements en d’autres som-

mets, a été appalé problème général de transport. C’est donc un cas particulier
du précédent et il peut être ramené à un problème de Hitchcock.

3.4.11 Le problème de l’affectation optimale

Il s’agit d’affecter m employés à m tâches en réalisant un coût minimum,
sachant que la réalisation de la tâche j par l’employé i coûte f (i,j).

C’est un problème de Hitchcock où ai = 1, ∀i et dj = 1, ∀j.

Ce problème est en général résolu par la “méthode hongroise”, inspirée de

l’algorithme de FORD-FULKERSON.

3.4.12 Le problème du plus court chemin

Il s’agit de trouver, dans un réseau où chaque arc (xi ,xj ) est muni d’une
longueur `ij , un chemin de longueur minimale de x1 à xn . Si on donne une unité
d’approvisionnement à x1 , une unité de demande à xn et une capacité infinie
à chaque arc, on est ramené à un problème général de transport (les longueurs
étant assimilées aux coûts).
148 CHAPITRE 3. THÉORIE DES RÉSEAUX DE TRANSPORT
149

Chapitre 4

Le problème de Hitchcock

4.1 Enoncé du problème

Un ensemble de m sources (ou centres de production) x1 . . . xm offrent respec-

tivement des quantités a1 . . . am d’un certain bien, qui est demandé en quantités
d1 . . . dn par n puits (ou centres de consommation) y1 . . . yn . Les frais de transport
d’une unité de bien de xi à yj (i = 1, . . . ,m; j = 1, . . . ,n sont donnés par fij . Le
problème est de déterminer les quantités ϕij à transporter de xi à yj de manière
à respecter les contraintes de demandes et d’approvisionnements et à minimiser
le coût total de transport.

On peut supposer que la somme des demandes est égale à la somme des
disponibilités, c’est-à-dire que

m
X n
X
ai = dj .
i=1 j=1

En effet, si la demande dépasse l’offre, on introduit une source fictive xm+1 et des
coûts fm+1,j très grands. Si c’est l’offre qui dépasse la demande, on introduit un
puits fictif yn+1 et des coûts fi,n+1 nuls.

A ce problème, on peut associer le réseau R suivant : on ajoute un sommet

x0 joint à chaque xi par un arc de capacité ai et un sommet yn+1 en recevant de
chaque yj un arc de capacité dj . Les capacités attribuées aux arcs (xi ,yj ) seront
définies lors de la description de l’algorithme.
150 CHAPITRE 4. LE PROBLÈME DE HITCHCOCK

4.2 Programmes linéaires primal et dual associés

Le problème de HITCHCOCK donne lieu au programme linéaire suivant :
 m X n

 X


 min fij ϕij ,

 i=1 j=1



 Xn

 ϕij = ai , i = 1,2, . . . ,m, (1)
(I)
 j=1
 m

 X



 ϕij = dj , j = 1,2, . . . ,n, (2)

 i=1



ϕij ≥ 0, ∀i, ∀j. (3)

Le programme dual est donc(les variables duales étant α1 . . . αm , δ1 . . . δn ) :

 m n
 X X


 max ai α i + d j δj ,

i=1 j=1
(II)

 αi + δj ≤ fij , ∀i,∀j, (4)



αi et δj sans restriction de signe

Etant donné la structure particulière du problème, il n’est pas avantageux de

le résoudre par la méthode du Simplexe. Nous allons présenter ici un algorithme
de marquage basé sur les propriétés de la dualité en programmation linéaire.

4.3 Une condition nécessaire et suffisante d’op-

timalité
Soit {ϕ̃ij } et {α̃i ,δ̃j } les solutions optimales des programmes linéaires (I) et
(II). Il résulte de la théorie de la dualité en programmation linéaire que les valeurs
optimales des deux fonctions économiques doivent être égales, c’est-à-dire que
X n
m X m
X n
X
fij ϕ̃ij = ai α̃i + dj δ̃j . (5)
i=1 j=1 i=1 j=1

Il résulte des contraintes (1) et (2) que cette relation peut encore s’écrire
m X
X n
(fij − α̃i − δ̃j )ϕ̃ij = 0. (6)
i=1 j=1
4.4. ALGORITHME 151

D’après les contraintes (3) et (4), cette somme ne peut être nulle que si chacun de
ses termes est nul; autrement dit, une condition nécessaire d’optimalité de {ϕ̃ij }
et {α̃i ,δ̃j } est :
α̃i + δ̃j < fij ⇒ ϕ̃ij = 0, ∀i,j. (7)

Réciproquement, soti {ϕ̃ij } et {α̃i ,δ̃j } des solutions admissibles de (I) et (II)
satisfaisant les relations (7). Il résulte de (4) et (7) que la relation (6) est vérifiée.
Celle-ci, combinée avec (1) et (2) entraı̂ne la relation (5) c’est-à-dire l’égalité des
fonctions économiques du primal (I) et du dual (II). Il découle de la théorie de la
dualité que {ϕ̃ij } et {α̃i ,δ̃j } sont optimales. Nous avons donc le théorème suivant,

Théorème
Une condition nécessaire et suffisante pour que les solutions admissibles {ϕ̃ ij } et
{α̃i ,δ̃j } des programmes (I) et (II) soient optimales est qu’elles satisfassent les
relations (7).

4.4 Algorithme
a) On définit une première solution admissible pour le progamme (II) de la
façon suivante : (
ᾱi = min` fi` , ∀i,
δ̄j = mink (fkj − ᾱk ), ∀j.
b) On recherche un flot maximum passant dans le réseau R1 obtenu à partir
de R (défini au §4.1) en donnant une capacité nulle aux arcs (xi ,yj ) tels que

ᾱi + δ̄j < fij ,

et une capacité infinie aux autres. Cette recherche se fait par l’algorithme
de FORD-FULKERSON.
Si ce flot {ϕ̄ij } épuise toute la marchandise à transporter, alors c’est la
solution optimale puisque {ϕ̄ij } et {ᾱi ,δ̄j } sont admissibles pour les pro-
grammes (I) et (II) et satisfont la C.N.S. d’optimalité grâce au choix de R 1 .
Sinon, on passe en c).
c) Soit I et I¯ respectivement les ensembles de sources marquées et non marquées
à la fin de l’étape b), et J et J¯ respectivement les ensembles de puits
152 CHAPITRE 4. LE PROBLÈME DE HITCHCOCK

marqués et non marqués à la fin de cette étape b).

Remarquons que x0 ∈ I et yn+1 ∈ J. ¯
On définit (
ᾱi , ¯
∀xi ∈ I,
¯i =
ᾱ
ᾱi + µ ,∀xi ∈ I,
et (
δ̄j , ¯
∀yj ∈ J,
δ̄¯j =
δ̄j − µ ,∀yj ∈ J,
où
µ = min (fij − ᾱi − δ̄j ).
xi ∈I
yj ∈J¯

Nous allons démontrer (voir §4.6) que :

¯ i ,δ̄¯j } est admissible pour le problème (II);
1) {ᾱ
2) La fonction économique du programme (II) est strictement plus grande
¯ i ,δ̄¯j } que pour {ᾱi ,δ̄j }.
pour {ᾱ

On reprend ensuite l’étape b) où l’on recherche un flot maximum passant

par le réseau R2 obtenu à partir de R en donnant une capacité nulle aux
arcs (xi ,yj ) tels que
¯ i + δ̄¯j < fij ,
ᾱ

et une capacité infinie aux autres. Si le flot n’épuise pas la marchandise, on

passe à l’étape c) et ainsi de suite.

4.5 Convergence de l’algorithme

L’algorithme aboutit à la solution optimale en un nombre fini d’étapes lorsque
les données sont des entiers (ou des rationnels) puisque la fonction économique
du problème II augmente strictement à chaque étape.

4.6 ¯ i,δ̄¯j }
Démonstrations des propriétés de {ᾱ
¯ i ,δ̄¯j } est admissible pour (II). En effet :
1) {ᾱ
– si xi ∈ I¯ et yj ∈ J, ¯ i + δ̄¯j = ᾱi + δ̄j ≤ fij ;
¯ alors ᾱ
– si xi ∈ I et yj ∈ J, alors ᾱ ¯ i + δ̄¯j = ᾱi + µ + δ̄j − µ ≤ fij ;
4.7. REMARQUE IMPORTANTE 153

¯ i + δ̄¯j = ᾱi + δ̄j − µ ≤ fij ; car µ ≥ 0;

– si xi ∈ I¯ et yj ∈ J, alors ᾱ
– si xi ∈ I et yj ∈ J, ¯ alors ᾱ¯ i + δ̄¯j = ᾱi + µ + δ̄j ≤ fij ; à cause de la
définition de µ.
m
X Xn m
X n
X
2) ¯
αi ᾱi + ¯
dj δ̄j > αi ᾱi + dj δ̄j .
i=1 j=1 i=1 j=1
En effet, la quantité de gauche moins la quantité de droite donne
 
X X
µ ai − dj  .
xi ∈I yj ∈J

Comme {ϕ̄ij } est un flot maximum, sa valeur est égale à la valeur de la

coupe {I ∪ J,I¯ ∪ J},
¯ c’est-à-dire la somme des capacités des arcs qui vont
d’un sommet marqué à un sommet non marqué. Comme les arcs (xi ,yj ) ont
des capacités nulles ou infinies, la valeur de cette coupe (et donc du flot
maximum) est donnée par :
X X
ai + dj .
xi ∈I¯ yj ∈J

Comme le flot {ϕ̄ij } n’épuise pas toute la marchandise à transporter, cette

m
X
valeur est strictement inférieure à l’offre totale, c’est-à-dire à ai .
i=1
Il en résulte que
 
X X m
X X X
ai − dj = ai −  ai + dj  > 0.
xi ∈I yj ∈J i=1 xi ∈I¯ yj ∈J

Il reste à démontrer que µ > 0.

Or, ∀xi ∈ I, ∀yj ∈ J, ¯ la capacité de (xi ,yj ) doit être nulle, sinon un arc de
la coupe aurait une capacité infinie; comme, par définition, les arcs (xi ,yj )
à capacité nulle sont ceux tels que ᾱi + δ̄j < fij , µ est strictement positif.

4.7 Remarque importante

Lorsqu’on cherche un flot maximum dans R2 , il n’est pas nécessaire de partir
d’un flot initial nul; on peut en effet, grâce au théorème suivant, prendre comme
flot initial le flot {ϕ̄ij } (flot maximum obtenu dans R1 ).
154 CHAPITRE 4. LE PROBLÈME DE HITCHCOCK

Théorème
{ϕ̄ij } est un flot admissible dans R2 .

Démonstration : il suffit de montrer que ϕ̄ij = 0 pour les arcs (xi ,yj ) qui ont une
capacité nulle dans R2 , c’est-à-dire pour les couples (i,j) tels que

¯ i + δ̄¯j < fij .

ᾱ

Si xi ∈ I et yj ∈ J ou si xi ∈ I¯ et yj ∈ J,
¯ alors

¯ i + δ̄¯j = ᾱi + δ̄j

ᾱ

et les arcs de capacité nulle sont les mêmes dans R1 et R2 .

¯ nous avons vu que la capacité de (xi ,yj ) doit être nulle dans
Si xi ∈ I et yj ∈ J,
R1 et donc ϕ̄ij = 0.

Si xi ∈ I¯ et yj ∈ J, alors xi n’est pas marqué et yj l’est; ϕ̄ij doit donc être nul,
sinon on pourrait marquer xi à partir de yj .

4.8 Disposition des calculs

Pour la recherche du flot maximum dans R1 , la structure particulière du
problème va permettre de ranger les opérations en tableau de façon plus effi-
cace que dans l’algorithme général de FORD-FULKERSON.
D’autre part, en vertu de la remarque précédente, c’est le même tableau qui ser-
vira à chercher le flot maximum dans R2 puisque le flot maximum dans R1 peut
servir de flot initial dans R2 .

On construit un tableau m × n (une ligne pour chaque xi et une colonne pour

chaque yj ) qui contiendra les flots successifs. Les cases (i,j) telles que ᾱi + δ̄j < fij
sont hachurées. Les marques associées aux lignes et aux colonnes seront indiquées
respectivement dans des colonnes et des lignes ajoutées au tableau.
Soit {ϕ0ij } un flot dans R1 (flot nul au départ).
P
a) On affecte les marques (0,i ), où i = ai − j ϕ0ij , aux lignes i telles que
i > 0 (i est donc la quantité de matière que xi peut encore envoyer).
4.8. DISPOSITION DES CALCULS 155

b) Pour chaque ligne i marquée, on repère les colonnes j non marquées telles
que les cases (i,j) ne soient pas hachurées et on leur affecte la marque (i,δj ),
où δj = i (cela indique que xi pourrait envoyer une quantité δj à yj ).
c) Pour chaque colonne j marquée, on repère les lignes i non marquées telles
que ϕ0ij > 0 et on leur affecte la marque (j,i ), où i = min{ϕ0ij ,δj }. Puisque
la colonne j est marquée, elle peut recevoir une quantité δj d’un certain xk ;
par conséquent, xi peut diminuer de i la quantité qu’il envoie à yj au profit
éventuel d’un autre y` : c’est ce qu’indique la marque (j,i ).
d) On continue à marquer les lignes et les colonnes alternativement. Dès qu’est
X
marquée une colonne j telle que ϕ0ij < dj , on calcule
i
X
ε = min{δj ,dj − ϕ0ij }
i

et on définit le flot {ϕ1ij } comme suit :

ϕ1kj = ϕ0kj + ε, si la marque de yj est (k,δj )

(la quantité que xk envoie à yj augmente de );

ϕ1k` = ϕ0k` − ε, si la marque de xk est (`,k )

(la quantité que xk envoie à y` diminue de ).

ϕ1r` = ϕ0r` − ε, si la marque de y` est (r,δ` )

(la quantité que xr envoie à y` augmente de ).

Cette procédure s’arrête lorsqu’on rencontre un sommet xi dont la marque
est (0,i ). Les autres ϕ0ij restent inchangés.
Par construction, le flot {ϕ1ij } a sa valeur supérieure à celle de {ϕ0ij } d’une
quantité .

On reprend ensuite le marquage sur base de ce nouveau flot. Lorsqu’il n’est

P
plus possible de marquer une colonne j telle que i ϕij < dj , on a un flot
maximum.
Cette procédure de marquage est basée sur le même principe que celle de
FORD-FULKERSON : les marques et la présentation ont été adaptées au
problème.
156 CHAPITRE 4. LE PROBLÈME DE HITCHCOCK

4.9 Exemple numérique

Disponibilités : a1 = 15, a2 = 9, a3 = 7, a4 = 9
Demandes : d1 = 4, d2 = 8, d3 = 15, d4 = 5, d5 = 8
Coûts :
y1 y2 y3 y4 y5
x1 2 1 1 2 6
x2 7 9 1 3 2
x3 6 4 5 1 3
x4 6 7 8 4 9

ᾱ1 = 1, ᾱ2 = 1, ᾱ3 = 1, ᾱ4 = 4

δ̄1 = 1, δ̄2 = 0, δ̄3 = 0, δ̄4 = 0, δ̄5 = 1

Recherche d’un flot maximum dans R1

dj 4 8 15 5 8
ai y y2 y3 y4 y5 1 3 5 7 9 11
1

15 x1 0 0
8
0
3
(0,15) (0,11) (0,3)
4

9 x2 0
9 0 (0,9) (0,9) (0,9) (0,9)

7 x3 0 (0,7) (0,7) (0,7) (0,7) (0,7) (0,2)

9 x4 0 (0,9) (0,9) (0,9) (0,9) (0,9) (0,9)

2 (0,15)

4 (1,11) (1,11)

6 (1,3) (1,3) (1,3)

8 (2,9)

10 (3,7)

12 (3,2)
4.9. EXEMPLE NUMÉRIQUE 157

- Flot nul au départ

(1) - On marque les 4 lignes
(2) - On marque y1 → nouveau flot avec = 4
(3) - On marque les 4 lignes
(4) - On marque y1 et y2 → nouveau flot avec = 8
(5) - On marque les 4 lignes
(6) - On marque y1 ,y2 et y3 → nouveau flot avec = 3
(7) - On marque x2 ,x3 et x4
(8) - On marque y3 → nouveau flot avec = 9
(9) - On marque x3 et x4
(10) - On marque y4 → nouveau flot avec = 5
(11) - On marque x3 et x4
(12) - On marque y4

On ne peut plus rien marquer et le flot n’épuise pas toute la marchandise →

nouveau réseau.

I = {3,4} I¯ = {1,2} J = {4} J¯ = {1,2,3,5}

y1 y2 y3 y5 ᾱi
x3 6 4 5 3 1
⇒µ=1
x4 6 7 8 9 4
δ̄j 1 0 0 1

¯ 1 = 1 ᾱ
ᾱ ¯ 2 = 1 ᾱ
¯ 3 = 2 ᾱ
¯4 = 5

δ̄¯1 = 1 δ̄¯2 = 0 δ̄¯3 = 0 δ̄¯4 = −1 δ̄¯5 = 1

158 CHAPITRE 4. LE PROBLÈME DE HITCHCOCK

Recherche d’un flot maximum dans R2

dj 4 8 15 5 8
ai y1 y2 y3 y4 y5 1 3 5 7

15 x 41
0
8 36 (1,4) (1,1)
1 7

9 x2 9
8
0
1 (3,1)

7 x3 5 02
(0,2) (4,5) (4,5) (4,5)
0 7

9 x4 03 0
5
(0,9) (0,9) (0,6) (0,5)
4

2 (4,9) (3,2) (3,2)

4 (4,9) (1,4) (1,4) (4,9)

6 (4,6) (1,1) (1,1) (4,6) (2,1)

8 (4,5) (4,5) (3,5)

(1) - Le flot initial est le flot maximum trouvé dans R1

(2) - On marque x3 et x4
(3) - On marque y1 ,y4 et y5 → nouveau flot avec = 2
(4) - On marque x4
(5) - On marque y1 et y4
(6) - On marque x1 et x3 
 ϕ13 → 6
(7) - On marque y2 et y3 → nouveau flot avec = 3 ϕ11 → 1

ϕ41 → 3
(8) - On marque x4
(9) - On marque y1 et y4
(10) - On marque x1 et x3
(11) - On marque y2 et y3
(12) - On marque x2
4.9. EXEMPLE NUMÉRIQUE 159


 ϕ25 →1

 ϕ23
 →8
(13) - On marque y5 → nouveau flot avec = 1 ϕ13 →7



 ϕ11 →0

ϕ41 →4
(14) - On marque x4
(15) - On marque y1 et y4
(16) - On marque x3

 ϕ35 → 7
(17) - On marque y5 → nouveau flot avec = 5 ϕ34 → 0

ϕ44 → 5

C’est la solution optimale.

160 CHAPITRE 4. LE PROBLÈME DE HITCHCOCK
161

Chapitre 5

Le problème d’affectation

5.1 Généralités

Il s’agit d’affecter m ouvriers à m tâches en réalisant un coût minimum, sa-

chant que la réalisation de la tâche j par l’employé i coûte fij (fij = ∞ si cette
affectation est exclue).
Ce problème peut être résolu par une procédure de séparation et d’évaluation.
On peut également considérer ce problème comme un problème de HITCHCOCK
dans lequel les ai et les dj valent 1 : c’est sur ce principe que se base la méthode
hongroise, que nous décrivons ci-dessous. Auparavant, considérons un cas parti-
culier.

5.2 Cas particulier : le problème du couplage

maximal

Dans le cas où tous les fij finis valent 1, le coût total de l’affectation vaut m et
le seul problème consiste à trouver une bijection entre les employés et les tâches,
sachant que certaines affectations sont exclues (fij = ∞). Cela revient à trouver
un flot maximum dans le réseau suivant, où seules les affectations possibles sont
représentées.
162 CHAPITRE 5. LE PROBLÈME D’AFFECTATION

1 1
1 1

HJILK4MNO és tâches

5.3 La méthode hongroise

On considère le tableau m × m, où une ligne est affectée à chaque employé et
une colonne à chaque tâche et où la case(i,j) contient la valeur fij .

a) Obtention des zéros

A tous les éléments d’une même colonne, on enlève le plus petit élément de
la colonne; dans le tableau obtenu, enlever à tous les éléments d’une même
ligne le plus petit élément de la ligne. On obtient ainsi un tableau contenant
au moins un zéro par ligne et par colonne.
b) Recherche d’une solution optimale
On détermine un couplage maximal entre les employés et les tâches, en ne
considérant que les arcs correspondant aux zéros obtenus à l’étape précédente
(c’est la recherche du flot maximum dans le réseau R1 où seuls les arcs tels
que ᾱi + δ̄j = fij ont une capacité non nulle).
Si ce couplage concerne tous les employés et toutes les tâches, on a la solu-
tion optimale. Sinon, on passe en c)
c) Modification du tableau
Soit I et I¯ respectivement les employés marqués et non marqués au cours
de l’étape b) et J et J¯ respectivement les tâches marquées et non marquées
au cours de cette étape b). On détermine la plus petite valeur µ de la partie
du tableau relative à I et J¯ et on soustrait cette valeur des colonnes non
marquées et on l’ajoute aux lignes non marquées.
5.4. REMARQUE 163

On reprend ensuite l’étape a) avec ce tableau modifié.

¯ i + δ̄¯j du tableau
Notons que la modification du tableau revient à soustraire ᾱ
initial des fij ; en effet, si on pose

fij0 = fij − ᾱi − δ̄j ,

la modification précédente consiste à définir

f − µ, ∀i ∈ I,∀j ∈ J¯
 0
 ij

f ”ij = ¯ ∈J
fij0 + µ, ∀i ∈ I,∀j

 0
fij , pour les autres i,j

f − (ᾱi + µ) − δ̄j , ∀i ∈ I,∀j ∈ J¯


 ij

= ¯ ∈J
fij − ᾱi − (δ̄j − µ), ∀i ∈ I,∀j


fij − ᾱi − δ̄j , pour les autres i,j

¯ i − δ̄¯j , ∀i,j.
= fij − ᾱ

5.4 Remarque
On peut parfois obtenir le couplage maximal de l’étape b) sans passer par
un algorithme de marquage. Une méthode heuristique consiste par exemple à
encadrer un zéro dans la ligne qui en contient le moins, à barrer les zéros qui se
trouvent dans la même ligne ou la même colonne que le zéro encadré et à recom-
mencer l’opération successivement. Les zéros encadrés déterminent un couplage
qui est parfois maximal.
Supposons que l’on ait ainsi obtenu un couplage maximal sans passer par un
algorithme de marquage. L’étape c) nécessite que l’on retrouve les employés et
les tâches marqués correspondants. On procèdera comme suit :

a) marquer toutes les lignes qui ne contiennent aucun zéro encadré.

b) pour chaque ligne marquée i, marquer les colonnes j qui ont un zéro barré
dans la case (i,j).
c) marquer toute ligne qui a un zéro encadré dans une colonne marquée.
d) répéter b) et c) jusqu’à ce qu’il ne soit plus possible de marquer des rangées.
On obtient ainsi les ensembles I, I, ¯ J et J.¯
164 CHAPITRE 5. LE PROBLÈME D’AFFECTATION

Dans la résolution du problème de HITCHCOCK,on recommençait le marquage

X
chaque fois que l’on était amené à marquer une colonne j telle que ϕ0ij < dj .
i
On pouvait alors augmenter le flot initial. Cette situation ne se présentera pas
ici puisque le couplage considéré est maximal (autrement dit, on a déjà le flot
maximum).

5.5 Exemple numérique

Les coûts d’affectation sont donnés dans le tableau suivant
 
7 3 5 7 10
 
 6 ∞ ∞ 8 7 
 
 
 6 5 1 5 ∞ 
 
 11 4 ∞ 11 15 
 
∞ 4 5 2 10
a) Obtention des zéros

   
1 0 4 5 3 1 0 4 5 3
   
 0 ∞ ∞ 6 0   0 ∞ ∞ 6 0 
   
   
 0 2 0 3 ∞  → 0 2 0 3 ∞ 
   
 5 1 ∞ 9 8   4 0 ∞ 8 7 
   
∞ 1 4 0 3 ∞ 1 4 0 3

b) Recherche d’un couplage maximal (application de l’heuristique)

 
1 0 4 5 3
 0 ∞ ∞ 6 \/0  Le couplage obtenu est maximal; en effet, un
 
  couplage meilleur devrait contenir 5 zéros en-
 
 \/0 2 0 3 ∞  cadrés, ce qui est impossible puisque la 1e et
 
 4 \/0 ∞ 8 7  la 4e lignes contiennent chacune un seul zéro
 
  et ils sont situés dans la même colonne.
∞ 1 4 0 3

¯ J et J¯
Détermination des ensembles I, I,

L’application des étapes a), b) c) et d) donnent

I = {1,4} I¯ = {2,3,5} J = {2} J¯ = {1,3,4,5}.

5.5. EXEMPLE NUMÉRIQUE 165

c) Modification dutableau : µ = 1 et on obtient le tableau suivant :

 
0 \/0 3 4 2
 
 \/0 ∞ ∞ 6 0 
 
 
 \/0 3 0 3 ∞ 
 
 
 3 0 ∞ 7 6 
 
∞ 2 4 0 3
Ce tableau contient un zéro par ligne et par colonne et l’heuristique fournit
un couplage maximal qui est la solution du problème

Vous aimerez peut-être aussi

Simplexe
100% (1)
Simplexe
156 pages
Recherche OPerationelle
Pas encore d'évaluation
Recherche OPerationelle
59 pages
Modele de Recherche Operationnele
Pas encore d'évaluation
Modele de Recherche Operationnele
113 pages
0746 Recherche Operationnelle Aspects Mathematiques Et Applications
Pas encore d'évaluation
0746 Recherche Operationnelle Aspects Mathematiques Et Applications
175 pages
Google
Pas encore d'évaluation
Google
249 pages
Optimisation des flux en logistique
Pas encore d'évaluation
Optimisation des flux en logistique
156 pages
CoursPontsRO 3 4
Pas encore d'évaluation
CoursPontsRO 3 4
2 pages
Optimisation EA1
Pas encore d'évaluation
Optimisation EA1
130 pages
Support de Cours M1 OFRC
Pas encore d'évaluation
Support de Cours M1 OFRC
40 pages
Introduction à la RO pour débutants
Pas encore d'évaluation
Introduction à la RO pour débutants
210 pages
Optimisation EA1
Pas encore d'évaluation
Optimisation EA1
130 pages
Poly
Pas encore d'évaluation
Poly
100 pages
Recherche Opérationnelle Pr. Khalid ISKAFI
Pas encore d'évaluation
Recherche Opérationnelle Pr. Khalid ISKAFI
115 pages
Théorie des graphes en recherche opérationnelle
100% (2)
Théorie des graphes en recherche opérationnelle
127 pages
Rope Cours 1 Et 2
Pas encore d'évaluation
Rope Cours 1 Et 2
111 pages
Mainoptimisation PDF
Pas encore d'évaluation
Mainoptimisation PDF
113 pages
Benmoussa INFO3 ENPC
Pas encore d'évaluation
Benmoussa INFO3 ENPC
64 pages
Optimisation1 Chap8
Pas encore d'évaluation
Optimisation1 Chap8
61 pages
Optimisation1 Chap8 PDF
Pas encore d'évaluation
Optimisation1 Chap8 PDF
61 pages
Opt Lin
100% (1)
Opt Lin
209 pages
Cours
Pas encore d'évaluation
Cours
35 pages
Universite Montpellier 2 - Cours DOptimisation Numerique
Pas encore d'évaluation
Universite Montpellier 2 - Cours DOptimisation Numerique
71 pages
Optimisation Discrète et Théorie des Graphes
Pas encore d'évaluation
Optimisation Discrète et Théorie des Graphes
66 pages
Optimisation1 PDF
Pas encore d'évaluation
Optimisation1 PDF
169 pages
Optimisation Logistique PDF
100% (1)
Optimisation Logistique PDF
169 pages
Introduction à la RO pour étudiants
Pas encore d'évaluation
Introduction à la RO pour étudiants
177 pages
Programmation Mathématique Discrète et Modèles
Pas encore d'évaluation
Programmation Mathématique Discrète et Modèles
129 pages
Polyao 101
Pas encore d'évaluation
Polyao 101
109 pages
Introduction à la Recherche Opérationnelle
Pas encore d'évaluation
Introduction à la Recherche Opérationnelle
185 pages
001-Syllabus Exercices
Pas encore d'évaluation
001-Syllabus Exercices
113 pages
Optimisation Combinatoire Programmation Linéaire Et Algorithmes
Pas encore d'évaluation
Optimisation Combinatoire Programmation Linéaire Et Algorithmes
155 pages
Programmation Linéaire et Simplexe
Pas encore d'évaluation
Programmation Linéaire et Simplexe
125 pages
Théorie D Graphes Prog Lin (Très Bien)
Pas encore d'évaluation
Théorie D Graphes Prog Lin (Très Bien)
69 pages
Introduction à la recherche opérationnelle
Pas encore d'évaluation
Introduction à la recherche opérationnelle
70 pages
Model Es
Pas encore d'évaluation
Model Es
119 pages
Cours 316 Recherche Opérationnelle
Pas encore d'évaluation
Cours 316 Recherche Opérationnelle
44 pages
Poly 435
Pas encore d'évaluation
Poly 435
213 pages
Recrutement Coordonnateur Livelihoods JRS Cameroun
Pas encore d'évaluation
Recrutement Coordonnateur Livelihoods JRS Cameroun
6 pages
RZB Plaquette Institutionnelle Chiffres 2024
Pas encore d'évaluation
RZB Plaquette Institutionnelle Chiffres 2024
6 pages
CCM 1308
Pas encore d'évaluation
CCM 1308
10 pages
CLIPSAS ANNUAIRE - 2017-2018 V1 PBDD
Pas encore d'évaluation
CLIPSAS ANNUAIRE - 2017-2018 V1 PBDD
13 pages
TDR Manuel Pratiques
Pas encore d'évaluation
TDR Manuel Pratiques
2 pages
Protection Environnementale: Urgences et Solutions
Pas encore d'évaluation
Protection Environnementale: Urgences et Solutions
3 pages
SPA de Travail en Hauteur
100% (1)
SPA de Travail en Hauteur
1 page
Le Formulaire Doit Être Utilisé Conformément Au Standard MS-AS-STD-0064 de Job Hazard Analysis
Pas encore d'évaluation
Le Formulaire Doit Être Utilisé Conformément Au Standard MS-AS-STD-0064 de Job Hazard Analysis
2 pages
Interculturaliser Le Développement Durable Colloque-Ouaga-A1-Esoh - Pdfuno
Pas encore d'évaluation
Interculturaliser Le Développement Durable Colloque-Ouaga-A1-Esoh - Pdfuno
11 pages
Fr-MS-HS-FRM-0082 Hot Work Permit Form
100% (1)
Fr-MS-HS-FRM-0082 Hot Work Permit Form
3 pages
Assurance et Contrats de Transport
100% (1)
Assurance et Contrats de Transport
27 pages
Recrutement Travailleur Social à Yagoua
Pas encore d'évaluation
Recrutement Travailleur Social à Yagoua
3 pages
Contrôle citoyen à Mozogo : Rapport 2018
Pas encore d'évaluation
Contrôle citoyen à Mozogo : Rapport 2018
113 pages
Uneapproche ASIFdistribuepourlecalculdesmissions CO2 Dansleschaineslogistiquesmarocaines V2
Pas encore d'évaluation
Uneapproche ASIFdistribuepourlecalculdesmissions CO2 Dansleschaineslogistiquesmarocaines V2
5 pages
112032-Article Text-310510-1-10-20150127
Pas encore d'évaluation
112032-Article Text-310510-1-10-20150127
8 pages
Questionnaire d'Agrément pour Ingénieurs et BET
Pas encore d'évaluation
Questionnaire d'Agrément pour Ingénieurs et BET
8 pages
Biostatistique et Dispositifs Expérimentaux
Pas encore d'évaluation
Biostatistique et Dispositifs Expérimentaux
82 pages
Journal de Recherche en Chimie: ISSN: 2455-8990
Pas encore d'évaluation
Journal de Recherche en Chimie: ISSN: 2455-8990
5 pages
Optimisation RMN : Déplacements et Couplages
Pas encore d'évaluation
Optimisation RMN : Déplacements et Couplages
33 pages
tp12 Dosage Diiode Corrige 2009-2010-2
Pas encore d'évaluation
tp12 Dosage Diiode Corrige 2009-2010-2
2 pages
Synthèse Organique : Méthodes et Mécanismes
100% (1)
Synthèse Organique : Méthodes et Mécanismes
11 pages
Synthese Des Hydroxides Doubles Lamellaires (H.D.L) Application À L'elimination Du Lixiviat
Pas encore d'évaluation
Synthese Des Hydroxides Doubles Lamellaires (H.D.L) Application À L'elimination Du Lixiviat
78 pages
VD Lemoine Hugues
Pas encore d'évaluation
VD Lemoine Hugues
250 pages
Guide du Test Khi-Deux pour Débutants
Pas encore d'évaluation
Guide du Test Khi-Deux pour Débutants
8 pages
Étude des Plantes Médicinales "Kel Tamaša"
Pas encore d'évaluation
Étude des Plantes Médicinales "Kel Tamaša"
140 pages
Baget 2003 B
Pas encore d'évaluation
Baget 2003 B
17 pages
Imagerie Médicale pour Médecins BAC3
Pas encore d'évaluation
Imagerie Médicale pour Médecins BAC3
4 pages
Arcgis Géoréférencement Méthode 1
100% (2)
Arcgis Géoréférencement Méthode 1
23 pages
CT GenAI Syllabus v1.0 FR
Pas encore d'évaluation
CT GenAI Syllabus v1.0 FR
75 pages
Algorithmique Et Structures de Données (ASD) : Chapitre 1: Et Rappel Des Fonctions/ Procédures (Partie 2)
Pas encore d'évaluation
Algorithmique Et Structures de Données (ASD) : Chapitre 1: Et Rappel Des Fonctions/ Procédures (Partie 2)
7 pages
Cispr 16-1-3-2016
Pas encore d'évaluation
Cispr 16-1-3-2016
142 pages
CM PHP-PGSQL
Pas encore d'évaluation
CM PHP-PGSQL
28 pages
Le Système de Gestion de Fichier
Pas encore d'évaluation
Le Système de Gestion de Fichier
24 pages
Système d'évaluation 68000 : Guide TP
Pas encore d'évaluation
Système d'évaluation 68000 : Guide TP
14 pages
Rapport Pfe e Learning
Pas encore d'évaluation
Rapport Pfe e Learning
46 pages
IPV6
Pas encore d'évaluation
IPV6
80 pages
Corrigé Examen Systèmes d'Information
Pas encore d'évaluation
Corrigé Examen Systèmes d'Information
2 pages
Dessin Kawasaki Ninja Pinterest - Recherche Google
Pas encore d'évaluation
Dessin Kawasaki Ninja Pinterest - Recherche Google
1 page
MINF226
Pas encore d'évaluation
MINF226
89 pages
Part of Project
Pas encore d'évaluation
Part of Project
6 pages
Pizzicato Pro 3.6 Guide Complet de L'utilisateur
100% (1)
Pizzicato Pro 3.6 Guide Complet de L'utilisateur
996 pages
TP2 Sécuriser Le Système D'exploitation Windows XP Professionnel
Pas encore d'évaluation
TP2 Sécuriser Le Système D'exploitation Windows XP Professionnel
2 pages
Cours D Introduction Au Langage C#
Pas encore d'évaluation
Cours D Introduction Au Langage C#
6 pages
OX-560 : Automate 5 Populations Compact et Performant
Pas encore d'évaluation
OX-560 : Automate 5 Populations Compact et Performant
4 pages
Exposé
Pas encore d'évaluation
Exposé
22 pages
Série 1 Decision Financiere
Pas encore d'évaluation
Série 1 Decision Financiere
5 pages
Le Piratage Informatique
Pas encore d'évaluation
Le Piratage Informatique
7 pages
Fiche de Mise en Service
Pas encore d'évaluation
Fiche de Mise en Service
2 pages
Exercices Réseaux et Sous-Réseaux
0% (1)
Exercices Réseaux et Sous-Réseaux
2 pages
Algorithmes de Tournées de Véhicules Pour L'optimisation Des Flux de Produits Et de Patients Dans Un Complexe Hospitalier
Pas encore d'évaluation
Algorithmes de Tournées de Véhicules Pour L'optimisation Des Flux de Produits Et de Patients Dans Un Complexe Hospitalier
266 pages
Epreuve Mensuelledu CM1 Decembre 2024
Pas encore d'évaluation
Epreuve Mensuelledu CM1 Decembre 2024
27 pages
Cartographie Numérique pour Abidjan
Pas encore d'évaluation
Cartographie Numérique pour Abidjan
124 pages
Oumaima Pfe
Pas encore d'évaluation
Oumaima Pfe
30 pages
AcademyCloudArchitecting Module 05
Pas encore d'évaluation
AcademyCloudArchitecting Module 05
63 pages
CV Technicien Spécialisé en BTP et Maintenance
Pas encore d'évaluation
CV Technicien Spécialisé en BTP et Maintenance
1 page

Info H 3000

Transféré par

Info H 3000

Transféré par

TABLE DES MATIÈRES 3

Table des matières

2 Différents types de programmes linéaires 29

8 L’algorithme dual simplexe 71

II Applications dans les graphes 79

1 Quelques problèmes de la théorie des graphes 81

1.6.2 Algorithme de FORD . . . . . . . . . . . . . . . . . . . . . 97

2 Les problèmes d’ordonnancement 109

3 Théorie des réseaux de transport 129

3.3.5 Rangement des opérations en tableau . . . . . . . . . . . . 140

4 Le problème de Hitchcock 149

5 Le problème d’affectation 161

PROBLEME 1 : un problème de placement

Combien l’entreprise doit-elle placer dans chaque modalité de façon à maxi-

PROBLEME 2 : composition d’aliments pour le

On a indiqué ci-dessous les pourcentages de protéines et de graisses contenus,

Orge Arachide Sésame

PROBLEME 3 : fabrication de crème glacée

Matières grasses Sucre Oeufs Eau Coût

Le fabriquant désire déterminer la composition du mélange de coût minimal.

PROBLEME 4 : problème de production

PROBLEME 5 : choix de pétroles bruts pour une

Quelles quantités de pétroles bruts doit-elle traiter pour réaliser un bénéfice

Bruts n0 1 Bruts n0 2 Bruts n0 3 Limites

Gaz et gaz liquéfiés 0,02 - 0,06 300.000 T.

PROBLEME 6 : un problème de production

En supposant que l’écoulement de la production ne pose pas de problème,

PROBLEME 7 : production d’un atelier

Les bénéfices unitaires sont respectivement de 60 par objet pour A1 , 40 par

Chaque objet est vérifié par un des 3 techniciens de l’équipe de contrôle:

Quelle est la production optimale?

PROBLEME 8: problème de découpe de bobines

On dispose d’une bobine B1 de largeur 9 et de longueur 20 et d’une bobine

Ceux de largeur 3 doivent représenter, ensemble, une longueur totale au moins

On désire maximiser la surface totale découpée.

PROBLEME 9: problème de découpe de barres

On veut découper 36 barreaux de 28 cm et 24 barreaux de 45 cm, commandés

Considérer deux cas :

a) Les barreaux éventuellement découpés en excédent ne sont pas considérés

PROBLEME 10: transport d’appareils photographi-

On demande le nombre de caisses de chaque type à expédier pour que le

PROBLEME 11: un problème d’investissement

Quel(s) projet(s) faut-il choisir de façon à maximiser les gains?

PROBLEME 12: localisation d’émetteurs de télévision

On cherche à déterminer les sites sur lesquels il faut construire un émetteur

PROBLEME 13: un problème de localisation

Clients 1 2 3 4 5 6 Capacité Coût

PROBLEME 14: un problème de planning

Comment organiser les opérations de façon à minimiser le temps total de

PROBLEME 15: un problème d’affectation de

On désire minimiser la durée de réalisation des n projets.

PROBLEME 16: le problème du flot maximum

PROBLEME 17: le problème de Hitchcock

PROBLEME 18: le problème du “sac à dos”

Comment remplir le sac de façon à maximiser le gain total?

PROBLEME 19: le problème d’affectation

PROBLEME 20: un exemple de programme qua-

Le coût unitaire de transport de l’endroit i à l’endroit j est cij .

Le volume de marchandises à transporter du centre de production k au centre

Où faut-il construire les m centres de production de façon à minimiser le coût

Différents types de programmes

En effet, maximiser une fonction revient à minimiser cette fonction changée

La nature d’un programme linéaire ne dépend donc pas de la forme particulière

* Un programme linéaire (P.L.) est un problème qui peut se mettre sous

         

Si x1 et x2 entiers ≥ 0 ⇒ (3) entier

Si x1 ≥ 0 et x2 entier ≥ 0 ⇒ (5) mixte-entier

(Le point encadré est la solution optimale)

2.2 Passage d’un type de P.L. à un autre

– Un programme linéaire booléen peut toujours s’exprimer comme un pro-

– Réciproquement, un programme linéaire entier peut toujours s’exprimer

2.3 Expression de contraintes logiques

gi (x1 ,x2 , . . . ,xn ) ≥ 0, i = 1,2, . . . ,m,

Un programme linéaire continu est un problème qui peut, moyennant une

appelée fonction économique, et qui vérifient les contraintes :

a11 x1 + a12 x2 + . . . + a1n xn ≤ b1 ,

En choisissant un nombre tel que |αi | < si , ∀i, on obtient