319
© Dunod – Toute reproduction non autorisée est un délit.
8.2 Algo rithme du sim plexe : méthode algé brique…
j
(1) (2) (3) (4)
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
12
2
4
3 3
3
3
3
3
z
i
j
c i
1
1
1
1
1
1
1
1
1
1
11 500
1 500
750
500
250
1
2
2
2
2
2
6
3
3
3
5
7
4
4
4
4
L’opti mum est atteint, puisque tous les D j rela tifs aux variables hors base, sont néga
tifs. Nous sommes évi dem ment par ve nus à la même solu tion que nous avions trou vée
plus haut par d’autres voies : x 1 5 250, x 2 5 500, x 3 5 1500, z 5 11 500 euros.
En se repor tant à l’annexe, qui contient les cal culs inter mé diaires, le lec teur consta
tera que, par tant du som met O, l’ori gine des axes (x 1 5 x 2 5 x 3 5 0, z 5 0), nous
sommes suc ces si ve ment passés, dans l’espace à trois dimen sions, par :
le sommet C (x 1 5 x 3 5 0, x 2 5 500, z 5 6 000),
puis le sommet B (x 1 5 1 000, x 2 5 500, x 3 5 0, z 5 10 000)
puis le sommet R (x 1 5 1 000, x 2 5 500, x 3 5 375, z 5 11 125),
enfin au sommet Q (x 1 5 1 000, x 2 5 500, x 3 5 1 500, z 5 11 500).
Mais il va sans dire que nous n’avons pu mener ce pro blème à bien, par des cal culs
manuels, que parce que le nombre de variables est très petit. Lorsque le nombre de
variables dépasse la dizaine, il ne peut être ques tion de cal cu ler à la main ; l’algo
rithme s’implé mente informatiquement et il est capable de résoudre des pro grammes
linéaires com por tant des cen taines de milliers de variables et des dizaines de milliers
de contraintes
(1)
. Le cas échéant, on fait appel à des méthodes de décom po si tion,
lorsque le pro blème est de grande taille.
Ces résul tats témoignent de la puis sance de l’outil d’explo ra tion du com bi na toire
consti tué par la pro gram ma tion linéaire et l’algo rithme du sim plexe.
8.2.3 Annexe : détails des ité ra tions
Ayant donné le détail de la pra tique de la pre mière ité ra tion, nous don nons pour les
ité ra tions sui vantes le résul tat du cal cul (à chaque ité ra tion le coef fi cient pivot est
mar qué par un asté risque), à suivre crayon en main.
1. Voire même au delà, pour des pro grammes linéaires dont les don nées ont des struc tures par
ti cu lières
(1)
© Dunod – Toute reproduction non autorisée est un délit.
8.2 Algo rithme du sim plexe : méthode algé brique…
j
(1) (2) (3) (4)
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
12
2
4
3 3
3
3
3
3
z
i
j
c i
1
1
1
1
1
1
1
1
1
1
11 500
1 500
750
500
250
1
2
2
2
2
2
6
3
3
3
5
7
4
4
4
4
L’opti mum est atteint, puisque tous les D j rela tifs aux variables hors base, sont néga
tifs. Nous sommes évi dem ment par ve nus à la même solu tion que nous avions trou vée
plus haut par d’autres voies : x 1 5 250, x 2 5 500, x 3 5 1500, z 5 11 500 euros.
En se repor tant à l’annexe, qui contient les cal culs inter mé diaires, le lec teur consta
tera que, par tant du som met O, l’ori gine des axes (x 1 5 x 2 5 x 3 5 0, z 5 0), nous
sommes suc ces si ve ment passés, dans l’espace à trois dimen sions, par :
le sommet C (x 1 5 x 3 5 0, x 2 5 500, z 5 6 000),
puis le sommet B (x 1 5 1 000, x 2 5 500, x 3 5 0, z 5 10 000)
puis le sommet R (x 1 5 1 000, x 2 5 500, x 3 5 375, z 5 11 125),
enfin au sommet Q (x 1 5 1 000, x 2 5 500, x 3 5 1 500, z 5 11 500).
Mais il va sans dire que nous n’avons pu mener ce pro blème à bien, par des cal culs
manuels, que parce que le nombre de variables est très petit. Lorsque le nombre de
variables dépasse la dizaine, il ne peut être ques tion de cal cu ler à la main ; l’algo
rithme s’implé mente informatiquement et il est capable de résoudre des pro grammes
linéaires com por tant des cen taines de milliers de variables et des dizaines de milliers
de contraintes
(1)
. Le cas échéant, on fait appel à des méthodes de décom po si tion,
lorsque le pro blème est de grande taille.
Ces résul tats témoignent de la puis sance de l’outil d’explo ra tion du com bi na toire
consti tué par la pro gram ma tion linéaire et l’algo rithme du sim plexe.
8.2.3 Annexe : détails des ité ra tions
Ayant donné le détail de la pra tique de la pre mière ité ra tion, nous don nons pour les
ité ra tions sui vantes le résul tat du cal cul (à chaque ité ra tion le coef fi cient pivot est
mar qué par un asté risque), à suivre crayon en main.
1. Voire même au delà, pour des pro grammes linéaires dont les don nées ont des struc tures par
ti cu lières
(1)