Habilitée par l’Etat suivant Arrêté N°1949/2013

Reconnue par la Fonction Publique suivant Arrêté N°0747/2010 – Arrêté N°5465/2013

Arrêté d’ouverture et Agrément N°027/METFP/2002/DG

PROGRAMMATION LINERAIRE
Optimisation d’une fonction linéaire de variable soumise à des contraintes économiques qui
interviennent sous forme d’équation ou d’inéquation linéaire
 Optimiser : programme favorable soit maximiser (bénéfice) ou minimiser (dépense, cout)
 Modèle :
Exemple : (Max) 𝑍 = 1500𝑥1 + 2500𝑥2

10𝑥1 + 5𝑥2 ≤ 150

{5𝑥1 + 10𝑥2 ≤ 150
𝑥1 ≥ 0; 𝑥2 ≥ 0
𝑥1, 𝑥2 Variables (inconnues)

𝑍: 𝑓° é𝑐𝑜𝑞
{: contrainte

1) Résolution graphique
Résoudre graphiquement
(Max) Z : 1500𝑥1 + 2500𝑥2
10𝑥1 + 5𝑥2 ≤ 150
{ 5𝑥1 + 10𝑥2 ≤ 150
𝑥1 ≥ 0; 𝑥2 ≥ 0
1) 10𝑥1 + 5𝑥2 = 150
𝑥1 = 0 𝑥2 = 30
𝑥2 = 0 𝑥1 = 15
2) 5𝑥1 + 10𝑥2 = 150
𝑥1 = 0 𝑥2 = 15
𝑥2 = 0 𝑥1 = 30

« GSI vous offre une vraie compétence, pour une meilleur performance »
GSI ANALAKELY: 034 64 272 51/033 17 767 44
BP 501 Antananarivo 101 Email: [email protected]/[email protected]
FB : Université GSI/gsimadagascar officiel
 Habilitée par l’Etat suivant Arrêté N°1949/2013
Reconnue par la Fonction Publique suivant Arrêté N°0747/2010 – Arrêté N°5465/2013
Arrêté d’ouverture et Agrément N°027/METFP/2002/DG

C (1)𝑛(2)
10𝑥1 + 5𝑥2 = 150
−2 {
5𝑥1 + 10𝑥2 = 150
−15𝑥1 = −150
Remarque :
Si 2 points extrêmes se trouvent avoir la même fonction équation on est dans le cas d’une infinité de
solution
2) Méthode du simplexe :
En vue de la résolution par la méthode du simplexe, il faut commencer par transformer le modèle
correspondant
A. Problème de maximalisation
 Règle 1 : dans un contrainte (≤) ; on ajoute une variable d’écart
