Exercices
365
© Dunod – Toute reproduction non autorisée est un délit.
1. Don ner, sous la forme d’un tableau, les 6 pos si bi li tés de coupe (« plans de
coupe ») stan dard en fonc tion des lar geurs com man dées, ainsi que les pertes sur
la lar geur (expri mées en cm). On jus ti fiera le fait qu’on ne consi dère que 6 pos
si bi li tés, à énu mé rer dans l’ordre lexi co gra phique : 1) AA, 2) AΒ, … 6) CCC.
2. a) En notant x j la lon gueur décou pée sui vant le plan de coupe j
( j = l, 2, …, 6), modé li ser ce pro blème sous forme de pro gramme linéaire.
b) Don ner son dual et poser le pre mier tableau de la réso lu tion de ce dual.
c) Trou ver une solu tion opti male du dual quasi évi dente (qu’implique la
3
e
contrainte du dual).
3. En divi sant chaque contrainte du primal par un entier conve nable, faire
appa raître une base évi dente (avec B = I ) et poser le tableau asso cié. Est il
opti mal ? (NB : intro duire les variables d’écart seulement APRES ces divi
sions.) Com pa rer cette démarche avec l’emploi de variables arti fi cielles
pour le primal sous sa forme du 2).
4. Par ins pec tion des contraintes expri mant que les lon gueurs décou pées,
res pec ti ve ment en lar geur 95 cm (A) et 84 cm (B), sont au moins égales aux
lon gueurs res pec tives com man dées, et en tenant compte des coef fi cients de
la fonc tion éco no mique, trou ver par un rai son ne ment direct le (ou les) opti
mum(s). On jus ti fiera le fait que les variables x 3 , x 5 et x 7 sont les variables
de base à l’opti mum. Don ner alors la sur face des chûtes en m
2
.
5. Don ner la matrice de base Β asso ciée à la solu tion du 4) pour laquelle la
lon gueur décou pée en lar geur 95 cm vaut exac te ment 180 m. Cal cu ler Β
–1
,
puis dres ser le tableau du sim plexe asso cié. Conclure.
6. a) A l’aide du 5), déter mi ner sans cal cul les valeurs opti males des variables
duales.
b) Retrou ver ces valeurs, à l’aide des rela tions d’exclu sion, connais sant l’opti
mum du primal.
**8.8 Démar rage de l’algo rithme du sim plexe : pro blème
de la base ini tiale
Soit le programme linéaire (PL) :
x 1
1
3x 2
1
5x 3
1
x 4
1
4x 5
5 z 3max4
d
x 1
1
x 2
2
x 3
1
x 4
5
1
3x 1
1
x 2
1
3x 3
1
3x 4
1
x 5
5
8
2x 1
1
7x 2
1
x 4
1
2x 5
5 20
x 1
,
x 2
,
x 3
,
x 4
,
x 5
>
0
1. Véri fier que la solu tion x 1 = 0 ; x 2 = 2 ; x 3 = 1 ; x 4 = 0 ; x 5 = 3 est une
solu tion de base ; on notera B la matrice for mée des colonnes asso ciées aux
variables de cette base.
2. Expri mer cha cune des variables de base en fonc tion des variables hors
base (il sera néces saire de cal cu ler B
–1
).
365
© Dunod – Toute reproduction non autorisée est un délit.
1. Don ner, sous la forme d’un tableau, les 6 pos si bi li tés de coupe (« plans de
coupe ») stan dard en fonc tion des lar geurs com man dées, ainsi que les pertes sur
la lar geur (expri mées en cm). On jus ti fiera le fait qu’on ne consi dère que 6 pos
si bi li tés, à énu mé rer dans l’ordre lexi co gra phique : 1) AA, 2) AΒ, … 6) CCC.
2. a) En notant x j la lon gueur décou pée sui vant le plan de coupe j
( j = l, 2, …, 6), modé li ser ce pro blème sous forme de pro gramme linéaire.
b) Don ner son dual et poser le pre mier tableau de la réso lu tion de ce dual.
c) Trou ver une solu tion opti male du dual quasi évi dente (qu’implique la
3
e
contrainte du dual).
3. En divi sant chaque contrainte du primal par un entier conve nable, faire
appa raître une base évi dente (avec B = I ) et poser le tableau asso cié. Est il
opti mal ? (NB : intro duire les variables d’écart seulement APRES ces divi
sions.) Com pa rer cette démarche avec l’emploi de variables arti fi cielles
pour le primal sous sa forme du 2).
4. Par ins pec tion des contraintes expri mant que les lon gueurs décou pées,
res pec ti ve ment en lar geur 95 cm (A) et 84 cm (B), sont au moins égales aux
lon gueurs res pec tives com man dées, et en tenant compte des coef fi cients de
la fonc tion éco no mique, trou ver par un rai son ne ment direct le (ou les) opti
mum(s). On jus ti fiera le fait que les variables x 3 , x 5 et x 7 sont les variables
de base à l’opti mum. Don ner alors la sur face des chûtes en m
2
.
5. Don ner la matrice de base Β asso ciée à la solu tion du 4) pour laquelle la
lon gueur décou pée en lar geur 95 cm vaut exac te ment 180 m. Cal cu ler Β
–1
,
puis dres ser le tableau du sim plexe asso cié. Conclure.
6. a) A l’aide du 5), déter mi ner sans cal cul les valeurs opti males des variables
duales.
b) Retrou ver ces valeurs, à l’aide des rela tions d’exclu sion, connais sant l’opti
mum du primal.
**8.8 Démar rage de l’algo rithme du sim plexe : pro blème
de la base ini tiale
Soit le programme linéaire (PL) :
x 1
1
3x 2
1
5x 3
1
x 4
1
4x 5
5 z 3max4
d
x 1
1
x 2
2
x 3
1
x 4
5
1
3x 1
1
x 2
1
3x 3
1
3x 4
1
x 5
5
8
2x 1
1
7x 2
1
x 4
1
2x 5
5 20
x 1
,
x 2
,
x 3
,
x 4
,
x 5
>
0
1. Véri fier que la solu tion x 1 = 0 ; x 2 = 2 ; x 3 = 1 ; x 4 = 0 ; x 5 = 3 est une
solu tion de base ; on notera B la matrice for mée des colonnes asso ciées aux
variables de cette base.
2. Expri mer cha cune des variables de base en fonc tion des variables hors
base (il sera néces saire de cal cu ler B
–1
).