Introduction à la Recherche Opérationnelle · Introduction à la Recherche Opérationnelle CERMICS, ENPC Diapositives : F. Meunier, Intervenant : A. Parmentier 27 septembre 2017

Introduction à la Recherche Opérationnelle

CERMICS,ENPC

Diapositives : F. Meunier, Intervenant : A. Parmentier

27 septembre 2017

Voyageur de commerce

10

5

4

11

12

1

10

4

7

13

6

65

8

2

3

2

10 10

31

47

9

8

5

5

10

7

???????

Monsieur R. doit organiser sa tournée.

Diapositives : F. Meunier, Intervenant : A. Parmentier, ENPC 27 septembre 2017 2 / 59


10

5

4

11

12

1

10

4

7

13

6

65

8

2

3

2

10 10

31

47

9

8

5

5

10

7

Monsieur R. a organisé sa tournée.



A 25 villes, cela fait 24! = 24× 23× 22× · · · × 2× 1 possibilités, soitenviron 6.204× 1025 possibilités.

A la main, à raison d’une possibilité par seconde, il faudrait environ1.976× 1016 années.

Avec un ordinateur, à raison d’1 million de possibilités par seconde, ilfaudrait environ 19 milliards d’années.


Plan

• Qu’est-ce que la Recherche Opérationnelle ?• Déroulement du cours.• Notions de bases (un peu de théorie).


Qu’est-ce que la RechercheOpérationnelle ?


La Recherche Opérationnelle

Ce que nous venons de voir, c’est un problème typique de laRecherche Opérationnelle : problème du voyageur de commerce.

Recherche Opérationnelle, ou RO :discipline des mathématiques appliquées traitant des questionsd’utilisation optimale des ressources en entreprise.


Exemples de problème de RO

• trouver la meilleure tournée10

5

4

11

12

1

10

4

7

13

6

65

8

2

3

2

10 10

31

47

9

8

5

5

10

7

• organiser le meilleur emploi du temps

• concevoir le réseau le plus robuste

• remplir de manière optimale un conteneur

• positionner intelligemment ses entrepôts

• ordonnancer des tâches sur des machinesDebut Fin

A

B

C

D

E

F

0

0

080

7080

30

30

30

50

40


Les Pères

Monge, Blackett, Dantzig.


A partir des années 50, fort développement de la RO :I laboratoires (mathématiques, informatique),I entreprises (supply chain, transport, télécommunications, etc.)

Deux mots-clés : Modélisation et Optimisation.


Progrès des performances sur le problème du voyageur de commerce

1954 Dantzig, Fulkerson, Johnson 49 villes1971 Held, Karp 64 villes1975 Camerini, Fratta, Maffioli 67 villes1977 Grötschel 120 villes1980 Crowder, Padberg 318 villes1987 Padberg, Rinaldi 532 villes1987 Grötschel, Holland 666 villes1987 Padberg, Rinaldi 2′392 villes1994 Applegate, Bixby, Chvátal, Cook 7′397 villes1998 Applegate, Bixby, Chvátal, Cook 13′509 villes2001 Applegate, Bixby, Chvátal, Cook 15′112 villes2004 Applegate, Bixby, Chvátal, Cook, Helsgaun 24′978 villes

Et ce n’est pas avant tout une question de puissance d’ordinateur.


Déroulement du cours


“Fondements”

1. Plus courts chemins et programmation dynamique

2. Flots

3. Graphes bipartis4. Problèmes difficiles : programmation linéaire en nombres entiers, heuristiques

et métaheuristiques

e−z

kBT


“Problématiques”

1. Localisation d’entrepôts

2. Remplissage de conteneurs

3. Conception de réseau

4. Tournées

5. OrdonnancementDebut Fin

A

B

C

D

E

F

0

0

080

7080

30

30

30

50

40


Intervenants extérieurs

A cela s’ajouteront des interventions d’1h par des personnes du mondeindustrielI Innovation 24.I Air France.


Support de cours et mode d’évaluation

Support Polycopié.Page web Educnet.

