Discussion:Inégalité de Nesbitt

bandeaux

je les ai enlevés, sauf "ébauche", mais même ce dernier bandeau me semble superflu désormais, non ?? Chassaing 7 août 2009 à 22:54 (CEST)

Inégalité de réarrangement

je comprend l'expression "inégalité de réarrangement" de la manière suivante :

Inégalité de réarrangement —  Si $\scriptstyle \ x_{1}\leq x_{2}\leq \dots \leq x_{n},\$ et si $\scriptstyle \ y_{1}\leq y_{2}\leq \dots \leq y_{n},\$ alors

$\forall \sigma \in {\mathfrak {S}}_{n},\qquad \sum _{i=1}^{n}x_{i}y_{i}\ \geq \ \sum _{i=1}^{n}x_{i}y_{\sigma (i)}.$

ou encore

$x_{1}y_{1}+\cdots +x_{n}y_{n}\geq x_{\sigma (1)}y_{1}+\cdots +x_{\sigma (n)}y_{n}\geq x_{n}y_{1}+\cdots +x_{1}y_{n}.$

Ou encore, on a intérêt à avoir les meilleures notes dans les matières qui ont le plus gros coefficient, ou autre interprétation concrète raisonnablement parlante. Si toutes les inégalités de l'hypothèse sont strictes, il n'y a égalité que pour σ=Id. Sûrement cette inégalité extrêmement basique et très utile existe quelque part dans Wikipedia, mais sous quel nom ??? Elle ne mérite pas vraiment démonstration, mais une démonstration est instructive quand même, p.e. réduire petit à petit le nombre d'inversions de σ ne fait qu'augmenter la fonctionnelle de σ qui apparaît dans le terme de droite, je crois. Ce qui permet de discuter le fait que ${\mathfrak {S}}_{n}\$ est engendré par les transpositions. Je suis probablement très approximatif, là . Chassaing 5 août 2009 à 16:02 (CEST)

Je me rappelle l'avoir vue utilisée pour la résolution de problèmes élémentaires d'ordonnancement, et en particulier pour l'optimisation d'algorithmes basiques de rangement. Un énoncé typique serait : minimiser le temps total d'attente des individus $\scriptstyle \ i\in [\![1,n]\!],\$ dans une file d'attente, sachant que le temps nécessaire pour traiter l'individu i est $\scriptstyle \ x_{i},\$ et sachant que $\scriptstyle \ x_{1}\leq x_{2}\leq \dots \leq x_{n}.\$ On applique alors l'"inégalité de réarrangement" avec $\scriptstyle \ y_{i}=n+1-i,\$ $\scriptstyle \ \sigma (i)\$ désignant le rang de l'individu i dans la file. Comme on minimise au lieu de maximiser, et comme la suite $\scriptstyle \ y_{i}=n+1-i,\$ est décroissante plutôt que croissante, la solution optimale est encore σ=Id, si je me rappelle bien : dans la queue au supermarché, il faut donc faire passer d'abord ceux qui ont le caddy le moins plein ... Cela doit s'appeler un problème de flow-shop ??? sous réserve ??? (appel à l'aide aux spécialistes de recherche opérationnelle ...) Chassaing 5 août 2009 à 16:12 (CEST)

voir en:Rearrangement inequality ou de:Umordnungs-Ungleichung qui fournissent en outre des sources bibliographiques. HB (d) 5 août 2009 à 18:03 (CEST)

merci !!! cette page manque clairement au wikipedia français. L'inégalité est tellement universelle que je doute qu'elle soit dûe à une référence aussi tardive que celle donnée par l'article anglais. (Mais après tout on s'en fout, en 1ère approximation) Chassaing 5 août 2009 à 20:33 (CEST)

Hardy Littlewood Polya, comme référence, me plait plus, et c'est une occasion de citer cet excellent livre. L'article allemand donne deux démonstrations utiles, au lieu d'une seule, qui plus est. Réarrangement serait plus joli que "réordonnement", non ?? Chassaing 5 août 2009 à 20:37 (CEST)