Recherche Opérationnelle 1ème année GE

ECOLE NATIONALE D’INGENIEURS DE TUNIS

Département Génie Electrique

Enseignants : Farah Zeghal Mansour, Imen Safra et Ali Balma

Durée : 1h30
Documents non autorisés

Examen de
RECHERCHE OPERATIONNELLE

Exercice 1 : (8 points)
Soit le programme linéaire dual (D) suivant :

(D) Minimiser W = 4 u1 + u2 + 3 u3
sc:
u1 - 2 u2 + u3  2
2 u1 + 2 u2 + u3  3
u1  0 ; u2  0 ; u3  0

1. Ecrire le programme primal (P).

2. Résoudre (P) graphiquement.
a. Donner la solution optimale.
b. Donner la valeur optimale de la fonction objectif.
c. Donner la base optimale de (P).
3. A partir de la solution de (P), déterminer la solution optimale du programme (D) ainsi
que W en détaillant votre raisonnement.

Exercice 2 : (6 points)
La société Pain Chaud produit divers types de pains et viennoiseries. En particulier, elle
travaille pour un groupe d'hypermarchés MiniPrix à qui elle vend 4 produits périssables : la
baguette tradition, le pain de campagne, le croissant et le pain au chocolat. MiniPrix absorbe
toute la production des baguettes tradition et des pains de compagne mais uniquement 1000
croissants et 1500 pains au chocolat par jour.

Pain Chaud vend une baguette au prix de 190 millimes et un pain au prix de 250 millimes.
Quant aux viennoiseries, elle vend un croissant au prix de 450 millimes et un pain au chocolat
au prix de 550 millimes.

Les baguettes et pains s'élaborent à partir de 2 farines, l'une fine de blé et l'autre complète d'un
mélange de céréales. Quant aux viennoiseries, elles sont préparées à partir de la pate
feuilletée. Les quantités nécessaires sont présentées dans le tableau ci-dessous.

2012-2013 1/4
Recherche Opérationnelle 1ème année GE

Produits Quantité (en gr) Quantité (en gr) Pate feuilletée

de farine fine de farine complète (en gr)
Baguette tradition 200 100
Pain de campagne 400 300
Croissant aux raisins 50
Pain au chocolat 65

Le problème quotidien de Pain Chaud est de répartir la production de la journée entre les
baguettes et les pains de façon à tirer à maximiser ses recettes.

Chaque matin, Pain Chaud dispose de 2200 kg de farine fine de blé, de 2400 kg de farine
complète de céréales et de 180 kg de pate feuilletée. Les ressources en machine et employés
de Pain Chaud lui permettent de traiter toutes les quantités de farine et de pate feuilletée.

Le problème de production de cette entreprise se formule comme suit :

Variables de décision :
X1 : nombre de baguettes tradition à produire par jour
X2 : nombre de pains campagne à produire par jour
X3 : nombre de croissants à produire par jour
X4 : nombre de pains au chocolat à produire par jour

Les contraintes de ressources sont notées respectivement FF, FC et PF pour les quantités
disponibles de farine fine, de farine complète et de pate feuilletée. Les contraintes CR et PC
traduisent les demandes limitées pour les croissants et les pains au chocolat respectivement.

Le programme linéaire s’écrit alors :

MAX 190 X1 + 250 X2 + 450 X3 + 550 X4

SUBJECT TO
FF) 0.2 X1 + 0.4 X2 <= 2200
FC) 0.1 X1 + 0.3 X2 <= 2400
PF) 0.05 X3 + 0.065 X4 <= 180
CR) X3 <= 1000
PC) X4 <= 1500
END

La résolution de ce problème par Lindo nous donne le rapport suivant :

1) 3365000.

VARIABLE VALUE REDUCED COST

Tableau 1

X1 11000.000000 0.000000
X2 0.000000 130.000000
X3 1000.000000 0.000000
X4 1500.000000 0.000000

2012-2013 2/4
Recherche Opérationnelle 1ème année GE

ROW SLACK OR SURPLUS DUAL PRICES

FF) 0.000000 950.000000
Tableau 2
FC) 1300.000000 0.000000
PF) 32.500004 0.000000
CR) 0.000000 450.000000
PC) 0.000000 550.000000

