iii
Table des MaTières
avanT-ProPos .........................................................................................
vii
inTroducTion À la recherche oPeraTionnelle ...................................
ix
1 sTruc Tures ordon nées aPPli ca Tions des Treillis
eT de l ’ algèbre de boole en recherche
oPé ra Tion nelle .................................................................................
1
1.1 NotioNs sur les struc tures ordoNNées .............................................
1
1.2 repré seN ta tioN eNsembliste des algèbres de boole.
appli ca tioN à la logique élé meN taire .................................................
11
1.3 l’algèbre de boole biNaire ...............................................................
19
1.4 appli ca tioNs élé meN taires .................................................................
27
2 noTions de coMPlexiTé .................................................................. 42
2.1 complexité des algorithmes .............................................................
42
2.2 complexité des problèmes .................................................................
47
3 élé MenTs de la Théo rie des graPhes : défi ni Tion, concePTs
essen Tiels ; Par cours des graPhes .................................................. 59
3.1 élé meNts de la théo rie des graphes ..................................................
59
3.2 par cours des graphes ........................................................................
70
4 aPPli ca Tions des graPhes à la recherche
oPé ra Tion nelle ................................................................................ 99
4.1 NotioNs de pro gram ma tioN dyNa mique (prd) ..................................
99
4.2 appli ca tioNs aux che miNs opti maux ................................................... 104
4.3 pro blèmes d ’ ordoN NaN ce meNt eN ges tioN de pro jets ........................ 114
4.4 pro blème du flot de valeur maximale .............................................. 128
4.5 flot de valeur maximale à coût miNi mal.......................................... 134
4.6 pro blèmes d ’ affec ta tioN ................................................................... 139
4.7 NotioNs d ’ arbre et d ’ arbo res ceNce .................................................. 144
4.8 appli ca tioNs aux arbres opti maux ..................................................... 146
4.9 les pro grammes de traN sport............................................................ 149
4.10 recherches arbo res ceNtes .............................................................. 163