V.3. La dualité en programmation linéaire
Connaissant K ◦
1 , la relation (5.22) se traduit par :
y 1 y 2 , y 1 + y 2 2y 3 , y 1 + y 2 + y 3 3y 4 , . . .
. . . , y 1 + . . . + y n−1 (n − 1) y n et y 1 + y 2 + . . . + y n = 0.
(5.23)
Un dernier effort pour montrer que (5.23) équivaut à :
y 1
y 1 +y 2
2
y 1 +y 2 +y 3
3
. . .
y 1 +...+yn
n
et y 1 + . . . + y n = 0.
(5.24)
Finalement
K
◦
3 =
y = (y 1 , . . . , y n ) ∈ R
n
| y 1
y 1 + y 2
2
. . .
y 1 + . . . + y k
k
. . .
. . .
y 1 + . . . + y n
n
et
n
i=1
y i = 0
.
En suivant une démarche similaire, on arrive à l’expression suivante de K ◦
4 :
K
◦
4 =
y = (y 1 , . . . , y n ) ∈ R
n
| y 1
y 1 + y 2
2
. . .
y 1 + . . . + y k
k
. . .
. . .
y 1 + . . . + y n
n
0
.
Commentaire : Les cônes K i interviennent en Statistique (régression monotone)
où à partir d’un échantillon x 1 , . . . , x n , on cherche x 1 , . . . , x n ordonné dans un
certain sens (i.e. (x 1 , . . . , x n ) ∈ K i ) le plus proche possible de x 1 , . . . , x n au sens
d’une distance euclidienne. Voir l’Exercice III.24 par exemple.
** Exercice V.10. Soit C le polyèdre convexe fermé de R n représenté de la manière suivante :
C := {x ∈ R
n
| |a i , x b i pour i = 1, . . . , p,
et a i , x = b i pour i = p + 1, . . . , q}.
187