Mode d’évaluation Par ordre décroissant de pondération.1. Contrôle final de 2h45 le 24 janvier (c)2. Un miniprojet (p)

I Donné le 29 novembreI Retour pour le 11 janvier minuit

3. Deux contrôles surprises de 20 minutes (qi pouri = 1, 2)

4. Participation, assiduité.

note =19(max(q1, q2) + 3p + 5c).

Pas de rattrapage si manque d’assiduité.


Séances en autonomie

Les deux séances en autonomie seront les 29 novembre et 10 janvier.

I ExercicesI Miniprojet


Notions de base


Quelles notions ?

1. Modélisation.2. Optimisation.3. Graphes.4. Problèmes.5. Algorithmes et Complexité.


Modélisation

Modèle =Un modèle mathématique est une traduction de la réalité pourpouvoir lui appliquer les outils, les techniques et les théoriesmathématiques, puis généralement, en sens inverse, latraduction des résultats mathématiques obtenus en prédictionsou opérations dans le monde réel.


Graphes

Brique de base en modélisation.

Graphe : G = (V ,E)V : ensemble de sommetsE : ensemble d’arêtes ; à toute arête correspond une paire de sommets.

v1

v2

v3

v4

v5

v6

v1v2

v1v2

v3v3

v5v6

v3v4

v2v5

degré d’un sommet : nombre d’arêtes incidentes au sommet.Diapositives : F. Meunier, Intervenant : A. Parmentier, ENPC 27 septembre 2017 21 / 59

Graphes complets, graphes bipartis

Graphe complet : toute paire de sommets est reliée par une arête.

Graphe biparti : sommets peuvent être partitionnés en deux partiesn’induisant chacune aucune arête.


Graphes : Chaîne

Chaîne : suite de la forme

v0, e1, v1, . . . , ek , vk

vi ∈ V , ej ∈ E avec ej = vj−1vj .

Chaîne ne passant jamais plus d’une fois par une arête : chaîne simple.

Chaîne ne passant jamais plus d’une fois sur un sommet : chaîneélémentaire.

Chaîne simple passant par toutes les arêtes d’un graphe : chaîneeulérienne.

Chaîne élémentaire passant par tous les sommets du graphe : chaînehamiltonienne.


Graphes : Chaîne hamiltonnienne


Hamilton inventa l’“Icosian Game” au XIXe siècle, mais ce fut un bidecommercial.


Hamilton (1805–1865)


Graphes : connexité, cycles

Graphe connexe : entre toute paire de sommets, il y a une chaîne.

Cycle : chaîne simple fermée.

Cycle élémentaire, hamiltonien, eulérien.


Graphes : Coloration

Coloration : c : V → N (N= couleurs).

Coloration propre : pour toute paire de voisins u, v , on a c(u) 6= c(v).

nombre minimum de couleurs d’une coloration propre : nombrechromatique (noté χ(G))


Graphes : Couplage et couverture

Ensemble d’arêtes deux à deux disjointes : couplage

Ensemble de sommets tel que toute arête touche au moins un de seséléments : couverture

: couverture par les sommets du graphe


Les ponts de Königsberg

Euler, 1736.

FIGURE – Königsberg et ses 7 ponts


Euler (1707–1783)


Chaîne et cycle eulériens : existence

Modélisation

Un graphe connexe admet une chaîne eulérienne si et seulement si ilpossède au plus deux sommets de degré impair. Un graphe connexeadmet un cycle eulérien si et seulement si il n’a pas de sommet dedegré impair.


Optimisation

Min f (x)s.c. x ∈ X .

f : critère.« s.c. » = « sous contraintes »X : ensemble des solutions réalisables« x ∈ X » : contraintes du programme.

Parmi les solutions réalisables, on veut chercher une solution optimalex∗, i.e. une solution réalisable qui minimise le critère.


Minimisation : De l’importance des bornes inférieures

OPT = Min f (x)s.c. x ∈ X .

Toujours se demander s’il n’y a pas une borne inférieure simple et debonne qualité à OPT.

Une borne inférieure permet d’évaluer la qualité d’une solutioncourante→ évite de continuer à chercher des solutions etéventuellement, montre l’optimalité d’une solution.


