9.4 Autre méthode de cal cul : les p.l. des deux joueurs sont en dua lité
377
© Dunod – Toute reproduction non autorisée est un délit.
On se sou vien dra, lors qu’on aura trouvé la valeur gr du jeu cor res pon dant à cette matrice,
que : g 5 gr 2 4. Écri vons alors les pro grammes linéaires rela tifs au nou veau jeu :
B f
3q 1
+ 6q 2 + 5q 3 < gr
A f
3p 1
+ 5p 2 + 7p 3 > gs
5q 1
+ 2q 2 + 6q 3 < gr
6p 1
+ 2p 2 + 8p 3 > gs
7q 1
+ 8q 2 + q 3 < gr
5p 1
+ 6p 2 + p 3 > gs
q 1
+ q 2 + q 3 = 1
p 1
+ p 2 + p 3 = 1
q 1
,
q 2 ,
q 3 > 0
p 1
,
p 2 ,
p 3 > 0
[min] gr
[max] gs
Pour B nous pou vons divi ser cha cune des in équa tions ci­ dessus par gr sans en changer
leur sens, puisque gr . 0. De même, par gs pour A, puisque gs . 0 (nous mon trons
plus bas que : gr 5 gs).
On obtient, en posant x j 5 q j / g r et y i 5 p i / g s :
A f
3y 1 + 5y 2 + 7y 3 > 1
6y 1 + 2y 2 + 8y 3 > 1
5y 1 + 6y 2 +
y 3 > 1
y 1 ,
y 2 ,
y 3 > 0
y 1 +
y 5 +
y 3 = 1
gs
[min].
B f
3x 1 + 6x 2 + 5x 3 < 1
5x 1 + 2x 2 + 6x 3 < 1
7x 1 + 8x 2 +
x 3 < 1
x 1 ,
x 2 ,
x 3 > 0
x 1 +
x 2 +
x 3 = 1
gr
[max]
et, bien entendu, B dési rant minimi ser gr qui est posi tif, il maxi mi sera son inverse :
z 5
1
gr
5 x 1 1 x 2 1 x 3 .
Par suite, les deux pro grammes linéaires obte nus sont en dua lité : le dual du pro ­
gramme de B est le pro gramme de A et réci pro que ment. En par ti cu lier, à l’opti mum,
on a :
1
gr
5
1
gs
et donc : g9 5 g 0 5 g.
Résol vons le pro gramme B (plutôt que celui de A, qui nécessiterait l’introduction de
trois variables artificielles) :
0
0
0
0
0
6
6
0
0
0
0
0
0
0
3
z  0
1
1
1
1
1
1
1
1
1
1
1
2
↑
s
↑
e
1
1
2
2
2
5
5
7
8
3
3
3