CoursROPonts PDF
CoursROPonts PDF
CoursROPonts PDF
Introduction à la recherche
opérationnelle
13 juillet 2017
ii
Table des matières
1 Généralités 1
I Fondements 7
2 Bases 9
2.1 Graphes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2 Retour sur les ponts et sur le voyageur . . . . . . . . . . . . . . . . . . . . . 14
2.3 Optimisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.4 Problème . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.5 Algorithme et complexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.6 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
4 Programmation linéaire 47
4.1 Définition et exemples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
4.2 Quelques éléments théoriques . . . . . . . . . . . . . . . . . . . . . . . . . . 50
4.3 Algorithmes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
4.4 Dualité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
4.5 Une application de la dualité : jeux matriciels à somme nulle . . . . . . . . . 61
4.6 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
5 Flots et Coupes 65
5.1 Flots et coupes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
5.2 Flot de coût minimum . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
5.3 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
TABLE DES MATIÈRES iv
II Problématiques 103
8 Remplissage de conteneurs 105
8.1 Sac-à-dos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
8.2 Bin-packing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
8.3 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
11 Tournées 143
11.1 Problème du voyageur de commerce . . . . . . . . . . . . . . . . . . . . . . . 143
11.2 Problème du postier . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
11.3 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154
13 Ouverture 175
13.1 Quelques outils absents de ce livre . . . . . . . . . . . . . . . . . . . . . . . . 175
13.2 Trois domaines à la frontière de la recherche opérationnelle . . . . . . . . . . 177
TABLE DES MATIÈRES vi
CHAPITRE 1
Généralités
Présentation
La recherche opérationnelle (RO) est la discipline des mathématiques appliquées qui traite
des questions d’utilisation optimale des ressources dans l’industrie et dans le secteur public.
Depuis une dizaine d’années, le champ d’application de la RO s’est élargi à des domaines
comme l’économie, la finance, le marketing et la planification d’entreprise. Plus récemment,
la RO a été utilisée pour la gestion des systèmes de santé et d’éducation, pour la résolution
de problèmes environnementaux et dans d’autres domaines d’intérêt public.
Exemples d’application
Planifier la tournée d’un véhicule de livraison qui doit passer par des points fixés à
l’avance puis revenir à son point de départ en cherchant à minimiser la distance parcourue
est un problème typique de recherche opérationnelle. On appelle ce problème le problème du
voyageur de commerce (étudié plus en détail au Chapitre 11).
Remplir un conteneur avec des objets de tailles et de valeurs variables. Si le conteneur a
une capacité finie, on va chercher à maximiser la valeur placée dans le conteneur. On appelle
ce problème le problème du sac-à-dos (étudié plus en détail au Chapitre 8).
Ordonnancer les tâches sur un chantier. Pour chaque tâche T , on connaı̂t sa durée. De
plus, on connaı̂t les autres tâches dont T dépend directement et combien de temps avant ou
après le début de chacune d’elles T doit démarrer. On désire minimiser la durée totale du
chantier. On dit que ce problème est un problème d’ordonnancement (étudié plus en détail
au Chapitre 10).
Chacun de ces problèmes peut bien sûr être compliqué à l’envie. Dans ce cours, on restera
relativement simple – quelques contraintes de plus suffisent en effet à faire de ces problèmes
de véritables sujets de thèse (par exemple pour le remplissage de conteneur un sujet de
thèse peut consister en : plusieurs types de conteneurs, plusieurs produits à stocker, des
incompatibilités).
Histoire
La recherche opérationnelle est née pendant la Seconde Guerre mondiale des efforts
conjugués d’éminents mathématiciens (dont von Neumann, Dantzig, Blackett) à qui il avait
CHAPITRE 1. GÉNÉRALITÉS 2
été demandé de fournir des techniques d’optimisation des ressources militaires. Le premier
succès de cette approche a été obtenue en 1940 par le Prix Nobel de physique Patrick
Blackett qui résolut un problème d’implantation optimale de radars de surveillance. Le
qualificatif opérationnelle vient du fait que les premières applications de cette disci-
pline avait trait aux opérations militaires. La dénomination est restée par la suite, même si
le domaine militaire n’est plus le principal champ d’application de cette discipline, le mot
opérationnelle prenant alors plutôt le sens d’ effectif . Ce sont donc ces mathématiciens
qui ont créé une nouvelle méthodologie caractérisée par les mots-clés modélisation et opti-
misation.
A partir des années 50, la recherche opérationnelle fait son entrée dans les entreprises.
En France, des entreprises comme EDF, Air France, la SNCF créent à cette époque des
services de recherche opérationnelle (qui existent toujours). La discipline commence à être
enseignée dans les universités et les grandes écoles. Puis, au milieu des années 70, sans doute
à cause d’un excès d’enthousiasme au départ et à l’inadéquation des moyens informatiques à
l’application des méthodes de la RO, la discipline s’essouffle. A partir du milieu des années 90,
on assiste à un retour en force la RO, les outils informatiques étant maintenant à la hauteur
des méthodes proposées par la recherche opérationnelle. On assiste depuis à une explosion
du nombre de logiciels commerciaux et l’apparition de nombreuses boı̂tes de conseil. Pour la
France, notons Ilog (65 millions d’euros de CA), Eurodécision (2,8 millions d’euros de CA),
Artelys (1,6 millions d’euros de CA) à l’étranger Dash-Optimization (racheté début 2008
pour 32 millions de dollars par Fair Isaac), IBM Optimization et beaucoup d’autres (le site
de INFORMS Institute of Operations Research and Management Science en liste près de
240).
Les racines
Si l’on cherche à trouver des précurseurs à la Recherche Opérationnelle, on peut penser
à Alcuin ou à Euler qui se sont tous deux intéressés à des problèmes du type RO, bien
qu’aucune application n’ait motivé leur travail.
Alcuin est le moine irlandais chargé par Charlemagne de construire l’école palatine et qui
inventa le problème du loup, de la chèvre et du chou devant traverser une rivière dans une
barque où au plus un élément peut prendre place.
Un homme devait transporter de l’autre côté d’un fleuve un loup, une chèvre et un
panier de choux. Or le seul bateau qu’il put trouver ne permettait de transporter
que deux d’entre eux. Il lui a donc fallu trouver le moyen de tout transporter de
l’autre côté sans aucun dommage. Dise qui peut comment il a réussi à traverser
en conservant intacts le loup, la chèvre et les choux 1 .
Euler est le mathématicien allemand à qui les notables de Königsberg demandèrent s’il
était possible de parcourir les ponts de la ville en passant sur chacun des 7 ponts exactement
1. Homo quidam debebat ultra fluvium transferre lupum, capram, et fasciculum cauli. Et non potuit
aliam navem invenire nisi quae duos tantum ex ipsis ferre valebat. Praeceptum itaque ei fuerat ut omnia
haec ultra illaesa omnino transferret. Dicat, qui potest, quomodo eis illaesis transire potuit.
3 CHAPITRE 1. GÉNÉRALITÉS
une fois (voir Figure 1.1). Ce genre de problème se rencontre maintenant très souvent dans
les problèmes de tournées du type facteur ou ramassage de déchets ménagers, dans lesquels il
faut parcourir les rues d’une ville de façon optimale. Euler trouva la solution en 1736 – un tel
parcours est impossible – en procédant à une modélisation subtile par des mots. La solution
actuelle, beaucoup plus simple, utilise une modélisation par un graphe (voir Chapitre 2).
On voit sur cet exemple qu’une bonne modélisation peut simplifier de manière drastique la
résolution d’un problème.
Le premier problème de recherche opérationnelle à visée pratique a été étudié par Monge
en 1781 sous le nom du problème des déblais et remblais. Considérons n tas de sable, devant
servir à combler m trous. Notons ai la masse du ième tas de sable et bj la masse de sable
nécessaire pour combler le jème trou. Quel plan de transport minimise la distance totale
parcourue par le sable ?
La solution que proposa Monge est intéressante et procède par une modélisation dans
un espace continu dans lequel on cherche une géodésique – malheureusement, elle n’est pas
correcte. La solution correcte pour trouver l’optimum est connue depuis les années 40 et
utilise la programmation linéaire (que nous verrons au Chapitre 4), ou mieux, la théorie des
flots (que nous verrons au Chapitre 5).
Modélisation et optimisation
[Wikipedia] Un modèle mathématique est une traduction de la réalité pour pou-
voir lui appliquer les outils, les techniques et les théories mathématiques, puis
généralement, en sens inverse, la traduction des résultats mathématiques obte-
CHAPITRE 1. GÉNÉRALITÉS 4
Objectif de ce cours
La recherche opérationnelle occupe une place grandissante dans l’industrie, la logistique et
les transports. Pour un ingénieur souhaitant faire un travail technique dans ces disciplines,
elle est quasi-incontournable. L’objectif de ce cours est de donner les bases de recherche
opérationnelle : la méthodologie, les problèmes et les modèles typiques, les principales tech-
niques de résolution. Un étudiant maı̂trisant les exercices de ce cours est capable de proposer
une modélisation de nombreux problèmes de recherche opérationnelle rencontrés dans l’in-
dustrie, de proposer des approches de résolution et d’en discuter les qualités respectives. Le
cours se focalisera principalement sur les étapes 2. et 3. ci-dessus.
CHAPITRE 1. GÉNÉRALITÉS 6
Première partie
Fondements
7
CHAPITRE 2
Bases
2.1 Graphes
Une brique de base dans la modélisation est le graphe. Les graphes apparaissent naturel-
lement lorsqu’on est confronté à un réseau (réseau de transport, réseau informatique, réseau
d’eau ou de gaz, etc.). Comment parcourir le réseau de manière optimale ? C’est la question
du voyageur de commerce par exemple. Comment concevoir un réseau informatique robuste,
tout en minimisant le nombre de connexions ? C’est le thème de la conception de réseau
(Network Design), abordé au Chapitre 12.
Mais les graphes apparaissent également de manière plus subtile dans certaines modélisations
de problèmes où la structure du graphe n’est pas physique. Un exemple classique est le
problème de l’affectation optimale d’employés à des tâches qui sera étudié aux Chapitres 5
et 6. Les sommets représentent des tâches et des employés, et les arêtes les appariements
possibles entre tâches et employés. Ils apparaissent également dans des problèmes d’ordon-
nancement, où les sommets représentent des tâches et les arcs les relations de précédence.
v3 v3 v 3
v5
v1 v 2 v2
v2 v 5
v1
v1 v 2 v5 v 6
v3 v 4
v4 v6
Figure 2.1 – Exemple de graphe. Ce graphe est non connexe, possède 6 sommets, 6 arêtes, dont deux arêtes
parallèles et une boucle.
v0 , e1 , v1 , e2 , . . . , vk−1 , ek , vk
Figure 2.4 – Graphe possédant une chaı̂ne hamiltonienne. La chaı̂ne hamiltonienne est mise en gras.
0, . . . , k − 1 sont distincts deux à deux. Un cycle passant par toutes les arêtes d’un graphe
est eulérien. Un cycle élémentaire passant par tous les sommets du graphe est hamiltonien.
Un graphe est connexe si entre toute paire de sommets il existe une chaı̂ne.
Couplage
Un couplage dans un graphe G = (V, E) est un sous-ensemble d’arêtes M ⊆ E tel que
toute paire d’arêtes de M sont disjointes. Une couverture est un sous-ensemble de sommets
C ⊆ V tel que toute arête de E touche au moins un sommet de C. La cardinalité maximale
d’un couplage se note ν(G). La cardinalité minimale d’une couverture se note τ (G).
On a la propriété très utile suivante, car elle permet par exemple d’évaluer la qualité d’un
couplage.
Proposition 2.1. Soit M un couplage et C une couverture d’un graphe G. Alors
|M | ≤ |C|.
La preuve est laissée en exercice. Cette proposition peut également s’écrire
ν(G) ≤ τ (G).
Coloration
Une notion fructueuse en théorie des graphes et très utile en Recherche Opérationnelle
est la notion de coloration. Une coloration d’un graphe est une application c : V → N. Les
entiers N sont alors appelés couleurs. Une coloration propre est telle que pour toute paire
de voisins u, v on a c(u) 6= c(v) : deux sommets voisins ont des couleurs différentes. Une
question que l’on peut se poser, étant donné un graphe, est le nombre minimum de couleurs
possible pour une coloration propre. Ce nombre, noté χ(G), s’appelle le nombre chromatique
de G.
On a l’inégalité
cardinalité du plus grand sous-graphe complet ≤ χ(G),
dont on peut aisément se convaincre.
13 CHAPITRE 2. BASES
u1
u3
(u3 , u4 )
u4
(u4 , u3 )
(u5 , u3 )
u5
(u7 , u5 )
u7 (u2 , u1 )
(u6 , u3 ) u2
u6
Figure 2.5 – Exemple de graphe orienté. Ce graphe possède 7 sommets et 5 arcs.
v0 , a1 , v1 , a2 , . . . , vk−1 , ak , vk
5 6
1
3
7 4
8
Figure 2.6 – Graphe orienté possédant un circuit eulérien. L’ordre des arcs dans un tel circuit est indiqué.
flèches. Si les ai sont distincts deux à deux, le chemin est dite simple. Si de plus le chemin ne
passe jamais plus d’une fois sur un sommet, elle est élémentaire. Un chemin simple passant
par tous les arcs d’un graphe orienté est eulérien. Un chemin élémentaire passant par tous
les sommets du graphe est hamiltonien.
Un circuit est un chemin de longueur ≥ 1, simple et fermée. C’est donc une suite de la
forme
v0 , a1 , v1 , . . . , ak , v0
avec aj = (vj−1 , vj ) pour j < k, et ak = (vk−1 , v0 ). Un circuit est élémentaire si les vi pour
i = 0, . . . , k − 1 sont distincts deux à deux. Un circuit passant par tous les arcs d’un graphe
orienté est dit eulérien. Un circuit élémentaire passant par tous les sommets du graphe est
dit hamiltonien. Un exemple de circuit eulérien est donné Figure 2.6.
Un graphe orienté est dit faiblement connexe si le graphe non orienté obtenu en “oubliant”
les orientations des arcs est connexe. Il est fortement connexe si pour tout couple (u, v) de
sommets, il existe un chemin allant de u à v.
Une dernière remarque : Si rien n’est précisé par ailleurs, n représentera |V | le nombre
de sommets et m représentera |E| (ou |A|) le nombre d’arêtes (ou le nombre d’arcs).
Figure 2.7 – Modélisation du problème des ponts de Königsberg. Ce graphe possède-t-il une chaı̂ne
eulérienne ?
sommets. Il y a donc 4 sommets. Chaque pont est représenté par une arête – voir Figure 2.7.
On cherche donc à savoir s’il y a une chaı̂ne eulérienne dans ce graphe.
La condition nécessaire et suffisante d’existence d’une chaı̂ne eulérienne dans un graphe
est simple. La preuve est laissée en exercice.
Théorème 2.1. Un graphe connexe admet une chaı̂ne eulérienne si et seulement si il possède
au plus deux sommets de degré impair.
Un graphe connexe admet un cycle eulérien si et seulement si il n’a pas de sommet de
degré impair.
Avec ce théorème, on voit donc qu’il n’existe pas de parcours passant exactement une
fois et une seule sur chaque ponts de la ville de Königsberg.
On appelle graphe eulérien un graphe possédant un cycle eulérien.
On peut également tenter une modélisation du problème du voyageur de com-
merce, qui a déjà été évoqué. Un camion doit quitter son entreprôt, livrer différents points
d’un réseau puis revenir à son point de départ, et ce, en parcourant la distance minimale.
Le point à livrer est représenté par un sommet du graphe, la route la plus courte entre deux
points est représentée par une arête. On note ce graphe Kn = (V, E), où n est le nombre de
sommets. Ce graphe – simple – est un graphe complet puisque toute paire de sommets cor-
respond à une arête. On ajoute encore une fonction d : E → R+ qui indique la longueur des
routes représentées par les arêtes. Il est à noter que la fonction d satisfait par construction
l’inégalité triangulaire
Notons qu’un graphe admettant un circuit eulérien est automatiquement fortement connexe.
2.3 Optimisation
2.3.1 Définition
Un problème d’optmisation s’écrit sous la forme suivante (on supposera que l’on cherche
à minimiser une certaine quantité).
Min f (x)
s.c. x ∈ X.
f est le critère. s.c. signifie sous contraintes . X est l’ensemble des solutions
possibles ou réalisables et x ∈ X est la ou les contraintes du programme. On cherche
parmi ces solutions réalisables une solution optimale x∗ , i.e. ici une solution réalisable qui
minimise le critère. La quantité inf{f (x) : x ∈ X} est appelée valeur du problème. Si X = ∅,
cette valeur est définie comme étant égale à +∞.
En plus de fournir un cadre compact pour formuler un problème, cette notation à l’avan-
tage de rappeler les questions essentielles à se poser lorsqu’on résout un problème. Veut-
on minimiser ou maximiser ? Que veut-on optimiser ? Quelles sont les contraintes de notre
système ? Quelles sont les variables sur lesquelles on peut jouer ?
Une remarque fondamentale et très utile est que tout problème de minimisation peut se
réécrire comme un problème de maximisation : il suffit de prendre comme critère −f (x). Et
réciproquement.
longuement un programme informatique, alors qu’une borne inférieure nous fournit la preuve
que l’on est à moins de 0,1% de l’optimum par exemple.
En particulier, un bon minorant peut permettre de montrer l’optimalité d’une solution.
Voir Figures 2.8 et 2.9.
Min f (x)
s.c. g(x) = 0, (P)
h(x) ≤ 0
x ∈ X,
CHAPITRE 2. BASES 18
On a toujours
En définissant
d(λ, µ) := inf L(x, λ, µ),
x∈X
Max d(λ, µ)
s.c. λ ∈ Rp (D)
µ ∈ Rq+ .
vP ≥ vD .
Cette inégalité est extrêmement utile et constitue un moyen “automatique” de générer des
bornes inférieures à un problème. Ces notions seront en particulier approfondies dans le
Chapitre 4 sur le programmation linéaire et dans le Chapitre 7. En programmation linéaire,
nous verrons qu’on dispose d’une relation plus forte, appelée dualité forte.
Remarque
d est une fonction concave car infimum de fonctions affines.
2.4 Problème
Une autre notion commode dans la modélisation est la notion de problème. Un problème
se décompose en deux parties : une partie Donnée et une partie Tâche ou Question.
Une telle formalisation permet d’écrire clairement quels sont les éléments dont on dispose
au départ et quelle est précisément la tâche que l’on veut résoudre. L’objectif à atteindre
devient donc clair et dans un tel contexte, il est plus facile de discuter des performances de
telle ou telle méthode.
Par exemple, le problème de l’existence d’une chaı̂ne eulérienne peut s’écrire :
Le premier problème est un type particulier de problème, qui joue un rôle important en
informatique théorique, et s’appelle un problème de décision, puisque la tâche à réaliser est
de répondre à une question fermée, i.e. dont la réponse est soit oui , soit non . Le
second problème est un problème d’optimisation.
Une fois que l’on a modélisé notre problème concret en un problème formalisé ou en un
programme mathématique, on doit se demander comment le résoudre. Dans ce cours, nous
verrons différents problèmes, différents programmes mathématiques, et quelles méthodes
pour les résoudre. De nouveaux problèmes sont proposés tout le temps par les chercheurs
travaillant en recherche opérationnelle ; dans ce cours, nous nous limiterons bien entendu aux
plus classiques.
On se fixe un ensemble d’opérations que l’on considère facile à faire . Par exemple,
comparaison d’entiers, lire une adresse mémoire, etc. Une suite d’opérations élémentaires
permettant de résoudre un problème s’appelle un algorithme. La résolution d’un problème
de recherche opérationnelle passe toujours par l’application d’un algorithme, qui est ensuite
implémenté. Lorsque le problème que l’on tente de résoudre est un programme d’optimisa-
tion, on parlera d’algorithme exact si l’algorithme est sûr de se terminer avec l’optimum du
programme, et d’algorithme approché sinon.
La question qui se pose également est celle de l’efficacité de l’algorithme, i.e. du temps
qu’il va mettre pour résoudre le problème (une fois admis que l’algorithme est correct et
résout bien le problème).
Une méthode peut être de tester l’algorithme sur de grandes quantités de données. Mais
ces tests-là peuvent être très, très longs, et de toute façon, à chaque fois que l’on va penser
à un algorithme possible, on ne va pas systématiquement procéder à son implémentation
et à des tests. La théorie de la complexité, un des fondement théorique de la recherche
opérationnelle, a pour but de mesurer a priori l’efficacité d’un algorithme. La petite histoire
qui va suivre va montrer l’intérêt de cette théorie, et est librement adapté du livre de Garey
et Johnson [10].
21 CHAPITRE 2. BASES
Taille n
Fonction de complexité 10 20 30 40 50 60
n 0, 01 µs 0, 02 µs 0, 03 µs 0, 04 µs 0, 05 µs 0, 06 µs
n2 0, 1 µs 0, 4 µs 0, 9 µs 1, 6 µs 2, 5 µs 3, 6 µs
n3 1 µs 8 µs 27 µs 64 µs 125 µs 216 µs
n5 0, 1 ms 3, 2 ms 24, 3 ms 102, 4 ms 312, 5 ms 777, 6 ms
2n ∼ 1 µs ∼ 1 ms ∼1s ∼ 18 min20 s ∼ 13 jours ∼ 36 années et 6 mois
particuliers. On peut chercher des algorithmes sans garantie sur le temps d’exécution, mais
qui en général semblent être rapides. Ou alors, on peut relaxer le problème et chercher un
algorithme rapide qui trouve des schmilblicks satisfaisant presque toutes les spécifications.
Dans les chapitres suivants, nous verrons des exemples concrets illustrant de telles approches.
permet de vérifier que la réponse est oui , sans pour autant être nécessairement capable
de trouver cette réponse (voir des exemples ci-dessous). Le sigle NP ne signifie pas non
polynomial mais non déterministiquement polynomial . Le non-déterminisme ici fait
référence aux machines de Turing non-déterministes, et dépasse largement le cadre de ce
cours.
Un problème de décision NP est NP-complet si l’existence d’un algorithme polynomial
le résolvant implique l’existence d’un algorithme polynomial pour tout problème NP. A ce
jour, on ne connaı̂t pas d’algorithme polynomial résolvant un problème NP-complet. En
revanche, on connaı̂t beaucoup de problèmes NP-complets. Le premier a été trouvé en 1970,
par un informaticien appelé Cook.
Ce problème de décision est dans P. En effet, le Théorème 2.1 ci-dessus permet facilement
de répondre à la question en temps polynomial : si m est le nombre d’arêtes de G et n son
nombre de sommets, tester le fait que tous les sommets sont de degré pair prend O(m) et
que le graphe est connexe prend O(n + m), au total O(n + m). Il est donc également dans
NP : le certificat est le graphe lui-même.
De même, le problème suivant est dans P.
A ce jour, nul n’a pu démontrer que ce problème est dans P, ni qu’il n’y était pas. En
revanche, il est facile de voir que ce problème est dans NP car si la réponse est positive, alors
l’algorithme qui consiste à suivre le cycle hamiltonien permet de prouver que la réponse est
bien positive. Ici, le cycle hamiltonien joue le rôle de certificat. Il a été également démontré
que ce problème est NP-complet. Cela signifie que si vous rencontrez quelqu’un vous disant
qu’il connaı̂t un algorithme efficace pour répondre à cette question, il est très probable qu’il se
trompe car tous les problèmes NP-complets pourraient alors être résolus par un algorithme
polynomial. Or personne à ce jour n’a pu en trouver, et quantité de gens très brillants ont
cherché un tel algorithme. S’il ne se trompe pas, c’est une découverte fondamentale, qui au-
rait un impact énorme tant dans le monde de l’informatique théorique, que dans la recherche
opérationnelle appliquée. De plus, cette personne percevrait le prix d’1 millions de dollars
?
offert par la Fondation Clay pour la résolution de la question ouverte P = NP.
On peut définir également les mêmes problèmes pour les graphes orientés, les résultats
seront semblables. En résumé, on a
Problèmes Complexité
Graphe non-orienté : Cycle eulérien P
Graphe non-orienté : Chaı̂ne eulérienne P
Graphe non-orienté : Cycle hamiltonien NP-complet
Graphe non-orienté : Chaı̂ne hamiltonienne NP-complet
Graphe orienté : Circuit eulérien P
Graphe orienté : Chemin eulérien P
Graphe orienté : Circuit hamiltonien NP-complet
Graphe orienté : Chemin hamiltonien NP-complet
NP-difficiles
NP-complets
NP
rencontre en RO sont rarement de ce type. Il existe une notion qui permet de caractériser
des problèmes difficiles qui ne sont pas des problèmes de décision : c’est celle de problème
NP-difficile.
Un problème est NP-difficile si savoir le résoudre en temps polynomial impliquerait que
l’on sait résoudre un problème (de décision) NP-complet en temps polynomial.
Théorème 2.3. Le problème du voyageur de commerce est NP-difficile.
La preuve de ce résultat découle de la NP-complétude du problème de cycle hamiltonien.
2.6 Exercices
2.6.1 Dessiner sans lever le crayon
Indiquez pour les Figures 2.11 et 2.12 quand il est possible de dessiner la figure sans lever
le crayon (et sans repasser sur un trait déjà dessiné) et quand il ne l’est pas.
Considérons des relais de téléphonie mobile. Chaque relais reçoit et émet des signaux
à une certaine fréquence. Pour éviter les interférences, on veut que deux relais à moins de
200 m fonctionnent avec des fréquences différentes. Le coût de gestion du parc de relais est
une fonction croissante du nombre de fréquences utilisées. On souhaite minimiser ce coût.
Modéliser ce problème avec les outils du cours.
Considérons maintenant un DRH qui doit assurer un certain nombre de formation à ses
employés. Les formations sont F1 , . . . , Fn . Et les employés sont E1 , . . . , Em . Le DRH sait
pour chaque employé Ei quelles sont les formations qu’il doit suivre. Il veut organiser une
session de formations – chacune des formation ne peut être dispensée qu’une fois au total
dans l’entreprise et un employé peut suivre au plus une formation par jour. En revanche,
plusieurs formations peuvent être dispensées le même jour. Le DRH souhaite organiser la
session la plus courte possible.
Modéliser ce problème avec les outils du cours.
27 CHAPITRE 2. BASES
G1
G2
G3
Figure 2.13 – Lequel de ces graphes contient une chaı̂ne hamiltonienne ? Lequel contient un cycle hamilto-
nien ?
Les problèmes de plus courts chemins apparaissent naturellement dans des contextes
variés. Ils peuvent apparaı̂tre comme modélisation de problèmes opérationnels (trajet le plus
rapide, ou le moins cher, gestion optimal d’un stock, plan d’investissement optimal, etc.),
ils sont aussi fréquemment des sous-problèmes d’autres problèmes d’optimisation (flot de
coût minimum – Chapitre 5 – ou en théorie de l’ordonnancement – Chapitre 10). Sous cette
appellation anodine de plus court chemin, nous verrons qu’il se cache une réalité extrêmement
variée, tant du point de vue de la complexité que des types d’algorithmes mis en œuvre. Le
graphe peut être orienté ou non, les arêtes ou les arcs avoir des poids positifs ou quelconque,...
Un cas particulier important est la programmation dynamique qui traite des situations où des
décisions doivent être prises de manière séquentielle, chaque décision faisant passer le système
d’un état à un autre. Ce passage d’un état à un autre s’appelle une transition. On suppose
qu’un coût est associé à chaque transition. L’objectif de la programmation dynamique est
de minimiser le coût de la suite des transitions, suite qu’on appelle trajectoire.
On s’arrête lorsque λ(u) = +∞ pour tout u ∈ U . La fonction λ donne alors les distances de
s à tout sommet que l’on peut atteindre en partant de s. Les sommets dans U à la fin de
l’algorithme sont ceux qui ne peuvent être atteints depuis s.
De plus, si pour chaque v 6= s, on garde en mémoire le dernier arc a = (u, v) pour lequel
on a redéfini λ(v) := λ(u) + w(a), on peut reconstruire l’ensemble des plus courts chemins
partant de s.
Il est clair que le nombre d’itérations est au plus |V |, et chaque itération prend un temps
O(n). L’algorithme a donc une fonction de complexité qui est en O(n2 ). D’où le théorème :
Théorème 3.1. Etant donnés un graphe orienté D = (V, A), un sommet s ∈ V et une
fonction de poids w : A → R+ , un ensemble de plus courts chemins de s à tout sommet
v ∈ V peut être calculé en O(n2 ).
Eléments de preuve. Pour démontrer le théorème, il faut simplement voir que lorsque u est retiré de U
dans l’itération au-dessus, λ(u) est la vraie distance de s à u (la preuve de cette assertion est laissée en
exercice).
Remarque
Exemple
a
2
b
3
1 1
s 3 d
c
1
5 3 3 6
2 e
2
t
f
7
Figure 3.1 – Exemple de graphe orienté avec poids positifs sur les arcs.
s a b c d e f t
(0) (∞) (∞) (∞) (∞) (∞) (∞) (∞)
0 (3) (∞) (∞) (3) (∞) (5) (∞)
0 3 (5) (∞) (3) (∞) (5) (∞)
0 3 (4) (∞) 3 (∞) (5) (∞)
0 3 4 (5) 3 (∞) (5) (∞)
0 3 4 5 3 (8) (5) (∞)
0 3 4 5 3 (7) 5 (12)
0 3 4 5 3 7 5 (9)
0 3 4 5 3 7 5 9
3.1.2 Les poids sont quelconques mais le graphe est sans circuit
On considère maintenant le cas où les poids peuvent prendre des valeurs négatives, mais
où le graphe est sans circuit, ou acircuitique. Lorsqu’on voit le problème du plus court chemin
comme la modélisation d’un plus court chemin dans un réseau physique, cela peut paraı̂tre
surprenant puisque les temps de parcours ou les distances de portion de réseau sont toujours
positifs. Mais dans de nombreux cas le graphe dont on cherche un plus court chemin est
issu d’une modélisation et les poids ne correspondent pas à des distances ou des temps qui
s’écoulent. Noter que dans ce cas, les notions de plus court chemin, plus court chemin simple
et plus court chemin élémentaire coı̈ncident, puisqu’il n’y a pas de circuit. Donc de même
que dans le cas où tous les w(a) sont positifs, il existe toujours un plus court chemin qui est
élémentaire.
Considérons donc maintenant le cas du graphe orienté D = (V, A) acircuitique, avec une
fonction de poids w : A → R.
CHAPITRE 3. PLUS COURTS CHEMINS ET PROGRAMMATION DYNAMIQUE 32
L’algorithme de Dijkstra ne fonctionne plus lorsque les poids peuvent être négatifs. En
effet, l’invariant de boucle qui fait fonctionner l’algorithme de Dijkstra est le fait que le
minimum de λ(u) pour u dans le U courant est la vraie distance de s à u. Ce qui justifie que
l’on retire u de U . Or si les poids peuvent être négatifs, il facile de voir que cette propriété
n’est plus vraie.
A la fin des années 50, des mathématiciens comme Ford, Bellman, Moore, et d’autres,
remarquèrent que dans ce contexte, un algorithme très simple permet de trouver le plus
court chemin.
Pour décrire cet algorithme, définissons pour v ∈ V :
Théorème 3.2. Etant donnés un graphe acircuitique D = (V, A) et une fonction de poids
w : A → R, un ensemble de plus courts chemins de s à tout sommet v ∈ V peut être calculé
en O(m).
33 CHAPITRE 3. PLUS COURTS CHEMINS ET PROGRAMMATION DYNAMIQUE
L’outil central de l’algorithme qui sous-tend ce théorème est l’ordre topologique. Un ordre
topologique des sommets d’un graphe orienté D = (V, A) est une indexation v1 , v2 , . . . , vn des
sommets de D telle que pour tout i, j tels que (vi , vj ) ∈ A on ait i < j. Un graphe orienté
admet un ordre topologique si et seulement si il est acircuitique. On peut alors trouver un
ordre topologique en O(m) avec l’algorithme suivant.
Scanner un sommet consiste à ouvrir le sommet, scanner ses successeurs puis fer-
mer le sommet (définition récursive, consistante puisque le graphe est sans circuit). On
choisit un sommet s sans prédécesseur. On scanne s. L’ordre opposé à celui dans lequel on
ferme les sommets est un ordre topologique.
En effet, s’il y a un arc de u à v, alors v sera fermé avant u et son indice sera plus
grand que celui de u.
Preuve du Théorème 3.2. Pour prouver ce théorème, il faut montrer que l’on peut trouver en O(m) un ordre
v1 , v2 , . . . , vn sur les sommets de D tel que tous les antécédents de vi ont un indice < i, ce qui assure que l’on
peut toujours calculer λ(vi ) une fois calculés les λ(vj ) pour j < i. Or, c’est ordre n’est rien d’autre qu’un
ordre topologique.
Remarque
Dans le cas acircuitique, on sait en particulier trouver un plus long chemin d’une origine
s à une destination t : en effet, en définissant des poids w0 (a) := −w(a), on voit que le même
algorithme fonctionne (en gardant les mêmes poids, il suffit de changer les min en max).
xk
..
.
s := x0 t
.. ...
.
..
.
posant λ(k, x) := +∞ s’il n’est pas possible d’amener le système dans l’état x en k étapes,
l’équation de Bellman (3.1) se réécrit
Cette équation permet de calculer de proche en proche les valeurs de λ(k, x) : à l’itération
k, on calcule tous les λ(k, x) pour x ∈ Xk , en utilisant les valeurs λ(k − 1, x) calculées à
l’itération k − 1. En voyant ce calcul comme un calcul de plus court chemin dans un graphe
35 CHAPITRE 3. PLUS COURTS CHEMINS ET PROGRAMMATION DYNAMIQUE
acircuitique (Section 3.1.2), cela revient à dire qu’un ordre topologique est donné facilement
par le découpage temporel.
Remarquons enfin que tout graphe orienté acircuitique n’est pas issu d’une modélisation
d’un système dynamique. En effet, un graphe modélisant un processus de programmation
dynamique a tous ses chemins de s à t ayant le même nombre d’arcs, à savoir N .
Venons-en maintenant à quelques exemples de modélisation par la programmation dyna-
mique.
où s est le coût unitaire de stockage et p le coût unitaire de défaillance. Si on veut interdire
les stocks négatifs, on pose p = +∞.
On veut minimiser
N
X −1
c(uk ) + g(xk+1 ).
k=0
Dans le vocabulaire de la programmation dynamique, les états sont les valeurs possibles de
niveau de stock, les transitions possibles sont tous les xk → xk+1 tels que xk+1 satisfasse
simultanément xk+1 ∈ Z, xk+1 ≤ K et xk+1 ≥ xk − dk . Le coût de la transition xk → xk+1
est c(xk+1 − xk + dk ) + g(xk+1 ). On souhaite donc trouver la trajectoire optimale pour ce
modèle de programmation dynamique.
On applique l’algorithme de plus court chemin dans le graphe acircuitique suivant. Pour
chaque période k, on aura un sommet pour chaque niveau de stock possible (inférieur à K et
supérieur à x0 − d0 − d1 − . . . − dk−1 ) en début de période. On notera un tel sommet (x, k),
où x est le niveau de stock, et k la période. Entre un sommet de période k et un sommet
de période k + 1, on a un arc ((x, k), (x0 , k + 1)) seulement si x0 ≥ x − dk . Le poids de l’arc
CHAPITRE 3. PLUS COURTS CHEMINS ET PROGRAMMATION DYNAMIQUE 36
((x, k), (x0 , k + 1)) est égal à c(x0 − x + dk ) + g(x0 ). On cherche un plus court chemin de (x0 , 0)
à un sommet de la forme (x, N ). Le poids de ce plus court chemin sera le coût optimal de la
gestion du stock.
qui se lit : le remplissage optimal x(j, W 0 ) d’un sac de capacité W 0 , avec les objets de 1 à j,
— soit n’utilise pas le jème objet, et dans ce cas x(j, W 0 ) = x(j − 1, W 0 )
— soit utilise le jème objet, et dans ce cas x(j, W 0 ) = x(j − 1, W 0 − wj ) + cj .
La complexité de l’algorithme est : O(nW ). En effet, il faut calculer tous les x(j, W 0 ) qui
sont au nombre de nW , et une fois calculés x(j − 1, W 0 ) et x(j − 1, W 0 − wj ), la quantité
x(j, W 0 ) se calcule en temps constant. Ce n’est pas polynomial car W nécessite log2 (W ) bits
pour être codé. On dit que c’est un algorithme pseudo-polynomial.
3.1.4 Les poids sont quelconques, mais le graphe est sans circuit absorbant : encore la
programmation dynamique
Supposons maintenant que l’on se demande comment calculer un plus court chemin dans
un graphe orienté pondéré, non nécessairement acircuitique. C’est encore possible si le graphe
ne possède pas de circuit absorbant, i.e. de circuit dont la somme des poids est < 0. Ce cas
contient les deux cas précédents (graphe avec poids ≥ 0 et graphe acircuitique). Noter qu’une
fois encore, il existe toujours un plus court chemin qui soit un chemin élémentaire car si le
plus court chemin passe par un circuit, on peut supprimer ce circuit sans détériorer le poids
du chemin.
En fait, pour calculer un plus court chemin dans un graphe sans circuit absorbant, on
peut appliquer la méthode de la programmation dynamique vue ci-dessus.
On considère que les états sont les sommets (Xk = V ) et qu’à chaque instant on traverse
un arc. Le coût de la transition u → v, c’est w(u, v) si (u, v) ∈ A, et +∞ sinon. Avec les
notations de la programmation dynamique, λ(k, v), c’est donc le poids minimal d’un s-v
chemin comportant exactement k arcs.
37 CHAPITRE 3. PLUS COURTS CHEMINS ET PROGRAMMATION DYNAMIQUE
Remarque : En utilisant des techniques totalement différentes [11], on peut obtenir une
complexité de O(n1/2 m log C) où C est la valeur abolue du plus petit poids négatif (en
supposant que C ≥ 2).
Considérons le problème
we
we
we
Considérons le problème
On a le théorème suivant.
Théorème 3.5. Le problème de la plus courte chaı̂ne élémentaire avec des poids quelconques,
dans un graphe quelconque, est NP-difficile.
3.3 Résumé
Complexité
Graphe orienté, poids positifs O(n2 ) (Dijkstra) 1
Graphe orienté, poids quelconques, O(m)
acircuitique (Programmation dynamique)
Graphe orienté, poids quelconques, O(nm)
sans circuit absorbant (Programmation dynamique, algorithme de Ford-Bellman) 2
Graphe orienté, poids quelconques NP-difficile
Graphe non-orienté, poids positifs O(n2 ) (Dijkstra) 1
Graphe non-orienté, poids quelconques, O(n3 )
pas de cycle absorbant (voir Chapitre 11)
Graphe non-orienté, poids quelconques NP-difficile
3.4 Exercices
Trouver la plus courte chaı̂ne de s à t dans le graphe de la Figure 3.4 et le plus court
chemin de s à t dans le graphe de la Figure 3.5.
1. On peut atteindre, avec les bonnes structures de données, O(m + n log n).
2. On peut atteindre avec des techniques différentes O(n1/2 m log C).
CHAPITRE 3. PLUS COURTS CHEMINS ET PROGRAMMATION DYNAMIQUE 40
a 1 b
3 2
5 2 10
c
s
6 1 9
d
g 3
h
4
f 2 1
3
t
2
3
e 5
6
i
2
a
10
3
−2
s
b c
4
2
6
3 3
t
5
d
veut déterminer un chargement qui maximise le bénéfice. Montrer que ce problème est un
problème de sac-à-dos. Le résoudre sur les données W = 6 et
Conteneurs
1 2 3
Bénéfice ck 9 2 8
Poids wk 5 3 2
Conteneurs
1 2 3
Bénéfice ck 12 25 50
Poids wk 4 5,5 6,5
n’a pas à retourner à son point de départ. De plus, on suppose que la livraison en chaque
point se fait de manière instantanée, et que le temps pour aller de xi à xj est proportionnel
à la distance les séparant. Montrer que l’on peut trouver la tournée optimale en O(n2 ) par
un algorithme de type programmation dynamique (c’est un résultat de Tsitsiklis).
A→B→G
H → I → J,
CHAPITRE 3. PLUS COURTS CHEMINS ET PROGRAMMATION DYNAMIQUE 44
également possible, fait changer l’orientation du wagonnet : s’il se déplaçait en marche avant
en H, il se déplace en marche arrière en J.
1. Est-il possible pour le réseau de la Figure 3.6 de passer de n’importe quel point de
réseau à n’importe quel autre ? Peut-on de plus le faire avec les orientations du wagonnet au
départ et à l’arrivée imposées ? Justifier brièvement vos réponses.
2. Considérons le graphe dont les sommets sont les tronçons, et les arêtes les enchaı̂nements
possibles entre les tronçons. La construction est explicitée sur la Figure 3.8. Oublions mo-
mentanément l’orientation. Quitte à modifier un peu le graphe, expliquer comment utiliser
ce graphe pour trouver le plus court trajet entre deux points particuliers du réseau.
1. Montrer que l’on sait trouver le sous-ensemble d’intervalles de C deux à deux disjoints
de poids maximal en temps polynomial (indication : construire un graphe orienté acircuitique
pondéré).
E
F
A C
c
e d e d c
b b
a
a
f
instant de fin et le gain qu’apporterait la satisfaction de cette demande. Montrez que grâce
à la question 1., on sait proposer une stratégie rapide maximisant le gain total de la location
de l’appartement.
CHAPITRE 4
Programmation linéaire
Min cT x
(4.1)
s.c. Ax ≤ b,
Exemple
Commençons par un exemple de problème de production dans l’agro-alimentaire 1 . Sup-
posons que l’on dispose d’une grande surface cultivable sur laquelle il est possible de faire
pousser des navets ou des courgettes. Le coût des semences est considéré comme négligeable.
On dispose de deux types d’engrais X et Y, ainsi que d’un anti-parasite AP. Le besoin en
engrais et en anti-parasite pour les courgettes et pour les navets est synthétisé dans le tableau
suivant.
Max 4x + 5y
s.c. 2x + y ≤ 8
x + 2y ≤ 7
y≤3
x ≥ 0, y ≥ 0
Ce programme est bien un programme linéaire comme défini par l’équation (4.1), avec
8 2 1
7 1 2
4
c= , b= 3 A= 0
1 .
5 0 −1 0
0 0 −1
Comme nous l’avons déjà noté lors du premier cours, le fait qu’il y ait Max dans notre
problème au lieu d’un Min comme dans l’équation (4.1) ne pose pas de problème : maximiser
une quantité revient à minimiser son opposé.
Comme on n’a que deux variables, on peut procéder à une représentation graphique (voir
Figure 4.1).
Problème de production
On considère une entreprise qui produit des biens de n types différents. Pour cela, elle
dispose de m types de ressources. Elle possède bi unités de la ressource i pour i = 1, . . . , m.
La production d’une unité du bien j entraı̂ne un bénéfice égal à cj , pour j = 1, . . . , n. Pour
produire une unité du bien j, elle a besoin de aij unités de chaque ressource i. Maximiser le
profit revient alors à résoudre le programme linéaire suivant.
Pn
Max cj x j
Pj=1
n
s.c. j=1 aij xj ≤ bi i = 1, . . . , m (4.2)
xj ≥ 0, j = 1, . . . , n.
La variable xj représente le nombre d’unités du bien j produites.
C’est un exemple classique et très fréquent de la programmation linéaire. L’aspect allo-
cation optimale des ressources de la RO est particulièrement bien illustré par le problème
de production.
49 CHAPITRE 4. PROGRAMMATION LINÉAIRE
P = {(x, y) : 2x + y ≤ 8, x + 2y ≤ 7, y ≤ 3, x ≥ 0, y ≥ 0}
y=3
x
x + 2y = 7
2x + y = 8
Figure 4.1 – Représentation graphique des contraintes du problème des navets et des courgettes.
Dans l’exemple des navets et des courgettes, nous avons pu résoudre le problème assez
facilement car il n’y avait que 2 variables, et donc une représentation graphique était possible.
Mais la plupart des problèmes réels le nombre de variables et le nombre de contraintes
peuvent dépasser le millier, et ni l’intuition, ni le dessin peuvent alors nous tirer d’affaire.
Heureusement, depuis la fin des années 40, de nombreux chercheurs ont travaillé sur la
programmation linéaire, et c’est maintenant un problème qui est bien résolu tant sur le plan
pratique que sur le plan théorique.
Plan pratique De nombreux logiciels (libres et commerciaux) résolvent des programmes
linéaires de grande taille. Voir la liste en annexe du polycopié. Il y a principalement deux
algorithmes qui sont utilisés dans ces codes : l’algorithme du simplexe et l’algorithme
des points intérieurs. On devrait plutôt parler de familles d’algorithmes car tant l’algo-
rithme du simplexe que l’algorithme des points intérieurs existent sous de nombreuses
variantes.
Plan théorique La programmation linéaire est dans P. Cela signifie qu’il existe des algo-
rithmes polynomiaux qui résolvent la programmation linéaire. L’algorithme des points
CHAPITRE 4. PROGRAMMATION LINÉAIRE 50
intérieurs est un de ceux-là. L’algorithme du simplexe, bien que très rapide en pratique,
ne possède pas pour le moment de version polynomiale : pour chacune de ses versions,
on connaı̂t des instances qui nécessitent un nombre exponentiel d’étapes.
Dans ce chapitre, nous donnons quelques propriétés théoriques de la programmation
linéaire (PL), qui ont un grand intérêt pratique (polyèdres, dualité,...). Les différents algo-
rithmes qui résolvent la programmation linéaire sont également présentés.
Min cT x
s.c. Ax = b (4.3)
x ≥ 0.
Comme d’habitude, x est le vecteur des variables, A est une matrice m × n donnée, c ∈ Rn ,
b ∈ Rm sont deux vecteurs donnés et 0 est le vecteur 0, avec n composantes.
En plus de la forme standard et de la forme inéquationnelle, il existe la forme canonique
qui consiste à écrire le programme linéaire de la façon suivante :
Min cT x
s.c. Ax ≤ b (4.4)
x ≥ 0.
Ces trois formes sont équivalentes : à partir d’une solution réalisable d’un programme
sous l’une des formes, on peut aisément construire une solution réalisable pour les deux
autres formes, donnant une même valeur pour la fonction objectif.
Min cT x
s.c. Ax + y = b
x, y ≥ 0.
yi := bi − (Ax)i pour j = 1, . . . , m
et
xj si xj ≥ 0 −xj si xj ≤ 0
uj := et vj := pour j = 1, . . . , n.
0 sinon, 0 sinon,
Il est alors aisé de vérifier que x0 := (u, v, y) est une solution réalisable du programme (4.5),
et que l’on a bien cT x = cT u − cT v.
Réciproquement, soient x0 = (u, v, y) une solution réalisable du programme (4.5). Posons
x := u − v. Le vecteur x est alors une solution réalisable du programme (4.3), et l’on a bien
cT x = cT u − cT v.
CHAPITRE 4. PROGRAMMATION LINÉAIRE 52
4.2.2 Préliminaires
Dans la suite, on supposera sans perte de généralité, que la matrice A de la forme standard
(4.3) est de plein rang, c’est-à-dire que les m lignes sont linéairement indépendantes. En effet,
on peut tester l’existence d’une solution réalisable en résolvant l’équation Ax = b (par des
pivots de Gauss par exemple). S’il y a une solution réalisable et si les lignes de A ne sont pas
linéairement indépendantes, alors forcément l’équation correspondante est redondante et on
peut la supprimer. D’où
Hypothèse : Nos programmes linéaires sous forme standard seront tels que A est de plein
rang.
AB xB + AN xN = b, (4.6)
La solution x̃ du système Ax = b obtenue en posant x̃B := A−1 B b et x̃N := 0 est une solution
basique. Si cette solution basique est réalisable (par rapport au programme linéaire (4.3)),
i.e. si A−1
B b ≥ 0, alors on dit que x̃ est une solution basique réalisable, et que B est une base
réalisable.
On a alors le théorème important suivant qui constitue la base de l’algorithme du sim-
plexe.
53 CHAPITRE 4. PROGRAMMATION LINÉAIRE
Théorème 4.1. Considérons un programme linéaire sous forme standard (forme (4.3)).
Alors
— si l’ensemble des solutions réalisables est non-vide et si la fonction objectif est bornée
inférieurement sur cet ensemble, alors il existe une solution optimale.
— s’il existe une solution optimale, alors il existe une solution optimale qui soit basique
réalisable.
Théorème 4.2. Considérons un programme linéaire sous forme standard (forme (4.3)). Si
l’ensemble des solutions réalisables est non-vide et si la fonction objectif n’est pas bornée
inférieurement sur cet ensemble, alors il existe x0 et q tels que les points x(t) = x0 − tq
soient tous réalisables pour t ≥ 0, et tels que limt→+∞ cT x(t) = −∞.
L’ensemble des points x(t) = x0 − tq pour t ≥ 0 est appelé rayon infini. La variable t
est le paramètre de ce rayon, x0 son origine et q sa direction.
4.2.4 Polyèdres
On peut également essayer de voir ce que signifie le programme (4.3), un peu comme
on l’a fait dans la résolution de l’exemple introductif des navets et des courgettes. Les
contraintes Ax = b et x ≥ 0 délimitent ce qu’on appelle un polyèdre, c’est-à-dire une
partie de Rn obtenue comme intersection d’un nombre fini de demi-espaces fermés délimités
par des hyperplans.
On vérifie facilement qu’un polyèdre est convexe, c’est-à-dire que pour toute paire de
points x et y d’un polyèdre P , l’ensemble des points du segment [x, y] est inclus dans P .
Un polyèdre possède en général des points extrêmes ou sommets, qui sont les “pointes”,
ou les “piques” du polyèdre (voir Figure 4.2). Pour éviter la confusion avec les sommets des
graphes, nous utiliserons plutôt l’appellation “points extrêmes” dans ce cours. On définit
n
' 4m .
2. Par exemple, pour n = 2m, on a m
CHAPITRE 4. PROGRAMMATION LINÉAIRE 54
Autrement dit, on ne peut avoir un segment inclus dans P et non réduit à un point qui
contienne v.
En réalité, comme le montre le théorème suivant, les points extrêmes et les solutions
basiques réalisables recouvrent le même concept.
Théorème 4.3. Soit P l’ensemble des solutions réalisables du programme linéaire (4.3) (P
est donc un polyèdre). Soit v ∈ P . Les deux assertions sont équivalentes :
— v est une solution basique réalisable de (4.3).
— v est un point extrême de P .
On peut voir une illustration sur la Figure 4.3, qui montre la solution optimale au
problème des navets et des courgettes du début du chapitre.
4.3 Algorithmes
Il y a trois (familles d’) algorithmes résolvant les programmes linéaires : le simplexe, les
ellipsoı̈des et les points intérieurs.
Nous allons décrire dans ces grandes lignes l’algorithme du simplexe et très brièvement
l’algorithme des points intérieurs. Notre objectif est de permettre d’en comprendre les prin-
cipes et certaines de leurs propriétés. Rappelons que lorsqu’un problème est décrit comme
un programme linéaire, il est inutile de programmer un algorithme pour le résoudre : de
nombreux logiciels, dont certains libres, le font déjà avec d’excellentes performances. Même
EXCEL dispose d’une implémentation de l’algorithme du simplexe.
Pour la description exacte de ces algorithmes, il existe de nombreux ouvrages. Un excellent
ouvrage qui couvre l’ensemble de la programmation linéaire et de ces algorithmes est celui
55 CHAPITRE 4. PROGRAMMATION LINÉAIRE
4x + 5y = 22 x
Figure 4.3 – La solution optimale au problème des navets et des courgettes est un sommet du polyèdre.
CHAPITRE 4. PROGRAMMATION LINÉAIRE 56
de Matoušek et Gärtner [21]. Sur l’algorithme du simplexe, le meilleur livre est certainement
celui de Chvátal [4]. Sur l’algorithme des ellipsoı̈des, le livre de Grötchel, Lovász et Schrijver
est une excellente référence et un grand classique [13]. Enfin, sur les points intérieurs, l’article
de Terlaky est une bonne introduction aux points intérieurs [22].
Sur le plan pratique, l’algorithme des ellipsoı̈des n’a pas encore fait ses preuves, ce qui
explique qu’il ne soit pas décrit dans ce cours. Son intérêt est (pour le moment ?) théorique
et historique puisqu’il constitue le premier algorithme polynomial proposé pour la program-
mation linéaire (en 1979, par Khachyan). Avant 1979, la question, alors ouverte, de savoir
s’il était possible de résoudre la programmation linéaire en temps polynomial passionnait
beaucoup de chercheurs.
4.3.1 Le simplexe
L’idée de l’algorithme du simplexe est de passer de base réalisable en base réalisable en
améliorant à chaque fois la valeur du critère. Comme le nombre de bases est fini, on obtient
l’optimum ou la preuve que le programme est non borné en un nombre fini d’étapes.
On suppose que l’on connaı̂t au départ une base réalisable B. L’algorithme du simplexe
commence par réécrire le programme (4.3) sous la forme équivalente
pour laquelle on est à nouveau capable de lire la valeur du critère pour la solution basique
réalisable associée à B 0 (c’est cTB 0 A−1
B 0 b) et la solution basique réalisable elle-même (x̃B 0 =
−1
AB 0 b et x̃N 0 = 0).
Et on recommence.
L’optimalité est atteinte quand tous les coefficients de cTN 0 − cTB 0 A−1 B 0 AN 0 sont ≥ 0. En
effet, quelque soit alors le choix de xN 0 , qui est à coefficients positifs ou nuls, le critère verra
sa valeur augmenter.
De deux choses l’une, soit on termine sur une base optimale, soit à la lecture des coeffi-
cients, on voit que le programme est non bornée (i.e −∞ est la valeur optimale) : cela arrive
lorsque toutes les composantes de la colonne q correspondante à la variable entrante sont
négatives ou nulles, on a alors un rayon infini d’origine x̃B 0 et de direction q.
On a supposé que l’on disposait d’une base réalisable de départ. C’est en effet souvent le
cas. Par exemple, si le programme est sous forme canonique et si b ≥ 0, l’ajout des variables
d’écart fait apparaı̂tre une sous-matrice identité, voir Section 4.2.1, dont les colonnes sont
une base réalisable naturelle de départ. Sinon, on dispose de techniques standard pour tester
la réalisabilité du programme et trouver une base réalisable, voir Exercice 4.6.5.
Interprétation géométrique : L’algorithme du simplexe s’interprète facilement géométriquement.
En effet, deux bases réalisables voisines fournissent des solutions basiques réalisables qui sont
des points extrêmes confondus ou voisins (au sens des arêtes du polyèdre) du polyèdre des so-
lutions réalisables. L’opération de pivot consiste à “glisser” le long d’une arête du polyèdre 3
pour aller vers un point extrême voisin, de meilleur valeur par la fonction objectif.
Par conséquent, la suite des solutions basiques réalisables et des pivots générés par l’al-
gorithme du simplexe fournit une trajectoire qui passe par des points extrêmes et des arêtes
du polyèdre et qui cherche à se diriger dans le sens de c.
Efficacité de l’algorithme du simplexe : On considère qu’en général, pour un programme à
m contraintes, l’algorithme du simplexe va faire entre 2m et 3m opérations de pivots avant
d’arriver à l’optimum. La réécriture du système lors d’un pivot nécéssite O(m2 ) opérations.
On a donc en général O(m3 ) opérations pour résoudre un programme linéaire par l’algorithme
du simplexe, ce qui est tout à fait raisonnable. Sur des instance réelles, le simplexe fonctionne
bien.
Cela dit, il existe des instances pour lesquelles le nombre de pivots est exponentiel. La
question de savoir s’il existe une règle de pivot – c’est-à-dire une façon de choisir la variable
entrante lorsque le choix est possible – conduisant à un comportement polynomial est une
(importante) question ouverte.
Min fµ (x)
s.c. Ax = b (4.9)
x > 0,
4.4 Dualité
4.4.1 Dualité faible, dualité forte
Nous abordons maintenant la propriété théorique fondamentale de la programmation
linéaire, dont les applications sont innombrables. Il s’agit de la propriété de dualité.
En suivant la méthode présentée en Section 2.3.5, à tout programme linéaire, on peut
associer un autre programme linéaire, son dual. Le premier programme est le programme
primal. Lors de la transformation, les variables du primal deviennent les contraintes du dual
et les contraintes du primal deviennent les variables du dual.
Considérons par exemple, le programme linéaire suivant, sous forme standard :
Min cT x
s.c. Ax = b (4.10)
x ≥ 0.
Son dual se définit alors
Max bT y
(4.11)
s.c. AT y ≤ c.
Cela se vérifie aisément en suivant la méthode présentée à la Section 2.3.5.
59 CHAPITRE 4. PROGRAMMATION LINÉAIRE
Noter que chaque yi multiplie la ième ligne (la contrainte) de A, pour i = 1, . . . , m, et que
chaque colonne de A, associée chacune à une des n variables du programme (4.10), devient
une contrainte pour le programme (4.11).
Nous expliquons maintenant une preuve de l’inégalité de dualité faible, alternative à celle
présentée en Section 2.3.5.
Prenons une solution réalisable x du primal et une solution réalisable y du dual. Multi-
plions à gauche les contraintes du primal par y. On obtient
y T Ax = y T b.
En utilisant les contraintes du dual et le fait que les composantes de x sont positives, on
obtient cT x ≥ y T b ou plus lisiblement
cT x ≥ bT y.
On retrouve bien la dualité faible. En particulier, la valeur optimale du dual minore la valeur
optimale du primal (si optimum il y a).
Min cT x
s.c. Ax = b (P)
x≥0
et
Max bT y
s.c. AT y ≤ c, (D)
une et une seule des possibilités suivantes se réalise
1. Ni (P), ni (D) n’ont de solution réalisable.
2. (P) est non borné et (D) n’a pas de solution réalisable.
3. (D) est non borné et (P) n’a pas de solution réalisable.
4. (P) et (D) sont tous deux réalisables. Ils ont alors tous deux des solutions optimales,
respectivement x∗ et y ∗ , et l’on a
cT x∗ = bT y ∗ .
Autrement dit, le minimum de (P) est égal au maximum de (D).
La preuve est omise, mais ce théorème peut se prouver soit en utilisant un lemme classique
en géométrie – le lemme de Farkas – soit en utilisant l’écriture de la base optimale dans
l’algorithme du simplexe (voir Exercice 4.6.4).
CHAPITRE 4. PROGRAMMATION LINÉAIRE 60
Dans le tableau suivant, on donne toutes les situations possibles. Un bon exercice consiste
à redémontrer ces programmes en utilisant la méthode de la Section 2.3.5.
Programme linéaire primal Programme linéaire dual
Variables x1 , x2 , . . . , xn y1 , y2 , . . . , ym
Matrice A AT
Membre de droite b c
Fonction objectif Min cT x Max bT y
ième contrainte a ≤ yi ≤ 0
Contraintes ≥ yi ≥ 0
= yi ∈ R
xj ≤ 0 jème contrainte a ≥
xj ≥ 0 ≤
xj ∈ R =
Une propriété importante de la dualité en programmation linéaire, qui se vérifie direc-
tement sur le tableau ci-dessus mais aussi à partir de la définition de la Section 2.3.5, est
que
Soit une firme F qui veut racheter les ressources de l’entreprise E. A quels prix doit-elle
le faire pour tout racheter au coût minimum ?
On note yi le prix de la ressource i. F doit fixer les yi de manière à ce que m
P
i=1 aij yi ≥
cj pour tout j = 1, . . . , n. En effet, pour tout j, cela garantit que E a intérêt à vendre
les ressources nécessaire pour produire une unité de j plutôt que de la produire. D’où le
programme mathématique suivant auquel se trouve confronté F.
Min Pm
P
i=1 bi yi
m
s.c. i=1 aij yi ≥ cj j = 1, . . . , n
yi ≥ 0 i = 1, . . . , m.
Théorème 4.5. Dans tout jeu matriciel à somme nulle, il existe un équilibre de Nash en
stratégies mixtes.
Démonstration. On peut supposer que toutes les entrées de A sont strictement positives. En effet, ajouter
une même constante sur chaque entrée de la matrice ne change rien au jeu.
Considérons le programme linéaire
Pn
Max i=1 xi
s.c. Ax ≤ 1 (4.12)
x ≥ 0.
Son dual est Pm
Min j=1 yj
s.c. y T A ≥ 1T (4.13)
y ≥ 0.
Le programme (4.12) est réalisable, car x = 0 est une solution réalisable. Le programme (4.13) est également
réalisable : A a toutes ses entrées strictement positives ce qui implique que tout y suffisament grand est
∗
solution réalisable.P
D’après le P
théorème 4.4, il existe
Pmx solution
Pn optimale du primal et y ∗ solution optimale
m n
du dual, telle que i=1 xi = j=1 yj . Soit w = i=1 xi = j=1 yj . Les solutions x̃ := w1 x∗ et ỹ := w1 y ∗
∗ ∗ ∗ ∗
On peut par ailleurs démontrer facilement que, même s’il y a plusieurs équilibres de Nash
en stratégies mixtes, la quantité y T Ax – i.e. w1 dans la preuve ci-dessus – ne change pas. On
l’appelle valeur du jeu.
4.6 Exercices
4.6.1 Production de boissons
Une entreprise fabrique trois types de boissons : XXX, YYY et ZZZ qui rapportent
respectivement 1, 55, 3, 05 et 4, 80 le litre. Chaque boisson a un niveau minimal de production
hebdomadaire qui sont respectivement de 1020, 1450 et 750 litres. 20 litres de chaque boisson
requiert un temps en heures de fabrication, un temps de mélange et un temps d’embouteillage.
XXX YYY ZZZ
fabrication 2 3 6
mélange 4 5,5 7,5
embouteillage 2 1 3,5
Pendant la semaine à venir, l’entreprise aura 708 heures disponibles en fabrication, 932
en mélange et 342 en embouteillage. Formuler un modèle donnant un plan de production qui
maximise le profit.
2. Montrer que le système (4.14) a une solution réalisable si et seulement si le programme (4.15)
a une valeur optimale = 0.
Par conséquent, l’algorithme du simplexe est une méthode pour résoudre un système de
la forme du système (4.14). En effet, le programme (4.15) a une solution basique réalisable
facile à identifier : y = b et x = 0. On peut alors dérouler l’algorithme du simplexe aisément
sur le programme (4.15) à partir de cette base initiale. Noter que s’il y a une solution au
système (4.14), cette méthode lui trouve une solution basique réalisable. C’est donc également
une méthode pour trouver une première solution réalisable à un programme linéaire pour
lequel il n’y en a pas d’évidente.
3. Réciproquement, montrer avec la théorie de la dualité que si on a une méthode pour trouver
une solution réalisable de n’importe quel système d’équations et d’inéquations linéaires, alors
on peut utiliser cette méthode pour résoudre les programmes linéaires.
Min cT x
s.c. Ax = b (4.16)
xj ∈ N j = 1, . . . , n
Flots et Coupes
La notion de flot dans un graphe est naturelle : étant donné un réseau de transport (train,
tuyau, cables électriques), avec des capacités sur les arcs, quelle quantité de biens peut-on
faire transiter au maximum ? Ou alors, en supposant qu’à chaque arc est attaché un coût
unitaire, à quel coût minimum peut-on faire transiter un volume de biens donné ?
Une notion duale est celle de coupe dans un graphe. Une coupe est un ensemble d’arcs
intersectant tout chemin entre deux sommets fixés. Les applications des coupes sont nom-
breuses : positionnement de postes d’enquêtes, robustesse de réseaux, imagerie, etc.
5.1.1 Généralités
Soit un réseau modélisé par un graphe orienté D = (V, A), muni d’une capacité u → R+
et de deux sommets particuliers s (la source) et t (le puits). Une fonction f : A → R+ est
un s-t flot si f (a) ≤ u(a) pour tout arc a ∈ A et si pour tout sommet v ∈ / {s, t}, la loi de
conservation X X
f (a) = f (a)
a∈δ − (v) a∈δ + (v)
est respectée. Un s-t flot f est tel que f (a) ∈ Z pour tout a ∈ A, alors il est entier.
Une s-t coupe est une coupe δ(X) telle que s ∈ X et t ∈ / X. Etant donnée une s-t coupe,
il est intuitivement clair qu’un flot aura
P une valeur inférieure à sa capacité, où la capacité
+
d’une s-t coupe δ (X) est définie par a∈δ+ (X) u(a). Le lemme suivant formalise entre autres
cette propriété.
Lemme 5.1. Soit δ + (X) une s-t coupe et soit f un s-t flot quelconque. Alors
X X
value(f ) = f (a) − f (a).
a∈δ + (X) a∈δ − (X)
En particulier,
X
value(f ) ≤ u(a). (5.1)
a∈δ + (X)
CHAPITRE 5. FLOTS ET COUPES 66
De plus, si f est entier, alors ces coefficients peuvent être choisis entiers.
Il peut alors être facilement vérifié que
X
value(f ) = λP .
P ∈P
La preuve de la Proposition 5.1 n’est pas triviale, mais constitue tout de même un exercice
raisonnable.
Ce problème est polynomial car il peut se modéliser comme un programme linéaire, voir
Exercice 5.3.2. La nature particulière du problème a poussé les chercheurs à concevoir des al-
gorithmes ad hoc plus performants. L’un de ces algorithmes est celui d’Edmonds et Karp [8],
qui est également polynomial. Il est décrit dans le paragraphe suivant.
Un problème associé est celui de la s-t coupe minimum. C’est en réalité le problème dual
du problème du s-t flot maximum, au sens de la dualité de la programmation linéaire, voir
Exercice 5.3.2.
Donnée : Un graphe orienté D = (V, A), deux sommets particuliers s et t, et des capacités
u : A → R+ .
Tâche : Trouver une s-t coupe de capacité minimum.
Proposition 5.2. Un s-t flot f est optimal si et seulement si il n’y a pas de chemin f
augmentant.
Démonstration. Supposons qu’il y ait un chemin f -augmentant P . Alors µ := mina∈P uf (a) est strictement
positif. Si a ∈ P est dans le même sens dans A (i.e. a ∈ A), alors on définit f 0 (a) := f (a) + µ ; sinon (i.e.
a−1 ∈ A), alors on définit f 0 (a) := f (a) − µ. On vérifie alors que value(f 0 ) = value(f ) + µ. On voit que f
n’est pas optimal.
Réciproquement, supposons qu’il n’y a pas de chemin f -augmentant. Posant X l’ensemble des sommets
que l’on peut atteindre depuis s dans Df , cela signifie que pour les arcs a quittant X (formellement a ∈
+ −
δP (X)), on a f (a)P= u(a) et que pour P ceux entrant dans X (formellement a ∈ δ (X)), on a f (a) = 0. Donc
a∈δ + (X) f (a) − a∈δ − (X) f (a) = a∈δ + (X) u(a), ce qui signifie
X
value(f ) = u(a).
a∈δ + (X)
Comme le terme de droite est une borne supérieure sur la valeur optimale d’un s-t flot (Lemme 5.1), le flot
f est optimal.
Théorème 5.1. L’algorithme d’Edmonds et Karp trouve un s-t flot maximum en O(nm2 ).
Remarque
Il existe maintenant de nombreux algorithmes polynomiaux. Le plus rapide de tous est
celui de Goldberg et Tarjan : ils ont montré qu’il était possible de trouver un flot maximum
en O(nm log n2 /m).
On obtient donc
Théorème 5.2. La valeur d’un s-t flot maximum est égale à la capacité d’une s-t coupe
minimum.
De plus, la discussion précédente implique que l’on peut trouver une s-t coupe minimum
en O(nm2 ). En effet, après avoir appliqué l’algorithme d’Edmonds et Karp, l’ensemble X
des sommets que l’on peut atteindre dans Df depuis s est tel que δ + (X) est une coupe de
capacité minimale.
Théorème 5.3. L’algorithme d’Edmonds et Karp trouve une s-t coupe minimum en O(nm2 ).
Théorème 5.4. Si toutes les capacités sont entières, alors il existe un s-t flot maximum
entier, et l’algorithme d’Edmonds et Karp le trouve.
Démonstration. La preuve est immédiate : si f est entier à une itération de l’algorithme, µ l’est aussi, et f
le sera encore à l’itération suivante.
Remarque
On peut définir les S-T coupes où S et T sont des ensembles disjoints de sommets. Une
S-T coupe est un ensemble d’arcs de la forme δ + (X), avec S ⊆ X et T ∩ X = ∅. Une S-T
coupe de capacité minimum se trouve en ajoutant une source fictive s, un puits fictif t, des
arcs (s, u) pour tout u ∈ S et des arcs (v, t) pour tout v ∈ T . Ces nouveaux arcs sont alors
munis de capacité infinis.
Cette astuce consistant à ajouter une source et un puits fictifs est utile dans de nombreuses
situations.
Remarque
Dans le cas non-orienté, on appelle s-t coupe un ensemble d’arêtes de la forme δ(X),
avec s ∈ X et t ∈
/ X. Trouver une s-t coupe de capacité minimum se ramène simplement à
remplacer chaque arête par deux arcs opposés.
Remarque
Considérons le problème suivant.
Ce problème coı̈ncide avec celui de la s-t coupe de capacité minimum. En effet, une s-t
coupe est une solution réalisable pour le problème de l’ensemble d’arcs déconnectant mi-
nimum. Inversement, s’il existe une solution réalisable B pour le problème de l’ensemble
d’arcs déconnectant minimum, alors l’ensemble X des sommets que l’on peut atteindre dans
D depuis s sans utiliser d’arcs de B est tel que δ + (X) ⊆ B.
effectués sur des tronçons d’autoroute. Faire un contrôle sur le tronçon t coûte ct . Le problème
consiste à trouver le sous-ensemble de tronçons sur lesquels les contrôles vont être effectués
tel que tout camion allant de P à Q passe par un contrôle, et ce, à coût minimum.
Avec les remarques ci-dessus, on peut voir que ce problème se modélise comme un
problème de s-t coupe minimum.
T + T0
T 0 := T . Sinon, c’est que T était trop petit, et on pose T :=
2
et on laisse T 0 := T 0 .
La solution optimale x∗ est telle T ≤ T (x∗ ) ≤ T 0 . On peut s’arrêter dès que T 0 − T est
plus petit qu’une quantité fixée au préalable.
On a résolu un problème d’optimisation par une recherche binaire, chaque étape étant
un problème de décision.
Cette façon de procéder est très efficace en pratique, plus que l’autre solution consistant
à voir le problème de l’affectation de tâches comme un programme linéaire.
On peut se demander si, dans le cas où les ti sont entiers, on a nécessairement alors une
solution optimale entière. L’auteur de ce polycopié ne sait pas. L’intérêt pourrait être de
montrer que la recherche binaire termine en un nombre fini d’étapes.
5.2.1 Généralités
Soit un graphe orienté D = (V, A), muni de capacités
P `, u : A → R+ tels que `(a) ≤ u(a)
pour tout a ∈ A, et des nombres b : V → R tels que v∈V b(v) = 0. Une fonction f : A → R+
est un b-flot si pour tout arc a ∈ A, on a `(a) ≤ f (a) ≤ u(a) et si pour tout sommet v ∈ V ,
la loi de conservation X X
f (a) − f (a) = b(v)
a∈δ + (v) a∈δ − (v)
est respectée.
Les sommets v tels que b(v) > 0 sont appelés sources et les sommets v tels que b(v) < 0
sont appelés puits. Pour une source, b(v) est l’offre ; pour un puits, b(v) est la demande.
Dans le cas particulier où tous les b(v) sont nuls, on parle de circulation.
Proposition 5.3. Soit f un b-flot. Notons P l’ensemble des chemins élémentaires reliant
les sources aux puits et C l’ensemble des circuits élémentaires. Il existe alors des coefficients
réels positifs (λP )P ∈P et (µC )C∈C tels que
X X
f= λP χP + µC χC .
P ∈P C∈C
De plus, si f est entier, alors ces coefficients peuvent être choisis entiers.
5.2.2 Le problème
On suppose que l’on a une fonction de coût c : A → R.
On peut alors se demander, parmi tous les b-flots, lequel est de plus petit coût, où le coût
d’un b-flot f est défini par X
c(a)f (a).
a∈A
Les applications des flots de coût minimum sont innombrables. Nous verrons ce que
cela peut apporter au problème d’affectation de tâches vu précédemment. Tout comme le
problème de flot maximum, le problème du b-flot de coût minimum se formule comme un
programme linéaire et peut donc être résolu avec ma méthode des points intérieurs (en temps
polynomial donc) ou par l’algorithme du simplexe.
En 1985, Goldberg et Tarjan [12] ont montré qu’il existait un algorithme particulièrement
efficace pour résoudre le problème flot de coût minimum. L’algorithme travaille encore sur
le graphe résiduel, en définissant c(a−1 ) := −c(a) pour a ∈ D et
somme des coûts des arcs du circuit C divisée par le nombre d’arcs du circuit C.
On repète
Théorème 5.5. On peut trouver un b-flot de coût minimum en O(n2 m3 log n).
73 CHAPITRE 5. FLOTS ET COUPES
Comme pour le problème du flot maximum, si les capacités sont entières, il existe une
solution optimale entière, que l’on trouve sans plus de difficulté.
Théorème 5.6. Supposons toutes les capacités entières et tous les b(v) entiers. S’il existe un
b-flot de coût minimum, il en existe un entier de coût minimum, et l’algorithme de Goldberg
et Tarjan le trouve.
Un corollaire immédiat mais important de ce théorème est que dans le cas où les capacités
sont entières et tous les b(v) entiers, alors s’il existe un b-flot, alors il en existe un entier.
Cela peut se voir en prenant un coût nul sur chaque arc.
Si l’on accepte d’avoir une complexité qui dépend de la taille des nombres de l’input (on
parle alors d’algorithme faiblement polynomial), on peut avoir d’autres bonnes complexités.
Par exemple, l’algorithme classique d’Edmonds et Karp [8] tourne en O(m(m + n log n)L),
où L est le nombre maximum de bits pour coder un coefficient du problème.
lequel est résolu par un problème de flot maximum, comme indiqué au début de cette dis-
cussion.
CHAPITRE 5. FLOTS ET COUPES 74
5.3 Exercices
5.3.1 Valeur d’un s-t flot
Prouver le Lemme 5.1.
5.3.2 Formulation des problèmes de flots maximum sous forme de programme linéaire
Montrer que le problème de flot maximum s’écrit comme un programme linéaire. Ecrire
son dual. Quelle remarque pouvez-vous faire ?
75 CHAPITRE 5. FLOTS ET COUPES
yt = yt−1 + xt − dt , (5.2)
pour t = 1, 2, . . . , T .
Sur la période t, le coût unitaire de stockage est st ≥ 0 et le coût unitaire de production
est pt ≥ 0. On veut gérer le stock au coût minimum.
2. Montrer que ce problème se modélise comme un programme linéaire.
3. Application numérique : On considère les données du tableau suivant
t= 1 2 3 4
dt 5 4 1 3
st 1 1 1 xxx
pt 2 3 3 4
Pt 9 5 5 5
77 CHAPITRE 5. FLOTS ET COUPES
Indiquer le coût minimal de gestion de stock, ainsi que les niveaux de productions (en
p.4 , des programmes linéaires sont donnés).
4. Montrer que ce problème peut également se modéliser comme un problème P de b-flot
de coût minimum. (Indication : introduire un sommet “source” v avec b(v) = Tt=1 dt et des
sommets “puits” wt avec b(wt ) = −dt ; à vous d’indiquer les arcs, les coûts sur les arcs, les
capacités sur les arcs, etc.) Justifier la modélisation.
5. Quel peut être l’intérêt d’une telle modélisation alors qu’on sait résoudre le problème
avec un solveur de programmation linéaire ?
P tout v ∈ V .
Donnée : Un graphe D = (V, A) orienté, des réels cv pour
Tâche : Trouver un sous-ensemble fermé S ⊆ V tel que v∈S cv soit maximal.
1. Expliquez pourquoi le problème peut se modéliser sous la forme d’un problème de
fermé maximum.
L’objectif va maintenant être de modéliser le problème du fermé maximum comme un
problème de s-t coupe de capacité minimale.
On construit un nouveau graphe D̃ = (Ṽ , Ã) en ajoutant un sommet source s et un
sommet puits t à V . On note V + = {v ∈ V : cv ≥ 0} et V − = {v ∈ V : cv < 0}. L’ensemble
à est alors A auquel on ajoute les arcs {(s, v) : v ∈ V + } et les arcs {(v, t) : v ∈ V − }. On
met une capacité u(s,v) = cv pour v ∈ V + et u(v,t) = −cv pour v ∈ V − .
2. Quelles capacités ua mettre sur les arcs a ∈ A de manière à ce que tout X ⊆ V tel que
+
δD̃ (X ∪ {s}) soit une s-t coupe de D̃ de capacité minimale soit un ensemble fermé de D ?
3. Soit X ⊆ V un ensemble fermé de D. Montrez que
X X X
ua = cv − cv .
a∈δ + (X∪{s}) v∈V + v∈X
D̃
CHAPITRE 5. FLOTS ET COUPES 78
Les nombres non-entourés sont les capacités; les nombres entourés forment le flot.
Graphe résiduel:
v1 6 6 v2
v1 6 v2
10 6 5
5 1 6
3 6
0
s 5 3 3
1 3
4 s t
t 1
3 5
2 3 7 2
3
2
3 3 2
5
5 8 v4 v4
v3 v3
5
L’objectif de ce cours est d’étudier un objet central de l’optimisation discrète et d’en voir
quelques applications parmi les plus importantes. Il s’agit des graphes bipartis.
6.1 L’objet
Un graphe biparti est un graphe dont l’ensemble des sommets peut être partitionné en
deux parties X et Y telles que toute arête à l’une de ces extrémités dans X et l’autre dans Y .
Voir la Figure 6.1. On a la proposition suivante, très utile, dont la démonstration est laissée
en exercice.
Proposition 6.1. Un graphe est biparti si et seulement si il ne contient pas de circuit de
taille impaire.
Ce problème modélise typiquement des situations où l’on veut affecter des personnes à
des tâches ou à des services. Le poids d’une arête uv représente alors le bénéfice obtenu en
affectant u à v.
Le problème du couplage de poids maximum se résout en temps polynomial. En effet,
ce problème peut se modéliser comme un problème de flot de coût maximum (qui est un
problème de flot de coût minimum avec des coûts opposés) : on oriente toutes les arêtes de
X vers Y , on ajoute un sommet s et un sommet t, on ajoute des arcs (s, v) pour v ∈ X et
(v, t) pour v ∈ Y ; enfin, on ajoute un arc (s, t), et on pose b(s) = |X| = −b(t) et b(v) = 0
CHAPITRE 6. GRAPHES BIPARTIS : PROBLÈME D’AFFECTATION, PROBLÈME DE TRANSPORT, MARIAGES STABLES 82
ailleurs. Enfin, les capacités des arcs sont partout = +∞ sauf sur les arcs (s, v) et (v, t) où
elles sont égales à 1, et les coûts sont partout nuls sauf sur les arcs de X à Y où ils sont
égaux aux poids w. C’est un problème de flot de coût maximum : en effet, tout flot entier
induit un couplage de même poids ; et tout couplage induit un flot entier de même coût.
Tout algorithme trouvant des flots entiers de coût optimal trouve donc la solution (en
particulier celui vu au chapitre précédent). En fait, il existe un algorithme plus efficace,
appelé algorithme hongrois, découvert par Kühn en 1955 [19].
Soit G = (V, E) notre graphe biparti, avec les ensembles X et Y partitionnant V et
n’induisant chacun aucune arête. On a de plus une fonction w de poids sur E. L’algorithme
hongrois commence avec un couplage M = ∅. Ensuite, on répète
Le théorème max flot–min coupe permet également de montrer le théorème suivant, dû
à König (la preuve est laissée en exercice). On rappelle qu’une couverture par les sommets
dans un graphe G = (V, E) est un sous-ensemble de sommets C ⊆ V tel que toute arête e
de G soit incident à au moins un sommet de C et qu’on note τ (G) la cardinalité minimale
d’une couverture par les sommets.
Théorème 6.3. Dans un graphe biparti, on a
ν(G) = τ (G).
Rappelons que l’inégalité ν(G) ≤ τ (G) est facile à montrer, voir Proposition 2.1. L’algo-
rithme de Ford-Fulkerson permet par la même construction que celle utilisée dans la preuve
de calculer une telle couverture optimale. Cela dit, il existe des algorithmes plus rapides.
Il se résout en temps polynomial par un algorithme de flot de coût minimum, avec une
construction similaire à celle de la section précédente. Noter que si on ne veut que maximiser
la cardinalité, on peut utiliser un algorithme de flot maximum (plus rapide), toujours avec
la même construction.
Exemple
On se place dans un centre de tri de palettes (plateforme logistique, aéroport, etc.). En
début de journée, on a n palettes 1, . . . , n à trier. La palette i contient des marchandises
mi,j . Chaque marchandise est caractérisée par une heure limite de tri tij . Si la palette où
se trouve la marchandise mij est triée avant l’heure tij , on gagne ci , sinon, on perd di . On
suppose que
• on dispose de k personnes pour trier,
• chaque personne met une heure pour trier une palette,
• on dispose de T créneaux d’une heure, sans contrainte sur le nombre de personnes
pouvant travailler sur un créneau.
Trouver la stratégie qui minimise l’amende totale.
C’est un problème de couplage généralisé. En effet, on considère le graphe biparti suivant.
D’un côté, on a les palettes 1, 2, . . ., de l’autre les horaires 1, 2, . . . , T . L’arête ih modélise
le fait qu’on trie la palette i ∈ {1, . . . , n} sur le créneau h ∈ {1, . . . , T }. Si h ≤ tij , on
met un poids ci sur l’arête it ; sinon, on met −di . On définit a(i) = b(i) = 1 pour les
palettes i = 1, . . . , n, signifiant qu’il faut trier chaque palette exactement une fois. On définit
également a(h) = 0 et b(h) = k pour le créneau h, signifiant qu’on ne peut pas trier plus de
k palettes sur un créneau horaire.
Problème de l’affectation
Donnée : Un graphe G = (V, E) biparti avec des poids w : E → R sur les arêtes.
Tâche : Trouver un couplage parfait de poids maximal.
de réalisation de la tâche par un employé donné. On veut réaliser toutes les tâches avec un
coût minimal, en supposant que tout employé peut réaliser n’importe quelle tâche.
C’est un cas particulier des couplages généralisés : pour s’y ramener, il suffit de poser
a(v) = b(v) = 1 pour tout v.
Théorème 6.4. On sait résoudre le problème de l’affectation en O(n(m + n log n)).
Il y a de nombreux algorithmes qui résolvent ce problème avec cette complexité. On peut
également appliquer l’algorithme hongrois auquel il a été fait mention ci-dessus. En effet,
l’algorithme hongrois fait en fait mieux que trouver un couplage de poids maximum : il
trouve, pour un k fixé, le couplage de cardinalité k de plus grand poids. Il suffit alors de
multiplier par −1 les poids et de chercher le couplage de cardinalité n/2.
Théorème 6.5. Il existe toujours un couplage stable dans un graphe biparti. De plus, un tel
couplage se trouve en O(nm).
Ce qui est remarquable, c’est que la preuve est simple, algorithmique et peut se raconter
sous la forme d’une histoire.
Démonstration. Tous les matins, chaque garçon invite à dı̂ner la fille qu’il préfère parmi celles qui ne lui ont
pas déjà refusé une invitation. Chaque fille qui a été invitée dı̂ne le soir avec le garçon qu’elle préfère parmi
ceux qui l’ont invitée ce jour là, à condition bien sûr qu’elle accepterait éventuellement de se marier avec lui.
Tout garçon qui a vu son invitation refusée par une fille décide de ne plus jamais l’inviter.
L’algorithme se poursuit tant qu’au moins une invitation change. Les couples qui ont dı̂né entre eux le
dernier soir sont mariés.
Pour se convaincre que cet algorithme fournit un couplage stable, il faut d’abord remarquer que
toute fille qui est invitée un soir à dı̂ner est sûre de dı̂ner le lendemain avec un garçon qui lui plaise au
moins autant.
En effet, si une fille, disons Alice, est invitée à dı̂ner par un garçon, disons Bob, c’est que Bob préfère
Alice à toutes celles qui ne l’ont pas déja refusé. Alice est donc sûre d’être réinvitée le lendemain par Bob,
mais elle sera peut-être aussi invitée par de nouveaux garçons qui viennent d’essuyer des refus et pour qui
elle est désormais le meilleur choix restant. Peut-être que Charlie, l’un de ces nouveaux garçons, lui plait plus
que Bob, dans ce cas elle dı̂nera avec Charlie, en congédiant Bob. Dans tous les cas, Alice dı̂ne le lendemain
avec un garçon au moins aussi plaisant.
Ensuite, on remarque que
l’algorithme se termine.
En effet, une invitation qui a été refusée ne sera jamais répétée. À chaque étape précédant la fin de
l’algorithme, au moins une invitation est refusée. Le nombre d’étapes avant que la liste des invitations ne se
stabilise est donc borné par le nombre d’invitations possibles, i.e. par le nombre de filles fois le nombre de
garçons.
Enfin, lorsque l’algorithme se termine,
les mariages fournissent un couplage stable.
En effet, considérons le mariage obtenu à l’issue de l’algorithme.
Supposons qu’Alice et Bob ne sont pas mariés ensemble et qu’Alice préfère Bob à son mari actuel. Cela
implique que Bob ne l’a jamais invitée car sinon, en vertu de la remarque ci-dessus, son mari serait forcément
mieux que Bob. Si Bob ne l’a jamais invitée, c’est qu’il est marié à une fille qu’il préfère à Alice.
Supposons qu’Alice et Bob ne sont pas mariés ensemble et que Bob préfère Alice à sa femme actuelle.
Comme Bob fait ses invitations dans l’ordre décroissant de ses préférences, c’est qu’Alice a refusé une
invitation de sa part, et donc qu’Alice, ce matin-là et les suivants, a reçu des invitations plus intéressantes
de son point de vue.
Dans tous les cas, si Alice et Bob ne sont pas mariés ensemble, c’est que l’un des deux est mariés à
quelqu’un qu’il préfère. L’ensemble des mariages est donc stable.
6.6 Exercices
6.6.1 Une caractérisation des graphes bipartis
Prouver la Proposition 6.1.
87 CHAPITRE 6. GRAPHES BIPARTIS : PROBLÈME D’AFFECTATION, PROBLÈME DE TRANSPORT, MARIAGES STABLES
O E
7.1 Introduction
Jusqu’à présent nous avons vu un certain nombre de problèmes, certains NP-difficiles,
d’autres polynomiaux. Pour les problèmes polynomiaux, nous avons discuté les algorithmes
possibles pour les résoudre ; pour les autres, rien n’a été indiqué, ce qui pourrait laisser penser
qu’on ne sait pas les résoudre. Bien entendu, c’est faux, et heureusement, car de nombreux
(la plupart ?) problèmes industriels sont NP-difficiles.
L’objet de ce chapitre est de présenter quelques méthodes générales, indépendantes du
problème, que l’on peut employer lorsqu’on est confronté à un problème d’optimisation NP-
difficile, que l’on écrit sous la forme
Min f (x)
(7.1)
s.c. x ∈ X,
où X est supposé fini mais très grand.
Un problème NP-difficile est tel qu’il n’est pas possible (sauf si finalement il s’avèrait
que P = NP) de trouver en temps polynomial, i.e. raisonnable, la solution exacte pour
toute instance. On peut donc soit relâcher la condition solution exacte et vouloir garder
un temps raisonnable d’exécution, soit relâcher la condition sur le temps et garder le désir
d’avoir une solution exacte.
La première option conduit aux algorithmes approchés, qui calculent en temps raisonnable
des solutions qui sont proches de l’optimum. Ces algorithmes approchés sont des heuristiques
ou des métaheuristiques. Une heuristique n’a de sens que pour un problème donné, c’est un
algorithme ad hoc pour lequel le bon sens assure son fonctionnement en général. Il n’est pas
toujours possible de garantir la qualité de la solution fournie par une heuristique et l’on est
parfois obligé de les valider par des batteries de tests prouvant leurs efficacités de manière
expérimentale. Nous verrons quelques exemples dans les chapitres suivants, mais il n’existe
pas de schéma général qui permettent de dériver de tels algorithmes. Une métaheuristique
est une méthodologie très générale pour concevoir un algorithme d’optimisation. Sa vocation
est de pouvoir s’adapter à un grand nombre de problèmes d’optimisation, plus ou moins
indépendamment de leur structure. Ce sera l’objet de la Section 7.3. Il est en général très
difficile de garantir a priori leurs performances et l’on ne peut alors échapper à des validations
CHAPITRE 7. QUE FAIRE FACE À UN PROBLÈME DIFFICILE ? 90
expérimentales.
La seconde option conduit aux algorithmes exacts, comme ceux de séparation et évaluation,
ou branch-and-bound, dont nous allons présenter le principe dans la Section 7.2. Plusieurs
exemples seront donnés aux cours des séances suivantes. Un branch-and-bound suppose l’exis-
tence de bonnes bornes sur la solution (borne inférieure si on minimise, borne supérieure si
on maximise).
Dans un contexte industriel, un algorithme exact, dont le temps d’exécution peut être
long, sera plutôt utilisé pour des questions stratégiques. Une heuristique ou une métaheuristique
peut avoir des temps d’exécution très courts et sera donc plutôt utilisée pour des questions
tactiques ou opérationnelles.
7.2 Branch-and-bound
7.2.1 Description
On suppose que l’on dispose d’une fonction λ : P(X) → R qui a toute partie Y de X,
associe λ(Y ) ≤ Min x∈Y f (x). La quantité λ(Y ) est donc une borne inférieure de f sur Y .
On supposera de plus que λ se calcule “facilement” (par exemple, en temps polynomial).
Conceptuellement, l’algorithme de branch-ad-bound maintient
S
— une collection Y de parties de X telle que Y contient un minimum de f sur X
— la meilleure solution courante x̃.
Une itération est alors
L’idée principale du branch-and-bound réside dans cette dernière étape : il ne sert à rien
de conserver la partie Yi si λ(Yi ) ≥ f (x̃). En effet, comme λ(Yi ) ≤ Min x∈Yi f (x), on n’est
sûr que sur Yi on ne parviendra pas à améliorer strictement la valeur de la fonction objectif.
Il ne sert donc à rien d’explorer cette partie.
On représente souvent l’exploration de l’espace des solutions par une arborescence, dont
les nœuds sont les Y , et les arêtes codent la partition (voir exemple ci-dessous).
On comprend qu’un algorithme de branch-and-bound marchera d’autant mieux que la
borne λ sera bonne. La branchement, i.e. l’opération de partition de Y est également impor-
tante. Souvent, la structure du problème impose assez naturellement les façons de brancher.
Enfin, le choix de la partie Y dans Y peut également influencer la qualité de l’algorithme.
Deux solutions classiques sont les suivantes :
91 CHAPITRE 7. QUE FAIRE FACE À UN PROBLÈME DIFFICILE ?
Relaxation continue
Une borne inférieure à la valeur optimale vplne de (7.2) s’obtient en relâchant la contrainte
d’intégrité, i.e. en ne demandant plus à ce que x soit à coordonnées entières. En effet,
considérons
Min c · x
s.c. Ax ≤ b (7.3)
n
x∈R ,
et notons vpl sa valeur optimale. Toute solution réalisable du programme (7.2) étant solution
réalisable de (7.3), on a vplne ≥ vpl .
CHAPITRE 7. QUE FAIRE FACE À UN PROBLÈME DIFFICILE ? 92
Exemple
On considère le programme
Max x1 + 5 2
s.c. −4x1 + 2x2 ≤ 3
(7.4)
2x1 + 8x2 ≤ 39
x1 , x2 ∈ Z.
L’arborescence est donnée Figure 7.1. Remarquer que par deux fois, on évite l’exploration
d’une sous-arborescence en utilisant la borne : une fois sur le noeud x1 ≤ 1, et l’autre fois
sur le noeud x1 ≥ 4, x2 ≤ 3.
Utilisation de solveurs
Il a déjà été noté que si un problème s’écrit sous la forme d’un programme linéaire
avec des variables continues, il est inutile de procéder à l’implémentation d’un algorithme
pour résoudre ce problème : il existe déjà de nombreux solveurs – libres ou commerciaux –
utilisant l’algorithme de simplexe ou l’algorithme des points intérieurs. La même remarque
vaut également en grande partie pour les programmes linéaires en nombres entiers : la plupart
des solveurs comportent des branch-and-bound intégrés et très performants, voir l’annexe du
polycopié. La partie informatique de la résolution du problème consiste alors principalement
à écrire le problème dans un langage de modélisation simple d’utilisation (comme OPL,
AMPL, GPL,...) que peut comprendre le solveur et à appuyer sur le bouton pour obtenir
la solution. Implémenter son propre branch-and-bound pour un problème linéaire en nombres
entiers peut cependant être justifié dans certains cas : par exemple, si le problème a une
structure particulière qui n’est pas exploitée par ces solveurs, ou si le nombre de contraintes
est exponentiel comme pour le problème du voyageur de commerce, voir Chapitre 11.
Min f (x)
s.c. x ∈ X
(7.5)
gi (x) = 0 i = 1, . . . , p
gi (x) ≤ 0 i = p + 1, . . . , p + q
avec λ ∈ Λ := Rp × (R+ )q .
Si on note v la valeur optimale de (7.5), on a toujours
où
G: Λ → R ∪ {−∞}
G(λ) 7→ inf x∈X L(x, λ),
est la fonction duale. Elle est concave et affine par morceaux (car infimum de fonctions af-
fines). L’idée de la relaxation lagrangienne est d’utiliser supλ∈Λ G(λ) comme borne inférieure,
laquelle peut ensuite être utilisée au sein d’un branch-and-bound. La question est donc de
savoir calculer cette quantité. Pour cela on peut utiliser des techniques de l’optimisation
non-différentiable, une méthode de sur-gradient par exemple 1 , qui nécessite principalement
de savoir calculer un sur-gradient en tout point λ. Cette méthode est décrite à la fin de cette
section.
Rappelons qu’un sur-gradient p de G au point λ est tel que
Proposition 7.1. Si X est fini, alors (gi (x))i=1,...,p+q est un sur-gradient de G au point λ
dès que x réalise inf x∈X L(x, λ).
Pp+q
Démonstration. Soit un tel x. Pour tout µ, on a G(µ)−G(λ) ≤ L(x, µ)−L(x, λ) = i=1 gi (x)(µi −λi ).
Un des intérêts de la relaxation lagrangienne est contenu dans le théorème suivant (preuve
omise).
Théorème 7.1. Pour un programme linéaire en nombres entiers, la borne obtenue par re-
laxation lagrangienne est toujours au moins aussi bonne que celle obtenue par relaxation
linéaire.
Cela dit, il existe beaucoup de cas où ces deux bornes coı̈ncident. Cela n’empêche pas la
relaxation lagrangienne d’être intéressante (comme dans l’exemple ci-dessous), car le calcul
de supλ∈Λ G(λ) peut-être plus rapide que la résolution du programme linéaire.
1. ou alors par la méthode des faisceaux, plus efficace mais qui dépasse le cadre de ce cours, voir [5].
CHAPITRE 7. QUE FAIRE FACE À UN PROBLÈME DIFFICILE ? 94
Exemple
Un exemple très classique est celui du plus court chemin avec contrainte de temps.
Soit D = (V, A) un graphe orienté, avec deux sommets s et t. A chaque arc a est associé un
coût ca ≥ 0 et un temps ta ≥ 0. On veut trouver le s–t chemin le moins coûteux qui mette
un temps inférieur à T . Ce problème se résout bien avec un branch-and-bound, utilisant
des bornes
P fournies par la relaxation lagrangienne. X est alors l’ensembleP des s–t chemins,
f (x) = a∈A ca xa et l’on a une seule contrainte du type gi , c’est g(x) := a∈A ta xa ≤ T .
Ecrivons G(λ), défini pour λ ≥ 0.
!
X X
L(x, λ) = ca xa + λ −T + ta xa .
a∈A a∈A
Donc X
G(λ) = −T λ + min (ca + ta λ)xa .
x∈X
a∈A
Le calcul de G(λ) se fait donc par un calcul de plus court chemin où les coûts des arcs sont
non plus les ca mais les ca + λta . Ce calcul peut se faire par l’algorithme de Dijkstra
P car les
poids sont positifs ou nuls, et la solution x, injectée dans g donne la valeur −T + a∈A ta xa ,
cette dernière quantité étant alors le sur-gradient de G en λ (d’après la Proposition 7.1).
On sait donc calculer les sur-gradients de G, donc on sait maximiser G sur Λ = R+ , donc
on sait calculer de bonnes bornes inférieures pour notre problème, et on peut donc faire un
branch-and-bound.
Méthode de sur-gradient
Posons Λ = {(λ1 , . . . , λp , λp+1 , . . . , λp+q ) ∈ Rp+q : λi ≥ 0 pour i ≥ p + 1}. Soit PΛ la
projection dans Λ définie par PΛ (λ) = (λ1 , . . . , λp , λ+ +
p+1 , . . . , λp+q ), avec la notation t
+
=
max(0, t). Supposons que l’on veuille maximiser G(λ) sur Λ, avec G concave. L’algorithme
de sur-gradient consiste à construire la suite
ρk
λk+1 = PΛ λk + p ,
||pk || k
où λ0 est choisi arbitrairement dans Λ, où pk est un sur-gradient de G au point λk , et où
(ρk ) est une suite prédéterminée de réels strictement positifs telle que
+∞
X
lim ρk = 0 et ρk = +∞.
k→+∞
k=0
7.3 Métaheuristiques
Nous allons décrire quelques métaheuristiques, qui sont des méthodes générales d’explo-
ration de l’espace des solutions réalisables, qui peuvent être décrites indépendamment du
problème. Les métaheuristiques peuvent parfois donner de très bons résultats ou constituer
la seule arme pour attaquer un problème ; il est donc nécessaire de les connaı̂tre lorsqu’on
fait de la recherche opérationnelle. De plus, il est facile de contrôler leur temps d’exécution.
Cela dit, leur implémentation dépend d’un certain nombre de paramètres dont les valeurs
nécessitent beaucoup d’expérimentations. De plus, ces algorithmes n’ont généralement pas
de garantie sur la qualité de la solution trouvée.
Si {y ∈ Γ(x) : f (y) < f (x)} est non vide, choisir y ∈ Γ(x) tel que
f (y) < f (x) et poser x := y.
Méthode tabou
2. par exemple l = 7.
97 CHAPITRE 7. QUE FAIRE FACE À UN PROBLÈME DIFFICILE ?
Recuit simulé
Le recuit simulé imite la pratique du recuit en métallurgie qui consiste à alterner de
lents refroidissements et de réchauffages (recuits) pour minimiser l’énergie d’un matériau.
L’algorithme maintient une température T qui va tendre vers 0, et les transitions d’une
solution réalisable à une solution réalisable voisine auront lieu avec une probabilité dépendant
de la différence de la valeur prise par f et de la température. Plus précisément, si on a choisi
y voisin de x, la probabilité de passer effecivement de x à y ∈ Γ(x) sera, par analogie avec
la physique 3
f (y)−f (x)
min 1, e− T .
Une fois fixée au préalable la suite Tk des températures (telle que Tk → 0 quand k → ∞),
on peut écrire l’algorithme. On part d’une solution réalisable x. Ensuite, on répète
Tirer un voisin
y uniformément dans Γ(x). Faire x := y avec la pro-
f (y)−f (x)
−
babilité min 1, e Tk
. Poser k := k + 1.
Plusieurs auteurs ont donné des conditions suffisantes pour que x tende en probabilité
vers l’optimum global. Par exemple, Hajek [14] a donné une condition nécessaire et suffisante
assez légère pour cette convergence en probabilité avec Tk de la forme log κ2+k .Cette condition
met en jeu les notions d’irréductibilité et de faible réversibilité des chaı̂nes de Markov.
En pratique, on aime bien avoir Tk de la forme 4
Tk := T0 β k
ou de la forme
1
Tk :=
α + sk
avec α et s des paramètres bien choisis. La plupart du temps, ces derniers sont déterminés
expérimentalement. Comme la méthode tabou, le recuit simulé autorise des détériorations
de la qualité de la solution courante. Elle permet donc de sortir des minima locaux, si ces
derniers ne sont pas trop petits par rapport à leurs voisins, et d’explorer une plus grande
partie de l’espace des solutions.
3. Pour un système fermé, à la température T , la probabilité d’être dans un état d’énergie E est de la
E
k T
forme e ZB où Z est la fonction de partition, kB la constante de Boltzmann.
4. avec par exemple β = 0, 93.
CHAPITRE 7. QUE FAIRE FACE À UN PROBLÈME DIFFICILE ? 98
7.4 Exercices
3. Ecrire une contrainte (indicée par k et t) qui limite la production du bien k en période
t, en tenant compte du fait que si un autre bien k 0 6= k est produit, alors la production du
bien k doit être nulle.
4. Montrer que ce problème peut se modéliser comme un programme linéaire mixte en
nombres entiers (mixte signifie que toutes les variables ne sont pas contraintes à être entières).
Dans une approche par branch-and-bound, on va chercher des bornes inférieures. Une
solution est de procéder par relaxation lagrangienne.
5. Montrer qu’en relaxant les bonnes contraintes, le calcul des bornes inférieures par
la relaxation lagrangienne se ramène à des calculs de gestion de stock à un seul bien, et
expliquer comment calculer ces bornes dans le cas où les Pkt sont suffisament grands.
6. Si les Pkt ne sont pas suffisament grands, le problème à un seul bien est NP-difficile.
Proposer une solution pour le calcul de la borne inférieure par la programmation dynamique
qui garde une complexité raisonnable.
P∗
2. Soit i∗ et τ ∗ tels que mi∗ + k∈Yi∗ mk > ττ 0 =1 Mτ 0 . On dit alors que (i∗ , τ ∗ ) est une
P
bonne paire. Expliquez pourquoi toute solution réalisable du programme linéaire en nombres
entiers de 1. satisfait xi∗ ,τ ∗ = 0 lorsque (i∗ , τ ∗ ) est une bonne paire.
3. Considérons deux blocs i∗ et j ∗ et une année τ ∗ tels que k∈Yi∗ ∪Yj∗ ∪{i∗ }∪{j ∗ } mk >
P
Pτ ∗ ∗ ∗ ∗
τ 0 =1 Mτ 0 . On dit alors que (i , j , τ ) est un bon triplet. Expliquez pourquoi toute solution
réalisable du programme linéaire en nombres entiers de 1. satisfait xi∗ ,τ ∗ + xj ∗ ,τ ∗ ≤ 1 lorsque
(i∗ , j ∗ , τ ∗ ) est un bon triplet (on dira que cette contrainte est induite par le bon triplet).
4. Supposons que le solveur fonctionne par un branch-and-bound qui utilise les bornes de
la relaxation continue (ou linéaire). On fixe à 0 les variables indicées par une bonne paire.
On ajoute au programme linéaire en nombres entiers de 1. plusieurs contraintes induites par
des bons triplets. Expliquez pourquoi cela ne change pas la solution optimale du programme
linéaire en nombres entiers, et en quoi cela va améliorer les temps de calculs (au moins pour
les grandes instances).
101 CHAPITRE 7. QUE FAIRE FACE À UN PROBLÈME DIFFICILE ?
x1 = 1, 5
x2 = 4, 5
v = 24
x1 ≤ 1 x1 ≥ 2
x1 = 1 x1 = 2
x2 = 3, 5
x2 = 4, 375
v = 18, 5
v = 23, 875
x2 ≤ 4
x2 ≥ 5
on abandonne l’exploration car v est moins bon x1 = 3, 5
que le meilleur résultat entier courant.
x2 = 4
irréalisable
v = 23, 5
x1 ≤ 3
x1 ≥ 4
x1 = 3 x1 = 4
x2 = 4 x2 = 3, 875
v = 23
v = 23, 375
x2 ≤ 3 x2 ≥ 4
x1 = 7, 5
x2 = 3
v = 22, 5 irréalisable
Problématiques
103
CHAPITRE 8
Remplissage de conteneurs
Le thème de ce chapitre est le suivant : on a des objets et des conteneurs, comment remplir
au mieux ? Ecrit comme cela, le problème est assez imprécis. Nous allons nous focaliser sur
deux problèmes particuliers qui rentrent dans la catégorie des problèmes de remplissage, le
problème du sac-à-dos et celui du bin-packing. Le problème du sac-à-dos a déjà été vu au
Chapitre 3, mais allons discuter d’autres aspects de ce problème.
Le problème du sac-à-dos dans sa version la plus simple peut se décrire informellement
de la manière suivante : on a des objets de poids et de valeur variable ; on dispose d’un
seul conteneur (le sac-à-dos) qui est muni d’une contrainte de poids ; remplir le conteneur de
manière à maximiser la valeur des objets stockés.
Le problème du bin-packing dans sa version la plus simple peut se décrire informellement
de la manière suivante : on a des objets de taille variée et un seul type de conteneur ; trouver
le nombre minimum de conteneur permettant de tout stocker.
Ces problèmes ont des applications directes dans le domaine de la logistique : stocker des
produits, remplir des camions, etc.
8.1 Sac-à-dos
8.1.1 Le problème
De façon formelle, le problème du sac-à-dos s’écrit
Problème du sac-à-dos
Donnée : des entiers positifs n, w1 , . . . , wn et W , et des réels c1 , . . . , cn .
P P
Tâche : trouver un sous-ensemble S ⊆ {1, . . . , n} tel que j∈S wj ≤ W et j∈S cj est
maximum.
Nous avons déjà vu au Chapitre 3 qu’une façon commode de résoudre ce problème, si les
wi sont entiers (ce à quoi on peut toujours se ramener en changeant l’unité de mesure) et
si W n’est pas trop grand, passe par l’utilisation de la programmation dynamique, laquelle
fournit un algorithme pseudo-polynomial en O(nW ). Nous allons présenter d’autres façons
de résoudre ce problème.
Eléments de preuve. On prouve d’abord que si x est optimal avec xi < 1, xk > 0 et i < k, alors ci /wi =
ck /wk . Par conséquent, il existe une solution optimale avec un indice j̄ tel que xi = 1 pour tout i < j̄ (si
j̄ ≥ 2) et tel que xi = 0 pour tout i > j̄ (si j̄ ≤ n − 1).
On sait donc calculer une borne d’assez bonne qualité (relâché continu) en O(n log(n)).
Cette borne permet de mettre en place un branch-and-bound. Pour le branchement, c’est la
technique usuelle pour les programmes linéaires en {0, 1} : fixer certaines variables à 0 et
d’autres à 1.
8.2 Bin-packing
8.2.1 Le problème
Le problème du bin-packing traite du cas où l’on a des objets de tailles variables et un
seul type de conteneurs, et où l’on se demande comment utiliser un nombre minimum de
conteneurs pour ranger tous les objets. Dans les formes les plus générales de ce problème,
on peut aussi prendre en compte la forme des objets (on parle alors de bin-packing 2D ou
de bin-packing 3D), des incompatibilités, etc.
Ce problème peut être parfois appelé aussi cutting-stock. En effet, les problèmes de
découpes (de pièces de textile, métal, etc.), où l’on cherche à minimiser les pertes, se
modélisent de façon similaire.
Ici, on se limite au cas le plus simple, 1D. C’est un cas déjà très utile en pratique, puisqu’il
peut fournir des bornes, être utilisé en sous-routines, ou être appliqué tel quel (nombre min
de CD-rom pour stocker le contenu d’un disque dur, découper des planches de longueurs
variables dans des grandes planches de longueur fixée, découpe dans des bandes de tissu,
etc.).
Le problème s’écrit alors formellement
Problème du bin-packing
Donnée : Des entiers positifs ou nuls a1 , . . . , an , W .
Non seulement il est NP-difficile, mais il existe encore de nombreuses instances de pe-
tite taille non résolue, ce qui justifie et motive largement des travaux de recherche dans
ces domaines. Par exemple, considérons l’instance suivante, dont on ne connaı̂t pas à ce jour
la solution optimale 1 .
Le défi est de trouver une solution en moins de 51 boı̂tes, ou alors de parvenir à montrer
que 51 boı̂tes est la solution optimale. Nous allons décrire maintenant quelques heuristiques
classiques (NEXT-FIT, FIRST-FIT, FIRST-FIT DECREASING), puis nous verrons les ap-
proches branch-and-bound.
On a
SOL ≤ 2OP T − 1,
Cette équation se montre en numérotant les boı̂tes de 1 à OP T dans la solution optimale. Ensuite, on
note o(j) l’ensemble des indices i d’objet tels que l’objet i soit dans la boı̂te j. Les o(j) forment une partition
de {1, . . . , n}. On a donc
OP
XT OP
XT X Xn
W ≥ ai = ai .
j=1 j=1 i∈o(j) i=1
Le fait que OP T soit entier permet de conclure (ajout des parties entières).
On Pveut prouver que le k fournit par NEXT-FIT est tel que k ≤ 2OP T − 1. On va montrer que
n
k ≤ 2 d( i=1 ai )/W e − 1 et utiliser la borne (8.1) pour conclure.
Pour j = 1, . . . , k2 on a
X
ai > W,
i: f (i)∈{2j−1,2j}
FIRST-FIT
Je prends les objets les uns après les autres. Je mets l’objet i dans la boı̂te de plus petit
rang où il peut entrer.
De façon plus formelle,
poser i := 1. Répéter :
n P o
poser f (i) := min j ∈ N : ai + h<i: f (h)=j ah ≤ W ; poser i := i+1.
La preuve de ce résultat, difficile, est omise. Ce que ce résultat indique et qui est vérifié
en pratique, c’est que l’heuristique FIRST-FIT marche en général mieux que l’heuristique
NEXT-FIT
CHAPITRE 8. REMPLISSAGE DE CONTENEURS 110
FIRST-FIT DECREASING
Théorème 8.5. FIRST-FIT DECREASING fournit une solution SOL telle que
3
SOL ≤ OP T.
2
Tout comme pour le Théorème 8.4, la preuve de ce résultat est omise. C’est cette heuris-
tique qui a en général les meilleurs résultats. L’avantage des deux premiers algorithmes sur
ce dernier est qu’ils peuvent fonctionner on-line, ce qui signifie qu’on peut les faire tourner
lorsque les objets arrivent les uns après les autres et qu’on ne connaı̂t pas la taille des objets
futurs.
8.2.3 Branch-and-bound
Formulation PLNE
où zj = 1 si la boı̂te j est utilisée et yji = 1 si l’objet i est mis dans la boı̂te j.
Relaxation continue
C’est un programme linéaire avec un nombre linéaire de contraintes, il n’y a donc pas de
problème pour calculer la borne obtenue par relaxation continue.
111 CHAPITRE 8. REMPLISSAGE DE CONTENEURS
Relaxation lagrangienne
PK
On peut faire de la relaxation lagrangienne en “oubliant” les contraintes j=1 yji = 1.
On écrit le lagrangien
K
X n
X XK
L(y, z, λ) := zj + λi ( yji − 1).
j=1 i=1 j=1
où
G: Λ → R ∪ {−∞}
G(λ) 7→ inf x∈X L(x, λ),
se réécrit
n
X K
X
G(λ) := λi + Sj
i=1 j=1
On sait donc calculer G(λ) (assez) facilement et trouver les y, z le réalisant. Et par
conséquent, on sait calculer les sur-gradients de la fonction concave G(λ), et donc la maxi-
miser.
CHAPITRE 8. REMPLISSAGE DE CONTENEURS 112
8.3 Exercices
8.3.1 Inégalités valides pour le sac-à-dos
On considère un problème de sac-à-dos avec a1 , . . . , an , b des réels positifs. On note S
l’ensemble des solutions réalisables
( n
)
X
n
S := x ∈ {0, 1} : ai x i ≤ b .
i=1
P
On appelle ensemble dépendant tout ensemble C ⊆ {1, . . . , n} tel que i∈C ai > b.
1. Montrer que tout x ∈ S satisfait l’inégalité
X
xi ≤ |C| − 1,
i∈E(C)
Positionnement d’entrepôts
9.1 Formalisation
La version la plus simple du problème de positionnement d’entrepôts est la suivante.
Problème du positionnement d’entrepôts
Donnée : Un ensemble fini de clients D, un ensemble fini d’entrepôts potentiels F, un coût
fixe fi ∈ R+ d’ouverture pour chaque entrepôt i ∈ F et un coût de service cij ∈ R+ pour
chaque i ∈ F et j ∈ D.
Tâche : Trouver un sous-ensemble X ⊆ F (dits entrepôts ouverts) et une affectation σ :
D → X des clients aux entrepôts ouverts, de façon à ce que la quantité
X X
fi + cσ(j)j
i∈X j∈D
soit minimale.
Un exemple d’input et d’output pour ce problème est donné Figures 9.1 et 9.2.
On dit qu’on est dans le le cas métrique si
cij + ci0 j + ci0 j 0 ≥ cij 0 pour tout i, i0 ∈ F et j, j 0 ∈ D.
C’est en particulier le cas lorsque les coûts de services cij sont proportionnels à la distance
géométrique. Cette inégalité contient plus de termes que l’inégalité triangulaire classique, à
laquelle elle ressemble. C’est dû au fait que les coûts ne sont pas nécessairement définis entre
entrepôts ou entre clients.
Commençons par la question de la complexité.
Proposition 9.1. Le problème du positionnement d’entrepôts est NP-difficile, même dans
le cas métrique.
Nous allons un peu discuter des formulations sous forme de programmes linéaires en
nombres entiers et parler rapidement de recherche locale.
CHAPITRE 9. POSITIONNEMENT D’ENTREPÔTS 116
Client
9.2 Branch-and-bound
P P P
Min i∈F fi yi + i∈F j∈D cij xij
Pij ≤ yi
s.c. x i ∈ F, j ∈ D (1)
i∈F xij = 1 j∈D (2)
xij ∈ {0, 1} i ∈ F, j ∈ D (3)
yi ∈ {0, 1} i ∈ F. (4)
On écrit le lagrangien
!
X XX X X
L(x, y, λ) = fi y i + cij xij + λj 1− xij .
i∈F i∈F j∈D j∈D i∈F
c’est-à-dire, en posant
max G(λ)
λ∈RF
Il est facile de résoudre le programme : G(λ) := minx∈{0,1}F ×D ,y∈{0,1}F : xij ≤yi L(x, y, λ).
En effet on peut écrire X X
G(λ) = λj + di (λ)
j∈D i∈F
avec X
di (λ) = min fi y i + (cij − λj )xij .
xi · ∈{0,1}D ,yi ∈{0,1},xij ≤yi
j∈D
Dans le cas du problème de positionnement d’entrepôts, on a réalisé dans les années 2000
que la recherche locale était extrêmement efficace (plus que pour les autres problèmes de
RO).
On a par exemple le théorème suivant [2]
Théorème 9.1. On se place dans le cas métrique. Si X est un minimum local pour le
voisinage défini précédemment, alors X vaut au plus 3 fois l’optimum.
En revanche, on n’a pas a priori d’évaluation du temps de calcul d’un optimum local.
9.4 Exercices
soit minimale.
pour tout triplet (i, j, k). On posera cii = 0 pour tout i. Noter que le contenu d’un entrepôt
fermé peut très bien être réparti entre plusieurs entrepôts restés ouverts.
1. Ecrire sous forme d’un programme linaire en variables mixtes (entières et continues)
le problème consistant à choisir les k entrepôts à fermer et le plan de transfert des pièces de
rechange des entrepôts fermés vers ceux restés ouverts, tout en minimisant le coût total du
transfert. Justifier en particulier les contraintes utilisées.
Il est maintenant demandé d’admettre que l’on peut assez facilement montrer que ce
problème est NP-difficile (il contient le problème du dominant d’un graphe).
4. Y a-t-il des logiciels libres permettant de résoudre un tel problème avec cette méthode ?
Si oui, en citer un.
On souhaite maintenant proposer une méthode du type “recherche locale” pour ce problème.
6. Expliquer pourquoi une recherche locale pour ce problème peut limiter le codage des
solutions au choix des k entrepôts fermés, sans précision sur les transferts. Donner le nom
d’un problème traditionnel de recherche opérationnelle dont la résolution rapide permet un
tel codage.
Min h
X
s.c. ys ≤ K (i)
s∈S
X
xs,c ≤ |C|ys s∈S (ii)
c∈C
X
xs,c = 1 c∈C (iii)
s∈S
ys ∈ {0, 1} s ∈ S (vi)
h ∈ R+ (vii)
Un tel programme linéaire se résout par branch-and-bound. La borne dont on se sert alors
peut être celle obtenue en relâchant les contraintes d’intégrité de x et de y. On se propose
de voir si l’on peut également obtenir des bornes par relaxation lagrangienne.
3. Ecrire le programme d’optimisation obtenu lorsqu’on procède à la relaxation lagran-
gienne de la contrainte (ii).
123 CHAPITRE 9. POSITIONNEMENT D’ENTREPÔTS
Ordonnancement industriel
10.1 Préliminaires
De manière un peu générique, un problème d’ordonnancement se formule avec des tâches,
qui elles-mêmes se découpent éventuellement en opérations. Etant données des contraintes,
on appellera ordonnancement la donnée des instants auxquels commencent les différentes
tâches ou opérations.
Les contraintes de temps peuvent être de deux natures :
— Durées des tâches
— Précédences
Les contraintes de ressource peuvent également être de deux natures :
— Disjonctive : si les tâches i et j sont effectuées sur la machine k, elles doivent être
faites dans tel ordre
— Cumulative : la tâche i consomme aik de la ressource k. La ressource k a une capacité
Ak . A tout instant, la somme des consommations sur la machine k doit être inférieure
à sa capacité.
Les critères à optimiser peuvent être variés. Exemples :
— Coût : Coût total de l’ordonnancement. Cela suppose défini le coût d’affectation d’une
tâche i sur une machine k.
— Makespan : Temps pour effectuer l’ensemble des tâches.
— Temps moyen : Temps moyen mis par une tâche pour être traitée. Son intérêt peut
être varié. Par exemple si le problème d’ordonnancement s’insère dans un processus
plus grand, ce genre de critère peut être intéressant.
CHAPITRE 10. ORDONNANCEMENT INDUSTRIEL 126
Figure 10.1 – Le diagramme de Gantt qui correspond à l’exemple de la section qui suit.
Fin. De plus, chaque arc (u, v) est muni d’une longueur égale à la durée minimale séparant
le début de u de celui de v.
La première remarque que l’on peut faire est la suivante
Si ce projet a un sens, le graphe est acircuitique.
En effet, un circuit traduirait l’obligation de remonter dans le temps.
Considérons l’exemple suivant.
30
Notons tI et t0I les instants au plus tôt et au plus tard auxquels commencer la tâche I.
Proposition 10.1. tI est la longueur du plus long chemin de Début à I. t0I , c’est tFin moins
la longueur du plus long chemin de I à Fin.
Démonstration. En effet,
— pour chaque tâche I, on ne peut pas commencer avant la somme des longueurs des arcs du plus long
chemin de Début à I.
CHAPITRE 10. ORDONNANCEMENT INDUSTRIEL 128
— on faisant débuter chaque tâche I précisément à la somme des longueurs des arcs du plus long chemin
de Début à I, on peut commencer chaque tâche à l’instant tI .
De même pour t0I .
Pour trouver la durée minimale du projet, les tâches critiques, etc. il faut donc savoir
calculer les plus longs chemins dans un graphe acircuitique D = (V, A), muni d’une longueur
l : A → R+ . Cela se fait par la programmation dynamique, comme nous l’avons vu au
Chapitre 3. Si on note ηI la longueur du plus long chemin de Début à I, on peut écrire
(équation de Bellman)
ηI = max (ηJ + l(J, I)).
(J,I)∈A
On peut calculer tous les ηI en O(m) où m est le nombre d’arcs. On peut calculer de
même les πI , plus longs chemins de I à Fin. On pose alors tI := ηI , t0I := tFin − πI et la
marge mI := t0I − tI . Les chemins critiques sont les plus longs chemins de Début à Fin ;
toutes les tâches d’un chemin critique sont caractérisées par une marge nulle.
10.3.1 Introduction
Un problème d’ordonnancement d’atelier se décrit sous la forme d’un ensemble de tâches
J1 , . . . , Jn et d’un ensemble de machines M1 , . . . , Mm . Une tâche j, pour être réalisée,
nécessite son exécution sur différentes machines successivement. Le temps d’exécution de
la tâche j sur la machine k est une donnée du problème et se note pjk . L’exécution d’une
tâche j sur une machine k s’appelle une opération, on parle également de passage de la tâche
j sur la machine k.
Remarque
Le flow-shop est un cas particulier du job-shop.
Trouver l’ordonnancement, c’est fixer les instants tjk de début du passage de toute tâche
j sur toute machine k. On note Cj l’instant d’achèvement de la tâche j.
Comme indiqué au début de ce chapitre, deux objectifs classiques sont
P
— minimiser “la durée moyenne”, lequel s’écrit donc j Cj , et
— minimiser le makespan, lequel s’écrit Cmax = maxj Cj .
L’essentiel du cours se focalisera sur la minimisation du makespan. L’objectif de minimisation
des coûts n’est pas abordé dans ce cours.
10.3.2 Difficulté
Les problèmes d’ordonnancement sont difficiles, dans tous les sens du terme.
54 83 15 71 77 36 53 38 27 87 76 91 14 29 12 77 32 87 68 94
79 3 11 99 56 70 99 60 5 56 3 61 73 75 47 14 21 86 5 77
16 89 49 15 89 45 60 23 57 64 7 1 63 41 63 47 26 75 77 40
66 58 31 68 78 91 13 59 49 85 85 9 39 41 56 40 54 77 51 31
58 56 20 85 53 35 53 41 69 13 86 72 8 49 47 87 58 18 68 28
1. Faire deux paquets : un paquet A avec les j tels que pj1 ≤ pj2 , un paquet B avec les
j tels que pj1 > pj2 . Ordonner A selon les pj1 croissants, B selon les pj2 décroissants.
Concaténer la suite des j de A à celle de B dans cet ordre.
2. Choisir la tâche Jj ayant le plus petit pj1 ou pj2 parmi tous les pji .
Appliquer récursivement l’algorithme sur les tâches 6= j : cela donne une séquence
j1 , j2 , . . . , jr , js0 , . . . , j10 , avec r + s = n − 1.
Les tâches j1 , . . . , jr sont choisies de façon à ce que le temps sur la machine 1 soit plus
court que sur la machine 2. Les tâches js0 , . . . , j10 sont choisies de façon à ce que le temps
sur la machine 2 soit strictement plus court que sur la machine 1.
Si pj1 ≤ pj2 , retourner j, j1 , j2 , . . . , jr , js0 , . . . , j10 .
Si pj1 > pj2 , retourner j1 , j2 , . . . , jr , js0 , . . . , j10 , j.
Considérons l’exemple suivant.
...,A
E, . . . , A
E, D, . . . , A
E, D, . . . , B, A
E, D, C, B, A.
Théorème 10.2. L’algorithme de Johnson résout correctement le problème du flow-shop à
deux machines et minimisation du makespan Cmax .
Démonstration. Déroulons maintenant l’algorithme et plaçons nous à l’itération j. On peut supposer sans
perte de généralité que qj est atteint sur la première machine. j − 1 tâches ont déjà été fixées : pour
fixer les notations, supposons que les tâches fixées sont celles d’indices j1 , . . . , jr et j10 , . . . , js0 . On suppose
donc que j = r + s + 1. On peut mettre les autres dans un ordre quelconque, pas forcément le même
sur la première et la seconde machine. On suppose que l’on a les instants de démarrage de chacune des
opérations et que cet ordonnancement est réalisable. On a donc un ordre de tâches sur la première machine
(1) (1) (2) (2)
j1 , . . . , jr , i1 , . . . , in−r−s , js0 , . . . , j10 et sur la seconde j1 , . . . , jr , i1 , . . . , in−r−s , js0 , . . . , j10 .
(1)
On fait maintenant commencer j sur la machine 1 à l’instant auquel commençait i1 , et sur la machine 2
(2)
à l’instant auquel commençait i1 . On décale vers la droite les tâches qui était à gauche de j sur la machine
1 et sur la machine 2 en conséquence. Cette opération est illustrée sur le Figure 10.3.
CHAPITRE 10. ORDONNANCEMENT INDUSTRIEL 132
i j20
j1 j2 j3 ` j10
M1
M2
j1 j2 j3 i0
`0 j20 j10
j1 j2 j3 i ` j20 j10
M1
M2
j1 j2 j3
i0 `0 j20 j10
Figure 10.3 – Illustration d’une itération de l’algorithme de Johnson : changer la position relative de la
tâche en pointillés par rapport à i et ` ne détériore pas la durée de l’ordonnancement
Montrons que ce nouvel ordonnancement est encore réalisable et garde le même makespan. Une fois
l’itération j finie, les tâches décalées ont vu leur temps de démarrage augmenter de pj1 sur la machine 1, et
de pj2 sur la machine 2. Comme pj1 < pj2 , on reste réalisable, en tout cas pour les tâches différentes de j.
Il faut encore vérifier que la tâche j démarre sur la machine 2 lorsqu’elle a été terminée sur la machine 1.
(2)
Mais c’est évident car j commence sur la machine 1 au plus tard à l’instant auquel commençait i1 sur la
machine 1 et pi(2) 1 ≥ pj1 .
1
Ce chemin se déplace soit de gauche à droite, soit de haut en bas, soir vers le nord-est. On
cherche donc le plus court chemin : c’est un problème de plus court chemin dans un graphe
acircuitique – le poids d’un arc étant la durée correspondant à la transition représentée par
l’arc – qui conduit à un algorithme en O(m2 log(m)) (le plus court chemin lui-même met
O(m2 ), mais la construction du graphe est un peu plus coûteuse).
En toute rigueur, le nombre de chemins respectant ce genre de déplacement est infinis :
si la tâche 1 met en jeu la machine 1 sur une certaine plage de temps, et si la tâche 2 peut
pendant ce temps passer sur la machine 2, avec un temps de passage beaucoup plus court,
on peut faire débuter à un grand nombre de moment sur la plage horaire l’opération sur
la machine 2. La démonstration du Théorème 10.4 ci-dessous, omise ici, consiste dans un
premier temps à montrer qu’en se limitant à un nombre fini de mouvements possibles (voir
Figure 10.5), on ne diminue pas la longueur du plus court chemin.
D’après cette discussion, on a
Théorème 10.4. L’algorithme de Brucker résout correctement le problème du job-shop à
deux tâches et minimisation du makespan.
L’algorithme est illustré sur les Figures 10.4 et 10.5.
Remarque
Cet algorithme peut se généraliser au problème à n tâches, mais la complexité devient
alors O(nmn log(m)), ce qui n’est pas polynomial...
CHAPITRE 10. ORDONNANCEMENT INDUSTRIEL 134
tâche 1: M1 → M2 → M3 → M4
tâche 2: M2 → M4 → M3 → M1
tâche 2
q24
M1
q23
M3
M4 q22
M2 q21
q14 tâche 1
q11 q12 q13
M4
M1 M2 M3
un ordonnancement possible
Figure 10.4 – Illustration de l’algorithme de Brucker qui résout le job-shop à deux tâches et minimisation
du makespan.
tâche 2
q24
M1
M4 q22
M2 q21
q14 tâche 1
q11 q12 q13
M4
M1 M2 M3
un ordonnancement possible
On a n tâches et deux machines. Chaque tâche est constituée de deux opérations, iden-
tifiées avec les machines. Comme on est en open-shop, il n’y a pas de contrainte sur l’ordre
dans lequel doivent être faites les opérations d’une tâche. On a alors le résultat suivant.
Démonstration. Il est clair que l’on ne peut pas faire mieux que la valeur
Pn T ci-dessus.
Pn Montrons qu’on peut
l’atteindre. Quitte à ajouter des tâches fictives, on peut supposer que j=1 pj1 = j=1 pj2 = T .
On peut définir j1 le plus grand indice j tel que
(p(j1 +1)1 + p(j1 +1)2 ) + (p(j1 +2)1 + p(j1 +2)2 ) + . . . + (pj1 + pj2 ) ≤ T.
Pj2 Pj2
On considère que cela donne une seule grande tâche J2∗ , avec p∗21 := j=j 1 +1
pj1 et p∗22 := j=j 1 +1
pj2 .
∗ ∗
Pn Enfin, on définit
∗
de
Pnmême j3 . On considère que cela donne une seule grande tâche J3 , avec p31 :=
j=j2 +1 pj1 et p32 := j=j2 +1 pj2 .
Après avoir défini J3∗ , toutes
Pn les tâches
∗
Pn sont soit dans J1 ,Psoit dans J2∗ , soit ∗ ∗ ∗
Pn dans J3 . En effet, p11 + p12 +
n
p(j1 +1)1 + p(j1 +1)2 > T et j=1 pj1 + j=1 pj2 = 2T , donc j=j1 +2 pj1 + j=j1 +2 pj2 < T .
On se retrouve donc avec l’open shop à trois tâches J1∗ , J2∗ , J3∗ , avec p∗11 +p∗21 +p∗31 = T et p∗12 +p∗22 +p∗32 =
T , et p∗j1 + p∗j2 ≤ T pour tout j = 1, 2, 3.
En renumérotant, on peut supposer que p∗11 ≥ p∗22 et p∗12 ≥ p∗31 . On vérifie ensuite que l’on peut
effectuer J1∗ , J2∗ , J3∗ sur la machine 1 dans cet ordre, et J2∗ , J3∗ , J1∗ sur la machine 2 dans cet ordre. C’est un
ordonnancement de durée T . Pour chaque Js∗ , on effectue les Jj dont il est composé, consécutivement selon
les indices.
Open-shop préemptif
On a n tâches et m machines, chaque tâche j est décrite par un vecteur pj = (pj1 , . . . , pjm ),
le nombre pjk indiquant le temps que la tâche j doit passer sur la machine k. Chaque
tâche peut passer dans un ordre quelconque sur les machines (open-shop). De plus, chaque
opération (passage sur une machine) peut être interrompue et reprise plus tard, et ce, autant
de fois que nécessaire (cas préemptif). L’important est qu’au total, chaque tâche j ait passé
un temps pjk sur la machine k, et ce pour tout k ∈ {1, . . . , m}.
On a le résultat suivant.
CHAPITRE 10. ORDONNANCEMENT INDUSTRIEL 136
Théorème 10.7 (Théorème Pde Birkhoff-von Neumann). PSoit A = ((aij )) une matrice carrée
bistochastique (ie aij ≥ 0 et i=1 aij = 1 pour tout j et nj=1 aij = 1 pour tout i).
n
..
. P
A := .
..
PT .
C’est une matrice (n + m) × (n + m). Quitte à ajouter des quantités positives sur la diagonale de A, on peut
supposer que A a toutes ses sommes par ligne et par colonne égale à
m n
!
X X
T := max max pjk , max pjk .
j k
k=1 j=1
P
On applique Birkhoff-von Neumann à A. On obtient que P peut s’écrire comme T P i λi Qi où les Qi
sont des matrices ayant au plus un 1 par ligne et par colonne, et où λi > 0 pour tout i et i λi = 1.
Cela donne un ordonnancement : sur les λ1 T premiers instants, on fait passer la tâche j sur la machine
k, pour tout (j, k) entrée non nulle de la matrice Q1 ; on fait passer la tâche j sur la machine k, pour tout
(j, k) entrée non nulle de la matrice Q2 , etc.
Graphe disjonctif
Un outil particulièrement commode pour les cas difficiles, et qui peut servir tant pour les
algorithmes de recherche locale que les méthodes exactes du type branch-and-bound est le
graphe disjonctif.
Le graphe disjonctif est un graphe mixte (à la fois des arcs et des arêtes) dont les sommets
sont les opérations, les arcs les relations conjonctives (un arc est mis entre deux opérations
consécutives d’une même tâche), les arêtes les relations disjonctives (une arête est mise entre
toute paire d’opérations utilisant la même machine). La longueur d’un arc est la durée de
l’opération dont il est issu.
Considérons par exemple le job-shop suivant, à trois tâches, et trois machines.
J1 M1 : 2 M2 : 5 M3 : 4
J2 M2 : 1 M1 : 6 M3 : 7
J3 M3 : 6 M2 : 8 M1 : 3
Le graphe disjonctif correspondant est donné sur la Figure 10.6.
: arc conjonctif
: arête disjonctive
2
5
J1
Début Fin
1 6 7
J2
3
J3
6 8
En mettant sur chaque arc obtenu par orientation d’une arête la durée de l’opération dont
elle est issue, il est facile de calculer le makespan, c’est-à-dire la durée totale de l’ordonnan-
cement. On se retrouve en effet dans la même situation que dans la méthode potentiel-tâche
(Section 10.2) où les durées et les précédences sont entièrement fixées.
Branch-and-bound
On définit alors comme dans la Section 10.2, pour toute opération O, la quantité ηO qui
est la longueur du plus long chemin de Début à O, et de même πO (en ne gardant que les
arcs). Les calculs sont décrits Section 10.2.
P
On définit η(O) := minO∈O ηO , π(O) := minO∈O πO et p(O) := O∈O p(O).
Cela permet de définir un schéma de branch-and-bound. On a en effet alors la borne
suivante sur la durée des ordonnancements :
max max η(O) + π(O) + p(O) ,
k=1,...,m O⊆Ok
où Ok est l’ensemble des opérations devant être effectuées sur la machine k. Carlier a montré
qu’elle se calculait en temps polynomial. Le branchement le plus naturel consiste à fixer
progressivement les arcs depuis l’origine Début.
Recherche locale
Pour faire de la recherche locale (recuit simulé, tabou, etc.), il faut définir une notion de
voisinage sur les ordonnancements réalisables, ces derniers étant identifiés avec les orienta-
tions acicuitique du graphe disjonctif. Par exemple, on peut dire que deux ordonnancements
réalisables sont voisins si on passe de l’un à l’autre par
— retournement d’arc
— retournement des arcs disjonctifs d’un chemin critique.
10.4 Exercices
10.4.4 Retour sur le problème de l’affectation de tâche (cours sur les flots)
On revient sur l’exercice d’affectation des tâches, mais cette fois on ne suppose plus que
les employés puissent travailler en parallèle.
On suppose que l’on a différentes tâches à accomplir dont on connaı̂t les durées d’exécution,
et que l’on dispose d’une ressource de main d’œuvre dont on connaı̂t les compétences. A un
instant donné, un employé ne peut se consacrer qu’à une seule tâche à la fois. Enfin, on se
met dans un cadre préemptif, c’est-à-dire qu’un employé peut interrompre son travail sur
une tâche, et le reprendre plus tard.
On veut trouver un ordonnancement, c’est-à-dire à tout instant la donnée pour chaque
employé i de la tâche j sur lequel il travaille. On souhaite minimiser le temps nécessaire pour
réaliser l’ensemble des tâches (makespan).
M1 M2
J1 6 → 3
J2 5 → 4
J3 7 ∅
J4 ∅ 3
J5 2 ← 6
J6 4 ← 3
Proposer un ordonnancement optimal.
M1 M2
J1 7 0
J2 3 7
J3 9 14
J4 7 3
J5 7 3
J6 7 0
Proposer un ordonnancement optimal.
pour se rendre d’un entrepôt à l’autre. A quelle heure peut-on avoir fini au plus tôt ? Justifier
votre réponse.
Tournées
Les problèmes de tournées sont parmi les plus naturels en Recherche Opérationnelle et
en Logistique. Le thème général est le suivant : un réseau étant donné, il s’agit de le visiter
entièrement en minimisant le coût. Les variations sont alors infinies et peuvent concerner la
nature du réseau, la notion de visite, la définition du coût. Des contraintes peuvent également
être ajoutées à l’envie : fenêtre de temps, retour au point de départ, etc.
Dans cette séance, nous nous intéresserons aux deux problèmes les plus simples à formu-
ler dans cette famille, tous deux d’un grand intérêt pratique : le problème du voyageur de
commerce et le problème du postier. De plus, nous verrons qu’ils illustrent les deux aspects de
la recherche opérationnelle car, bien que très semblables dans leur formulation, ils diffèrent
radicalement quant à leur résolution puisque l’un d’eux peut être résolu en temps polynomial
par un algorithme simple à implémenter, et l’autre au contraire est NP-difficile et nécessite
pour être résolu un mélange de techniques avancées et d’heuristiques.
Rappelons que c’est un problème difficile, comme il a été déjà signalé au Chapitre 2.
2 a
2
a 4 2
b
c
1 2
d 2
4
1 2
3
3
e
e c
1 3
1
2
a
2
b d
2 b
4
2 2
2
3
3 a 4
e
c c
1 3 1
d 2
1
2
1
d
e
Figure 11.1 – Le problème du voyageur de commerce peut se reformuler comme un problème de cycle
hamiltonien dans un graphe complet.
Il faut donc mettre en œuvre des stratégies de résolutions plus intelligentes, et donc
se tourner vers les techniques de la recherche opérationnelle. Nous allons présenter trois ap-
proches : heuristique, branch-and-bound, recherche locale. Les grands progrès de ces dernières
années dans la résolution du problème du voyageur de commerce résident principalement dans
les techniques de branch-and-bound, et plus précisément dans le calcul des bornes. On sait
de nos jours résoudre des instances à 1000 000 villes, alors qu’il y a une vingtaine d’années,
on ne dépassait pas quelques centaines de villes (la puissance de calcul joue un rôle très
secondaire dans ces performances – voir la discussion sur la complexité du Chapitre 2).
Les approches que nous allons décrire s’énoncent plus facilement sous la reformulation
suivante sur le graphe complet Kn . Elle s’obtient en prenant le même ensemble de sommets
et en mettant comme coût c(xy) le coût du plus court chemin dans G de x à y. En effet,
prenons une chaı̂ne fermée de G passant par tous les sommets. La succession des premiers
passages en chaque sommet plus le sommet de départ induit un cycle hamiltonien de coût
inférieur dans Kn . Réciproquement, un cycle hamiltonien de coût minimum dans Kn induit
une chaı̂ne fermée de même coût dans G. Cela permet de conclure que le cycle hamiltonien
de plus petit coût dans Kn induit une tournée de coût minimum dans G.
Voir l’illustration de cette reformulation sur la Figure 11.1.
145 CHAPITRE 11. TOURNÉES
Heuristique de Christofidès
La plus célèbre heuristique du voyageur de commerce dans le cas non-orienté est l’heuristique
de Christofidès qui fournit une 3/2-approximation, c’est-à-dire une solution dont la valeur
est au plus 1,5 fois la valeur optimale.
L’algorithme est très simple (voir l’illustration Figure 11.2).
Cet algorithme utilise deux routines : celle de l’arbre couvrant de poids minimum, qui est
décrite au chapitre sur la conception de réseau (Chapitre 12) ; et celle du couplage parfait
de poids minimum, non décrit dans ce cours. Il suffit de savoir qu’un couplage parfait est un
couplage qui couvre tous les sommets d’un graphe. Si le graphe est pondéré, et s’il existe
un tel couplage, on sait trouver un couplage parfait de poids minimum avec un algorithme
d’Edmonds.
Théorème 11.2. L’algorithme polynomial décrit ci-dessus fournit une 3/2-approximation
au problème du voyageur de commerce.
Démonstration. Soit H le cycle hamiltonien obtenu à la fin. Il faut prouver que l’on obtient bien
X 3
ce ≤ OP T.
2
e∈H
7 7
2
3 4
5
6
4
1
1 5
7
7 2
2
3 3
6
6
4
4
5
5
j1
M H
j3
j6
M
j5
j4
Recherche locale
Proposition 11.1. Les vecteurs d’incidences des cycles hamiltoniens sont exactement les
vecteurs entiers du système
0P≤ xe ≤ 1 e∈E
x =2 v∈V
Pe∈δ(v) e
e∈δ(X) xe ≥ 2 X ⊆ V, X 6= ∅, V.
Démonstration. Soit x le vecteur d’incidence d’un cycle hamiltonien. Il est clair que ce vecteur satisfait les
contraintes ci-dessus. Réciproquement, soit x un vecteur satisfaisant les contraintes ci-dessus. Comme
0P≤ xe ≤ 1 e∈E
e∈δ(v) xe = 2 v ∈ V,
les arêtes e telles que xe = 1 forment une collection disjointe de cycles élémentaires couvrant tous les sommets
du graphe. Il P suffit donc de montrer qu’il n’y a qu’un seul cycle dans la collection. C’est une conséquence
des inégalités e∈δ(X) xe ≥ 2 pour tout X ⊆ V, X 6= ∅, V . En effet, s’il y a un cycle qui ne couvre pas tous
les sommets, en posant X l’ensemble des sommets couverts par ce cycle, on obtient une contradiction.
Branch-and-cut
On peut essayer d’en tirer une borne pour construire une méthode de branch-and-bound.
Le problème, c’est que les contraintes sont en nombre exponentiel. On peut en prendre moins
de contraintes, de manière à obtenir des bornes calculables en temps raisonnable, mais la
qualité des bornes est moindre.
P
Min e∈E c(e)xe
0P≤ xe ≤ 1 e∈E
(11.2)
x = 2 v∈V
Pe∈δ(v) e
e∈δ(X) xe ≥ 2 pour certains X ⊆ V, X 6= ∅, V.
149 CHAPITRE 11. TOURNÉES
Dans les branch-and-bound, la qualité de la borne est cruciale. Une technique efficace,
appelée branch-and-cut, permet d’améliorer la qualité de la borne. Elle consiste à suivre le
schéma d’un branch-and-bound en agrandissant le programme linéaire qui fournit les bornes
au fur et à mesure de l’exploration de l’arbre de branchement.
On résout le programme (11.2). Supposons que l’on ait une solution x∗ du programme
linéaire. Il y a 3 possibilités
1. x∗ est le vecteur d’incidence d’un cycle hamiltonien. On a trouvé une solution
optimale pour le nœud courant de l’arbre de branchement.
P
2. On trouve une inégalité du type e∈δ(X) xe ≥ 2 qui soit violée. Cela se fait
en temps polynomial : c’est un problème de coupe minimum (voir le Chapitre 5). On
ajoute la contrainte violée au programme linéaire, et on résout le nouveau programme
linéaire.
3. On ne trouve aucune inégalité de ce type qui soit violée, mais x∗ n’est pas
entier. On a une borne pour le nœud de l’arbre de branchement. Il faut brancher sur
ce nœud et recommencer pour les fils.
Relaxation lagrangienne
Nous avons vu que dans certains cas, la relaxation lagrangienne pouvait fournir de
bonnes bornes, si une partie des contraintes est facile .
C’est le cas ici (Held et Karp 1970). On peut réécrire le système linéaire (11.1)
0 ≤ xe ≤ 1 e∈E
Pe ∈ Z
x e∈E
x =2 v∈V
Pe∈δ(v) e
e∈E[X] xe ≤ |X| − 1 X ⊆ V, X 6= ∅, V.
où E[X] désigne l’ensemble des arêtes induites par X, i.e. l’ensemble des arêtes ayant leurs
deux extrémités
P dans X. P P P P
En effet 2 e∈E[X] xe + e∈δ(X) xe = v∈X e∈δ(v) xe . Donc, si e∈δ(v) xe = 2 pour tout
P P
v ∈ V , on a 2 e∈E[X] xe + e∈δ(X) xe = 2|X|, d’où l’équivalence des deux formulations. En
faisant jouer un rôle particulier au sommet 1, on peut réécrire le système sous la forme
0 ≤ xe ≤ 1 e∈E
Pe ∈ Z
x e∈E
x = 2
Pe∈δ(1) e
x ≤ |X| − 1 X ⊆ {2, . . . , n}, X 6= ∅
Pe∈E[X] e
Pe∈E xe = n
e∈δ(v) xe = 2 v ∈ {2, . . . , n}.
P
En oubliant les contraintes e∈δ(v) xe = 2 pour v ∈ {2, . . . , n}, on obtient un système
linéaire qui décrit les 1-arbres. Un 1-arbre est un arbre couvrant {2, . . . , n}, avec deux arêtes
CHAPITRE 11. TOURNÉES 150
supplémentaires quittant 1 (voir la Figure 11.5) et se calcule en temps linéaire (la routine de
calcul des arbres couvrants de poids minimum est décrite au Chapitre 12).
On a tout ce qu’il faut pour calculer une borne par relaxation lagrangienne. Le lagrangien
est
X n
X X
L(x, λ) := ce x e + λi xe − 2 .
e∈E i=2 e∈δ(i)
max G(λ)
λ∈Rn−1
où X
G(λ) := −2 λi + min L(x, λ)
x vecteur d’incidence d’un 1-arbre
i∈V
On sait calculer G(λ) en temps polynomial, pour tout λ, cela suffit (voir Chapitre 7) pour
pouvoir calculer maxλ∈Rn−1 G(λ) par une méthode de sur-gradient.
Cette borne est très bonne.
Théorème 11.3 (Held Karp 1970). maxλ∈Rn−1 G(λ) est égal à la solution de la relaxation
linéaire (11.1).
Branchement
En général, dans un branch-and-bound ou dans un branch-and-cut, le problème résolu
en un nœud de l’arbre est de même nature qu’à la racine de l’arbre, laquelle consiste en
la résolution du relâché continu du problème de départ. Dans le cas du voyageur de com-
merce, ce n’est pas le cas. En un nœud de l’arbre de branchement, on doit résoudre des
tournées contraintes à passer par certaines arêtes ou à en éviter d’autres, ce qui est a priori
un problème plus général que le problème de départ. Nous expliquons maintenant une façon
classique de traiter cette difficulté.
La façon classique de brancher pour le voyageur de commerce est de choisir une arête e,
et d’écrire l’ensemble des solution X = Xe ∪ (X \ Xe ) où Xe est l’ensemble des solutions
empruntant l’arête e. Par conséquent, tout noeud de l’arbre de branch-and-bound est de la
forme
SA,B = {S ∈ S : A ⊆ S, B ∩ S = ∅} avec A, B ⊆ E.
Résoudre le problème au niveau du noeud SA,B consiste donc à chercher le cycle hamiltonien
de plus petit coût empruntant toutes les arêtes de A, et aucune de B. Il reste à décrire la
151 CHAPITRE 11. TOURNÉES
façon de calculer des bornes lorsqu’on branche. On pourrait se dire qu’il suffit de calculer des
1-arbres avec des arêtes prescrites (celles de A) et des arêtes interdites (celles de B), mais il
n’y a pas d’algorithme simple qui effectue cette tâche. Une petite astuce permet de pallier
cette difficulté.
On niveau d’un nœud de l’arbre de branchement, on a donc un problème de voyageur de
commerce avec contraintes (ensemble d’arêtes prescrites et interdites). Une petite astuce per-
met d’écrire ce problème de voyageur de commerce avec contraintes , comme un problème
de voyageur de commerce sans contrainte, simplement en modifiant la fonction de coût.
Si on pose
c(e) si e ∈ A
0
c (e) := c(e) + C si e ∈ / A∪B
c(e) + 2C si e ∈ B,
P
où C := e∈E c(e) + 1, on a la propriété, qui peut se démontrer assez aisément,
Les cycles hamiltoniens de SA,B sont exactement ceux dont le nouveau coût est ≤ (n +
1 − |A|)C. De plus, les cycles hamiltoniens dans SA,B ont un coût qui diffère de l’ancien coût
d’exactement (n − |A|)C.
On peut donc calculer des bornes pour un problème de voyageur de commerce non
contraint, avec la nouvelle fonction de coût, pour obtenir des bornes inférieures pour le
problème avec contraintes.
De même que dans le cas non-orienté, on peut reformuler la problème sur le graphe
complet orienté (toute paire de sommets est reliée par deux arcs de sens opposé).
Théorème 11.4. Le problème du voyageur de commerce dans sa version orientée est NP-
difficile.
Cela peut se retrouver à partir du Théorème 11.1. En effet, en prenant un graphe non-
orienté, on peut dédoubler les arêtes pour en faire deux arcs parallèles mais de sens opposés.
On se ramène alors au problème du voyageur de commerce sur un graphe orienté, et si
on avait un algorithme polynomial le résolvant, on en aurait également un dans la version
non-orientée, ce qui contredit le Théorème 11.1.
Algorithmes
Le problème dans se version orientée est considéré comme plus difficile.
Voici un résumé de la situation.
— Complexité : pareil, c’est NP-difficile.
— Heuristique nearest-neighbor : également mauvaise.
— Heuristique avec un ratio d’approximation (à la Christofidès) : c’est une question ou-
verte. On ne connaı̂t à ce jour aucun algorithme fournissant en temps polynomial une
solution dans un rapport borné avec l’optimum.
— Recherche locale : même voisinage. En revanche, Lin-Kernighan fonctionne beaucoup
moins bien.
— Branch-and-Bound : pareil :
— La formulation par programme linéaire semblable.
— La relaxation lagrangienne semblable : on cherche alors un 1-arbre orienté, voir
ci-dessous.
Problème du postier
153 CHAPITRE 11. TOURNÉES
Ici, G peut être vu comme la modélisation d’une ville, les sommets étant les intersections
de rues et les arêtes les portions de rues. Les poids peuvent être le temps de parcours des
rues. Le problème est alors celui que se pose un facteur voulant déposer tout son courrier en
un minimum de temps.
Algorithme
Contrairement au problème du voyageur de commerce, il existe un algorithme polynomial
simple qui trouve la tournée optimale. Remarquons déjà que dans le cas où le graphe est
eulérien, la question est triviale.
Sinon, on a la propriété suivante.
Lemme 11.1. La chaı̂ne fermée de coût minimum qui passe par toutes les arêtes au moins
une fois passe au plus deux fois par chaque arête.
Démonstration. Soit G = (V, E) le graphe. Soit une chaı̂ne C passant par toutes les arêtes au moins une fois.
Pour chaque arête e, on construit des arêtes e1 , . . . , er correspondant à chacun des passages sur e. Notons
G0 ce nouveau (multi)graphe. G0 est eulérien. On a donc créé des copies de certaines arêtes de manière à
rendre G eulérien. Réciproquement, si on crée des copies d’arêtes pour rendre G eulérien, on a la possibilité
de parcourir le multigraphe en passant par chaque arête du multigraphe une fois et une seule, et cela induit
sur G une chaı̂ne C passant par toutes les arêtes au moins une fois.
Soit un multigraphe G0 eulérien, et soit une arête e présente un nombre s de fois s ≥ 3. Alors, si on
enlève 2p représentant de e, avec p ∈ N et s > 2p, alors G0 reste eulérien.
Chercher la chaı̂ne de G qui passe à moindre coût par toutes les arêtes consiste donc à dupliquer à
moindre coût des arêtes de G afin de le rendre eulérien. Ici, le coût de la duplication est égal à la somme des
coûts des arêtes dupliquées.
Problème du postier
Donnée : Un graphe G = (V, E) et une fonction de coût sur les arêtes c : E → R+ .
Tâche
P : Trouver F ⊆ E tel que degF (v) = degE (v) mod 2 pour tout v ∈ V , et tel que
e∈F c(e) soit minimal.
P Trouver F ⊆ E tel que degF (v) = degE (v) mod 2 pour tout v ∈ V et tel que
e∈F c(e) soit minimal : On peut vérifier que, si les c(e) ≥ 0, un tel F est constitué de
chaı̂nes appariant les sommets de degré impairs de G (qui sont en nombre pair).
Un tel F est alors facile à trouver : soit J l’ensemble des sommets de degré impair de G.
On considère le graphe complet K sur J, et on met un coût
sur chaque arête jj 0 de K. Le couplage parfait de plus petit coût donne alors la solution (on
sait trouver un tel couplage en temps polynomial, comme indiqué dans le paragraphe sur
l’heuristique de Christofidès).
D’où
Algorithme
Et de même que pour la version non orientée, on a un algorithme de résolution exacte
en temps polynomial, simple à implémenter. En effet, un tel chemin est une circulation
x ∈ RA + de coût minimum, étudiée au Chapitre 5, pour des capacités inférieures la = 1 et
des capacités supérieures ua = +∞ pour tout a ∈ A. (Rappelons qu’une circulation satisfait
la loi de Kirchoff en tous les sommets – c’est un flot sans source ni puits). Réciproquement,
si on a une circulation x ∈ RA + entière satisfaisant ces contraintes, et si D est faiblement
connexe, en vertu du Théorème 2.2, il existe un chemin fermé passant par chaque arc un
nombre xa de fois.
Théorème 11.6. Il existe un algorithme polynomial qui résout le problème du postier, dans
sa version orientée.
11.3 Exercices
11.3.4 T -joints
Soit G un graphe avec des coûts c : E → R (contrairement au cours, on accepte des coûts
négatifs). Soit T un ensemble de cardinalité paire. Notons E − l’ensemble des arêtes de coût
négatif, T − l’ensemble des sommets incidents à un nombre impair d’arêtes de E − , et enfin
d : E → R+ avec d(e) := |c(e)|. On dit que J est un T -joint si degJ (v) est impair si v ∈ T
et pair sinon. (rappel A4B = (A \ B) ∪ (B \ A)).
1. Montrer que c(J) = d(J4E − ) + c(E − ).
2. Montrer que J est un T -joint si et seulement si J4E − est un (T 4T − )-joint.
3. Conclure que J est un T -joint de coût minimal pour le coût c si et seulement si J4E −
est un (T 4T − )-joint de coût minimal pour le coût d.
4. Conclure que l’on sait trouver en temps polynomial un T -joint de coût minimum,
quelque soit le coût.
11.3.5 Plus courte chaı̂ne dans les graphes sans cycle absorbant
Utiliser l’exercice précédent pour montrer que l’on sait calculer en O(n3 ) une plus courte
chaı̂ne dans les graphes sans cycle absorbant (rappel : un cycle absorbant est un cycle de
coût total < 0 ; trouver un couplage parfait de coût min se fait en O(n3 )).
1. En prenant comme états les couples (X, v) tels que v ∈ X ⊆ V \ {s}, montrer que
l’on peut écrire une équation de programmation dynamique permettant le calcul de la chaı̂ne
optimale.
Pour les questions suivantes, on peut se servir des identités indiquées à la fin de l’examen.
2. Quel est le nombre d’états possibles ?
On prend comme opération élémentaire l’addition.
3. Estimez le nombre d’additions que ferait un algorithme exploitant cette équation de
programmation dynamique. Comparez ce nombre au nombre d’additions que ferait un algo-
rithme qui énumérerait toutes les solutions.
4. Si votre ordinateur est capable de faire 1 million d’opérations élémentaires par seconde,
pour chacune des valeurs suivantes de n, indiquez (par un calcul “à la louche”) si vous serez
capable de résoudre le problème avec cet algorithme en 1 seconde, 1 heure, 1 jour, 1 semaine,
1 mois, 1 an, 1 siècle :
n = 15 n = 30 n = 45.
7
2
4
5
Conception de réseaux
Les réseaux sont omniprésents. Qu’ils soient routiers, ferrés, informatiques, électriques
ou gaziers, ils ont souvent des rôles stratégiques et économiques cruciaux, et leur robustesse
(i.e. leur capacité à assurer leur mission même en cas de défaillance locale) est une qualité
souvent recherchée.
L’objet de ce chapitre est de présenter quelques modèles et algorithmes de base dans le
domaine de la conception de réseau robuste – champ essentiel de la recherche opérationnelle.
Nous étudierons deux problèmes :
— celui de l’arbre couvrant de poids minimal : étant donné un graphe pondéré, trouver
un arbre inclus dans ce graphe, de poids minimal, tel que tous les sommets soient reliés
par l’arbre.
— celui de l’arbre de Steiner de poids minimal, qui généralise le problème précédent : étant
donné un graphe pondéré, trouver un arbre inclus dans ce graphe, de poids minimal,
tel que tous les sommets d’un sous-ensemble prédéterminé soient reliés par l’arbre.
A B C D E F G
A 0 3 8 9 10 5 5
B 3 0 9 9 12 5 4
C 8 9 0 2 10 9 9
D 9 9 2 0 11 9 8
E 10 12 10 11 0 11 11
F 5 5 9 9 11 0 1
G 5 4 9 8 11 1 0
On veut trouver le réseau routier de distance totale minimale qui relie tous les villages,
sachant qu’un tronçon relie toujours deux villages (il n’y a pas d’embranchement sur les
routes).
On peut modéliser le problème précédent par un graphe complet Kn = (V, E), où V est
l’ensemble des villages et E tous les tronçons possibles, i.e. toutes les paires ij avec i 6= j
des éléments de V . On a une fonction de poids w : E → PR+ .
On cherche alors un sous-ensemble F ⊆ E tel que e∈F w(e) soit minimal et tel que le
graphe (V, F ) soit connexe.
161 CHAPITRE 12. CONCEPTION DE RÉSEAUX
Remarque
Le problème ci-dessus admet toujours une solution qui soit un arbre. En effet, s’il ne l’était
pas, il y aurait nécessairement un cycle puisqu’il est connexe. On pourrait alors supprimer
une arête de ce cycle sans faire disparaı̂tre la connexité et sans détériorer le poids total
puisque la fonction de poids est à valeur ≥ 0.
On cherche donc à résoudre un problème d’arbre couvrant de poids minimal.
Une autre application a déjà été vue : les arbres couvrants apparaissent dans la relaxation
lagrangienne du problème du voyageur de commerce (borne du 1-arbre), voir Chapitre 11.
Cela justifie la formulation sous forme de problème.
Problème de l’arbre couvrant de poids minimal
Donnée : Un graphe G = (V, E), une fonction de poids w : E → R.
Tâche : Trouver un arbre couvrant de plus petit poids.
Pour ce problème, il y a un petit miracle puisque nous allons voir qu’il existe un
algorithme polynomial glouton qui le résout : l’algorithme de Kruskal. Rappelons qu’un
algorithme est dit glouton si à chaque itération on fait le meilleur choix local. Ces algorithmes
sont rarement optimaux (penser aux algorithmes FIRST-FIT et NEXT-FIT du bin-packing :
ils sont gloutons, mais non-optimaux ; de même pour l’algorithme glouton pour le sac-à-dos).
L’algorithme de Kruskal se décrit de la manière suivante.
— Trier les arêtes par poids croissant : e1 , . . . , em .
— Poser F := {e1 }, i := 1.
— Répéter
Faire i := i + 1. Si F ∪ {ei } ne contient pas de cycle, faire
F := F ∪ {ei }.
Théorème 12.1. L’algorithme de Kruskal résout le problème de l’arbre couvrant de poids
minimal.
La preuve s’appuie sur le lemme suivant, illustré Figure 12.2. On dit qu’une forêt F =
(V, F ) est bonne s’il existe un arbre couvrant T = (V, F 0 ) de poids minimal avec F ⊆ F 0
Lemme 12.1. Soit F = (V, F ) une bonne forêt, soit une coupe δ(X) (avec X ⊆ V ) disjointe
de F et e une arête de poids minimal dans δ(X). Alors (V, F ∪ {e}) est encore une bonne
forêt.
Démonstration. Soit T un arbre couvrant de poids minimal contenant F . Soit P le chemin reliant dans T
les extrémités de e. P intersecte δ(X) en au moins une arête f . Alors T 0 := T \ {f } ∪ {e} est encore un arbre
couvrant. D’après la définition de e, on a w(e) ≤ w(f ), et donc w(T 0 ) ≤ w(T ). Par conséquent, T 0 est encore
un arbre couvrant de poids minimal. Comme F ∪ {e} est contenu dans T 0 , c’est encore une bonne forêt.
Preuve du Théorème 12.1. L’algorithme de Kruskal ajoute à chaque itération l’arête de plus petit poids
dans la coupe δ(K), où K est l’une des deux composantes connexes de F = (V, F ) incidentes à ei . Comme
δ(K) est disjointe de F , le Lemme 12.1 s’applique.
Tout au long de l’algorithme, (V, F ∪ {ei }) est donc une bonne forêt. En particulier à la dernière itération
où la forêt se transforme en arbre. Par définition d’une bonne forêt, cet arbre est optimal.
CHAPITRE 12. CONCEPTION DE RÉSEAUX 162
Figure 12.2 – Une bonne forêt, qui reste une bonne forêt lorsqu’on ajoute l’arête e (on suppose que e est
de poids minimal dans δ(X)).
163 CHAPITRE 12. CONCEPTION DE RÉSEAUX
Remarque
Cet algoritme fonctionne quelque soit le signe des poids des arêtes. Dans l’exemple intro-
ductif, on supposait que les poids étaient tous positifs ; cela pour permettre de conclure que
le problème du graphe connexe couvrant de plus petit poids pouvait se ramener au problème
de l’arbre couvrant de plus petit poids. Ce dernier problème lui se résout par l’algorithme
de Kruskal indépendament du signe du poids des arêtes.
Théorème 12.2. Le problème de l’arbre de Steiner est NP-difficile, même si tous les poids
sont égaux à 1.
Théorème 12.3. L’algorithme décrit ci-dessus fournit une solution de poids au plus 2 fois
plus grand que la solution optimale.
Démonstration. Il suffit de prouver que w̄(T 0 ) est au plus deux fois plus grand que celui de l’arbre de Steiner
T de poids minimum w(T ).
Soit T l’arbre de Steiner de plus petit poids. Dupliquons chacune des arêtes de T . On a donc maintenant
un graphe eulérien que l’on peut parcourir en passant exactement une fois sur chaque arête : cycle C. Cela
induit un cycle hamiltonien C 0 dans K : on parcourt S dans l’ordre de leur première apparition dans C. On
a finalement
où dist(x, y) est la distance de x à y, i.e. la longueur d’une plus courte chaı̂ne de x à y
en prenant w comme longueur des arêtes (voir Chapitre 3 pour ces calculs de plus courts
chemins).
Pour voir que l’équation (12.1) est vraie, supposons d’abord que x est une feuille. Dans
ce cas, x est relié par une chaı̂ne à un sommet y qui est tel que
— soit y ∈ U
— soit y ∈
/ U et y de degré au moins 2.
Pour le premier point, l’équation (12.1) est vraie en posant U 0 := {y}. Pour le second point,
l’équation est vraie car alors y est le point de rencontre d’une chaı̂ne partand de x, d’un
arbre couvrant U 0 ∪ {y} et d’un arbre couvrant U \ U 0 ∪ {y}.
Enfin, supposons que x ne soit pas une feuille. Dans ce cas l’équation est vraie pour
y = x.
L’équation (12.1) calculées de proche en proche conduit à
Elements de preuve. La preuve de l’équation (12.1) a été esquissée ci-dessus. Il reste à expliquer la com-
plexité.
Le terme O(3s n2 ) vient du calcul de p(U ). Supposons que l’on ait calculé tous les p(U ) pour un cardinal
|U | = i. Le calcul d’un p(U ) pour une cardinalité |U | = i+1 se fait en n2i (interprétation de l’équation (12.1)).
Ps−1 s
La complexité totale est donc de l’ordre de i=0 n2i i+1 = O(3s ns).
2
Le terme O(mn + n log n) vient du calcul des plus courtes distances.
Une approche par la programmation dynamique peut donc être pertinente si le nombre
s de terminaux est petit.
12.3.4 Branch-and-cut
L’approche branch-and-cut (voir le Chapitre 11 pour une première approche du branch-
and-cut) repose sur la proposition suivante.
Démonstration. Si x est vecteur d’incidence d’un arbre de Steiner, il est clair qu’il satisfait les inégalités ci-
dessus. Réciproquement,
P soit x∗ une solution optimale du programme linéaire. Notons T := {e ∈ E : xe = 1}.
D’après l’inégalité e∈δ(X) xe ≥ 1, l’ensemble T est connexe. Et si T contient un cycle C, on peut trouver
une arête e ∈ C telle que w(e) = 0, arête que l’on peut supprimer sans que les contraintes se retrouvent
violées.
Le problème de l’arbre de Steiner consiste à trouver minx maxλ L(x, λ). On peut minorer
cette quantité par max G(λ), avec G(λ) := minx L(x, λ), ie :
G(λ) := P P P
min e∈E w(e)xe + v∈V \S e∈δG (v) λv,e (xv0 v + xe − 1)
s.c. xe est le vecteur indicateur d’un arbre couvrant G0
qui peut se réécrire...
X X
G(λ) := − λv,e + poids minimal d’un arbre couvrant G0
v∈V \S e∈δ(v)
0
où l’arbre couvrant GP 0 est calculé avec les poids wuv := wuv + λu,uv 1(u ∈
/ S) + λv,uv 1(v ∈
/ S)
0
si uv ∈ E et wv0 v := e∈δ(v) λv,e .
G(λ) se calcule donc aisément par l’algorithme de Kruskal, ainsi que ses sur-gradients.
On sait donc maximiser G(λ), et on peut calculer de bonnes bornes inférieures.
Pour le branchement, c’est simple : les solutions réalisables associées à un nœud de l’arbre
de branch-and-bound correspond à l’ensemble des arbres avec un sous-ensemble d’arêtes
imposé. Il est en effet facile de voir que trouver l’arbre couvrant de poids minimum avec des
167 CHAPITRE 12. CONCEPTION DE RÉSEAUX
arêtes imposées se fait encore avec l’algorithme de Kruskal. La situation est ici plus simple
que dans le cas du voyageur de commerce où pour conserver la borne du 1-arbre en fixant
des arêtes et en en interdisant d’autres il faut modifier la fonction de coût.
Sans surprise, on a
Remarquons que l’arbre de Steiner de plus petite longueur est le réseau de plus petite
longueur reliant tous les points, l’existence d’un cycle conduisant toujours à une solution
sous-optimale. Pour une illustration d’un tel réseau, voir Figure 12.4.
Les heuristiques de résolutions, les algorithmes, etc. s’appuient sur la propriété suivante.
On appelle point de Steiner une extrémité de segment qui ne soit pas un des points de l’input.
Proposition 12.4. Les points de Steiner sont toujours de degré 3 (au sens du nombre
d’arêtes). De plus, on ne peut avoir deux segments se rencontrant en un angle faisant stric-
tement moins de 120◦ .
CHAPITRE 12. CONCEPTION DE RÉSEAUX 168
12.5 Exercices
12.5.6 Matroı̈des (pour les élèves ayant un goût pour les maths)
Soit E un ensemble fini et soit I une collection de parties de E. Si I satisfait
(i) si I ∈ I et J ⊆ I, alors J ∈ I.
(ii) si I, J ∈ I et |I| < |J|, alors I ∪ {z} ∈ I pour un certain z ∈ J \ I.
alors (E, I) est appelé un matroı̈de.
1. Soit G = (V, E) un graphe connexe. Montrer que (E, F) où F est l’ensemble des forêts
de G est un matroı̈de.
2. Soit E = E1 ∪ E2 ∪ . . . ∪ Ek l’union de k ensemble disjoints, et soient u1 , u2 , . . . , uk des
entiers positifs. Montrer que (E, I) où I est l’ensemble des parties I de E telles que
I ∩ Ei ≤ ui est un matroı̈de (appelé matroı̈de de partition).
3. Soit M une matrice réelle. Soit E l’ensemble des colonnes de M et soit I les sous-
ensembles de colonnes indépendantes (pour l’agèbre linéaire). Montrer que (E, I) est
un matroı̈de (appelé matroı̈de matriciel).
4. Soit (E, I) un matroı̈de. Supposons donnée une fonction de poids w : E → R. Montrer
que trouver l’indépendant de poids maximum peut se faire par l’algorithme glouton.
Le coût de sélection de l’arc a se note fa et le coût d’utilisation de l’arc a pour une unité
de bien i se note cia . On veut trouver A0 tel que le coût total (sélection des arcs et transport
du flot) soit le plus petit possible.
1. Modéliser ce problème sous forme d’un programme liénaire en nombres entiers, en les
variables xia , pour a ∈ A et i = 1, . . . , k, et ya , pour a ∈ A, où ya code la sélection de l’arc
A dans la conception du réseau.
2. Proposer une relaxation lagrangienne qui permette de calculer de bonnes bornes
inférieures.
On définit G(λ) = minx∈X L(x, λ). Calculer G(λ) revient à résoudre un problème de
minimisation. On note xλ la solution dans X correspondante.
2. A λ fixé, peut-on calculer en temps polynomial la valeur de G(λ) ? Avec quel algo-
rithme ?
171 CHAPITRE 12. CONCEPTION DE RÉSEAUX
3. Montrer que si x0 est le vecteur indicateur d’un arbre couvrant K dont le degré en p
est au plus s, alors G(0) ≥ G(λ) pour tout λ ≥ 0. Que peut-on par ailleurs dire de cet arbre
couvrant par rapport à notre problème de départ ? Justifier.
Supposons maintenant que x0 est le vecteur indicateur d’un arbre couvrant K dont le
degré en p est strictement plus grand que s.
4. On veut trouver λ ∈ R+ tel que G(λ) soit maximal. Expliquer pourquoi on peut se
limiter aux valeurs de λ de la forme λ = ce − cf avec e ∈/ δ(p) et f ∈ δ(p). Evaluer une borne
supérieure N sur le nombre de telles valeurs et en conclure que maximiser G se fait en temps
polynomial.
On ordonne ces valeurs de λ de façon à avoir une séquence λ1 < λ2 < cldots < λN . Soit i
le plus petit indice tel que xλi est un arbre couvrant dont le degré en p est inférieur ou égal
à s.
6. Montrer que quitte à changer un peu la solution xλi on peut obtenir un arbre couvrant
de degré s en p de vecteur indicateur x∗ tel que
L(xλi , λi ) = L(x∗ , λi ).
7. En déduire que G(λi ) = e∈E ce x∗e et que x∗ est la solution à notre problème de départ.
P
On est donc dans une situation où la borne fournie par la relaxation lagrangienne coı̈ncide
avec l’optimum.
CHAPITRE 12. CONCEPTION DE RÉSEAUX 172
u x
3 3
1 1
2 u x x
2 8 3 u
3
4
7
4
1
1 4
3 4
4
2 4
2 v w v w
v
5
w
u x u x
2
1
1 1
2 2
v v
w w
Figure 12.4 – A gauche, l’input d’un problème de Steiner euclidien, à droite l’output.
173 CHAPITRE 12. CONCEPTION DE RÉSEAUX
Château d’eau
1
4 4
2 2 2 4
2 1
1
2 1 2 2
7
1
2
6
1 2 2
1
1 4
4 4
4 4
5 1 2
Figure 12.5
CHAPITRE 12. CONCEPTION DE RÉSEAUX 174
CHAPITRE 13
Ouverture
En conclusion, signalons les outils de la recherche opérationnelle ainsi que des domaines
à la frontière que nous avons simplement évoqués, par manque de temps et de place, mais
qui sont extrêmement importants.
Ces outils sont les méthodes de décomposition, les méthodes de coupes, l’optimisation
convexe et la simulation.
Ces domaines sont les statistiques, les files d’attente et la théorie des jeux.
13.1.4 Simulation
Simuler c’est reproduire à volonté un phénomène original à l’aide d’un modèle qui en
abstrait les éléments essentiels, dans le but de tirer des conclusions sur ce phénomène.
L’intérêt est évident quand
— le phénomène original est difficile à reproduire à volonté (conditions particulières dif-
ficiles à remplir, coût, durée, etc.)
— la modélisation sous forme problème ne se résout pas facilement (par exemple, les
problèmes biniveaux compliqués ; ou en physique : équations Navier-Stokes)
On distingue les simulations à temps continu et ceux à événements discrets.
La simulation peut être utile par exemple pour dimensionner une flotte de véhicule de
transport à la demande, compte tenu de la fonction d’utilité des agents, de la congestion,
etc. ; pour proposer un nouveau système logistique, avec des tarifications variables ; pour
étudier une chaı̂ne d’approvisionnement complexe ; etc.
177 CHAPITRE 13. OUVERTURE
La simulation est souvent couplée avec des techniques plus classiques de recherche opérationnelle,
comme on le dévine aisément à la lecture des exemples ci-dessus.
départ
arrivée service
attente
Les taux d’arrivée et de service, λ et µ sont donnés. Si le processus d’arrivée est poissonien
et si la durée de service suit une loi exponentielle, le nombre de personnes dans la file est
une chaı̂ne de Markov en temps continu. Notons que pour avoir un régime stationnaire, il
faut que λ/µ < 1. En toute généralité, il n’y a pas de raison que la file d’attente puisse être
modélisée par une chaı̂ne de Markov, et leur étude peut devenir extrêmement difficile.
Les applications sont nombreuses : dimensionnement des caisses de supermarché, des
services hospitaliers, des standard téléphoniques, serveurs informatiques, etc.
dans le Chapitre 6, nous avons vu les mariages stables (théorème de Gale-Shapley), qui
appartiennent au champ des jeux coopératifs où l’on s’intéresse à la stabilité des coalitions.
Il y a parfois des intéractions fortes entre la théorie des jeux et le recherche opérationnelle :
1. lorsque la fonction objectif ne veut pas optimiser mais partager équitablement : les
problèmes académiques sont par exemple les mariages stables, cake cutting, necklace
splitting. Dans ces deux derniers problèmes, on veut partager un objet (un gâteau ou
un collier) et l’on veut que toutes les personnes perçoivent le partage comme juste dans
un certain sens, même si elles n’ont pas la même fonction d’évaluation.
2. lorsque la fonction objectif contient un terme qui résulte d’un terme réponse économique.
Par exemple, lorsqu’on veut concevoir un réseau routier, on est obligé de se demander
par où va s’écouler le flot des usagers. Mais le flot est le résultat de ce que chaque
personne décide de faire, d’un processus d’optimisation locale. Il faut donc évaluer et
comparer les équilibres de Nash selon les choix qui sont faits. On parle alors de problème
biniveau.
Dans ce second cas, il faut souligner que les choses sont difficiles, et peu intuitives comme
en témoigne le célèbre paradoxe de Braess.
v v
c(x) = x c(x) = x
c(x) = 1 c(x) = 1
c(x) = 0
s s
t t
c(x) = 1 c(x) = x c(x) = 1 c(x) = x
w w
Considérons les réseaux de la Figure 13.2. Un flot de valeur 1 veut aller de s à t. Chaque
élément infinitésimal du flot – un usager – choisit le chemin le moins coûteux. On obtient
un équilibre de Nash. Dans le réseau de gauche, cet équilibre de Nash est formé d’un flot de
valeur 1/2 empruntant la route supérieure, et d’un flot de valeur 1/2 empruntant la route
inférieure. L’ajout d’une autoroute au milieu détériore tout : on peut vérifier qu’à l’équillibre
de Nash la totalité de flot unitaire suit la route s, v, w, t. On vérifie que le coût s’est détérioré
pour chaque usager.
d’utilité des clients potentiels. Dans les problèmes d’enchères, utilisées en particulier par les
prestataires logistiques, on se demande quelles règles mettre en place pour maximiser le prix
auquel est vendue in fine la prestation.
CHAPITRE 13. OUVERTURE 180
Eléments de correction
Exercice 2.6.5
Considérons le graphe G = (V, E) dont les sommets V sont les formations, et dans lequel
une arête relie deux formations s’il existe un employé devant suivre ces deux formations. En-
fin, les couleurs sont les jours. Il est clair que tout planning compatible avec les contraintes de
la DRH induit une coloration propre du graphe, et dont le nombre de couleurs est le nombre
de jours de la session. Réciproquement, toute coloration induit un planning compatible avec
les contraintes de la DRH, avec un nombre de jours égal au nombre de couleurs.
Exercice 3.4.5
Ce problème se résout par la programmation dynamique. Les états sont les âges possibles
de la machine en début d’année. Les périodes sont les années. On s’intéresse aux quantités
π(t, k) = profit maximal possible en terminant la tème année en possédant une machine d’âge k.
On souhaite trouver maxk∈{1,2,3} (π(5, k) + pk ).
π(t, k) satisfait les relations suivantes :
0 pour tout k ∈ {2, 3}
π(1, k) =
b 0 − c0 pour k = 0.
π(t + 1, k + 1) = π(t, k) + bk − ck si k ∈ {1, 2}
π(t + 1, 1) = max (π(t, k) + pk−1 − 100000 + b0 − c0 ) si t ∈ {1, 2, 3, 4}
k∈{1,2,3}
Exercice 3.4.10
1. On peut passer de n’importe quel point à n’importe quel autre point. On peut vérifier
exhaustivement que l’on peut atteindre n’importe quel tronçon depuis le point supérieur
gauche. On peut de plus imposer l’orientation du wagonnet : on peut partir du point supérieur
gauche vers la droite, et suivre un parcours fermé qui ramène la wagonnet au même point
avec l’orientation opposée ; quitte à ajouter ce parcours fermé au début du trajet, on peut
donc fixer l’orientation en fin de trajet.
2. Soient s et t les deux points particuliers. On peut arbitrairement dire que les sommets
associés aux tronçons sont les milieux physiques des tronçons. On les relie conformément à
l’énoncé. On relie s et t aux plus proches milieux de tronçons, et éventuellement entre eux s’ils
ne sont séparés par aucun milieu de tronçon. On obtient donc le graphe dont la construction
est précisée dans l’énoncé, avec en plus deux sommets particuliers s et t. Les coûts sur chaque
arête sont les distances correspondantes dans le réseau. On peut appliquer l’algorithme de
Djikstra pour calculer la chaı̂ne de plus petit coût dans ce graphe, qui correspond au trajet
le plus court dans le réseau.
Exercice 3.4.11
satisfaisant cette demande. Maximiser le gain revient alors à chercher le sous-ensemble d’in-
tervalles disjoints (les locations ne pouvant se recouvrir) de plus grand poids.
Exercice 5.3.12
1. Considérons le graphe D = (V, A) dont les sommets sont les blocs et pour lequel on a un
arc (u, v) si v ∈ Yu . Une solution du cas statique est un fermé de ce graphe et réciproquement
tout fermé du graphe est une solution du cas statique.
3. On note X̄ := V \ X. Comme X est fermé, les seuls arcs qui vont jouer un rôle dans
la coupe sont les arcs de la forme (s, v) avec v ∈ X̄ et ceux de la forme (v, t) avec v ∈ X.
On a donc X X X X X
ua = cv − cv = cv − cv .
a∈δ + (X∪{s}) v∈X̄∩V + v∈X∩V − v∈V + v∈X
D̃
P
4. Posons C := v∈V + cv .
Soit X un fermé de D de valeur maximale η. D’après ce qui a été montré ci-dessus, on a
alors une s-t coupe de D̃ de capacité C − η.
Réciproquement, prenons une s-t coupe de D̃ de capacité minimale κ. D’après ce qui a
été montré, l’ensemble X induit sur D est alors fermé et de valeur C − κ.
On a donc : C −κ = η, et chercher une coupe minimale sur D̃ est équivalent à chercher un
fermé maximum sur D. Comme chercher une coupe minimale se fait en temps polynomial,
on sait résoudre le problème de manière efficace.
Exercice 6.6.3
Dans le cas de la Figure, ce maximum est 4. Pour prouver son optimalité, il suffit de
trouver 4 lignes ou colonnes qui contiennent tous les points. Notons ν la cardinalité maximale
d’une famille P de points tels que deux points quelconques de P ne soient jamais dans la
même ligne ou colonne, et notons τ la cardinalité minimale d’une famille R de lignes ou
colonnes contenant tous les points. On a forcément ν ≤ τ puisque chaque élément de R
contient au plus un élément de P .
Ces ensembles P et R de cardinalité 4 sont indiqués sur la Figure 13.3.
CHAPITRE 13. OUVERTURE 184
O E
Le cas général est polynomial. En effet, ce problème se modélise sous la forme d’un graphe
biparti de la façon suivante :
les sommets sont les lignes d’une part et les colonnes d’autre part, une arête relie la ligne l
et la colonne c s’il y a un point noir à leur intersection. Un ensemble de points tels que deux
points quelconques de l’ensemble soient toujours sur des lignes et des colonnes distinctes
correspond à un couplage dans ce graphe. On recherche donc √ un couplage de cardinalité
maximale dans ce graphe biparti, ce qui peut se faire en O( nm) où n est le nombre de
sommets (ici le demi-périmètre du rectangle), et m le nombre d’arêtes (ici le nombre de
points noirs).
Exercice 7.4.2
Gestion dynamique de stock, cas à 1 seul bien
1. Par définition du processus : ce qui reste dans le stock sur la période t, c’est ce qui
était déjà dans le stock à la période t − 1, plus ce qui a été produit, moins ce qui est parti à
cause de la demande.
2. Aux contraintes décrivant la dynamique du stock, il faut ajouter les contraintes de
capacité xtP≤ Pt et les
PTcontraintes de positivité. La fonction objectif est simplement le
T −1
coût total t=1 pt xt + t=1 st yt . On s’arrête à T − 1 pour le stock car comme on souhaite
minimiser et que les coût de stockage sont positifs, on aura toujours yT = 0.
Le programme linéaire s’écrit donc
PT PT −1
Min t=1 pt xt + t=1 st yt
s.c. xt − yt + yt−1 = dt t = 1, . . . , T
x t ≤ Pt t = 1, . . . , T
xt ≥ 0 t = 1, . . . , T
yt ≥ 0 t = 1, . . . , T − 1.
185 CHAPITRE 13. OUVERTURE
3. Le coût minimal est 37. Le vecteur de production est x = (8, 1, 3, 1) ou x = (9, 0, 4, 0),
ou n’importe quelle combinaison convexe des deux.
4. En dehors du puits et des sources proposées par l’énoncé, il n’y a pas d’autres sommets.
Il y a deux types d’arcs :
— les arcs (v, wt ), avec une capacité supérieure = Pt , une capacité inférieure = 0 et un
coût = pt et
— les arcs (wt−1 , wt ) avec une supérieure = +∞, une capacité inférieure = 0 et un coût
= st−1 .
Le problème du b-flot de coût minimum est exactement le problème linéaire de la question
2. En particulier, la dynamique correspond à la loi de Kirchoff.
5. Les problèmes de flot de coût min sont des cas particuliers de la programmation
linéaire. Ils possèdent des algorithmes dédiés qui peuvent être plus rapides que les solveurs
généraux de programme linéaire (méthode des cycles de coût moyen minimum, vu en cours
par exemple).
7. C’est K
P
k=1 zkt ≤ 1 pour tout t.
PK PT PK PT −1
Min k=1 t=1 p kt x kt + k=1 t=1 skt ykt
s.c. xkt − ykt + yk(t−1) = dkt t = 1, . . . , T ; k = 1, . . . , K
xkt ≤ Pkt zkt t = 1, . . . , T ; k = 1, . . . , K
PK
k=1 zkt ≤ 1 t = 1, . . . , T
zkt ∈ {0, 1} t = 1, . . . , T , pour k = 1, . . . , K
xkt ≥ 0 t = 1, . . . , T ; k = 1, . . . , K
ykt ≥ 0 t = 1, . . . , T − 1 ; k = 1, . . . , K.
PT P P PK PT −1
K T PK PT
G(λ, µ) = − λ
t=1 t + min k=1 p x
t=1 kt kt + k=1 s
t=1 kt kty + k=1 (λ
t=1 t − µ P )z
kt kt kt
Exercice 7.4.3
187 CHAPITRE 13. OUVERTURE
1.
Pn PT
Min i=1 (xi,τ − xi,τ −1 )
τ =1 ci,τ
s.c. xi,τ −1 ≤ xi,τ i ∈ {1, . . . , n} ; τ ∈ {1, . . . , T } (i)
Pn xi,τ ≤ xj,τ i ∈ {1, . . . , n} ; j ∈ Yi ; τ ∈ {1, . . . , T } (ii)
i=1 mi (x i,τ − x i,τ −1 ) ≤ Mτ τ ∈ {1, . . . , T } (iii)
xi,τ ∈ {0, 1} i ∈ {1, . . . , n} ; τ ∈ {0, 1, . . . , T } (iv)
xi,0 = 0 i ∈ {1, . . . , n} (v)
xi,τ − xi,τ −1 vaut 1 si le bloc i est extrait au cours de l’année τ et 0 sinon. La fonction
objectif est donc bien celle attendue. Les contraintes (i) imposent que pour i fixé, la séquence
des xi,τ est de la forme 0, 0, . . . , 0, 1, 1, . . . , 1, comme attendu. Les contraintes (ii) imposent
que si un bloc i est extrait au cours de l’année τ ou avant, alors tout bloc de Yi est extrait au
cours de l’année τ ou avant, conformément à la définition de Yi . Les contraintes (iii) imposent
que la masse totale extraite au cours de l’année τ soit inférieure à Mτ , comme attendu.
P∗
2. ττ 0 =1 Mτ 0 est la masse maximale qui a pu être extraite sur les années de 1 à τ ∗ . Si
la masse de Yi∗ et du bloc i∗ est strictement supérieure, forcément le bloc i∗ ne peut être
extrait au cours de l’année τ ∗ ou avant.
P∗
3. ττ 0 =1 Mτ 0 est la masse maximale qui a pu être extraite au cours des années de 1 à τ ∗ .
Si la masse de Yi∗ ∪ Yj ∗ et des blocs i∗ et j ∗ est strictement supérieure, forcément les blocs
i∗ et j ∗ ne peuvent être extraits tous deux au cours de l’année τ ∗ ou avant.
4. La suppression des variables indicées par des bonnes paires réduit le nombre de variables
du programme linéaire. Cela réduit forcément sa complexité. L’ajout des contraintes induites
par des bons triplets ne changent pas les solutions entières du programme linéaire, mais
diminue la valeur de la relaxation continue, ce qui améliore la qualité de la borne utilisée
dans le branch-and-bound – on est dans un problème de maximisation – et donc réduit
potentiellement le nombre de branchements.
Exercice 8.3.3
Question 2. Supposons que l’on ait une solution optimale S et notons p et g respectivement
le plus petit et le plus gros objets qui soient placés. S’ils ne sont pas mis ensemble dans un
conteneur, notons p0 celui qui est avec g et g 0 celui qui est avec p. On a ap ≤ ap0 et ag0 ≤ ag .
Comme ap0 + ag ≤ 1, on a ap0 + ag0 ≤ 1 et ap + ag ≤ 1. Il existe donc toujours une solution
optimale dans laquelle le plus petit et le plus gros objets placés sont ensemble dans un
conteneur. Par induction, on peut montrer qu’en triant les ai et en cherchant à mettre le
plus petit objet courant avec le plus grand possible, on obtient une solution optimale en
O(n log(n)).
Exercice 9.4.3
Nous proposons dans la suite une modélisation, toute en sachant que plusieurs autres
sont possibles.
CHAPITRE 13. OUVERTURE 188
1. Notons xij (resp. yij ) la part de la demande du client j desservie par l’entrepôt forward
(resp. reverse) i. Notons ui (resp. vi ) la variable binaire codant l’ouverture d’un entrepôt
forward (resp. reverse) i.
Un programme linéaire possible est alors
P P
Min i∈I (fi ui + ri vi + j∈J cij hj (xij + αj yij ))
P
s.c. Pi∈I xij = hj j∈J
Pi∈I yij = αj hj j∈J
x ≤ bi u i i∈I
Pj∈J ij
j∈J yij ≤ ei vi i∈I
ui , vi ∈ {0, 1} i ∈ I, j ∈ J
xij , yij ∈ R+ i ∈ I, j ∈ J.
u = u0
0
on passe de v à v par une opération drop, add ou swap – définies en cours,
189 CHAPITRE 13. OUVERTURE
ou
v = v0
Avec une telle définion de voisinage, l’espace des solutions est clairement connexe, ce qui
assure qu’une recherche locale potentiellement pourra atteindre la meilleure solution.
Remarque : on peut également faire les opérations simultanément sur u et v, mais alors
il faut démontrer, ce qui n’est pas immédiat, que l’espace des solutions est bien connexe...
4. Cela ne change rien, car les hj , αj hj , bi , ei étant entier, le problème de transport a
forcément une solution entière.
Exercice 9.4.4
Pn
2. Le problème a une solution réalisable si et seulement si i=1 qi ≤ n − k : il faut
simplement que la capacité totale lorsque les k entrepôts sont fermés soit suffisante pour
tout accueilir.
4. Oui, le plus célèbre des logiciels libres étant GLPK (ou GUSEK).
5. Une recherche locale permet d’avoir des solutions raisonnables en un temps d’exécution
court. Cela peut permettre à des décideurs de pouvoir obtenir rapidement des solutions
optimisées.
CHAPITRE 13. OUVERTURE 190
7. L’espace des solutions est donc l’ensemble des F ⊆ {1, . . . , n} avec |F | = k. On définit
F et F 0 comme étant voisins si |F \ F 0 | = |F 0 \ F | = 1. Une telle opération s’appelle opération
de pivot, et rappelle le pivot de l’algorithme du simplexe.
Exercice 9.4.5
X
s.c. ys ≤ K (i)
s∈S
X
xs,c = 1 c∈C (iii)
s∈S
ys ∈ {0, 1} s ∈ S (vi)
h ∈ R+ (vii)
4. Les variables y d’une part, et les variables x et h d’autre part sont indépendantes dans
les contraintes du programme linéaire de la question précédente. Quelque soit le choix de y,
on peut fixer x et h indépendament. On optimise donc les deux programmes
XX
min h + λs xs,c
s∈S c∈C
X
s.c. xs,c = 1 c∈C (iii)
s∈S
h ∈ R+ (vii)
et X
min (−λs )ys
s∈S
X
s.c. ys ≤ K (i)
s∈S
ys ∈ {0, 1} s ∈ S (vi)
indépendament.
CHAPITRE 13. OUVERTURE 192
5. Optimiser le deuxième programme est simple : il suffit de trier les s par valeurs de λs
décroissantes ; ensuite on met ys = 1 pour les K premiers s, et ys = 0 pour les suivants.
Complexité O(S log S).
Optimiser le premier programme est presque aussi simple. Noter que les λs sont positifs.
A l’optimum, (iv) est une égalité. On essaie successivement dans h toutes les valeurs de ts,c ,
et pour chacune de ces valeurs, on fait la chose suivante : pour chaque c, on cherche parmi
les ts,c ≤ h celui tel que λs est le plus petit, et c’est ce couple (s, c) pour lequel xs,c = 1.
Pour chacune des SC valeurs de h essayées, on obtient une valeur de la fonction objectif ;
on garde alors la plus petite. Complexité O(S 2 C 2 ).
6. Avec les notations de cours, pour tout λ ∈ RS , on sait calculer G(λ) et ses surgradients
en O(S 2 C 2 ) (donc rapidement), et donc optimiser par un algorithme de surgradient G(λ),
fournissant ainsi des bornes au programme linéaire en nombres entiers.
Exercice 10.4.3
Les deux premières questions sont triviales. Pour la dernière, notons pj la durée de la
tâche j. Sans perte de généralité, supposons que les tâches sont ordonnées de manière à ce
que
w1 w2 wn
≥ ≥ ... ≥ .
p1 p2 pn
Prenons maintenant un ordonnancement quelconque et supposons qu’il y ait une tâche j et
w w 0
suivie d’une tâche j 0 telles que pjj ≤ p j0 . En inversant l’ordre de ces deux tâches, on ajoute
j
à la fonction objectif la quantité wj pj 0 − wj 0 pj qui est négative ou nulle. Un ordonnancement
optimal est donc obtenu en ordonnant les tâches dans l’ordre de leur indexation.
Exercice 10.4.8
Si on voit les entrepôts D et C comme des machines, les camions comme des tâches,
et le déchargement et le chargement comme des opérations, on est exactement dans le cas
d’un problème de flow-shop à 2 machines, 15 tâches et minimisation du makespan, ce qui se
résout en temps polynomial (et même à la main) par l’algorithme de Johnson. Les durées
des opérations sont données par le temps qu’il faut pour décharger ou charger les boı̂tes.
Ici la solution est de 91 minutes. On terminera donc au plus tôt à 7h31.
Exercice 11.3.7
Conformément à ce qui a été ajouté à l’oral, on suppose les coûts positifs.
1. Pour (X, v) tels que v ∈ X ⊆ V \ {s}, on note π(X, v) le coût minimum d’une chaı̂ne
élémentaire dont les sommets sont {s} ∪ X et dont les extrémités sont s et v. On a alors
c(sv) si |X| = 1
π(X, v) =
minu∈X\{v} (π(X \ {v}, u) + c(uv)) sinon.
193 CHAPITRE 13. OUVERTURE
Pour trouver la meilleure chaı̂ne hamiltonienne d’extrémité s, il suffit alors de comparer les
valeurs de π(V, v) pour tout v ∈ V (les coûts étant positifs, on n’a pas intérêt à revenir en
s).
2. C’est le nombre de couples (X, v) comme dans l’énoncé. Il y en a
n−1
n−1
X
k = (n − 1)2n−2 .
k=1
k
3. Pour chaque état (X, v), le nombre d’additions est |X| − 1 (nombre de u possibles dans
l’équation de programmation dynamique). D’où un nombre d’opérations
n−1
n−1
X
k(k − 1) = (n − 1)(n − 2)2n−3 .
k=1
k
√ n
Enumérer toutes les solutions donne un nombre d’additions (n−1)!(n−1) ∼ n! ∼ 2πn ne ,
ce qui est incomparablement plus grand.
4. Pour n = 15, on compte 7450 472 opérations, ce qui se fait en moins d’une seconde.
Pour n = 30, on compte 1.09 × 1011 opérations, ce qui se fait en 1.09 × 105 secondes, soit
environ 30 heures. On ne peut résoudre cette instance en 1 jour, mais en une semaine oui.
Pour n = 45, on compte 8.32 × 1015 opérations, ce qui fait 8.32 × 109 secondes, soit
environ 263 années. Même en un siècle on ne parvient à résoudre cette instance.
5. On sait calculer la plus courte chaı̂ne hamiltonienne de s à v, pour tout v ∈
/ V . Il suffit
alors de comparer les valeurs de π(V, v) + c(vs) pour tout v.
Exercice 12.5.1
C’est une application directe de l’algorithme de Kruskal, qui détermine l’arbre couvrant
de plus petit poids. Il y a plusieurs arbres possibles. L’un est donné Figure 13.4. Le coût
optimal est 35.
Exercice 12.5.9
P P
1. L(x, λ) = e∈E ce xe + λ x
e∈δ(p) e − s .
2. A λ fixé, on cherche à trouver l’arbre couvrant du graphe K de plus petit coût avec comme
coût ce sur l’arête e si e ∈/ δ(p) et ce + λ si e ∈ δ(p). L’algorithme de Kruskal résout cela en
temps polynomial.
Château d’eau
1
4 4
2 2 2 4
2 1
1
2 1 2 2
7
1
2
6
1 2 2
1
1 4
4 4
4 4
5 1 2
Figure 13.4
195 CHAPITRE 13. OUVERTURE
Par ailleurs, x0 est un arbre couvrant, satisfaisant les contraintes de l’énoncé et dont le coût
est égal à G(0) borne inférieure du problème. C’est donc une solution optimale pour notre
problème.
4. Quand λ varie, xλ ne change que lorsque l’ordre obtenu en classant les arêtes par coûts
croissants change (algorithme de Kruskal). Cet ordre ne peut changer que lorsque une arête
f ∈ δ(p) voit son coût coı̈ncider avec celui d’une arête e ∈
/ δ(p), ce qui ne peut arriver que
si λ est de la forme donnée dans l’énoncé. On a alors N ≤ 21 |T |2 (|T | − 1) (en comptant le
nombre de tels couples d’arêtes (e, f )). On peut maximiser G(λ) en appliquant au plus N
fois l’algorithme de Kruskal.
X X X X
G(λ) = ce xλe + λ xλe − s ≥ ce xλe + µ xλe − s ≥ min L(x, µ) = G(µ).
x∈X
e∈E e∈δ(p) e∈E e∈δ(p)
Avec ce raisonnement, on montre que G(λ) est croissant jusqu’à λi . Comme G(λ) est continue
P suffit en fait), on peut conclure que G(λ) ≤ G(λi ).
(ou concave – cela
Par ailleurs, e∈δ(p) xλe i − s ≤ 0 et donc on a pour tout λ ≥ λi
X X X X
G(λi ) = ce xλe i +λi xλe i − s ≥ ce xλe i +λ xλe i − s ≥ min L(x, λ) = G(λ).
x∈X
e∈E e∈δ(p) e∈E e∈δ(p)
6. Si xλi est de degré s en p, il n’y a rien à montrer. Supposons donc que ce ne soit pas le
cas. Pour λ légèrement inférieur à λi , le degré de xλ en p est > s. Notons que xλ et xλi
sont tous deux solutions du problème de minimisation de G(λi ). Ensuite, il faut remarquer
que si on a deux arbres couvrant optimaux d’un graphe pondéré, on peut progressivement
substituer les arêtes de l’un par les arêtes de l’autre, tout en maintenant le caractère optimal.
En procédant à une telle transformation de xλ à xλi , l’un des arbres intermédiaires constitue
une solution à la question.
7. Comme G(λi ) = L(x∗ , λi ) et que le degré de x∗ en p est égal à s, on a G(λi ) = e∈E ce x∗e .
P
Par ailleurs La solution x∗ est une solution réalisable à notre problème, et dont le coût
coı̈ncide avec celui d’une borne inférieure (en l’occurence G(λi )). C’est donc une solution
optimale.
CHAPITRE 13. OUVERTURE 196
Bibliographie
[1] R.K. Ahuja, T.I. Magnanti, and J.B. Orlin, Network flows, Prentice Hall, 1993.
[2] V. Arya, N. Garg, R. Khandekar, A. Meyerson, K. Mungala, and V. Pandit, Local search
heuristics for k-median and facility location problems, SIAM Journal on Computing 33
(2004), 544–562.
[3] P. Brucker, An efficient algorithm for the job-shop problem with two jobs, Computing
40 (1988), 353–359.
[4] V. Chvátal, Linear programming, W. H. Freeman, New York, 1983.
[5] R. Correa and C. Lemarechal, Convergence of some algorithms for convex minimization,
Mathematical Programming 62 (1993), 261–275.
[6] D. de Werra, T. M. Liebling, and Hêche J.-F., Recherche opérationnelle pour ingénieurs,
Presses polytechniques et universitaires romandes, 2003.
[7] S.E. Dreyfus and R.A. Wagner, The Steiner problem in graphs, Networks (1972), 195–
207.
[8] J. Edmonds and R.M. Karp, Theoretical improvements in algorithmic efficiency for
network flow problems, Journal of the ACM 19 (1972), 248–264.
[9] D. Gale and L.S. Shapley, College admissions and the stability of marriage, American
Mathematical Monthly (1962), 9–15.
[10] M.R. Garey and D.S. Johson, Computers and intractability : A guide to the theory of
np-completness.
[11] A. V. Goldberg, Scaling algorithms for the shortest paths problem, SIAM Journal on
Computing 24 (1995), 222–231.
[12] A.V. Goldberg and R.E. Tarjan, Finding minimum-cost circulations by cancelling ne-
gative cycles, Journal of the ACM 36 (1985), 873–886.
[13] M. Grötchel, L. Lovász, and L. Schrijver, Geometric algorithms and combinatorial op-
timization, 2nd edition, Springer, Heidelberg, 1994.
[14] B. Hajek, Cooling schedules for optimal annealing, Mathematics of Operations Research
13 (1991), 311–329.
BIBLIOGRAPHIE 198
[15] A. Hertz and D. De Werra, Using tabu search techniques for graph coloring, Computing
39 (1987), 345–351.
[16] J.R. Jackson, Scheduling a production line to minimize maximum tardiness, Tech. re-
port, University of California, Los Angeles, 1955.
[17] S.M. Jonson, Optimal two- and three-stage production schedules with setup times inclu-
ded, Naval Res. Log. Quart 1 (1954), 61–68.
[18] R.M. Karp, A characterization of the minimum cycle mean in a digraph, Discrete Ma-
thematics 23 (1978), 309–311.
[19] Kuhn, (1955).
[20] S. Lin and B.W. Kernighan, An effective heuristic algorithm for the traveling-salesman
problem, Operations Research 21 (1973), 498–516.
[21] J. Matousek and B. Gärtner, Understanding and using linear programming, Sringer,
Berlin Heidelberg New York, 2007.
[22] T. Terlaky, An easy way to teach interior-point methods, European Journal of Opera-
tional Research 130 (2001), 1–19.
Annexe
199
Quelques outils de R.O.
Quelques sociétés
Roadef (www.roadef.org) : société francaise de recherche opérationnelle et d’aide à la décision.
Euro (www.euro-online.org) : associations européennes des sociétés de recherche opérationnelle.
Informs (www.informs.org) : Institute for Operations Research and the Management Sciences.
C’est la plus grande société professionnelle dans le domaine de la recherche opérationnelle.
Ressources en ligne
— 24h Operations research.
— Une liste d’outils open-source logiciels pour la Recherche Opérationnelle : NEOS :
Server for optimisation (http ://www-neos.mcs.anl.gov) Propose des serveurs de logiciel
R.O utilisables en ligne via des formats de modélisation standard (AMPL, ...)
— Outils par ordre alphabétique COIN-OR (http ://www.coin-or.org/) COmputational
INfrastructure for Operations Research Projet Open source, ambitieux, d’origine IBM
(C++).
— COMET (http ://www.cs.brown.edu/people/pvh/comet/comet.html) COMET est une
platforme associant la recherche local et la programmation par contrainte. COMET
s’appuit sur un langage objet et peut être étendu (création de contraintes...) en C++.
— GLPK (http ://www.gnu.org/software/glpk/) : La bibliothèque Glpk est livrée avec
un solveur autonome (glpsol), capable de traiter des problèmes linéaires (continus ou
en nombre entier) par des méthodes de simplexe ou de Points Intérieur. Ces problèmes
peuvent être modélisés dans différents langages, dont l’excellent GMPL (clone de
AMPL).
— Page RO de Google (http ://code.google.com/p/or-tools/) : Google a développé pour
ses besoins propres un certain nombre d’outils de recherche opérationnelle. Sur ce site,
ils sont proposés en open-source.
— GUSEK (http ://gusek.sourceforge.net/gusek.html) : le solveur GLPK avec une inter-
face ; pour Windows.
BIBLIOGRAPHIE 202