[PDF] Précis de recherche opérationnelle

View - Download Précis de recherche opérationnelle

Previous PDF

Next PDF

Précis

de recherche opérationnelle

Méthodes et exercices d'application

robert Faure

était professeur de la chaire

de recherche opérationnelle au CNAM

Bernard Lemaire

est professeur émérite de la chaire de recherche opérationnelle au CNAM christophe Picouleau est professeur des universités au CNAM 7 e

édition

© Dunod, Paris, 2014

isBN 978-2-10-070612-9illustration de couverture ©Kentoh-Fotolia.com REMER

CIEMENTS

Nous remer

cions toutes les per sonnes qui ont contri bué à la réa li sa tion de cette

édi

tion du Pré cis de recherche opé ra tion nelle. En par ti cu lier :

Mme Nacera SEGHOUANI-

BENNACER Enseignante- chercheuse à Supélec, pour le cha pitre por tant sur la simu la tion ;

M. Patrick SIARRY, Pro

fes seur à l"Uni ver sité Paris XII, pour le cha pitre trai tant des méta heu ris tiques ;

M Daniel VANDERPOOTEN, Pro

fes seur à l"Uni ver sité Paris- Dauphine pour le cha pitre intro duc tif à l"aide multi cri tère à la déci sion. Mme Agnès PLATEAU-ALFANDARI, maître de conférences au CNAM, pour ses remarques pertinentes. iii

TA B L E D E S MATI È R E S

AV A NT-PR OPO S ........................................................................ ................. vii

INTR O D U CTI O N À L A R E C H E R C H E OPE R ATI O N N E L L E ................................... ix

1 STR U C TU R E S O R D O N N É E S AP PL I C A TI O N S D E S TR E I L L I S

ET D E L

A L G È B R E D E BO O L E E N R E C H E R C H E

OPÉ R A TI O N N E L L E ........................................................................

......... 1 1.1

NO T i ONs s U r L E s s T r U c T U r E s O r D ON NÉ E s ............................................. 1

1.2 r E P r É s EN T A T i ON ENs E M B L i s T E D E s A L G È B r E s D E BO O L E. A

P P L i c A T i ON À L A L O G i Q U E É L É M EN T A i r E ................................................. 11

1.3 L'

A L G È B r E D E BO O L E B iNA i r E ............................................................... 19

1.4 A

P P L i c A T i ONs É L É M EN T A i r E s ................................................................. 27

2

NOTI O N S D E C OM PL E X ITÉ .................................................................. 42

2.1

cO M P L E x i T É D E s AL G O r i T H M E s ............................................................. 42

2.2 c

O M P L E x i T É D E s Pr O B L È M E s ................................................................. 47

3

ÉL É ME NTS D E L A TH É O R I E D E S G R APH E S : D É F I N I TI O N, C O N C EP TS

E S S E N TI E L S ; PA R C O U R S D E S G R APH E S .................................................. 59

3.1

ÉL É M ENT s D E L A T H É O r i E D E s G r A P H E s .................................................. 59

3.2 P

A r c O U r s D E s G r A P H E s ........................................................................

70
4 AP PL I C A TI O N S D E S G R APH E S À L A R E C H E R C H E

OPÉ R A TI O N N E L L E ........................................................................

........ 99 4.1

NO T i ONs D E P r O G r A M M A T i ON D YNA M i Q U E (PrD) .................................. 99

4.2 A

P P L i c A T i ONs A U x c H E M iNs O P T i M A U x ................................................... 104

4.3 P r O B L È M E s D O r D ON NAN c E M ENT EN G E s T i ON D E P r O J E T s ........................ 114 4.4 P

r O B L È M E D U F L O T D E V A L E U r M A x i M A L E .............................................. 128

4.5 F

L O T D E V A L E U r M A x i M A L E À c O Û T M iNi M A L.......................................... 134

4.6 P r O B L È M E s D A F F E c T A T i ON ................................................................... 139 4.7 N

O T i ONs D

A r B r E E T D

A r B O r E s c ENc E .................................................. 144 4.8 A

P P L i c A T i ONs A U x A r B r E s O P T i M A U x ..................................................... 146

4.9

LE s P r O G r A M M E s D E T r AN s P O r T............................................................ 149

4.10 r

E c H E r c H E s A r B O r E s c ENT E s .............................................................. 163

iv

Table des Matières

5 PR O C E S S U S STO C H A S TI Q U E S ET PR O G R AM MA TI O N

D Y N A MI Q U E STO C H A S TI Q U E ............................................................... 186

5.1

iNT r O D U c T i ON A U x P r O B L È M E s s T O c H A s T i Q U E s ...................................... 186

5.2 D

É F i Ni T i ON D

UN P r O c E s s U s s T O c H A s T i Q U E ............................................ 188 5.3 c

H A ÎNE s D E MA r K O V À E s P A c E D

É T A T s D i s c r E T .................................... 188 5.4 c

L A s s i F i c A T i ON D E s É T A T s D

UNE c H A ÎNE D E MA r K O V

FiNiE À L

