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

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

مسابقة تخصص · Recherche Opérationnelle · المعامل: 1

⬇️ تحميل☆ حفظ

Concours d'accès à la Formation Doctorale Mathématiques Appliquées — Spécialité ROM — Épreuve de Spécialité (1h30, coefficient 1), USTHB, Faculté de Mathématiques — 26 Octobre 2019.

التمرين 1

Exercice 1 — Appariement parfait pondéré sur graphe d'incompatibilité

#graph-theory#matching#integer-programming#assignment

On considère un ensemble de personnes P={1,2,…,n}P = \{1,2,\dots,n\} (avec nn pair) qui doivent travailler en binômes sur des projets. Chaque personne ii possède une capacité connue à l'avance et le temps d'un binôme {i,j}\{i,j\} est ci+cjc_i + c_j. On dispose d'un graphe d'incompatibilité G=(P,A)G=(P,A) : une arête signifie que les personnes ne peuvent pas être en binôme. Le but est de répartir les personnes en binômes compatibles de sorte que tous les projets soient exécutés en un minimum de temps.

  1. Donner une formulation mathématique avec variables indiquant la compatibilité des personnes.
  2. Donner une autre formulation.
  3. Comparer les deux formulations.
◀الحل

C'est un problème d'appariement parfait pondéré sur le graphe de compatibilité (complémentaire du graphe d'incompatibilité).

Variables binaires xij=1x_{ij}=1 si ii et jj sont appariés.

min⁡∑i<j(ci+cj)xij\min \sum_{i<j} (c_i+c_j)x_{ij}

s.c. chaque sommet est incident à exactement une arête choisie, xij=0x_{ij}=0 si {i,j}\{i,j\} est incompatible, xij∈{0,1}x_{ij} \in \{0,1\}.

Une autre formulation passe par un problème de couplage parfait dans le graphe de compatibilité. La comparaison porte sur la taille et la force de la relaxation linéaire.

التمرين 2

Exercice 2 — Sac de regret minimal

#knapsack#integer-programming#dynamic-programming

On considère nn objets, de poids respectifs pip_i et de regret rir_i, et soit PP un entier. Le regret d'un sac est la somme des regrets des objets qui ne sont pas dans le sac. On cherche un sac de poids inférieur ou égal à PP qui soit de regret minimal. Modéliser ce problème à l'aide d'un programme mathématique.

◀الحل

Variables binaires xix_i indiquant si l'objet ii est dans le sac.

min⁡∑i=1nri(1−xi)\min \sum_{i=1}^n r_i(1-x_i)

sous

∑i=1npixi≤P,xi∈{0,1}.\sum_{i=1}^n p_i x_i \leq P, \quad x_i \in \{0,1\}.

On peut aussi écrire max⁡∑rixi\max \sum r_i x_i à constante près.

التمرين 3

Exercice 3 — Optimisation linéaire multiobjectif continue

#multiobjective-optimization#linear-programming#efficient-solutions#ideal-point#nadir-point

On considère le problème d'optimisation linéaire multiobjectif continu

(P){max⁡  x1−3x2=f1max⁡  x1+3x2=f2sujet aˋ x1+2x2≤8,  2x1+x2≤7,  x1−2x2≤1,  x1,x2≥0.(P) \begin{cases} \max \; x_1 - 3x_2 = f_1 \\\\ \max \; x_1 + 3x_2 = f_2 \\\\ \text{sujet à } x_1 + 2x_2 \leq 8, \; 2x_1 + x_2 \leq 7, \; x_1 - 2x_2 \leq 1, \; x_1,x_2 \geq 0. \end{cases}
  1. Résoudre les problèmes mono-objectif (Pi)(P_i) relatifs aux fonctions objectif fif_i.
  2. Donner l'ensemble des solutions efficientes du problème (P)(P).
  3. Donner la définition d'une solution faiblement efficiente et trouver l'ensemble des solutions pour (P)(P).
  4. Donner les coordonnées du point idéal et du point anti-idéal de (P)(P).
  5. Donner la définition du point nadir et en déduire sa valeur approximative relative à (P)(P).
◀الحل

On résout P1P_1 et P2P_2 sur le polygone admissible. Les solutions efficientes sont les points non dominés de ce polygone. Les solutions faiblement efficientes autorisent l'égalité composante par composante.

Le point idéal est (max⁡f1,max⁡f2)(\max f_1, \max f_2), l'anti-idéal est (min⁡f1,min⁡f2)(\min f_1, \min f_2) sur l'ensemble efficient, et le point nadir correspond aux pires valeurs objectives atteintes sur l'ensemble efficient.

Les ensembles s’obtiennent par eˊtude geˊomeˊtrique du polytope admissible\boxed{\text{Les ensembles s'obtiennent par étude géométrique du polytope admissible}}