Chapitre I
Modélisation
Mohamed Hachimi TD Programmation linéaire 2 / 19
Modélisation
Exercice 1
Un atelier fabrique des tables et des bureaux.
— Chaque table nécessite 2, 5 h pour l’assemblage, 3 h pour le
polissage et 1 h pour la mise en caisse.
— Chaque bureau exige 1 h pour l’assemblage, 3 h pour le po-
lissage et 2 h pour la mise en caisse.
L’entreprise ne peut disposer, chaque semaine, de plus de 10 h
pour l’assemblage, de 15 h pour le polissage et de 8 h pour la
mise en caisse.
Sa marge de profit est de 30 dh par table et de 40 dh par bureau.
Combien de tables et de bureaux doit-on produire afin d’obtenir
un profit hebdomadaires maximal ?
Mohamed Hachimi TD Programmation linéaire 3 / 19
Modélisation
Solution de l’exercice 1
1◦ Identification des variables :
Le profit hebdomadaire évolue en fonction du nombre de
tables et bureaux fabriqués.
Le problème consiste donc à déterminer les nombres de
tables et bureaux qui permettent de réaliser le profit le plus
important. On note :
x1 = le nombre de tables à fabriquer par semaine
x2 = le nombre de bureaux à fabriquer par semaine
Mohamed Hachimi TD Programmation linéaire 4 / 19
Modélisation
Solution de l’exercice 1
2◦ Fonction objectif :
Le profit hebdomadaire z s’obtient à partir de l’expression,
z = 30x1 + 40x2
L’objectif poursuivi consiste à trouver le couple de valeurs x1
et x2 qui maximise le profit hebdomadaire z :
Max z = 30x1 + 40x2
Mohamed Hachimi TD Programmation linéaire 5 / 19
Modélisation
Solution de l’exercice 1
3◦ Contraintes :
Les valeurs prises par x1 et x2 sont limitées par les disponi-
bilités des ateliers. Ainsi, il convient de prendre en compte :
— Contraintes de production : Par exemple, le temps utilisé
pour assembler tables et bureaux ne peut excéder les 10
heures disponibles. Ce qui s’écrit donc :
2, 5x1 + x2 6 10
De même, pour le polissage et la mise en caisse, on écrit
3x1 + x2 6 15
x1 + 5x2 6 8
Mohamed Hachimi TD Programmation linéaire 6 / 19
Modélisation
Solution de l’exercice 1
— Contraintes de non-négativité : Ce type de contraintes ne
figure pas de manière explicite dans l’énoncé. Cependant
son caractère est évident car les nombres de tables et de
bureaux à fabriquer ne peuvent être que positives ou nulles :
x1 > 0, x2 > 0
Le programme linéaire ainsi défini s’écrit :
max z = 20x1 + 40x2
2, 5x1 + x2 6 10
3x1 + 3x2 6 15
x1 + 2x2 6 8
x1 > 0, x2 > 0
Mohamed Hachimi TD Programmation linéaire 7 / 19
Modélisation
Exercice 2
Un agriculteur souhaite mélanger des engrais de façon à obtenir
au minimum 15 unités de potasse, 20 unités de nitrates et
24 unités de phosphates. Il achète deux types d’engrais.
— Le type 1 procure 3 unités de potasse, 1 unité de nitrates et
3 unités de phosphates. Il coûte 120 dh.
— Le type 2 procure 1 unités de potasse, 5 unité de nitrates et
2 unités de phosphates. Il coûte 60 dh.
Exprimer à l’aide d’un programme linéaire la combinaison
d’engrais qui remplira les conditions exigées au moindre coût.
Mohamed Hachimi TD Programmation linéaire 8 / 19
Modélisation
Solution de l’exercice 2
1◦ Identification des variables :
Le coût est fonction des quantités achetées des deux types
d’engrais. Appelons :
x1 = la quantité d’engrais de type 1 à acheter
x2 = la quantité d’engrais de type 2 à acheter
Mohamed Hachimi TD Programmation linéaire 9 / 19
Modélisation
Solution de l’exercice 2
2◦ Fonction objectif :
Le coût z s’obtient à partir de l’expression,
z = 120x1 + 60x2
L’objectif poursuivi consiste à trouver la combinaison des va-
leurs x1 et x2 qui minimise le coût z :
Min z = 120x1 + 60x2
Mohamed Hachimi TD Programmation linéaire 10 / 19
Modélisation
Solution de l’exercice 2
3◦ Contraintes :
Les valeurs prises par x1 et x2 sont limitées par les exigences
minimales du mélange. Ainsi, il convient de prendre en
compte :
— Contraintes de mélange : Par exemple, il faut au moins 15
unités de potasse dans le mélange. Ce qui s’écrit :
3x1 + x2 > 15
De même, pour le nitrates et le phosphate, on écrit
x1 + 5x2 > 20
3x1 + 2x2 > 24
Mohamed Hachimi TD Programmation linéaire 11 / 19
Modélisation
Solution de l’exercice 2
— Contraintes de non-négativité : Elles assurent que les
quantités achetées ne peuvent être que positives ou nulles :
x1 > 0, x2 > 0
Le programme linéaire ainsi défini s’écrit :
min z = 120x1 + 60x2
3x1 + x2 > 15
x1 + 5x2 > 20
3x1 + 2x2 > 24
x1 > 0, x2 > 0
Mohamed Hachimi TD Programmation linéaire 12 / 19
Modélisation
Exercice 3
Un maraîcher, vendant des citrons et des oranges, veut les
grouper par lots de vente.
— Le premier lot contient 5 citrons et 1 orange, et se vend à
4 dirhams.
— Le deuxième lot contient 1 citron et 10 oranges, et se vend à
6 dirhams.
Il dispose au total de 60 citrons et 110 oranges.
Quelle est la répartition la plus avantageuse pour lui, entre les
deux types de lots ?
Mohamed Hachimi TD Programmation linéaire 13 / 19
Modélisation
Solution de l’exercice 3
Dans ce problème, l’étape la plus importante et la plus délicate
est celle de la détermination des inconnues.
Ici, il s’agit de connaître la répartition entre les deux types de lots ;
on note :
x1 = le nombre de lots du premier type
x2 = le nombre de lots du deuxème type
On obtient facilement la formulation suivante :
max z = 4x1 + 6x2
5x1 + x2 6 60
x1 + 10x2 6 110
x1 > 0, x2 > 0
Mohamed Hachimi TD Programmation linéaire 14 / 19
Modélisation
Exercice 4
On donne ci-après les caractéristiques de 3 gaz : A, B, C :
A B C
Teneur en souffre (g/m3 ) 6 2 4
Prix (Dh/m3 ) 10 25 15
Pouvoir calorifique (kcal/m3 ) 1 000 2 000 1 500
Réaliser le mélange qui donne le plus grand pouvoir calorifique
en respectant les contraintes suivantes :
• La teneur en souffre doit être au plus de 3 g/m3 ,
• Le prix ne doit pas dépasser 22 Dh/m3 .
Mohamed Hachimi TD Programmation linéaire 15 / 19
Modélisation
Solution de l’exercice 4
1◦ Identification des variables :
Le pouvoir calorifique dépend des volumes de gaz utilisés
pour produire le mélange. Appelons :
x1 = le volume de gaz A utilisé pour produire 1 m3 de mélange
x2 = le volume de gaz B utilisé pour produire 1 m3 de mélange
x3 = le volume de gaz C utilisé pour produire 1 m3 de mélange
Mohamed Hachimi TD Programmation linéaire 16 / 19
Modélisation
Solution de l’exercice 4
2◦ Fonction objectif :
Le pouvoir calorifique z d’un tel mélange est
z = 1000x1 + 2000x2 + 1500x3
L’objectif poursuivi consiste à choisir le mélange qui a le plus
grand pouvoir calorifique z :
Max z = 1000x1 + 2000x2 + 1500x3
Mohamed Hachimi TD Programmation linéaire 17 / 19
Modélisation
Solution de l’exercice 4
3◦ Contraintes :
Les ingrédients x1 , x2 et x3 d’un mélange réalisable doivent
vérifier les conditions suivantes :
— Teneur en soufre : elle doit être au plus de 3 g/m3 . Ce qui
s’écrit :
6x1 + 2x2 + 4x3 6 3
— Prix du mélange : il ne doit pas dépasser 22 Dh/m3 . Ce qui
s’écrit :
10x1 + 25x2 + 15x3 6 22
— Volume du mélange : il est de 1 m3 . Ce qui s’écrit :
x1 + x2 + x3 = 1
Mohamed Hachimi TD Programmation linéaire 18 / 19
Modélisation
Solution de l’exercice 4
— Contraintes de non-négativité : les volumes utilisés ne
peuvent être que positives ou nulles :
x1 > 0, x2 > 0 x3 > 0
Le programme linéaire ainsi défini s’écrit :
min z = 1000x1 + 2000x2 + 1500x3
6x1 + 2x2 + 4x3 6 3
10x1 + 25x2 + 15x3 6 22
x1 + x2 + x3 = 1
x1 > 0, x2 > 0, x3 > 0
Mohamed Hachimi TD Programmation linéaire 19 / 19
