8.7 Dua lité
345
© Dunod – Toute reproduction non autorisée est un délit.
(P) f
2x 1
1
x 2
2
4x 3
<
10
2x 1
1
5x 2
2
6x 3
<
22
3x 1
2
2x 2
1
7x 3
<
5
23x 1
1
2x 2
2
7x 3
<
25
x 1
,
x 2
,
x 3
>
0
3max 4
2x 1
2
3x 2
2
4x 3
5
2z
.
D’où le dual :
(D) e
2y 1
2
y 2
1
3(y 3 2 y 4 )
>
2
y 1
1
5y 2
2
2(y 3 2 y 4 )
>
23
2 4y 1
2
6y 2
1
7(y 3 2 y 4 )
>
24
y 1
,
y 2
,
y 3 , y 4 )
>
0
3min 4
10y 1
2
2y 2 1
5(y 3 2 y 4 )
5
zr
On­a­donné,­ci-dessus,­le­dual­que­le­lec­ ­ teur­obtien­ ­ dra­en­appli­ ­ quant­la­règle­de­pas­ -
sage que nous avons détaillée plus haut.
8.7.2 Liens entre le primal et le dual
Don nons main te nant des prop rié tés impor tantes liant le primal et le dual.
1) D’abord, si l’on a la curio sité de chercher le dual du dual pour notre pre mier
exemple, il nous fau dra com men cer par rame ner les contraintes du dual à des in -
équa tions de la forme <,­et­la­fonc­ ­ tion­éco­ ­ no­ ­ mique­à­une­maxi­ ­ mi­ ­ sa­ ­ tion­:­afin­de­lemettre sous forme standard de passage au dual :
dual e
2 y 1
2
3y 4
<
24
2
y 2
2
6y 4
<
212
2
y 3
2
2y 4
<
23
y 1
,
y 2
,
y 3
,
y 4
>
0
2 1 000y 1
2
500y 2 2
1 500y 3
2
6 750y 4
3max4
Nommons t 1 , t 2 et t 3 les nouvelles variables duales :
dual
du
dual
f
2t 1
> 21 000
2 t 2
> 2500
2 t 3 > 21 500
23t 1 2 6t 2 2 2t 3 > 26 750
t 1
,
t 2
, t 3 >
0
24t 1 2 12t 2 2 3t 3 3min4
f
t 1
<
1 000
t 2
<
500
t 3
<
1 500
3t 1 1 6t 2 1 2t 3
<
6 750
t 1 ,
t 2
, t 3
>
0
4t 1 1 12t 2 1 3t 3
3max4