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

A. On considère un ensemble de personnes $P=\{1,2,\ldots,n\}$ (n pair) devant travailler en binômes sur des projets. Chaque personne $i$ a une capacité $c_i$. Si on constitue un binôme $(i,j)$, le temps de travail est $c_i+c_j$. On dispose d'un graphe d'incompatibilité $G=(P,A)$ indiquant les binômes interdits.

1. Donner une formulation mathématique où les variables indiquent la compatibilité entre personnes.
2. Donner une autre formulation.
3. Comparer les deux formulations.

A.2 On considère le problème suivant : $n$ objets, poids $p_i$, regrets $r_i$, capacité $P$. Construire un sac de poids inférieur ou égal à $P$ de regret minimal. Modéliser le problème.

B. On considère le problème multiobjectif continu :

$$\max f_1=x_1-3x_2, \quad \max f_2=x_1+3x_2$$

sous contraintes $x_1+2x_2 \le 8$, $2x_1+x_2 \le 7$, $x_1-2x_2 \le 1$, $x_1,x_2 \ge 0$.

1. Résoudre les problèmes mono-objectif relatifs à $f_1$ et $f_2$.
2. Donner l'ensemble des solutions efficientes.
3. Définir une solution faiblement efficiente et trouver l'ensemble correspondant.
4. Donner les coordonnées du point idéal et du point anti-idéal.
5. Définir le point nadir et en déduire sa valeur approximative.