Recherche Opérationnelle

Examens avec Solutions – Recherche Opérationnelle

Examen Session Normale – Printemps 2016 (Filière Economie et Gestion)

Exercice 1 – Société JET (12 pts)

Énoncé : Peintures A et B à partir de M1, M2, M3.
A : 10 kg M1, 2 kg M2, 1 kg M3, prix 1200 Dhs.
B : 5 kg M1, 3 kg M2, prix 1000 Dhs.
Disponibilités : M1=200 kg, M2=60 kg, M3=34 kg.

1. Programme linéaire :
\(x_1\) = quantité A, \(x_2\) = quantité B.
\[
\max Z = 1200x_1 + 1000x_2 \quad \text{s.c.}
\begin{cases}
10x_1 + 5x_2 \le 200 \\
2x_1 + 3x_2 \le 60 \\
1x_1 \le 34 \\
x_1, x_2 \ge 0
\end{cases}
\]

2. Résolution par simplexe (forme standard avec éarts \(e_1,e_2,e_3\)). Tableaux successifs :
Premier tableau : base \(\{e_1,e_2,e_3\}\), \(Z=0\).
Après itérations, dernier tableau optimal :

\[
\begin{array}{c|ccccc|c}
\text{Base} & x_1 & x_2 & e_1 & e_2 & e_3 & \text{CD} \\ \hline
x_1 & 1 & 0 & 3/2 & 0 & -1/4 & 15 \\
x_2 & 0 & 1 & -1/10 & 1/2 & 0 & 10 \\
e_3 & 0 & 0 & -3/10 & 1/4 & 1 & 19 \\ \hline
Z & 1200 & 1000 & 80 & 200 & 0 & 28000
\end{array}
\]
Solution optimale : \(x_1=15,\; x_2=10,\; Z=28000\) Dhs.

3. Programme dual :
Variables duales \(y_1\) (M1), \(y_2\) (M2), \(y_3\) (M3).
\[
\min W = 200y_1 + 60y_2 + 34y_3 \quad \text{s.c.}
\begin{cases}
10y_1 + 2y_2 + y_3 \ge 1200 \\
5y_1 + 3y_2 \ge 1000 \\
y_1,y_2,y_3 \ge 0
\end{cases}
\]
Solution duale lue dans le dernier tableau : \(y_1=80,\; y_2=200,\; y_3=0\) ; \(W=28000\).

4. Analyse de sensibilité pour le prix de B (1000 Dhs) :
Soit \(\Delta\) la variation. Le dernier tableau donne les coûts réduits :
\(-80+\Delta/10 \le 0 \Rightarrow \Delta \le 800\) ; \(-200-\Delta/2 \le 0 \Rightarrow \Delta \ge -400\).
Intervalle de stabilité : \(600 \le \text{prix}_B \le 1800\).

5. Vente de 50% de M1 (100 kg) :
Valeur marginale de M1 = 80 Dhs/kg → prix minimum = \(100 \times 80 = 8000\) Dhs.

6. Troisième type C (2 kg M1, 3 kg M2, prix 650 Dhs) :
Valeur marginale (coût d’opportunité) = \(2\times 80 + 3\times 200 = 760\) Dhs > 650 → ne pas produire C.

Exercice 2 – PERT (8 pts)

Tableau des tâches (A à J) avec durées et antériorités.
Résultats :
- Dates au plus tôt et plus tard calculées.
- Marges libres et totales : seules les tâches A, E, H, J ont marge totale nulle.
- Chemin critique : A – E – H – J.
- Si retard de E de 10 jours (marge totale de E = 0), la date au plus tôt de H devient 18, et la durée du projet augmente de 2 jours (passe de 20 à 22).

Examen Session Normale – Printemps 2017 (Yaourts)

Énoncé : Yaourts A et B. A : 2 kg fraise, 4 kg lait ; B : 1 kg fraise, 2 kg lait, 1 kg sucre. Disponibilités : fraise 800, lait 700, sucre 300. Bénéfices : A=50 DH, B=60 DH.

1. Programme :
\(\max Z = 50x_1 + 60x_2\)
\(2x_1 + x_2 \le 800\), \(4x_1 + 2x_2 \le 700\), \(x_2 \le 300\), \(x_1,x_2\ge0\).

2. Simplexe : dernier tableau optimal
\[
\begin{array}{c|ccccc|c}
& x_1 & x_2 & e_1 & e_2 & e_3 & \text{CD} \\ \hline
e_1 & 0 & 0 & 1 & -1/2 & 0 & 450 \\
x_1 & 1 & 0 & 1/4 & -1/2 & 0 & 25 \\
x_2 & 0 & 1 & 0 & 0 & 1 & 300 \\ \hline
Z & 0 & 0 & 50/4 & 35 & 0 & 19250
\end{array}
\]
Solution : \(x_1=25,\; x_2=300,\; Z=19250\).

3. Dual : \(\min W = 800y_1 + 700y_2 + 300y_3\) s.c. \(2y_1+4y_2 \ge 50,\; y_1+2y_2+y_3 \ge 60,\; y_i\ge0\).
Solution duale : \(y_1=0,\; y_2=50/4=12.5,\; y_3=35\).

4. Diminution d’une ressource : la fraise n’est pas entièrement consommée (reste 450 kg) → on peut la diminuer sans affecter la solution.

5. Doubler la production de A (25 unités supplémentaires) : consommation 50 kg fraise (valeur marg. 0) et 100 kg lait (valeur marg. 12.5) → coût max = \(100 \times 12.5 = 1250\) DH.

Examen de Rattrapage (Artisan)

Énoncé : Articles A et B. Usinage : A=1h, B=2h ; traitement thermique : 3h chacun ; finition seulement B=1h ; matières premières : A=2kg, B=1kg. Disponibilités : usinage 80h, thermique 150h, finition 35h, matière 80kg. Marges : A=30 DH, B=25 DH.

1. Programme :
\(\max Z = 30x_1 + 25x_2\)
\(x_1 + 2x_2 \le 80\) (usinage)
\(3x_1 + 3x_2 \le 150\) (thermique)
\(x_2 \le 35\) (finition)
\(2x_1 + x_2 \le 80\) (matière)
\(x_1,x_2 \ge 0\).

2. Résolution graphique : sommets (0,0), (40,0), (20,30), (0,35), etc.
Optimum au sommet intersection de \(x_1+2x_2=80\) et \(3x_1+3x_2=150\) → \(x_1=20,\; x_2=30,\; Z=1350\).

3. Analyse sensibilité pour bénéfice de A : intervalle de stabilité trouvé par pentes.

4. Ressources épuisées : usinage et thermique (matière première et finition ne sont pas saturées).

QCM – Programmation Linéaire et PERT

Exemple de questions :
- Fonction objectif pour société (produits A, B) : \(\max Z=140x_1+170x_2\).
- Contrainte M1 : \(6x_1+4x_2\le2000\).
- Contrainte M3 : \(x_1+2x_2\le500\).
- Dernier tableau simplexe : valeurs de la colonne \(e_1\) : \((1/4,\ -1/4,\ -1/8,\ -1/8)\).
- Solution optimale : \(x_1=250,\; x_2=125,\; Z=56250\).
- Ressources épuisées : M2 et M3 (M1 non saturée).
- Intervalle de variation du bénéfice de A : [85, 255].
- Vente de 50% de M3 : prix minimum = 6875 Dhs.
- Coût max pour 50 unités supplémentaires de A = 10000 Dhs.

PERT :
Tâches A à K. Dates au plus tôt pour F = 12 ; au plus tard pour K = 28 ; marge totale de F = 5 ; marge libre de H = 0.
Retard de E de 3 → début de G = 15 ; retard de E=4 et C=8 → durée projet = 38 ; retard de B=14 → durée projet = 36.

Remarques importantes

- Les solutions duales donnent les prix fictifs (valeurs marginales) des ressources.
- Les intervalles de stabilité permettent de juger de la robustesse de la solution.
- La méthode PERT identifie le chemin critique et les marges.