Centre universitaire de Mila Année universitaire 2022/2023
Matière : Programmation linéaire 3° Année informatique
Série de TD N°1 (La modélisation des problèmes par des programmes linéaires et les résoudre
graphiquement)
Partie I : Modélisation des problèmes sous forme des PLs
Exercice 1. Une entreprise fabrique deux produits A et B à l’aide de deux matières premières
M1 et M2. Elle dispose de 100 unités de M1 et 120 unités de M2. Pour produire une unité de A,
on utilise 10 unités de M1 et 12 unités de M2, pour produire une unité de B, on utilise 20 unités
de M1 et 16 unités de M2. Le profit tiré de la vente d’une unité de A est estimé à 40 DA celui
de B est estimé à 45 DA. On s’intéresse au programme de production de cette entreprise qui
donnera le profit maximum. On demande d’exprimer ce problème en tant que PL.
Exercice 2. Une unité de production de parpaings fabrique quatre types de produit :
Les parpaings de dimensions respectivement 10cm (noté P1), 15 cm (noté P2), 20cm (noté P3),
et l’ourdi (noté P4). Pour la fabrication de ces produits, on utilise quatre matières premières, le
sable(M1), le gravier(M2), le ciment(M3) et l’eau (M4), disponibles en quantité respectivement
de 5000, 3000 et 2000 unités, l’eau est disponible en quantité illimitée. Le plan de production
de l’unité est donné dans le tableau ci-dessous :
Produits P1 P2 P3 P4 Quantité matières
premières disponibles
Matières
premières
M1 2 3 5 6 5000
M2 1 2 3 3 3000
M3 0. 1 2 3 2000
8
M4 1 1 2 2 /
Les parpaings sont vendu respectivement à raison de 6, 7, 9 et 10 DA l’unité.
Le problème pour la direction de l’unité est de trouver le nombre maximal de produit P 1, P2,
P3 et P4 à fabriquer pour avoir un bénéfice maximal, tout en respectant les contraintes de
l’unité.
1
Problème. Un appareil peut etre fabriqué à l’aide de 3 processus techniques de production :
T1, T2 et T3. Ces processus consomment chacun 4 ressources : E(énergie), MP (matière
première), L (main d’ouvre), et K (machine). Les consommations par processus, les
ressources disponibles et le prix de revient des pièces sont donnés dans le tableau suivant.
L’appareil sera vendu 280€. Trouver la quantité d’appareil à produire afin de maximiser le
profit.
E MP L K Prix de revient
T1 3 2 3 5 170
T2 2 3 6 4 160
T3 4 1 4 5 190
capacité 86 64 156 138
Partie II (Résolution graphique d’un PL)
Exercice 1. Résoudre le problème PL de l’exercice 1 à l’aide de la méthode graphique.
Exercice 2. Déterminer à l’aide de la méthode graphique la solution du PL suivant.
Min Z= X+Y
{
X +4 Y ≥ 8
4 X +Y ≥ 8
X ∧≥ 0 ,Y ≥ 0
Exercice 3. Résoudre avec la méthode graphique :
Max z =3 x 1+ x 2
{
x1 − x 2 ≤ 4
− x 1 − x 2 ≤− 3
2 x1+ x2≤ 2
x 1 , x 2≥ 0
2
Exercice 4. Déterminer à l’aide de la méthode graphique la solution du PL suivant.
{
10 x 1 +8 x 2=100
x1 ≥ 3
x2 ≤ 4
x 1 ≥ 0 et x 2 ≥0
Min z=10 x 1+ 20 x 2
Exercice 5. On considère une entreprise produisant deux biens en quantités x1 et x2
respectivement sous contraintes de capacités de production relatives à deux ateliers de
production. Le programme linéaire correspondant à la maximisation de la marge est le
suivant :
Max Z= 3x1+5x2
(a) Déterminer graphiquement le sommet optimal et donner ses coordonnées.
(b) Mettre le problème sous la forme d’´égalité par l’ajout de variables d’´écart.
(c) A l’optimum, quelles sont les variables en base et les variables hors base?
(d) Des progrès importants dans l’organisation du travail permettraient de réduire le temps
d’usinage du second bien dans le premier atelier. La première contrainte devient donc αx2 12,
où α, le nouveau temps d’usinage, est un paramètre inférieur à 2. Jusqu’`a quelle valeur peut-
on faire descendre α pour que la même base (c’est-`a-dire les mêmes variables de base) reste
optimale?
(e) En dessous de cette valeur quel est le sommet optimal (donner ses coordonnées) et quelle
est la nouvelle base (c’est-`a-dire quelles sont les nouvelles variables de base)?
