Ministère de l’Enseignement Supérieur ‫وزارة التعليـم العالي و البحث العلمي‬

et de la Recherche Scientifique
Université de Carthage ‫جامعـة قرطاج‬
Ecole Polytechnique de Tunisie ‫المدرسـة التونسية للتقنيات‬

Travaux Dirigés de Recherche Opérationnelle

Modélisation
Exercice 1. Une usine fabrique 2 produits 𝑃1 et 𝑃2 en utilisant un certain nombre de ressources : équipement,
main d'œuvre, matières premières. Ces besoins sont indiqués dans le tableau ci-dessous. Par ailleurs, chaque
ressource est disponible en quantité limitée.
𝑃1 𝑃2 Disponibilité
Equipement 3 9 81
Main d'œuvre 4 5 55
Matière première 2 1 20
Les deux produits 𝑃1 et 𝑃2 rapportent à la vente respectivement des bénéfices de 6 dinars et 4 dinars par unité.
Donner une formulation algébrique du PL correspondant à la situation.
Exercice 2. Un fabricant d'aliment pour bétail cherche à optimiser la composition de celui-ci sachant qu'il
n'entre dans sa composition que trois ingrédients : Blé, colza et soja. L'aliment devra comporter au moins 22
pour cent d'un composant 𝐶1 et 4 pour cent d'un composant 𝐶1 pour se conformer aux normes en vigueur. Les
données sont résumées dans le tableau ci-dessous :
Blé Soja Colza
Pourcentage de 𝐶1 12 52 42
Pourcentage de 𝐶2 2 2 10
Prix d’une tonne 25 41 39
Donner la formulation algébrique du PL en prenant comme variables structurelles les différents pourcentages
requis pour obtenir une tonne d'aliment.
Exercice 3. Une entreprise fabrique deux produits X et Y à partir de 3 matières premières A, B et C, disponibles
en quantités respectives 40, 480 et 16.
Pour fabriquer une unité de X, on utilise 2 unités de A, 6 unités de B et une unité de C.
La production de 2 unités de Y utilise comme matière A la quantité nécessaire pour fabriquer une unité de X
et comme matière B, la quantité nécessaire pour fabriquer 10 unités de X.
La matière C entre dans la fabrication du produit X uniquement.
Le budget de l'entreprise est de 6000 Dinars, et X et Y coutent respectivement 200 Dinars et 300 Dinars l'unité.
Le prix de vente de X et Y est de 240 Dinars et 330 Dinars l'unité.
Formulez le programme linéaire correspondant à la situation.

Résolution graphique et normalisation