RANGES IN WHICH THE BASIS IS UNCHANGED:

OBJ COEFFICIENT RANGES

VARIABLE CURRENT ALLOWABLE ALLOWABLE
Tableau 3

COEF INCREASE DECREASE

X1 190.000000 INFINITY 65.000000
X2 250.000000 130.000000 INFINITY
X3 450.000000 INFINITY 450.000000
X4 550.000000 INFINITY 550.000000

RIGHTHAND SIDE RANGES

ROW CURRENT ALLOWABLE ALLOWABLE
RHS INCREASE DECREASE
Tableau 4

FF 2200.000000 2600.000000 2200.000000

FC 2400.000000 INFINITY 1300.000000
PF 180.000000 INFINITY 32.500004
CR 1000.000000 650.000061 1000.000000
PC 1500.000000 500.000092 1500.000000

Répondre aux questions suivantes en utilisant le rapport ci-dessus. Indiquer le numéro du(des)
tableau(x) utilisé(s) pour chaque question.

1. Donner :
a. la base optimale,
b. la quantité optimale à produire de chaque produit,
c. la valeur maximale de la recette journalière,
d. la solution optimale du dual.

2. Le pain de campagne s’avère peu rentable au prix actuel. A quel prix serait-il
éventuellement intéressant de le produire ?

3. Le prix d’un pain au chocolat a été sur-estimé.

a. La base actuelle reste-t-elle optimale si celui-ci passe de 550 à 500 ? Justifier.
b. Donner la solution optimale et la valeur correspondante de la recette.

4. La base actuelle reste-t-elle optimale si le groupe MiniPrix décide d’acheter 1700

croissants par jour ? Justifier.
5. On peut obtenir de la pate feuilletée au prix de 800 millimes le kilo Conseilleriez-vous
d’en acheter ? Justifier.
6. Pain Chaud envisage de lancer la production de pains aux céréales qui nécessite 200gr
de farine fine et 400gr de farine complète par unité. A quel prix vendre ce nouveau
pain pour qu’il soit intéressant de le produire ? Justifier.

2012-2013 3/4
Recherche Opérationnelle 1ème année GE

Exercice 3 : (6 points)
Une entreprise stocke ses produits dans 5 dépôts D1, D2, D3, D4 et D5 de capacités
respectives 50, 55, 70, 60 et 50. Elle dispose de 3 points de vente P1, P2 et P3 dont les
demandes respectives sont 85, 90 et 80 unités par semaine.
La matrice des coûts unitaires (par unité de produit) de transport de chaque dépôt vers chaque
point de vente est donnée par le tableau suivant. Quand un dépôt ne peut pas servir un point
de vente, la case correspondante est marquée par ---.

P1 P2 P3
D1 5 7 8
D2 6 --- 10
D3 4 9 ---
D4 5 6 12
D5 --- 8 10

Le problème consiste à déterminer les quantités de produits à transporter des différents dépôts
vers les différents points de vente de façon à minimiser le coût total de transport tout en
respectant les quantités de produits disponibles à chaque dépôt ainsi que la demande de
chaque point de vente.

1. Modéliser ce problème par la théorie des graphes en précisant le graphe (ensemble des
sommets, ensemble des arcs, valeurs sur les arcs) et le problème correspondant. Ne
pas résoudre.

2. On suppose qu’un coût unitaire de stockage de 4 unités monétaires est à payer pour
chaque unité de produit conservée en dépôt, après livraison des quantités demandées
par les différents points de vente. Comment intégrer cette donnée au graphe initial ?
Ne pas résoudre.

3. On suppose qu’au niveau de chaque dépôt, un coût de manutention est à payer par
unité de produit à transporter. Ce coût correspond aux opérations de comptage, de
contrôle, de mise en palette et de chargement du produit dans les moyens de
transports. Il est estimé à 3 unités monétaires pour le dépôt D1, 2 unités monétaires
pour les dépôts D2 et D3 et 1,5 unités monétaires pour les dépôts D4 et D5. Comment
modifier le graphe pour intégrer cette nouvelle donnée ? Ne pas résoudre.

Bonne chance

2012-2013 4/4