Ezzeddine DELHOUMI

Institut des Hautes Etudes Commerciales. Carthage

Filières : Licence de Finance
Matière : Recherche Opérationnelle 2H
Enseignants : Delhoumi E. & Siala J.

Examen rattrapage, Juin 2016

Exercice 1 : (3 points)

On souhaite investir une somme entre 1 et 4 millions de dinars. Trois choix sont possibles,
dont les rapports annuels sont les suivants :

Immobilier: 1%, actions: 14% et obligations : 6%.

Ces taux étant supposés rester constants dans un futur proche, on cherche à déterminer la
politique d’investissement assurant le rendement global maximal, tout en respectant les règles
suivantes, issues d’une analyse des risques du marché :

- L’investissement immobilier ne doit pas excéder 2 millions de dinars.

- L’investissement en obligations ne doit pas excéder 3 million de dinars.
- L’investissement en actions ne doit pas excéder 2 millions de dinars diminués du tiers
(1/3) de l’investissement en obligations.

Formuler un programme linéaire (sans le résoudre) qui assure cette politique

d’investissement.

Exercice 2: (4.5 points)

Soit le programme linéaire suivant :

𝑀𝑎𝑥 𝑍 = 3𝑥1 + 𝑥2
𝑠/𝑐
3 𝑥1 + 2𝑥2 ≤ 12
(𝑃𝐿 )
4𝑥1 − 𝑥2 ≥ 4
𝑥1 − 2𝑥2 ≤ 0
{ 𝑥1 , 𝑥2 ≥ 0

1) Résoudre graphiquement le PL. (2 points)

2) Ecrire le dual de ce PL. (1 point)
3) Trouver le dernier tableau de dual en se basant sur la solution du PL (en utilisant la
méthode matricielle). (1.5 points)

Exercice 3 : (3 points)

Résoudre par la méthode dual-simplexe le PL suivant :

1
Ezzeddine DELHOUMI

𝑀𝑖𝑛 𝑍 = 2𝑥1 + 3𝑥2

𝑠/𝑐
2𝑥1 + 𝑥2 − 𝑥3 ≥ 4
3𝑥1 − 𝑥2 + 5𝑥3 ≥ 5
{ 𝑥1 , 𝑥2 , 𝑥3 ≥ 0

Exercice 4 : (9.5 points)

On vous donne le programme linéaire suivant :

𝑀𝑎𝑥 𝑍 = 2𝑥1 + 3𝑥2 + 5𝑥3

𝑠/𝑐
𝑥1 + 𝑥2 + 2𝑥3 ≤ 8
𝑥1 − 𝑥2 + 𝑥3 ≤ 4
{ 𝑥1 , 𝑥2 , 𝑥3 ≥ 0

Le dernier tableau du simplexe est :

. . . . .
𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒆𝟏 𝒆𝟐
. 𝒙𝟐 1 1 2 1 0 8
. 𝒆𝟐 2 0 3 1 1 12
𝜹𝒋 . . . . . .

1) Compléter le dernier tableau. (1 point)

2) Ecrire le dual et déduire son dernier tableau à partir de celui du primal. (2 points)
3) Si le coefficient 𝑐3 de 𝑥3 dans Z passe de 5 à 8, donner la nouvelle solution du PL.
(1.5 points)
4) Si le second membre 𝑏2 de la deuxième contrainte passe de 4 à (-8), que devient la
solution optimale trouvée ? (1 point)
5) Si le second membre 𝑏2 de la deuxième contrainte passe de 4 à (-9), la solution
optimale trouvée va-t-elle changer. Si oui peut-on trouver une nouvelle solution ? (1
point)
6) Si on ajoute une nouvelle variable 𝑥4 dont son coefficient dans la fonction 𝑍 , 𝒄𝟒 = 𝟖 et ces
coefficients dans le système des contraintes sont 𝒂𝟏𝟒 = 𝒂𝟐𝟒 = 𝟏 . Est-il profitable que cette
variable soit dans la base ? Si oui donner la nouvelle solution. (1.5 points)
7) Donner la nouvelle solution du programme linéaire si on introduit la nouvelle contrainte
suivante : 𝒙𝟐 ≤ 𝟔 . (1.5 points)

BON COURAGE

2
Ezzeddine DELHOUMI

Correction
Exercice 1 :

Soient :

𝑥1 : Le montant en investissement immobilier.

𝑥2 : Le montant d’investissement en actions.

𝑥3 : Le montant d’investissement en obligations.

L’objectif est la maximisation des rendements.