Exercice 1. Résoudre graphiquement les Programmes linéaires :
min 2𝑥1 + 𝑥2 𝐞𝐧𝐬𝐮𝐢𝐭𝐞 max 2𝑥1 + 𝑥2
min 5𝑥1 + 3𝑥2 𝐞𝐧𝐬𝐮𝐢𝐭𝐞 max 5𝑥1 + 3𝑥2
𝑥1 + 𝑥2 ≥ 1
{ { 𝑥1 + 𝑥2 ≤ 2
𝑥2 ≤ 2
𝑥1 , 𝑥2 ≥ 0
𝑥1 , 𝑥2 ≥ 0
max 𝑥1 + 3𝑥2 max 𝑥1 + 𝑥2
max 𝑥1 + 𝑥2 𝐞𝐧𝐬𝐮𝐢𝐭𝐞 max −3𝑥1 + 4𝑥2
𝑥1 + 𝑥2 ≤ 14 𝑥1 + 𝑥2 ≤ 14
−𝑥1 + 𝑥2 ≤ 1
−2𝑥1 + 3𝑥2 ≤ 12 −2𝑥1 + 3𝑥2 ≤ 12 {
−𝑥1 + 2𝑥2 ≤ 4
2𝑥1 − 𝑥2 ≤ 12 2𝑥1 − 𝑥2 ≤ 12
𝑥1 , 𝑥2 ≥ 0
{ 𝑥1 , 𝑥2 ≥ 0 { 𝑥1 , 𝑥2 ≥ 0
Exercice 2. Mettez sous forme canonique, puis sous forme standard les PL suivants :
 Ministère de l’Enseignement Supérieur ‫وزارة التعليـم العالي و البحث العلمي‬
et de la Recherche Scientifique
Université de Carthage ‫جامعـة قرطاج‬
Ecole Polytechnique de Tunisie ‫المدرسـة التونسية للتقنيات‬

min 𝑥1 + 𝑥2 + 𝑥3 max 𝑥1 + 𝑥2 − 𝑥3 max 𝑥1 + 𝑥2 + 2𝑥3

𝑥1 + 𝑥2 ≥ 1 𝑥1 + 𝑥2 + 𝑥3 ≤ 2 𝑥1 + 𝑥2 ≤ 14
𝑥2 ≤ 2 𝑥1 − 𝑥2 − 𝑥3 ≥ 2 𝑥1 − 𝑥3 ≤ 12
2𝑥1 − 𝑥2 + 𝑥3 ≤ 12 2𝑥2 − 𝑥3 = 2 𝑥1 − 2𝑥2 − 𝑥3 ≤ 12
{ 𝑥1 , 𝑥2 , 𝑥3 ≥ 0 { 𝑥1 , 𝑥2 ≥ 0 { 𝑥1 , 𝑥2 ≥ 0 ; 𝑥3 ≤ 0

Simplexe
Exercice 1. Résoudre par la méthode du simplexe et interprétez graphiquement les programmes linéaires :
max 36𝑥1 + 24𝑥2
max 𝑥1 + 𝑥2
𝑥1 + 𝑥2 ≤ 27
−2𝑥1 + 𝑥2 ≤ 1
3𝑥1 ≤ 16 {
𝑥1 − 2𝑥2 ≤ 4
𝑥1 + 2𝑥2 ≤ 32
𝑥1 , 𝑥2 ≥ 0
{ 𝑥1 , 𝑥2 ≥ 0
Exercice 2. Dégénérescence. Résoudre par la méthode du simplexe et interprétez graphiquement les PL :
max 𝑥1 + 𝑥2 max 3𝑥1 + 𝑥2
𝑥1 + 𝑥2 ≤ 14 𝑥1 + 𝑥2 ≤ 4
−2𝑥1 + 3𝑥2 ≤ 12 𝑥1 ≤ 2
2𝑥1 − 𝑥2 ≤ 12 2𝑥1 + 𝑥2 ≤ 6
{ 𝑥1 , 𝑥2 ≥ 0 { 𝑥1 , 𝑥2 ≥ 0
Exercice 3. Simplexe en 2 phases. Résoudre par la méthode du simplexe en 2 phases les programmes linéaires
suivants
max 𝑥1 + 𝑥2
min 𝑥1 − 2𝑥2 max 𝑥1 + 2𝑥2
𝑥1 + 𝑥2 ≥ 6
𝑥1 + 𝑥2 ≤ 3 2𝑥 + 3𝑥2 ≥ 3
𝑥1 ≤ 1 { { 1
−𝑥1 + 3𝑥2 ≤ −4 3𝑥1 + 𝑥2 ≤ 4
𝑥1 − 𝑥2 = 3
𝑥1 , 𝑥2 ≥ 0 𝑥1 , 𝑥2 ≥ 0
{ 𝑥1 , 𝑥2 ≥ 0
max 2𝑥1 + 𝑥2 − 𝑥3
max −𝑥1 + 2𝑥2 − 2𝑥3
𝑥1 + 2𝑥2 − 𝑥3 = 8
𝑥 + 𝑥2 − 𝑥3 = 3
−𝑥1 + 𝑥2 + 𝑥3 ≤ 4 { 1
−𝑥1 + 3𝑥2 = −4
4𝑥1 + 𝑥2 + 3𝑥3 ≥ 2
𝑥1 , 𝑥2 , 𝑥3 ≥ 0
{ 𝑥1 , 𝑥2 , 𝑥3 ≥ 0
Exercice 4. Dualité. Solve the following LP problem using the dual simplex method.
min 3𝑥1 + 4𝑥2 + 5𝑥3
2𝑥1 + 2𝑥2 + 𝑥3 ≥ 6
𝑥1 + 2𝑥2 + 3𝑥3 ≥ 5
𝑥1 , 𝑥2 , 𝑥3 ≥ 0.

Exercice Boolean Variables. Une société dispose de 1 400 000 DT à investir. Les experts proposent 4
investissements possibles
Coût Bénéfice
Inv 1 500 000 1 600 000
Inv 2 700 000 2 200 000
Inv 3 400 000 1 200 000
Inv 4 300 000 800 000
Variables de décision : 𝑥𝑖 , 𝑖 = 1, … ,4 : 𝑥𝑖 = 1 si l’investissement i est choisi ; 𝑥𝑖 = 0 sinon
Objectif : maximiser bénéfice max 16 𝑥1 + 22 𝑥2 + 12 𝑥3 + 8 𝑥4
Contrainte : budget d’investissement 5 𝑥1 + 7 𝑥2 + 4 𝑥3 + 3 𝑥4 ≤ 14
 Ministère de l’Enseignement Supérieur ‫وزارة التعليـم العالي و البحث العلمي‬
et de la Recherche Scientifique
Université de Carthage ‫جامعـة قرطاج‬
Ecole Polytechnique de Tunisie ‫المدرسـة التونسية للتقنيات‬

Exercice Integer Programming. Solve the following problem using the Branch and Bound algorithm
max 3𝑥1 + 4𝑥2
2𝑥1 + 𝑥2 ≤ 6
{
2𝑥1 + 3𝑥2 ≤ 9
𝑥1 , 𝑥2 ∈ ℕ
Exercice 4. Une raffinerie fabrique deux qualités d’essence (A et B) en mélangeant dans certaines proportions
deux produits semi-finis (P1 et P2). Les indices d’octane et les quantités disponibles par jour pour ces deux
produits sont indiqués dans le tableau suivant :
Indice d’octane Nb. de barils/jour
Produit 1 71 3900
Produit 2 99 5000
L’indice d’octane de l’essence A doit être d’au moins 96 et celui de l’essence B d’au moins 85. La raffinerie
vend toute sa production de A et B aux prix respectifs de 3,75 $ et 2,75 $ par baril. Les excédents éventuels
de P1 sont revendus au prix de 1,25 $ par baril à une fabrique de goudron et ceux de P2 sont revendus à un
terrain d’aviation au prix de 2,25 $ par baril.
On notera 𝑥1𝐴 et 𝑥2𝐴 (resp. 𝑥1𝐵 et 𝑥2𝐵 ) le nombre de barils de P1 et de P2 utilisés pour fabriquer A (resp. B).
Indication : Indice d’octane des essences A et B :
71𝑥1𝐴 + 99𝑥2𝐴 71𝑥1𝐵 + 99𝑥2𝐵
𝐼𝐴 = ; 𝐼𝐵 =
𝑥1𝐴 + 𝑥2𝐴 𝑥1𝐵 + 𝑥2𝐵
1. Calculer, en fonction de 𝑥1𝐴 et 𝑥2𝐴 , l’indice d’octane de A.
2. Ecrire le programme correspondant à l’optimisation du profit de la raffinerie.
3. Résoudre ce programme par la méthode du simplexe.
4. Indiquer en % la composition de A et B, solutions du problème. Quel est finalement leur indice
d’octane ?