Ctr. Univ. Naâma 3ème Année L.M.
D 2024/
Dépt. D’Informatique Programmation Linéaire 2025
Fiche TD N°2
Exercice 1 :
Par la méthode graphique, résoudre les PL suivants :
max 𝑧 = 4𝑥 + 10𝑦
3𝑥 + 4𝑦 ≥ 12 max 𝑧 = 2𝑥 + 3𝑦 max 𝑧 = 8𝑥 + 16𝑦
3𝑥 + 4𝑦 ≤ 36 2𝑥 + 𝑦 4 −𝑥 + 2𝑦 ≤ −1
𝑥≥2 x≥7 𝑥 + 2𝑦 ≤ 5
𝑠. 𝑐 𝑠. 𝑐 { 𝑠. 𝑐 {
𝑥 ≤ 10 4x − 3y ≥ 24 𝑥+𝑦 ≥ 0
𝑦≤4 x, y ≥ 0 𝑥, 𝑦 ≥ 0
{ 𝑥, 𝑦 ≥ 0
max 𝑧 = 80𝑥 + 60𝑦 min 𝑧 = 24𝑥 + 20𝑦
5𝑥 + 3𝑦 30 𝑥 + 𝑦 30
2x + 3y ≤ 24 x + 2y ≤ 40
𝑠. 𝑐 { 𝑠. 𝑐 {
x + 3y ≥ 18
x, y ≥ 0 x, y ≥ 0
Exercice 2 :
Un agriculteur souhaite que son troupeau de moutons consomme la plus faible ration quotidienne de trois
éléments nutritifs A, B et C. les exigences quotidiennes sont de 16 pour A, 12 pour B et 35 pour C. L’agriculteur
achète deux types d’aliments P et Q.
Une unité de P comprend 2 unités de A, 1 unité de B et 5 unités de C ; et elle coute 200 DA.
Une unité de Q comprend 1 unité de A, 1 unité de B et 7 unités de C ; et elle coute 400 DA.
L’agriculteur cherche la combinaison la moins couteuse des quantités de P et Q qui respectera l’exigence de
consommation minimale éléments nutritifs.
Exercice 3 :
Soit le modèle de programmation linéaire suivant :
max 𝑧 = 9𝑥 + 5𝑦
3𝑥 + 4𝑦 ≤ 36
𝑠. 𝑐 { 3𝑥 + 4𝑦 ≥ 0
𝑥, 𝑦 ≥ 0
a) Ecrire le P.L sous la forme standard.
b) Quel est le nombre maximal de solutions de base pour ce P.L ?
c) Quel est nombre exact de solutions de base ?
d) Déterminer la solution correspondante à la base constituée de 𝑥 et de la variable d’écart de la
première contrainte.
e) La solution trouvée est-elle réalisable ? Justifier.
f) Déterminer la solution correspondante à la base constituée de x, y et de la variable d’écart de la
première contrainte, pour le PL suivant :
max 𝑧 = 10𝑥 + 12𝑦
𝑥 + 2𝑦 ≤ 40
𝑦 ≤ 30
𝑠. 𝑐 {
𝑥 ≤ 25
𝑥, 𝑦 ≥ 0
g) La solution trouvée est-elle réalisable ? Justifier.