Coloration

b

vb

b

b

b

v

r

r

r

n

j

j

Graphe colore avec cinq couleurs: r, b, j, v, n.

Peut-on colorer ce graphe avec moins de cinq couleurs ?Diapositives : F. Meunier, Intervenant : A. Parmentier, ENPC 27 septembre 2017 35 / 59

Coloration et sous-graphe complet : une inégalité

cardinalité d’un sous-graphe complet ≤ nombre de couleurs dans une coloration propre.

La cardinalité maximale d’un sous-graphe complet de G se note ω(G).

ω(G) ≤ χ(G).


Couplage


Couplage et couverture : une inégalité

Soit M un couplage et C une couverture par les sommets. Alors

|M| ≤ |C|.

τ (G) : cardinalité minimale d’une couvertureν(G) : cardinalité maximale d’un couplage

ν(G) ≤ τ (G).



Problèmes

Problème :I “Donnée”I “Tâche” ou “Question”.


Exemples de problèmes

PROBLÈME DE LA CHAÎNE EULÉRIENNE

Donnée : Un graphe G = (V ,E).

Question : G a-t-il une chaîne eulérienne ?

PROBLÈME DU COUPLAGE DE PLUS GRAND POIDS

Donnée : Un graphe G = (V ,E), une fonction de poids w : E → R+.

Tâche : Trouver le couplage de G de plus grand poids.


Problème de décision, problème d’optimisation

Problème de décision : consiste à répondre ‘Oui’ ou ‘Non’ à unequestion.

Problème d’optimisation : consiste à trouver l’optimum d’une fonction.


Algorithmes et complexité

algorithme = suite d’opérations élémentaires implémentable dans unordinateur

Supposons donnés un problème P et un algorithmeA qui le résout. Sepose alors la question de son efficacité.→ Théorie de la complexité.


Fonction de complexité

Fonction de complexité f (n) d’un algorithme : nombre d’opérationsélémentaires qu’il faut effectuer si la donnée est de taille n.

Exemples :Trier n entiers : O(n log(n)).Tester l’existence d’un cycle eulérien : O(n + m).


Les ponts de Königsberg – optimisation


ExerciceQuel est le nombre mini-mum de ponts qu’il faut tra-verser pour traverser tousles ponts de Königsberg(un pont traversé n foiscompte pour n) ?


Les ponts de Königsberg – optimisation


ExerciceQuel est le nombre mini-mum de ponts qu’il faut tra-verser pour traverser tousles ponts de Königsberg(un pont traversé n foiscompte pour n) ?

Réponse : 8


Algorithme polynomial/exponentiel

Algorithme polynomial : fonction de complexité = O(na) avec aconstante.

Sinon, algorithme exponentiel.Taille n

Fonction de complexité 10 20 50 60n 0, 01 µs 0, 02 µs 0, 05 µs 0, 06 µsn2 0, 1 µs 0, 4 µs 2, 5 µs 3, 6 µsn3 1 µs 8 µs 125 µs 216 µsn5 0, 1 ms 3, 2 ms 312, 5 ms 777, 6 ms2n ∼ 1 µs ∼ 1 ms ∼ 13 jours ∼ 36 années et 6 mois

TABLE – Comparaison de diverses fonctions de complexité pour un ordinateureffectuant 1 milliard d’opérations par seconde.


Une question de puissance des ordinateurs ?

Soit A un algorithme résolvant un problème P en 2n opérations.On a une machine qui résout P avec A en 1 heure jusqu’à n = 438.

Si on a un machine 1000 fois plus rapide ?


Une question de puissance des ordinateurs ?

On a une machine qui résout P avec A en 1 heure jusqu’à n = 438.

Machine 1000 fois plus rapide→ en une heure, jusqu’à n = 448.


Une question de puissance d’ordinateurs ?

Taille de l’instance la plus large que l’on peut résoudre en 1 heureFonction Avec un ordinateur Avec un ordinateur Avec un ordinateur

de complexité actuel 100 × plus rapide 1000 × plus rapiden N1 100N1 1000N1