A i D E D U G r A P H E D E s T r AN s i T i ONs ............................................ 191 5.5 P r O c E s s U s D E MA r K O V À E s P A c E D É T A T s D i s c r E T ................................ 197 5.6 P

r O B A B i L i T É s D E s É T A T s ....................................................................... 200

5.7 E r G O D i c i T É ........................................................................ .................. 202 5.8 c A L c U L D E s P r O B A B i L i T É s D E s É T A T s EN r É G i M E

P E r M ANENT-T H É O r È M E D E s c O U P E s........................................................ 204

5.9

Pr O c E s s U s D E MA r K O V P A r T i c U L i E r s.................................................... 208

5.10 N O T i ON D E P r O G r A M M A T i ON D YNA M i Q U E s T O c H A s T i Q U E ........................................................................ ............ 216 6 FIA B I L ITÉ D E S C OM PO S A NTS, S Û R ETÉ D E F O N C TI O N N E ME NT D E S S Y S TÈME S ........................................................................ ............ 228 6.1

DON NÉ E s D i s c r È T E s. c O U r B E s D E s U r V i E E x P É r i M EN T A L E ....................... 228

6.2 L

O i D E s U r V i E : F O r M E ANA L Y T i Q U E ....................................................... 233

6.3 P

r O B A B i L i T É D E c ONs O M M A T i ON. A P P r O V i s i ON NE M ENT s .......................... 237

6.4 c

A L c U L D E s A P P r O V i s i ON NE M ENT s ......................................................... 239

6.5 U

N A U T r E c O M P r O M i s : L

ENT r E T i EN P r É V EN T i F ..................................... 244 6.6 F

iA B i L i T É D E s s Y s T È M E s NON r É P A r A B L E s .............................................. 250

6.7 s

Û r E T É D E F ONc T i ON NE M ENT D E s s Y s T È M E s r É P A r A B L E s ......................... 254

6.8 s

T r A T É G i E D E r E M P L A c E M ENT ............................................................... 259

7

LE S PH É N O MÈ N E S D

AT TE NTE ............................................................. 270 7.1 GÉNÉ r A L i T É s s U r L E s P H É NO M ÈNE s D A T T ENT E ....................................... 270 7.2 L

O i D E s A r r i V É E s. LO i D E s s E r V i c E s ...................................................... 271

7.3 F

i L E À UNE s T A T i ON. sY s T È M E O U V E r T : F i L E M/M/1 ............................. 272

7.4 F

i L E À S s T A T i ONs, s Y s T È M E O U V E r T : F i L E M/M/s ................................ 278

7.5 A

P P L i c A T i ON NU M É r i Q U E ....................................................................... 280

7.6 F i L E À S s T A T i ONs, c A s D U s Y s T È M E F E r M É : F i L E M/M/s/N ........................................................................ ............. 286 © Dunod - Toute reproduction non autorisée est un délit. v

Table des Matières

7.7 Pr O B A B i L i T É D E D É P A s s E r UNE c E r T A iNE A T T ENT E : c A s D E L A F i L E M/M/1 ........................................................................ . 289 8

LA PR O G R AM MA TI O N LINÉAIRE ........................................................... 297

8.1

Ex E M P L E D E P r O G r A M M E L iNÉ A i r E (P L) - As P E c T G É O M É T r i Q U E ................ 298

8.2 A L G O r i T H M E D U s i M P L E x E : M É T H O D E A L G É B r i Q U E,

M É T H O D E D E s T A B L E A U x ........................................................................

307
8.3 D

É G É NÉ r E s c ENc E s P O s s i B L E s ................................................................ 321

8.4 A s P E c T M A T r i c i E L ........................................................................ ......... 324 8.5 D

É M A r r A G E D E L

A L G O r i T H M E D U s i M P L E x E : P r O B L È M E

D E L A B A s E iNi T i A L E ........................................................................

..... 330 8.6 N

O T i ONs s U r L A M É T H O D E r É V i s É E D U s i M P L E x E ..................................... 340

8.7 D U A L i T É ........................................................................ ....................... 342 8.8 Pquotesdbs_dbs22.pdfusesText_28

[PDF] Wikipédia et Éducation : un exemple de réconciliation - Framablog

[PDF] L 'éducation physique et le sport ? l 'école - EACEA - Europa EU

[PDF] L 'Identité de l 'EPS - Guyane

[PDF] Etablissement de la carte consulaire - El mouwatin

[PDF] Corrigé du Test n° 1 - Maths et Tice en Polynésie

[PDF] windows et manipulation du clavier - pmtic

[PDF] QUALITÉ DES SOLS ET DE L 'EAU

[PDF] pourquoi ? et comment ? ? quoi sert le compost - Préval Haut-Doubs

[PDF] Le nombre d 'or - Histoire des arts académie de Rouen

[PDF] Le personnage de roman - mediaeduscoleducationfr - Ministère

[PDF] Culture, tourisme et territoire - Bibliothèque de Sciences Po Lyon

[PDF] Les manuels scolaires : situation et perspectives - Ministère de l

[PDF] Le monument aux morts

[PDF] A quoi sert donc un ordinateur - resooorg

[PDF] Qu 'est-ce qu 'une association de parents d 'élèves - National Parents