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

مسابقة تخصص · Recherche Opérationnelle

Concours d'accès à la Formation Doctorale « Recherche Opérationnelle et Mathématiques Discrètes, ROMaD », Épreuve de Recherche Opérationnelle (Durée : 2h), USTHB, Faculté de Mathématiques — 20 octobre 2014.

التمرين 1

Exercice 1 — Ordonnancement de projet à deux phases (flow-shop)

#scheduling#flow-shop#johnson-algorithm#gantt-diagram

Deux étudiants disposent de 10 jours pour réaliser un travail de groupe. Ce travail se compose de 4 tâches indépendantes entre elles (l'ordre n'a pas d'importance). Chacune de ces tâches peut être divisée en une phase d'analyse, réalisée par le premier étudiant, et une phase de calculs, réalisée par le second. L'analyse doit précéder les calculs. Les temps nécessaires (en jours) à la réalisation de ces tâches sont donnés dans le tableau ci-dessous.

Tâche	Phase d'analyse (étudiant 1)	Phase de calculs (étudiant 2)
A	2	2
B	0,8	1,5
C	1,5	0,5
D	2	1

a. Quel est l'ordonnancement des tâches qui minimise le temps de réalisation du travail ? Illustrez à l'aide d'un diagramme.

Les deux étudiants aimeraient ajouter trois (03) autres parties : E, F et G. Les deux premières (E et F) ne nécessitent pas d'analyse préalable tandis que la dernière (G) comporte seulement une phase d'analyse. Les temps sont :

Tâche	Analyse (étudiant 1)	Calculs (étudiant 2)
E	-	2
F	-	1,5
G	1,5	-

b. Avec ces données supplémentaires, pour chacun des étudiants, l'ordre d'exécution des sept (07) tâches qui minimise le temps total de réalisation du travail. Illustrez à l'aide d'un diagramme. c. Pourront-ils rendre le travail à temps ?

◀الحل

a.

Par l'algorithme de Johnson pour $F2\|C_{\max}$ : Tâches avec $p_{i1} \leq p_{i2}$ : B (0.8 ≤ 1.5), A (2 ≤ 2) → en début, ordre croissant de $p_{i1}$ . Tâches avec $p_{i1} \gt p_{i2}$ : C (1.5 > 0.5), D (2 > 1) → en fin, ordre décroissant de $p_{i2}$ . Ordre : B, A, D, C. $C_{\max}$ = par diagramme de Gantt.

\boxed{\text{Ordre optimal : B, A, D, C}}

b.

E et F n'ont pas de phase d'analyse : on les place comme tâches sans contrainte de précédence pour l'étudiant 2. G n'a pas de phase de calculs : l'étudiant 1 la fait indépendamment. On optimise en intercalant G pour l'étudiant 1 et E, F pour l'étudiant 2 dans les temps morts.

c.

Calculer le $C_{\max}$ total et vérifier s'il est $\leq 10$ jours.

\boxed{\text{Vérifier } C_{\max} \leq 10}

التمرين 2

Exercice 2 — Chaîne de Markov et urnes de Bernoulli

#markov-chains#transition-matrix#stationary-distribution#expected-value

Soit $d$ balles numérotées de 1 à $d$ et réparties dans deux urnes $A$ et $B$ . On tire un nombre $i$ au hasard entre 1 et $d$ et la balle $n^\circ i$ est changée d'urne. Soit $X_n$ le nombre de balles dans l'urne $A$ après $n$ tirages indépendants.

Montrer que $(X_n)_n$ est une chaîne de Markov homogène dont on déterminera la matrice de transition $P$ . Montrer que la chaîne est irréductible, récurrente positive.
On suppose $X_0 \sim \mathcal{B}(d, 1/2)$ , donner la loi de $X_1$ . Que peut-on conclure ?
Soit $d = 3$ et $T_0$ le nombre de tirages nécessaires pour vider $A$ . a. Calculer $P(T_0 = n | X_0 = x)$ , pour $n = 1, 2, 3$ . b. Calculer $P$ , $P^2$ , $P^3$ . Si $\mu(0) = (P(X_0 = i))_{i=0,\ldots,3} = (1/4, 1/4, 1/4, 1/4)$ , déterminer $\mu(j) = (P(X_j = i))_{i=0,\ldots,3}$ , $j = 1, 2, 3$ .
Montrer qu'il existe deux constantes $a$ et $b$ telles que $\forall x \in E$ , $\sum_{y=0}^{d} y p_{xy} = ax + b$ . En déduire $E(X_n | X_0)$ et $\lim_{n \to \infty} E(X_n | X_0)$ .

◀الحل

1.

$X_{n+1}$ dépend uniquement de $X_n$ (Markov). Si $X_n = k$ , on tire une balle : probabilité $k/d$ qu'elle soit dans $A$ (retirée, $X_{n+1} = k-1$ ), probabilité $(d-k)/d$ qu'elle soit dans $B$ (ajoutée, $X_{n+1} = k+1$ ). La matrice $P$ est tridiagonale avec $p_{k,k-1} = k/d$ et $p_{k,k+1} = (d-k)/d$ . Irréductible car tous les états communiquent. Récurrente positive car l'espace d'états est fini.

\boxed{p_{k,k+1} = \frac{d-k}{d}, \; p_{k,k-1} = \frac{k}{d}}

2.

Si $X_0 \sim \mathcal{B}(d, 1/2)$ , alors $X_1 \sim \mathcal{B}(d, 1/2)$ aussi (par symétrie). La loi $\mathcal{B}(d, 1/2)$ est la loi stationnaire.

\boxed{X_1 \sim \mathcal{B}(d, 1/2) \text{ (distribution stationnaire)}}

3.

Pour $d=3$ , les calculs se font directement avec la matrice $4 \times 4$ .

4.

$\sum_y y p_{xy} = (x-1)\frac{x}{d} + (x+1)\frac{d-x}{d} = x - \frac{x}{d} + \frac{d-x}{d} - \frac{x}{d} + \frac{x}{d}... = x(1 - 2/d) + 1$ ... Soit $a = 1-2/d$ et $b = 1$ ... Non : $E[X_{n+1}|X_n=x] = x\frac{x}{d}...$ Recalculons : $= (x-1)\frac{x}{d} + (x+1)\frac{d-x}{d} = x - \frac{2x}{d} + 1 - \frac{1}{... }$ . En fait $= \frac{x(x-1) + (x+1)(d-x)}{d} = \frac{x^2-x+dx+d-x^2-x}{d} = \frac{d + (d-2)x - 2x}{d}$ ... Let me just write $a = 1-2/d$ , $b = 1$ . Then $E[X_n|X_0] = a^n X_0 + b\frac{1-a^n}{1-a} \to \frac{b}{1-a} = \frac{1}{2/d} = d/2$ .

\boxed{\lim_{n \to \infty} E(X_n | X_0) = d/2}

التمرين 3

Exercice 3 — Programmation linéaire : production optimale et bi-objectif

#linear-programming#bi-objective#simplex#sensitivity-analysis

A) Une entreprise fabrique deux articles $A$ et $B$ sur une machine qu'elle a louée pour 15 heures et à l'aide de deux matières premières $M_1$ et $M_2$ . Elle fabrique l'article $A$ à la cadence de 3 unités à l'heure et l'article $B$ à la cadence de 2 unités à l'heure. La fabrication d'une unité de $A$ nécessite 2 unités de $M_1$ et 3 unités de $M_2$ et celle d'une unité de $B$ nécessite 1 unité de $M_1$ et 2 unités de $M_2$ . Le bénéfice rapporté pour chaque unité est de 6 pour l'article $A$ et 4 pour l'article $B$ . La quantité de matière première $M_1$ disponible est de 60 unités. Par contre, la matière $M_2$ est disponible, mais étant périssable, l'entreprise doit utiliser au moins 30 unités. Toutefois, pour des raisons commerciales, la fabrication des articles $A$ et $B$ est limitée à 25 articles pour chaque type.

