Correction TD N° 4

Exercice 1
𝑀𝑎𝑥𝑖𝑚𝑖𝑠𝑒𝑟 𝑍 = 4𝑥1 + 5𝑥2 − 3𝑥3

𝑆𝑜𝑢𝑠 𝑐𝑜𝑛𝑡𝑟𝑎𝑖𝑛𝑡𝑒𝑠 𝑥1 + 𝑥2 + 𝑥3 ≤ 5

𝑥1 − 𝑥2 ≥1 ⇔ −𝑥1 + 𝑥2 ≤ −1

𝑥1 + 3𝑥2 + 𝑥3 ≤ 11

𝑒𝑡 𝑥1 , 𝑥2 , 𝑥3 ≥0

1) Résolution par le simplexe

Ecriture de la forme standard après ajout des variables d’écart et artificielle

𝑀𝑎𝑥𝑖𝑚𝑖𝑠𝑒𝑟 𝑍 = 4𝑥1 + 5𝑥2 − 3𝑥3 − 𝑀𝑎1

𝑆𝑜𝑢𝑠 𝑐𝑜𝑛𝑡𝑟𝑎𝑖𝑛𝑡𝑒𝑠 𝑥1 + 𝑥2 + 𝑥3 + 𝑒1 = 5

𝑥1 − 𝑥2 − 𝑒2 + 𝑎1 = 1

𝑥1 + 3𝑥2 + 𝑥3 + 𝑒3 = 11

𝑒𝑡 𝑥1 , 𝑥2 , 𝑥3 , 𝑒1 , 𝑒2 , 𝑒3 , 𝑎1 ≥0

Premier tableau du simplexe

Cj 4 5 -3 0 0 0 -M XB
Variables x 1 x2 x3 e1 e2 e3 a1
CB de base
0 e1 1 1 1 1 0 0 0 5
-M a1 1 -1 0 0 -1 0 1 1 V.S
0 e3 1 3 1 0 0 1 0 11
Zj M M 0 0 M 0 -M -M
Zj-Cj -M-4 M-5 3 0 M 0 0
V.E

1
 Cj 4 5 -3 0 0 0 -M XB
Variables x 1 x2 x3 e1 e2 e3 a1
CB de base
0 e1 0 2 1 1 1 0 -1 4 V.S
4 x1 1 -1 0 0 -1 0 1 1
0 e3 0 4 1 0 1 1 -1 10
Zj 4 -4 0 0 -4 0 4 4
Zj-Cj 0 -9 3 0 -4 0 4+M
V.E

Cj 4 5 -3 0 0 0 -M XB
Variables x 1 x2 x3 e1 e2 e3 a1
CB de base
5 x2 0 1 1/2 1/2 1/2 0 -1/2 2 S2
4 x1 1 0 1/2 1/2 -1/2 0 1/2 3 S1
0 e3 0 0 -1 -2 -1 1 1 2 y3
Zj 4 5 9/2 9/2 1/2 0 -1/2 22
Zj-Cj 0 0 15/2 9/2 1/2 0 -1/2+M

S1 S2 S3 y1 y2 y3
Le tableau est optimal. La solution optimale est :

𝑥1∗ = 3; 𝑥2∗ = 2; 𝑒2∗ = 2; 𝑒1∗ = 𝑒2∗ = 𝑎1∗ = 0 𝑒𝑡 𝑍 ∗ = 22

Le programme DUAL s’écrit :

𝑀𝑖𝑛𝑖𝑚𝑖𝑠𝑒𝑟 𝑊 = 5𝑦1 − 𝑦2 + 11𝑦3

𝑆𝑜𝑢𝑠 𝑐𝑜𝑛𝑡𝑟𝑎𝑖𝑛𝑡𝑒𝑠 𝑦1 − 𝑦2 + 𝑦3 ≥4

𝑦1 + 𝑦2 + 3𝑦3 ≥ 5

𝑦1 + 𝑦3 ≥ −3

𝑒𝑡 𝑦1 , 𝑦2 , 𝑦3 ≥0

2
Tableau optimal DUAL

