Chapitre 8 • La pro gram ma tion linéaire
334
La base pro po sée n’est pas opti male ; en fai sant entrer x 4 en base on obtient l’opti mum
en une seule ité ra tion : z
* 5 30 et x 1 5 0, x 2 5 0,9, x 3 5 0, x 4 5 0,1 et x 5 5 6,8.
8.5.3 Cas d’une base « évi dente » : B 5 I
Soit le pro gramme linéaire :
e
y 1
1 3y 4 2 y 1
5
4
y 2
1 6y 4
2 y 2
5 12
y 3
1 2y 4
2 y 3 5
3
y 1
,
y 2
,
y 3
,
y 4
, y 1 , y 2 , y 3 >
0
2 31 000y 1 1 500y 2 1 1 500y 3 1 750y 4 4
5 z 3max4
Les variables d’écart y 1 , y 2 et y 3 forment certes une base de matrice Br 5 2I ; mais
cette base n’est pas admis sible. En effet si l’on annule les variables hors base : y 1 ,
y 2 , y 3 , et y 4 , il vient : y 1 5 24, y 2 5 212, y 3 5 23, ce qui viole les contraintes de
non négativité des variables (les contraintes dites « impli cites »).
En revanche, les variables y 1 , y 2 et y 3 forment une base « évi dente », c’est àdire de
matrice B 5 I . Après avoir exprimé z en fonc tion des variables hors base :
z 5 214 500 1 2 250y 4 2 1 000y 1 2 500y 2 2 1 500y 3 , l’opti mum s’obtient alors en
une ité ra tion (cf 8.7.4 pour le détail des calculs).
Le pro gramme ci dessus est en fait le « dual » du pro gramme linéaire asso cié à notre
exemple de l’ate lier ; il sera traité in extenso dans un para graphe 8.7 consa cré à la
notion de dua lité.
Il arrive que l’on puisse se rame ner au cas d’une base évi dente. Aussi pour le PL
ci dessous (issu d’un pro blème d’opti mi sation de découpes) :
d
3y 1 1 y 2
>
36
y 2 1 2y 3 >
24
y 1
,
y 2
,
y 3 >
0
16y 1 1 27y 2 1 10y 3 5 z 3min4
il suf fit de divi ser la pre mière contrainte par 3 et la seconde par 2 pour avoir une base
B 5 I, asso ciée aux variables y 1 et y 3 :
d
y 1
1 1/3y 2
2 y 1
5
12
1/2y 2 1 y 3
2 y 2 5
12
y 1
,
y 2
,
y 3
, y 1 , y 2 >
0
216y 1 2 27y 2 2 10y 3
5 zr 3max4
l’expres sion de z r(5 2z ) en fonc tion des variables hors base four nit :
z r 5 216 # (12 2 1/3y 2 1 y 1 ) 2 27y 2 2 10 # (12 2 1/2y 2 1 y 2 ),
soit:
z r 5 2312 2 50/3y 2 2 16y 1 2 10y 2 .
Ainsi, ici, la base « évi dente » se révèle être l’opti mum... trouvé en 0 ité ra tion !
334
La base pro po sée n’est pas opti male ; en fai sant entrer x 4 en base on obtient l’opti mum
en une seule ité ra tion : z
* 5 30 et x 1 5 0, x 2 5 0,9, x 3 5 0, x 4 5 0,1 et x 5 5 6,8.
8.5.3 Cas d’une base « évi dente » : B 5 I
Soit le pro gramme linéaire :
e
y 1
1 3y 4 2 y 1
5
4
y 2
1 6y 4
2 y 2
5 12
y 3
1 2y 4
2 y 3 5
3
y 1
,
y 2
,
y 3
,
y 4
, y 1 , y 2 , y 3 >
0
2 31 000y 1 1 500y 2 1 1 500y 3 1 750y 4 4
5 z 3max4
Les variables d’écart y 1 , y 2 et y 3 forment certes une base de matrice Br 5 2I ; mais
cette base n’est pas admis sible. En effet si l’on annule les variables hors base : y 1 ,
y 2 , y 3 , et y 4 , il vient : y 1 5 24, y 2 5 212, y 3 5 23, ce qui viole les contraintes de
non négativité des variables (les contraintes dites « impli cites »).
En revanche, les variables y 1 , y 2 et y 3 forment une base « évi dente », c’est àdire de
matrice B 5 I . Après avoir exprimé z en fonc tion des variables hors base :
z 5 214 500 1 2 250y 4 2 1 000y 1 2 500y 2 2 1 500y 3 , l’opti mum s’obtient alors en
une ité ra tion (cf 8.7.4 pour le détail des calculs).
Le pro gramme ci dessus est en fait le « dual » du pro gramme linéaire asso cié à notre
exemple de l’ate lier ; il sera traité in extenso dans un para graphe 8.7 consa cré à la
notion de dua lité.
Il arrive que l’on puisse se rame ner au cas d’une base évi dente. Aussi pour le PL
ci dessous (issu d’un pro blème d’opti mi sation de découpes) :
d
3y 1 1 y 2
>
36
y 2 1 2y 3 >
24
y 1
,
y 2
,
y 3 >
0
16y 1 1 27y 2 1 10y 3 5 z 3min4
il suf fit de divi ser la pre mière contrainte par 3 et la seconde par 2 pour avoir une base
B 5 I, asso ciée aux variables y 1 et y 3 :
d
y 1
1 1/3y 2
2 y 1
5
12
1/2y 2 1 y 3
2 y 2 5
12
y 1
,
y 2
,
y 3
, y 1 , y 2 >
0
216y 1 2 27y 2 2 10y 3
5 zr 3max4
l’expres sion de z r(5 2z ) en fonc tion des variables hors base four nit :
z r 5 216 # (12 2 1/3y 2 1 y 1 ) 2 27y 2 2 10 # (12 2 1/2y 2 1 y 2 ),
soit:
z r 5 2312 2 50/3y 2 2 16y 1 2 10y 2 .
Ainsi, ici, la base « évi dente » se révèle être l’opti mum... trouvé en 0 ité ra tion !