7.5 Espaces de permutations
207
α(t) =
t
τ
α(τ ) 1 [0,τ ] (t) + α(τ ) 1 [τ,∞[ (t)
o` u α(τ ) repr´ esente la perte financi` ere relative `
a un contrat qui n’a pas ´ et´ e
honor´ e au temps fix´ e τ . De mˆ eme, le nombre maximal δ de pi` eces d´ efectueuses
admises lors d’un contrat de vente est souvent fix´ e. Cette situation peut `
a
nouveau ˆ etre mod´ elis´ ee par des fonctions lin´ eaires par morceaux
β(d) =
d
δ
β(δ) 1 [0,δ] (d) + β(δ)1 [δ,∞[ (d)
o` u β(δ) repr´ esente la perte financi` ere relative `
a un contrat de production
contenant plus de pi` eces d´ efectueuses que le nombre autoris´ e δ.
7.5 Espaces de permutations
7.5.1 Syst` emes de voisinages
Les trajets commerciaux entre N villes, les allocations de N ressources
entre N ´ equipes, les r´ epartitions de N tˆ aches dans N locaux, et les stockages
de N produits sur N sites industriels, correspondent ` a des r´ epartitions de
N objets virtuels dans N cases, tout aussi virtuelles. L’espace d’´ etat naturel
est donn´ e par l’ensemble des applications bijectives de l’ensemble des indices
{1, . . . , N} sur lui mˆ eme
E = G N = {σ : {1, . . . , N} → {1, . . . , N} bijectives}
Dans l’exemple du voyageur de commerce, chaque application σ caract´ erise
un parcours bien pr´ ecis entre chacune des N villes :
1 → σ(1) = premi` ere ville visit´ ee
2 → σ(2) = seconde ville visit´ ee
3 → σ(3) = troisi` eme ville visit´ ee
. . . = . . .
N → σ(N ) = derni` ere ville visit´ ee
On a coutume de noter chaque application σ, par la matrice (2× N ) suivante :
σ =
1
2
3 . . . N − 1
N
σ(1) σ(2) σ(3) . . . σ(N − 1) σ(N )
Toujours dans l’exemple du voyageur de commerce, la seconde ligne correspond au circuit entre les N villes
σ(1) → σ(2) → σ(3) → . . . → σ(N − 1) → σ(N ) (→ σ(1))
La figure 7.3 repr´ esente un exemple de chemin associ´ e ` a une permutation.