Ecole Mohammadia d’Ingénieurs Jeudi 31 mai 2012Département Génie Civil 1ère Année Contrôle de recherche opérationnelleDurée : une heure et demieDocuments non autorisés et réponses sur les feuilles de l'énoncé

Le tableau de passage au dual se trouve en page 4.Les réponses doivent être écrites sur les feuilles de l'énoncé (recto (et verso si nécessaire)).

Exercice 1 La compagnie UNIVERS fabrique 4 types de produits A, B, C et D à partir de deux ressources X et Y disponibles respectivement en quantités de 1000 et 2000 unités. Le tableau ci-dessous donne les consommations des ressources (X, Y et main d'oeuvre) par unité de produit fabriquée ainsi que les profits unitaires des ces différents produits:

A B C D Quantité disponibleX 2 3 2 5 1000Y 1 2 4 3 2000m.o (heures) 10 20 20 10 1200Profit unitaire(dh) 200 250 300 350UNIVERS doit produire au minimum 100 unités (tous types de produits confondus) et cherche bien évidemment à déterminer un plan de production qui tienne compte des contraintes résultant des données générant un profit global maximum .1/ Montrer que ce problème peut se formuler comme le programme linéaire ci-dessous :

Préciser la signification des variables et écrire le dual de ce programme linéaire. Quelle interprétation pouvez-vous donner de la variable duale correspondant à la 4ème contrainte?

1

Nom&Prénom:

2/ Les tableaux ci-dessous représentent les résultats obtenus à l’aide du solveur d’Excel.Rapport des réponses Rapport de sensibilité

F.O. (Max)

NameValeur initiale

Valeur finale

F.0. m1 0 42000

Variables Variables Valeur Coût Coeff Augmentation Réduction

NomValeur initiale

Valeur finale Nom Finale Réduit dans f.o. admissible admissible

valvar xA 0 0 valvar xA 0 -150 200 150 1E+30valvar xB 0 0 valvar xB 0 -450 250 450 1E+30valvar xC 0 0 valvar xC 0 -400 300 400 1E+30

valvar xD 0 120 valvar xD 120 0 350 1E+30 150

Contraintes Contraintes Valeur Ombre Second Augmentation Réduction

Nom Cell Value Statut Ecart Nom Finale coût membre admissible admissiblecont1 m1 600 Lâche 400 cont1 m1 600 0 1000 1E+30 400cont2 m1 360 Lâche 1640 cont2 m1 360 0 2000 1E+30 1640cont3 m1 1200 Serrée 0 cont3 m1 1200 35 1200 800 200

cont4 m1 120 Lâche 20 cont4 m1 120 0 100 20 1E+30Utiliser ces tableaux pour répondre aux questions suivantes (lesquelles sont indépendantes):

i. Expliciter une solution optimale et le profit maximum. La solution trouvée est-elle unique ? Donner une solution optimale du dual.

ii. Que se passe-t-il au niveau du profit maximum si la quantité disponible de l'ingrédient X passe à 2000 (resp.400)?

iii. Même question dans le cas où le nombre minimum d'unités à produire passe de 100 à 130?

iv. Même question dans le cas où le nombre d'heures disponibles passe à 2000 (resp.900) d'unités à produire passe de 100 à 130?

v. A partir de quelle valeur du profit unitaire du produit C , cela deviendra t-il profitable de produire à l'optimum des produits de type C? Expliquer.

vi. UNIVERS songe à introduire un nouveau type de produit (disons E) pour lequel la consommation unitaire est de 4, 2 et 10 pour l'ingrédient X, l'ingrédient Y et la main d'oeuvre respectivement. A quelle condition ce nouveau produit pourra-t-il augmenter la valeur optimale du profit global trouvée auparavant?

2

Nom&Prénom:

Exercice 2 : Trois centrales à béton, Sj, j={1, 2, 3} reçoivent du ciment par trois rampes de déchargement, Ri , i={1, 2, 3}. Les quantités requises par chaque station et les quantités offertes par chaque rampe de déchargement ainsi que les coûts unitaires de transport de la rampe Ri à la station Sj sont indiqués dans le tableau ci-dessous:

S1 S2 S3 Qté offerteR1 7 2 5 19R2 3 6 3 28R3 4 5 6 14Qté requise 17 21 21On cherche à déterminer un plan de transport tel que le coût total de transport soit minimum sous la contrainte de satisfaire les demandes de toutes les centrales.1/ Déterminer une solution réalisable pour ce problème à l’aide de l’algorithme d’initialisation étudié en classe.

2/ Appliquer une itération de l'algorithme d'optimisation à partir de la solution trouvée dans la question1/.

3

Nom&Prénom:

Rappel: Formule de passage au dual:Primal à maximiser Dual à minimiser

ième cont.

ième var.≥0

≥ = libre

jème var. ≥0

jème cont.≥

libre =

Exercice 3: Une entreprise de construction produit trois types de panneaux de coffrage (S1, S2 et S3) à partir de quatre types de matières premières (panneau (P), planches de sapin (PS), madriers (M) et clous (C)). Le tableau ci-dessous indique:

pour chaque type de panneaux de coffrage, sa consommation unitaire des différentes matières premières ainsi que son niveau minimum de production,

pour chaque matière première son coût unitaire.

P PS M C Niveau minimum de productionS1 1 1 0 1 2S2 1 2 1 0 4S3 0 1 1 1 3Coût unitaire 6 8 12 10L'objectif de cette entreprise est de déterminer un plan de production de coût minimum sous la contrainte de satisfaire (au moins) les niveaux minima de production.On suppose que l'entreprise a la possibilité de se procurer n'importe quelle quantité de matières premières.1/ Modéliser ce problème comme un programme linéaire en précisant clairement les variables de décision, la fonction objective et les contraintes.2/ Vérifier en utilisant le théorème des écarts complémentaires si l'optimum est atteint en produisant deux unités de S1, Quatre unités de S2 et 3 unités de S3.

4

Nom&Prénom:

Brouillon

Bonne année

5

Nom&Prénom: