Examen de recherche operationnelle session de mai 2014 -Prog
Télécharger PDFUNIVERSITÉ DE TUNIS
École Supérieure des Sciences Économiques et Commerciales de Tunis
Examen de Recherche Opérationnelle (3ème Année Finance)
Session principale (Mai 2014)
Aucun document n'est autorisé. Durée : 2 heures. Cet examen contient deux pages.
Exercice 1 : Production d'alliage
Un industriel souhaite produire un alliage Z composé de 30% de plomb, 30% de zinc et 40% d'étain. Il peut se procurer sur le marché des alliages A, B, C, D, E, F, G, H, I. Leurs compositions en pourcentage et leurs prix respectifs au kilogramme sont détaillés ci-dessous :
- Alliage A: Plomb 10%, Zinc 30%, Étain 30%, Coût 4.1
- Alliage B: Plomb 10%, Zinc 10%, Étain 80%, Coût 4.3
- Alliage C: Plomb 40%, Zinc 30%, Étain 60%, Coût 5.8
- Alliage D: Plomb 60%, Zinc 50%, Étain 10%, Coût 6
- Alliage E: Plomb 30%, Zinc 30%, Étain 10%, Coût 7.6
- Alliage F: Plomb 30%, Zinc 30%, Étain 40%, Coût 7.5
- Alliage G: Plomb 30%, Zinc 40%, Étain 30%, Coût 7.3
- Alliage H: Plomb 50%, Zinc 20%, Étain 50%, Coût 6.9
- Alliage I: Plomb 20%, Zinc 40%, Étain 10%, Coût 7.3
L'objectif est de déterminer la quantité de chaque alliage (A à I) à acheter pour obtenir 1 Kg de l'alliage Z au coût de revient minimum. Écrire le programme linéaire correspondant.
Exercice 2 : Campagne publicitaire
Une entreprise désire effectuer une campagne publicitaire dans la télévision (locale, par satellite), la radio et les journaux pour un produit lancé récemment sur le marché. Le but de la campagne est d'attirer le maximum possible de clients. Les résultats d'une étude de marché sont donnés par le tableau suivant :
- Télévision Locale: Coût d'une publicité 40 DT, Nombre de clients potentiels 400, Nombre de clientes potentielles (femmes) 300
- Télévision par Satellite: Coût d'une publicité 75 DT, Nombre de clients potentiels 900, Nombre de clientes potentielles (femmes) 400
- Radio: Coût d'une publicité 30 DT, Nombre de clients potentiels 500, Nombre de clientes potentielles (femmes) 200
- Journaux: Coût d'une publicité 15 DT, Nombre de clients potentiels 200, Nombre de clientes potentielles (femmes) 100
Pour la campagne, on prévoit de ne pas dépenser plus de 800 DT au total et on demande que ces objectifs soient atteints :
- Au minimum 2000 femmes regardent, entendent ou lisent la publicité.
- La campagne publicitaire à la télévision ne doit pas dépasser 500 DT.
- Au moins 3 spots publicitaires seront assurés par la télévision locale et au moins 2 spots par la télévision par satellite.
- Le nombre des publicités à la radio ou dans les journaux est pour chacun entre 5 et 10.
Écrire le programme linéaire qui permet de déterminer le nombre optimal de spots publicitaires.
Exercice 3 : Résolution graphique de programmes linéaires
Résoudre graphiquement ces programmes linéaires :
-
Problème 1 : Maximisation
Max Z = 100x1 + 200x2
Sous contraintes :
x1 + x2 ≤ 150
4x1 + 2x2 ≤ 440
x1 + 4x2 ≤ 480
x1 ≤ 90
x1 ≥ 0, x2 ≥ 0
-
Problème 2 : Maximisation
Max Z = -2x1 + 3x2
Sous contraintes :
x1 ≤ 5
2x1 - 3x2 ≤ 6
x1 ≥ 0, x2 ≥ 0
-
Problème 3 : Minimisation
Min Z = 3x1 + 2x2
Sous contraintes :
x1 + 2x2 ≤ 2
2x1 + 4x2 ≥ 8
x1 ≥ 0, x2 ≥ 0
-
Problème 4 : Maximisation
Max Z = x1 + 3x2
Sous contraintes :
2x1 + 6x2 ≤ 30
x1 ≤ 10
x2 ≤ 4
x1 ≥ 0, x2 ≥ 0
-
Problème 5 : Maximisation
Max Z = x1 + x2
Sous contraintes :
3x1 + 2x2 ≤ 40
x1 ≤ 10
x2 ≤ 5
x1 ≥ 0, x2 ≥ 0
CORRECTION EXAMEN DE RECHERCHE OPÉRATIONNELLE
Correction Exercice 1 : Modélisation du mélange d'alliages (6 points)
Variables de décision :
Soit xi : la quantité (en Kg) d'alliage i, pour i = A, B, ..., I, à acheter.
Les contraintes de non-négativité sont : xA ≥ 0, xB ≥ 0, xC ≥ 0, xD ≥ 0, xE ≥ 0, xF ≥ 0, xG ≥ 0, xH ≥ 0, xI ≥ 0.
Fonction objectif :
Minimiser le coût d'achat des différents alliages :
Min Z = 4.1xA + 4.3xB + 5.8xC + 6xD + 7.6xE + 7.5xF + 7.3xG + 6.9xH + 7.3xI
Contraintes :
- Équation de la conservation de la matière (1 Kg total d'alliage Z) :
- Équation de la satisfaction des proportions en Plomb (30%) :
- Équation de la satisfaction des proportions en Zinc (30%) :
- Équation de la satisfaction des proportions en Étain (40%) :
xA + xB + xC + xD + xE + xF + xG + xH + xI = 1
0.1xA + 0.1xB + 0.4xC + 0.6xD + 0.3xE + 0.3xF + 0.3xG + 0.5xH + 0.2xI = 0.3
0.3xA + 0.1xB + 0.3xC + 0.5xD + 0.3xE + 0.3xF + 0.4xG + 0.2xH + 0.4xI = 0.3
0.3xA + 0.8xB + 0.6xC + 0.1xD + 0.1xE + 0.4xF + 0.3xG + 0.5xH + 0.1xI = 0.4
Le programme linéaire qui modélise ce problème de mélange s'écrit :
Min Z = 4.1xA + 4.3xB + 5.8xC + 6xD + 7.6xE + 7.5xF + 7.3xG + 6.9xH + 7.3xI
Sous contraintes :
xA + xB + xC + xD + xE + xF + xG + xH + xI = 1
0.1xA + 0.1xB + 0.4xC + 0.6xD + 0.3xE + 0.3xF + 0.3xG + 0.5xH + 0.2xI = 0.3
0.3xA + 0.1xB + 0.3xC + 0.5xD + 0.3xE + 0.3xF + 0.4xG + 0.2xH + 0.4xI = 0.3
0.3xA + 0.8xB + 0.6xC + 0.1xD + 0.1xE + 0.4xF + 0.3xG + 0.5xH + 0.1xI = 0.4
xA, xB, xC, xD, xE, xF, xG, xH, xI ≥ 0
Correction Exercice 2 : Modélisation de la campagne publicitaire (6 points)
Variables de décision :
- x1 : le nombre de spots publicitaires dans la télévision locale
- x2 : le nombre de spots publicitaires dans la télévision par satellite
- x3 : le nombre de spots publicitaires dans la radio
- x4 : le nombre d'affiches publicitaires dans les journaux
Les contraintes de non-négativité sont vérifiées : x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0.
Fonction objectif :
La fonction objectif à maximiser représente le nombre total de clients potentiels par publicité :
Max Z = 400x1 + 900x2 + 500x3 + 200x4
Contraintes du problème :
- Coût total de la campagne publicitaire (budget maximal de 800 DT) :
- Nombre de clientes femmes potentielles (au minimum 2000) :
- Contrainte budgétaire pour la télévision (ne doit pas dépasser 500 DT) :
- Contrainte sur le nombre de spots TV locale (au moins 3) :
- Contrainte sur le nombre de spots TV par satellite (au moins 2) :
- Contraintes sur le nombre de publicités à la radio (entre 5 et 10) :
- Contraintes sur le nombre de publicités dans les journaux (entre 5 et 10) :
40x1 + 75x2 + 30x3 + 15x4 ≤ 800
300x1 + 400x2 + 200x3 + 100x4 ≥ 2000
40x1 + 75x2 ≤ 500
x1 ≥ 3
x2 ≥ 2
5 ≤ x3 ≤ 10
5 ≤ x4 ≤ 10
Le programme linéaire résultant est :
Max Z = 400x1 + 900x2 + 500x3 + 200x4
Sous contraintes :
40x1 + 75x2 + 30x3 + 15x4 ≤ 800
300x1 + 400x2 + 200x3 + 100x4 ≥ 2000
40x1 + 75x2 ≤ 500
x1 ≥ 3
x2 ≥ 2
5 ≤ x3 ≤ 10
5 ≤ x4 ≤ 10
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0
Correction Exercice 3 : Résolution graphique des programmes linéaires (10 points)
1) Problème de maximisation
Max Z = 100x1 + 200x2
Sous contraintes :
x1 + x2 ≤ 150 (1)
4x1 + 2x2 ≤ 440 (2)
x1 + 4x2 ≤ 480 (3)
x1 ≤ 90 (4)
x1 ≥ 0, x2 ≥ 0
La solution optimale est B(40, 110).
2) Problème avec solution non bornée
Max Z = -2x1 + 3x2
Sous contraintes :
x1 ≤ 5 (1)
2x1 - 3x2 ≤ 6 (2)
x1 ≥ 0, x2 ≥ 0
On peut augmenter la valeur de la fonction objectif dans la direction des flèches indéfiniment, donc la solution est non bornée.
3) Problème impossible (espace des solutions vide)
Min Z = 3x1 + 2x2
Sous contraintes :
x1 + 2x2 ≤ 2 (1)
2x1 + 4x2 ≥ 8 (2)
x1 ≥ 0, x2 ≥ 0
L'espace des solutions réalisables est vide. Il n'y a pas de points (x1, x2) qui satisfassent simultanément les deux inégalités.
4) Problème à solutions multiples
Max Z = x1 + 3x2
Sous contraintes :
2x1 + 6x2 ≤ 30 (1)
x1 ≤ 10 (2)
x2 ≤ 4 (3)
x1 ≥ 0, x2 ≥ 0
L'ensemble des points décrit par le segment [AB] représente les solutions optimales du problème linéaire. Cela signifie qu'il existe une infinité de solutions qui donnent la même valeur maximale pour la fonction objectif.
5) Problème de dégénérescence
Max Z = x1 + x2
Sous contraintes :
3x1 + 2x2 ≤ 40 (1)
x1 ≤ 10 (2)
x2 ≤ 5 (3)
x1 ≥ 0, x2 ≥ 0
La solution optimale B(10, 5) est dite dégénérée si trois contraintes (ou plus) concourent en ce point. Ici, les contraintes x1 ≤ 10, x2 ≤ 5 et 3x1 + 2x2 ≤ 40 (car 3*10 + 2*5 = 30 + 10 = 40) sont toutes satisfaites à l'égalité en B(10, 5).
Questions Fréquemment Posées (FAQ)
- Qu'est-ce que la Recherche Opérationnelle ?
- La Recherche Opérationnelle est une discipline qui utilise des méthodes scientifiques et mathématiques pour aider à prendre des décisions optimales dans des situations complexes, notamment en modélisant des problèmes et en utilisant des algorithmes pour trouver les meilleures solutions possibles.
- Qu'est-ce qu'un programme linéaire ?
- Un programme linéaire est un modèle mathématique qui permet d'optimiser (maximiser ou minimiser) une fonction objectif linéaire, sous réserve d'un ensemble de contraintes exprimées sous forme d'équations ou d'inégalités linéaires. Les variables de décision doivent être non-négatives.
- Comment interpréter une solution dégénérée en programmation linéaire ?
- Une solution optimale est dite dégénérée lorsque le nombre de contraintes actives (qui sont satisfaites à l'égalité) au point optimal est supérieur au nombre de variables de décision. Graphiquement, cela signifie que le point optimal est l'intersection de plus de deux lignes de contrainte dans un problème à deux dimensions.