Chapitre 8 • La programmation linéaire
362
1. Quelle est la meilleure répar tition des quan ti tés de minerais à extraire ?
2. On conteste le pro fit réa lisé sur le mine rai extrait de la taille 1 : com
ment l’opti mum est il modi fié si ce pro fit varie autour de 4 uni tés moné
taires ? Poser : c 1 = 4(1 + l).
Les cal culs pour la ques tion 3 étant longs, le lec teur est invité à consul ter
le cor rigé.
3. La quan tité maximale, extraite de t 3 a été mal éva luée. Com ment la
répar tition opti male évolue telle si l’on pose : e 3 = 300(1 + μ) ?
NB. Cet exer cice couvre une grande par tie de ce cha pitre de P.L.
Le niveau de la ques tion 2 est de 2 étoiles ; celui de la 3
ème
, de 3 étoiles.
*8.3 Contrainte redon dante. Dua lité
Soit à maxi mi ser la fonc tion nelle linéaire :
5x 1
1
4x 2
1
3x 3
1
x 4
5 z
sous les contraintes :
e
x 1
1
x 2
1
x 3
1
x 4
< 12 (1)
3x 1
1
2x 2
1
3x 3
1
x 4
< 5 (2)
2x 1
1
x 2
1
x 3
1
4x 4
< 7 (3)
x 1
,
x 2
,
x 3
,
x 4
> 0 (4, 5, 6 et 7) (cf. 3)).
1. Résoudre ce pro gramme par l’algo rithme du sim plexe.
2. Don ner, sans cal cul, l’optimum du pro gramme dual cor res pon dant.
3. Mon trer que l’in équa tion (1) du pro gramme primal est redon dante.
Tenant compte de ce fait, sim pli fier le pro gramme dual puis le résoudre
gra phi que ment.
**8.4 Formulation d'un P.L. Paramétrage d'un second membre
Ondésirefaireunmélangedetroisgazcom bus tiblesdanslescondi tionssui vantes:
– le volume total doit atteindre 250 000 m
3
;
– la teneur en soufre ne doit pas dépas ser 3 grammes/m
3
;
– levolumecalo ri fiquedoitêtrecom prisentre2200mth/m
3
et 2 600 mth/m
3
;
– la pro por tion du troi sième gaz ne doit pas excé der 28 % du volume total.
Les teneurs res pec tives en soufre sont de 7,5 et 2 grammes par m
3
. Les pou voirs
calo ri fiquesres pec tifssemontentà1000,2000et6000mth/m
3
.
Onpren dralemillierdem
3
comme unité de volume.
1. Déter mi ner le mélange le moins coû teux, en admet tant que les prix res
pec tifs sont de 12, 36 et 10 uni tés moné taires par millier de m
3
et en notant
x 1 , x 2 et x 3 le volume de cha cun des trois gaz conte nus dans le mélange,
gra phi que ment.
362
1. Quelle est la meilleure répar tition des quan ti tés de minerais à extraire ?
2. On conteste le pro fit réa lisé sur le mine rai extrait de la taille 1 : com
ment l’opti mum est il modi fié si ce pro fit varie autour de 4 uni tés moné
taires ? Poser : c 1 = 4(1 + l).
Les cal culs pour la ques tion 3 étant longs, le lec teur est invité à consul ter
le cor rigé.
3. La quan tité maximale, extraite de t 3 a été mal éva luée. Com ment la
répar tition opti male évolue telle si l’on pose : e 3 = 300(1 + μ) ?
NB. Cet exer cice couvre une grande par tie de ce cha pitre de P.L.
Le niveau de la ques tion 2 est de 2 étoiles ; celui de la 3
ème
, de 3 étoiles.
*8.3 Contrainte redon dante. Dua lité
Soit à maxi mi ser la fonc tion nelle linéaire :
5x 1
1
4x 2
1
3x 3
1
x 4
5 z
sous les contraintes :
e
x 1
1
x 2
1
x 3
1
x 4
< 12 (1)
3x 1
1
2x 2
1
3x 3
1
x 4
< 5 (2)
2x 1
1
x 2
1
x 3
1
4x 4
< 7 (3)
x 1
,
x 2
,
x 3
,
x 4
> 0 (4, 5, 6 et 7) (cf. 3)).
1. Résoudre ce pro gramme par l’algo rithme du sim plexe.
2. Don ner, sans cal cul, l’optimum du pro gramme dual cor res pon dant.
3. Mon trer que l’in équa tion (1) du pro gramme primal est redon dante.
Tenant compte de ce fait, sim pli fier le pro gramme dual puis le résoudre
gra phi que ment.
**8.4 Formulation d'un P.L. Paramétrage d'un second membre
Ondésirefaireunmélangedetroisgazcom bus tiblesdanslescondi tionssui vantes:
– le volume total doit atteindre 250 000 m
3
;
– la teneur en soufre ne doit pas dépas ser 3 grammes/m
3
;
– levolumecalo ri fiquedoitêtrecom prisentre2200mth/m
3
et 2 600 mth/m
3
;
– la pro por tion du troi sième gaz ne doit pas excé der 28 % du volume total.
Les teneurs res pec tives en soufre sont de 7,5 et 2 grammes par m
3
. Les pou voirs
calo ri fiquesres pec tifssemontentà1000,2000et6000mth/m
3
.
Onpren dralemillierdem
3
comme unité de volume.
1. Déter mi ner le mélange le moins coû teux, en admet tant que les prix res
pec tifs sont de 12, 36 et 10 uni tés moné taires par millier de m
3
et en notant
x 1 , x 2 et x 3 le volume de cha cun des trois gaz conte nus dans le mélange,
gra phi que ment.