Chapitre 8 • La programmation linéaire
366
3. Don ner l’expres sion de la fonc tion éco no mique, z, en fonc tion des
variables hors base ; est­ on à l’opti mum du P.L. ?
4. Dres ser le tableau du sim plexe cor res pon dant à cette solu tion de base ;
au besoin ité rer l’algo rithme du sim plexe pour obte nir l’opti mum, que l’on
don nera en détail.
**8.9 Pro blème de Klee et Minty (1972)
Il s’agit ici d’un cas extrême, pour lequel le 1
er
cri tère de Dantzig conduit à un
nombre très grand d’ité ra tions (énu mé ra tif) (c’est pourquoi on peut lui substituer le
critère de Bland, par exemple).
Soit les pro grammes linéaires ci- dessous :
PL 2 d
x 1
<
1
20x 1
1
x 2
<
100
x 1
,
x 2
>
0
10x 1
1
x 2
5 z 3max 4
PL 3 e
x 1
<
100
0
20x 1
1
x 2
<
100
1
200x 1
1
20x 2
1
x 3
<
100
2
x 1
,
x 2
,
x 3
>
0
100x 1
1
10x 2
1
x 3
5
z 3max4
PL n f
x 1
< 100
0 5 1
a2 a
i 2 1
j51
10
i 2 j # x j b 1 x i <
100
i 2 1
(i 5 2, 3, c , n)
x j
>
0
(j 5 1, 2, c , n)
a
n
j51
10
n2j # x j
5
z
1. Résoudre PL 2 , puis PL 3 à l’aide de l’algo rithme du sim plexe (en uti ­
li sant le pre mier cri tère « gour mand » de Dantzig). Com bien d’ité ra tions
sont alors néces saires pour résoudre PL 2 ? PL 3 ?
2. Mon trer qu’il fau drait 2
n
– 1 ité ra tions pour résoudre ainsi PL n ... : la
« gour man dise » est punie !
3. On modi fie la règle de choix de la variable entrante, pour faire entrer en
base la variable (hors­ base) entraî nant la plus forte aug men ta tion de la fonc ­
tion éco no mique. Mon trer alors que PL n se résout en... une seule ité ra tion !
NB : le lec teur trou vera plu sieurs exemples et exer cices de pro gram ma tion
linéaire­en­variables­0-1­(boléennes)­ou­en­variables­entières­à­la­fin­du­cha­ ­ pitre­1.