Cj 5 -1 11 0 0 0 XB
Variables y1 y2 y3 s1 s2 s3
CB de base
0 s3 0 0 1 -1/2 -1/2 1 15/2
5 y1 1 0 2 -1/2 -1/2 0 9/2
-1 y2 0 1 1 1/2 -1/2 0 1/2
Zj 5 -1 9 -3 -2 0 22
Zj-Cj 0 0 -2 -3 -2 0

Exercice 2
1) a)
Cj 2 3 4 0 0 0 XB
Variables x 1 x2 x3 e1 e2 e3
CB de base
4 x3 1 3 1 1 0 0 100
0 e2 1 -2 0 0 1 0 3
0 e3 -2 4 0 1 0 1 93
Zj 4 12 4 4 0 0 400
Zj-Cj 2 9 0 4 0 0

b) La solution est optimale vu que tous les (𝑍𝑗 − 𝐶𝑗 ) ≥ 0. La solution optimale est :

𝑥3∗ = 100; 𝑒2∗ = 3; 𝑒3∗ = 93; 𝑥1∗ = 𝑥2∗ = 𝑒1∗ = 0 𝑒𝑡 𝑍 ∗ = 400

2) a) 𝑥2 est une variable hors base ; on agit sur le coefficient 𝑐2 de telle sorte que 𝛿2 =
𝑍2 − 𝐶2 soit nul. 𝑍2 − 𝐶2 = 0 ⟹ 12 − 𝐶2 = 0 ⟹ 𝐶2 = 12.
b) soit 𝑐3′ = 𝑐3 + 𝜆 ⟹ 𝑐3′ = 4 + 𝜆
on part du tableau optimal et on recalcule les nouveaux (𝑍𝑗 − 𝐶𝑗 ). Pour que la solution
reste optimale, il faut que tous les (𝑍𝑗 − 𝐶𝑗 ) demeurent ≥ 0.

2 3 4+𝜆 0 0 0
𝑥1 𝑥2 𝑥3 𝑒1 𝑒2 𝑒3
𝑍𝑗 4+𝜆 12 + 3𝜆 4+𝜆 4+𝜆 0 0
𝑍𝑗 − 𝐶𝑗 2+𝜆 9 + 3𝜆 0 4+𝜆 0 0

2+𝜆 ≥ 0 𝜆 ≥ −2 𝑐3 ≥ 2
{9 + 3𝜆 ≥ 0 ⟺ { 𝜆 ≥ −3 ⟺ {𝑐3 ≥ 1
4+𝜆 ≥ 0 𝜆 ≥ −4 𝑐3 ≥ 0

3
 Pour que la solution reste optimale, il faut que 𝑐3 ∈ [2 , +∞[
3) a) La matrice de base inverse est donnée par {𝑒1 , 𝑒2 , 𝑎1 }

1 0 0
−1
𝐵 = (0 1 0)
1 0 −1
b) Soit 𝛿3 la modification de la troisième contrainte. Soit 𝑏3′ = 𝛿3 + 7

1 0 0 100 100
𝐵−1 𝑏3′ = (0 1 0 ) ( 3 ) = ( 3 ) ≥ 0 si et seulement si
1 0 −1 𝛿3 + 7 93 − 𝛿3

93 − 𝛿3 ≥ 0 ⟺ 𝛿3 ≤ 93. Donc 𝑏3 ≤ 100.

4) La contrainte duale correspondante est : 𝑦1 + 𝑦2 + 𝑦3 ≥ 5.

𝑦1∗ + 𝑦2∗ + 𝑦3∗ = 4 + 0 + 0 = 4 < 5 . la contrainte n’est pas vérifiée. Trouvons la nouvelle
solution optimale.

1 1 0 0 1 1
−1 (1) = (0
𝐵 1 0) ( 1) = ( 1)
1 1 0 −1 1 0

Cj 2 3 4 5 0 0 0 XB
Variables x 1 x2 x3 x4 e1 e2 e3
CB de base
4 x3 1 3 1 1 1 0 0 100
0 e2 1 -2 0 1 0 1 0 3 V.S
0 e3 -2 4 0 0 1 0 1 93
Zj 4 12 4 4 4 0 0 400
Zj-Cj 2 9 0 -1 4 0 0
V.E

Le tableau n’est pas optimal. 𝑥4 entre dans la base et 𝑒2 sort de la base.

Cj 2 3 4 5 0 0 0 XB
Variables x 1 x2 x3 x4 e1 e2 e3
CB de base
4 x3 0 5 1 0 1 -1 0 97
5 x4 1 -2 0 1 0 1 0 3
0 e3 -2 4 0 0 1 0 1 93
Zj 5 10 4 5 4 1 0 403
Zj-Cj 3 7 0 0 4 1 0

Le tableau est optimal. La solution optimale est : 𝑥3∗ = 97 ; 𝑥4∗ = 3; 𝑒3∗ = 93 𝑒𝑡 𝑧 ∗ = 403

4
 5) Nouvelle contrainte 𝑥1 + 𝑥2 + 𝑥3 ≤ 10.