𝑀𝑎𝑥 𝑍 = 0.01𝑥1 + 0.14𝑥2 + 0.06𝑥3
𝑀𝑎𝑥 𝑍 = 0.01𝑥1 + 0.14𝑥2 + 0.06𝑥3
𝑠/𝑐
𝑠/𝑐
𝑥1 + 𝑥2 + 𝑥3 ≥ 1
1 ≤ 𝑥1 + 𝑥2 + 𝑥3 ≤ 4
𝑥1 + 𝑥2 + 𝑥3 ≤ 4
𝑥1 ≤ 2
⇔ 𝑥1 ≤2
𝑥3 ≤ 3
𝑥3 ≤ 3
1
𝑥2 ≤ 2 − 𝑥3 1
3 𝑥2 + 𝑥3 ≤ 2
{ 𝑥1 , 𝑥2 , 𝑥3 ≥ 0 3
{ 𝑥1 , 𝑥2 , 𝑥3 ≥ 0
Exercice 2 :
𝑀𝑎𝑥 𝑍𝑥 = 3𝑥1 + 𝑥2 𝑀𝑎𝑥 𝑍𝑥 = 3𝑥1 + 𝑥2
𝑠/𝑐 𝑠/𝑐
3 𝑥1 + 2𝑥2 ≤ 12 3 𝑥1 + 2𝑥2 + 𝑒1 = 12
4𝑥1 − 𝑥2 ≥ 4 ⇒ 4𝑥1 − 𝑥2 − 𝑒2 = 4
𝑥1 − 2𝑥2 ≤ 0 𝑥1 − 2𝑥2 + 𝑒3 = 0
𝑥1 , 𝑥2 ≥ 0 𝑥1 , 𝑥2 , 𝑒1 , 𝑒2 , 𝑒3 ≥ 0
𝑓𝑜𝑟𝑚𝑒 𝑐𝑎𝑛𝑜𝑛𝑖𝑞𝑢𝑒 𝑓𝑜𝑟𝑚𝑒 𝑠𝑡𝑎𝑛𝑑𝑎𝑟𝑑

1) Résolution graphique :

La solution optimale est

donnée par e point C de
B
coordonnées :

3 13
𝑥1 = 3 , 𝑥2 = 𝑒𝑡 𝑒2 =
2 2
𝑒1 = 𝑒3 = 0
C
A 𝑍 = 10.5

3
Ezzeddine DELHOUMI

2) Le programme dual est :

𝑀𝑖𝑛 𝑍𝑦 = 12𝑦1 − 4𝑦2 𝑀𝑖𝑛 𝑍𝑦 = 12𝑦1 − 4𝑦2
𝑠/𝑐 𝑠/𝑐
3𝑦1 − 4𝑦2 + 𝑦3 ≥ 3 3𝑦1 − 4𝑦2 + 𝑦3 − 𝑒1′ = 3
2𝑦1 + 𝑦2 − 2𝑦3 ≥ 1 ⇒ 2𝑦1 + 𝑦2 − 2𝑦3 − 𝑒2′ = 1
𝑦1 , 𝑦2 , 𝑦3 ≥ 0 𝑦1 , 𝑦2 , 𝑦3 , 𝑒1′ , 𝑒2′ ≥ 0