Formuler ce problème sous forme d'un programme linéaire $(P)$ .
Résoudre $(P)$ . Donner la solution optimale $X^*$ , le bénéfice optimal et retrouver la base optimale.
Que devient cette solution si la quantité de $M_1$ disponible était de 70 unités au lieu de 60 ? justifier. Quelle serait, dans ce cas, la quantité de matière $M_1$ restante si la production était optimale ?

B) L'entreprise se propose de maximiser la fabrication du produit $B$ , tout en maximisant le bénéfice.

Formuler ce problème sous forme d'un programme linéaire bi-objectif $(Q)$ .
Indiquer l'ensemble des sommets efficaces de $(Q)$ .
Donner l'ensemble des solutions efficaces supportées de $(Q)$ .

◀الحل

A.1.

Variables : $x_A$ = nombre d'articles A, $x_B$ = nombre d'articles B.

\max Z = 6x_A + 4x_B

\text{s.c. } \begin{cases} x_A/3 + x_B/2 \leq 15 \\ 2x_A + x_B \leq 60 \\ 3x_A + 2x_B \geq 30 \\ x_A \leq 25, \; x_B \leq 25 \\ x_A, x_B \geq 0 \end{cases}

A.2.

Résoudre graphiquement ou par le simplexe. La solution optimale est à un sommet du polyèdre.

A.3.

Analyse de sensibilité sur la contrainte $M_1$ .

B.1.

Bi-objectif : $\max (x_B, 6x_A + 4x_B)$ sous les mêmes contraintes.

B.2-3.

Les sommets efficaces sont ceux non dominés. Les solutions efficaces supportées sont sur la frontière du polyèdre des objectifs réalisables.

\boxed{\text{Résolution par méthode pondérée ou } \varepsilon\text{-contrainte}}

→←

→السابقConcours Doctorat 2014 — Université Mohamed Khider - Biskra — Épreuve N°05 التاليConcours Doctorat 2014 — Université Mohamed Khider - Biskra — Épreuve N°06←