Introduction à la RO pour étudiants
Introduction à la RO pour étudiants
INTRODUCTION LA RECHERCHE
OPRATIONNELLE
Frdric Meunier
Universit Paris Est, CERMICS, Ecole des Ponts Paristech, 6-8 avenue Blaise Pascal, 77455
Marne-la-Valle Cedex.
E-mail : [email protected]
Frdric Meunier
1. Gnralits
..........................................................................
Prsentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Histoire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Modlisation et optimisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Objectif de ce cours . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
partie I. Fondements
2. Bases
................................................................
................................................................................
2.1. Graphes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
13
15
2.4. Problme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
18
19
2.6. Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
23
............................
27
27
34
3.3. Rsum . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
36
3.4. Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
36
4. Programmation linaire
............................................................
43
43
45
4.3. Algorithmes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
50
4.4. Dualit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
52
54
4.6. Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
55
5. Flots et Coupes
....................................................................
59
59
5.2. Multiots . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
66
5.3. Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
67
71
6.1. L'objet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
71
71
73
74
74
6.6. Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
76
..........................................
77
7.1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
77
78
7.3. Mtaheuristiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
82
7.4. Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
85
..........................................................
8. Remplissage de conteneurs
........................................................
87
89
8.1. Sac--dos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
89
8.2. Bin-packing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
91
8.3. Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
94
9. Positionnement d'entrepts
........................................................
97
9.1. Formalisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
97
9.2. Branch-and-bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
98
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
11. Tournes
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
13. Ouverture
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
Elments de correction
Bibliographie
Annexe
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167
vi
vii
CHAPITRE 1
GNRALITS
Prsentation
La recherche oprationnelle (RO) est la discipline des mathmatiques appliques qui traite
des questions d'utilisation optimale des ressources dans l'industrie et dans le secteur public.
Depuis une dizaine d'annes, le champ d'application de la RO s'est largi des domaines comme
l'conomie, la nance, le marketing et la planication d'entreprise. Plus rcemment, la RO a t
utilise pour la gestion des systmes de sant et d'ducation, pour la rsolution de problmes
environnementaux et dans d'autres domaines d'intrt public.
Exemples d'application.
par des points xs l'avance puis revenir son point de dpart en cherchant minimiser la
distance parcourue est un problme typique de recherche oprationnelle. On appelle ce problme
le
Remplir un conteneur avec des objets de tailles et de valeurs variables. Si le conteneur a une
capacit nie, on va chercher maximiser la valeur place dans le conteneur. On appelle ce
problme le
problme du sac--dos
T,
problme d'ordonnancement
Chacun de ces problmes peut bien sr tre compliqu l'envie. Dans ce cours, on restera
relativement simple quelques contraintes de plus susent en eet faire de ces problmes de
vritables sujets de thse (par exemple pour le remplissage de conteneur un sujet de thse peut
consister en : plusieurs types de conteneurs, plusieurs produits stocker, des incompatibilits).
Histoire
La recherche oprationnelle est ne pendant la Seconde Guerre mondiale des eorts conjugus
d'minents mathmaticiens (dont von Neumann, Dantzig, Blackett) qui il avait t demand
de fournir des techniques d'optimisation des ressources militaires. Le premier succs de cette
approche a t obtenue en 1940 par le Prix Nobel de physique Patrick Blackett qui rsolut un
problme d'implantation optimale de radars de surveillance. Le qualicatif oprationnelle
vient du fait que les premires applications de cette discipline avait trait aux oprations militaires. La dnomination est reste par la suite, mme si le domaine militaire n'est plus le
principal champ d'application de cette discipline, le mot oprationnelle prenant alors plutt
le sens d' eectif . Ce sont donc ces mathmaticiens qui ont cr une nouvelle mthodologie
caractrise par les mots-cls
modlisation
et
optimisation.
A partir des annes 50, la recherche oprationnelle fait son entre dans les entreprises. En
France, des entreprises comme EDF, Air France, la SNCF crent cette poque des services de
recherche oprationnelle (qui existent toujours). La discipline commence tre enseigne dans
les universits et les grandes coles. Puis, au milieu des annes 70, sans doute cause d'un
excs d'enthousiasme au dpart et l'inadquation des moyens informatiques l'application
des mthodes de la RO, la discipline s'essoue. A partir du milieu des annes 90, on assiste
un retour en force la RO, les outils informatiques tant maintenant la hauteur des mthodes
proposes par la recherche oprationnelle. On assiste depuis une explosion du nombre de
logiciels commerciaux et l'apparition de nombreuses botes de conseil. Pour la France, notons
Ilog (65 millions d'euros de CA), Eurodcision (2,8 millions d'euros de CA), Artelys (1,6 millions
d'euros de CA) l'tranger Dash-Optimization (rachet dbut 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 prs de 240).
Les racines.
peut penser Alcuin ou Euler qui se sont tous deux intresss des problmes 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 problme du loup, de la chvre et du chou devant traverser une rivire dans une
barque o au plus un lment peut prendre place.
Un homme devait transporter de l'autre ct d'un euve un loup, une chvre 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
ct sans aucun dommage. Dise qui peut comment il a russi traverser en conservant
intacts le loup, la chvre et les choux
(1) .
Euler est le mathmaticien allemand qui les notables de Knigsberg demandrent s'il tait
possible de parcourir les ponts de la ville en passant sur chacun des 7 ponts exactement une fois
(voir Figure 1). Ce genre de problme se rencontre maintenant trs souvent dans les problmes
de tournes du type facteur ou ramassage de dchets mnagers, dans lesquels il faut parcourir
les rues d'une ville de faon optimale. Euler trouva la solution en 1736 un tel parcours est
impossible en procdant une modlisation subtile par des mots. La solution actuelle, beaucoup
plus simple, utilise une modlisation par un
graphe
qu'une bonne modlisation peut simplier de manire drastique la rsolution d'un problme.
Le premier problme de recherche oprationnelle vise pratique a t tudi par Monge en
1781 sous le nom du problme des dblais et remblais. Considrons
combler
trous. Notons
pour combler le
j me
ai
la masse du
ime
tas de sable et
bj
sable ?
La solution que proposa Monge est intressante et procde par une modlisation dans un espace continu dans lequel on cherche une godsique malheureusement, elle n'est pas correcte.
1. Homo quidam debebat ultra uvium 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.
Figure 1.
La solution correcte pour trouver l'optimum est connue depuis les annes 40 et utilise la programmation linaire (que nous verrons au Chapitre 4), ou mieux, la thorie des ots (que nous
verrons au Chapitre 5).
Modlisation et optimisation
[Wikipedia] Un modle mathmatique est une traduction de la ralit pour pouvoir lui
appliquer les outils, les techniques et les thories mathmatiques, puis gnralement,
en sens inverse, la traduction des rsultats mathmatiques obtenus en prdictions ou
oprations dans le monde rel.
Les problmes d'organisation rencontrs dans une entreprise ne sont pas mathmatiques dans
leur nature. Mais les mathmatiques peuvent permettre de rsoudre ces problmes. Pour cela,
il faut traduire le problme dans un cadre mathmatique, cadre dans lequel les techniques de la
recherche oprationnelle pourront s'appliquer. Cette traduction est le modle du problme.
Cette phase essentielle s'appelle la
modlisation.
cialement du modle choisi. En eet, pour un mme problme, direntes modlisations sont
possibles et il n'est pas rare que le problme semble insoluble dans une modlisation et trivial
dans une autre.
D'autre part, tous les lments d'un problme ne doivent pas tre modliss. Par exemple,
lorsqu'on souhaite planier une tourne, la couleur du vhicule n'a pas d'intrt. Le statut du
conducteur, la nature du vhicule ou du produit transport peuvent, eux, en avoir, et seule
une comprhension de l'objectif de l'optimisation de la tourne peut permettre de trancher.
Souvent, la phase de modlisation est accompagne ou prcde de nombreuses discussions avec
le commanditaire (lequel n'a d'ailleurs pas toujours une ide claire de ce qu'il cherche obtenir
ces discussions lui permettent alors galement de prciser ses objectifs).
Une des vrais dicults de dpart est de savoir quels lments doivent tre modliss et quels
sont ceux qui n'ont pas besoin de l'tre. Il faut parvenir trouver le juste quilibre entre un
modle simple, donc plus facilement soluble, et un modle compliqu, plus raliste, mais plus
dicile rsoudre. Cela dit, pour commencer, un modle simple est toujours prfrable et permet
souvent de capturer l'essence du problme
variables de dcision ?
contraintes ?
Rappelons immdiatement que, en toute rigueur, on n'optimise qu'une seule quantit la fois.
On ne peut pas demander d'optimiser la fois la longueur d'un trajet et son temps de parcours :
le trajet le plus court peut trs bien passer par un chemin vicinal et le trajet le plus rapide tre
trs long mais sur autoroute. L'optimum par rapport un critre n'a pas de raison de concider
avec l'optimum par rapport l'autre critre. Il existe bien ce qu'on appelle l'optimisation
objectif
ou
multi-critre,
multi-
qui consiste hirarchiser les objectifs, ou leur donner une certaine pondration, ce qui revient
in ne un vrai problme d'optimisation ; ou alors de proposer toute une famille de solutions
dite Pareto-optimale.
Une fois le modle crit, le chercheur oprationnel va proposer un algorithme de rsolution qui
tiendra compte de l'objectif qui lui a t x. Comme nous le verrons de nombreuses reprises
dans ce cours, pour un mme modle, un grand nombre d'algorithmes peut tre propos. Ces
algorithmes se direncient par la qualit de la solution qu'ils fournissent, le temps d'excution,
la simplicit d'implmentation. Dans certains cas, il peut tre cruciale de pouvoir fournir une
solution en
1 ms,
avec une certaine tolrance sur la qualit de la solution. Dans d'autres cas,
semaine de calcul peut tre acceptable mais en revanche on souhaite trouver l'optimum. En
validation thorique.
dploiement de la solution,
validation pratique.
interface, discuter les formats des chiers d'input, de discuter la question de la maintenance du
code, etc. mais l on s'loigne du cur du mtier du chercheur oprationnel.
En rsum, la mthodologie de la recherche oprationnelle suit en gnral le schma suivant.
1. Objectifs, contraintes, variables de dcision.
2. Modlisation.
3. Proposition d'un algorithme, validit thorique de l'algorithme (temps d'excution pour
trouver la solution, qualit de la solution fournie).
4. Implmentation, validation pratique de la solution.
5. Dploiement de la solution.
Objectif de ce cours
La recherche oprationnelle occupe une place grandissante dans l'industrie, la logistique et les
transports. Pour un ingnieur souhaitant faire un travail technique dans ces disciplines, elle est
quasi-incontournable. L'objectif de ce cours est de donner les bases de recherche oprationnelle :
la mthodologie, les problmes et les modles typiques, les principales techniques de rsolution.
Un tudiant matrisant les exercices de ce cours est capable de proposer une modlisation d'une
grande part des problmes de recherche oprationnelle rencontrs dans l'industrie, de proposer des approches de rsolution et d'en discuter les qualits respectives. Le cours se focalisera
principalement sur les tapes 2. et 3. ci-dessus.
Premire PARTIE I
FONDEMENTS
CHAPITRE 2
BASES
2.1. Graphes
Une brique de base dans la modlisation est le
lorsqu'on est confront un rseau (rseau de transport, rseau informatique, rseau d'eau ou de
gaz, etc.). Comment parcourir le rseau de manire optimale ? C'est la question du voyageur de
commerce par exemple. Comment concevoir un rseau informatique robuste, tout en minimisant
le nombre de connexions ? C'est le thme de la conception de rseau (Network Design), abord
au Chapitre 12.
Mais les graphes apparaissent galement de manire plus subtile dans certaines modlisations
de problmes o la structure du graphe n'est pas physique. Un exemple classique est le problme
de l'aectation optimale d'employs des tches qui sera tudi aux Chapitres 5 et 6. Les
sommets reprsentent des tches et des employs, et les artes les appariements possibles entre
tches et employs. Ils apparaissent galement dans des problmes d'ordonnancement, o les
sommets reprsentent des tches et les arcs les relations de prcdence.
On parle de famille d'artes pour souligner le fait que les rptitions sont autorises. En cas
de rptition, on parle d'artes
parallles.
boucle.
le plan par des points ce sont les sommets relis par des lignes ce sont les artes. Voir la
Figure 1.
L'ensemble des artes dont une extrmit exactement est un sommet
boucle dont les extrmits sont
deg(u) est
v
/ X.
la quantit
|(u)|.
complet
On note
(X)
(u).
Le
degr
(u). Une
u et not
uv avec u X et
est not
d'un sommet
si toute paire de sommets est relie par une arte. Voir exemple
biparti
v3
v3 v 3
v5
v1 v 2
v2
v2 v 5
v1
v5 v 6
v1 v 2
v3 v 4
v6
v4
Figure 1.
Figure 2.
Une
chane
v0 , e1 , v1 , e2 , . . . , vk1 , ek , vk
0, vi V pour i = 0, . . . , k et ej E pour j = 1, . . . , k avec ej = vj1 vj .
L'entier k est la longueur de la chane. En d'autres termes, une chane est un trajet possible dans
o
est un entier
la reprsentation d'un graphe lorsqu'on suit les artes sans rebrousser chemin sur une arte. Si
les
ei
simple.
1. Dans la terminologie anglaise, un tel sous-graphe est appel induced subgraph. Ces artes sont notes E[V 0 ].
On parle aussi en franais de graphe partiel de G, qui a le mme ensemble de sommets que G, mais n'a qu'une
partie de ses artes, et de sous-graphe partiel, qui a comme ensemble de sommets une partie des sommets de G
et comme ensemble d'artes une partie de celles de E en anglais, on parle alors de subgraph.
10
Figure 3.
lmentaire.
cycle
est
v0 , e1 , v1 , . . . , ek , v0
j < k , et ek = v0 vk1 . Un cycle est lmentaire si les vi pour i = 0, . . . , k1
sont distincts deux deux. Un cycle passant par toutes les artes d'un graphe est dit eulrien.
Un cycle lmentaire passant par tous les sommets du graphe est dit hamiltonien.
Un graphe est dit connexe si entre toute paire de sommets il existe une chane.
avec
ej = vj1 vj
pour
un sommet de
C.
(G).
La cardinalit minimale
(G).
On a la proprit trs utile suivante, car elle permet par exemple d'valuer la qualit d'un
couplage.
Proposition 2.1.1.
G. Alors
2.1.1.3. Coloration.
(G) (G).
Une notion fructueuse en thorie des graphes et trs utile en Recherche
V N.
Les entiers
paire de voisins
u, v
on ait
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'ingalit
cardinalit du plus grand sous-graphe complet
(G),
Comme pour les graphes non orients, les rptitions d'arcs sont autorises et, en cas de rp-
parallles.
boucle.
v0 , a1 , v1 , a2 , . . . , vk1 , ak , vk
k est une entier 0, vi V pour i = 0, . . . , k et aj A pour j = 1, . . . , k avec aj = (vj1 , vj ).
k est la longueur du chemin. En d'autres termes, un chemin est un trajet possible dans la
reprsentation d'un graphe lorsqu'on suit les arcs dans le sens des 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 dite lmentaire. Un chemin simple passant par tous les arcs d'un graphe
L'entier
2. Rappelons que les deux lments d'un couple sont ordonns, ceux d'une paire ne le sont pas.
12
u1
u3
(u3 , u4 )
u4
(u4 , u3 )
(u5 , u3 )
u5
(u7 , u5 )
(u2 , u1 )
u7
u2
(u6 , u3 )
u6
Figure 5.
hamiltonien.
Un circuit
eulrien.
Un chemin lmentaire passant par tous les sommets du graphe est dit
1,
v0 , a1 , v1 , . . . , ak , v0
aj = (vj1 , vj ) pour j < k , et ak = (vk1 , v0 ). Un circuit est lmentaire 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 eulrien. Un circuit lmentaire passant par tous les sommets du graphe est dit
hamiltonien. Un exemple de circuit eulrien est donn Figure 6.
avec
Thorme 2.2.1.
Un graphe connexe admet un cycle eulrien si et seulement si il n'a pas de sommet de degr
impair.
13
6
2
3
7
8
Figure 6. Graphe orient possdant un circuit eulrien. L'ordre des arcs dans un tel
circuit est indiqu.
Figure 7.
Avec ce thorme, on voit donc qu'il n'existe pas de parcours passant exactement une fois et
une seule sur chaque ponts de la ville de Knigsberg.
On appelle
graphe eulrien
qui a dj t voqu. Un camion doit quitter son entreprt, livrer dirents points d'un rseau
puis revenir son point de dpart, et ce, en parcourant la distance minimale. Le point livrer est
reprsent par un sommet du graphe, la route la plus courte entre deux points est reprsente
par une arte. On note ce graphe
simple est un
Kn = (V, E),
14
On cherche le
u, v, w.
Chapitre 11 donne plus de dtail sur cette transformation et traitera des mthodes pour rsoudre
le problme.
Dans le cas orient, la condition ncessaire et susante d'existence de chemin ou circuit
eulrien est semblable celle du Thorme 2.2.1.
Un graphe faiblement connexe admet un cycle eulrien si et seulement si deg+ (u) = deg (u)
pour tout sommet u.
Notons qu'un graphe admettant un cycle eulrien est automatiquement fortement connexe.
critre,
ou
cot,
ou
fonction de cot.
qui
Min
s.c.
f (x)
x X.
f est le critre. s.c. signie sous contraintes . X est l'ensemble des solutions possibles
ralisables, et x X est la ou les contraintes du programme. On cherche parmi ces
solutions ralisables une solution optimale x , i.e. ici une solution ralisable qui minimise le
critre. inf{f (x) : x X} est appel valeur du programme. Si X = , cette valeur est dnie
comme tant gale +.
ou
En plus de fournir un cadre compact pour formuler un problme, cette notation l'avantage
de rappeler les questions essentielles se poser lorsqu'on rsout un problme. Veut-on minimiser
ou maximiser ? Que veut-on optimiser ? Quelles sont les contraintes de notre systme ? Quelles
sont les variables sur lesquelles on peut jouer ?
Une remarque fondamentale et trs utile est que tout problme de minimisation peut se
rcrire comme un problme de maximisation : il sut de prendre comme critre
rciproquement.
grammation linaire
(Chapitre 4) et la
f (x).
la
Et
pro-
l'tude
sera initie Chapitre 7). Ces trois types de programmation sont trs frquents en recherche
oprationnelle.
15
Figure 8.
de f ,
l'cart de la solution
propose la solution
borne infrieure
on peut majorer
f (x) g(x )
%
g(x )
de l'optimum. Il est toujours utile de vrier si l'on n'a pas une borne infrieure de qualit,
facile calculer. On peut alors viter de chercher amliorer une solution en faisant tourner
longuement un programme informatique, alors qu'une borne infrieure 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 8 et 9.
Si
relve de l'optimisation
avec l'optimisation continue dans ce cours se fera par l'intermdiaire de la programmation linaire, qui, elle, ne peut pas se rsoudre par une simple drivation.
Dans les problmes industriels, l'ensemble
tre mis en bijection avec une partie de
N.
discrte, i.e.
voyageur de
qu'il peut
commerce
qui consiste trouver le cycle le plus court passant par des villes xes l'avance est de nature
discrte.
est ici l'ensemble des cycles hamiltoniens. Tout cycle de ce type est une solution
ralisable. Le critre est la distance parcourue. Il y a un nombre ni de cycles. On est bien dans
le cadre de l'optimisation discrte (et l'on voit bien qu'ici la plupart des notions de l'optimisation
continue sont sans intrt : que driver ici ?).
16
Figure 9.
f (x)
g(x) = 0,
h(x) 0
x X,
Considrons le programme
(P)
X =
6 , f : X R, g : X Rp et h : X Rq . On dit que (P ) est un programme
linaire si f est une fonction linaire, et si g et h sont toutes deux anes (cf. Chapitre 4). On
dit que (P ) est un programme convexe si f , et h sont toutes deux convexes, et si g est ane.
avec
et
Rq+ .
On dnit le
lagrangien
sup
Rp ,Rq+
L(x, , ) =
(P )
f (x)
+
si
g(x) = 0
sinon.
et
h(x) 0,
de la manire suivante
min
sup
xX Rp ,Rq
+
L(x, , ).
On a toujours
(1)
min
sup
xX Rp ,Rq
+
L(x, , )
17
sup
min L(x, , ).
Rp ,Rq+ xX
En dnissant
d(, )
Rp
Rq+ .
Max
s.c.
primal.
vP (resp. vD ) la valeur de (P )
ingalit de dualit faible
dual
de
(P )
(D)
(resp.
(D)),
vP vD .
Cette ingalit est extrmement utile et constitue un moyen automatique de gnrer des bornes
infrieures un problme. Ces notions seront en particulier approfondies dans le Chapitre 4 sur
le programmation linaire et dans le Chapitre 7. En programmation linaire, nous verrons qu'on
dispose d'une relation plus forte, appele
Remarque.
dualit forte.
2.4. Problme
Une autre notion commode dans la modlisation est la notion de
dcompose en deux parties : une partie
problme.
Un problme se
formalisation permet d'crire clairement quelles sont les lments dont on dispose au dpart et
quelle est prcisment la tche que l'on veut rsoudre. L'objectif atteindre devient donc clair
et dans un tel contexte, il est plus facile de discuter des performances de telle ou telle mthode.
Par exemple, le problme de l'existence d'une chane eulrienne peut s'crire :
Pn
j=1 d(ej ).
Le premier problme est un type particulier de problme, qui joue un rle important en
informatique thorique, et s'appelle un
problme de dcision,
rpondre une question ferme, i.e. dont la rponse est soit oui , soit non . Le second
problme est un
problme d'optimisation.
18
rationnelle passe toujours par l'application d'un algorithme, qui est ensuite implment. Si le
problme que l'on tente de rsoudre est un programme d'optimisation, on parlera d'algorithme
exact si l'algorithme
proch sinon.
ap-
La question qui se pose galement est celle de l'ecacit de l'algorithme, i.e. du temps qu'il
va mettre pour rsoudre le problme (une fois admis que l'algorithme est correct et rsout bien
le problme).
grandes quantits de donnes. Mais ces tests-l peuvent tre trs, trs longs, et de toute faon,
chaque fois que l'on va penser un algorithme possible, on ne va pas systmatiquement procder
son implmentation et des tests. La
thorie de la complexit,
la recherche oprationnelle, a pour but de mesurer a priori l'ecacit d'un algorithme. La petite
histoire qui va suivre va montrer l'intrt de cette thorie, et est librement adapt du livre de
10].
Garey et Johnson [
patron vous appelle dans son bureau et vous annonce que l'entreprise est sur le point d'entrer
sur le march comptitif du schmilblick. Il faut donc trouver une bonne mthode qui permette
de dire si une collection de spcications peuvent tre satisfaites ou non, et si oui, qui donne
la faon de construire ce schmilblick. On peut imaginer qu'un schmilblick est dcrit par des
variables boolennes
De plus, on a des
rgles du type si
Etc.
(3) . Dans ce cas, vous pourriez sereinement aller voir votre patron
3. anglicisme signiant dans ce contexte qu'il n'existe pas d'algorithme ecace rsolvant le problme considr.
19
et lui dire : Je ne parviens pas trouver d'algorithme ecace car un tel algorithme ne peut
exister.
Malheureusement, personne ce jour n'a t capable de montrer qu'il existe un problme
intrinsquement intractable. En revanche, les thoriciens de l'informatique ont dvelopp un
concept qui est presqu'aussi bon, celui de problme
fournit des techniques varies pour prouver qu'un problme est aussi dicile qu'une grande
quantit d'autres problmes, pour lesquels aucune mthode ecace n'a t trouve ce jour,
malgr les eorts rpts des plus grands experts de la plante. Avec ces techniques, vous pourrez
peut-tre prouver que votre problme est
diciles. Vous pourriez alors entrer dans le bureau de votre patron et annoncer : Je ne parviens
pas trouver d'algorithme ecace, mais aucune star de la RO, aucune star de l'informatique
thorique, aucune star de l'optimisation discrte ne peut le faire. Au pire, cela l'informera qu'il
ne sert rien de vous virer pour embaucher un autre expert votre place.
Prouver qu'un problme est
NP-complet
NP-complet
fournit une
information sur l'approche la plus productive. Cela montre qu'il ne faut pas se focaliser sur la
recherche d'un algorithme exact et ecace et qu'il faut avoir des approches moins ambitieuses.
Par exemple, on peut chercher des algorithmes ecaces rsolvant divers cas particuliers. On peut
chercher des algorithmes sans garantie sur le temps d'excution, mais qui en gnral semblent
tre rapides. Ou alors, on peut relaxer le problme et chercher un algorithme rapide qui
trouve des schmilblicks satisfaisant presque toutes les spcications. Dans les chapitres suivants,
nous verrons des exemples concrets illustrant de telles approches.
compte le nombre d'oprations lmentaires que cet algorithme eectue pour le rsoudre. Comme
la taille des donnes de
f (n)
fonction de complexit f
qui
n,
la taille
pour trouver une solution. La taille des donnes, c'est le nombre de bits qu'il faut pour coder
les donnes.
g(n)
comme ecace, un algorithme exponentiel est en gnral mauvais. Le Tableau 1 montre le temps
qu'il faut des algorithmes de fonction de complexit variable pour rsoudre un problme pour
direntes tailles de donnes.
On entend souvent dire : Ces problmes ne se poseront plus lorsque la puissance des ordinateurs aura augment . C'est faux, comme le montre le Tableau 2. Supposons par exemple que
l'on ait un algorithme rsolvant le problme du schmilblick
est une constante et o
B2n
oprations lmentaires, o
bien plus d'1 milliard d'oprations par seconde). Et supposons que l'on soit capable de rsoudre
rsout.
20
Taille
Fonction de complexit
10
20
30
40
50
60
n
n2
n3
n5
2n
0, 01 s 0, 02 s 0, 03 s
0, 04 s
0, 05 s
0, 06 s
0, 1 s 0, 4 s
0, 9 s
1, 6 s
2, 5 s
3, 6 s
1 s
8 s
27 s
64 s
125 s
216 s
0, 1 ms 3, 2 ms 24, 3 ms
102, 4 ms
312, 5 ms
777, 6 ms
1 s 1 ms
1s
18 min20 s 13 jours 36 annes et 6 mois
Table 1. Comparaison de diverses fonctions de complexit pour un ordinateur eectuant 1 milliard d'oprations par seconde.
n
n2
n3
n5
2n
3n
Table 2.
Un problme de dcision
ticat
Avec un ordinateur
Avec un ordinateur
N1
100N1
N2
10N2
N3
4.64N3
N4
2.5N4
N5
N5 + 6.64
N6
N6 + 4.19
Comparaison de diverses fonctions de complexit.
est
dans
NP
1000N1
31.6N2
10N3
3.98N4
N5 + 9.97
N6 + 6.29
cer-
de vrier que la rponse est oui , sans pour autant tre capable de trouver cette rponse
(voir des exemples ci-dessous). Le sigle
O(n + m),
au total
P.
21
G et n
O(m) et
nombre de sommets, tester le fait que tous les sommets sont de degr pair prend
O(n + m).
son
que
NP : le
NP
P,
l'algorithme qui consiste suivre le cycle hamiltonien permet de prouver que la rponse est
bien positive. Ici, le cycle hamiltonien joue le rle de certicat. Il a t galement dmontr que
ce problme est
NP-complet.
connat un algorithme ecace pour rpondre cette question, il est trs probable qu'il se trompe
car tous les problmes
Or personne ce jour n'a pu en trouver, et quantit de gens trs brillants ont cherch un tel algorithme. S'il ne se trompe pas, c'est une dcouverte fondamentale, qui aurait un impact norme
tant dans le monde de l'informatique thorique, que dans la recherche oprationnelle applique.
De plus, cette personne percevrait le prix d'1 millions de dollars oert par la Fondation Clay
pour la rsolution de la question ouverte
P =? NP.
NP-complet.
Complexit
P
P
NP-complet
NP-complet
Graphe orient : Circuit eulrien
P
Graphe orient : Chemin eulrien
P
Graphe orient : Circuit hamiltonien
NP-complet
Graphe orient : Chemin hamiltonien
NP-complet
La Figure 10 illustre les relations entre problmes P, NP, NP-complets, si P 6= NP (ce qui
Graphe non-orient : Cycle hamiltonien
La notion de problme
de dcision, dont la rponse est oui ou non . Mais les problmes que l'on rencontre en RO
22
NP-difficiles
NP-complets
NP
Figure 10.
Figure 11.
Les problmes
NP
sont rarement de ce type. Il existe une notion qui permet de caractriser des problmes diciles
qui ne sont pas des problmes de dcision : c'est celle de problme
NP-dicile.
Thorme 2.5.1.
NP-dicile.
2.6. Exercices
2.6.1. Dessiner sans lever le crayon.
possible de dessiner la gure sans lever le crayon (et sans repasser sur un trait dj dessin) et
quand il ne l'est pas.
23
Figure 12.
Et celle-l ?
G1
G2
G3
Figure 13.
pour chacun d'eux s'il possde une chane hamiltonienne. Mme question avec pour le cycle
hamiltonien.
Justiez votre rponse.
20
et
20
adjacents ?
relais reoit et met des signaux une certaine frquence. Pour viter les interfrences, on
veut que deux relais moins de
200 m
de gestion du parc de relais est une fonction croissante du nombre de frquences utilises. On
souhaite minimiser ce cot.
24
Figure 14.
Le jeu Icosian.
E1 , . . . , Em .
Ei
Il veut organiser une session de formations chacune des formation ne peut tre dispense
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 dispenses le mme jour. Le DRH souhaite
organiser la session la plus courte possible.
Modliser ce problme avec les outils du cours.
de la Figure 8, et proposer une borne infrieure gnrale pour les nombre chromatique.
plage de la Figure 9, et proposer une borne suprieure gnrale pour les couplages maximum.
2.6.8. NP-compltude de la chane hamiltonienne. Montrer que le problme de l'existence de la chane hamiltonnienne est NP-complet, sachant que celui du cycle hamiltonien l'est.
Rciproquement, montrer que le problme de l'existence du cycle hamiltonnien est NP-complet,
sachant que celui de la chane hamiltonienne l'est.
pratique a t tudi par Monge en 1781 sous le nom du problme des dblais et remblais.
Considrons
sable et
bj
trous. Notons
connat la distance
j,
dij
j me
ai
(i, j)
on
du ime tas au
25
CHAPITRE 3
Les problmes de plus courts chemins apparaissent naturellement dans des contextes varis.
Ils peuvent apparatre comme modlisation de problmes oprationnels (trajet le plus rapide,
ou le moins cher, gestion optimal d'un stock, plan d'investissement optimal, etc.), ils sont aussi
frquemment des sous-problmes d'autres problmes d'optimisation (ot de cot minimum
Chapitre 5 ou en thorie de l'ordonnancement Chapitre 10). Sous cette appellation anodine
de plus court chemin, nous verrons qu'il se cache une ralit extrmement varie, tant du point
de vue de la complexit que des types d'algorithmes mis en uvre. Le graphe peut tre orient ou
non, les artes ou les arcs avoir des poids positifs ou quelconque,... Un cas particulier important
est la
programmation dynamique
manire squentielle, chaque dcision faisant passer le systme d'un tat un autre. Ce passage
d'un tat un autre s'appelle une
transition.
trajectoire.
le cas du graphe orient avec des poids strictement positifs sur les arcs. En eet, le problme
du trajet le plus court dans un rseau (routier, de transport, informatique, etc.) rentre dans
ce cadre. Le temps de parcours d'un arc, ou sa longueur, sont dans ces contextes strictement
positifs.
En 1959, Dijkstra proposa le premier algorithme ecace. On suppose que l'on a un graphe
orient
et un sommet
la
que dans un graphe dont tous les poids sont positifs, il existe toujours un plus court chemin qui
soit un chemin lmentaire (avec rptition de sommets interdite) car si le plus court chemin
passe par un circuit, on peut supprimer ce circuit sans dtriorer le poids du chemin. Si tous
les poids sont strictement positifs, les notions de plus court chemin, plus court chemin simple
(avec rptition d'arcs interdite) et plus court chemin lmentaire (avec rptition de sommets
interdite) concident puisqu'alors suivre un circuit dtriore strictement le poids du chemin.
L'algorithme de Dijkstra va calculer les plus courts chemins dmarrant en
sommets d'arrive possibles, donc en particulier pour
t.
a
2
b
3
1
s
c
1
2
t
Figure 1.
(v)
est le
U V
et une fonction
: V R+ .
On
On s'arrte lorsque
(u) = +
pour tout
u U.
La fonction
s.
v 6= s, on garde en mmoire le dernier arc a = (u, v) pour lequel on
(v) := (u) + w(a), on peut reconstruire l'ensemble des plus courts chemins partant
s.
Il est clair que le nombre d'itrations est au plus
O(n).
|V |,
O(n2 ).
D'o le thorme :
Elments de preuve. Pour dmontrer le thorme, il faut simplement voir que lorsque u est
retir de U dans l'itration au-dessus, (u) est la vraie distance de s u (la preuve de cette
assertion est laisse en exercice).
Remarque.
plexit de
28
Exemple.
s
(0)
0
0
0
0
0
0
0
0
a
()
(3)
3
3
3
3
3
3
3
b
c
d
e
f
t
() () () () () ()
() () (3) () (5) ()
(5) () (3) () (5) ()
(4) ()
3
() (5) ()
4
(5)
3
() (5) ()
4
5
3
(8) (5) ()
4
5
3
(7)
5
(12)
4
5
3
7
5
(9)
4
5
3
7
5
9
3.1.2. Les poids sont quelconques mais le graphe est sans circuit.
On considre
maintenant le cas o les poids peuvent prendre des valeurs ngatives, mais o le graphe est sans
circuit, ou
d'un plus court chemin dans un rseau physique, cela peut paratre surprenant puisque les
temps de parcours ou les distances de portion de rseau sont toujours positifs. Mais dans de
nombreux cas le graphe dont on cherche un plus court chemin est issu d'une modlisation 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 lmentaire
concident, puisqu'il n'y a pas de circuit. Donc de mme que dans le cas o tous les
w(a)
sont
D = (V, A)
w : A R.
fonction de poids
L'algorithme de Dijkstra ne fonctionne plus lorsque les poids peuvent tre ngatifs. En eet,
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 justie que l'on retire u
U . Or si les poids peuvent tre ngatifs, il facile de voir que cette proprit n'est plus vraie.
de
A la n des annes 50, des mathmaticiens comme Ford, Bellman, Moore, et d'autres, remarqurent que dans ce contexte, un algorithme trs simple permet de trouver le plus court
chemin.
Pour dcrire cet algorithme, dnissons pour
(v) :=
posant
(v) :=
vV
sv
chemin,
de Bellman
qui dit
(2)
(u,v)A
pour tout
v V.
v,
sv
s u, o u est un antcdent
(u, v).
En fait, de faon un peu plus compacte, on a le principe suivant qui implique ce qui prcde
[Principe d'optimalit de Bellman] La sous-trajectoire d'une trajectoire optimale est
encore optimale.
29
(s) := 0
et
(u) := pour tout u tel qu'il n'existe pas de su chemin. Ensuite, on repte la boucle suivante
v dont on connat pour tous les prdcesseurs (on
Chercher un sommet
(v).
Remarquons qu'il n'est pas dicile de reconstruire le plus court chemin : en mme temps que
(v),
(v).
on peut stocker
p(v)
antcdent de
pour tout
v,
v V.
ordre
D = (V, A) est une indexation v1 , v2 , . . . , vn des
que (vi , vj ) A on ait i < j . Un graphe orient
topologique
sommets de
i, j
tels
admet un ordre topologique si et seulement si il est acircuitique. On peut alors trouver un ordre
topologique en
Scanner
O(m)
le sommet (dnition rcursive, consistante puisque le graphe est sans circuit). On choisit un
sommet
s.
v,
alors
u.
Preuve du Thorme 3.1.2. Pour prouver ce thorme, 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 antcdents de vi ont un
indice < i, ce qui assure que l'on peut toujours calculer (vi ) une fois calculs les (vj ) pour
j < i. Or, c'est ordre n'est rien d'autre qu'un ordre topologique.
Remarque.
origine s
Dans le cas acircuitique, on sait en particulier trouver un plus long chemin d'une
une destination
w0 (a) := w(a),
mme algorithme fonctionne (en gardant les mmes poids, il sut de changer les
en
max).
min
pro-
l'instant
on voit que le
et
30
Xk
d'tats possibles
xk
..
.
s := x0
t
...
..
.
..
.
k=1
Figure 2.
k=3
k=2
k =N 1
k=N
trajectoire optimale = plus court st chemin dans un graphe acircuitique
k
co
uts := 0
priodes et a la
forme
xk+1 = fk (xk , uk ),
k = 1, 2, . . . , N
k=1
Le problme de la programmation dynamique consiste trouver la trajectoire optimale, i.e.
minimisant le cot total.
Ce problme de la programmation dynamique se modlise trs bien comme celui du plus
court chemin dans un graphe orient, pondr et sans circuit. En eet, pour chaque priode
k,
on reprsente les tats possibles par des sommets. Les transitions possibles sont des arcs. Le cot
de la transition
(ou
xk xk+1
acircuitique)
(xk , xk+1 ).
et d'arrive
t,
un tat de priode
on va chercher le chemin de
k + 1.
qui a le plus
(k, x) :=
posant
l'tat
(k, x) := +
31
en
en
tapes,
tapes,
(k, x) : l'itration k ,
(k 1, x) calcules l'itration
k 1.
(k, x)
pour
x Xk ,
En voyant ce calcul comme un calcul de plus court chemin dans un graphe acircuitique
(Section 3.1.2), cela revient dire qu'un ordre topologique est donn facilement par le dcoupage
temporel.
Remarquons enn que tout graphe orient acircuitique n'est pas issu d'une modlisation d'un
systme dynamique. En eet, un graphe modlisant un processus de programmation dynamique
a tous ses chemins de
N.
priodes conscutives.
Un stock suit une dynamique de la forme
pour la priode
priode et
k ime
uk
k , suppose connue, xk
xk+1 = xk dk + uk ,
dsigne la demande
xk Z,
k ime
x0
dk
priode. On prendra
supposera
x.
g(xk+1 ),
c(uk ),
xk K .
On
en
uk
units, et
priode et le cot de pnurie si la demande ne peut tre totalement satisfaite sur la priode.
Typiquement, on a
c(u) = b + au,
g(x) =
o
sx
px
si
si
un cot xe et
x0
x 0,
p = +.
On veut minimiser
N
1
X
c(uk ) + g(xk+1 ).
k=0
Dans le vocabulaire de la programmation dynamique, les tats sont les valeurs possibles de niveau
xk xk+1
tels que
dynamique.
On applique l'algorithme de plus court chemin dans le graphe acircuitique suivant. Pour
chaque priode
objets
k = 1, . . . , N , l'objet k
ck 0 et un volume ak > 0, et
P
W . Si N
k=1 ak > W ,
supposons que l'on ait stocker ces objets dans un conteneur de volume ni
32
Considrons un
on va devoir slectionner des objets an de maximiser la valeur des objets stocks. Ce problme
est connu sous le nom du
problme du sac--dos,
avec lequel on veut transporter des objets de plus grand valeur totale, sous des contraintes de
capacit. On note
x(j, W 0 ) la valeur maximale qui peut tre transporte dans un sac de capacit
j premiers objets.
x(j, W 0 )
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 pondr, non ncessairement acircuitique.
C'est encore possible si le graphe ne possde pas de
somme des poids est
< 0.
circuit absorbant,
et
graphe acircuitique). Noter qu'une fois encore, il existe toujours un plus court chemin qui soit
un chemin lmentaire car si le plus court chemin passe par un circuit, on peut supprimer ce
circuit sans dtriorer le poids du chemin.
En fait, pour calculer un plus court chemin dans un graphe sans circuit absorbant, on peut
appliquer la mthode de la programmation dynamique vue ci-dessus.
On considre que les tats sont les sommets (Xk
(4)
(u,v)A
pour tout
v V.
de
v,
utilisant
utilisant
(u, v).
k1
un
k.
(k, v) de
k > n,
est le nombre de sommets, car l'absence de circuit absorbant garantie l'existence d'un
chemin de poids minimal qui soit sans circuit. En eet, supprimer un circuit dans un chemin
fait diminuer son poids total. Puisqu'un chemin sans circuit a moins d'arcs qu'il y a de sommets
dans le graphe, on peut drouler l'algorithme de programmation dynamique en s'arrtant au
calcul des
(n 1, v),
pour
v V.
33
s -t
(k, v)
calculs pour
k = 0, . . . , n 1
et pour
v V,
minimisant
(k, t).
Remarquons qu'il n'est pas dicile de reconstruire le plus court chemin : en mme temps que
(k, v),
on peut stocker
pk (v)
pour tout
(k, v).
Comme
v V.
Thorme 3.1.3.
Remarque : En utilisant des techniques totalement direntes [12], on peut obtenir une complexit de
que
O(n1/2 m log C)
C 2).
nomial qui trouve un plus court chemin lmentaire. Rappelons qu'un chemin lmentaire est
un chemin dans lequel chaque sommet apparat au plus une fois. Si l'on ne se restreint pas au
chemin lmentaire, le problme peut ne pas avoir de solution : en eet, en faisant passer un
chemin par un circuit absorbant, on peut rpter un nombre arbitraire de fois le passage sur le
circuit absorbant et dcrotre le cot autant qu'on le souhaite.
Considrons le problme
tV.
Considrons un
graphe (non-orient)
sommets
fait prcdemment s'applique encore : on sait qu'il existe une chane lmentaire de mme poids
que la chane de plus petit poids puisqu'on peut supprimer les cycles d'une chane de plus petit
poids (ces cycles sont alors forcments de poids nul).
L'algorithme de Dijkstra permet encore de rsoudre le problme : en eet, il sut de remplacer
chaque arte
de l'arte
uv .
uv
(u, v)
et
(v, u)
Voir Figure 3. Un plus court chemin dans ce graphe orient induit alors une plus
34
we
we
we
Figure 3.
vouloir refaire la mme transformation que dans la sous-section prcdente, savoir de remplacer
chaque arte par deux arcs de sens opposs, chacun recevant le poids de l'arte dont ils sont
issus. Le problme, c'est que dans cette transformation, on fait apparatre quantit de circuits
absorbants : toute arte de poids
<0
de style programmation dynamique ne peuvent pas appliquer. Il n'y a pas de raison particulire
de penser que ce problme soit
accepte des circuits absorbants avec un nombre d'arcs non born. Ici nos circuits absorbants ont
deux arcs seulement.
En fait, il y a bien un algorithme polynomial mais curieusement elle provient d'un tout autre
domaine de l'optimisation discrte et nous en reparlerons dans le chapitre sur les tournes (Chapitre 11). L'outil dont on a besoin est le
T -joint
de tourne du style facteur . Avec cet outil, on peut trouver une plus courte chane lmentaire
en
O(n3 ).
NP-
dicile.
Considrons le problme
: Un graphe
G = (V, E),
tV.
w : E R,
deux sommets
sV
et
On a le thorme suivant.
Le problme de la plus courte chane lmentaire avec des poids quelconques, dans un graphe quelconque, est NP-dicile.
Thorme 3.2.1.
35
2
5
10
c
s
6
4
f
2
3
t
2
6
i
Figure 4.
3.3. Rsum
Complexit
O(n2 )
(Dijkstra)
(1)
O(m)
acircuitique
(Programmation dynamique)
O(nm)
NP-dicile
O(n2 )
(Dijkstra)
(1)
O(n3 )
NP-dicile
3.4. Exercices
3.4.1. Plus court chemin.
c : A R+ .
Soit
capacit
dans le graphe de la
et une destination
La
1. On peut atteindre, avec les bonnes structures de donnes, O(m + n log n).
2. On peut atteindre avec des techniques direntes O(n1/2 m log C).
36
d.
(2)
2
a
10
2
6
t
5
d
Figure 5.
k
dk
La quantit
dk
xk + uk 6
k . uk
(suppose connue).
xk N
avec
x1 = 2
est nombre
xk+1 = xk dk + uk ,
4uk + 3 + xk+1
xk+1 + dk 6).
uk 6= 0
et
xk+1
sinon.
W.
transport rapporte
ck .
Le
k ime
conteneur pse
wk
et son
W =6
et
Conteneurs
Bnce
ck
wk 5 3
suivant, W = 13 et
Poids
2
avec la possibilit de prendre autant de
ck
wk
Bnce
12
25
50
Poids
5,5
6,5
chine neuve, dont elle a besoin pour assurer son bon fonctionnement pour les cinq annes venir.
Une telle machine a une dure de vie de trois ans. A la n de chaque anne, l'entreprise peut
37
dcider de vendre sa machine et d'en racheter une neuve pour 100 000. Le bnce annuel
assur par la machine est not
quantits dpendent de l'ge
bk ,
Age
k
bk
ck
pk
ck
pk .
Ces
80 000
60 000
30 000
10 000
14 000
22 000
50 000
24 000
10 000
Une
entreprise dispose d'un budget de 500 000 pour l'amlioration de ses usines pendant l'anne
venir. L'entreprise possde trois sites de production dont les bnces annuels esprs, en
fonction de la somme investie pour leur amlioration, sont donnes dans le tableau suivant.
Montants investis
(en centaines de milliers d'euros)
Sites
Bnces annuels
1
5,5
0,5
2,5
6,5
5,5
6,5
7,5
5 mois. Pour chaque mois, elle a besoin des nombres suivants d'intrimaires en plus de ses salaris.
Mois
Nombre d'intrimaires
10
11
et veut terminer sa tourne au plus tt. Le camion n'a pas retourner son point de dpart. De
plus, on suppose que la livraison en chaque point se fait de manire instantane, et que le temps
pour aller de
xi
xj
est proportionnel la distance les sparant. Montrer que l'on peut trouver
la tourne optimale en
O(n2 )
rsultat de Tsitsiklis).
Un
croissante de
{1, 2, . . . , n0 }
dans
{1, 2, . . . , n}
telle que
plus long. Montrer que c'est un problme de type programmation dynamique, et qu'il peut se
rsoudre en
O(n1 n2 ),
n1
et
n2
w1
et de
w2 .
3.4.10. Dplacement de wagonnet dans un mine souterraine avec contrainte d'orientation. Les mines souterraines sont souvent dotes d'un rseau ferr souterrain sur lequel
circulent des wagonnets. Ces derniers servent essentiellement vacuer la roche sans valeur extraite lors des forages. Un wagonnet rcupre la roche dans sa benne en un point d'extraction
et se dplace le long du rseau, jusqu' atteindre un point d'vacuation. Un wagonnet peut se
dplacer en avant ou en arrire, mais la benne se trouve l'avant. Cela signie que lorsque le
wagonnet arrive en un point d'extraction ou un point d'vacuation, il faut imprativement qu'il
arrive en marche avant, les demi-tours tant impossibles. L'objectif de ce problme est de proposer une mthode qui trouve les trajets les plus courts satisfaisant cette contrainte additionnelle.
On se limite au cas un seul wagonnet (dans le problme rel, la question de la congestion
induite par les autres wagonnets se pose galement).
La Figure 6 reprsente un tel rseau souterrain. Un wagonnet ne peut suivre que des trajectoires
C1
ABG
est impossible car l'orientation du wagonnet changerait brusquement en
B.
En revanche, l'en-
chanement
ABCDEF G
est possible.
Concernant l'orientation du wagonnet, l'enchanement
H I J,
galement possible, fait changer l'orientation du wagonnet : s'il se dplaait en marche avant en
H,
J.
1. Est-il possible pour le rseau de la Figure 6 de passer de n'importe quel point de rseau
n'importe quel autre ? Peut-on de plus le faire avec les orientations du wagonnet au dpart et
l'arrive imposes ? Justier brivement vos rponses.
2. Considrons le graphe dont les sommets sont les tronons, et les artes les enchanements
possibles entre les tronons. La construction est explicite sur la Figure 8. Oublions momentanment l'orientation. Quitte modier un peu le graphe, expliquer comment utiliser ce graphe
pour trouver le plus court trajet entre deux points particuliers du rseau.
3. Montrer que, en introduisant une copie de ce graphe et au prix de quelques transformations,
on peut de plus trouver le plus court trajet entre deux points avec les orientations du wagonnets
au dpart et l'arrive imposes.
39
Figure 6.
E
F
G
C
A
B
Figure 7.
f
f
Figure 8.
R+ .
40
w:C
41
CHAPITRE 4
PROGRAMMATION LINAIRE
nelle)
Min
(5)
s.c.
x, c Rn , b Rm
et o
est une
mn
inquation-
cT x
Ax b,
matrice relle.
Exemple.
(1) .
Supposons que l'on dispose d'une grande surface cultivable sur laquelle il est possible de faire
pousser des navets ou des courgettes. Le cot des semences est considr comme ngligeable. 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 synthtis dans le tableau suivant.
Engrais X
Courgettes
Navets
l.m2
2
1 l.m2
Engrais Y
Anti-parasite AP
l.m2
1
2 l.m2
0 l.m2
1 l.m2
Quel est le gain maximum qui peut tre fait compte tenu des ressources disponibles ?
On modlise ce problme comme un programme linaire.
x : surface
y : surface
Max 4x + 5y
Variables de dcision :
Fonction objectif :
1. Source : N. Brauner.
de courgettes.
de navets.
Contraintes
2x + y 8
x + 2y 7
y3
x 0 et y 0.
(ressources d'engrais A)
(ressources d'engrais B)
(ressources d'anti-parasite AB)
4x + 5y
2x + y 8
x + 2y 7
y3
x 0, y 0
Ce programme est bien un programme linaire comme dni par l'quation (5), avec
c=
4
5
,
b=
8
7
3
0
0
A=
2
1
1
2
0
1
1 0
0 1
Comme nous l'avons dj not lors du premier cours, le fait qu'il y ait Max dans notre problme
au lieu d'un Min comme dans l'quation (5) ne pose pas de problme : maximiser une quantit
revient minimiser son oppos.
Comme on n'a que deux variables, on peut procder une reprsentation graphique (voir
Figure 1).
Problme de production.
n types
m types de ressources. Elle possde bi units de la ressource
i pour i = 1, . . . , m. La production d'une unit du bien j entrane un bnce gal cj , pour
j = 1, . . . , n. Pour produire une unit du bien j , elle a besoin de aij units de chaque ressource
i. Maximiser le prot revient alors rsoudre le programme linaire suivant.
Pn
cj xj
Max
Pj=1
n
(6)
s.c.
j=1 aij xj bi i = 1, . . . , m
xj 0,
j = 1, . . . , n.
On considre une entreprise qui produit des biens de
La variable
xj
produites.
C'est un exemple classique et trs frquent de la programmation linaire. L'aspect allocation optimale des ressources de la RO est particulirement bien illustr par le problme de
production.
Dans l'exemple des navets et des courgettes, nous avons pu rsoudre le problme assez facilement car il n'y avait que 2 variables, et donc une reprsentation graphique tait possible. Mais la
plupart des problmes rels le nombre de variables et le nombre de contraintes peuvent dpasser
le millier, et ni l'intuition, ni le dessin peuvent alors nous tirer d'aaire. Heureusement, depuis
la n des annes 40, de nombreux chercheurs ont travaill sur la programmation linaire, et c'est
maintenant un problme qui est bien rsolu tant sur le plan pratique que sur le plan thorique.
Plan pratique :
points intrieurs.
du simplexe
et l'algorithme
des
du simplexe que l'algorithme des points intrieurs existent sous de nombreuses variantes.
44
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 1.
Plan thorique :
P.
utilisent une criture du programme linaire dirente de celle de l'quation (5). Ils utilisent la
forme standard
(7)
s.c.
Comme d'habitude,
cT x
Ax = b
x 0.
est le vecteur
45
0,
avec
mn
composantes.
donne,
c Rn ,
forme canonique
qui
s.c.
cT x
Ax b
x 0.
Ces trois formes sont quivalentes : partir d'une solution ralisable d'un programme sous
l'une des formes, on peut aisment construire une solution ralisable pour les deux autres formes,
donnant une mme valeur pour la fonction objectif.
A0 :=
programme
A
A
b0 :=
b
b
c0 := c.
Le
c Tx
A0 x b 0
x0
Min
s.c.
A0 := A Im , b0 = b et c0 := (c, 0).
variables d'cart y et considrer le programme
Min
s.c.
cT x
Ax + y = b
x, y 0.
Pour
A
b
0
0
passer de la forme standard la forme inquationnelle, on pose A := A , b := b ,
In
0
0
c := c. Le programme
0T
Min c x
s.c.
A0 x b0 ,
est alors clairement quivalent au programme (7).
La transformation rciproque est un peu plus subtile. On a alors le programme linaire sous
forme standard suivant :
Min
(9)
s.c.
avec
A0 :=
A A Im
b0 := b
et
c0T x0
A0 x0 = b0
x0 0,
c0 := (c, c, 0).
Rm de la manire suivante
yi := bi (Ax)i
pour
46
j = 1, . . . , m
u, v Rn
et
et
uj :=
xj
0
si
xj 0
et
sinon,
vj :=
xj
0
si
xj 0
sinon,
pour
j = 1, . . . , n.
4.2.2. Prliminaires.
A
indpendantes. En eet, on peut tester l'existence d'une solution ralisable en rsolvant l'qua-
Ax = b (par des pivots de Gauss par exemple). S'il y a une solution ralisable et si les
lignes de A ne sont pas linairement indpendantes, alors forcment l'quation correspondante
tion
Hypothse : Nos programmes linaires sous forme standard seront tels que A est de plein rang.
4.2.3. Solutions basiques ralisables.
de plein rang. Pour introduire la notion de solution basique, nous introduisons la notation
B {1, 2, . . . , n},
lments de B .
on note
AB
la sous-matrice de
rduite aux
Par exemple, si
1 2 0 3 3 1
A = 0 8 9 3 4 4 ,
5 6 0 7 1 1
et si
B = {1, 4, 5}
alors
1 3 3
AB = 0 3 4 .
5 7 1
et
Ax = b
B = {1, 4, 5},
sous la forme
AB xB + AN xN = b,
(10)
o
x = (5, 4, 5, 1, 1, 2)
xB = (5, 1, 1).
est le complmentaire de
Une partie
Dans ce cas,
est inversible.
l'criture (10)
en
1
xB + A1
B AN xN = AB b.
La solution
du systme
Ax = b
obtenue en posant
B := A1
x
B b
et
N := 0
x
est une
solution
basique. Si cette solution basique est ralisable (par rapport au programme linaire (7)), i.e. si
est une solution basique ralisable, et que B est une base ralisable.
A1
B b 0, alors on dit que x
On a alors le thorme important suivant qui constitue la base de l'algorithme du simplexe.
Thorme 4.2.1.
Alors
47
si l'ensemble des solutions ralisables est non-vide et si la fonction objectif est borne infrieurement sur cet ensemble, alors il existe une solution optimale.
s'il existe une solution optimale, alors il existe une solution optimale qui soit basique ralisable.
Ce thorme conduit un algorithme naf pour rsoudre un programme linaire : comme il
n
m ), on essaye chaque base l'une aprs l'autre et on
T
garde celle ralisable qui fournit la plus petite valeur pour c x. Il faudrait encore vrier que le
n'y a qu'un nombre ni de bases (au plus
fonction objectif est borne infrieurement, mais dans tous les cas, un tel algorithme n'a aucun
intrt pratique. En eet, le nombre d'tapes est exponentiel
(2) .
L'algorithme du simplexe va galement numrer des bases ralisables, mais dans un ordre
intelligent, ce qui va rduire considrablement (en gnral) le nombre de bases ralisables
valuer. Pour dcrire cet ordre (voir Section 4.3.1), on a besoin de la notion de
est une base voisine de la base
B0 \ B
base voisine. B 0
(et puisque les bases ont toute mme cardinalit, elle est galement telle que
qu'un lment).
B \ B0
ne contient
Il se peut aussi que l'ensemble des solutions ralisables soit non-vide, mais que la fonction
objectif ne soit pas borne infrieurement sur cet ensemble. Dans ce cas, on a un
rayon inni.
paramtre
de ce rayon,
4.2.4. Polydres.
appel
rayon inni.
La variable
est le
un peu comme on l'a fait dans la rsolution de l'exemple introductif des navets et des courgettes.
Les contraintes
Ax = b
et
x0
polydre,
n
de R obtenue comme intersection d'un nombre ni de demi-espaces ferms dlimits par des
hyperplans.
On vrie facilement qu'un polydre est
et
d'un polydre
P,
convexe,
points extrmes
ou
ou les
piques du polydre (voir Figure 2). Pour viter la confusion avec les sommets des graphes, nous
utiliserons plutt l'appellation points extrmes dans ce cours. On dnit mathmatiquement
un point extrme de la manire suivante.
on a l'implication
(le
segment
[x, y]
vP
contient
v) (v = x
ou
si pour tout
x, y P ,
v = y).
v.
En ralit, comme le montre le thorme suivant, les points extrmes et les solutions basiques
ralisables recouvrent le mme concept.
n
m
' 4m .
48
(7)
(P
Figure 2.
Un polydre.
4x + 5y = 22
(7).
On peut voir une illustration sur la Figure 3, qui montre la solution optimale au problme
des navets et des courgettes du dbut du chapitre.
49
4.3. Algorithmes
Il y a trois (familles d') algorithmes rsolvant les programmes linaires : le
ellipsodes
et les
points intrieurs.
simplexe,
les
Nous allons dcrire dans ces grandes lignes l'algorithme du simplexe et trs brivement l'algorithme des points intrieurs. Notre objectif est de permettre d'en comprendre les principes et
certaines de leurs proprits. Rappelons que lorsqu'un problme est dcrit comme un programme
linaire, il est inutile de programmer un algorithme pour le rsoudre : de nombreux logiciels,
dont certains libres, le font dj avec d'excellentes performances. Mme EXCEL dispose d'une
implmentation 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 linaire et de ces algorithmes est celui de
Matouek et Grtner [
de Chvtal [ ]. Sur l'algorithme des ellipsodes, le livre de Grtchel, Lovsz et Schrijver est une
Sur le plan pratique, l'algorithme des ellipsodes n'a pas encore fait ses preuves, ce qui explique
qu'il ne soit pas dcrit dans ce cours. Son intrt est (pour le moment ?) thorique et historique
puisqu'il constitue le premier algorithme polynomial propos pour la programmation linaire
(en 1979, par Khachyan). Avant 1979, la question, alors ouverte, de savoir s'il tait possible de
rsoudre la programmation linaire en temps polynomial passionnait beaucoup de chercheurs.
4.3.1. Le simplexe.
en base ralisable en amliorant chaque fois la valeur du critre. Comme le nombre de bases
est ni, on obtient l'optimum ou la preuve que le programme est non born en un nombre ni
d'tapes.
On suppose que l'on connat au dpart une base ralisable
B.
L'algorithme du simplexe
Min
(11)
s.c.
T 1
cTB A1
B b + c N c B AB AN x N
1
xB + A1
B AN xN = AB b
x 0.
Il faut bien noter que ce programme et le programme (7) sont compltement quivalents.
L'avantage de cette forme, c'est qu'on peut directement lire la valeur de la solution basique
cTB A1
B b de la fonction objectif. En eet, la
1
B = AB b et x
N = 0.
solution basique ralisable associe B est x
0
Ensuite, l'algorithme cherche une base ralisable voisine B qui amliore le critre (c'est l'op0
ration de pivot). Il est en eet assez simple de construire une telle base B partir de B ,
1
T 1
simplement la lecture des entres de cN cB AB AN et de AB AN . On slectionne d'abord
0
l'lment j
/ B qui va entrer dans B (la variable entrante xj ), la lecture des coecients de
1
T
cN cB AB AN . Ensuite, la lecture des coecients de la colonne correspondante de A1
B AN ,
on trouve l'lment i qui va quitter B (la variable sortante xi ).
Variable entrante : Tout coecient ngatif de cTN cTB A1
B AN peut faire oce de variable
ralisable associe
entrante.
Variable sortante :
soit
p :=
1
Soit q la colonne de AB AN correspondant la variable entrante et
1
AB b. On regarde les coecients strictement positifs de q et parmi ceux-l, on
xi
telle que
pi /qi
50
s.c.
1
1
T
T
cTB 0 AB
0 b + cN 0 cB 0 AB 0 AN 0 xN 0
1
0
0
xB 0 + A1
B 0 AN xN = AB 0 b
x 0.
pour laquelle on est nouveau capable de lire la valeur du critre pour la solution basique
ralisable associe
et
B0
(c'est
cTB 0 A1
B 0 b)
B0
et la solution basique ralisable elle-mme (x
1
= AB
0b
N 0 = 0).
x
Et on recommence.
L'optimalit est atteinte quand tous les coecients de
xN 0 ,
0
cTN 0 cTB 0 A1
B 0 AN
sont
0.
En eet,
augmenter.
De deux choses l'une, soit on termine sur une base optimale, soit la lecture des coecients,
on voit que le programme est non borne (i.e
toutes les composantes de la colonne
B0
x
et de direction
q.
On a suppos que l'on disposait d'une base ralisable de dpart. C'est en eet souvent le
cas. Par exemple, si le programme est sous forme canonique et si
b 0,
d'cart fait apparatre une sous-matrice identit, voir Section 4.2.1, dont les colonnes sont une
base ralisable naturelle de dpart. Sinon, on dispose de techniques standard pour tester la
ralisabilit du programme et trouver une base ralisable, voir Exercice 4.6.5.
Interprtation gomtrique : L'algorithme du simplexe s'interprte facilement gomtriquement.
En eet, deux bases ralisables voisines fournissent des solutions basiques ralisables qui sont des
points extrmes confondus ou voisins (au sens des artes du polydre) du polydre des solutions
ralisables. L'opration de pivot consiste glisser le long d'une arte du polydre
c.
O(m3 )
ce qui est tout fait raisonnable. Sur des instance relles, 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 rgle de pivot c'est--dire une faon de choisir la variable entrante
lorsque le choix est possible conduisant un comportement polynomial est une (importante)
question ouverte.
points intrieurs cherche viter le bord du polydre et rester le plus possible l'intrieur.
C'est seulement la dernire tape que l'algorithme atteint le bord, prcisment sur une solution
optimale.
3. ou rester sur le mme points extrme ; un pivot ne parvient pas toujours amliorer directement la valeur
du critre.
51
f (x) := cT x
n
X
log xi
i=1
f (x)
Ax = b
x > 0,
Min
(13)
x>0
s.c.
xi > 0
signie que
pour
i = 1, . . . , n.
vers
0,
et de chercher la solution
x ()
tend
alors vers l'optimum du programme (7) ( quelques conditions techniques prs). La recherche
de la solution optimale
x ()
O(n3 L)
est le nombre maximum de bits ncessaires pour coder un coecient du programme, ce qui en
fait bien un algorithme polynomial. Le nombre d'itrations (nombre de
O( nL)
4.4. Dualit
4.4.1. Dualit faible, dualit forte.
la transformation, les variables du primal deviennent les contraintes du dual et les contraintes
du primal deviennent les variables du dual.
Considrons par exemple, le programme linaire suivant, sous forme standard :
Min
(14)
s.c.
cT x
Ax = b
x 0.
(15)
s.c.
bT y
AT y c.
yi
A,
multiplie la
ime
A,
pour
i = 1, . . . , m,
et que
Nous expliquons maintenant une preuve de l'ingalit de dualit faible, alternative celle
prsente en Section 2.3.5.
52
y.
du dual. Multiplions
On obtient
y T Ax = y T b.
En utilisant les contraintes du dual et le fait que les composantes de
cT x
y T b ou plus lisiblement
cT x bT y.
On retrouve bien la
dualit faible.
en gnral, pour la programmation linaire, les valeurs optimales des programmes primal et dual concident. Plus prcisment :
En ralit, on a beaucoup plus :
Thorme 4.4.1
s.c.
cT x
Ax = b
x0
(P)
et
Max
s.c.
bT y
AT y c,
(D)
2.
3.
4.
(P) et (D) sont tous deux ralisables. 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)
(D).
La preuve est omise, mais ce thorme peut se prouver soit en utilisant un lemme classique en
gomtrie le lemme de Farkas soit en utilisant l'criture de la base optimale dans l'algorithme
du simplexe (voir Exercice 4.6.4).
53
x1 , x2 , . . . , xn
A
b
T
Min c x
y1 , y2 , . . . , ym
AT
c
T
Max b y
yi 0
yi 0
yi R
Variables
Matrice
Membre de droite
Fonction objectif
ime
contrainte a
Contraintes
xj 0
xj 0
xj R
j me
contrainte a
Proposition 4.4.2.
une entreprise E :
Max
s.c.
Pn
cj xj
Pj=1
n
j=1 aij xj bi i = 1, . . . , m
xj 0
j = 1, . . . , n.
Soit une rme F qui veut racheter les ressources de l'entreprise E. A quels prix doit-elle le
faire pour tout racheter au cot minimum ?
Pm
i=1 aij yi
j , cela garantit que E a intrt vendre les
ressources ncessaire pour produire une unit de j plutt que de la produire. D'o le programme
On note
cj
yi
pour tout
le prix de la ressource
j = 1, . . . , n.
i. F
yi
de manire ce que
Pm
i=1 bi yi
Pm
i=1 aij yi cj
yi 0
j = 1, . . . , n
i = 1, . . . , m.
appelle un
maximiser.
Ce qu'on cherche en thorie des jeux, ce sont les
des joueurs n'a intrt changer de choix. Ici, lorsque le choix est restreint au choix d'une ligne
et d'une colonne, on parle d'un quilibre en
pures est un couple
(j, i)
stratgies pures.
tel que
aj 0 i aji0 , pour
toute ligne
j0
et toute colonne
i0 .
54
En revanche, comme l'avait remarqu von Neumann, si les joueurs choisissent des distributions
de gain. Notons
4k
T Ax0
y 0T A
xy
pour tout
x0 4n
et
y 0 4m .
Le thorme suivant, d von Neumann, assure l'existence d'un quilibre en stratgies mixtes
pour les jeux matriciels somme nulle.
Thorme 4.5.1.
stratgies mixtes.
Dmonstration.
eet, ajouter une mme constante sur chaque entre de la matrice ne change rien au jeu.
Considrons le programme linaire
Pn
i=1 xi
Ax 1
x 0.
Max
(16)
s.c.
Pm
j=1 yj
T
y A 1T
Min
(17)
s.c.
y 0.
x=0
susament grand est solution ralisable. D'aprs le thorme 4.4.1, il existe x solution optimale
P
Pm Pn
xi = j=1 yj . Soit w = m
du primal et y solution optimale du dual, telle que
i=1 xi =
i=1
Pn
:= w1 x et y
:= w1 y satisfont les relations demandes.
j=1 yj . Les solutions x
On peut par ailleurs dmontrer facilement que, mme s'il y a plusieurs quilibres de Nash
en stratgies mixtes, la quantit
l'appelle
valeur
y T Ax
i.e.
1
w dans la preuve ci-dessus ne change pas. On
du jeu.
4.6. Exercices
4.6.1. Production de boissons.
1, 55, 3, 05
et
4, 80
20
un temps d'embouteillage.
XXX
YYY
ZZZ
fabrication
mlange
5,5
7,5
embouteillage
3,5
55
le prot.
Une
ranerie doit fournir chaque jour deux qualits A et B d'essence partir de constituants 1, 2 et
3. On note
Qmax
Qmax
cot unitaire
3000
2000
4000
essence
spcication
30%
40%
50%
50%
10%
de 1
5,5
de 2
de 3
de 1
4,5
de 2
Donner un modle qui permet de maximiser la recette, sachant que toute la production pourra
tre coule.
Ax = b
x0
(18)
o
b Rm
et
A est une mn matrice relle. L'objectif de l'exercice est de proposer une mthode
pour tester si un tel systme a une solution ralisable, et s'il en existe, en trouver une.
1. Montrer qu'on peut supposer que
b 0.
Pm
i=1 yi
Min
s.c.
(19)
Ax + y = b
x0
y0
2. Montrer que le systme (18) a une solution ralisable si et seulement si le programme (19) a
une valeur optimale
= 0.
Par consquent, l'algorithme du simplexe est une mthode pour rsoudre un systme de la
forme du systme (18). En eet, le programme (19) a une solution basique ralisable facile
identier :
y = b
et
x = 0.
56
programme (19) partir de cette base initiale. Noter que s'il y a une solution au systme (18),
cette mthode lui trouve une solution basique ralisable. C'est donc galement une mthode
pour trouver une premire solution ralisable un programme linaire pour lequel il n'y en a
pas d'vidente.
3. Rciproquement, montrer avec la thorie de la dualit que si on a une mthode pour trouver
une solution ralisable de n'importe quel systme d'quations et d'inquations linaires, alors on
peut utiliser cette mthode pour rsoudre les programmes linaires.
Soit
des points
dans le plan. On cherche la meilleure droite approximante pour la norme sup, i.e. la droite
du plan d'quation
ax + b = y
telle que
supi=1,...,n |axi + b yi |
trer que cela revient rsoudre un programme linaire. Mme question en cherchant minimiser
Pn
i=1 |axi
+ b yi | .
Demande
vitamine A
vitamine C
19
35
30
60
50
27
22
Prix par
kg
s.c.
cT x
Ax = b
xj N j = 1, . . . , n
57
CHAPITRE 5
FLOTS ET COUPES
La notion de ot dans un graphe est naturelle : tant donn un rseau de transport (train,
tuyau, cables lectriques), avec des capacits sur les arcs, quelle quantit de biens peut-on faire
transiter au maximum ? Ou alors, en supposant qu' chaque arc est attach un cot unitaire,
quel cot 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 xs. Les applications des coupes sont nombreuses
en recherche oprationnelle bien st, mais galement en dehors de la recherche oprationnelle :
positionnement de postes d'enqutes, robustesse de rseaux, imagerie, etc.
de dfnir ce qu'est un ot, il nous faut d'abord xer un rseau. Soit donc un rseau modlis par
un graphe orient
a (v)
a + (v)
est respecte.
s-t coupe, il est intuitivement clair qu'un ot aura une valeur infrieure sa
P
+
capacit d'une s-t coupe (X) est dnie par
a + (X) u(a). Le lemme suivant
capacit,
o la
Lemme 5.1.1.
Soit + (X) une s-t coupe et soit f un s-t ot quelconque. Alors
X
X
value(f ) =
f (a)
f (a).
a (X)
a + (X)
En particulier,
(21)
value(f )
u(a).
a + (X)
s -t
chemins lmentaires et
Pour tout
B A,
on note
la fonction qui
aA
renvoie
si
aB
et
sinon.
Soit f un s-t ot, P l'ensemble des s-t chemins lmentaires et C l'ensemble des circuits lmentaires. Il existe alors des coecients rels positifs (P )P P et (C )CC
tels que
X
X
f=
P P +
C C .
Proposition 5.1.2.
P P
CC
De plus,
value(f ) =
P .
P P
La preuve n'est pas triviale, mais constitue tout de mme un exercice raisonnable.
donn un rseau avec des capacits. Informellement, tant donn un rseau avec des capacits
sur des arcs, la question est de savoir quelle quantit maximum de matire on peut faire passer
de la source
la destination
t.
= (V, A),
et
et des capacits
u : A R+ .
ad hoc
s -t
s -t
Exercice 5.3.2.
et
t,
et des capacits
u : A R+ .
5.1.2.2. Graphe rsiduel et chemins f -augmentants. Les algorithmes ad hoc utilisent souvent
les graphes rsiduels et les chemins augmentants, que nous dnissons maintenant. Informellement, le graphe rsiduel est le graphe qui indique les arcs o l'on peut augmenter ou diminuer
la quantit de ot sans violer la loi de conservation et les bornes de capacits (voir exemple
Figure 1).
Pour un arc
a = (u, v),
on note
a1 := (v, u).
On dnit
ot. On dnit
Af := {a : a A
et
A1 := {a1 : a A}.
et
Soit
un
st
graphe rsiduel est le graphe Df := (V, Af ). Pour a Af , on associe une capacit rsiduelle
uf (a) := u(a) f (a) si a A et uf (a) := f (a) si a1 A. Tout s-t chemin dans Df est appel
chemin f -augmentant.
Le
Ensuite on rpte
Df . S'il n'y
en a pas, alors f est optimal. Sinon, on calcule le plus grand possible
qui permette d' augmenter f le long de P et on augmente f de
la quantit .
Trouver un chemin
Le calcul de
se formalise par
la manire suivante : si
f (a) := f (a) + ;
f augmentant P
:= minaP uf (a).
Augmenter
le long de
se fait de
alors on pose
sinon (i.e.
f -augmentant
ayant le moins d'arcs possible, ce qui se fait par un algorithme de plus court chemin avec des
cots unitaires sur les arcs
(1) .
D'o
Thorme 5.1.3.
Remarque.
tous est celui de Goldberg et Tarjan : ils ont montr qu'il tait possible de trouver un ot
maximum en
dessus est la clbre proprit de max otmin coupe. En eet, lorsque l'algorithme se termine,
on a obtenu un ot maximum. En notant
est l'absence de chemin
f -augmentant
1. Dans ce cas particulier, cot = 1, il n'est pas ncessaire d'appliquer l'algorithme de Dijkstra du Chapitre 3.
Une simple recherche en largeur d'abord donne la solution.
Les nombres non-entoures sont les capacites; les nombres entoures forment le flot.
Graphe residuel:
6
v1
v2
10
6
1
5
6
5
4
3
v2
v1
3
1
2
5
v4
v4
v3
5
Figure 1.
Le graphe rsiduel.
61
5
v3
t
5
s dans Df ,
cela signie que pour les arcs a quittant X (formellement a
f (a) = u(a) et que
P
dans
Df .
Posant
+ (X)), on a
a + (X)
On obtient donc
Thorme 5.1.4.
minimum.
La valeur d'un s-t ot maximum est gale la capacit d'une s-t coupe
s -t
coupe minimum
2
en O(nm ). En eet, aprs 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.
Thorme 5.1.5.
Thorme 5.1.6. Si toutes les capacits sont entires, alors il existe un s-t ot maximum
entier, et l'algorithme d'Edmonds et Karp le trouve.
Dire que le ot
f (a)
a A.
En fait, on a aussi
et
entiers
Remarque. On peut dnir 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 ctive s, un puits ctif 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 innis.
Cette astuce consistant ajouter une source et un puits ctifs est utile dans de nombreuses
situations.
Remarque. Dans le cas non-orient, on appelle s-t coupe un ensemble d'artes de la forme
(X), avec s X et t
/ X . Trouver une s-t coupe de capacit minimum se ramne simplement
remplacer chaque arte par deux arcs opposs.
Remarque.
et
t,
et des capacits
u : A R+ .
Tche : Trouver un sous-ensemble B d'arcs de capacit minimum tel que pour tout s-t chemin
P,
on a
P B 6= .
s-t
s-t
coupe
est une solution ralisable pour le problme de l'ensemble d'arcs dconnectant minimum. Inversement, s'il existe une solution ralisable
minimum, alors l'ensemble
62
depuis
s sans
utiliser
d'arcs de
+ (X) B .
diminuer les missions de CO2 par exemple), on souhaite eectuer des contrles de poids lourds
partant d'une rgion
ct .
R.
t cote
Les contrles sont eectus sur des tronons d'autoroute. Faire un contrle sur le tronon
Le problme consiste trouver le sous-ensemble de tronons sur lesquels les contrles vont
Avec les remarques ci-dessus, on peut voir que ce problme se modlise comme un problme
de
s -t
coupe minimum.
tches accomplir dont on connat les dures d'excution, et que l'on dispose d'une ressource
de main d'uvre dont on connat les comptences. Les tches sont supposes telles que les
employs peuvent y travailler en parallle. On souhaite minimiser le temps ncessaire pour
raliser l'ensemble des tches.
Tche
R+ ; m
i.
Si
Par consquent pour rsoudre le problme de l'aectation de tches (trouver une solution
Pn
i=1 ti si on pose
T :=
Pn
D.
Pn
T :=
2
Pn
et
T 0 :=
Pn
i=1 ti . On rpte
i=1 ti
63
T :=
T 0 := T 0 .
La solution optimale
est telle
T T (x ) T 0 .
T + T0
2
et on laisse
T0 T
est plus
On a rsolu un problme d'optimisation par une recherche binaire, chaque tape tant un
problme de dcision.
Cette faon de procder est trs ecace en pratique, plus que l'autre solution consistant
voir le problme de l'aectation de tches comme un programme linaire.
On peut se demander si, dans le cas o les ti sont entiers, on a ncessairement alors une solution
optimale entire. L'auteur de ce polycopi ne sait pas. L'intrt pourrait tre de montrer que la
recherche binaire termine en un nombre ni d'tapes.
plus, pour des commodits de modlisation, on va autoriser plusieurs sources et plusieurs puits.
a A, et des
b-ot si pour tout
tout
nombres
arc
conservation
X
a + (v)
f (a)
f (a) = b(v)
a (v)
est respecte.
b(v) > 0 sont appels sources et les sommets v tels que b(v) < 0 sont
b(v) est l'ore ; pour un puits, b(v) est la demande.
Dans le cas particulier o tous les b(v) sont nuls, on parle de circulation.
On suppose que l'on a une fonction de cot c : A R.
On peut alors se demander, parmi tous les b-ots, lequel est de plus petit cot, o le cot
d'un b-ot f est dni par
X
c(a)f (a).
Les sommets
appels
puits.
tels que
aA
Les applications des ots de cot minimum sont innombrables. Nous verrons ce que cela peut
apporter au problme d'aectation de trches vu prcdemment. Tout comme le problme de
ot maximum, le problme du
et peut donc tre rsolu avec ma mthode des points intrieurs (en temps polynomial donc) ou
par l'algorithme du simplexe.
En 1985, Goldberg et Tarjan [
13]
ecace pour rsoudre le problme ot de cot minimum. L'algorithme travaille encore sur le
graphe rsiduel, en dnissant
c(a1 ) := c(a)
Af := {a : a A
Le graphe rsiduel
Df
et
pour
aD
et
et
5.1.3.2. Algorithme de Goldberg et Tarjan. On commence par xer un b-ot (voir ci-dessous :
comment trouver un b-ot ralisable). Le cot moyen d'un circuit C est dni par
P
aC c(a)
,
|C|
64
C.
On repte
Reprer un circuit
pas, alors
f (a) := f (a) + ;
le long de
Df .
S'il n'y en a
et on augmente
de la
se formalise par
la manire suivante : si
:= minaC uf (a).
Augmenter
le long de
se fait de
alors on pose
sinon (i.e.
La dicult de cet algorithme est de trouver un circuit de cot moyen minimum dans le
graphe rsiduel
Df .
19]
Thorme 5.1.7.
qui
O(nm).
Comme pour le problme du ot maximum, si les capacits sont entires, il existe une solution
optimale entire, que l'on trouve sans plus de dicult.
Si toutes les capacits sont entires et tous les b(v) sont entiers, alors il
existe un b-ot entier de cot minimum, et l'algorithme de Goldberg et Tarjan le trouve.
Thorme 5.1.8.
Si l'on accepte d'avoir une complexit qui dpend de la taille des nombres de l'input (on
parle alors d'algorithme
faiblement polynomial),
est
5.1.3.3. Comment trouver un b-ot ralisable. Remarquons d'abord que le cas o `(a) = 0
pour tout a A est facile. En eet, en ajoutant une source ctive s, un puits ctif t, les arcs
(s, v) avec capacit b(v) pour les v tels que b(v) > 0 et les arcs (v, t) avec capacit b(v) pour
les v tels que b(v) < 0, l'existence d'un b-ot se resout par un algorithme de ot maximum, par
exemple avec l'algorithme d'Edmonds et Karp ci-dessus.
arc
f (a) =
f (a)
Posons
a + (v)
`(a) +
X
a + (v)
pour tout
v V,
a A.
pour tout
a (v)
a + (v)
f0
f 0 (a) =
satisfaisant
`(a) +
a (v)
f 0 (a)
pour tout
a (v)
pour tout
a A.
v V,
f (a)
a (v)
a + (v)
lequel est rsolu par un problme de ot maximum, comme indiqu au dbut de cette discussion.
c(u, v)
(u, v),
on
le rseau dont l'tablissement soit de cot minimum ? On suppose que l'on connat pour les
sources, l'ore et pour les destinations, la demande.
le Thorme 5.1.8, on peut trouver une solution entire ce problme, ce qui est commode si
chaque tronon ne peut avoir que des capacits unitaires.
Dans
le cas du problme de l'aectation des tches, mettre de cots sur les arcs dans la modlisation
par les ots permet de prendre en compte des considrations salariale.
Soit le problme
pour l'employ
Si
horaire cij
i;
un salaire
des tches.
R+
tels
i.e.
pour tous
P
maxj{1,...,m} i: jSi xij T . Minimiser le cot
P
la quantit C(x) :=
j{1,...,m},i{1,...,n} cij xij .
5.2. Multiots
Nous n'avons jusqu' maintenant envisag qu'un seul bien traversant le rseau. Dans de nombreuses applications (en particulier dans le transport), il y a plusieurs biens distincts qui utilisent
le mme rseau. On parle alors de multiots.
rR
66
s1
t2
t1
s2
Figure 2.
Dirents objectifs peuvent tre cherchs. On peut chercher maximiser la quantit totale
demande
d : R R+ et se demander si le rseau permet de la satisfaire, i.e. s'il existe un multiot f
tel que pour tout r on ait value(fr ) = d(r). On munit parfois les arcs de cots c : A R et
on cherche satisfaire la demande au moindre cot, i.e. que l'on cherche le multiot f tel que
P
P
value fr = d(r) pour tout r R avec aA c(a) rR fr (a) minimum.
de biens transitant dans le rseau, i.e. la quantit
Toutes ces questions peuvent tre rsolus en temps polynomial. En eet, elles se formulent
0, 1
comme coecients dans ses contraintes c'est le cas pour les multiots , alors il existe des
algorithmes plus ecaces que le simplexe ou les points intrieurs. Par exemple, Tardos a propos
23] qui est fortement polynomial, i.e. dont le nombre d'itrations ne dpend
tel un algorithme [
ou
d.
11]).
gnration de colonnes
facilement. La
1.
On peut voir que le seul ot possible n'est pas entier (on dit qu'il est
fractionnaire).
Ce dont il faut se souvenir, c'est que si un problme peut tre modlis comme un problme
de multiot, il peut tre bon de le souligner, et de chercher des mthodes qui exploitent cette
proprit.
5.3. Exercices
5.3.1. Valeur d'un s-t ot.
67
5.3.2. Formulation des problmes de ots maximum sous forme de programme linaire. Montrer que le problme de ot maximum s'crit comme un programme linaire.
Ecrire son dual. Quelle remarque pouvez-vous faire ?
et de
d'un rseau non-orient. On connat la position des subordonns modlise par un sous-ensemble
des sommets du rseau. On souhaite dtruire un nombre minimum de liens an d'empcher
citoyens,
clubs et
Pk
certains de ces reprsentants sont membre d'un parti politique... Un citoyen sigeant au conseil
ne peut que reprsenter qu'un seul club. Proposer un algorithme polynomial permettant de
dcider si ces contraintes peuvent tre satisfaites.
Soit D = (V, A) une graphe orient, et s et t deux sommets particuliers. Le nombre maximum de s-t chemins arc-disjoints est gale la cardinalit minimale d'un sous-ensemble d'arcs
intersectant tout s-t chemin.
i = 1, . . . , p, elle connat son lieu oi et son heure de dpart hi , la dure du vol ti et le lieu
di . De plus, le temps pour se rendre de dj oi est connu pour chaque couple (i, j).
d'arrive
est connu (frais, salaire, carburant). La compagnie souhaite maximiser son gain, sachant qu'elle
dispose de
avions.
68
p(i, j).
l'aroport
passagers
2, 3, . . . , n successivement. Le nombre de
j (avec i < j ) est d(i, j) et le prix de ce
seul bien.
priodes
yt = yt1 + xt dt ,
(22)
pour
t = 1, 2, . . . , T .
Sur la priode
p t 0.
t,
st 0
Application numrique :
t=
dt
st
pt
Pt
xxx
Indiquer le cot minimal de gestion de stock, ainsi que les niveaux de productions (en p.4 ,
des programmes linaires sont donns).
4. Montrer que ce problme peut galement se modliser comme un problme de
minimum. (Indication : introduire un sommet source
puits
wt
avec
b(wt ) = dt ;
avec
b(v) =
b-ot de cot
PT
vous d'indiquer les arcs, les cots sur les arcs, les capacits sur
oprationnelle est l'exploitation des mines ciel ouvert. Un problme important consiste
dterminer les
blocs
blocs numrots de
n.
L'extraction du bloc
rapporte la quantit
ci ;
tre positive ou ngative (en fonction de la quantit de minerai prsent dans le bloc).
Les blocs ne peuvent pas tre extraits dans n'importe quel ordre : pour chaque bloc
connat l'ensemble
Yi
i,
on
des blocs qu'il faut avoir extraits pour pouvoir extraire le bloc i. L'objectif
S.
de sommets est
ferm
si tout successeur
s -t
= (V , A)
en ajoutant un sommet source s et un sommet
D
puits t V . On note V
= {v V : cv 0} et V = {v V : cv < 0}. L'ensemble A 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 .
On construit un nouveau graphe
2. Quelles capacits
+
D
(X
{s})
3. Soit
soit une
XV
un ensemble ferm de
D.
X
a +
(X{s})
D
que
Montrez que
ua =
X
vV
cv
cv .
vX
70
CHAPITRE 6
L'objectif de ce cours est d'tudier un objet central de l'optimisation discrte et d'en voir
quelques applications parmi les plus importantes. Il s'agit des graphes bipartis.
6.1. L'objet
graphe biparti est un graphe dont l'ensemble des sommets peut tre partitionn en deux
parties X et Y telles que toute arte l'une de ces extrmits dans X et l'autre dans Y . Voir la
Un
Figure 1. On a la proposition suivante, trs utile, dont la dmonstration est laisse en exercice.
Proposition 6.1.1.
taille impaire.
(G)
et
dans
M,
Figure 1.
les artes
uv
v.
X vers Y , on
(v, t) pour v Y ;
de ot de cot minimum avec des cots opposs) : on oriente toutes les artes de
(s, v) pour v X et
b(s) = |X| = b(t) et b(v) = 0 ailleurs. Enn, les
capacits des arcs sont partout = + sauf sur les arcs (s, v) et (v, t) o elles sont gales 1, et
les cots sont partout nuls sauf sur les arcs de X Y o ils sont gaux aux poids w . C'est un
ajoute un sommet
et un sommet
(s, t),
t,
et on pose
problme de ot de cot maximum : en eet, tout ot entier induit un couplage de mme poids ;
et tout couplage induit un ot entier de mme cot.
Tout algorithme trouvant des ots entiers de cot optimal trouve donc la solution (en particulier celui vu au chapitre prcdent). En fait, il existe un algorithme plus ecace, appel
DM de la faon suivante :
Orienter chaque arte e de M de Y vers X , et dnir l(e) := w(e).
Orienter chaque arte e de E \M de X vers Y et dnir l(e) := w(e).
Soit XM (resp. YM ) les sommets de X (resp. Y ) qui ne sont pas couverts
par une arte de M . S'il y a un chemin de XM YM , en chercher un
plus court (pour la fonction l), que l'on note P . Remplacer le M courant
par M 4E(P ) (o E(P ) est l'ensemble des artes de P , et o B4C
reprsente les lments prsents dans exactement l'un des ensembles B
(1) ).
ou C
Crer le graphe orient
XM
YM
dans
DM . On peut
Un lecteur attentif remarquera qu'il faut calculer un plus court chemin dans
graphe orient avec des poids quelconques. Ce problme est
ici, on peut montrer que l'algorithme est tel que
DM
DM
qui est un
et que l'on peut donc calculer un tel plus court chemin avec la mthode Bellman-Ford vue au
Chapitre 3.
Avec quelque subtilit d'implmentation, l'algorithme hongrois peut tourner en
n log n)).
Thorme 6.2.1.
n log n)).
O(n(m +
72
dirence symtrique de B et de C .
Si on veut simplement trouver le couplage le plus grand (en nombre d'artes), on peut aller
encore plus vite.
maximale en O( nm).
Dans ce cas, on gardant la mme modlisation par un graphe orient (et en oubliant les cots),
on cherche le
s-t ot de valeur maximale, ce qui donne une complexit de O(nm2 ). Par une srie
d'astuces, non dtailles ici, et sans utiliser la modlisation par les ots, on arrive la complexit
donne dans le thorme ci-dessus.
G = (V, E)
et qu'on note
Thorme 6.2.3.
(G) (G)
rithme de Ford-Fulkerson permet par la mme construction que celle utilise dans la preuve de
calculer une telle couverture optimale. Cela dit, il existe des algorithmes plus rapides.
Soit
appelle
tout
N,
des poids
w : E R.
Il se rsout en temps polynomial par un algorithme de ot de cot minimum, avec une
construction similaire celle de la section prcdente. Noter que si on ne veut que maximiser la cardinalit, on peut utiliser un algorithme de ot maximum (plus rapide), toujours avec
la mme construction.
Exemple.
marchandises
mi,1 , . . . , mi,ai . Chaque marchandise est caractrise par une heure limite de tri tij ,
{1, . . . , ai }. Si la palette o se trouve la marchandise mij est trie avant l'heure tij , on
sinon, on perd di . On suppose que
on dispose de k personnes pour trier,
chaque personne met une heure pour trier une palette,
73
avec
j
ci ,
gagne
on dispose de
horaire.
est
parfait
M.
Problme de l'aectation
Donne : Un graphe G = (V, E) biparti avec des poids w : E R sur les artes.
Tche : Trouver un couplage parfait de poids minimal.
Ce problme apparat dans quantit de situations. Comme prcdemment, les sommets du
graphe biparti peuvent tre des employs d'une part et des tches eectuer de l'autre (on
suppose qu'il y a autant d'employs que de tches). Les poids peuvent modliser le cot de
ralisation de la tche par un employ donn. On veut raliser toutes les tches avec un cot
minimal, en supposant que tout employ peut raliser n'importe quelle tche.
Thorme 6.4.1.
n/2.
lles et
Chaque lle accepterait ventuellement de se marier avec certains garons, et elle a un ordre total
de prfrence sur ces garons. De mme, chaque garon accepterait ventuellement de se marier
avec certaines lles et a un ordre de prfrence total sur ces lles. On modlise cela de la manire
74
suivante. Les lles et les garons forment les sommets d'un graphe biparti
arte entre un sommet lle et un sommet garon si l'un et l'autre accepteraient ventuellement
de se marier ensemble. L'existence de l'ordre de prfrence pour chaque lle et chaque garon
v V.
G. Un couplage M est dit
stable si la condition suivante est satisfaite pour toute arte uv de G : si uv n'est pas dans M ,
alors il existe e (u) M avec uv u e ou il existe e (v) M avec uv v e. En d'autres
termes, si une lle u et un garon v ne sont pas maris ensemble alors que l'un et l'autre seraient
se traduit par l'existence d'un ordre total
sur
(v)
pour tout
prts ventuellement l'tre, c'est que l'un des deux est mari avec quelqu'un qu'il prfre.
C'est une notion tout fait naturelle de stabilit : un tel coulage stable ne conduira pas des
rarrangements locaux. Ce sont Gale et Shapley [ ] qui ont imagin ce concept en 1962 et ont
prouv le thorme suivant. Shapley a d'ailleurs obtenu le prix Nobel d'conomie en 2012 pour
ses travaux sur ce sujet. De nombreux domaines en ont en eet bnci : ces mariages stables
ont t appliqus aux aectations d'internes dans des services hospitaliers, aux attributions de
bourses, aux acceptations d'lves dans les coles prparatoires, etc.
Ce qui est remarquable, c'est que la preuve est simple, algorithmique et peut se raconter sous
la forme d'une histoire.
Dmonstration.
Tous les matins, chaque garon invite dner la lle qu'il prfre parmi
celles qui ne lui ont pas dj refus une invitation. Chaque lle qui a t invite dne le soir
avec le garon qu'elle prfre parmi ceux qui l'ont invite ce jour l, condition bien sr qu'elle
accepterait ventuellement de se marier avec lui. Tout garon qui a vu son invitation refuse par
une lle dcide de ne plus jamais l'inviter.
L'algorithme se poursuit tant qu'au moins une invitation change. Les couples qui ont dn
entre eux le dernier soir sont maris.
Pour se convaincre que cet algorithme fournit un couplage stable, il faut d'abord remarquer
que
toute lle qui est invite un soir dner est sre de dner le lendemain avec un garon qui lui
plaise au moins autant.
En eet, si une lle, disons Alice, est invite dner par un garon, disons Bob, c'est que Bob
prfre Alice toutes celles qui ne l'ont pas dja refus. Alice est donc sre d'tre rinvite le
lendemain par Bob, mais elle sera peut-tre aussi invite par de nouveaux garons qui viennent
d'essuyer des refus et pour qui elle est dsormais le meilleur choix restant. Peut-tre que Charlie,
l'un de ces nouveaux garons, lui plait plus que Bob, dans ce cas elle dnera avec Charlie, en
congdiant Bob. Dans tous les cas, Alice dne le lendemain avec un garon au moins aussi
plaisant.
Ensuite, on remarque que
l'algorithme se termine.
En eet, une invitation qui a t refuse ne sera jamais rpte. chaque tape prcdant la
n de l'algorithme, au moins une invitation est refuse. Le nombre d'tapes avant que la liste
75
N
O
E
S
Figure 2.
des invitations ne se stabilise est donc born par le nombre d'invitations possibles, i.e. par le
nombre de lles fois le nombre de garons.
Enn, lorsque l'algorithme se termine,
6.6. Exercices
6.6.1. Une caractrisation des graphes bipartis.
6.6.2. Thorme de Knig.
2. Chaque point indique une position possible pour un poste d'observation. On veut que chaque
poste d'observation ait la vue compltement dgage dans les 4 directions cardinales (nord, sud,
est, ouest) deux postes d'observation ouverts ne peuvent donc ni se trouver sur la mme ligne,
ni se trouver sur la mme colonne. On veut en ouvrir un nombre maximum. Proposer un nombre
maximum dans le cas particulier de la Figure 2. Prouver la qualit de votre solution. Proposer
la mthode gnrale (est-ce polynomial ?).
76
CHAPITRE 7
7.1. Introduction
Jusqu' prsent nous avons vu un certain nombre de problmes, certains
NP-durs, d'autres
polynomiaux. Pour les problmes polynomiaux, nous avons discut les algorithmes possibles
pour les rsoudre ; pour les autres, rien n'a t indiqu, ce qui pourrait laisser penser qu'on ne
sait pas les rsoudre. Bien entendu, c'est faux, et heureusement, car de nombreux (la plupart ?)
problmes industriels sont
NP-durs.
L'objet de ce chapitre est de prsenter quelques mthodes gnrales, indpendantes du problme, que l'on peut employer lorsqu'on est confront un problme d'optimisation
NP-dur,
Min
(23)
s.c.
f (x)
x X,
Un problme
NP-dur
est tel qu'il n'est pas possible (sauf si nalement il s'avrait que
P = NP) de trouver en temps polynomial, i.e. raisonnable, la solution exacte pour toute instance. On peut donc soit relcher la condition solution exacte et vouloir garder un temps
raisonnable d'excution, soit relcher la condition sur le temps et garder le dsir d'avoir une
solution exacte.
La premire option conduit aux
solutions qui sont proches de l'optimum. Ces algorithmes approchs sont des heuristiques ou des
mtaheuristiques. Une heuristique n'a de sens que pour un problme donn, c'est un algorithme
ad hoc pour lequel le bon sens assure son fonctionnement en gnral. 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 ecacits de manire exprimentales. Nous
verrons quelques exemples dans les chapitres suivants, mais il n'existe pas de schma gnral
qui permettent de driver de tels algorithmes. Une mtaheuristique est une mthodologie trs
gnrale pour concevoir un algorithme d'optimisation. Sa vocation est de pouvoir s'adapter un
grand nombre de problmes d'optimisation, plus ou moins indpendamment de leur structure. Ce
sera l'objet de la Section 7.3. Il est en gnral trs dicile de garantir
seront donns aux cours des sances suivantes. Un branch-and-bound suppose l'existence de
bonnes bornes sur la solution (borne infrieure si on minimise, borne suprieure si on maximise).
Dans un contexte industriel, un algorithme exact, dont le temps d'excution peut tre long,
sera plutt utilis pour des questions stratgiques. Une heuristique ou une mtaheuristique peut
avoir des temps d'excution trs courts et sera donc plutt utilise pour des questions tactiques
ou oprationnelles.
partie
sur
une collection
de parties de
X
x
.
telle que
contient un minimum de
f (x)
sur
Si
de
Y.
poser
x
:= y .
{y} : supprimer Y
de
Y ; si f (y) < f (
x),
Y en parties Y1 , Y2 , . . . , Ys ; supprimer Y
i = 1, . . . , s, si (Yi ) < f (
x), poser Y := Y {Yi }.
Sinon : partitionner
faire : pour
de
Y;
L'ide principale du branch-and-bound rside dans cette dernire tape : il ne sert rien de
Yi
conserver la partie
sur
Yi
si
(Yi ) f (
x).
En eet, comme
(Yi )
Y,
sera bonne. La
branchement,
Souvent, la structure du problme impose assez naturellement les faons de brancher. Enn, le
choix de la partie
dans
En profondeur d'abord
Yi
ajoute
Y.
On va
descendre trs vite dans l'arborescence. Cela peut tre utile par exemple si on n'a pas de
bonne solution ralisable.
En largeur d'abord : brancher toujours sur la partie Y telle que Y = argminY Y (Y ). C'est
intressant si est une bonne valuation par dfaut de f .
Nous allons maintenant voir deux exemples trs classiques de calcul de borne, et nous appliquerons ensuite l'algorithme sur un exemple trs simple, en guise d'illustration.
branch-and-bound est la programmation linaire en nombres entiers. Comme il va tre vu cidessous, la programmation linaire en nombres entiers est
78
NP-dicile.
Remarque importante.
programme linaire avec des variables continues, il est inutile de procder l'implmentation
d'un algorithme pour rsoudre ce problme : il existe dj de nombreux solveurs libres ou
commerciaux utilisant l'algorithme de simplexe ou l'algorithme des points intrieurs. La mme
remarque vaut galement en grande partie pour les programmes linaires en nombres entiers : la
plupart des solveurs comportent des branch-and-bound intgrs et trs performants, voir l'annexe
du polycopi. La partie informatique de la rsolution du problme consiste alors principalement
crire le problme dans un
langage de modlisation
GPL,...) que peut comprendre le solveur et appuyer sur le bouton pour obtenir la solution.
Implmenter son propre branch-and-bound pour un problme linaire en nombres entiers peut
cependant tre justi dans certains cas : par exemple, si le problme a une structure particulire
qui n'est pas exploite par ces solveurs, ou si le nombre de contraintes est exponentiel comme
pour le problme du voyageur de commerce, voir Chapitre 11.
s.c.
cT x
Ax b
x Zn .
avec les
wi
et
Pn
ci xi
Pi=1
n
i=1 wi xi W
xi {0, 1}
pour
NP-dur.
i = 1, . . . , n,
Noter que les algorithmes du simplexe, des points intrieurs ou des ellipsodes ne peuvent
absolument pas rsoudre les programmes linaires en nombres entiers, ils sont conus uniquement
pour les variables continues.
et notons
s.c.
vpl
ralisable de (25), on a
Exemple.
vplne vpl .
On considre le programme
Max
(26)
cx
Ax b
x Rn ,
s.c.
x1 + 52
4x1 + 2x2 3
2x1 + 8x2 39
x1 , x2 Z.
79
L'arborescence est donne Figure 1. Remarquer que par deux fois, on vite l'exploration d'une
sous-arborescence en utilisant la borne : une fois sur le noeud
x1 4, x2 3.
Considrons le problme
f (x)
xX
gi (x) = 0 i = 1, . . . , p
gi (x) 0 i = p + 1, . . . , p + q
Min
s.c.
(27)
f, g1 , . . . , gp+q
gi
Rn
dans
R,
gi
avec
:=
v
Si on note
(28)
(R+ )
L(x, ) := f (x) +
q
et
Rn .
On
Rp
p+q
X
i gi (x),
i=1
xX
x1 = 1, 5
x2 = 4, 5
v = 24
x1 2
x1 1
x1 = 1
x2 = 3, 5
x1 = 2
x2 = 4, 375
v = 18, 5
x2 4
on abandonne lexploration car v est moins bon
que le meilleur resultat entier courant.
v = 23, 875
x2 5
x1 = 3, 5
x2 = 4
irrealisable
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
Figure 1.
Un arbre de branch-and-bound.
80
irrealisable
G:
R {}
G() 7 inf xX L(x, ),
est la fonction duale. Elle est concave et ane par morceaux (car inmum de fonctions afnes). L'ide de la
relaxation lagrangienne
est d'utiliser
sup G()
La question est donc de savoir calculer cette quantit. Pour cela on peut utiliser des techniques
de l'optimisation non-direntiable, une mthode de sur-gradient par exemple
principalement de savoir calculer un sur-gradient en tout point
la n de cette section.
Rappelons qu'un
En particulier, si
sur-gradient p
de
au point
G() G() pT ( )
pour tout
Proposition 7.2.1.
Dmonstration. Soit
Pp+q
i=1 gi (x)(i i ).
un tel
x.
Pour tout
on a
Un des intrts de la relaxation lagrangienne est contenu dans le thorme suivant (preuve
omise).
Pour un programme linaire en nombres entiers, la borne obtenue par relaxation lagrangienne est toujours au moins aussi bonne que celle obtenue par relaxation linaire.
Thorme 7.2.2.
Cela dit, il existe beaucoup de cas o ces deux bornes concident. Cela n'empche pas la
relaxation lagrangienne d'tre intressante (comme dans l'exemple ci-dessous), car le calcul de
sup G()
Exemple.
Un exemple trs classique est celui du plus court chemin avec contrainte de
temps.
D = (V, A) un graphe orient, avec deux sommets s et t. A chaque arc a est associ un cot
et un temps ta 0. On veut trouver le st chemin le moins coteux qui mette un temps
infrieur T . Ce problme se rsout bien avec un branch-and-bound, utilisant des bornes fournies
P
par la relaxation lagrangienne. X est alors l'ensemble des st chemins, f (x) =
aA ca xa et
P
l'on a une seule contrainte du type gi , c'est g(x) :=
aA ta xa T .
Ecrivons G(), dni pour 0.
!
X
X
L(x, ) =
ca xa + T +
ta xa .
Soit
ca 0
aA
aA
Donc
G() = T + min
xX
Le calcul de
non plus les
ca
G()
(ca + ta )xa .
aA
se fait donc par un calcul de plus court chemin o les cots des arcs sont
mais les
1. ou alors par
la mthode des faisceaux, plus ecace mais qui dpasse le cadre de ce cours, voir [5].
81
P
g donne la valeur T + aA ta xa , cette
dernire quantit tant alors le sur-gradient de G en (d'aprs la Proposition 7.2.1). On sait
donc calculer les sur-gradients de G , donc on sait maximiser G sur = R+ , donc on sait calculer
sont positifs ou nuls, et la solution
x,
injecte dans
de bonnes bornes infrieures pour notre problme, et on peut donc faire un branch-and-bound.
k
k+1 = P k +
pk ,
||pk ||
pk
est un sur-gradient de
lim k = 0
k+
Lorsque
pk
vaut
0,
l'algorithme s'arrte,
et
+
X
au point
k ,
et o
(k )
k = +.
k=0
G.
G , mais
0).
la convergence est
7.3. Mtaheuristiques
Nous allons dcrire quelques mtaheuristiques, qui sont des mthodes gnrales d'exploration
de l'espace des solutions ralisables, qui peuvent tre dcrites indpendamment du problme.
Les mtaheuristiques peuvent parfois donner de trs bons rsultats ou constituer la seule arme
pour attaquer un problme ; il est donc ncessaire de les connatre lorsqu'on fait de la recherche
oprationnelle. De plus, il est facile de contrler leur temps d'excution. Cela dit, leur implmentation dpend d'un certain nombre de paramtres dont les valeurs ncessitent beaucoup
d'exprimentations. De plus, ces algorithmes n'ont gnralement pas de garantie sur la qualit
de la solution trouve.
de dpart, trouve par une heuristique quelconque. Ensuite, on essaie d'amliorer la solution
courante en procdant des modications locales.
Plus prcisment,
1. il faut dnir sur
machine), une solutions ralisable tant connecte une autre solution ralisable si on passe
x,
(x) l'ensemble de ses voisins dans le graphe implicite, i.e. l'ensemble des solutions
ralisables que l'on peut atteindre de x par une modication locale. Une condition ncessaire
de la premire la seconde par une modication autorise. Pour une solution ralisable
on note
pour pouvoir trouver l'optimum global est que la solution ralisable de dpart est dans la
mme composante connexe du graphe implicite que l'optimum cherch.
2. il faut aussi dnir quelle condition on modie la solution courante. La solution consistant
modier la solution courante si la modication a amlior la valeur de
est nave : en
eet, un tel algorithme va plonger vers un optimum local, qu'il ne va plus quitter.
82
x.
Ensuite
y (x)
tel que
Si
Puisqu'on a suppos
de
f.
x X,
Pour viter de se retrouver bloqu sur n'importe quel minimum local, deux stratgies classiques
sont employes, la
mthode tabou
et le
recuit simul,
graphe (voir Section 2.1.1.3). On veut colorer les sommets d'un graphe
G = (V, E)
de manire
ce que deux sommets voisins ont des couleurs distinctes, et en utilisant un nombre minimum
de couleurs. C'est un problme
NP-dicile.
comme l'ensemble des colorations propres et considrer deux colorations propres comme voisines si elles dirent uniquement par la couleur d'un sommet. La fonction objectif est le nombre
de couleurs utilises. Cette approche a un inconvnient : la plupart des modications n'implique
pas un changement de la valeur de la fonction objectif. Avec la dnition stricte de l'algorithme
naf ci-dessus, on se retrouve trs vite bloqu sur des minima locaux. Mme en acceptant des
modications valeur constante de la fonction objectif, ou des modications dtriorant cette
valeur (comme dans les mtaheuristiques dcrites ci-dessous), cela reste problmatique car la
fonction objectif donne peut d'information sur la direction prendre.
Une faon plus ecace de rsoudre le problme de la coloration [
16]
P
k et de rsoudre le problme consistant minimiser ki=1 |E[Vi ]| sur l'ensemble des partitions
V1 . . .Vk de V . Rappelons que E[Vi ] est l'ensemble des artes de G ayant leurs deux extrmits
dans Vi . Si l'on parvient atteindre 0, on aura trouv une coloration en au plus k couleurs : chaque
partie Vi peut tre vue comme l'ensemble des sommets de couleur i ; comme alors E[Vi ] = ,
on est sr de ne pas avoir deux sommets de mme couleur adjacents. La recherche locale rsout
extrmement bien cette tche : l'ensemble
partitions
V1 . . . Vk
de
V.
Pk
passer d'une solution une autre si le changement consiste modier la couleur (l'appartenance
l'un des
Vi )
d'un sommet appartenant une arte dont les deux extrmits sont de couleur
permet de trouver
in ne
le nombre chromatique de
G.
de solutions
est cette
(2) , on commence par une solution ralisable x tabou. On choisit une liste L qui contient l
taille
on rpte
choisir
minimisant
f (y)
sur
x := y ,
f (x) < f (x ),
(x) \ L
L, et ajouter x
poser
si
poser
2. par exemple l = 7.
83
x := x.
la n de
L,
Puisqu'on a suppos
f.
x X ,
solution ralisable une solution ralisable voisine auront lieu avec une probabilit dpendant
de la dirence de la valeur prise par
voisin de
x,
(3)
physique
min(1, e
Une fois xe au pralable la suite
Tk
f (y)f (x)
T
bilit
min(1, e
x.
uniformment dans
f (y)f (x)
Tk
).
Poser
).
y (x)
Tk 0
quand
Ensuite, on rpte
(x).
Faire
x := y
k ),
on
avec la proba-
k := k + 1.
Tk
de la forme
Tk
de la forme
Tk := T0 k
(4) ou de la forme
Tk :=
avec
et
1
+ sk
des paramtres bien choisis. La plupart du temps, ces derniers sont dtermins
exprimentalement.
algorithmes volutionnaires
Il y a bien d'autres
tions ralisables des individus et de coder ces solutions ralisables sur les chromosomes des
individus. On autorise les individus se croiser avec une probabilit d'autant plus grande que
les individus sont de qualit. De plus ces individus peuvent muter. On part alors d'une population de taille xe d'individus, et on laisse voluer le tout. Ce qui est crucial ici, c'est le codage
d'une solution ralisable sur les chromosomes et la nature du croisement, qui doit maintenir les
avantages comptitifs de ses parents.
L'algorithme
naires, cherche imiter la nature dans la faon dont elle rsout ses problmes d'optimisation.
Les fourmis pour trouver leur nourriture explorent au hasard l'espace des solutions, en ayant une
toute petite vue locale, mais grce des changes d'information (phromones), elles parviennent
trouver la source de nourriture et trouver le trajet le plus court. Une fourmi qui a trouv
de la nourriture revient la fourmilire en dposant au sol des phromones, qui s'vaporent
au bout d'un certain temps. D'autre part, une fourmi qui part la recherche de nourriture va
3. Pour un systme ferm, la temprature T , la probabilit d'tre dans un tat d'nergie E est de la forme
e kB T
Z
84
suivre prfrentiellement ces phromones au sol. Etant donns deux chemins conduisant de la
fourmilire la nourriture, le plus court sera donc plus attractif que le long car les fourmis
qui l'empruntent dposent des phromones plus frquemment. L'algorithme va donc simuler
l'exploration de l'espace des solutions par des fourmis, qui marqueront leur passage.
7.4. Exercices
7.4.1. Borne infrieure par la relaxation lagrangienne.
l'exercice 5.3.11.
Supposons maintenant qu'il n'y ait pas un seul bien, mais
Pour chaque bien
produisant
yk(t1)
xkt
k,
Pkt .
pkt ,
k = 1, 2, . . . , K .
de bien
de la priode
pas excder
en priode
est not
skt .
et
t)
k 0 6= k
en priode
t,
k
4. Montrer que ce problme peut se modliser comme un programme linaire mixte en nombres
entiers (mixte signie que toutes les variables ne sont pas contraintes tre entires).
Dans une approche par branch-and-bound, on va chercher des bornes infrieures. Une solution
est de procder par relaxation lagrangienne.
5. Montrer qu'en relaxant les bonnes contraintes, le calcul des bornes infrieures par la relaxation lagrangienne se ramne des calculs de gestion de stock un seul bien, et expliquer
Pkt
Pkt
NP-dur. Proposer
une solution pour le calcul de la borne infrieure par la programmation dynamique qui garde
une complexit raisonnable.
On se remet dans le
contexte de l'Exercice 5.3.12. On essaie cette fois de prendre en compte l'aspect dynamique. On
cherche dterminer la squence d'extraction des
est assimile une collection de
blocs
1
blocs numrots de
n,
le bloc
mi .
On
se place dans un contexte horizon de temps ni. Le temps est discrtis est assimil des
annes
ci,
entrane un prot de
ci,
dpendance en temps permet de tenir compte du taux d'actualisation, des tendances des cours
boursiers, etc.
85
A l'anne
Les blocs ne peuvent pas tre extraits dans n'importe quel ordre : pour chaque
connat l'ensemble
M .
bloc i, on
donne, on peut extraire plusieurs blocs, mais pas plus d'une masse totale
Yi
des blocs qu'il faut avoir extraits pour pouvoir extraire le bloc i. Si le bloc
tout bloc de
Yi
ou
avant. L'objectif est de proposer un sous-ensemble de blocs extraire et les annes auxquelles
plan d'extraction).
On suppose maintenant que les ci, dpendent bien du temps. On parle alors du cas dynamique.
Etant donn un plan d'extraction, on note xi, = 0 si le bloc i est extrait strictement aprs l'anne
et xi, = 1 sinon. On tient nouveau compte de la contrainte de masse.
extraire ces blocs de manire maximiser le prot total (on appelle cela un
xi, .
On posera de plus
xi,0 = 0
pour tout
i.
En pratique, ces programmes linaires peuvent avoir un grand nombre de variables (le produit
NT
peut tre grand). On va chercher dans la suite des mthodes pour amliorer les temps de
et
tels que
mi +
kYi
mk >
paire. Expliquez pourquoi toute solution ralisable du programme linaire en nombres entiers de
1. satisfait xi , = 0 lorsque (i , ) est une bonne paire.
P
ajoute au programme linaire en nombres entiers de 1. plusieurs contraintes induites par des
bons triplets. Expliquez pourquoi cela ne change pas la solution optimale du programme linaire
en nombres entiers, et en quoi cela va amliorer les temps de calculs (au moins pour les grandes
instances).
86
Deuxime PARTIE II
PROBLMATIQUES
CHAPITRE 8
REMPLISSAGE DE CONTENEURS
Le thme de ce chapitre est le suivant : on a des objets et des conteneurs, comment remplir
au mieux ? Ecrit comme cela, le problme est assez imprcis. Nous allons nous focaliser sur deux
problmes particuliers qui rentrent dans la catgorie des problmes de remplissage, le problme
du
8.1. Sac--dos
8.1.1. Le problme.
Problme du sac--dos
Donne : des entiers n, w1 , . . . , wn et W , et des rels c1 , . . . , cn .
Tche : trouver un sous-ensemble S
mum.
{1, . . . , n}
ci
sa valeur. On a
tel que
jS
wj W
et
jS cj est maxi-
wi
cotant chacun
wi
et rapportant
ci
W,
Thorme 8.1.1.
on a des produits
NP-dicile.
wi
W
n'est pas trop grand, passe par l'utilisation de la programmation dynamique, laquelle fournit un
algorithme pseudo-polynomial en
O(nW ).
problme.
Pn
cj xj
Pj=1
n
j=1 wj xj W
xj {0, 1}
Max
s.c.
j {1, . . . , n}.
Remarquons que dans un sens ce programme linaire en nombres entiers est le plus simple
possible : chaque variable ne peut prendre que deux valeurs, et il n'y a qu'une seule contrainte.
La relaxation continue fournit une borne suprieure naturelle la solution du programme
prcdent
Pn
cj xj
Pj=1
n
j=1 wj xj W
0 xj 1
Max
s.c.
j {1, . . . , n}.
Pour la calculer (pour faire du branch-and-bound par exemple voir ci-dessous), on pourrait
bien sr faire appel l'algorithme du simplexe ou l'algorithme des points intrieurs. Mais il
existe un algorithme trs simple, glouton, qui calcule la solution optimale du relch continu.
On suppose que
Pn
j=1 wj
> W,
c1
c2
cn
...
.
w1
w2
wn
Poser
Pj
x1 = x2 = . . . = xj := 1
j=1 wj
Lemme 8.1.2.
avec
W.
P
W jj=1 wj
.
wj+1
Poser
xj+1 :=
Poser
xj+2 = = xn := 0.
Elments 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 consquent, 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 (relch continu) en
{0, 1}
90
et d'autres
1.
{1, . . . , j}
Pj+1
8.2. Bin-packing
8.2.1. Le problme.
et
12 OP T ,
OP T
OP T .
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 gnrales de ce
problme, on peut aussi prendre en compte la forme des objets (on parle alors de bin-packing
2D ou de bin-packing 3D), des incompatibilits, etc.
Ce problme peut tre parfois appel aussi
cutting-stock.
(de pices de textile, mtal, etc.), o l'on cherche minimiser les pertes, se modlisent de faon
similaire.
Ici, on se limite au cas le plus simple, 1D. C'est un cas dj trs 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, dcouper des planches de longueurs variables
dans des grandes planches de longueur xe, dcoupe dans des bandes de tissu, etc.).
Le problme s'crit alors formellement
Problme du bin-packing
Donne : Des entiers positifs ou nuls a1 , . . . , an , W .
Tche
:
P
avec
k minimium
j {1, . . . , k}.
i: f (i)=j ai 1
pour tout
Thorme 8.2.1.
et une aectation
f : {1, . . . , n} {1, . . . , k}
NP-dicile.
taille non rsolue, ce qui justie et motive largement des travaux de recherche dans ces domaines.
Par exemple, considrons l'instance suivante, dont on ne connat pas ce jour la solution optimale
(1) .
91
Le d est de trouver une solution en moins de 51 botes, ou alors de parvenir montrer que 51
botes est la solution optimale. Nous allons dcrire maintenant quelques heuristiques classiques
(NEXT-FIT, FIRST-FIT, FIRST-FIT DEACRISING), puis nous verrons les approches branchand-bound.
Je prends les objets les uns aprs les autres. Ds que l'objet
ne peut
k := 1, i := 1
Si
et
S := 0.
et
Rpter
On a
Thorme 8.2.2.
Pn
i=1 ai
(29)
OP T.
o(j)
o(j)
{1, . . . , n}.
OP
XT
j=1
Le fait que
OP T
OP T
j.
Les
On a donc
OP
XT
ai =
j=1 io(j)
n
X
ai .
i=1
que
que
i: f (i){2j1,2j}
par dnition de l'algorithme NEXT-FIT.
En sommant :
X
n
k
<
ai ,
W
2
i=1
k1
Pn
i=1 ai
92
k 2OP T 1.
conclure.
1,
On va montrer
8.2.2.2. FIRST-FIT.
Je prends les objets les uns aprs les autres. Je mets l'objet
dans la
i := 1.
Rpter :
poser
Poser
n
o
P
f (i) := min j N : ai + h<i: f (h)=j ah W ;
poser
i := i + 1.
k := maxi{1,...,n} f (i).
Thorme 8.2.3.
La preuve de ce rsultat, dicile, est omise. Ce que ce rsultat indique et qui est vri en
pratique, c'est que l'heuristique FIRST-FIT marche en gnral mieux que l'heuristique NEXTFIT
ai
plique FIRST-FIT.
Thorme 8.2.4.
Tout comme pour le Thorme 8.2.3, la preuve de ce rsultat est omise. C'est cette heuristique
qui a en gnral les meilleurs rsultats. L'avantage des deux premiers algorithmes sur ce dernier
est qu'ils peuvent fonctionner
on-line,
objets arrivent les uns aprs les autres et qu'on ne connat pas la taille des objets futurs.
8.2.3. Branch-and-bound.
8.2.3.1. Formulation PLNE.
Min
s.c.
(30)
zj = 1
si la bote
PK
zj
Pj=1
K
y =1
Pnj=1 ji
i=1 ai yji W zj
yji , zi {0, 1}
est utilise et
yji = 1
i = 1, . . . , n
j = 1, . . . , K
i = 1, . . . , n ; j = 1, . . . , K
si l'objet
j.
relaxation continue :
Min
s.c.
PK
zj
Pj=1
K
yji = 1
Pj=1
n
i=1 ai yji W zj
yji , zi 0
yji , zi 1
i = 1, . . . , n
j = 1, . . . , K
i = 1, . . . , n ; j = 1, . . . , K
i = 1, . . . , n ; j = 1, . . . , K
C'est un programme linaire avec un nombre linaire de contraintes, il n'y a donc pas de
problme pour calculer la borne obtenue par relaxation continue.
93
On crit le lagrangien
K
X
L(y, z, ) :=
Si on note
zj +
j=1
n
X
i (
i=1
K
X
j=1
yji 1).
xX
G:
R {}
G() 7 inf xX L(x, ),
Rappelons que cette dernire est concave et ane par morceaux et que l'ide de la relaxation
lagrangienne est d'utiliser
proche de l'optimum).
sup G()
G()
Ici,
G() :=
Min
s.c.
P
P
PK
zj + ni=1 i ( K
j=1 yji 1)
Pj=1
n
a
y
W
z
j = 1, . . . , K
j
i=1 i ji
yji , zi {0, 1}
i = 1, . . . , n ; j = 1, . . . , K
se rcrit
G() :=
Sj := miny,z{0,1} {z +
On doit donc rsoudre K
avec
Pn
i=1 i yi
n
X
i +
Sj
i=1
j=1
i=1 ai yi
W z}.
Pn
K
X
problmes de sac--dos
(
Sj :=
min
z+
y,z{0,1}
n
X
i yi :
i=1
n
X
i=1
)
ai yi W z
8.3. Exercices
8.3.1. Ingalits valides pour le sac--dos.
a1 , . . . , a n , b
(
S :=
On appelle
ensemble dpendant
xS
x {0, 1}n :
tout ensemble
n
X
i=1
)
ai xi b .
C {1, . . . , n}
satisfait l'ingalit
X
iE(C)
xi |C| 1,
E(C) = C {j : aj maxiC ai }.
94
tel que
iC
ai > b.
2. Expliquer l'intrt de ce type d'ingalits dans une rsolution d'un problme de sac--dos
dans une approche branch-and-bound.
botes de taille
1.
PK
zj
Pj=1
K
y =1
i = 1, . . . , n
s.c.
Pnj=1 ji
i=1 ai yji zj j = 1, . . . , K
yji , zi {0, 1}
i = 1, . . . , n ; j = 1, . . . , K
j est utilise et yji = 1 si l'objet i est mis dans la bote j .
min
zj = 1
si la bote
PK
zj zj+1 ,
j=1 zj
pour
j = 1, . . . , K 1,
on continue
P
d ni=1 ai e.
3. Expliquer l'intrt de ce type d'ingalit dans une rsolution d'un problme de bin-packing
dans une approche branch-and-bound.
1
3 pour tout
i = 1, . . . , n.
a1 , . . . , a n
1.
O(n log(n)).
95
Complter la
CHAPITRE 9
POSITIONNEMENT D'ENTREPTS
9.1. Formalisation
La version la plus simple du problme de positionnement d'entrepts est la suivante.
fi R+ d'ouverture
i F et j D.
iF
(dits
et un cot de service
cij R+
pour chaque
fi +
iX
c(j)j
jD
soit minimale.
mtrique
si
pour tout
i, i0 F
cij
et
j, j 0 D.
gomtrique. Cette ingalit contient plus de termes que l'ingalit triangulaire classique,
laquelle elle ressemble. C'est d au fait que les cots ne sont pas ncessairement dnis entre
entrepts ou entre clients.
Commenons par la question de la complexit.
Proposition 9.1.1.
le cas mtrique.
Nous allons un peu discuter des formulations sous forme de programmes linaires en nombres
entiers et parler rapidement de recherche locale.
Client
Figure 1.
Figure 2.
9.2. Branch-and-bound
9.2.1. Programme linaire en nombres entiers.
schma de branch-and-bound est de commencer par la modlisation sous forme d'un programme
linaire en nombres entiers. Ici, le problme s'crit facilement sous cette forme.
98
Min
s.c.
P
P
fi yi + iF jD cij xij
x yi
Pij
iF xij = 1
xij {0, 1}
yi {0, 1}
iF
i F, j D
jD
i F, j D
i F.
(1)
(2)
(3)
(4)
xij
et
yi .
ou
certaines
(31)
P
P
fi yi + iF jD cij xij
x yi
Pij
iF xij = 1
0 xij
0 yi
iF
i F, j D
jD
i F, j D
i F.
(1)
(2)
(3)
(4)
xij = 1
fi yi +
XX
iF
pour
On crit le lagrangien
j F.
!
L(x, y, ) =
X
iF
cij xij +
iF jD
jD
xij
iF
max L(x, y, ).
min
max
min
L(x, y, ),
c'est--dire, en posant
G() :=
on a
G()
min
RF ,
L(x, y, ),
max G()
RF
On veut donc tre capable de calculer
G(),
i.e. de rsoudre
min
G() =
x
L(x, y, ).
j +
jD
di ()
iF
avec
di () =
fi yi +
X
jD
(cij j )xij .
Chacun des
qui impose
min
99
F.
iX
de
2.
:= X \ {x}
X0
voisin
est
pour un
X 0 := X {x0 }
0
3. X
l'entrept ouvert
cij .
0
1. X
x X , (drop)
pour un
:= X \ {x}
de
x0 F \ X (add)
ou
{x0 } (swap).
Dans le cas du problme de positionnement d'entrepts, on a ralis dans les annes 2000 que
la recherche locale tait extrmement ecace (plus que pour les autres problmes de RO).
En revanche, on n'a pas a priori d'valuation du temps de calcul d'un optimum local.
9.4. Exercices
9.4.1. Positionnement d'entrepts avec capacit.
tionnement d'entrepts vu en cours, mais avec cette fois une contrainte supplmentaire : chaque
entrept ne peut desservir qu'un nombre limit de clients. Modliser le problme suivant comme
un problme linaire en nombres entiers.
Donne
(dits
X
iX
fi +
c(j)j
jD
soit minimale.
P
P
fi yi + iF jD cij xij
x yi
Pij
iF xij = 1
xij {0, 1}
yi {0, 1}
iF
100
i F, j D
jF
i F, j D
i F.
(1)
(2)
(3)
(4)
On re-
Dans le cours, on a relch la contrainte (2). Relcher maintenant la contrainte (1) la place
de la contrainte (2) et montrer que la fonction duale se calcule encore trs simplement.
La
logistique traditionnellement prise en compte est la logistique forward, qui concerne l'approvisionnement de clients partir d'entrepts, que nous appellerons dans cet exercice
entrepts
Pour de nombreuses raisons (environnementales, dure de vie plus courte des produits, vente
distance), la reverse logistique prend de l'importance dans le management de la supply-chain.
L'objectif de cet exercice est d'tudier l'implication que cela peut avoir dans la modlisation des
problmes de positionnement d'entrepts.
On suppose donc que l'on dispose d'un ensemble
d'un ensemble
fi R+ et celui d'un
entrept reverse ri R+ . La capacit d'un entrept forward en position i (ie la demande totale
qu'il peut satisfaire) est note bi et la capacit d'un entrept reverse en position i (ie le retour
total qu'il peut accepter) est note ei . Chaque client j a une demande hj R. De plus, chaque
client j a un taux de retour j [0, 1], ce qui signie qu'il renvoie une quantit j hj du bien. Le
cot de tranport d'une unit de bien d'un entrept i un client j , ou d'un client j l'entrept
i, est cij R+ .
Le cot d'ouverture d'un entrept forward en la position
est not
Le bien tant suppos parfaitement fractionnable, un client peut tre approvisionn par plu-
sieurs entrepts forward ; et de mme, plusieurs entrepts reverse peuvent tre destination des
retours d'un client. De plus, il est possible d'ouvrir au mme endroit
en entrept forward et
un entrept reverse.
1. Proposer une modlisation par la programmation linaire mixte (avec des variables entires
et des variables relles) du problme de minimisation des cots de conception d'un tel systme,
pouvant traiter toute la demande et tous les retours. Noter que ce problme se dcompose en
deux sous-problmes indpendants : un pour le forward et l'autre pour le reverse.
On suppose maintenant que si on parvient ouvrir un entrept forward et un entrept reverse
au mme endroit
i,
cela diminue le cot total d'ouverture des deux entrepts d'une quantit
si .
2. Modier la modlisation prcdente pour tenir compte de cette nouvelle possibilit, tout en
restant dans la programmation linaire mixte. Noter que les deux sous-problmes ne sont plus
indpendants.
3. Proposer une dnition de l'espace des solutions et d'un voisinage et expliquer comment
pourrait tre construite une mtaheuristique de type recherche locale partir de cette dnition.
4. Toujours dans le cas d'une mtaheuristique de type recherche locale, comment adapter la
mthode au cas o le bien n'est pas parfaitement fractionnable (les quantits seront donc des
entiers) et que les
j hj ,
les
hj ,
les
bi
et les
ei
et
j?
entrepts et
transfrer le contenu des entrepts ferms dans les entrepts rests ouverts qui disposent encore
de place. Tous les entrepts sont considrs comme identiques et possdent une capacit de
101
1.
par
qi .
cij
: si l'on transfert
cij
(i, j, k).
On posera
cii = 0
pour tout
i.
ferm peut trs bien tre rparti entre plusieurs entrepts rests ouverts.
1. Ecrire sous forme d'un programme linaire en variables mixtes (entires et continues) le
problme consistant choisir les
rechange des entrepts ferms vers ceux rests ouverts, tout en minimisant le cot total du
transfert. Justier en particulier les contraintes utilises.
2. Expliquer pourquoi il est facile de voir si ce problme a une solution ralisable.
Il est maintenant demand d'admettre que l'on peut assez facilement montrer que ce problme
est
3. Ce problme tant
l'optimum exact de ce problme (quelques lignes donnant le nom de la mthode et son principe
sont susantes). Est-on certain de pouvoir obtenir l'optimum en quelques minutes ?
4. Y a-t-il des logiciels libres permettant de rsoudre un tel problme avec cette mthode ? Si
oui, en citer un.
On souhaite maintenant proposer une mthode du type recherche locale pour ce problme.
5. Quel peut tre l'intrt d'une telle mthode ?
6. Expliquer pourquoi une recherche locale pour ce problme peut limiter le codage des solutions au choix des
entrepts ferms, sans prcision sur les transferts. Donner le nom d'un
problme traditionnel de recherche oprationnelle dont la rsolution rapide permet un tel codage.
7. Proposer une dnition du voisinage pour cette recherche locale.
pour atteindre les victimes d'accidents, certains hpitaux envisagent de les positionner de manire optimise sur le dpartement dont ils ont la charge. Considrons donc un certain hpital
ayant
C.
|S| K .
de
c C et s S , on note ts,c
c. Si S 0 S est l'ensemble
0
des points o sont positionnes les ambulances (avec bien sr |S | K ), dans le pire des cas, une
ambulance atteindra la commune o a eu lieu l'appel en un temps gal maxcC minsS 0 ts,c .
points de stationnement potentiel et on suppose que
Pour
pour atteindre
C'est ce temps maximum que l'hpital souhaite rendre le plus petit possible.
1. Montrer que ce problme est
orient ; on appelle
a un voisin dans
dominant
NP-dicile.
un sous-ensemble
Indication : soit
Y V
G = (V, E) un
v V est soit
est
NP-complet.
graphe nondans
Y,
soit
2. Dmontrer que le programme linaire suivant modlise le problme. Pour cela, procdez
en deux temps : montrez que toute solution optimale du problme donne une solution de mme
102
valeur au programme linaire ; puis montrez que toute solution optimale du programme linaire
donne une solution de mme valeur au problme.
Min
s.c.
X
sS
X
cC
ys K
(i)
xs,c |C|ys
sS
(ii)
xs,c = 1
cC
(iii)
sS; cC
(iv)
sS
ts,c xs,c h
xs,c
ys
{0, 1} s S ; c C
(v)
{0, 1} s S
(vi)
h R+
(vii)
Un tel programme linaire se rsout par branch-and-bound. La borne dont on se sert alors
peut tre celle obtenue en relchant les contraintes d'intgrit de
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 procde la relaxation lagrangienne
de la contrainte (ii).
4. Montrer que ce programme se ramne deux programmes distincts et indpendants, l'un
ne mettant en jeu que les variables
y,
et
h.
103
CHAPITRE 10
ORDONNANCEMENT INDUSTRIEL
NP-diciles, mais
10.1. Prliminaires
tches,
contraintes, on
oprations.
Les
contraintes de temps
Les
Cot : Cot total de l'ordonnancement. Cela suppose dni le cot d'aectation d'une tche
i sur une machine k .
Makespan : Temps pour eectuer l'ensemble des tches.
Temps moyen : Temps moyen mis par une tche pour tre traite. Son intrt peut tre
vari. Par exemple si le problme d'ordonnancement s'insre dans un processus plus grand,
ce genre de critre peut tre intressant.
diagramme de Gantt
: en abs-
cisse, on met le temps, et on ordonne, les direntes tches. Sur chaque ligne repre par une
tche, on met des intervalles qui occupent les instants pendant lesquels la tche est traite. Un
exemple est donn Figure 1.
F
E
D
C
B
A
20
Figure 1.
40
60
80
100
120
jours
140
i,
on se donne sa dure
r%
de la tche
di ,
et des
au moins a t eectu .
On veut trouver
la dure minimale du projet.
les tches critiques : les tches pour lesquelles une modication de l'instant de dbut rallonge
la dure du projet.
les marges : la marge d'une tche est l'intervalle de temps sur lequel on peut faire dmarrer
la tche sans rallonger la dure du projet. En particulier, une marge nulle signie une tche
critique.
On modlise ce problme sous la forme d'un graphe dont les sommets sont les dbuts des
tches et les arcs sont les relations de prcdence. On ajoute deux tches ctives :
Dbut
et
Fin. De plus, chaque arc (u, v) est muni d'une longueur gale la dure minimale sparant le
dbut de
de celui de
v.
106
Tches
Description
Dure (j)
Contraintes
A
B
C
D
E
F
80
Dbut
70
Dbut
30
Dbut
30
50
40
B
A, D
A, C
D
80
70
30
30
Debut
0
Fin
50
80
0
40
F
C
30
Figure 2.
Notons
tI
et
t0I
Dmonstration.
Dbut
I.
En eet,
I,
Dbut I .
t0I .
Pour trouver la dure minimale du projet, les tches critiques, etc. il faut donc savoir calculer
les plus longs chemins dans un graphe acircuitique
Cela se fait par la programmation dynamique, comme nous l'avons vu au Chapitre 3. Si on note
en
O(m)
les
tches d'un chemin critique sont caractrises par une marge nulle.
107
d'un ensemble de
et d'un ensemble de
machines M1 , . . . , Mm .
Une tche
j,
pour tre ralise, ncessite son excution sur direntes machines successivement. Le temps
d'excution de la tche
tion d'une tche
la tche
sur la machine
sur la machine
s'appelle une
opration,
on parle galement
k.
non-premptif.
ow-shop : Toutes les tches doivent passer sur les machines dans le mme ordre.
job-shop : L'ordre dans lequel dans passer chaque tche sur les machines est x, mais peut
direr d'une tche l'autre.
open-shop
Remarque.
: L'ordre dans lequel dans passer chaque tche sur les machines n'est pas x.
k.
On note
Cj
tjk
j.
makespan,
lequel s'crit
Cj ,
et
Cmax = maxj Cj .
10.3.2. Dicult.
terme.
Le problme du ow-shop non-premptif trois machines et minimisation du makespan Cmax est NP-dicile.
P
Le problme du ow-shop non-premptif deux machines et minimisation du j Cj est
NP-dicile.
Le problme de l'open-shop non-premptif trois machines et minimisation du makespan
Cmax est NP-dicile.
P
Le problme de l'open-shop non-premptif deux machines et minimisation du j Cj est
NP-dicile.
Thorme 10.3.1.
problmes, contrairement au problme du voyageur de commerce par exemple, que l'on tudiera
au Chapitre 11. Mme avec des mtaheuristiques ou des techniques de branch-and-bound, des
instances job-shop 15 machines et 15 tches sont encore non rsolues ce jour !
108
Par exemple, on ne connat pas l'ordonnancement optimal pour l'instance suivante de owshop
20
tches et
machines
(1)
54
83
15
71
77
36
53
38
27
87
76
91
14
29
12
77
32
87
68
94
79
11
99
56
70
99
60
56
61
73
75
47
14
21
86
77
16
89
49
15
89
45
60
23
57
64
63
41
63
47
26
75
77
40
66
58
31
68
78
91
13
59
49
85
85
39
41
56
40
54
77
51
31
58
56
20
85
53
35
53
41
69
13
86
72
49
47
87
58
18
68
28
5 oprations 1, 2, 3, 4 et 5, identies avec 5 machines. Les oprations doivent tre faites dans
k me opration de la tche j se lit sur l'entre qui
est l'intersection de la k me ligne et de la j me colonne.
en
premptif
problme polynomial.
un schma de branch-and-bound pour le job-shop.
un schma de recherche locale pour le job-shop.
Cmax
algorithme de Brucker.
4. Le problme de l'open-shop non-premptif deux machines et minimisation du makespan
j=n
:
si
si
qj
qj
Faire
jr+1 := j
0
js+1
:= j
j := j + 1.
109
et
et
r := r + 1 ;
s := s + 1.
Retourner l'ordre
j1 , . . . , jr , js0 , . . . , j10 .
que
avec les
la suite des
2.
tels que
ordre.
Choisir la tche Jj ayant le plus petit pj1 ou pj2 parmi tous les pji .
Appliquer rcursivement l'algorithme sur les tches 6= j : cela
j1 , j2 , . . . , jr , js0 , . . . , j10 ,
Les tches j1 , . . . , jr
avec
r + s = n 1.
js0 , . . . , j10
pj1 pj2 ,
pj1 > pj2 ,
A
B
C
D
E
12
14
11
25
13
17
15
...,A
E, . . . , A
E, D, . . . , A
E, D, . . . , B, A
E, D, C, B, A.
Thorme 10.3.2. L'algorithme de Johnson rsout correctement le problme du ow-shop
deux machines et minimisation du makespan Cmax .
Dmonstration.
j.
On peut
j 1 tches ont dj
t xes : pour xer les notations, supposons que les tches xes sont celles d'indices j1 , . . . , jr
0
0
et j1 , . . . , js . On suppose donc que j = r + s + 1. On peut mettre les autres dans un ordre
qj
quelconque, pas forcment le mme sur la premire et la seconde machine. On suppose que l'on
a les instants de dmarrage de chacune des oprations et que cet ordonnancement est ralisable.
On a donc un ordre de tches sur la premire machine
(1)
(1)
et sur
(2)
(2)
0
0
la seconde j1 , . . . , jr , i1 , . . . , inrs , js , . . . , j1 .
On fait maintenant commencer
gauche de
sur la machine
(1)
i1
, et sur
(2)
l'instant auquel commenait i1 . On dcale vers la droite les tches qui tait
2
j sur
la machine
la machine
et sur la machine
sur le Figure 3.
110
j1
M1
j2
M2
j3
j2
j1
j1
M1
j2
M2
j20
i0
j3
j3
j2
j1
j10
`0
j20
j20
j3
j10
i0
j20
`0
Figure 3.
Montrons que ce nouvel ordonnancement est encore ralisable et garde le mme makespan.
Une fois l'itration
sur la machine
1,
et de
pj2
sur la machine
j.
2.
Comme
1.
(2)
au plus tard l'instant auquel commenait i1 sur la machine
pj1
et
2
1
pi(2) 1 pj1 .
1
En conclusion, partant d'un ordonnancement quelconque, on peut toujours obtenir un ordonnancement de mme makespan tel que les tches soient classes de la mme faon que par
l'algorithme de Johsonn.
machine
tches
2.
J1 , J2 , . . . , Jn .
j,
C'est
Chaque tche
Jj
a une dure
pj1
sur la machine
et
et
pj2
sur la
est x.
J12 := {Jj : Jj
J21 := {Jj : Jj
puis sur
2}
puis sur
1}
J12
et
J21
J12 J21 ,
J21 J12 ,
Dmonstration.
111
j10
j10
Pour rsoudre ce problme, on peut appliquer l'algorithme de Brucker [ ], qui est en fait un
algorithme de plus court chemin dans un certain graphe.
ime
opration de la tche
Pi1
k=1 p1k ,
q1i
et
Pj1
k=1 p2k
q2j .
m
X
q1i ,
i=1
m
X
(0, 0)
et allant jusqu'
!
q2i
i=1
Ce chemin se dplace soit de gauche droite, soit de haut en bas, soir vers le nord-est. On
cherche donc le plus court chemin : c'est un problme de plus court chemin dans un graphe
acircuitique le poids d'un arc tant la dure correspondant la transition reprsente par l'arc
qui conduit un algorithme en
O(m2 log(m)) (le plus court chemin lui-mme met O(m2 ), mais
Remarque.
n
devient alors O(nm log(m)), ce qui n'est pas polynomial...
Thorme 10.3.5.
n
n
X
X
Cmax = max max(pj1 + pj2 ),
pj1 ,
pj2 .
j
j=1
j=1
tache 1: M1 M2 M3 M4
tache 2: M2 M4 M3 M1
tache 2
M1
q24
q23
M3
M4 q22
M2 q21
q12
q11
M1
q14
q13
M2
t
ache 1
M4
M3
un ordonnancement possible
un autre ordonnancement possible
Figure 4.
tache 2
M1
q24
poids de cet arc: p22
q23
M3
M4 q22
M2 q21
q11
M1
q12
M2
q13
q14
t
ache 1
M4
M3
un ordonnancement possible
un autre ordonnancement possible
Figure 5.
Dmonstration.
Il est clair que l'on ne peut pas faire mieux que la valeur
ci-dessus.
Montrons qu'on peut l'atteindre. Quitte ajouter des tches ctives, on peut supposer que
Pn
j=1 pj1
Pn
j=1 pj2
= T.
113
On peut dnir
j1
tel que
On considre que cela donne une seule grande tche J1 , avec p11 :=
j=1 pj1
De mme, on peut dnir j2 le plus grand indice j tel que
On considre
et
p12 :=
(p(j1 +1)1 + p(j1 +1)2 ) + (p(j1 +2)1 + p(j1 +2)2 ) + . . . + (pj1 + pj2 ) T.
Pj2
Pj1
j=1 pj2 .
et
p22 :=
Pj2
j=j1 +1 pj2 .
Enn, on dnit de mme
Pn
j .
P3n
J3 ,
avec
Aprs avoir dni J3 , toutes les tches sont soit dans J1 , soit dans J2 , soit dans J3 . En eet,
Pn
Pn
Pn
Pn
p11 +p12 +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 <
p31
T.
J1 , J2 , J3 , avec p11 + p21 + p31 = T et
+
+
=
+
T pour tout j = 1, 2, 3.
En renumrotant, on peut supposer que p11 p22 et p12 p31 . On vrie ensuite que l'on
peut eectuer 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 dure T . Pour chaque Js , on eectue les Jj dont il est
On se retrouve donc avec l'open shop trois tches
p12
p22
p32
T , et pj1
pj2
10.3.3.5. Open-shop premptif. On a n tches et m machines, chaque tche j est dcrite par
un vecteur pj = (pj1 , . . . , pjm ), le nombre pjk indiquant le temps que la tche j doit passer sur
la machine k . Chaque tche peut passer dans un ordre quelconque sur les machines (open-shop).
De plus, chaque opration (passage sur une machine) peut tre interrompue et reprise plus tard,
et ce, autant de fois que ncessaire (cas premptif ). L'important est qu'au total, chaque tche
ait pass un temps
pjk
sur la machine
k,
et ce pour tout
On a le rsultat suivant.
Thorme 10.3.6.
A l'optimum, on a
m
X
k {1, . . . , m}.
, max
pjk
k=1
n
X
pjk .
j=1
Thorme 10.3.7
(Thorme de Birkho-von
Neumann).
P
i).
(ie aij 0 et
n
i=1 aij
P := ((pjk )).
Considrons la matrice
A :=
..
PT
114
P
.
..
Dnissons
!
m
n
X
X
T := max max
pjk , max
pjk .
A,
on peut
Q sont des
P i
i i = 1.
o les
et
k=1
A.
j=1
On obtient que
diagonale
i > 0
i i Qi
pour tout
k,
k,
pour tout
pour tout
qui peut servir tant pour les algorithmes de recherche locale que les mthodes exactes du type
graphe disjonctif.
Le graphe disjonctif est un graphe mixte ( la fois des arcs et des artes) dont les sommets sont
branch-and-bound est le
les oprations, les arcs les relations conjonctives (un arc est mis entre deux oprations conscutives d'une mme tche), les artes les relations disjonctives (une arte est mise entre toute
paire d'oprations utilisant la mme machine). La longueur d'un arc est la dure de l'opration
dont il est issu.
Considrons par exemple le job-shop suivant, trois tches, 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 6.
La remarque fondamentale qui motive l'introduction du graphe disjonctif est la suivante
Trouver un ordonnancement, c'est orienter les artes du graphe disjonctif de manire acircuitique.
En mettant sur chaque arc obtenu par orientation d'une arte la dure de l'opration dont elle
est issue, il est facile de calculer le makespan, c'est--dire la dure totale de l'ordonnancement.
On se retrouve en eet dans la mme situation que dans la mthode potentiel-tche (Section
10.2) o les dures et les prcdences sont entirement xes.
115
: arc conjonctif
: arete disjonctive
J1
4
Debut
1
Fin
J2
3
J3
8
Un exemple de graphe disjonctif.
Figure 6.
10.3.4.2. Branch-and-bound. On dnit alors comme dans la Section 10.2, pour toute opration O , la quantit O qui est la longueur du plus long chemin de Dbut O , et de mme O
(en ne gardant que les arcs). Les calculs sont dcrits Section 10.2.
On dnit
et
p(O) :=
OO
p(O).
max
k=1,...,m
o
Ok
max (O) + (O) + p(O) ,
OOk
k.
Carlier a mon-
Dbut.
il faut dnir une notion de voisinage sur les ordonnancements ralisables, ces derniers tant
identis avec les orientations acicuitique du graphe disjonctif. Par exemple, on peut dire que
deux ordonnancements ralisables sont
voisins
retournement d'arc
retournement des arcs disjonctifs d'un chemin critique.
10.4. Exercices
10.4.1. Management de projet.
116
T.
Description
Dure (j)
Contraintes
A
B
C
D
E
F
G
H
I
J
prparation, fondations
Dbut
10
plomberie extrieure
plomberie intrieure
lectricit
toit
16
B,C,F
lambris
D,E
sol
D,E
11
H,I
Dures
10
Dbut
12
A, G
14
10
au plus tt
Contraintes
Pose de cloisons
B
menuiserie
C
vitrerie
D
construction
de l'ossature
plomberie
11
charpente
de
sont termins
13
15
E, I
16
pose de
la couverture
H
installation
des radiateurs
I
revtement des murs
et des cloisons
dans le cas une seule machine. On se met dans le cas non premptif, chaque tche est faite d'une
117
Cj ,
minimum
wj C j
(o chaque tche
j ).
10.4.4. Retour sur le problme de l'aectation de tche (cours sur les ots).
On
revient sur l'exercice d'aectation des tches, mais cette fois on ne suppose plus que les employs
puissent travailler en parallle.
On suppose que l'on a direntes tches accomplir dont on connat les dures d'excution,
et que l'on dispose d'une ressource de main d'uvre dont on connat les comptences. A un
instant donn, un employ ne peut se consacrer qu' une seule tche la fois. Enn, on se met
dans un cadre premptif, c'est--dire qu'un employ peut interrompre son travail sur une tche,
et le reprendre plus tard.
On veut trouver un ordonnancement, c'est--dire tout instant la donne pour chaque employ
de la tche
R+ ; m
i.
Si
Tche : Trouver un ordonnancement, c'est--dire tout instant la donne pour chaque employ
i
de la tche
sur lequel il travaille, minimisant le temps ncessaire pour raliser l'ensemble des
tches (makespan).
Montrer que ce problme peut se rsoudre en temps polynomial.
1. Avec l'aide du thorme de Knig (qui dit que la cardinalit minimale d'une couverture
par les sommets est gale la cardinalit maximale d'un couplage), montrer le thorme de Hall
suivant :
A,
J1
J2
J3
J4
J5
J6
M1
6
5
7
2
4
M2
3
4
3
6
3
118
suivante.
J1
J2
J3
J4
J5
J6
M1 M 2
7
0
3
7
9
14
7
3
7
3
7
0
C ).
Le matin, 6h,
15
D)
et l'autre
nombre de caisses connu, indiqu dans le tableau ci-dessous. Chacun de ces camions doit tre
intgralement vid dans l'entrept
avec un nombre de caisses connu, indiqu galement dans le tableau ci-dessous. Pour des raisons
lies aux eectifs en personnel et aux contraintes de manutention, un seul camion peut tre trait
la fois par chaque entrept, et lorsqu'on commence traiter un camion, on ne peut interrompre
par caisse. On nglige le temps pour se rendre d'un entrept l'autre. A quelle heure peut-on
avoir ni au plus tt ? Justier votre rponse.
Camions
20
11
10
11
12
11
12
13
14
15
119
CHAPITRE 11
TOURNES
Les problmes de tournes sont parmi les plus naturels en Recherche Oprationnelle et en
Logistique. Le thme gnral est le suivant : un rseau tant donn, il s'agit de le visiter entirement en minimisant le cot. Les variations sont alors innies et peuvent concerner la nature du
rseau, la notion de visite, la dnition du cot. Des contraintes peuvent galement tre ajoutes
l'envie : fentre de temps, retour au point de dpart, etc.
Dans cette sance, nous nous intresserons aux deux problmes les plus simples formuler
dans cette famille, tous deux d'un grand intrt pratique : le
et le
problme du postier.
oprationnelle car, bien que trs semblables dans leur formulation, ils dirent radicalement
quant leur rsolution puisque l'un d'eux peut tre rsolu en temps polynomial par un algorithme
simple implmenter, et l'autre au contraire est
NP-dicile
soit
minimum.
Rappelons que c'est un problme dicile, comme il a t dj signal au Chapitre 2.
Thorme 11.1.1.
NP-dicile.
Il faut donc mettre en uvre des stratgies de rsolutions plus intelligentes, et donc se tourner
vers les techniques de la recherche oprationnelle. Nous allons prsenter trois approches : heuristique, branch-and-bound, recherche locale. Les grands progrs de ces dernires annes dans la
rsolution du problme du voyageur de commerce rsident principalement dans les techniques de
branch-and-bound, et plus prcisment dans le calcul des bornes. On sait de nos jours rsoudre
des instances
1000 000 villes, alors qu'il y a une vingtaine d'annes, on ne dpassait pas quelques
b
2
c
1
3
e
a
2
b
4
3
3
e
1
4
c
1
d
Le problme du voyageur de commerce peut se reformuler comme un problme de cycle hamiltonien dans un graphe complet.
Figure 1.
centaines de villes (la puissance de calcul joue un rle trs secondaire dans ces performances
voir la discussion sur la complexit du Chapitre 2).
Les approches que nous allons dcrire s'noncent plus facilement sous la reformulation suivante
sur le graphe complet
comme cot
c(xy)
le
G passant par tous les sommets. La succession des premiers passages en chaque sommet
Kn . Rciproquement,
un cycle hamiltonien de cot minimum dans Kn induit une chane ferme de mme cot dans G.
Cela permet de conclure que le cycle hamiltonien de plus petit cot dans Kn induit une tourne
de cot minimum dans G.
ferme de
Kn = (V, E)
c(xy) + c(yz) c(xz)
: Le graphe complet
c : E R+
avec
avec
pour tout
x, y, z V .
consistant toujours se rendre la ville la plus proche non encore visite. Cette heuristique
s'appelle
nearest-neighbor.
122
5
6
4
7
2
7
2
3
6
6
4
4
Figure 2.
L'heuristique de Christods.
Cet algorithme utilise deux routines : celle de l'arbre couvrant de poids minimum, qui est
dcrite au chapitre sur la conception de rseau (Chapitre 12) ; et celle du couplage parfait de
poids minimum, non dcrit dans ce cours. Il sut de savoir qu'un
qui couvre tous les sommets d'un graphe. Si le graphe est pondr, et s'il existe un tel couplage,
on sait trouver un couplage parfait de poids minimum avec un algorithme d'Edmonds.
123
inegalite triangulaire :
c(M ) + c(M ) c(H)
j2
j1
H
j3
j6
j5
j4
Figure 3.
Dmonstration.
Soit
bien
X
eH
3
ce OP T.
2
M est 21 OP T .
un cycle hamiltonien optimal. J = {j1 , . . . , js } sont les sommets de degr impair de T ,
Soit H
. Considrons le couplage ji ji+1 pour i = 1, 3, . . ., ainsi
numrot dans l'ordre de parcours de H
que son complmentaire ji ji+1 pour i = 2, 4, . . .. La somme de leur poids est OP T , par
1
ingalit triangulaire. Par consquent, l'un des deux a un poids OP T . A fortiori, c'est le cas
2
pour M (car c'est le couplage de plus petit poids sur J ). La preuve est illustre Figure 3.
Pour cela, il faut prouver que le poids de
voisinage. Le
voisinage 2-OPT est le plus classique. On dit que deux cycles hamiltoniens C, C 0 sont voisins
voyageur de commerce par des mta-heuristiques. Il faut alors dnir la notion de
|C \ C 0 | = |C 0 \ C| = 2,
intgrer ce voisinage dans n'importe quel schma de mtaheuristique du type recherche locale
(mthode tabou, recuit simul,...).
Des gnralisations du voisinage
et consistent changer
2-OPT
k -OPT
avec
k 2,
recherches locales extrmement performantes, tout en restant prudant sur la taille du voisinage
explorer : un
21].
Kernigan [
124
k {2, 3}.
k -OPT,
avec en
en moins d'une minute sur une machine du commerce l'optimum d'instances jusqu'
1000 villes.
11.1.1.5. Formulation sous forme d'un programme linaire en nombres entiers. Rappelons
B o
qu'un vecteur d'incidence d'une partie A d'un ensemble B est le vecteur x {0, 1}
xe =
1
0
si
eA
sinon.
On peut modliser le problme du voyageur de commerce de faon trs compacte sous forme
d'un programme linaire en nombres entiers.
0x 1
eE
P e
x =2 vV
Pe(v) e
e(X) xe 2 X V, X 6= , V.
Dmonstration.
Soit
0x 1
eE
P e
e(v) xe = 2 v V,
les artes
e telles que xe = 1 forment une collection disjointe de cycles lmentaires couvrant tous
les sommets du graphe. Il sut donc de montrer qu'il n'y a qu'un seul cycle dans la collection.
C'est une consquence des ingalits
e(X) xe
pour tout
X V, X 6= , V .
Figure 4.
En eet, s'il
(32)
11.1.1.6. Branch-and-cut.
c(e)xe
0 xe 1
xe Z
P
x =2
Pe(v) e
e(X) xe 2
eE
eE
eE
vV
X V, X 6= , V.
On peut essayer d'en tirer une borne pour construire une mthode
c(e)xe
0 xe 1
eE
P
x
=
2
vV
Pe(v) e
e(X) xe 2 pour certains X V, X 6= , V.
eE
Dans les branch-and-bound, la qualit de la borne est cruciale. Une technique ecace, appele
branch-and-cut,
branch-and-bound en agrandissant le programme linaire qui fournit les bornes au fur et mesure
de l'exploration de l'arbre de branchement.
On rsout le programme (33). Supposons que l'on ait une solution
Il y a
1.
3 possibilits
x est le vecteur d'incidence d'un cycle hamiltonien.
du programme linaire.
e(X) xe
Cela se fait en
temps polynomial : c'est un problme de coupe minimum (voir le Chapitre 5). On ajoute
la contrainte viole au programme linaire, et on rsout le nouveau programme linaire.
3.
On ne trouve aucune ingalit de ce type qui soit viole, mais x n'est pas
entier. On a une borne pour le nud de l'arbre de branchement. Il faut brancher sur ce
nud et recommencer pour les ls.
relaxation la-
grangienne pouvait fournir de bonnes bornes, si une partie des contraintes est facile .
C'est le cas ici (Held et Karp 1970). On peut rcrire le systme linaire (32)
0 xe 1
xe Z
P
x =2
Pe(v) e
eE[X] xe |X| 1
eE
eE
vV
X V, X 6= , V.
E[X] dsigne l'ensemble des artes induites par X , i.e. l'ensemble des artes ayant leurs deux
X.
P
P
P
P
P
En eet 2
xe + e(X) xe = vX e(v) xe . Donc, si e(v) xe = 2 pour tout
eE[X]
P
P
v V , on a 2 eE[X] xe + e(X) xe = 2|X|, d'o l'quivalence des deux formulations. En
faisant jouer un rle particulier au sommet 1, on peut rcrire le systme sous la forme
extrmits dans
126
7
2
3
6
4
5
Figure 5.
Un 1-arbre.
0 xe 1
eE
xe Z
eE
P
x =2
Pe(1) e
x |X| 1 X {2, . . . , n}, X 6=
PeE[X] e
x
=n
PeE e
v {2, . . . , n}.
e(v) xe = 2
P
En oubliant les contraintes
e(v) xe = 2 pour v {2, . . . , n}, on obtient un systme
linaire qui dcrit les 1-arbres. Un 1-arbre est un arbre couvrant {2, . . . , n}, avec deux artes
supplmentaires quittant 1 (voir la Figure 5) et se calcule en temps linaire (la routine de calcul
des arbres couvrants de poids minimum est dcrite au Chapitre 12).
On a tout ce qu'il faut pour calculer une borne par relaxation lagrangienne. Le lagrangien est
L(x, ) :=
ce xe +
n
X
i=2
eE
e(i)
xe 2 .
max G()
Rn1
o
G() := 2
en posant
1 := 0,
X
iV
pouvoir calculer
min
L(x, )
soit encore
G() = 2
On sait calculer
i +
G() en temps
maxRn1 G()
X
iV
i +
min
est un 1-arbre
(cij + i + j ).
ijT
127
Thorme 11.1.4
11.1.1.8. Branchement.
le problme rsolu en un nud de l'arbre est de mme nature qu' la racine de l'arbre, laquelle
consiste en la rsolution du relch continu du problme de dpart. Dans le cas du voyageur
de commerce, ce n'est pas le cas. En un nud de l'arbre de branchement, on doit rsoudre des
tournes contraintes passer par certaines artes ou en viter d'autres, ce qui est
a priori
un problme plus gnral que le problme de dpart. Nous expliquons maintenant une faon
classique de traiter cette dicult.
La faon classique de brancher pour le voyageur de commerce est de choisir une arte
d'crire l'ensemble des solution
l'arte
e.
X = Xe (X \Xe ) o Xe
e,
et
SA,B = {S S : A S, B S = }
Rsoudre le problme au niveau du noeud
SA,B
avec
A, B E.
A,
et aucune de
B.
de calculer des bornes lorsqu'on branche. On pourrait se dire qu'il sut de calculer des
avec des artes prescrites (celles de
A)
B ),
1-arbres
d'algorithme simple qui eectue cette tche. Une petite astuce permet de pallier cette dicult.
On niveau d'un nud de l'arbre de branchement, on a donc un problme de voyageur de
commerce avec contraintes (ensemble d'artes prescrites et interdites). Une petite astuce permet
d'crire ce problme de voyageur de commerce avec contraintes , comme un problme de
voyageur de commerce sans contrainte, simplement en modiant la fonction de cot.
Si on pose
c(e)
c0 (e) :=
c(e) + C
c(e) + 2C
o
C :=
eE
c(e) + 1,
si
si
si
eA
e
/ AB
e B,
Les cycles hamiltoniens de SA,B sont exactement ceux dont le nouveau cot est (n+1|A|)C .
De plus, les cycles hamiltoniens dans SA,B ont un cot qui dire de l'ancien cot d'exactement
(n |A|)C .
On peut donc calculer des bornes pour un problme de voyageur de commerce non contraint,
avec la nouvelle fonction de cot, pour obtenir des bornes infrieures pour le problme avec
contraintes.
Tche : Trouver un chemin ferm de cot minimum passant par tous les sommets.
De mme que dans le cas non-orient, on peut reformuler la problme sur le graphe complet
orient (toute paire de sommets est relie par deux arcs de sens oppos).
128
c : A R+ .
aC
c(a)
soit
minimum.
Comme dans le cas non-orient, on a :
Thorme 11.1.5.
dicile.
NP-
Cela peut se retrouver partir du Thorme 11.1.1. En eet, en prenant un graphe nonorient, on peut ddoubler les artes pour en faire deux arcs parallles mais de sens opposs. On
se ramne alors au problme du voyageur de commerce sur un graphe orient, et si on avait un
algorithme polynomial le rsolvant, on en aurait galement un dans la version non-oriente, ce
qui contredit le Thorme 11.1.1.
11.1.2.2. Algorithmes.
cile.
Voici un rsum de la situation.
Complexit : pareil, c'est
NP-dicile.
1-arbre orient,
voir ci-
dessous.
Un
1-arbre orient
est un ensemble
r-arborescences).
Problme du postier
Donne : Un graphe G = (V, E) et une fonction de cot sur les artes c : E R+ .
Tche : Trouver une chane ferme de cot minimum passant par toutes les artes
une fois.
129
au moins
Ici,
peut tre vu comme la modlisation d'une ville, les sommets tant les intersections de
rues et les artes les portions de rues. Les poids peuvent tre le temps de parcours des rues. Le
problme est alors celui que se pose un facteur voulant dposer tout son courrier en un minimum
de temps.
11.2.1.2. Algorithme.
algorithme polynomial simple qui trouve la tourne optimale. Remarquons dj que dans le cas
o le graphe est eulrien, la question est triviale.
Sinon, on a la proprit suivante.
Lemme 11.2.1. La chane ferme de cot minimum qui passe par toutes les artes au moins
une fois passe au plus deux fois par chaque arte.
Dmonstration.
G = (V, E) le graphe. Soit une chane C passant par toutes les artes au
moins une fois. Pour chaque arte e, on construit des artes e1 , . . . , er correspondant chacun
0
0
des passages sur e. Notons G ce nouveau (multi)graphe. G est eulrien. On a donc cr des
copies de certaines artes de manire rendre G eulrien. Rciproquement, si on cre des copies
d'artes pour rendre G eulrien, on a la possibilit de parcourir le multigraphe en passant par
chaque arte du multigraphe une fois et une seule, et cela induit sur G une chane C passant
Soit
2p
G0
reprsentant de
Chercher la chane de
e,
avec
pN
et
qui passe moindre cot par toutes les artes consiste donc
Problme du postier
Donne : Un graphe G = (V, E) et une fonction de cot sur les artes c : E R+ .
P
Tche : Trouver F E tel que degF (v) = degE (v) mod 2 pour tout v V , et tel que eF c(e)
soit minimal.
Trouver F E tel que degF (v) = degE (v) mod 2 pour tout v V et tel que eF c(e)
soit minimal : On peut vrier que, si les c(e) 0, un tel F est constitu de chanes appariant
P
c(jj 0 ) =
sur chaque arte
jj 0
de
sur
J,
G.
On
et on met un cot
et
j0
K . Le couplage parfait de plus petit cot donne alors la solution (on sait
trouver un tel couplage en temps polynomial, comme indiqu dans le paragraphe sur l'heuristique
de Christods).
D'o
Thorme 11.2.2.
Figure 6.
11.2.2.1. Formulation.
rsolution exacte en temps polynomial, simple implmenter. En eet, un tel chemin est une
circulation x RA
+ de cot minimum, tudie au Chapitre 5, pour des capacits infrieures la = 1
et des capacits suprieures ua = + pour tout a A. (Rappelons qu'une circulation satisfait
la loi de Kircho en tous les sommets c'est un ot sans source ni puits). Rciproquement, si
on a une circulation
x RA
+
en vertu du Thorme 2.2.2, il existe un chemin ferm passant par chaque arc un nombre
xa
de
fois.
Thorme 11.2.3.
sa version oriente.
11.3. Exercices
11.3.1. Nombre de sommets de degr pair.
Les distances sont les distances euclidiennes ( vol d'oiseau ). Montrez que cette tourne est
optimale en vous inspirant de la Figure 7.
131
Figure 7.
11.3.4.
T -joins.
Soit
c:ER
(contrairement au cours, on
l'ensemble des
vT
A4B = (A \ B) (B \ A)).
1. Montrer que
2. Montrer que
3. Conclure que
est un
T -join
est un
si et seulement si
T -join
J4E
est un
(T 4T )-join.
si et seulement si
J4E
est
d.
T -joint
soit le cot.
11.3.5. Plus courte chane dans les graphes sans cycle absorbant.
Utiliser l'exercice
3
prcdent pour montrer que l'on sait calculer en O(n ) une plus courte chane dans les graphes
sans cycle absorbant (rappel : un cycle absorbant est un cycle de cot total
couplage parfait de cot min se fait en
< 0;
trouver un
O(n3 )).
des clients situs en des villes direntes. Il a x un rendez-vous pour chacun de ses clients,
i.e. pour tout client
tant
bi .
i,
ai ,
Il souhaite optimiser sa tourne (et en passant vrier que les contraintes ne sont pas
contradictoires). On suppose qu'il sait le temps qu'il lui faut pour aller d'une ville une autre.
Proposer une formulation sous la forme d'un programme linaire mixte (variables entires et
continues), qui, contrairement au problme du voyageur de commerce usuel, ne contient pas un
nombre exponentiel de contraintes.
v, w
Kn = (V, E)
sommets (n
Considrons l'ins-
s.
132
n,
an,
seconde,
heure,
jour,
semaine,
sicle :
n = 15 n = 30 n = 45.
5. Comment utiliser l'algorithme pour rsoudre le problme du voyageur de commerce (cycle
hamiltonien de plus petit cot) sur
Kn ?
133
CHAPITRE 12
CONCEPTION DE RSEAUX
Les rseaux sont omniprsents. Qu'ils soient routiers, ferrs, informatiques, lectriques ou
gaziers, ils ont souvent des rles stratgiques et conomiques cruciaux, et leur robustesse (i.e.
leur capacit assurer leur mission mme en cas de dfaillance locale) est une qualit souvent
recherche.
L'objet de ce chapitre est de prsenter quelques modles et algorithmes de base dans le
domaine de la conception de rseau robuste champ essentiel de la recherche oprationnelle.
Nous tudierons deux problmes :
celui de l'arbre couvrant de poids minimal : tant donn un graphe pondr, trouver un
arbre inclus dans ce graphe, de poids minimal, tel que tous les sommets soient relis par
l'arbre.
celui de l'arbre de Steiner de poids minimal, qui gnralise le problme prcdent : tant
donn un graphe pondr, trouver un arbre inclus dans ce graphe, de poids minimal, tel
que tous les sommets d'un sous-ensemble prdtermin soient relis par l'arbre.
arbre
Proposition 12.1.1.
arbre couvrant
un graphe
G = (V, E)
est un arbre
T,
et les artes de
fort.
1. Si on veut tre prcis, il faut encore prouver qu'un tel sommet existe. Cela a l'air vident,... mais il faut
parfois se mer des vidences en thorie des graphes. Pour le prouver, on prend un sommet quelconque de
l'arbre. On suit une chane partant de ce sommet en s'interdisant de repasser par un mme sommet. Par nitude
de l'arbre, la chane s'arrte en un sommet v . Si v est de degr 2, alors il existe une autre arte que par celle
par laquelle on est arriv dont l'autre extrmit est sur la chane. Or ceci est impossible, car il y aurait alors un
cycle sur l'arbre. Donc le sommet v est de degr 1.
Figure 1.
A
A
B
C
D
E
F
G
et le village
0 3 8 9 10 5 5
3 0 9 9 12 5 4
8 9 0 2 10 9 9
9 9 2 0 11 9 8
10 12 10 11 0 11 11
5 5 9 9 11 0 1
5 4 9 8 11 1 0
On veut trouver le rseau routier de distance totale minimale qui relie tous les villages, sachant
qu'un tronon relie toujours deux villages (il n'y a pas d'embranchement sur les routes).
On peut modliser le problme prcdent par un graphe complet
l'ensemble des villages et
lments de
V.
soit connexe.
Remarque.
est
des
w : E R+ .
P
F E tel que eF w(e) soit minimal et tel que le graphe
(V, F )
Kn = (V, E), o V
ij avec i 6= j
Le problme ci-dessus admet toujours une solution qui soit un arbre. En eet,
s'il ne l'tait pas, il y aurait ncessairement un cycle puisqu'il est connexe. On pourrait alors
supprimer une arte de ce cycle sans faire disparatre la connexit et sans dtriorer le poids
total puisque la fonction de poids est valeur
0.
136
Une autre application a dj t vue : les arbres couvrants apparaissent dans la relaxation
lagrangienne du problme du voyageur de commerce (borne du
1-arbre),
glouton
si chaque itration 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 mme pour l'algorithme glouton pour le sac--dos).
L'algorithme de Kruskal se dcrit de la manire suivante.
Trier les artes par poids croissant :
Poser
e1 , . . . , e m .
F := {e1 }, i := 1.
Rpter
i := i + 1.
F {ei }.
Faire
Thorme 12.2.1.
minimal.
Si
F {ei }
La preuve s'appuie sur le lemme suivant, illustr Figure 2. On dit qu'une fort
bonne
F :=
T =
F0
F = (V, F ) est
Soit F = (V, F ) une bonne fort, soit une coupe (X) (avec X V )
disjointe de F et e une arte de poids minimal dans (X). Alors (V, F {e}) est encore une
bonne fort.
Lemme 12.2.2.
Preuve du Thorme 12.2.1. L'algorithme de Kruskal ajoute chaque itration l'arte 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.2.2 s'applique.
Tout au long de l'algorithme, (V, F {ei }) est donc une bonne fort. En particulier la
dernire itration o la fort se transforme en arbre. Par dnition d'une bonne fort, cet arbre
est optimal.
Remarque.
Cet algoritme fonctionne quelque soit le signe des poids des artes. Dans l'exemple
introductif, on supposait que les poids taient tous positifs ; cela pour permettre de conclure que
le problme du graphe connexe couvrant de plus petit poids pouvait se ramener au problme
de l'arbre couvrant de plus petit poids. Ce dernier problme lui se rsout par l'algorithme de
Kruskal indpendament du signe du poids des artes.
137
1
2
Une bonne fort, qui reste une bonne fort lorsqu'on ajoute l'arte e (on
suppose que e est de poids minimal dans (X)).
Figure 2.
ensemble des sommets du graphe que l'on souhaite voir reli par un arbre. Curieusement, alors
que le problme de l'arbre couvrant de poids minimal est polynomial, celui de l'arbre de Steiner
est
NP-dicile.
appels
terminaux.
S.
Thorme 12.3.1.
sont gaux 1.
138
T0
de
G.
pour le poids
w
.
w.
Dmonstration.
l'arbre de Steiner
Soit
w(T
0)
w(T ).
T.
On a donc
maintenant un graphe eulrien que l'on peut parcourir en passant exactement une fois sur chaque
arte : cycle
C.
C.
: on parcourt
dans
On a nalement
C0
3
4
7
4
1
1
4
2
5
w
2
1
1
2
v
2
v
w
Figure 3.
de Steiner.
139
w(T
0 ) w(C
0 ) w(C) = 2w(T ).
assez astucieuse base sur la programmation dynamique (voir Chapitre 3) qui permet de
calculer un arbre de Steiner de poids minimum, quand le nombre d'lments de
grand.
En eet, si on pose pour
U V
et
x
/U
p(U ) := min{w(T ) : T
U },
p(U {x}) =
(34)
o
min
yV,$U 0 $U
dist(x, y) est la distance de x y , i.e. la longueur d'une plus courte chane de x y en prenant
comme longueur des artes (voir Chapitre 3 pour ces calculs de plus courts chemins).
Pour voir que l'quation (34) est vraie, supposons d'abord que
soit
soit
yU
y
/U
et
U 0 {y}
de degr au moins 2.
couvrant
U 0 := {y}.
U \ U 0 {y}.
x,
d'un arbre
ne soit pas une feuille. Dans ce cas l'quation est vraie pour
y = x.
Elements de preuve.
la complexit.
O(3s n2 ) vient du calcul de p(U ). Supposons que l'on ait calcul tous les p(U ) pour un
i
cardinal |U | = i. Le calcul d'un p(U ) pour une cardinalit |U | = i+1 se fait en n2 (interprtation
Ps1 i s
s
de l'quation (34)). La complexit totale est donc de l'ordre de
i=0 n2 i+1 = O(3 ns).
2
Le terme O(mn + n log n) vient du calcul des plus courtes distances.
Le terme
Une approche par la programmation dynamique peut donc tre pertinente si le nombre
de
12.3.4. Branch-and-cut.
140
Dmonstration.
Si
est vecteur d'incidence d'un arbre de Steiner, il est clair qu'il satisfait
P
T := {e E : xe = 1}. D'aprs l'ingalit e(X) xe 1, l'ensemble T est connexe.
T contient un cycle C , on peut trouver une arte e C telle que w(e) = 0, arte que l'on
Notons
Et si
On est exactement dans la mme situation que pour la formulation PLNE du problme du
voyageur de commerce. La relaxation continue lve le premier problme : la solution de ce
problme fournit une borne infrieure sur la solution optimale. Cela indique qu'une mthode de
branch-and-cut peut tre approprie. Pour rsoudre le programme linaire prcdent, on peut
utiliser une approche branch-and-cut trs semblable celle suivie pour le voyageur de commerce.
Pour pouvoir appliquer un branch-and-cut, il faut pouvoir trouver s'il existe
r
/X
et
X S =
6 tel que e(X) xe < 1. Cela se fait par une recherche
v r ot maximum pour tout v S (voir Chapitre 5).
X V
avec
de coupe minimum :
on recherche le
On a donc tout ce qu'il faut pour faire du branch-and-cut. L'algorithme suit le mme schma
que celui dcrit au Chapitre 11.
Dmonstration.
Si
est vecteur d'incidence d'un arbre de Steiner, il est clair qu'il satisfait
xv0 v := 1,
v0 ,
T := {e E : xe = 1}.
En ne
cot.
Comme d'habitude pour ce genre de problme, on peut avoir de meilleures bornes en utilisant
la relaxation lagrangienne, ce qui peut tre cruciale pour les problmes de grande taille. Il faut
donc se demander si la suppression de certaines contraintes du programme (35) rend le problme
soluble.
Il est clair que la suppression des contraintes
L(x, ) :=
X
eE
w(e)xe +
vV \S e(v)
max G(),
avec
On peut minorer
G() :=
P
P
P
min
eE w(e)xe +
vV \S
eG (v) v,e (xv0 v + xe 1)
s.c.
xe est le vecteur indicateur d'un arbre couvrant G0
qui peut se rcrire...
G() :=
G
P0
o l'arbre couvrant
uv E
G()
0
et wv v
0
:=
v,e + poids
G0
vV \S e(v)
e(v) v,e .
0 := w
wuv
/ S) + v,uv 1(v
/ S)
uv + u,uv 1(u
si
se calcule donc aisment par l'algorithme de Kruskal, ainsi que ses sur-gradients. On
G(),
Pour le branchement, c'est simple : les solutions ralisables associes un nud de l'arbre de
branch-and-bound correspond l'ensemble des arbres avec un sous-ensemble d'artes impos.
Il est en eet facile de voir que trouver l'arbre couvrant de poids minimum avec des artes
imposes 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
problme du Steiner tree s'appuient sur la remarque suivante : Une fois xs les sommets
de l'arbre de Steiner (on a bien sr
couvrant de poids minimum.
T V 0 ),
V0 V
V0
de
: on dit que
V0
est
voisin
de
V 00
si l'on est
V 00 := V 0 \ {v 0 }
pour un
V 00 := V 0 {v 00 }
v 0 V 0 , (drop)
pour un
v 00 V \ V 0 (add)
ou
V 00 := V 0 \ {v 0 } {v 00 } (swap).
Thorme 12.4.1.
NP-dicile.
Figure 4.
Remarquons que l'arbre de Steiner de plus petite longueur est le rseau 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 rseau, voir Figure 4.
Les heuristiques de rsolutions, les algorithmes, etc. s'appuient sur la proprit suivante. On
appelle
point de Steiner
[
CP
A
dans le triangle,
fassent tous trois 120 . La preuve de ce fait est un exercice classique de gomtrie plane
en les points A, B et C .
[A, B]
et
[B, C].
Tout comme le problme de l'arbre de Steiner sur un graphe, le problme de l'arbre de Steiner
euclidien est trs tudi. On connat des branch-and-bound ecaces et de bonnes heuristiques
et mtaheuristiques du style recherche locale.
Un autre problme trs tudi avec des rsultats semblables est le problme de l'arbre
de Steiner Manhattan , en ne s'autorisant que les segments horizontaux et verticaux. Une
application rside par exemple dans la conception des circuits intgrs.
12.5. Exercices
12.5.1. Un rseau d'eau.
canalisation d'eau au moindre cot un chteau d'eau. Voir Figure 5. Sur la gure, les liaisons
possibles sont indiques par la prsence d'un lien entre deux pavillons. Le cot d'ouverture d'une
liaison est indiqu proximit de ce lien.
Mettez en vidence un rseau de moindre cot sur la gure, indiquez son cot et justiez
l'optimalit de la solution que vous proposez.
143
Ch
ateau deau
Figure 5
w : E R.
Considrons un graphe
G = (V, E)
Considrons un graphe
strictement positifs. Peut-on trouver en temps polynomial l'arbre couvrant dont le produit des
poids est minimal ?
w : E R.
Considrons un graphe
G = (V, E) muni de
poids minimal ?
Rappelons qu'un
V V
et
H = (V 0 , F )
avec
pij .
d'interception ?
12.5.6. Matrodes (pour les lves ayant un got pour les maths).
ensemble ni et soit
144
E.
Si
satisfait
Soit
un
I I et J I , alors J I .
(ii) si I, J I et |I| < |J|, alors I {z} I
alors (E, I) est appel un matrode.
(i) si
1. Soit
G = (V, E)
pour un certain
est un matrode.
(E, F)
z J \ I.
2. Soit
3. Soit
(appel
4. Soit
I les sous-ensembles
(E, I) est un matrode
et soit
matrode matriciel).
de transport de faon pouvoir assurer des livraisons depuis des sources jusqu' des destinations.
Pour chaque tronon direct
(u, v),
on connat le cot
c(u, v)
capacit unitaire. Comment construire le rseau dont l'tablissement soit de cot minimum ? On
suppose que l'on connat pour les sources, l'ore et pour les destinations, la demande. Modliser
ce problme comme un problme de ot.
D = (V, A).
t1 , . . . , tk . Le bien i circule de la source si
i
la destination ti . Ce bien est modlis par un ot x : A R+ .
0
On doit slectionner maintenant un sous-ensemble A de A tel que chaque bien puisse circuler
s1 , . . . , s k
et des destinations
de sa source sa destination.
Le cot de slection de l'arc
bien
se note
cia .
fa
se note
On veut trouver
A0
1. Modliser ce problme sous forme d'un programme linaire en nombres entiers, en les
variables
xia ,
aA
pour
et
i = 1, . . . , k ,
et
ya ,
pour
a A,
ya
2. Proposer une relaxation lagrangienne qui permette de calculer de bonnes bornes infrieures.
p,
On se donne un
cbles. On veut crer un rseau connectant l'ensemble des terminaux la centrale. Une
connexion consiste soit relier deux terminaux entre eux, soit connecter un terminal la
centrale. Comme la centrale a au plus
connexions
c
K , de
un vecteur de cot
arbre couvrant de
K = (V, E),
avec
V = T {p}.
On a donc
145
n'excde pas
s.
Pour un ensemble
Notons
B E,
x {0, 1}E
l'ensemble
x {0, 1}E
est le
vecteur indicateur
de
si
xe = 1 e B.
K.
On cherche
P
c x
PeE e e
e(p) xe s
xX
(i)
(ii)
La mthode que l'on va suivre consiste utiliser la relaxation lagrangienne. Ici, non seulement elle permettra d'obtenir des bornes infrieures, mais elle permettra galement de trouver
l'optimum.
1. Ecrire le lagrangien
de la contrainte (i), avec
On dnit
sation. On
2. A
lagrangienne
G() ?
3. Montrer que si
plus
s,
alors
x0
dont le degr
s.
4. On veut trouver
aux valeurs de
sur le
plus
est la valeur de
en laquelle
est maximal.
en
xi
L(xi , i ) = L(x , i ).
7. En dduire que
G(i ) =
eE ce xe et que
On est donc dans une situation o la borne fournie par la relaxation lagrangienne concide avec
l'optimum.
146
CHAPITRE 13
OUVERTURE
En conclusion, signalons les outils de la recherche oprationnelle ainsi que des domaines la
frontire que nous avons simplement voqus, par manque de temps et de place, mais qui sont
extrmement importants.
ces techniques, les mthodes de dcomposition traitent des cas o le nombre de variables est
trs grand, voire exponentiel en la taille du problme. Trs schmatiquement, dans le cas o
le problme se formule sous la forme d'un programme linaire
la faon suivante (on parle alors de
gnration de colonnes
(P ),
(D0 )
(P 0 ) ;
(P 0 )
(D)
de
(P )
auquel
(P ),
et
(D). On slectionne
alors une des contraintes violes (par exemple, la plus viole, ce qui ncessite souvent
un autre problme d'optimisation), on ajoute la variable correspondante
(P 0 )
ce qui
min(cT x : x P Zn ),
est un polydre.
Les mthodes de coupes consistent ajouter des contraintes linaires qui sont vries par tous
les points entiers de
P , mais pas par tous les points de P . Comme on cherche une solution entire,
on ne se prive pas de solution, et la relaxation continue est meilleure. Il existe des techniques
de gnration automatique de contraintes linaires (coupes de Dantzig, Gomory, Chvtal,...), on
peut aussi trouver de telles coupes par des mthodes
ad hoc,
naire est la programmation convexe, dont les contraintes et l'objectif sont convexes. Dans le
domaine du transport de gaz ou dans les rseaux tlcom par exemple, on rencontre souvent
des problmes du type : on se donne un graphe orient, avec des contraintes de capacit, et des
cots
On dispose de nombreux algorithmes ecaces (et trs souvent polynomiaux) pour rsoudre ces
problmes.
r-
solue en temps polynomial par les points intrieurs. Elle concerne le cas o les vecteurs des
problmes de programmation linaires, tant ceux qui dnissent l'objectif ou les contraintes que
les variables, sont remplacs par des
13.1.4. Simulation.
d'un
modle
original
l'aide
qui en abstrait les lments essentiels, dans le but de tirer des conclusions sur ce
phnomne.
L'intrt est vident quand
le phnomne original est dicile reproduire volont (conditions particulires diciles
remplir, cot, dure, etc.)
la modlisation sous forme problme ne se rsout pas facilement (par exemple, les problmes
biniveaux compliqus ; ou en physique : quations Navier-Stokes)
On distingue les simulations
temps continu
et ceux
vnements discrets.
La simulation peut tre utile par exemple pour dimensionner une otte de vhicule de transport la demande, compte tenu de la fonction d'utilit des agents, de la congestion, etc. ; pour
proposer un nouveau systme logistique, avec des tarications variables ; pour tudier une chane
d'approvisionnement complexe ; etc.
La simulation est souvent couple avec des techniques plus classiques de recherche oprationnelle, comme on le dvine aisment la lecture des exemples ci-dessus.
science de la re-
Donne
d'un Problme : les donnes ne sont pas toujours faciles obtenir, ou peuvent tre
entaches d'erreurs.
et de communication. Il y a des
d'obtenir un
clients,
ressources
limites, an
service. Ces demandes concurrentes engendrent des dlais et donc des les d'attente
de clients.
Les mesures de performance sont en gnral :
148
et
depart
service
arrivee
attente
Figure 1.
et
et si la dure de service suit une loi exponentielle, le nombre de personnes dans la le est une
chane de Markov en temps continu. Notons que pour avoir un rgime stationnaire, il faut que
/ < 1.
En toute gnralit, il n'y a pas de raison que la le d'attente puisse tre modlise
par une chane de Markov, et leur tude peut devenir extrmement dicile.
Les applications sont nombreuses : dimensionnement des caisses de supermarch, des services
hospitaliers, des standard tlphoniques, serveurs informatiques, etc.
Dans ces deux derniers problmes, on veut partager un objet (un gteau ou un collier) et
l'on veut que toutes les personnes peroivent le partage comme juste dans un certain sens,
mme si elles n'ont pas la mme fonction d'valuation.
2. lorsque la fonction objectif contient un terme qui rsulte d'un terme rponse conomique. Par exemple, lorsqu'on veut concevoir un rseau routier, on est oblig de se demander par o va s'couler le ot des usagers. Mais le ot est le rsultat de ce que chaque
personne dcide 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
biniveau.
problme
Dans ce second cas, il faut souligner que les choses sont diciles, et peu intuitives comme en
tmoigne le clbre paradoxe de Braess.
Considrons les rseaux de la Figure 2. Un ot de valeur
1/2
1/2
em-
d'une autoroute au milieu dtriore tout : on peut vrier qu' l'quillibre de Nash la totalit
de ot unitaire suit la route
s, v, w, t.
c(x) = x
c(x) = x
c(x) = 1
c(x) = 1
c(x) = 0
s
s
t
c(x) = 1
t
c(x) = 1
c(x) = x
Figure 2.
enchres.
c(x) = x
La question traite par le yield management concerne la trajectoire suivie par le tarif
d'une prestation en fonction de la date o elle est achete : on peut maximiser le bnce en
suivant une trajectoire tenant compte des direntes fonctions d'utilit des clients potentiels.
Dans les problmes d'enchres, utilises en particulier par les prestataires logistiques, on se
demande quelles rgles mettre en place pour maximiser le prix auquel est vendue
prestation.
150
in ne
la
ELMENTS DE CORRECTION
Exercice 2.6.5.
Considrons le graphe
et dans lequel une arte relie deux formations s'il existe un employ devant suivre ces deux
formations. Enn, 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. Rciproquement, 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.
les ges possibles de la machine en dbut d'anne. Les priodes sont les annes. On s'intresse
aux quantits
(t, k) = prot
On souhaite trouver
(t, k)
tme
k.
maxk{1,2,3} ((5, k) + pk ).
(1, k) =
0
b0 c0
pour tout
pour
k {2, 3}
k = 0.
(t + 1, k + 1) = (t, k) + bk ck
(t + 1, 1) =
t
k
1
2
3
k {1, 2}
k{1,2,3}
si
t {1, 2, 3, 4}
10000) = 200000.
si
Une stratgie optimale consiste garder la machine deux ans, puis la vendre
Exercice 3.4.10.
1. On peut passer de n'importe quel point n'importe quel autre point. On peut vrier
exhaustivement que l'on peut atteindre n'importe quel tronon depuis le point suprieur gauche.
On peut de plus imposer l'orientation du wagonnet : on peut partir du point suprieur gauche vers
la droite, et suivre un parcours ferm qui ramne la wagonnet au mme point avec l'orientation
oppose ; quitte ajouter ce parcours ferm au dbut du trajet, on peut donc xer l'orientation
en n de trajet.
2. Soient
et
les deux points particuliers. On peut arbitrairement dire que les sommets
associs aux tronons sont les milieux physiques des tronons. On les relie conformment
l'nonc. On relie
et
ne sont spars par aucun milieu de tronon. On obtient donc le graphe dont la construction est
prcise dans l'nonc, avec en plus deux sommets particuliers
sont les distances correspondantes dans le rseau. On peut appliquer l'algorithme de Djikstra
pour calculer la chane de plus petit cot dans ce graphe, qui correspond au trajet le plus court
dans le rseau.
avec des orientations xes, on peut donc le faire en calculant une chane de plus
Exercice 3.4.11.
1. On considre le graphe orient
valles
de
et
C)
J.
les sommets des chemins lmentaires sont prcisement les sous-ensembles d'intervalles deux
(I, X)
sous-ensemble d'intervalles de
plus long chemin de
avec
dynamique (le graphe tant acircuitique). Pour se ramener totalement au cas du cours, on peut
galement ajouter un sommet
chercher le chemin de
(Y, I)
avec
I C
0,
et
2. Une demande de location se modlise par un intervalle de la droite relle dont les extrmits
sont les debut et n de la location, pondr par la gain qui serait obtenue en satisfaisant cette
demande. Maximiser le gain revient alors chercher le sous-ensemble d'intervalles disjoints (les
locations ne pouvant se recouvrir) de plus grand poids.
Exercice 5.3.12.
1. Considrons le graphe
arc
(u, v)
si
v Yu .
D = (V, A)
+
tel que (X
D
152
N
O
E
S
Figure 3.
3. On note
:= V \ X .
X
donc
ua =
cv
(v, t)
et ceux de la forme
cv =
vXV
X
vV +
cv
avec
v X.
On a
cv .
vX
vV + cv .
une
s -t
C :=
X
+
vXV
a +
(X{s})
4. Posons
X est ferm,
(s, v) avec v X
Comme
un ferm de
coupe de
de valeur maximale
de capacit
Exercice 6.6.3.
il sut de trouver
au plus un lment de
et
P.
R de
cardinalit
la cardinalit
ne soient jamais
Ces ensembles
4.
de lignes ou
contient
Le cas gnral est polynomial. En eet, ce problme se modlise sous la forme d'un graphe
biparti de la faon suivante :
les sommets sont les lignes d'une part et les colonnes d'autre part, une arte relie la ligne
la colonne
et
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
primtre du rectangle), et
O( nm)
Exercice 7.4.2.
153
t 1,
t,
2. Aux contraintes dcrivant la dynamique du stock, il faut ajouter les contraintes de capa-
cit
PT
P 1
+ Tt=1
s t yt
xt yt + yt1 = dt
xt Pt
xt 0
yt 0
PT
t=1 pt xt
t = 1, . . . , T
t = 1, . . . , T
t = 1, . . . , T
t = 1, . . . , T 1.
x = (8, 1, 3, 1)
ou
x = (9, 0, 4, 0),
ou
= pt
(v, wt ),
= Pt ,
=0
et un cot
et
les arcs
Le
pour tout
6. On a
pour
k, t.
P
PT 1
+ K
k=1
t=1 skt ykt
xkt ykt + yk(t1) = dkt
xkt Pkt zkt
PK
k=1 zkt 1
zkt {0, 1}
xkt 0
ykt 0
PK PT
k=1
PK
t = 1, . . . , T ; k = 1, . . . , K
t = 1, . . . , T ; k = 1, . . . , K
t = 1, . . . , T
t = 1, . . . , T , pour k = 1, . . . , K
t = 1, . . . , T ; k = 1, . . . , K
t = 1, . . . , T 1 ; k = 1, . . . , K.
k=1 zkt
et
154
G(, ) =
PT
t=1 t +
min
P
K PT
k=1
t=1 pkt xkt
s.c.
PK PT 1
k=1
t=1
t = 1, . . . , T
t = 1, . . . , T
t = 1, . . . , T
t = 1, . . . , T
skt ykt +
PK PT
k=1
; k = 1, . . . , K
; k = 1, . . . , K
; k = 1, . . . , K
1 ; k = 1, . . . , K,
G(, ) =
PT
t=1 t +
PK
min
k=1
P
T
t=1 pkt xkt
PT 1
t=1
s.c.
skt ykt +
PT
t = 1, . . . , T
t = 1, . . . , T
t = 1, . . . , T
t = 1, . . . , T
k,
PT
P
T 1
T
(
P
)z
s
y
+
p
x
+
t
t
t
t
t
t
t
t
t=1
t=1
t=1
; k = 1, . . . , K
; k = 1, . . . , K
; k = 1, . . . , K
1 ; k = 1, . . . , K.
P
min
xt yt + yt1 = dt pour t = 1, . . . , T
zt {0, 1}
t = 1, . . . , T
xt 0
t = 1, . . . , T
yt 0
t = 1, . . . , T 1.
s.c.
zt = 0 si t t Pt 0 et zt = 1 si t t Pt < 0.
valeur de zt peut tre xe indpendament de x et
:
Min
s.c.
P
T
t=1 pt xt
PT 1
t=1
st yt
xt yt + yt1 = dt t = 1, . . . , T
xt 0
t = 1, . . . , T
yt 0
t = 1, . . . , T 1.
qui est prcisment le problme de la premire partie, sans les capacits de production. C'est
bien un problme de
b-ot.
x , y
et
qui rsolvent
G(, ).
et donc
trouver de bonnes bornes infrieures notre problme de dpart. Tout est en place pour un
branch-and-bound.
Exercice 7.4.3.
1.
Min
s.c.
Pn PT
i=1
(xi, xi, 1 )
xi, 1
xi,
Pn
i=1 mi (xi, xi, 1 )
xi,
xi,0
xi, xi, 1
=1 ci,
xi,
xj,
M
{0, 1}
0
i {1, . . . , n} ; {1, . . . , T }
i {1, . . . , n} ; j Yi ; {1, . . . , T }
{1, . . . , T }
i {1, . . . , n} ; {0, 1, . . . , T }
i {1, . . . , n}
(ii)
(iii)
(iv)
(v)
(i)
155
et
Yi .
Yi
soit infrieure
M ,
comme attendu.
0 =1 M 0 est la masse maximale qui a pu tre extraite sur les annes de 1 . Si la masse
de Yi et du bloc i est strictement suprieure, forcment le bloc i ne peut tre extrait au cours
de l'anne ou avant.
2.
4. La suppression des variables indices par des bonnes paires rduit le nombre de variables du
programme linaire. Cela rduit forcment sa complexit. L'ajout des contraintes induites par
des bons triplets ne changent pas les solutions entires du programme linaire, mais diminue la
valeur de la relaxation continue, ce qui amliore la qualit de la borne utilise dans le branch-andbound on est dans un problme de maximisation et donc rduit potentiellement le nombre
de branchements.
Exercice 8.3.3.
g
et
ag0 ag .
et
et notons
respectivement le plus petit et le plus gros objets qui soient placs. S'ils ne sont pas mis
Comme
ap0 + ag 1,
p0
on a
ap0 + ag0 1
et
solution optimale dans laquelle le plus petit et le plus gros objets placs sont ensemble dans un
conteneur. Par induction, on peut montrer qu'en triant les
ai
petit objet courant avec le plus grand possible, on obtient une solution optimale en
Exercice 9.4.3.
O(n log(n)).
xij (resp. yij ) la part de la demande du client j desservie par l'entrept forward
(resp. reverse) i. Notons ui (resp. vi ) la variable binaire codant l'ouverture d'un entrept forward
(resp. reverse) i.
1. Notons
Min
s.c.
P
P
(fi ui + ri vi + jJ cij hj (xij + j yij ))
iI
P
x = hj
PiI ij
y = j hj
PiI ij
x bi ui
PjJ ij
jJ yij ei vi
ui , vi {0, 1}
xij , yij R+
jJ
jJ
iI
iI
i I, j J
i I, j J.
Ce programme linaire est dcomposable en deux sous-problmes indpendants : l'un avec les
xij
et
ui
yij
2. En ajoutant la variable
zi
et
vi .
sont tous deux ouverts en i, on peut modliser un gain la mutualisation de la manire suivante :
156
Min
s.c.
En eet, si
objectif,
zi
ui
P
P
(f u + ri vi si zi + jJ cij hj (xij + j yij ))
PiI i i
x = hj
PiI ij
iI yij = j hj
zi ui
zi v i
P
x bi ui
PjJ ij
y
jJ ij ei vi
ui , vi {0, 1}
xij , yij R+
et
vi
jJ
jJ
iI
iI
iI
iI
i I, j J
i I, j J.
ui
et
vi
la fonction
(zi , xij , yij ) sont automatiquement xes, puisqu'on cherche minimiser la fonction objectif. Les
xij
et
et
yij
sont alors le rsultat d'un problme de transport sur le graphe biparti complet avec
Par consquent, une faon compacte de coder les solutions consistent ne considrer que les
couples
ds que
ou
on passe de
u0
drop, add
v = v0
ou
swap
dnies en cours,
Avec une telle dnion 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 oprations simultanment sur
et
v,
mais alors il
faut dmontrer, ce qui n'est pas immdiat, que l'espace des solutions est bien connexe...
4. Cela ne change rien, car les
hj , j hj , bi , ei
Exercice 9.4.4.
1. On introduit la variable
galement la variable
yij
xi
qui vaut
si l'entrept
est ferm et
s.t.
Pn Pn
i=1P j=1 cij yij
qj + ni=1 yij 1
Pn
j=1 yij = qi xi
yij 1 xj
Pn
i=1 xi = k
xi {0, 1}
yij 0
157
sinon. On introduit
i l'entrept j . Le problme
Min
j {1, . . . , n}
i {1, . . . , n}
i, j {1, . . . , n}
i {1, . . . , n}
i, j {1, . . . , n}.
Pn
i=1 qi
nk
: il faut simplement
branch-and-bound.
Le principe est de
procder implicitement l'numration exhaustive de toutes les solutions. Une borne infrieure,
calcule ici par relaxation linaire, permet d'viter de calculer la valeur exacte d'un grand nombre
de solutions. Puisque le problme est
mation linaire. Mieux encore, il peut se rsoudre par un algorithme de ot de cot minimum.
Une fois xs les
0
et F comme tant voisins si
pivot,
|F \
F 0|
|F 0
F {1, . . . , n}
\ F | = 1.
avec
|F | = k .
F
opration de
On dnit
Exercice 9.4.5.
1. Prenons un graphe
G = (V, E)
dominant
on pourrait alors s'en servir pour tester l'existence en temps polynomial de dominant de taille
NP-complet.
sinon. Si plusieurs sites sont les plus proches, on en choisit arbitrairement un. Enn, on pose
h=
temps maximum pour qu'une commune soit atteinte par une ambulance. Cette solution est
Le problme et le programme linaire ont donc mme valeur optimale et on peut passer
directement d'une solution du problme une solution du programme linaire et vice-versa.
158
3. En notant
h+
Min
X
XX
(s )|C|ys +
s xs,c
sS
sS cC
s.c.
sS
ys K
(i)
xs,c = 1
sS
ts,c xs,c h
xs,c
ys
cC
(iii)
sS; cC
(iv)
{0, 1} s S ; c C
(v)
{0, 1} s S
(vi)
h R+
4. Les variables
et
(vii)
y,
on
par valeurs de
et
min h +
XX
s xs,c
sS cC
s.c.
xs,c = 1
sS
ts,c xs,c h
xs,c
cC
(iii)
sS; cC
(iv)
{0, 1} s S ; c C
h R+
et
min
(v)
(vii)
X
(s )ys
sS
s.c.
X
sS
ys K
ys
indpendament.
(i)
{0, 1} s S
(vi)
s
ys = 0
ys = 1
pour les
premiers
s,
et
Optimiser le premier programme est presque aussi simple. Noter que les
l'optimum, (iv) est une galit. On essaie successivement dans
sont positifs. A
159
SC
valeurs de
(s, c)
pour lequel
xs,c = 1.
petite. Complexit
O(S 2 C 2 ).
RS ,
on sait calculer
G()
et ses surgradients en
Exercice 10.4.3.
la dure de la tche
G(),
fournis-
j.
pj
manire ce que
w1
w2
wn
...
.
p1
p2
pn
et
wj 0
pj 0 . En inversant l'ordre de ces deux tches, on ajoute la
wj
0
suivie d'une tche j telles que
pj
est donc obtenu en ordonnant les tches dans l'ordre de leur indexation.
Exercice 10.4.8.
et
des tches, et le dchargement et le chargement comme des oprations, on est exactement dans
le cas d'un problme de ow-shop 2 machines, 15 tches et minimisation du makespan, ce qui
se rsout en temps polynomial (et mme la main) par l'algorithme de Johnson. Les dures des
oprations sont donnes par le temps qu'il faut pour dcharger ou charger les botes.
Ici la solution est de 91 minutes. On terminera donc au plus tt 7h31.
Exercice 11.3.7.
1. Pour
(X, v)
(V, v)
pour tout
vV
s,
s).
y en a
k=1
(X, v),
|X| 1
(nombre de
possibles dans
n1
X
k=1
n1
k(k 1) = (n 1)(n 2)2n3 .
k
(n 1)!(n 1) n!
2n
n = 15, on compte 7450 472 oprations, ce qui se fait en moins d'une seconde.
n = 30, on compte 1.09 1011 oprations, ce qui se fait en 1.09 105 secondes,
30 heures. On ne peut rsoudre cette instance en 1 jour, mais en une semaine oui.
n n
,
e
4. Pour
Pour
environ
160
soit
Ch
ateau deau
Figure 4
Pour
263
n = 45,
on compte
8.32 1015
8.32 109
Exercice 12.5.1.
(V, v) + c(vs)
pour tout
v,
pour tout
v.
v
/ V.
Il sut
l'arbre couvrant de plus petit poids. Il y a plusieurs arbres possibles. L'un est donn Figure 4.
Le cot optimal est
35.
Exercice 12.5.9.
P
1.
L(x, ) =
2. A
cot
eE ce xe +
P
e(p) xe s
temps polynomial.
3. On a alors
0
e(p) xe
s 0.
Donc
G(0) =
Par ailleurs,
gal
x0
X
eE
ce x0e
X
eE
ce x0e +
X
e(p)
est un arbre couvrant, satisfaisant les contraintes de l'nonc et dont le cot est
G(0) borne infrieure du problme. C'est donc une solution optimale pour notre problme.
161
4. Quand
varie,
ne change que lorsque l'ordre obtenu en classant les artes par cots
croissants change (algorithme de Kruskal). Cet ordre ne peut changer que lorsque une arte
f (p)
(e, f )).
On peut maximiser
de Kruskal.
e(p) xe
on a
> s.
N
G() en
appliquant au plus
fois l'algorithme
< , on a
X
X
X
X
xe s min L(x, ) = G().
xe s
ce xe +
G() =
ce xe +
5. Si
< i ,
e
/ (p),
1
2
2 |T | (|T | 1) (en comptant le nombre de
eE
eE
e(p)
xX
X
X
X
X
G(i ) =
ce xe i + i
xe i s
ce xe i +
xe i s min L(x, ) = G().
G()
e(p)
eE
eE
e(p)
xi
cas. Pour
est de degr
en
p,
e(p)
xX
G() G(i ).
lgrement infrieur
i ,
le degr de
a deux arbres couvrant optimaux d'un graphe pondr, on peut progressivement substituer les
artes de l'un par les artes de l'autre, tout en maintenant le caractre optimal. En procdant
une telle transformation de
xi ,
question.
P
G(i ) = L(x , i ) et que le degr de x en p est gal s, on a G(i ) = eE ce xe .
Par ailleurs La solution x est une solution ralisable notre problme, et dont le cot concide
avec celui d'une borne infrieure (en l'occurence G(i )). C'est donc une solution optimale.
7. Comme
162
BIBLIOGRAPHIE
Network ows,
Local search
33
(2004), 544562.
[3] P. Brucker,
Computing
40
(1988), 353359.
[4] V. Chvtal,
Linear programming,
62 (1993), 261275.
ow problems,
19 (1972), 248264.
American Ma-
completness.
np-
24 (1995), 222231.
cycles,
36 (1985), 873886.
zation,
[15] B. Hajek,
(1991), 311329.
[16] A. Hertz and D. De Werra,
Computing
39
(1987), 345351.
Tech. report,
Optimal two- and three-stage production schedules with setup times included,
1 (1954), 6168.
23 (1978), 309311.
Discrete Mathe-
problem,
Operations Research
21 (1973), 498516.
Sringer, Berlin
tions Research
[24] T. Terlaky,
Research
34 (1986), 250256.
164
Opera-
ANNEXE
Quelques socits
Roadef (www.roadef.org) : socit francaise de recherche oprationnelle et d'aide la dcision.
Euro (www.euro-online.org) : associations europennes des socits de recherche oprationnelle.
Informs (www.informs.org) : Institute for Operations Research and the Management Sciences.
C'est la plus grande socit professionnelle dans le domaine de la recherche oprationnelle.
Ressources en ligne
24h Operations research.
Une liste d'outils open-source logiciels pour la Recherche Oprationnelle : NEOS : Server for optimisation (http ://www-neos.mcs.anl.gov) Propose des serveurs de logiciel R.O
utilisables en ligne via des formats de modlisation standard (AMPL, ...)
Outils par ordre alphabtique 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 (cration de contraintes...) en C++.
GLPK (http ://www.gnu.org/software/glpk/) : La bibliothque Glpk est livre avec un
solveur autonome (glpsol), capable de traiter des problmes linaires (continus ou en nombre
entier) par des mthodes de simplexe ou de Points Intrieur. Ces problmes peuvent tre
modliss dans dirents langages, dont l'excellent GMPL (clone de AMPL).
Page RO de Google (http ://code.google.com/p/or-tools/) : Google a dvelopp pour ses
besoins propres un certain nombre d'outils de recherche oprationnelle. Sur ce site, ils sont
proposs en open-source.
GUSEK (http ://gusek.sourceforge.net/gusek.html) : le solveur GLPK avec une interface ;
pour Windows.
Graphviz (http ://www.graphviz.org/) : Logiciel permettant d'acher automatiquement
un graphe partir de formats de description textuels simples.
LP_Solve (http ://groups.yahoo.com/group/lp_solve/) : autre solveur de programmation
linaire.
LocalSolver (http ://www.localsolver.com/) : solveur permettant de modliser et rsoudre
des problmes d'optimisation discrte par recherche locale ; dvelopp par l'e-lab de Bouygues.
Operations Research - Java object (http ://OpsResearch.com/OR-Objects) Librairie JAVA
pour (petits) problmes de R.O. Utilisation gratuite, mais sources non accessibles. Ne semble
plus maintenue, mais reste intressante pour les API.
QSopt-Exact Home Page (http ://www.dii.uchile.cl/ daespino/) Solveur linaire avec calculs
exacts (car rationnels), bas sur la librairie GMP (Gnu Multi Precision)
TSP (http ://www.tsp.gatech.edu/index.html) : le site de rfrence sur le TSP. De la documentation, des solveurs, interfaces, jeux, etc.
SCILAB(http ://www.scilab.org/) : L'environnement de calcul scientique open-source de
rfrence.
SCIP (http ://scip.zib.de/doc/html/index.html) : Peut-tre un des meilleurs logiciels libres
actuels. Il possde de plus une librairie permettant une implmentation simple des branchand-cuts.
168
169