Maximisation produit à somme constante
Bonjour !
Je n'ai pas fait d'optimisation depuis longtemps et n'ai malheureusement pas conservé mes cours de ma période étudiante.
Je suis tombé par hasard sur l'exercice suivant et j'apprécierais énormément si vous pouviez m'indiquer où regarder pour avoir l'inspiration.
"Trouver $x_i, i = 1 \cdots n$ entiers qui maximisent le produit des $x_i$ sous la condition que la somme des $x_i$ soit égale à $100$".
Merci pour votre aide.
Sophie
Je n'ai pas fait d'optimisation depuis longtemps et n'ai malheureusement pas conservé mes cours de ma période étudiante.
Je suis tombé par hasard sur l'exercice suivant et j'apprécierais énormément si vous pouviez m'indiquer où regarder pour avoir l'inspiration.
"Trouver $x_i, i = 1 \cdots n$ entiers qui maximisent le produit des $x_i$ sous la condition que la somme des $x_i$ soit égale à $100$".
Merci pour votre aide.
Sophie
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Essaie avec $n=2$.
Puis, tape sur wikipedia " multiplicateur de lagrange ".
Je m'explique : une méthode semble fonctionner avec l'étude d'une fonction de plusieurs variables.
On cherche les points critiques etc.
On trouvera, de mémoire, une seule solution dans $\mathbb R^n$, où les composantes sont toutes égales.
Intuitivement on prend les entiers qui s'approchent du vecteur trouvé (il reste un choix à faire pour l'une ou plusieurs des composantes afin d'avoir des entiers dont la somme reste 100).
Voilà pour la conjecture.
Pour la rigueur, la continuité doit fonctionner : les extremums sont locaux sur des voisinages.
Si on arrive à isoler un voisinage contenant les entiers choisis. Là j'avoue m'avancer un peu sans regarder en détail.
Pour $\displaystyle n=2$, tu as trouvé $49, 51$. Moi je trouve $50, 50$ avec $\displaystyle 50 \times 50 = 2500 > 2499 = 49 \times 51.$
Sans se soucier du fait que les $x_i$ sont des entiers, on trouve, par la méthode des multiplicateurs de Lagrange, que tous les $\displaystyle x_i$ sont égaux et alors : $\displaystyle x_i = {100 \over n}$ et le maximum vaut $\displaystyle ({100 \over n})^n.$
En effet, on cherche le maximum de la fonction $\displaystyle F(x) = \prod_{i=1}^n x_i - \lambda (\sum_{i=1}^n x_i - 100).$
Les dérivées partielles donnent $\displaystyle \prod_{i=1, i\neq j}^n x_i - \lambda = 0, \quad j=1, \cdots, n$ pour chaque $\displaystyle x_j$ et $\displaystyle \sum_{i=1}^n x_i - 100 = 0$ pour $\lambda$, et ces équations impliquent que tous les $\displaystyle x_i$ sont égaux puis $\displaystyle x_i = {100 \over n}$.
Comme les $x_i$ doivent être entiers, il est naturel de considérer la partie entière des solutions non-entières. Soit $x_i = E({100 \over n}).$
La solution est alors, intuitivement, de choisir les $x_i$ au plus près de la solution non-entière (on arrondit donc, si $x=14.28$ on choisit $x=14$, si $x=16.67$ on choisit $x=17$) et, pour satisfaire la contrainte de la somme, d'attribuer la valeur précédent moins $1$ à un nombre suffisant de $x_k$.
Par exemple pour $n=6$, on a $16.67$ donc $x=17$ et comme $17 \times 6 = 102$ donc $2$ unités de trop, on attribue la valeur $17-1 = 16$ à $2$ variables. La solution est donc : $17$ pour $4$ variables et $16$ pour $2$ variables. Il s'agit d'écrire cette solution formellement, puis de démontrer qu'elle est maximale, c'est-à-dire que si on ajoute $1$ à une variable et retranche $1$ à une autre, alors cette solution n'est pas supérieure à celle trouvée. Je vous laisse le plaisir de l'écrire. D'ailleurs, ce raisonnement n'est pas rigoureux mathématiquement, mais est un bon argument...
a priori l'énoncé ne stipule pas que les $x_i$ sont distincts.
Je trouve alors que $(50,50)$ est meilleur que $(49,51)$.
On peut conjecturer que la suite est $(33,33,34),(25,25,25,25),(20,20,20,20,20),(16,16,17,17,17,17)...$
Cordialement
Paul
Si un des $x$ vaut 5 ou plus, il vaut mieux le remplacer
par un facteur 3 et un facteur $(x-3)$ parce que
$x<3(x-3)$
jai vu que YvesM m'avait grillé et je ne comprends pas ta remarque, Soland: quand tu remplaces $x$ par $3$ et $x-3$ tu changes le nombre de facteurs et ça ne correspond plus à la question telle, en tout cas, que je l'avais comprise. Cela dit, ça ouvre une question: quel est le plus grand produit qu'on peut obtenir en multipliant des nombres dont la somme est $100$? A l'arrache, je pense à $2^2*3^{32}$ ,mais c'est du poker, manière de faire vivre un fil plus rigolo que les éternelles conjectures.
J'ai pensé à une autre extension de la question initiale suite au fait que soso avait sous-entendu par son $(49,51)$ qu'elle voulait des $x_i$ deux à deux distincts.
Il me semble bien que, que l'on exige ou pas que les $x_i$ soient deux à deux distincts, il y a pour chacun des deux cas une et une seule solution, le second cas étant réglé.
En effet, pour le premier cas, pour tout naturel $n$, tout naturel $S$, pourvu qu'il soit somme de $n$ naturels distincts deux à deux, est somme d'une et une seule façon de $n$ naturels distincts deux à deux tels que la différence entre le plus grand et le plus petit est inférieure à $n$.
Le produit des naturels en question est le seul à atteindre le record.
En espérant etc...
Cordialement
Paul
je n'avais pas immédiatement réalisé que ta remarque me faisait gagner au poker!