On a 𝑥1∗ + 𝑥2∗ + 𝑥3∗ = 0 + 0 + 100 > 10. La contrainte n’est pas vérifiée. La solution n’est
plus optimale.

6) Il suffit d’ajouter une contrainte de telle sorte que si on remplace les variables dans cette
contrainte par leurs valeurs optimales on aura une contrainte qui est juste vérifiée. Par
exemple : soit la contrainte 𝑥1 + 3𝑥3 ≤ 300. Ici, 𝑥1∗ = 0; 𝑥3∗ = 100.

𝑥1∗ + 𝑥3∗ = 300. ⟹ 𝑒4∗ = 300 − 𝑥1∗ − 3𝑥3∗ = 0

Exercice 3
1) Ecriture de la forme standard

𝑀𝑖𝑛𝑖𝑚𝑖𝑠𝑒𝑟 𝐶 = 7𝑥1 + 3𝑥2 + 4𝑥3 + 𝑀𝑎1 + 𝑀𝑎2

𝑆𝑜𝑢𝑠 𝑐𝑜𝑛𝑡𝑟𝑎𝑖𝑛𝑡𝑒𝑠 𝑥1 + 𝑥2 − 𝑒1 + 𝑎1 = 10

2𝑥1 + 2𝑥2 + 𝑥3 + 𝑒2 = 40

−2𝑥1 + 𝑥2 − 𝑥3 − 𝑒3 + 𝑎2 = 12

𝑥1 , 𝑥2 , 𝑥3 , 𝑒1 , 𝑒2 , 𝑒3 , 𝑎1 , 𝑎2 ≥ 0

Premier tableau du simplexe

Cj 7 3 4 0 0 0 M M XB
Variables x1 x2 x3 e1 e2 e3 a1 a2
CB de base
M a1 1 1 0 -1 0 0 1 0 10 V.S
0 e2 2 2 1 0 1 0 0 0 40
M a2 -2 1 -1 0 0 -1 0 1 12
Zj -M 2M -M -M 0 -M M M 22M
Zj-Cj -M-7 2M-3 -M-4 -M 0 -M 0 0
V.E

5
Première itération

Cj 7 3 4 0 0 0 M M XB
Variables x1 x2 x3 e1 e2 e3 a1 a2
de base
3 x2 1 1 0 -1 0 0 1 0 10
0 e2 0 0 1 2 1 0 -2 0 20
M a2 -3 0 -1 1 0 -1 -1 1 2 V.S
Zj -3M+3 3 -M -3+M 0 -M 3-M M 30+2M
Zj-Cj -3M-4 0 -M-4 -3+M 0 -M 3-2M 0
V.E

Deuxième itération

Cj 7 3 4 0 0 0 M M XB
Variables x1 x2 x3 e1 e2 e3 a1 a2
de base
3 x2 -2 1 -1 0 0 -1 0 1 12 S2
0 e2 6 0 3 0 1 2 0 -2 16 Y2
0 e1 -3 0 -1 1 0 -1 -1 1 2 Y1
Zj -6 3 -3 0 0 -3 0 3 36
Zj-Cj -13 0 -7 0 0 -3 -M 3-M

S1=13 S2=0 S3=7 Y1=0 Y2=0 Y3=3

Tous les (𝑍𝑗 − 𝐶𝑗 ) sont ≤ 0, l’optimum est atteint. La solution optimale est donnée par :

(𝑥1∗ = 0, 𝑥2∗ = 12, 𝑥3∗ = 0, 𝑒1∗ = 2, 𝑒2∗ = 16, 𝑒3∗ = 0) 𝑒𝑡 𝐶 ∗ = 36

