Chapitre 8 • La programmation linéaire
352
Enfincesrela tionsimpliquentque:
– si une contrainte du primal n’est pas satu rée (x i 2 0), alors la variable duale
asso ciée à cette contrainte est nulle : y i = 0 ;
– si une contrainte du dual n’est pas satu rée (y j 2 0), alors la variable primale
asso ciée à cette contrainte est nulle : xj = 0 ;
– si une variable du primal x j est non nulle, alors la variable d’écart du dual y j
est nulle.
– si une variable du dual y i est non nulle, alors la variable d’écart du primal x i
est nulle.
8.8 pro gramme liNéaire eN Nombres eNtiers
méthodes des troNcatures de gomory
En pra tique il arrive fré quem ment que dans un pro gramme linéaire cer taines
variablessoientastreintesàêtreentières,commenousl’avonsdéjàvuenfinducha -
pitre1.Onparlealorsde«pro grammelinéaireennombresentiers»(PLNE).
Ainsi une entre prise ne sau rait construire 1, 45 entre pôts, acqué rir x 2 = 2, 37 camions
ou encore affré ter x 3 = 0, 41 avion. . . comme pour rait lui indi quer la solu tion opti -
male d’un PL en variables conti nues ! Mal heu reu se ment l’arrondi des variables, que ce
soit par excès ou par défaut, peut ne pas être opti mal ou, pire, ne pas être admis sible
(comme dans l’exemple du para graphe sui vant). Aussi ne pourra- t-on pas se contenter
d’arron dir les variables pour pas ser de l’opti mum du PL continu à celui du PLNE.
En outre, dans la modé li sa tion de nom breux pro blèmes de recherche opé ra tion nelle,
il se révèle néces saire d’intro duire des variables binaires : x j = 0 ou 1, pour repré sen ter
des contraintes non clas siques, comme par exemple des dis conti nui tés dans une courbe
detarifd’untran spor teuroudanslecasdechargesfixes,s’ajou tantàuncoûtd’acti vitépro por tion nel au niveau de cette acti vité, dès lors que ce niveau n’est pas nul ; ou, plus
clas si que ment, pour le choix d’entre pôts à construire sur des sites à déter mi ner dans
une liste des sites pos sibles ; ou encore pour le choix de maté riels à acqué rir ou pas.
Quelques modèles clas siques sont impor tants pour les appli ca tions en logis tique
comme dans les plan nings de tran sport de per sonnes (auto bus, métros, trains, avions) :
le pro blème du sac à dos ou knapsack (déjà traité dans cet ouvrage), le pro blème de par
tition ne ment, le pro blème de recou vre ment (consul ter, par exemple, [Roseaux, tome 3]).
Voici un exemple de « knapsack » : un camion peut tran spor ter une charge maximale de b
= 14 tonnes, de n = 4 mar chan dises dif fé rentes. Le poids de cha cune des 4 mar chan dises
estres pec ti ve mentde4,6,8et10tonnes.Enfin,lebéné ficeattendudelaventedecha cunedes mar chan dises, après son tran sport, vaut res pec ti ve ment : 2 000, 2 700, 3 600 et 4 400
euros.Déter mi nerlechar ge mentducamionper met tantdemaxi mi serlebéné fice.
Le pro blème s’écrit :
c
4x 1
1
6x 2
1
8x 3
1
10x 4
< 14
x 1
,
x 2
,
x 3
,
x 4
5 0 ou 1
2 000x 1
1
2 700x 2
1
3 600x 3
1
4 400x 4
5 z 3max4
352
Enfincesrela tionsimpliquentque:
– si une contrainte du primal n’est pas satu rée (x i 2 0), alors la variable duale
asso ciée à cette contrainte est nulle : y i = 0 ;
– si une contrainte du dual n’est pas satu rée (y j 2 0), alors la variable primale
asso ciée à cette contrainte est nulle : xj = 0 ;
– si une variable du primal x j est non nulle, alors la variable d’écart du dual y j
est nulle.
– si une variable du dual y i est non nulle, alors la variable d’écart du primal x i
est nulle.
8.8 pro gramme liNéaire eN Nombres eNtiers
méthodes des troNcatures de gomory
En pra tique il arrive fré quem ment que dans un pro gramme linéaire cer taines
variablessoientastreintesàêtreentières,commenousl’avonsdéjàvuenfinducha -
pitre1.Onparlealorsde«pro grammelinéaireennombresentiers»(PLNE).
Ainsi une entre prise ne sau rait construire 1, 45 entre pôts, acqué rir x 2 = 2, 37 camions
ou encore affré ter x 3 = 0, 41 avion. . . comme pour rait lui indi quer la solu tion opti -
male d’un PL en variables conti nues ! Mal heu reu se ment l’arrondi des variables, que ce
soit par excès ou par défaut, peut ne pas être opti mal ou, pire, ne pas être admis sible
(comme dans l’exemple du para graphe sui vant). Aussi ne pourra- t-on pas se contenter
d’arron dir les variables pour pas ser de l’opti mum du PL continu à celui du PLNE.
En outre, dans la modé li sa tion de nom breux pro blèmes de recherche opé ra tion nelle,
il se révèle néces saire d’intro duire des variables binaires : x j = 0 ou 1, pour repré sen ter
des contraintes non clas siques, comme par exemple des dis conti nui tés dans une courbe
detarifd’untran spor teuroudanslecasdechargesfixes,s’ajou tantàuncoûtd’acti vitépro por tion nel au niveau de cette acti vité, dès lors que ce niveau n’est pas nul ; ou, plus
clas si que ment, pour le choix d’entre pôts à construire sur des sites à déter mi ner dans
une liste des sites pos sibles ; ou encore pour le choix de maté riels à acqué rir ou pas.
Quelques modèles clas siques sont impor tants pour les appli ca tions en logis tique
comme dans les plan nings de tran sport de per sonnes (auto bus, métros, trains, avions) :
le pro blème du sac à dos ou knapsack (déjà traité dans cet ouvrage), le pro blème de par
tition ne ment, le pro blème de recou vre ment (consul ter, par exemple, [Roseaux, tome 3]).
Voici un exemple de « knapsack » : un camion peut tran spor ter une charge maximale de b
= 14 tonnes, de n = 4 mar chan dises dif fé rentes. Le poids de cha cune des 4 mar chan dises
estres pec ti ve mentde4,6,8et10tonnes.Enfin,lebéné ficeattendudelaventedecha cunedes mar chan dises, après son tran sport, vaut res pec ti ve ment : 2 000, 2 700, 3 600 et 4 400
euros.Déter mi nerlechar ge mentducamionper met tantdemaxi mi serlebéné fice.
Le pro blème s’écrit :
c
4x 1
1
6x 2
1
8x 3
1
10x 4
< 14
x 1
,
x 2
,
x 3
,
x 4
5 0 ou 1
2 000x 1
1
2 700x 2
1
3 600x 3
1
4 400x 4
5 z 3max4