📚 الرئيسية
دخول

مسابقة دكتوراه 2019 — Université des Sciences et de la Technologie Houari Boumediène (USTHB) — الموضوع 02

مسابقة عامة · الرياضيات

⬇️ تحميل☆ حفظ

Bundle mixte USTHB 2018-2019 visible sur scans : épreuves générales et spécialité ROM, aide à la décision, réseaux/optimisation, graphes, chaînes de Markov.

التمرين 1

Exercice 1 — Formulation graphique d'un MOLP et solutions de Pareto

#multiobjective-optimization#pareto-front#geometric-methods

On considère un problème de maximisation bi-objectif (MOLP) dont le domaine et les vecteurs gradients sont donnés graphiquement.

  1. Donner la formulation mathématique du problème.
  2. Définir le cône polaire semi-positif généré par les gradients et l'ensemble de dominance.
  3. Citer le théorème du point de contact.
  4. Trouver géométriquement l'ensemble des solutions efficaces.
  5. Déterminer s'il existe des solutions faiblement efficaces.
  6. Représenter le front de Pareto dans l'espace des critères.
  7. Ajouter des contraintes d'intégrité et redonner les solutions efficaces.
◀الحل

On formalise les deux fonctions objectif d'après leurs gradients et la région admissible d'après le polygone dessiné. Les solutions efficaces sont les points du bord supportés par des normales appartenant au cône polaire semi-positif. Le front de Pareto est l'image de cette frontière dans l'espace des critères.

التمرين 2

Exercice 2 — Chaîne de Markov finie : classes, premier passage et matrice potentielle

#markov-chains#classification-of-states#hitting-probabilities#fundamental-matrix

On considère une chaîne de Markov finie de matrice de transition PP sur E={1,…,7}E=\{1,\ldots,7\}.

  1. Dessiner le graphe de la chaîne et le graphe réduit.
  2. Donner les ensembles fermés.
  3. Dire si la chaîne est irréductible.
  4. Calculer la probabilité de ne jamais retourner à l'état 5 et la probabilité d'aller de 3 à 5 pour la première fois.
  5. Classer les états.
  6. Calculer la matrice potentielle P~\tilde P et la matrice du premier passage VV.
  7. En déduire la matrice P∞P^\infty.
◀الحل

On décompose la chaîne en classes communicantes, on identifie les classes fermées et les états transitoires. Les probabilités de premier passage se calculent via systèmes linéaires. Pour les états transitoires, la matrice fondamentale est N=(I−Q)−1N=(I-Q)^{-1}. La limite P∞P^\infty s'obtient à partir des probabilités d'absorption vers les classes fermées.

التمرين 3

Exercice 3 — Réseaux, arbres de poids maximum et bi-objectif en ROM

#network-optimization#maximum-spanning-tree#multiobjective-optimization#graph-theory

On regroupe ici plusieurs exercices de ROM visibles sur les scans 2018-2019 :

  1. Arbre/forêt de poids maximum dans un graphe connexe pondéré.
  2. Réseaux et optimisation avec équilibres de flux.
  3. Programme linéaire bi-objectif continu et détermination des solutions efficientes/faiblement efficientes, point idéal, anti-idéal et nadir.

Formuler et résoudre les versions générales de ces problèmes.

◀الحل

Les arbres de poids maximum se résolvent par algorithmes gloutons type Kruskal inversé. Les équilibres de flux se formulent via le potentiel de Beckmann et conditions de Wardrop. Les MOLP continus se traitent par scalarisation pondérée, analyse géométrique du polyèdre admissible et étude de la frontière de Pareto.