{ 𝑓𝑜𝑟𝑚𝑒 𝑐𝑎𝑛𝑜𝑛𝑖𝑞𝑢𝑒 { 𝑓𝑜𝑟𝑚𝑒 𝑠𝑡𝑎𝑛𝑑𝑎𝑟𝑑

3) D’après le théorème des écarts complémentaires on a :
𝑥1∗ . 𝑒′1∗ = 0 ⇒ 𝑒1′ 𝑉𝐻𝐵
𝑥2∗ . 𝑒′∗2 = 0 ⇒ 𝑒2′ 𝑉𝐻𝐵 1 1
3 1 4 8
𝑒2∗ . 𝑦2∗ = 0 ⇒ 𝑦2 𝑉𝐻𝐵 𝐴𝐼 = ( ) ⇔ 𝐴−1𝐼 = (1 3)
∗ ∗ 2 −2 −
𝑒1 . 𝑦1 = 0 ⇒ 𝑦1 𝑉𝐵 4 8
∗ ∗
{ 𝑒3 . 𝑦3 = 0 ⇒ 𝑦3 𝑉𝐵

1 1 7
1 − 0
−1 4 8 3 −4 1 8
𝐴𝐼 𝐴𝑝 = ( )( )=( )
1 3 2 1 −2 11
− 0 − 1
4 8 8
1 1 1 1
− −
𝐴−1 4 8 ) (−1 0 ) = ( 4 8)
𝐼 𝐴𝑒 = (1 3 1 3
0 −1
− −
4 8 4 8
1 1 7
𝑦1 4 8 ) (3) = (8)
(𝑦 ) = 𝐴−1
𝐼 𝐵 = (1
3 3 1 3
−
4 8 8
12 -4 0 0 0
𝒚𝟏 𝒚𝟐 𝒚𝟑 𝒆′𝟏 𝒆′𝟐
12 𝒚𝟏 1 -7/8 0 -1/4 -1/8 7/8
0 𝒚𝟑 0 -11/8 1 -1/4 3/8 3/8
𝜹𝒋 0 13/2 0 3 3/2 Z=10.5
Exercice 3 :

Résolution par le dual-simplexe :

𝑀𝑖𝑛 𝑍 = 2𝑥1 + 3𝑥2 𝑀𝑎𝑥 𝑍 ′ = −2𝑥1 − 3𝑥2 𝑀𝑎𝑥 𝑍 ′ = −2𝑥1 − 3𝑥2 + 0𝑒1 + 0𝑒2
𝑠/𝑐 𝑠/𝑐 𝑠/𝑐
2𝑥1 + 𝑥2 − 𝑥3 ≥ 4 ⇔ −2𝑥1 − 𝑥2 + 𝑥3 ≤ −4 ⇒ −2𝑥1 − 𝑥2 + 𝑥3 + 𝑒1 = −4
3𝑥1 − 𝑥2 + 5𝑥3 ≥ 5 −3𝑥1 + 𝑥2 − 5𝑥3 ≤ −5 −3𝑥1 + 𝑥2 − 5𝑥3 + 𝑒2 = −5
{ 𝑥1 , 𝑥2 , 𝑥3 ≥ 0 { 𝑥1 , 𝑥2 , 𝑥3 ≥ 0 { 𝑥1 , 𝑥2 , 𝑥3 , 𝑒1 , 𝑒2 ≥ 0

4
Ezzeddine DELHOUMI

-2 -3 0 0 0
𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒆𝟏 𝒆𝟐
0 𝒆𝟏 -2 -1 1 1 0 -4
0 𝒆𝟐 -3 1 -5 0 1 -5→
𝜹𝒋 -2 -3 0 0 0 .

-2 -3 0 0 0
𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒆𝟏 𝒆𝟐
0 𝒆𝟏 0 -5/3 13/3 1 -2/3 -2/3→
-2 𝒙𝟏 1 -1/3 5/3 0 -1/3 5/3
𝜹𝒋 0 -11/3 10/3 0 -2/3 .

-2 -3 0 0 0
𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒆𝟏 𝒆𝟐
0 𝒆𝟐 0 5/2 -13/2 -3/2 1 1
0 𝒙𝟏 1 1/2 -1/2 -1/2 0 2
𝜹𝒋 0 -2 -1 -1 0 Z’= -4

𝑥 ∗ = 2, 𝑒2∗ = 1 ∗
La solution optimale est { ∗1 𝑍 ′ = −4 𝑒𝑡 𝑍 ∗ = 4
𝑥2 = 𝑥3∗ = 𝑒1∗ = 0

Exercice 4 :

Soit programme linéaire suivant :

𝑀𝑎𝑥 𝑍 = 2𝑥1 + 3𝑥2 + 5𝑥3

𝑠/𝑐
𝑥1 + 𝑥2 + 2𝑥3 ≤ 8
𝑥1 − 𝑥2 + 𝑥3 ≤ 4
{ 𝑥1 , 𝑥2 , 𝑥3 ≥ 0

1) Le dernier tableau du simplexe est :

2 3 5 0 0
𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒆𝟏 𝒆𝟐
3 𝒙𝟐 1 1 2 1 0 8
0 𝒆𝟐 2 0 3 1 1 12
𝜹𝒋 -1 0 -1 -3 0 Z=24

2) le dual et son dernier tableau :

𝑀𝑖𝑛 𝑍𝑦 = 8 𝑦1 + 4 𝑦2
𝑠/𝑐
𝑦1 + 𝑦2 ≥ 2
𝑦1 − 𝑦2 ≥ 3
2𝑦1 + 𝑦2 ≥ 5
{ 𝑦1 , 𝑦2 , 𝑦3 ≥ 0

5
Ezzeddine DELHOUMI

8 4 0 0 0
𝒚𝟏 𝒚𝟐 𝒆′𝟏 𝒆′𝟐 𝒆′𝟑
8 𝒚𝟏 1 -1 0 -1 0 3
0 𝒆′𝟏 0 -2 1 -1 0 1
0 𝒆′𝟑 0 -3 0 -2 1 1
𝜹𝒋 0 12 0 8 0 Z=24

3) Si le coefficient 𝑐3 passe de 5 à 8, 𝛿𝑥3 passe de -1 à 2. Alors la solution n’est plus

optimale. 𝑥3 entre dans la base et 𝑥2 ou 𝑒2 sort de la base. En effet1,
- Si 𝑥2 sort de la base, la solution est :

2 3 8 0 0
𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒆𝟏 𝒆𝟐
8 𝒙𝟑 1/2 1/2 1 1/2 0 4
0 𝒆𝟐 -1/2 -3/2 0 -1/2 1 0
𝜹𝒋 -2 -1 0 -4 0 Z=32

La solution est dégénérée.

- Si 𝑒2 sort de la base, la solution est :

2 3 8 0 0
𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒆𝟏 𝒆𝟐
3 𝒙𝟐 1/3 1 0 1/3 -2/3 0
8 𝒙𝟑 2/3 0 1 1/3 1/3 4
𝜹𝒋 -7/3 0 0 -11/3 -2/3 Z=32

La solution est dégénérée.

4) Si le second membre 𝑏2 de la deuxième contrainte passe de 4 à (-8).

𝑥2 1 0 8 8 0
( 𝑒 ) = 𝐴−1 ′
𝐼 𝐵 =( )( ) = ( ) ≥ ( )
2 1 1 −8 0 0
La solution reste optimale mais elle devient dégénérée.

5) Si le second membre 𝑏2 de la deuxième contrainte passe de 4 à (-9).

𝑥2 1 0 8 8
( 𝑒 ) = 𝐴−1 ′
𝐼 𝐵 =( ) ( ) = ( ) , 𝑒2 < 0, alors la solution n’est plus
2 1 1 −9 −1
réalisable. Pour trouver une nouvelle solution nous devrons appliquer le dual-simplexe
en faisant sortant de la base 𝑒2 . Mais on ne peut pas déterminer la variable entrante car

1
Dans cette question j’ai présenté les deux cas, mais l’étudiant est demandé de présenter l’un des deux cas.

6
Ezzeddine DELHOUMI

tous les éléments de la ligne de la variable 𝑒2 dans le tableau de simplexe sont positifs
ou nuls. Alors la solution devient non bornée (pas de solution).
6) Si on ajoute une nouvelle variable 𝑥4 dont son coefficient dans la fonction 𝑍 , 𝒄𝟒 = 𝟖 et ces
coefficients dans le système des contraintes sont 𝒂𝟏𝟒 = 𝒂𝟐𝟒 = 𝟏 .
La contrainte duale correspondante à cette variable est 𝑦1 + 𝑦2 ≥ 8.
Or 𝑦1∗ + 𝑦2∗ = 3 + 0 = 3 < 8. La contrainte n’est pas vérifiée. La solution n’est plus
optimale. Cherchons la nouvelle solution.
𝑎14 1 0 1 1
𝐴−1
𝐼 (𝑎 ) = ( )( ) = ( )
24 1 1 1 2
2 3 5 8 0 0
𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒙𝟒 𝒆𝟏 𝒆𝟐
3 𝒙𝟐 1 1 2 1 1 0 8
0 𝒆𝟐 2 0 3 2 1 1 12→
𝜹𝒋 -1 0 -1 5 -3 0 Z=24

2 3 5 8 0 0
𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒙𝟒 𝒆𝟏 𝒆𝟐
3 𝒙𝟐 0 1 1/2 0 1/2 -1/2 2
8 𝒙𝟒 1 0 3/2 1 1/2 1/2 6
𝜹𝒋 -6 0 -17/2 0 -11/2 -5/2 Z=54
7) Si on introduit une nouvelle contrainte : 𝒙𝟐 ≤ 𝟔 .
𝑥2∗ = 8 > 6. La contrainte n’est pas vérifiée. Alors la solution optimale va changer. En
effet,

2 3 5 0 0 0
𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒆𝟏 𝒆𝟐 𝒆𝟑
3 𝒙𝟐 1 1 2 1 0 0 8
0 𝒆𝟐 2 0 3 1 1 0 12
0 𝒆𝟑 0 1 0 0 0 1 6
𝜹𝒋 -1 0 -1 -3 0 0 Z=24

2 3 5 0 0 0
𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒆𝟏 𝒆𝟐 𝒆𝟑
3 𝒙𝟐 1 1 2 1 0 0 8
0 𝒆𝟐 2 0 3 1 1 0 12
0 𝒆𝟑 -1 0 -2 -1 0 1 -2→
𝜹𝒋 -1 0 -1 -3 0 0 Z=24

2 3 5 0 0 0
𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒆𝟏 𝒆𝟐 𝒆𝟑
3 𝒙𝟐 0 1 0 0 0 1 6
0 𝒆𝟐 1/2 0 0 -1/2 1 3/2 9
5 𝒙𝟑 1/2 0 1 1/2 0 -1/2 1
𝜹𝒋 -1/2 0 0 -5/2 0 -1/2 Z=23

7
Ezzeddine DELHOUMI