Upload
marjolaine-pham
View
116
Download
5
Embed Size (px)
Citation preview
Septembre 2004 1
30 ANS DE RECHERCHE
OPERATIONNELLEET D’OPTIMISATION
Yves CramaEcole d’Administration des Affaires
Septembre 2004 2
PLAN:
1. Quelques notions de complexité algorithmique
2. Impact en optimisation
3. Retombées industrielles
Septembre 2004 3
Intro…
HOMER SIMPSON
A CYBERLAND
Septembre 2004 4
Septembre 2004 5
Septembre 2004 6
Septembre 2004 7
Septembre 2004 8
Septembre 2004 9
Septembre 2004 10
PLAN:
1. Quelques notions de complexité algorithmique
2. Impact en optimisation
3. Retombées industrielles
Septembre 2004 11
Vieille question:
Pourquoi certains problèmes mathématiques sont-ils (ou semblent-ils) intrinsèquement plus difficiles à résoudre que d’autres ?
Septembre 2004 12
Gödel, Turing, Von Neumann
~1965: Jack Edmonds introduit la notion de « bonne caractérisation » des solutions et d’algorithme «polynomial».
~ 1972: Stephen Cook définit les classes de problèmes P et NP
Septembre 2004 13
Idée : distinguer entre les problèmes
1) pour lesquels on peut « facilement » trouver la réponse;
2) pour lesquels on peut « facilement » vérifier qu’une réponse est correcte, lorsqu’elle est connue;
3) les autres….
P et NP
Septembre 2004 14
Exemple 1:
Déterminer si l’équation du second degré
5x2 - 4x - 3 = 0possède deux racines distinctes.
Facile à résoudre… (« oui »)
Septembre 2004 15
Exemple 2:
Déterminer si
N1 = 281472829095937 est un nombre premier.
Pas très facile à résoudre…La réponse est « non ».
Septembre 2004 16
281472829095937 = 131071 2147483647
Preuve:
Septembre 2004 17
Exemple 3 (voyageur de commerce):
Déterminer si il existe une tournée de longueur inférieure à 1650 kms visitant 67 grandes villes de Belgique.
Pas très facile à résoudre…La réponse est « oui ».
Septembre 2004 18
Preuve: Il suffit que je donne la tournée:
Septembre 2004 19
Septembre 2004 20
Septembre 2004 21
Exemple 3 (suite):
Déterminer si il existe une tournée de longueur inférieure à 1500 kms visitant 67 grandes villes de Belgique.
Pas très facile à résoudre…La réponse est « non ».
Septembre 2004 22
Preuve: ????
Septembre 2004 23
Problèmes de décision
Un problème de décision est une question qui admet une réponse « Oui » ou « Non ».
Septembre 2004 24
P et NP
Un problème de décision est dans P (polynomial) si il peut être résolu par un algorithme efficace, c’est-à-dire un algorithme dont le temps de calcul n'augmente pas trop rapidement (polynomialement) avec la taille du problème à résoudre.
Septembre 2004 25
P et NP
Un problème de décision est dans NP (polynomial non déterministe) si il existe une preuve permettant de vérifier efficacement la validité de la réponse lorsque cette réponse est « Oui ».(par exemple, « existe-t-il une tournée de longueur au plus 1650…? »)
Septembre 2004 26
P vs NP
Il est à peu près évident que P et NP sont deux classes différentes de problèmes. En fait, P contient par définition des problèmes « faciles » à résoudre, alors que certains problèmes très difficiles sont dans NP.
Septembre 2004 27
NP
• problème du voyageur de commerce• programmation linéaire en variables binaires • ordonnancement d’ateliers• localisation d’entrepôts• etc.
Septembre 2004 28
Cook (1972) a conjecturé que P n’est pas égal à NP.Mais personne n’a pu le démontrer rigoureusement !!Il s’agit d’un des problèmes ouverts les plus célèbres des maths et de l’informatique théorique.
P = NP ?
Septembre 2004 29
P = NP ?
A l’occasion du passage à l’an 2000, le Clay Mathematics Institute a offert 1 million de dollars pour la solution de cette question (et de l’hypothèse de Riemann, etc.)
De là l’intérêt d’Homer Simpson…
Septembre 2004 30
Septembre 2004 31
PLAN:
1. Quelques notions de complexité algorithmique
2. Impact en optimisation
3. Retombées industrielles
Septembre 2004 32
Programmation linéaire (PL)
Min cj xj
s.c. jaij xj ≤ bi (i = 1,…,m)
Résolu par l’algorithme du simplexe (Dantzig 1947). Archétype du modèle d’optimisation en RO.
Septembre 2004 33
Complexité de la PL
Les travaux d’Edmonds, Cook et al. soulèvent de nouvelles questions:
• PL est-il dans NP ?
Oui (quand une solution est connue, il est facile de calculer sa valeur).
Septembre 2004 34
Complexité de la PL
• PL est-il dans P ?Oui (parce que la méthode du simplexe est efficace)? Pas évident…Klee et Minty (1972) observent que la méthode du simplexe peut effectuer un nombre exponentiel d'itérations sur certains exemples et n'est donc pas un algorithme polynomial (« efficace »).
Septembre 2004 35
Complexité de la PL
• PL est-il dans P ?Cette question a généré un nouvel intérêt pour la PL et un important courant de résultats.
Septembre 2004 36
Complexité de la PL
• Khachiyan (1979) propose un algo polynomial pour la PL – mais inefficace en pratique!
• Karmarkar (1984) décrit un algo polynomial et efficace en pratique: méthode de point intérieur.
Septembre 2004 37
Retombées algorithmiques
Développement de nouvelles méthodes de points intérieurs, de plus en plus efficaces
Suscite des améliorations spectaculaires de la méthode du simplexe.
Septembre 2004 38
État des lieux
• Empiriquement, méthodes du simplexe et de point intérieur sont complémentaires (selon les caractéristiques du problème à résoudre).
Septembre 2004 39
État des lieux
De 1987 à 2002, réduction du temps de calcul pour la solution de grands problèmes: facteur de 1.000.000 (1 an 30 sec), dont
- facteur de 1000 dû au « hardware »
- facteur de 1000 dû aux algorithmes
Septembre 2004 40
HeuristiquesPuisque certains problèmes ne peuvent pas être résolus en temps polynomial:
Heuristiques: méthodes approchées efficaces
Métaheuristiques: stratégies génériques de développement d’heuristiques
Septembre 2004 41
HeuristiquesExemples:
- recuit simulé (simulated annealing)
- exploration tabou (tabu search)
- algorithmes génétiques
- arrondi déterministe ou stochastique, voisinages variables, algorithmes de fourmis, réseaux de neurones, …
Septembre 2004 42
PLAN:
1. Quelques notions de complexité algorithmique
2. Impact en optimisation
3. Retombées industrielles
Septembre 2004 43
Tendance lourde:Développement simultané et « symbiotique » de l’informatique (micro-informatique, structures de données, bases de données, systèmes embarqués,…) et de la RO. Intégration croissante des algos d’optimisation dans les systèmes d’information et d’aide à la décision.
Septembre 2004 44
Exemples:
- calcul de routes et de tournées (navigateurs GPS, transport routier, Géoroute, …)
- construction d’horaires (écoles, infirmiers, équipes d’ouvriers,…)
- planification de production (affectation aux unités de production, gestion des stocks, ordonnancement, projets,…)
Septembre 2004 45
Exemples:
- optimisation des achats (localisation, rabais, …)
- optimisation des recettes de production (pétrochimie, agro-alimentaire,…)
- découpe de matériaux (verre, métal, tissu)
- électronique (conception et production de circuits intégrés)
Septembre 2004 46
Exemples:- yield management (optimisation des réservations et pricing pour les compagnies de transport, hôtels, …)- optimisation de portefeuilles financiers- moteurs de recherche Internet- bioinformatique (identification de structures génétiques)- etc.
Septembre 2004 47
Un exemple d’intégration:ERP - APS
1970-80: Systèmes MRP
- aide à la gestion des matières (approvisionnement des stocks, lancements de production)
- comportent des fonctionnalités d’optimisation, peu utilisées
Septembre 2004 48
Un exemple d’intégration:ERP - APS
1990: Systèmes ERP
- systèmes d’information couvrant les différentes fonctions de l’entreprise (production, stocks, achats, clients, personnel, comptabilité, …)
- peu de capacité d’optimisation
Septembre 2004 49
Un exemple d’intégration:ERP - APS
2000: Systèmes APS (Advanced Planning Systems)
- compléments aux ERP
- optimisation de l’allocation des ressources, planification de production, ordonnancement d’ateliers, etc
Septembre 2004 50
Un exemple d’intégration:ERP - APS
Rendus possibles grâce à l’adoption des systèmes ERP (dont ils utilisent les bases de données) et à l’amélioration des performances des algorithmes d’optimisation (programmation linéaire, programmation en variables entières, heuristiques, …)
Septembre 2004 51
Conclusions
Septembre 2004 52
De la théorie à la pratique…
Cheminement:théorie de la complexité (informatique
théorique) algorithmes d’optimisation plus efficaces
(simplexe, point intérieur, heuristiques)
systèmes d’aide à la décision performants (ERP, etc)
Septembre 2004 53
The world’s most important invisible profession…
Les algorithmes de RO sont intégrés de plus en plus complètement dans les systèmes d’aide à la décision ils deviennent invisibles pour l’utilisateur (cf. M. Jourdain)C’est probablement une preuve de succès.
Septembre 2004 54