Cours de Recherche Opérationnelle

 

Année 2002 - 2003

 

PRESENTATION ET HISTORIQUE

 

 

 

Recherche Opérationnelle (RO) 2

Historique succinct 2

Les précurseurs 2

Les applications militaires 2

Comment sauver l’Angleterre ?_ 3

Ce qui caractérise la RO_ 3

Les caractères qui en découlent 3

Définition de la RO_ 4

Les domaines d’applications dans l’entreprise_ 4

Exemple : multiprocesseurs 5

Les règles 5

4 cas de figures à envisager 5

Question : déterminer le cas de figure le plus rapide_ 5

Autre exemple_ 7

 


 

Recherche Opérationnelle (RO)

-         solution à un problème avec des ressources

-         diversité de la façon de regarder les choses (les différentes facettes)

 

 

 

Historique succinct

 

Les précurseurs

1850 : Fermat, Pascal                  Espérance Mathématique

1840 : Cournot                            Théorie mathématiques des richesses

1917 : Emile Ernag                       File d’attente (réseaux téléphonique)

1925 : Borel                                 Théorie mathématique, jeux

1936 : Kœnig                               Théorie des graphes

1939 : Kantorovitch                     Programmation linéaire

 

Les applications militaires

1940 : Equipe Blackett (Prix Nobel 1948 en Physique)

-       efficacité optimale et globale des stations de surveillance radars (bataille d’Angleterre)

-       efficacité due à l’hétérogénéité de l’équipe

USA 1940 : Groupe Opération Research dans les états majors

-       organisation des convois de navire

-       blocus des ports japonais

-      

 

 

Après la seconde guerre mondiale, mise en place de groupe RO dans les grandes entreprises :

- 6 EDF,

- 6 SNCF, Armée, 

-        

 

1948 : Enseignement de RO au MIT (en baisse de reconnaissance en 1970)

 

Gestion pratique RO (pour les informaticiens)

-         aide à concevoir les différents logiciels

-         connaissance des limites des algorithmes utilisés


 

 

Comment sauver l’Angleterre ?

 

Positionnement des radars :

-         complexité du problème

-         localisation des radars (algorithme de positionnement)

-         traitement des données – délai (réseau)

-         répartition du problème : détection, riposte, transmission

-         bonne fiabilité

-         maintenance pour la défaillance

-         organisation des tâches (gestion des tâches – chemin critique)

-         stratégie informatique (espionnage)

-         arborescence du groupe (civil – régulation, donnée – chercher (exhaustivité)

-         redondance (réseau – optimisation des réseaux)

-         arborescence des moyens de défense

-         normalisation

-         finance/coût – optimisation de la répartition budgétaire ( optimisation)

-         approvisionnement (vivres / matières premières)

-         but / procédures

-         gestion du temps (notion de contrainte) (tenir un planning)

-         formation : maintenance, avion, procédure, … (gestion d’information)

-         multiplier/répartit les postes de décision/optimiser (redondance)

-         gestion information (adressage / interne / externe)

-         cryptage des informations (appareillé les gens à leurs fonctions)

-         gestion des ressources d’un site pilote ou des sites pilotes

 

 

Ce qui caractérise la RO

-         localisation : où installer les radars en nombre limité ?

-         transmissions et traitements de données

-         comment assurer un bon fonctionnement des systèmes en condition opérationnelles avec du personnel hétérogène ?

 

 

Les caractères qui en découlent

-         bien poser le problème (qui souvent se construit) et inventorier les voies de traitement

-         vision globale

-         recours à des disciplines multiples

-         primauté accordée à la démarche rationnelle et aux méthodes quantitatives

-         rôle important des ordinateurs et de l’information

-         une attention porté aux conditions réelles (et non seulement théorique)

 

 

Définition de la RO

-         ensemble :

Ø de méthode et d’outils

Ø d’analyse et de synthèse

Ø des phénomènes d’organisation

Ø utilisables pour élaborer de meilleurs décisions

-         une discipline – carrefour entre :

Ø l’information

Ø les mathématiques

Ø l’économie d’entreprise

 

Les domaines d’applications dans l’entreprise

-         production

Ø allocation des ressources limitées pour l’obtention d’un objectif

Ø ordonnancement :

      1960 : méthode PERT (programme evaluation review technique – Fusées Polaris)

      séquencement d’instruction dans les ordinateurs multiprocesseurs

-         gestion des stocks

-         logistique

Ø localisation optimale des dépôts

Ø apprendre les clients à partir des dépôts afin de minimiser les coûts global du transport

Ø choix des meilleurs chemins

      voyage, transport

      déplacement de pièce dans un atelier

-         problèmes combinatoires

Ø exercice : nombre de possibilités pour 8 personnes, 2 repas/jour

Ø définition des investissements les plus rentables

Ø ordonnancements

Ø

-         problèmes aléatoires ou stochastiques

Ø exemple : files d’attentes, pointes de trafic, …

Ø problème de structure

-         problème de situation de concurrence

Ø exemple : situation avec un concurrent

Ø définition d’une politique de vente, d’approvisionnement

 


 

Exemple : multiprocesseurs

Les règles

-      une tâche ne peut être commencée que si la précédente est terminée

-      toute tâche commencée ne peut être interrompue

-      s’il y a choix de démarrer plusieurs tâches possibles, le choix se fera par ordre alphabétique

-      les tâches sont attribuées au processeur par n° d’ordre processeur croissant

 

4 cas de figures à envisager

1.   durée nominale, 2 processeurs

2.   durée réduite (-1), 2 processeurs

3.   durée nominale, 3 processeurs

4.   durée réduite (-1), 3 processeurs

 

Question : déterminer le cas de figure le plus rapide

 

E(7)

 
            Les tâches :

 

 

 

 

 

 

 

 

 

 

 



Durée nominale, 2 processeurs

P

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

1

 

 

 

A

 

 

 

 

 

 

 

E

 

 

 

 

 

 

 

 

 

 

 

G

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2

B

 

 

C

 

 

D

 

 

 

 

F

 

 

 

H

 

 

 

 

I

 

 

 

 

 

 

 

J

 

 

 

 

 

 

 

 

 

 

 

 

 

Durée réduite (-1), 2processeurs

P

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

1

 

 

A

 

 

 

 

 

 

E

 

 

 

 

 

F

 

 

 

 

 

 

 

 

 

 

G

 

 

 

 

 

 

 

 

 

 

 

 

 

2

B

C

 

D

 

H

 

 

 

I

 

 

 

 

 

 

J

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Durée nominale, 3 processeurs

P

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

1

 

 

 

A

 

 

 

 

 

 

 

E

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

G

 

 

 

 

 

 

 

 

 

 

2

B

 

 

D

 

 

 

 

I

 

 

 

 

 

 

 

F

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

3

 

C

 

H

 

 

 

 

J

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Durée réduite (-1), 3 processeurs

P

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

1

 

 

A

 

 

 

 

 

 

E

 

 

 

 

 

 

 

 

 

 

 

 

 

 

G

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2

B

D

 

 

 

 

I

 

 

 

 

 

F

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

3

C

 

H

 

 

 

J

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ATTENTION : si on ne connaît pas le temps, il est impossible de synchroniser les tâches sans le temps.    SOLUTION : cas 1


 

 

 

Autre exemple

Combien de temps, vais-je avoir le temps de faire toutes les combinaisons possibles ?

-       8 places autour d’une table + 2 repas/jour

                  ( 8 ! / 2 ) / 365 » 55 ans

-       20 personnes à 20 poste différents

20 ! = 2,43 * 1018

-       100 personnes à 100 poste différents

100 ! = 9,33 * 10157