Pensez à lire la Charte avant de poster !

$\newcommand{\K}{\mathbf K}$


Les-Mathematiques.net - Cours de mathématiques supérieures
 Les-Mathematiques.net - Cours de mathématiques universitaires - Forum - Cours à télécharger

A lire
Deug/Prépa
Licence
Agrégation
A télécharger
Télécharger
150 personne(s) sur le site en ce moment
E. Cartan
A lire
Articles
Math/Infos
Récréation
A télécharger
Télécharger
Théorème de Cantor-Bernstein
Théo. Sylow
Théo. Ascoli
Théo. Baire
Loi forte grd nbre
Nains magiques
 
 
 
 
 

Maximisation produit à somme constante

Envoyé par soso23 
Maximisation produit à somme constante
il y a trois années
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 :)



Edité 3 fois. La dernière correction date de il y a trois années et a été effectuée par jacquot.
Re: Maximisation produit sous condition sur la S
il y a trois années
avatar
Bonjour,

Essaie avec $n=2$.

Puis, tape sur wikipedia " multiplicateur de lagrange ".
Re: Maximisation produit sous condition sur la S
il y a trois années
avatar
@YvesM: les $x_i$ doivent être entiers.

Greg

Ora, lege, lege, relege, labora et invenies (Prie, lis, lis , relis, travaille et tu trouveras)
Re: Maximisation produit sous condition sur la S
il y a trois années
J'avais essayé ça, i.e. commencer par $n=2$ et j'avais trouvé $49$ et $51$, mais après je voyais pas comment généraliser à $n$...
Dom
Re: Maximisation produit sous condition sur la S
il y a trois années
En effet cette histoire d'entiers suggère davantage des conjectures que de la rigueur...
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.
Re: Maximisation produit sous condition sur la S
il y a trois années
avatar
Je suppose que les $x_i$ sont positifs ?

Greg

Ora, lege, lege, relege, labora et invenies (Prie, lis, lis , relis, travaille et tu trouveras)



Edité 1 fois. La dernière correction date de il y a trois années et a été effectuée par GreginGre.
Re: Maximisation produit sous condition sur la S
il y a trois années
avatar
Bonjour @soso23,

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...
Re: Maximisation produit sous condition sur la S
il y a trois années
Bonjour,

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
Re: Maximisation produit sous condition sur la S
il y a trois années
Oui c'est vrai. Au temps pour moi. Merci bien pour ces explications parfaitement claires et détaillées. J'ai refait un tour sur Wikipédia pour le multiplicateur de Lagrange, ne l'ayant pas vu depuis des années. :)
Re: Maximisation produit à somme constante
il y a trois années
avatar
Autre piste de réflexion :

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)$
Re: Maximisation produit à somme constante
il y a trois années
Bonsoir,

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
Re: Maximisation produit à somme constante
il y a trois années
Merci Soland,

je n'avais pas immédiatement réalisé que ta remarque me faisait gagner au poker!
Seuls les utilisateurs enregistrés peuvent poster des messages dans ce forum.

Cliquer ici pour vous connecter

Liste des forums - Statistiques du forum

Total
Discussions: 136 310, Messages: 1 317 626, Utilisateurs: 24 007.
Notre dernier utilisateur inscrit Sana79.


Ce forum
Discussions: 734, Messages: 5 960.

 

 
©Emmanuel Vieillard Baron 01-01-2001
Adresse Mail:

Inscription
Désinscription

Actuellement 16057 abonnés
Qu'est-ce que c'est ?
Taper le mot à rechercher

Mode d'emploi
En vrac

Faites connaître Les-Mathematiques.net à un ami
Curiosités
Participer
Latex et autres....
Collaborateurs
Forum

Nous contacter

Le vote Linux

WWW IMS
Cut the knot
Mac Tutor History...
Number, constant,...
Plouffe's inverter
The Prime page