Ingénieur forestier
BGR PROGRAMMATION LINEAIRE
ENSAF
STF 3
Ingénieur forestier
I. RESUME DU COURS
1.Définition :
La programmation linéaire est un outil mathématique
[Link] :
Elle permet de trouver des solutions optimales aux problèmes qui se présentent dans le monde
3. Domaines d’intervention de la programmation linéaire :
Elle est utilisée dans tous les secteurs de l’industrie et aussi dans la société afin de résoudre des
problèmes.
4. Formulation générale d’un problème de programmation linéaire :
Elle s’écrit de la manière suivante :
W = CO + C1X1 + C2X2+………+. CnXn max.(min)
b1 + b11x1 + b12x12 + ……+b1nxn ≥ 0
b2 + b21x21 + b22x22 + …. + b2nxn ≥ 0
bm + bm1xm1 + bm2xm2 + …. + bmnxn ≥ 0
X1 ≥ 0 ; X2 ≥ 0 ; X3 ≥ 0 car ce sont des contraintes de non négativité
5. Formulation essential d’un problème de programmation linéaire
Pour écrire la formulation essentielle il faut, dans le cas où les inégalités de la formulation
générale seraient ≤ multiplié ses inégalités par (-1) afin d’avoir les ≥ et ainsi écrire la
formulation et veillé aussi à ce que la fonction économique (W) tende vers
(min) dans le cas ou la fonction générale tendra vers (max) multiplié cette équation
objective ou économique par (-1)
Elle s’écrit de la manière suivante :
W = CO + C1X1 + C2X2+………+. CnXn min
b1 + b11x1 + b12x12 + ……+b1nxn =b1
b2 + b21x21 + b22x22 + …...+ b2nxn =b2 bm + bm1xm1 + bm2xm2 + …...+ bmnxn =bm
Unis par la chlorophylle
X1 ≥ 0 ; X2 ≥ 0 ; X3 ≥ 0 car ce sont des contraintes de non négativité et b1 ; b2 ; bm des
constantes(nombres)
6. Méthode de résolution graphique :
6.1 Démarche :
On désigne les demi-plans des contraintes
On détermine le domaine « D » désignant l’ensemble des points satisfaisant toutes les
contraintes. Le domaine « D » est l’intersection de tous les demi-plans
On trace la droite représentant la fonction « objective » et passant par l’origine
On translate la droite de la fonction « objectif » selon son vecteur normal
Le point optimal est le point du domaine « D » que la droite de la fonction « objective »
touchera lors de son déplacement
6.2 Remarque :
Faire un dessin suffisamment grand pour être précis
Le vecteur normal de la droite définissant la fonction « objective » indique le sens dans
lequel on doit la translater pour trouver le point optimal. Il se trouve facilement la
𝑎
droite :ax1 + bx2 + c a pour vecteur normal ( )
𝑏
Si le vecteur normal indique déplacement vers le haut, la fonction « objective » doit
couper l’axe Ox2 le plus haut possible dans le cas d’une maximisation, et le plus bas
possible dans le cas d’une minimisation, tout en touchant le domaine « D » c’est-à-dire
dans le cas d’une maximisation le point optimal est celui le plus éloigné du domaine et
dans le cas d’une minimisation celui le plus proche
Si le vecteur normal indique un déplacement vers le bas, la fonction « objective » doit
couper l’axe Ox2 le plus haut possible dans le cas d’une minimisation, tout en touchant
le domaine « D » c’est-à-dire le point optimal est le point le plus proche dans le cas
d’une maximisation et le point éloigné dans le cas d’une minimisation
7. Méthode simplexe de résolution d’un programme linéaire :
Pour traiter un problème à la méthode du simplexe il faut suivre et respecter quelques étapes
importantes que nous pouvons citer :
Premièrement, présenter la formulation linéaire du problème problème poser (plus tard
vous verrez ce qu’on entend par FL
L3-STF
Deuxièmement, présenter la formulation essentielle du problème tout en respectant
comment passer de la formulation générale à essentiel c’est-à-dire si donc votre si dans
votre formulation linéaire il y a les ≤ veillé à les transformer en ≥ afin que vous obteniez
la formulation générale et ainsi passer à la formulation essentielle
Présenter la forme standard, dresser le tableau et ainsi commencer la résolution
7.1 Présentation du tableau de résolution :
VB ML Variable hors base
X1 X2 … Xi … Xn
Y1 B1 A11 A12 … A1j … A1n
Y2 B2 A21 A22 … A2j … A2n
… … … … … … … …
Yi Bi Ai1 Ai2 … Aij … Ain
… … … … … … … …
ym bm Am1 Am2 … amj … Amn
VB = variables de base ; ML = Membres libres
La méthode simplexe est une méthode qui s’effectue avec 2 solutions pour que une fois que
vous les auriez trouvé le travail sera terminé et vous pourriez conclure il s’agit de la :
Solution de départ
Solution optimale
La solution de départ est trouvée lorsque tous les membres (ML) de votre problème sont
positifs. Les détails voire cours …
La solution optimale est trouvée lorsque tous les éléments de la ligne ym de ce tableau sont
négatifs ou de la ligne contenue la fonction économique ou objective dans le cadre d’une vraie
résolution, vous comprendriez lorsqu’on traitera les sujets. Détail voire cours
L3-STF
II. RESOLUTION DES SUJETS DES EXAMENS PASSES
Sujet1 : (formulation d’un problème linéaire)
Solution :
1. Détermination des variables :
Xij : quantité de fret i à charger dans le compartiment j
2. Détermination des contraintes :
2.1 Contraintes liées à la capacité de stockage des compartiments
Pour le poids :
A l’avant: X1A + X2A + X3A + X4A ≤ 12 (1)
Au centre : X1C + X2C + X3C + X4C ≤ 18 (2)
A l’arrière : X1A + X2A + X3A + X4A ≤ 10 (3)
Pour le volume
A l’avant: 70X1A + 100X2A + 85X3A + 65X4A ≤ 1000 (4)
Au Centre : 70X1C + 100X2C + 85X3C + 65X4C ≤ 1300 (5)
A l’arrière : 70X1A + 100X2A + 85X3A+ 65X4A ≤ 700 (6)
2. Détermination de la fonction économique ou objective
W = 220(X1A + X1C + X1A) + 280(X2A + X2C + X2A) + 250(X3A+ X3C+X3A) +200(X4A + X4C +
X4A) max
La model sera :
W = 220(X1A + X1C + X1A) + 280(X2A + X2C + X2A) + 250(X3A+ X3C+X3A) +200(X4A + X4C +
X4A) max
(1)
(2)
(3)
(4)
(5)
(6)
L3-STF
X1A ≥ 0 ; X2A ≥ 0 ; X3A ≥ 0 ; X4A ≥ 0 ; X1C ≥ 0 ; X2C ≥ 0 ; X3C ≥ 0 ; X4C ≥ 0 ; X1A ≥ 0 ; X2A ≥ 0 ;
X3A ≥ 0 ; X4A ≥ 0 ; Car ce sont des contraintes de non négativité
Nb : lors de la résolution d’un problème linéaire il est interdit de représenter la formulation
linéaire avec des chiffres tel que s’est fait là-haut (1) ; (2) mais il faut représenter les
inéquations de toutes les contraintes du problème linéaire.
Sujet 2 : (résoudre par la méthode graphique)
Exo 1 : Soit le problème linéaire suivant : Y = 6X1 + 5X2 max
2X1 + X2 ≤ 9
3X1 + X2 ≥ 6
2X1 + 2X2 ≤14 ; X1 ≥ 0 ; X2 ≥ 0
1. Résolution graphique :
0 4,5
D1: 2X1 + X2 ≤ 9 X1 0 4,5 A1 ( ) ; A2 ( )
X2 9 0 9 0
2X1 + X2 = 9
0 2
D2: 3X1 + X2 ≥ 6 X1 0 2 A3 ( ); A4 ( )
6 0
X2 6 0
3X1 + X2 = 6
D3 : 2X1 + 2X2 ≤14
X1 0 7
X2 7 0 0 7
2X1 + 2X2 = 14 A5 ( ) ; A6 ( )
7 0
Vecteur normal :
6
Y = 6X1 + 5X2 → ( )
𝑉𝑛 5
GRAPHIQUE :
L3-STF
Le point optimal est l’intersection des droites (D1) et (D3)
2X1 + X2 =9 (-1)
2X1 + 2X2 = 14
-X2 + 2X2 = -9 + 14 X2 = 5 (3)
(3) dans (1) :
2X1 + 5 = 9 X1 = 2
Conclusion :
X1 = 2 ; X2 = 5 et le bénéfice Y sera Y = 6(2) +5 (5) Y = 37
2. Trouvons la Formulation essentiel : Y = 6X1 + 5X2 max
2X1 + X2 ≤ 9
3X1 + X2 ≥ 6
2X1 + 2X2 ≤ 14 ; X1 ≥ 0 ; X2 ≥ 0
L3-STF
Après les procédures de transformation du passage de la Générale à essentiel c’est-à-dire en
transformant le (max) en (min) et en changeant les ≤ en ≥ par la multiplication par (-1) on
trouve ce système ci-dessous
Y’ = - Y = - 6X1 – 5X2 min Y’ = - Y = -6X1 – 5X2 min
-2X1 – X2 ≥ -9 9-2X1 – X2 ≥ 0
3X1 + X2 ≥ 6 -6+3X1 + X2 ≥ 0
-2X1 - 2X2 ≥ -14 14-2X1 - 2X2 ≥ 0
Soit Y1 ; Y2 ; Y3 des constantes
Le système de formulation du système est :
Y’ = - 6X1 – 5X2 min
Y1 = 9- 2X1 – X2
Y2 = -6 + 3X1 + X2
Y3 = 14 – 2X1 – 2X2
X1 ≥ 0 ; X2 ≥ 0 ce sont des contraintes de non négativité
Exo 2 : (formulation du problème linéaire)
1. Détermination des variables :
X1 : Quantité de boisson A
X2 : Quantité de boisson B
X3 : Quantité de boisson C
X4 : Quantité de boisson D
X5 : Quantité de boisson E
2. Détermination des contraintes :
2.1 Contraintes liés à la disponibilité des quantités de boisson :
Boisson A : X1 ≤ 200 (1)
L3-STF
Boisson B : X2 ≤ 400 (2)
Boisson C : X3 ≤ 100 (3)
Boisson D : X4 ≤ 50 (4)
Boisson E : X5 ≤ 800 (5)
2.2 Contraintes liées à la quantité nécessaire de chaque jus :
Pour le jus d’orange : 40X1 + 5X2 + 100 X3 ≥ 20 (6)
Pour le jus de pamplemousse : 40X1 + 10X2 + 100X4 ≥ 10 (7)
Pour le jus de framboise : 20X2 ≥ 5 (8)
3. Détermination de la fonction économique :
W = 1,5X1 + 0,75X2 + 2X3 + 1,75X4 + 0,25X5 min
Le modèle sera :
W = 1,5X1 + 0,75X2 + 2X3 + 1,75X4 + 0,25X5 min
(1)
(2)
(3)
(4)
(5)
(6)
(7)
(8)
X1 ≥ 0 ; … X5 ≥ 0 ; ce sont des contraintes de non négativité
Nb : j’attire encore votre attention veillez à ne pas mettre les (1) dans le modèle de Formulation
linéaire comme là-haut mais représentez plutôt toutes les inéquations des contraintes du
problème.
Sujet 2 :
Exo 1 : (Formulation du problème linéaire)
1. Détermination des variables :
X1 : quantité de P1 à incorporer dans la nourriture
L3-STF
X2 : quantité de P2 à incorporer dans la nourriture
X3 : quantité de P3 à incorporer dans la nourriture
2. Détermination des contraintes :
2.1 Contraintes liées aux quantité des éléments de chaque produit afin d’obtenir une
bonne nourriture
Pour la protéine : X1 + 2X2 + X3 ≥ 1100
Pour le lipide : X1 + 3X2 + 2X3 ≥ 1400
Pour la vitamine A : X1 + X2 +3X3 ≥ 1500
3 . Détermination de la fonction économique :
W = 340X1 + 2400X2 + 560X3 min
Le model sera :
W = 340X1 + 2400X2 + 560X3 min
(1)
(2)
(3)
X1 ≥ 0 ; X2 ≥ 0 ; X3 ≥ 0 Ce sont des contraintes de non négativité
Exo 2 : (Méthode simplexe)
Le model sera
Fonction économique : S = 4X1 + 6X2 + 20X3 + 17X4 max
X1 + X3 + 2X4 ≤ 10
X2 + 2X3 + X4 ≤ 4
X1 ≥ 0 ; X2 ≥ 0 ; X3 ≥ 0 et X4 ≥ 0 ce sont des
contraintes de non négativité
L3-STF
Déterminons la formulation essentielle :
Après le procédé des démarches cités là-haut on obtient :
Le système de formulation essentiel est
S’= - 4X1 - 6X2 - 20X3 - 17X4 min
Y1 = 10 – X1 - X3 - 2X4
Y2 = 4 - X2 - 2X3 – X4
X1 ≥ 0 ; X2 ≥ 0 ; X3 ≥ 0 Ce sont des contraintes de non négativité
Forme standard :
S’= - 4X1 - 6X2 - 20X3 - 17X4 min
Y1 = 10 – (X1 +0X2 + X3 +2X4)
Y2 = 4 – (0X1+ X2 + 2X3 + X4)
S’=0 – (4X1 + 6X2 + 20X3 +17X4)
TABLDEAU STANDARD
VB ML Variable hors base
X1 X2 X3 X4
Y1 10 1 0 1 2
Y2 4 0 1 2 1
S’ 0 4 6 20 17
Comme tous les membres libres du tableau standard sont positifs alors la solution de départ est
trouvée :
X1 = X2 = X3 = X4 = 0 , la valeur de la fonction objective est 0
Cherchons la solution optimale :
1 a été choisi comme pivot voilà pourquoi il est encerclé
L3-STF
Tableau intermédiaire
ML Variable hors base
VB
X1 X2 X3 X4
Y1 10 1 0 1 2
-8 0 0 -4 -2
Y2 4 0 1 2 1
4 0 1 2 𝛼 =1
S’ 0 4 6 20 17
0 0 -17 -34 -17
ML Variable hors base
VB
X1 X2 X3 X4
Y1 2 1
0 -3 -2
Y2
4 0 1 2 1
S’ 4 -11 -17
0 -14
ML Variable hors base
VB
X1 X2 X3 X4
Y1 2 1 0 -3 -2
2 1 0 -3 -2
Y2 4 0 1 2 1
0 0 0 0 0
S’ 4 -11 -14 -17
0 -4 0 0 0
L3-STF
ML Variable hors base
VB
X1 X2 X3 X4
Y1 4 1 0 -3 -2
Y2 4 0 1 2 1
S’ -11 -14 -17
0 -4
Conclusion :
Ce Tableau présente le résultat final, dans ce tableau les membres correspondants sont tous
positifs et dans la ligne « W » tous les éléments sont négatifs hormis le membre libre. La
solution optimale est alors trouvée :
NB : cet exercice a été faite dans le plus grand doute possible dans ne vous confiez pas à 100%
sur ça si cela vient à revenir dans le cadre d’un devoir ou à la session je vous en prie asseyez
de réfléchir un peu mais je peux vous rassurer que cette méthode simplexe a été traité avec
toute la sureté possible. Merci pour votre compréhension
Sujet 3 :
Exo 1 : (Formuler le problème linéaire)
1. Détermination des variables :
X1 : nombres de pièces P1 à fabriquer
X2 : nombres de pièces P2 à fabriquer
L3-STF
2. Détermination des contraintes :
2.1 Contraintes liées aux nombres d’heures machines :
Pour l’atelier A : 3X1+X2 =1200 (1)
Pour l’atelier B : 5X1 + 3X2 = 3000 (2)
Pour l’atelier C : 2X1 + 3X2 =18000 (3)
2.2 Détermination de la fonction économique :
W = 150 X1 + 100 X2 min
Le modèle sera :
W = 150 X1 + 100 X2 min
(1)
(2)
(3)
X1 ≥ 0 ; X2 ≥ 0 ; car ce sont des contraintes de non négativités
Exo 2 : (Résoudre par la méthode graphique)
W = X – 2Y min, max
5X + 3Y≥ 30
X – Y≤ 3
-3X + 5Y ≤ 15
X1 ≥ 0 ; X2 ≥ 0 ; ce sont des contraintes de non négativités
Résolution graphique :
X 0 6 0 6
D1 : 5X + 3Y =30 A1 ( ) ; A2 ( )
Y 10 0 10 0
0 3
D2 : X – Y = 3 X 0 3 A3 ( ) ; A4 ( )
Y -3 0 −3 0
X 0 -5
Y 3 0 0 −5
D3 : -3X + 5Y = 15 A3 ( ) ; A4 ( )
3 0
L3-STF
1
D4 : = X – 2Y 𝑣⃗ ( )
−2
1er Cas : W = X – 2Y min
Le point optimal est le point le plus éloigner du domaine, donc le point d’intersection entre
X–Y=3
-3X + 5Y = 15
2Y = 9+15 ; Y = 24/2 ; Y= 12 dans la 1ère équation on a : X = 3 +12 = 9 ; X = 15
W = 15 -2(12) = -9
Conclusion : X = 15 ; Y = 12 et W = -9
2e Cas : W = X – 2Y max
L3-STF
Le point optimal est le point le point le plus rapproché du domaine, donc le point
d’intersection entre ses droites
X – Y = 3 (3)
5X + 3Y = 30
8X = 9+30 ; X = 39/8 = 4,875 cette valeur dans (1) on a : Y = -3 +4,875 = 1,875
W = 4,875 -2(1,875) =
Conclusion : X = 4,875 ; Y = 1,875 et W = 1,125
Exo 3 : (Résolution graphique)
1.Détermination des variables :
X1 : Nombres de Kg de IND1
X2 : Nombres de Kg de IND2
2. Détermination des contraintes :
Contraintes liées à la quantité de la substance A : 500X1 + 400X2 ≥500
Contraintes liées à la quantité de la substance B : 150X1 + 50X2 ≥ 100
Contraintes par rapport à la quantité de la substance C : 5 ≤ 20X1 ≤ 15
3.Détermination de la fonction économique :
W = 20X1 + 40X2 min
Le model sera
W = 20X1 + 40X2 min
(1)
(2)
(3)
X1 ≥ 0 ; X2 ≥ 0 ; ce sont des contraintes de non négativités
Résolution graphique :
D1 : 500X1 + 400X2 = 500
D2 : 150X1 + 50X2 =100 Vous recherchez les coordonnées des points comme là-haut
L3-STF
D3 : 20X1 =5 et D4 : 20X1 = 15 ; X1 = 0,25 et X1 = 0,75
20 1
D6 : W = 20X1 + 40X2 min ; 𝑣⃗ ( ) 𝑣⃗ ( )
40 2
Sujet 4 :
Exo1 : (Formulation du problème linéaire)
1.Détermination des variables :
X1 : Nombres de vaches
X2 : Nombres de moutons
2.Détermination des contraintes
2.1Contraintes liées à la capacité de stockage des établies : pour Vaches : X1 ≤ 50 ; pour
moutons : X2 ≤ 200
L3-STF
2.2 Contraintes liées à la disponibilité des arpents : X1 + 0,2X2 ≤ 72
2.3Contraintes liées à la limite d’heure de travail : 150X1 + 25X2 ≤ 10000
3. Fonction objective :
W= 250X1 + 45X2 max
Le modèle sera
W= 250X1 + 45X2 max
(1)
(2)
(3)
(4)
X1 ≥ 0 ; X2 ≥ 0 ; ce sont des contraintes de non négativités
NB : une fois de plus je le redis il est interdit de mettre (1) dans le modèle vous devrez écrire
toutes les contraintes telle qu’elles sont.
Exo 2 : (Formulation du problème linéaire)
1.Détermination des contraintes :
X1 : Quantité de carotte
X2 : Quantité de pomme de terre
2.Détermination des contraintes :
2.1Contraintes liées aux besoins des éléments contenue dans la carotte et pomme de terre :
Kcal : X1 + 2X2 ≥ 2
Vitamine B : 4X1 +3X2 ≥ 6
Vitamine A : 3X1 + X2 ≥ 3
3. Fonction économique :
W = PX1 + P/2 X2 min avec P : un montant quelconque ; si P= 500 alors la condition
sera respectée parce qu’une mesure de carotte coute autant que 2 mesures de pomme de terre
donc on aura W = 500X1 + (500/2) X2 min et vous voyez bien que 1carotte =2 P.T
L3-STF
Le modèle sera
W = PX1 + P/2 X2 min
(1)
(2)
(3)
X1 ≥ 0 ; X2 ≥ 0 ; ce sont des contraintes de non négativités
Sujet 5 :
Exo 1 : (Formulation du problème linéaire)
1.Détermination des variables :
X1 = Quantité de carotte à produire
X2 : Quantité de courgette à produire
2.Détermination des contraintes :
2.1 Contrainte liée à la disponibilité du terrain : 4X1 + 5X2 ≤ 1000
2.2 Contrainte liée à la quantité des éléments :
Pour l’engrais A : 2X1 +X2 ≤ 8
Pour l’engrais B : X1 + 2X2 ≤ 7
Pour antiparasite X2 ≤ 3
[Link] économique :
W = P1X1 + P2X2 max avec P1 et P2 des montants
Le modèle sera
W = P1X1 + P2X2 max
(1)
(2)
(3)
X1 ≥ 0 ; X2 ≥ 0 ; ce sont des contraintes de non négativités
L3-STF
Exo2 : (Formulation du problème linéaire)
1.Détermination des variables :
X1 : Nombre de lots de 6F
X2 : Nombres de lots de 8F
2.Détermination des contraintes
Contraintes par rapport à la disponibilité des chaussettes en coton : 2X1 + 2X2 ≤ 24
Contraintes liées par rapport à la disponibilité des chaussures en laines : 4X1 + 8X2 ≤
84
[Link] économique :
W = 6X1 + 8X2 max
2X1 + 2X2 ≤ 24
4X1 + 8X2 ≤ 84
X1 ≥ 0 ; X2 ≥ 0 ; ce sont des contraintes de non négativités
3.1 Formulation essentielle :
2X1 + 2X2 ≤ 24 -2X1 -2X2 ≥ -24 24-2X1 -2X2 ≥ 0
4X1 + 8X2 ≤ 84 -4X1 -8X2 ≥ -84 84-4X1 -8X2 ≥ 0
Soit Y1 et Y2 des entiers on a :
W’ = -6X1 - 8X2 min
Y1 = 24-2X1 -2X2
Y2 = 84-4X1 -8X2
X1 ≥ 0 ; X2 ≥ 0 ; ce sont des contraintes de non négativités
3.2 Forme standard :
Y1 = 24-(2X1 + 2X2)
Y2 = 84-(4X1 +8X2)
W’ = 0-(6X1 + 8X2)
L3-STF
Tableau standard
VB ML Variable hors base
X1 X2
Y1 24 2 2
Y2 84 4 8
W’ 8
0 6
Tous les membres libres du Tableau standard sont positifs alors la solution de départ est trouvée
Y1 = 24 ; Y2 = 84
Cherchons la solution optimale : Après transformation on obtient
Tableau standard
VB ML Variable hors base
X1 X2
Y1 62/6 5/9 -1/6
Y2 10 -1/3 1/6
W’ -5/6
-482/6 6
NB : je tiens à vous informer que ceci est un travail manuel donc il peut toujours y avoir des
erreurs surtout quand il s’agit de la méthode simplexe car chacun est libre de choisir son pivot
donc les méthodes simplexes de ce document ne sont pas trop à prendre en compte il vous sera
L3-STF
donc pas d’une grande importance en clair vous devriez comprendre la procédure en classe et
appliquer les pendant une évaluation ou examens .
Conclusion pour cet exercice : Comprendre la cour puis le faire.
NB : il est important de savoir que le doc d’industrie du bois ne va jamais loin de ses anciens
sujets qui se trouvent ici dans ce document il suffit juste à un bon étudiant qui assiste au cours
et les comprend pour valider sa matière donc je vous suggère de beaucoup lire ce document ça
vous aidera énormément mais toute fois le doc peut faire des recherches et vous donner un sujet
qui ne figure pas ici donc soyez prudent et merci pour votre compréhension.
L3-STF
Bonne compréhension et chance à tous.