Exemple : (Max) Z = 15𝑥1 + 25𝑥2
10𝑥1 + 5𝑥2 ≤ 150
{5𝑥1 + 10𝑥2 ≤ 150
𝑥1 ≥ 0; 𝑥2 ≥ 0

« GSI vous offre une vraie compétence, pour une meilleur performance »
GSI ANALAKELY: 034 64 272 51/033 17 767 44
BP 501 Antananarivo 101 Email: [email protected]/[email protected]
FB : Université GSI/gsimadagascar officiel
 Habilitée par l’Etat suivant Arrêté N°1949/2013
Reconnue par la Fonction Publique suivant Arrêté N°0747/2010 – Arrêté N°5465/2013
Arrêté d’ouverture et Agrément N°027/METFP/2002/DG

10𝑥1 + 5𝑥2 + 𝑥3 = 150

Variable d’écart {5𝑥1 + 10𝑥2 + 𝑥2 = 150
𝑥𝑗 ≥ 0; (𝑗 = 1 à 4)

𝑥1 = 0 𝑥 = 150
A l’initialisation { →{ 3
𝑥2 = 0 𝑥4 = 150
Variable hors base (Vhb) Variable de base (Vb)

Coeff é𝑐𝑜 𝑞 𝐶𝑗 15 25 0 0

𝐶𝑝 𝑉𝑏 𝑄 𝑡é 𝑥1 𝑥2 𝑥3 𝑥4

0 𝑥3 150 10 5 1 0

0 𝑥4 150 5 10 0 1

𝑧𝑗 0 0 0 0
𝑍=0
𝐴𝑗 =(𝐶𝑗 − 𝑍𝑗 ) 15 25 0 0
Colone
pivot

 𝑽𝒉𝒃 → 𝑽𝒃
Max {𝐴𝑗 } >0 ici 𝑥2 devient 𝑉𝑏

 𝑽𝒃 → 𝑽𝒉𝒃
𝑄𝑡é 150 150
Min {𝑎 } :> 0 Min { ; }
𝑖𝑗 5 10

𝑥4 Devient 𝑉ℎ𝑏
10 pivot
 Transformation ligne pivot
On divise la ligne pivot par le pivot LP (𝐿2 ) :

150 5 10 0 1
10 10 10 10 10

15 1⁄2 1 0 1⁄10

 Transformation autres lignes

Ancienne ligne - 𝑎𝑖𝑗 (nouvelle ligne pivot)
𝐿1 : 150 10 5 1 0
15 1⁄2 1 0 1⁄10
−5 ( )
75 15⁄ 0 1 −1⁄
2 2
Coeff é𝑐𝑜 𝑞 𝐶𝑗 15 25 0 0

𝐶𝑝 𝑉𝑏 𝑄 𝑡é 𝑥1 𝑥2 𝑥3 𝑥4

« GSI vous offre une vraie compétence, pour une meilleur performance »
GSI ANALAKELY: 034 64 272 51/033 17 767 44
BP 501 Antananarivo 101 Email: [email protected]/[email protected]
FB : Université GSI/gsimadagascar officiel
 Habilitée par l’Etat suivant Arrêté N°1949/2013
Reconnue par la Fonction Publique suivant Arrêté N°0747/2010 – Arrêté N°5465/2013
Arrêté d’ouverture et Agrément N°027/METFP/2002/DG

0 𝑥3 75 15⁄ 0 1 −1⁄
2 2
25 𝑥2 15 1⁄ 1 0 1⁄
2 10
𝑧𝑗 25⁄ 25 0 5⁄
2 2
𝑍 = 375
5⁄ −5⁄
𝐴𝑗 =(𝐶𝑗 − 𝑍𝑗 ) 2 0 0 2

𝑥1 : 𝑉𝑏; 𝑥3 : 𝑉ℎ𝑏

2 −1⁄
LP (𝐿1 ): 10 1 0 15
15
(𝐿2 ): 15 1⁄2 1 0 −1⁄10
−1⁄ (10 1 0 2⁄
2 15
10 0 1 −1⁄15

𝐶𝑗 15 25 0 0
𝐶𝑝 𝑉𝑏 𝑡é 𝑥1 𝑥2 𝑥3 𝑥4
𝑄
15 𝑥1 10 1 0 2⁄ −1⁄
15 15
25 𝑥2 10 0 01 −1⁄ 2⁄
15 15

𝑧𝑗 15 25 1⁄ 7⁄
3 3
𝑍 = 375
−1⁄ −7⁄
𝐴𝑗 0 0 3 3

 Arrêt tableau optimum Quand tous les 𝐴𝐽 ≪ 0

Tous 𝐴𝐽 (𝑉𝑏) = 0
𝐴𝐽 (𝑉ℎ𝑏) Solution
< 0 unique
 Règle 2 :
Dans une contrainte (≥) du 1er membre, on retranche une variable d’excédent et on ajoute une
variable artificiel et cette variable artificielle multipliée par –M est à introduire dans f° éco𝑞 à
maximiser
- Exercice d’application
(Max) Z= 2𝑥1 + 6𝑥2
𝑥1 + 𝑥2 ≤ 80
𝑥 − 𝑥1 ≥ 30
{ 2
4𝑥2 − 𝑥1 ≤ 160
𝑥1 ≥ 0; 𝑥2 ≥ 0

𝑥1 + 𝑥2 + 𝑥3 = 80
−𝑥1 + 𝑥2 − 𝑥4 + 𝑥6 = 30
{−𝑥 + 4𝑥 + 5𝑥 = 160
1 2 1
𝑥𝑗 ≥ 0; (𝑗 = 1 à 6)

« GSI vous offre une vraie compétence, pour une meilleur performance »
GSI ANALAKELY: 034 64 272 51/033 17 767 44
BP 501 Antananarivo 101 Email: [email protected]/[email protected]
FB : Université GSI/gsimadagascar officiel
 Habilitée par l’Etat suivant Arrêté N°1949/2013
Reconnue par la Fonction Publique suivant Arrêté N°0747/2010 – Arrêté N°5465/2013
Arrêté d’ouverture et Agrément N°027/METFP/2002/DG

(Max) Z = 2𝑥1 + 6𝑥2 + 0𝑥3 + 0𝑥4 + 𝑥5 − 𝑀𝑥6

A l’initialisation = 𝑥1 = 0; 𝑥2 = 0; 𝑥4 = 0
→ 𝑥3 = 80; 𝑥6 = 30 ; = 160

𝐶𝑗 2 6 0 0 0 −𝑀
𝐶𝑝 𝑉𝑏 𝑡é 𝑥1 𝑥2 𝑥3 𝑥4 𝑥5 𝑥6
𝑄
0 𝑥3 80 1 1 1 0 0 0

−M 𝑥6 30 -1 1 0 -1 0 1

𝑥5 160 -1 4 0 0 1 0
0
𝑧𝑗 M −M 0 𝑀 0 −M
𝑍 = 30𝑀

𝐴𝑗 2−M 6+M 0 −M 0 0

𝑉𝑏 = 𝑥2
𝑉ℎ𝑏 = 𝑥6
LP (𝐿2 ) = 30 -1 1 0 -1 0 1

(𝐿1 ): 80 1 1 1 0 0 0

−1 (30 − 1 1 0 − 1 0 1)
50 2 0 1 1 0 − 1

(𝐿3 ): 160 -1 4 0 0 1 0 -1

−4 (30 − 1 1 0 − 1 0 1)
40 3 0 0 4 1 − 4

𝐶𝑗 2 6 0 0 0 −𝑀
𝐶𝑝 𝑉𝑏 𝑡é 𝑥1 𝑥2 𝑥3 𝑥4 𝑥5 𝑥6
𝑄
0 𝑥3 50 2 0 01 1 0 -1

0 𝑥2 30 -1 1 0 -1 0 1

𝑥5 40 3 0 0 04 1 -4
0
𝑧𝑗 -6 6 0 −6 0 −M
𝑍 = 180𝑀

𝐴𝑗 8 0 0 6 0 -M-6

« GSI vous offre une vraie compétence, pour une meilleur performance »
GSI ANALAKELY: 034 64 272 51/033 17 767 44
BP 501 Antananarivo 101 Email: [email protected]/[email protected]
FB : Université GSI/gsimadagascar officiel
 Habilitée par l’Etat suivant Arrêté N°1949/2013
Reconnue par la Fonction Publique suivant Arrêté N°0747/2010 – Arrêté N°5465/2013
Arrêté d’ouverture et Agrément N°027/METFP/2002/DG

𝑉𝑏 = 8 → 𝑥1
{25; −30; 40⁄3} 𝑉ℎ𝑏 = 𝑥5
𝐿𝑃(𝐿3 ): 40⁄3 1 0 0 4⁄3 1⁄3 −4⁄3
- T° autre ligne
(𝐿1 ): 50 2 0 1 1 0 -1
−2(40⁄3 1 0 0 4⁄3 1⁄3 −4⁄3)
070⁄ 0 0 1 1⁄ −2⁄ 5⁄
3 3 3 3
(𝐿2 ): 30 -1 1 0 -1 0 1
+(40⁄3 1 0 0 4⁄3 1⁄3 −4⁄3)
130⁄ 1⁄ 1⁄ −1⁄
3 0 1 0 3 3 3
 Règle 3 :
Dans une contrainte (=) du 1er membre, on ajoute une variable artificielle.

- Exercice d’application
(Max) Z = 3𝑥1 + 5𝑥2
𝑥1 + 𝑥2 = 40
𝑥1 ≥ 15
{
𝑥2 ≤ 25
𝑥1 ≥ 0; 𝑥2 ≥ 0
𝑥1 + 𝑥2 + 𝑥5 = 40
{𝑥1 − 𝑥3 + 𝑥6 = 15
𝑥2 + 𝑥4 = 25
A l’initialisation, 𝑥1 = 𝑥2 = 𝑥3 = 0
𝑥5 = 40 ; 𝑥6 = 15; 𝑥4 = 25
Z= 3𝑥1 + 5𝑥2 + 0𝑥3 + 0𝑥4 − 𝑀𝑥5 − 𝑀𝑥6

𝐶𝑗 3 5 0 0 −𝑀 −𝑀
𝐶𝑝 𝑉𝑏 𝑡é 𝑥1 𝑥2 𝑥3 𝑥4 𝑥5 𝑥6
𝑄
−𝑀 𝑥5 40 1 1 0 0 1 0

−𝑀 𝑥6 15 1 0 -1 0 0 1

𝑥4 25 0 1 0 1 0 0
0
𝑧𝑗 -2𝑀 −𝑀 𝑀 0 −𝑀 −𝑀
𝑍 = −55𝑀

𝐴𝑗 3 + 2𝑀 5+𝑀 -M 0 0 0
𝑉𝑏 = 𝑥1
𝑉ℎ𝑏 = 𝑥6
𝐿𝑃(𝐿2 ): 15 1 0 -1 0 0 1

- T° autre ligne

« GSI vous offre une vraie compétence, pour une meilleur performance »
GSI ANALAKELY: 034 64 272 51/033 17 767 44
BP 501 Antananarivo 101 Email: [email protected]/[email protected]
FB : Université GSI/gsimadagascar officiel
 Habilitée par l’Etat suivant Arrêté N°1949/2013
Reconnue par la Fonction Publique suivant Arrêté N°0747/2010 – Arrêté N°5465/2013
Arrêté d’ouverture et Agrément N°027/METFP/2002/DG

(𝐿1 ): 40 1 1 0 0 1 0
−1(15 1 0 − 01 0 0 01)
25 0 1 1 0 1 −1
(𝐿3 ): 25 0 1 0 1 0 0

𝐶𝑝 3 5 0 0 −𝑀 −𝑀
𝐶𝑝 𝑉𝑏 𝑡é 𝑥1 𝑥2 𝑥3 𝑥4 𝑥5 𝑥6
𝑄
−𝑀 𝑥5 25 0 1 01 0 1 -0

−𝑀 𝑥6 15 1 0 -1 0 0 1

𝑥4 25 0 1 0 1 0 0
0
𝑧𝑗 3 −𝑀 −3 − 𝑀 0 −𝑀 3
𝑍 = 45 − 25𝑀

𝐴𝑗 0 5+𝑀 -M 0 0 -3-M
𝑉𝑏 = 𝑥2
𝑉ℎ𝑏 = 𝑥5
𝐿𝑃(𝐿1 ): 25 0 1 1 0 1
- T° autre ligne
(𝐿2 ): 15 1 0 -1 0 0
(𝐿3 ): 25 0 1 0 1 0
−1(25 0 1 1 0 1)
0 0 0 −1 1 −1

𝐶𝑝 3 5 0 0 −𝑀 −𝑀

𝐶𝑝 𝑉𝑏 𝑄 𝑡é 𝑥1 𝑥2 𝑥3 𝑥4 𝑥5 𝑥6

−𝑀 𝑥5 25 0 1 01 0 1 1

−𝑀 𝑥6 15 1 0 -1 0 0 0

𝑥4 0 0 1 0 1 0 -1
0
𝑧𝑗 3 −𝑀 −3 − 𝑀 0 −𝑀 5
𝑍 = 170
𝐴𝑗
0 5+𝑀 -M 0 0 -5-M

𝑥1 = 15

𝑥2 = 25

𝑍 = 170
B. Problème de minimisation

« GSI vous offre une vraie compétence, pour une meilleur performance »
GSI ANALAKELY: 034 64 272 51/033 17 767 44
BP 501 Antananarivo 101 Email: [email protected]/[email protected]
FB : Université GSI/gsimadagascar officiel
 Habilitée par l’Etat suivant Arrêté N°1949/2013
Reconnue par la Fonction Publique suivant Arrêté N°0747/2010 – Arrêté N°5465/2013
Arrêté d’ouverture et Agrément N°027/METFP/2002/DG

 Règle 4 : Les 3 précédentes règles sont valables pour le cas minimisation, sauf que les variables artificielles sont
multipliés par +M (M≫)
- Exercice d’application
(Min) W = 10𝑥1 + 20𝑥2

25𝑥1 + 30𝑥2 ≥ 600

{ 40𝑥1 + 60𝑥2 ≥
𝑥1 ≥ 0; 𝑥2 ≥ 0

25𝑥1 + 30𝑥2 − 𝑥3 + 𝑥5 =
{40𝑥1 + 60𝑥2 − 𝑥4 + 𝑥6 =
𝑥1 ≥ 0; 𝑥2 ≥ 0
(Min) W = 10𝑥1 + 20𝑥2 + 0𝑥3 + 0𝑥4 + 𝑀𝑥5 + 𝑀

A l’initialisation,
𝑥1 = 0
𝑥2 = 0
𝑉ℎ𝑏 {
𝑥3 = 0
𝑥4 = 0

𝑥5 = 600
𝑉𝑏 {
𝑥6 = 800

𝐶𝑝 10 20 0 0 𝑀 𝑀
𝐶𝑝 𝑉𝑏 𝑡é 𝑥1 𝑥2 𝑥3 𝑥4 𝑥5 𝑥6
𝑄
𝑀 𝑥5 600 25 30 -1 0 +1 0

𝑀 𝑥6 800 40 60 0 -1 0 +1

65M 90M −𝑀 −𝑀 𝑀 𝑀
𝑀 = 1400

10 − 65𝑀 20 − 90𝑀 𝑀 𝑀 0 0

𝑉ℎ𝑏 → 𝑉ℎ: Min {𝐴𝑗 } :< 0

Ici 𝑥2 : 𝑣𝑏
𝑄 𝑡é
𝑉𝑏 → 𝑉ℎ𝑏: Min { }
𝑎𝑖𝑗
Ici 𝑥6 : 𝑣ℎ𝑏

« GSI vous offre une vraie compétence, pour une meilleur performance »
GSI ANALAKELY: 034 64 272 51/033 17 767 44
BP 501 Antananarivo 101 Email: [email protected]/[email protected]
FB : Université GSI/gsimadagascar officiel
 Habilitée par l’Etat suivant Arrêté N°1949/2013
Reconnue par la Fonction Publique suivant Arrêté N°0747/2010 – Arrêté N°5465/2013
Arrêté d’ouverture et Agrément N°027/METFP/2002/DG

EXERCICE
1) (Min) 𝑊 = 1,5𝑥1 + 𝑥2
3𝑥1 + 2𝑥2 ≥ 6
2𝑥1 − 3𝑥2 ≤ 0
𝑥1 + 𝑥2 ≤ 8
𝑥2 ≤ 4
{𝑥1 ≥ 1 𝑥1 ≥ 0; 𝑥2 ≥ 0

2) (Min) 𝑍 = 7500𝑥1 + 6000𝑥2

30𝑥1 + 10𝑥2 ≥ 12 000
40𝑥1 − 40𝑥2 ≥ 32 00
{
30𝑥1 + 50𝑥2 ≥ 3000
𝑥1 ≥ 0; 𝑥2 ≥ 0
3) (Max) 𝑍 = 100𝑥1 + 120𝑥2
3𝑥1 + 4𝑥2 ≤ 42 000
𝑥 + 3𝑥2 ≤ 24 00
{ 1
2𝑥1 + 2𝑥2 ≤ 2600
𝑥1 ≥ 0; 𝑥2 ≥ 0
4) (Max) 𝑍 = 1000𝑥1 + 2500𝑥2
𝑥1 ≤ 60
𝑥2 ≤ 60
𝑥1 + 𝑥2 ≤ 100
𝑥1 + 2𝑥2 ≤ 150
{ 𝑥1 ≥ 0; 𝑥2 ≥ 0
5) (Max) 𝑍 = 4𝑥1 + 5𝑥2
𝑥1 ≥ 600
𝑥2 ≥ 600
𝑥2 ≤ 1000
𝑥1 + 𝑥2 ≤ 100
2𝑥1 + 3𝑥2 ≤ 4500
{ 𝑥1 ≥ 0; 𝑥2 ≥ 0
6) (Max) 𝑍 = 6𝑥1 + 4𝑥2
2𝑥1 + 2,8𝑥2 ≤ 28
𝑥1 + 𝑥2 ≥ 2
3𝑥1 − 7,8𝑥2 ≤ 18
𝑥2 ≤ 1
{ 𝑥1 ≥ 0; 𝑥2 ≥ 0

« GSI vous offre une vraie compétence, pour une meilleur performance »
GSI ANALAKELY: 034 64 272 51/033 17 767 44
BP 501 Antananarivo 101 Email: [email protected]/[email protected]
FB : Université GSI/gsimadagascar officiel