n2 N2 10N2 31.6N2

n3 N3 4.64N3 10N3

n5 N4 2.5N4 3.98N42n N5 N5 + 6.64 N5 + 9.973n N6 N6 + 4.19 N6 + 6.29

TABLE – Comparaison de diverses fonctions de complexité.


Classe P

Problème (de décision) est polynomial ou dans P : il existe unalgorithme polynomial qui le résout.

Problème (de décision) est non-déterministiquement polynomial oudans NP : si la réponse est oui pour l’instance considérée, il existe uncertificat et un algorithme polynomial qui permet de vérifier que laréponse est bien oui.


Classe NP

PROBLÈME DU CYCLE HAMILTONIEN

Donnée : Un graphe G = (V ,E).

Question : G a-t-il un cycle hamiltonien ?

Pour F ⊆ E , on peut tester en temps polynomial si F est un cyclehamiltonien.F est un certificat.Le problème du cycle hamiltonien est dans NP.


Classe NP

Proposition

P ⊆ NP.

Démonstration.En cas de réponse ‘Oui’, la donnée est un certificat.


Problèmes NP-complets

problème de décision est NP-complet : s’il existe un algorithmepolynomial qui le résout, alors il existe un algorithme polynomial pourtout problème NP.

On ne connaît pas d’algorithme polynomial résolvant un problèmeNP-complet.

Theorem (Cook, 1970)

Il existe des problèmes NP-complets.


Exemple de problème NP-complet

PROBLÈME DU CYCLE HAMILTONIEN

Données : Un graphe G = (V ,E).

Question : G a-t-il un cycle hamiltonien ?

est NP-complet.


Problèmes NP-difficiles

problème est NP-difficile : s’il existe un algorithme polynomial qui lerésout, alors il existe un algorithme polynomial pour tout problème NP.

Différence avec NP-complet : pas nécessairement un problème dedécision.

Exemple : le problème du voyageur de commerce est NP-difficile.


Les problèmes NP

P

NP-complets

NP

NP-difficiles


Question à 1 millions de $

P ?= NP.

offerts par la Fondation Clay.


NP-complétude du cycle Hamiltonien

Montrer que le problème de l’existence de la chaîne hamiltonnienneest NP-complet, sachant que celui du cycle hamiltonien l’est.

Soit une instance ...Réciproquement, montrer que le problème de l’existence du cycle ha-miltonnien est NP-complet, sachant que celui de la chaîne hamilto-nienne l’est.

Soit une instance ...


NP-complétude du cycle Hamiltonien

Montrer que le problème de l’existence de la chaîne hamiltonnienneest NP-complet, sachant que celui du cycle hamiltonien l’est.

Soit une instance du cycle hamiltonien, etc.

Réciproquement, montrer que le problème de l’existence du cycle ha-miltonnien est NP-complet, sachant que celui de la chaîne hamilto-nienne l’est.

Soit une instance de la chaîne hamiltonienne, etc.


NP-complétude de la chaine Eulérienne – correction

Montrer que le problème de l’existence de la chaîne Hamiltonienneest NP-complet, sachant que celui du cycle hamiltonien l’est.

Correction : Soit G = (V ,E) un graphe (une instance du problème decycle Hamiltonien). Pour chaque arête (u, v) de E , on crée un grapheG′ une instance du problème de chaine Hamiltonienne en ajoutantdeux sommets u′ et v ′ à E et en enlevant l’arête (u, v) (toutes lesarêtes entre u et v si le graphe n’est pas simple). Alors le problème dela chaine Hamiltonienne sur admet une solution si et seulement si ilexiste un cycle Hamiltonien passant par (u, v) (ou par une autre arêteentre u et v ). Le problème du cycle Hamiltonien admet donc uneréponse positive si au moins une des instances de la chaineHamiltonienne crée admet une réponse positive.


Documents

Introduction à la Recherche Opérationnelle · Introduction à la Recherche Opérationnelle CERMICS, ENPC Diapositives : F. Meunier, Intervenant : A. Parmentier 27 septembre 2017