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

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

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

⬇️ تحميل☆ حفظ✓ تم الحل

Concours d'accès à la Formation Doctorale Mathématiques Appliquées — Spécialité ROM — Épreuve de spécialité (2h00, coefficient 3), USTHB, Faculté de Mathématiques — 30 Octobre 2018.

التمرين 1

Exercice 1 — Sac à dos, ensembles bloquants et formulation équivalente

#integer-programming#knapsack#blocking-set#greedy-algorithm

On considère le problème classique du sac à dos : les objets à emporter sont 1,2,…,n1,2,\dots,n, de poids p1,…,pnp_1,\dots,p_n, de coefficients d'utilité a1,…,ana_1,\dots,a_n. La capacité du sac est bb.

  1. Écrire le problème d'optimisation du remplissage du sac sous forme d'un programme linéaire à variables booléennes.
  2. Montrer qu'on peut supposer pj≥0p_j \geq 0 et aj≥0a_j \geq 0.
  3. Montrer que l'algorithme glouton donne une solution optimale pour le cas at=(7,5,4,3,2)a^t=(7,5,4,3,2), pt=(8,6,6,4,3)p^t=(8,6,6,4,3) et b=18b=18.
  4. Un ensemble d'objets est dit bloquant si la somme des poids est supérieure à bb. Un ensemble est caractéristique s'il est bloquant et si chacun de ses sous-ensembles propres ne l'est pas. a) Associer à chaque ensemble caractéristique une contrainte à coefficients 0/1. b) Montrer que l'ajout de ces contraintes permet de supprimer la contrainte obtenue en 1. c) Peut-on être assuré que l'optimum trouve toutes ses coordonnées égales à 0 ou 1 ? Appliquer à l'exemple précédent.
◀الحل

1.

max⁡∑j=1najxjs.c.∑j=1npjxj≤b,xj∈{0,1}.\max \sum_{j=1}^n a_jx_j \quad \text{s.c.} \quad \sum_{j=1}^n p_jx_j \leq b, \quad x_j \in \{0,1\}.

2.

Un objet de poids négatif ou utilité négative peut être traité séparément : poids négatif toujours pris, utilité négative jamais prise. Donc on peut supposer pj,aj≥0p_j, a_j \geq 0.

3.

L'algorithme glouton par rapport au ratio aj/pja_j/p_j ou par structure de l'exemple sélectionne ici une solution optimale (à vérifier sur les données).

4.

Un ensemble caractéristique CC donne la contrainte ∑j∈Cxj≤∣C∣−1\sum_{j\in C} x_j \leq |C|-1. L'ensemble de ces contraintes remplace la contrainte globale de capacité. Cela ne garantit pas toujours l'intégralité dans la relaxation linéaire.

التمرين 2

Exercice 2 — Optimisation multi-objectifs booléenne et caractérisation de Geoffrion

#multiobjective-optimization#binary-variables#geoffrion-efficiency#pareto-front

Considérons le problème d'optimisation multi-objectifs à variables binaires :

max⁡∗z1=6x1+3x2+x3\max^* z_1 = 6x_1 + 3x_2 + x_3 max⁡∗z2=x1+3x2+6x3\max^* z_2 = x_1 + 3x_2 + 6x_3 s.c. x1+x2+x3≤1,x1,x2,x3∈R+.\text{s.c. } x_1 + x_2 + x_3 \leq 1, \quad x_1,x_2,x_3 \in \mathbb{R}_+.
  1. Représenter l'ensemble des solutions admissibles dans l'espace des critères.
  2. Trouver géométriquement l'ensemble des solutions efficaces et l'ensemble des solutions non-dominées.
  3. Ajouter les contraintes x1,x2,x3∈Zx_1,x_2,x_3 \in \mathbb{Z} et représenter les solutions efficaces dans l'espace des décisions et les non-dominées dans l'espace des critères.
  4. La caractérisation de Geoffrion est-elle valable ? Justifier.
◀الحل

Le problème se traite géométriquement. L'ensemble admissible continu est le simplexe standard de dimension 3 tronqué par x1+x2+x3≤1x_1+x_2+x_3 \leq 1. Son image dans l'espace des critères est le convexe engendré par les images des sommets.

Les solutions efficaces sont celles qui forment la frontière nord-est de cet ensemble. Avec intégralité, on ne garde que les sommets booléens. La caractérisation de Geoffrion peut échouer dans le cas discret non convexe.

Les solutions efficaces se lisent sur l’enveloppe non domineˊe\boxed{\text{Les solutions efficaces se lisent sur l'enveloppe non dominée}}
→السابقConcours Doctorat 2018 — Université Mohamed Khider - Biskra — Épreuve N°04التاليConcours Doctorat 2018 — Université des Sciences et de la Technologie Houari Boumediène (USTHB) — Épreuve N°04←