Recherche Opérationnelle - Mathématiques discrètes - 3MMROMD

Objectif(s)

Le premier but de ce cours est de donner des outils mathématiques et informatiques efficaces pour modéliser et résoudre des problèmes de base de la recherche opérationnelle. Le deuxième but est de donner des outils mathématiques et informatiques pour montrer que certains problèmes sont difficiles à résoudre voire impossible.

Contenu(s)

Contexte

Le cours traite principalement la théorie des graphes et la programmation linéaire comme outils de modélisation et résolution. Ces deux outils ainsi que les algorithmes efficaces vu en cours permettent par exemple aux étudiants de répondre aux questions ci-dessus.
Comment trouver un plus court chemin dans un réseau (de transport, informatique) ? Comment concevoir et faire fonctionner une organisation ? Comment exécuter un projet le plus vite possible ? Comment construire un réseau de coût minimum ? Comment affecter des tâches aux employés en respectant des contraintes légales et de préférences ? Comment maximiser le profit de la production en utilisant les matières premières disponibles ? Comment prendre des décisions économiques optimales ?
Le cours traite en deuxième partie de la complexité des problèmes et montre aussi l'existence des problèmes qu'on ne peut pas décider.

Syllabus

1. Mathématiques discrètes 1 : technique de preuves (induction, récurrence) - 4h, combinatoire-dénombrement - 4h,
2. Théorie des graphes et ses applications - 16h : modélisation, coloration, connexité, couplages, arbres de coût minimum, parcours des graphes, plus courts chemins, implémentation de l’algorithme de Dijkstra, ordonnancement.
3. Programmation linéaire et ses applications -16h : modélisation, applications industrielles en RO, méthode du simplexe, dualité, analyse de sensibilité, théorie des jeux.
4. Mathématiques discrètes 2 : Complexité des problèmes -4h, calculabilité et indécidabilité -4h.

Les bases de l'algèbre linéaire et de la probabilité, algorithmique de base et structure de données