2) La matrice de base inverse 𝐵−1 est formée par les colonnes des variables {𝑎1 , 𝑒2 , 𝑎2 }
du tableau optimal.

0 0 1
−1
𝐵 = (0 1 −2)
−1 0 1
10
3) Soit 𝑏3′ = 12 + 𝜆 ; 𝑏′ = ( 40 )
12 + 𝜆
0 0 1 10 12 + 𝜆
−1 ′
𝐵 𝑏 = (0 1 −2) ( 40 ) = (16 − 2𝜆)
−1 0 1 12 + 𝜆 2+𝜆
12 + 𝜆 ≥ 0 𝜆 ≥ −12
−1 ′
𝐵 𝑏 ≥ 0 ⇔ {16 − 2𝜆 ≥ 0 ⇔ { 𝜆 ≤8
2+𝜆 ≥0 𝜆 ≥ −2

6
Donc −2 ≤ 𝜆 ≤ 8 𝑒𝑡 10 ≤ 𝑏3 ≤ 20

Tant que 𝑏3 ∈ ⟦10 , 20⟧ et que toute chose égale par ailleurs, la solution reste optimale.

4) Ecriture du DUAL

𝑀𝑎𝑥𝑖𝑚𝑖𝑠𝑒𝑟 𝑍 = 10𝑦1 − 40 𝑦2 + 12𝑦3

𝑆𝑜𝑢𝑠 𝑐𝑜𝑛𝑡𝑟𝑎𝑖𝑛𝑡𝑒𝑠 𝑦1 − 2𝑦2 − 2𝑦3 ≤ 7

𝑦1 − 2𝑦2 + 𝑦3 ≤3

−𝑦2 − 𝑦3 ≤4

𝑦1 , 𝑦2 , 𝑦3 ≥0

Tableau optimal DUAL

Cj 10 -40 12 0 0 0 XB
Variables y1 y2 y3 s1 s2 s3
de base
y3 1 -2 1 0 1 0 3
s1 3 -6 0 1 2 0 13
s3 1 -3 0 0 1 1 7
Zj 12 -24 12 0 12 0 36
Zj-Cj 2 16 0 0 12 0

5) Vérifions les relations d’exclusions

𝑥1∗ × 𝑠1∗ = 0 × 13 = 0

𝑥2∗ × 𝑠2∗ = 12 × 0 = 0

𝑥3∗ × 𝑠3∗ = 0 × 7 = 0

𝑦1∗ × 𝑒1∗ = 0 × 2 = 0

𝑦2∗ × 𝑒2∗ = 0 × 16 = 0

𝑦3∗ × 𝑒3∗ = 3 × 0 = 0

6) Introduction d’un nouveau produit 𝑃4

La contrainte duale correspondante s’écrit : 2𝑦1∗ + 𝑦2∗ + 𝑦3∗ = 3 ≤ 2 FAUX. La contrainte

n’est pas vérifiée, il est profitable d’introduire cette variable (donc produire 𝑃4 )

2 1
−1 (1) = (−1)
𝐵
1 −1
7
 Cj 7 3 4 2 0 0 0 XB
Variables x1 x2 x3 x4 e1 e2 e3
de base
3 x2 -2 1 -1 1 0 0 -1 12 V.S
0 e2 6 0 3 -1 0 1 2 6
0 e1 -3 0 -1 -1 1 0 -1 2
Zj -6 3 -3 3 0 0 -3
Zj-Cj -13 0 -7 1 0 0 -3
V.E

Cj 7 3 4 2 0 0 0 XB
Variables x1 x2 x3 x4 e1 e2 e3
de base
2 x4 -2 1 -1 1 0 0 -1 12
0 e2 4 1 2 0 0 1 1 28
0 e1 -5 1 -2 0 1 0 -2 14
Zj -4 2 -2 2 0 0 -2 24
Zj-Cj -11 -1 -2 0 0 0 -2

La nouvelle solution optimale est donnée par :

(𝑥1∗ = 𝑥2∗ = 𝑥3∗ = 0, 𝑥4∗ = 12 , 𝑒1∗ = 14 , 𝑒2∗ = 28 , 𝑒3∗ = 0) 𝑒𝑡 𝐶 ∗ = 24

7) Introduction d’une nouvelle contrainte

