Solutions
558
s
d
x 2
x 1
x 2
x 3
x 4
x 5
x 3
x 5
10
1
11
0
0
0
2
2/11
0
1/10 *
i / ie
1
3
0
0
Z 23
1
0
0
e
70
c
1
10
0
0
9
62
34
38
En fai sant entrer x 4 en base (d’après le 1
er
cri tère de Dantzig), x 3 sort de la base. La nou -
velle base ainsi obte nue est opti male :
x 2
x 1
x 2
x 3
x 4
x 5
x 4
x 5
0,1
1,1
1
7
0,9
0,2
1
0
0,1
0
0
0,9
0,1
6,8
Z 30
0
1
1
0
3,8
0
0
0
0
La solu tion opti male est :
x 1 5 0 , x 2 5 0,9 , x 3 5 0 , x 4 5 0,1 , x 5 5 6,8 et Ζ 5 30.
8.9 1) La solu tion opti male de PL 2 est x
*
2 5 100 , x
*
1 5 0 , Z
*
2 5 100. Elle est obte nue
après 3 ité ra tions (si l’on applique le pre mier cri tère de Dantzig pour déter mi ner la variable
entrante). Celle de PL 3 est x
*
3 5 100
2
, x
*
1 5 x
*
2 5 0 et Z
*
3 5 10 000 , obte nue après 7 ité ra -
tions.
2) La solu tion opti male de PL n est x
*
n 5 100
n21
; x
*
1 5 x
*
2 5 c 5 x
*
n21 5 0 , obte nue après
2
n 21 ité ra tions, avec Z
*
n 5 100
n21
.
3) En fai sant entrer en base ini tia le ment x n , c’est àdire la variable qui a le coef fi cient D j
le plus PETIT posi tif (contrai re ment au 1
er
cri tère de Dantzig qui fait choi sir le D j le plus
GRAND posi tif), on obtient l’opti mum... en une seule ité ra tion !
En effet la base opti male est for mée des variables x 1 , x 2 , c , x n21 et de x n .
L’expres sion de x n en fonc tion des variables hors base est :
x n 5 100
n21 2 a2 #
a
n21
j51
10
n2j # x j b 2 x n
Expri mons alors Z 5 a
n21
j51
10
n2j # x j 1 x n , en fonc tion des variables hors base : x 1 , x 2 , c ,
x n21 et x n .
Il vient : Z 5 2 a
n21
j51
10
n2j # x j 2 x n 1 100
n21
Ainsi D j 5 210
n2j
pour j 5 1, 2, c , n 2 1 et Dj 5 21 pour j 5 n.
Les D j des variables hors base étant néga tifs, on est bien à l’opti mum de PL n .
558
s
d
x 2
x 1
x 2
x 3
x 4
x 5
x 3
x 5
10
1
11
0
0
0
2
2/11
0
1/10 *
i / ie
1
3
0
0
Z 23
1
0
0
e
70
c
1
10
0
0
9
62
34
38
En fai sant entrer x 4 en base (d’après le 1
er
cri tère de Dantzig), x 3 sort de la base. La nou -
velle base ainsi obte nue est opti male :
x 2
x 1
x 2
x 3
x 4
x 5
x 4
x 5
0,1
1,1
1
7
0,9
0,2
1
0
0,1
0
0
0,9
0,1
6,8
Z 30
0
1
1
0
3,8
0
0
0
0
La solu tion opti male est :
x 1 5 0 , x 2 5 0,9 , x 3 5 0 , x 4 5 0,1 , x 5 5 6,8 et Ζ 5 30.
8.9 1) La solu tion opti male de PL 2 est x
*
2 5 100 , x
*
1 5 0 , Z
*
2 5 100. Elle est obte nue
après 3 ité ra tions (si l’on applique le pre mier cri tère de Dantzig pour déter mi ner la variable
entrante). Celle de PL 3 est x
*
3 5 100
2
, x
*
1 5 x
*
2 5 0 et Z
*
3 5 10 000 , obte nue après 7 ité ra -
tions.
2) La solu tion opti male de PL n est x
*
n 5 100
n21
; x
*
1 5 x
*
2 5 c 5 x
*
n21 5 0 , obte nue après
2
n 21 ité ra tions, avec Z
*
n 5 100
n21
.
3) En fai sant entrer en base ini tia le ment x n , c’est àdire la variable qui a le coef fi cient D j
le plus PETIT posi tif (contrai re ment au 1
er
cri tère de Dantzig qui fait choi sir le D j le plus
GRAND posi tif), on obtient l’opti mum... en une seule ité ra tion !
En effet la base opti male est for mée des variables x 1 , x 2 , c , x n21 et de x n .
L’expres sion de x n en fonc tion des variables hors base est :
x n 5 100
n21 2 a2 #
a
n21
j51
10
n2j # x j b 2 x n
Expri mons alors Z 5 a
n21
j51
10
n2j # x j 1 x n , en fonc tion des variables hors base : x 1 , x 2 , c ,
x n21 et x n .
Il vient : Z 5 2 a
n21
j51
10
n2j # x j 2 x n 1 100
n21
Ainsi D j 5 210
n2j
pour j 5 1, 2, c , n 2 1 et Dj 5 21 pour j 5 n.
Les D j des variables hors base étant néga tifs, on est bien à l’opti mum de PL n .