Chapitre 8 • La programmation linéaire
342
Pour les pro grammes linéaires de plus grande taille, on uti lise plu tôt la variante
PFI (forme pro duit de l’inverse), où B
21
est uti li sée, mais impli ci te ment.
L’avan tage de la méthode révi sée (par rap port à la ver sion ini tiale de l’algo rithme
du sim plexe, par exemple implé men tée par la méthode des tableaux) est double :
– Une réduc tion de la masse des cal culs : lors de chaque ité ra tion on expli cite une
seule colonne hors- base : y
e
, la colonne entrante, au lieu des n 2 m colonnes hors
base dans la ver sion ini tiale de l’algo rithme du sim plexe.
–Desgainsdepré ci sionsontobte nus;enarith mé tiqueflot tanteleserreursdetron -
ca turesecumulent,cequipeutame ner,aufildesité ra tions,àdescal culsimpré cis,voire même faux. Ainsi lorsque l’on connaît l’ensemble des variables de base, on
peut recal cu ler B
21
direc te ment à par tir des don nées ini tiales (donc non enta chées
d’erreursaufildesité ra tions).Onrecal culeainsiB
21
(« ré inver sion ») en pra tique,
toutes les 15 à 20 ité ra tions envi ron. L’ana lyse numé rique nous four nit, ici aussi, des
méthodeseffi cacesetpré cisespourrecal cu lerB
21
.
La méthode révi sée du sim plexe est celle qui est implé men tée dans les logi ciels uti -
li sant l’algo rithme du sim plexe.
Il existe d’autres méthodes pour résoudre les pro grammes linéaires (déve lop pées
effi ca ce ment à par tir de 1985): les méthodes dites « inté rieures », dont l’exposé
sort du cadre de cet ouvrage (elles relèvent des tech niques de la pro gram ma tion non
linéaire). Leur com plexité (dans le pire des cas) est poly no miale, ce qui n’est pas le
cas de l’algo rithme du sim plexe. À l’heure actuelle aucune de ces deux approches ne
sur classe en pra tique l’autre ; d’ailleurs cer tains logi ciels très per for mants les implé -
mentent toutes deux et, lors de la réso lu tion d’un pro blème, toutes les deux sont
exé cu tées indé pen dam ment, en paral lèle : il s’opère ainsi une « course » (dont le
« gagnant » varie selon les ins tances trai tées).
8.7 dua lité
8.7.1 Défi ni tion du dual
Une des remarques les plus fruc tueuses que l’on peut faire à pro pos de la pro gram -
ma tion linéaire, est qu’à chaque pro gramme linéaire on peut asso cier, par la règle
donnée ci- dessous, un autre pro gramme linéaire, nommé « pro gramme dual ». Le
pre mier pro gramme linéaire est alors appelé « pro gramme primal ». Leurs prop rié -
tés, nous le verrons, sont étroi te ment liées.
Repre nons l’exemple pré cé dent :
f
x 1
<
1 000
x 2
<
500
x 3 <
1 500
3x 1
+
6x 2
+
2x 3 <
6 750
x 1
,
x 2
,
x 3 >
0
4x 1
+
12x 2
+
3x 3
=
z [max]
342
Pour les pro grammes linéaires de plus grande taille, on uti lise plu tôt la variante
PFI (forme pro duit de l’inverse), où B
21
est uti li sée, mais impli ci te ment.
L’avan tage de la méthode révi sée (par rap port à la ver sion ini tiale de l’algo rithme
du sim plexe, par exemple implé men tée par la méthode des tableaux) est double :
– Une réduc tion de la masse des cal culs : lors de chaque ité ra tion on expli cite une
seule colonne hors- base : y
e
, la colonne entrante, au lieu des n 2 m colonnes hors
base dans la ver sion ini tiale de l’algo rithme du sim plexe.
–Desgainsdepré ci sionsontobte nus;enarith mé tiqueflot tanteleserreursdetron -
ca turesecumulent,cequipeutame ner,aufildesité ra tions,àdescal culsimpré cis,voire même faux. Ainsi lorsque l’on connaît l’ensemble des variables de base, on
peut recal cu ler B
21
direc te ment à par tir des don nées ini tiales (donc non enta chées
d’erreursaufildesité ra tions).Onrecal culeainsiB
21
(« ré inver sion ») en pra tique,
toutes les 15 à 20 ité ra tions envi ron. L’ana lyse numé rique nous four nit, ici aussi, des
méthodeseffi cacesetpré cisespourrecal cu lerB
21
.
La méthode révi sée du sim plexe est celle qui est implé men tée dans les logi ciels uti -
li sant l’algo rithme du sim plexe.
Il existe d’autres méthodes pour résoudre les pro grammes linéaires (déve lop pées
effi ca ce ment à par tir de 1985): les méthodes dites « inté rieures », dont l’exposé
sort du cadre de cet ouvrage (elles relèvent des tech niques de la pro gram ma tion non
linéaire). Leur com plexité (dans le pire des cas) est poly no miale, ce qui n’est pas le
cas de l’algo rithme du sim plexe. À l’heure actuelle aucune de ces deux approches ne
sur classe en pra tique l’autre ; d’ailleurs cer tains logi ciels très per for mants les implé -
mentent toutes deux et, lors de la réso lu tion d’un pro blème, toutes les deux sont
exé cu tées indé pen dam ment, en paral lèle : il s’opère ainsi une « course » (dont le
« gagnant » varie selon les ins tances trai tées).
8.7 dua lité
8.7.1 Défi ni tion du dual
Une des remarques les plus fruc tueuses que l’on peut faire à pro pos de la pro gram -
ma tion linéaire, est qu’à chaque pro gramme linéaire on peut asso cier, par la règle
donnée ci- dessous, un autre pro gramme linéaire, nommé « pro gramme dual ». Le
pre mier pro gramme linéaire est alors appelé « pro gramme primal ». Leurs prop rié -
tés, nous le verrons, sont étroi te ment liées.
Repre nons l’exemple pré cé dent :
f
x 1
<
1 000
x 2
<
500
x 3 <
1 500
3x 1
+
6x 2
+
2x 3 <
6 750
x 1
,
x 2
,
x 3 >
0
4x 1
+
12x 2
+
3x 3
=
z [max]