On a 𝑥1∗ + 𝑥2∗ + 𝑥3∗ = 0 + 12 + 0 = 12 > 10 → la solution optimale initiale va changer vu

que la nouvelle contrainte n’est pas respectée.

Exercice 4
1) la matrice de base inverse 𝐵−1 du tableau est formée par les colonnes des variables
d’écart {𝑒1 , 𝑒2 } du tableau optimal. donc
3/7 −1/7
𝐵−1 = ( )
1/7 2/7

2)

8
 Cj 2 3 6 0 0
Variables x1 x2 x3 e1 e2 XB
CB de base
x2 2/7 1 0 3/7 -1/7 24/7 S2
x3 3/7 0 1 1/7 2/7 22/7 S3
Zj 24/7 3 6 15/7 9/7 204/7
Zj-Cj 10/7 0 0 15/7 9/7

S1=10/7 S2=0 S3=0 U1=15/7 U2=9/7

Le vecteur 𝑋𝐵 est donné par :
10 3/7 −1/7 10 24/7
𝑋𝐵 = 𝐵−1 ( ) = ( )( ) = ( )
6 1/7 2/7 6 22/7
La solution optimale est donnée par :
24 22
𝑥1∗ = 0, 𝑥2∗ = 7
, 𝑥3∗ = 7
, 𝑒1∗ = 𝑒2∗ = 0 et 𝑍 ∗ = 204/7

3) Formulation du P.L
Pour revenir au tableau initial, on détermine 𝐵. Remarquons que 𝐵 × 𝐵−1 = 𝐼 correspond
à la matrice des variables d’écart {𝑒1 , 𝑒2 } du tableau initial.

2 1
𝐵= ( )
−1 3
On a 𝐵 × tableau optimal =

2 3 1 24
2 1 1 0 −7 1 2 1 1 0 10
( ) × (73 7
1 2
7
22) =( )
−1 3 0 1 1 −1 3 0 1 6
7 7 7 7

Le programme linéaire s’écrit :

𝑀𝑎𝑥𝑖𝑚𝑖𝑠𝑒𝑟 𝑍 = 2𝑥1 + 3𝑥2 + 6𝑥3

𝑆𝑜𝑢𝑠 𝑐𝑜𝑛𝑡𝑟𝑎𝑖𝑛𝑡𝑒𝑠 𝑥1 + 2𝑥2 + 𝑥3 ≤ 10

𝑥1 − 𝑥2 + 3𝑥3 ≤ 6

𝑥1 , 𝑥2 , 𝑥3 ≥0

4) Le programme dual s’écrit :

a) 𝑀𝑖𝑛𝑖𝑚𝑖𝑠𝑒𝑟 𝑊 = 10𝑈1 + 6 𝑈2
𝑠𝑜𝑢𝑠 𝑐𝑜𝑛𝑡𝑟𝑎𝑖𝑛𝑡𝑒𝑠 𝑈1 + 𝑈2 ≥ 2

2𝑈1 − 𝑈2 ≥3

9
 𝑈1 + 3𝑈2 ≥ 6

𝑈1 , 𝑈2 ≥0

Dressons le tableau optimal Dual :

Cj 10 6 0 0 0
Variables u1 u2 s1 s2 s3 XB
CB de base
0 s1 0 0 1 -2/7 -3/7 10/7
10 u1 1 0 0 -3/7 -1/7 15/7
6 u2 0 1 0 1/7 -2/7 9/7
Zj 10 6 0 -24/7 -22/7 204/7
Zj-Cj 0 0 0 -24/7 -22/7

b) La solution optimale du dual est :

15 9 10 204
𝑈1∗ = , 𝑈2∗ = 7 , 𝑆1∗ = , 𝑆2∗ = 𝑆3∗ = 0 et 𝑊 ∗ = = 𝑍∗
7 7 7

c) vérifions les relations d’exclusions

10
𝑥1∗ × 𝑠1∗ = 0 × =0
7

24
𝑥2∗ × 𝑠2∗ = ×0 = 0
7

22
𝑥3∗ × 𝑠3∗ = ×0 = 0
7

15
𝑢1∗ × 𝑒1∗ = ×0 =0
7

9
𝑢2∗ × 𝑒2∗ = 7 × 0 = 0

10