Bonjour,
J'ai un petit problème mathématique et je précise que mes connaissances datent d'il y a longtemps.
On m'a indiqué que le problème est insoluble (je n'ai pas compris pourquoi) mais il est clair qu'il y a une solution d'optimisation.
Voici le problème:
J'ai un panier P1 avec 5 pommes, 3 oranges, 1 litchi et demi :), et une demi mangue
J'ai un panier P2 avec 10 oranges
J'ai un panier P3 avec 6 litchis, 3 mangues, une demi pomme et une demi orange
Quelle combinaison de panier P1, P2, P3 dois-je avoir pour se rapprocher le plus possible de 3 pommes, 3 oranges, 3 litchis et 1 mangue. (les paniers sont inséparables, on prend un pourcentage de panier)
D'où mes questions:
1) s'agit-il d'un problème d'optimisation linéaire ?
2) comment poser l'équation sous la forme min ou max (ou autre), sc...
En vous remerciant d'avance pour vos réponses, je tenterai ensuite de le résoudre avec le solver d'Excel.
Optimisation linéaire
10 messages
- Page 1 sur 1
par eriadrim » 02 Jan 2015, 14:45
Si on veut un nombre entier de paniers (ce qui serait le plus logique), le problème est bien insoluble.
En effet, si on prend plus d'une fois le panier P3, alors on a forcemment plus de 1 mangue. De même avec le panier P2, on a forcemment plus de 3 oranges. Donc on doit le faire avec seulement le panier P1, et le nombre de mangues dans le panier P1 nous indique qu'il en faut 2.
On aurait donc 1 mangue, 3 litchis (jusque la c'est parfait), mais on aurait aussi 6 oranges et 10 pommes, ce qui est incohérent. Donc il n'y a pas de solutions.
Maintenant si tu autorise les solutions non entière, on peut travailler de façon matricielle. Tu veut x panier P1, y panier P2, z panier P3, tel qu'à la fin, on ai exactement 3 pommes, 3 oranges, 3 litchis, 1 mangue.
L'idée est d'abord de simplifier le problème un petit peu quitte à ne pas le résoudre totalement. Par exemple, on peut mettre de coté provisoirement les mangues et chercher x panier P1, y panier P2, z panier P3 tel qu'à la fin, on ai exactement 3 pommes, 3 oranges, 3 litchis.
Donc :
3x + 10y + 0.5z = 3
5x + 0y + 0.5z = 3
1.5x + 0y + 6z = 3
Sous forme matricielle :
La matrice étant inversible, il y aura une unique solution, il restera plus qu'a vérifier qu'elle fonctionne aussi pour les mangues.
Donc si ça ne marche pas pour les mangues, mais que tu veux approcher le résultat au plus proche alors la oui c'est un problème d'optimisation.
L'idée pour bien poser ces problèmes c'est savoir ce que l'on veut optimiser. Ce rapprocher le plus possible de 3 oranges, 3 pommes, 3 litchis, 1 mangue c'est très vague : se rapprocher dans le sens la moyenne des écarts est le plus bas possible ou on veut qu'il y en ai le maximum avec le nombre exact (par exemple).
Dans le deuxième cas, c'est la résolution qu'il y a au-dessus. Pour la moyenne, si on appelle a, b, c, d, les quantités de pommes, d'oranges, le litchis et de mangues, on veut minimiser P = |3-a| + |3-b| + |3-c| + |1-d|
Mais on peut simplifier ce problème, on remarque que a et c imposent le nombre de panier P1 et P3, donc impose d car il n'y a ps e mangues dans le panier P2.
Donc on peut compléter le nombre d'oranges avec le panier P2. Donc l'écart que l'on peut avoir entre le nombre d'orange voulu et obtenu est de 0.
Donc P = |3-a| + |3-c| + |1-d|
De plus d dépendant de a et c, on obtient finalement une fonction à deux variables dont on veut trouver le minimum.
En trouvant le minimum, on trouve le nombre de panier P1 et P3 et il suffit de completer avec le nombre de panier P2 pour avoir exactement 3 oranges
En effet, si on prend plus d'une fois le panier P3, alors on a forcemment plus de 1 mangue. De même avec le panier P2, on a forcemment plus de 3 oranges. Donc on doit le faire avec seulement le panier P1, et le nombre de mangues dans le panier P1 nous indique qu'il en faut 2.
On aurait donc 1 mangue, 3 litchis (jusque la c'est parfait), mais on aurait aussi 6 oranges et 10 pommes, ce qui est incohérent. Donc il n'y a pas de solutions.
Maintenant si tu autorise les solutions non entière, on peut travailler de façon matricielle. Tu veut x panier P1, y panier P2, z panier P3, tel qu'à la fin, on ai exactement 3 pommes, 3 oranges, 3 litchis, 1 mangue.
L'idée est d'abord de simplifier le problème un petit peu quitte à ne pas le résoudre totalement. Par exemple, on peut mettre de coté provisoirement les mangues et chercher x panier P1, y panier P2, z panier P3 tel qu'à la fin, on ai exactement 3 pommes, 3 oranges, 3 litchis.
Donc :
3x + 10y + 0.5z = 3
5x + 0y + 0.5z = 3
1.5x + 0y + 6z = 3
Sous forme matricielle :
La matrice étant inversible, il y aura une unique solution, il restera plus qu'a vérifier qu'elle fonctionne aussi pour les mangues.
Donc si ça ne marche pas pour les mangues, mais que tu veux approcher le résultat au plus proche alors la oui c'est un problème d'optimisation.
L'idée pour bien poser ces problèmes c'est savoir ce que l'on veut optimiser. Ce rapprocher le plus possible de 3 oranges, 3 pommes, 3 litchis, 1 mangue c'est très vague : se rapprocher dans le sens la moyenne des écarts est le plus bas possible ou on veut qu'il y en ai le maximum avec le nombre exact (par exemple).
Dans le deuxième cas, c'est la résolution qu'il y a au-dessus. Pour la moyenne, si on appelle a, b, c, d, les quantités de pommes, d'oranges, le litchis et de mangues, on veut minimiser P = |3-a| + |3-b| + |3-c| + |1-d|
Mais on peut simplifier ce problème, on remarque que a et c imposent le nombre de panier P1 et P3, donc impose d car il n'y a ps e mangues dans le panier P2.
Donc on peut compléter le nombre d'oranges avec le panier P2. Donc l'écart que l'on peut avoir entre le nombre d'orange voulu et obtenu est de 0.
Donc P = |3-a| + |3-c| + |1-d|
De plus d dépendant de a et c, on obtient finalement une fonction à deux variables dont on veut trouver le minimum.
En trouvant le minimum, on trouve le nombre de panier P1 et P3 et il suffit de completer avec le nombre de panier P2 pour avoir exactement 3 oranges
par Matnul » 02 Jan 2015, 16:43
Bonjour Eriadrim,
Merci beaucoup pour votre réponse qui me fait vraiment avancer. En effet, il s'agit d'un problème des moindres carrés (on a à la fin des fractions de fruits et les mangues sont nécessaires :).
Mes connaissances datent tellement que je ne suis pas sûr de pouvoir résoudre le modèle simplifié: P (a,b) t.q. ? ensuite il faut minimiser ?
Cependant, il se pourrait que certains fruits n'imposent plus le nombre de panier dans l'avenir, donc je désire construire un modèle non simplifié, comment poser cela dans Excel svp?
En vous remerciant encore !
Merci beaucoup pour votre réponse qui me fait vraiment avancer. En effet, il s'agit d'un problème des moindres carrés (on a à la fin des fractions de fruits et les mangues sont nécessaires :).
Mes connaissances datent tellement que je ne suis pas sûr de pouvoir résoudre le modèle simplifié: P (a,b) t.q. ? ensuite il faut minimiser ?
Cependant, il se pourrait que certains fruits n'imposent plus le nombre de panier dans l'avenir, donc je désire construire un modèle non simplifié, comment poser cela dans Excel svp?
En vous remerciant encore !
par Cliffe » 02 Jan 2015, 18:56
le titre n'est pas correct, c'est du non linéaire ^^
Si je fait le calcul sous excel, on obtient le vecteur solution :
et qui donne dans le panier final :
Si je fait le calcul sous excel, on obtient le vecteur solution :
- Code: Tout sélectionner
0,569568755129229
0,112449145676142
0,333604556458704
et qui donne dans le panier final :
- Code: Tout sélectionner
3,014646054 pommes
3,000000000 oranges
2,855980472 litchis
1,285598048 mangues
par Matnul » 02 Jan 2015, 19:25
Bonjour Cliffe,
Merci pour votre réponse, mais comment avez-vous fait ? Cela est-il compliqué à "programmer" dans Excel ?
finalement pourquoi est-ce non linéaire ?
Merci d'avance.
Merci pour votre réponse, mais comment avez-vous fait ? Cela est-il compliqué à "programmer" dans Excel ?
finalement pourquoi est-ce non linéaire ?
Merci d'avance.
par Cliffe » 02 Jan 2015, 19:31
Si je traduit sous forme de vecteur on a : P = a.P1 + b.P2 + c.P3
avec P le pannier final et (a, b, c) les inconnues.
De plus :
P1 = (5, 3, 3/2, 1/2)
P2 = (0, 10, 0, 0)
P3 = (1/2, 1/2, 6, 3)
On a donc : P = (5a + c/2, 3a + 10b + c/2, 3/2a + 6c, a/2 + 3c)
On cherche (a, b, c) tel que P soit le plus proche de (3, 3, 3, 1) par les moindres carrés.
On minimise alors z = (5a + c/2 - 3)^2 + (3a + 10b + c/2 - 3)^2 + (3/2a + 6c - 3)^2 + (a/2 + 3c - 1)^2.
On résout avec excel ^^ :
[CENTER]
[/CENTER]
avec P le pannier final et (a, b, c) les inconnues.
De plus :
P1 = (5, 3, 3/2, 1/2)
P2 = (0, 10, 0, 0)
P3 = (1/2, 1/2, 6, 3)
On a donc : P = (5a + c/2, 3a + 10b + c/2, 3/2a + 6c, a/2 + 3c)
On cherche (a, b, c) tel que P soit le plus proche de (3, 3, 3, 1) par les moindres carrés.
On minimise alors z = (5a + c/2 - 3)^2 + (3a + 10b + c/2 - 3)^2 + (3/2a + 6c - 3)^2 + (a/2 + 3c - 1)^2.
On résout avec excel ^^ :
[CENTER]
[/CENTER]par Cliffe » 02 Jan 2015, 19:33
Si je traduit sous forme de vecteurs on a : P = a.P1 + b.P2 + c.P3
avec P le pannier final et (a, b, c) les inconnues.
De plus :
P1 = (5, 3, 3/2, 1/2)
P2 = (0, 10, 0, 0)
P3 = (1/2, 1/2, 6, 3)
On a donc : P = (5a + c/2, 3a + 10b + c/2, 3/2a + 6c, a/2 + 3c)
On cherche (a, b, c) tel que P soit le plus proche de (3, 3, 3, 1) par les moindres carrés.
On minimise alors z = (5a + c/2 - 3)^2 + (3a + 10b + c/2 - 3)^2 + (3/2a + 6c - 3)^2 + (a/2 + 3c - 1)^2.
On résout avec excel ^^ :
[CENTER]
[/CENTER]
avec P le pannier final et (a, b, c) les inconnues.
De plus :
P1 = (5, 3, 3/2, 1/2)
P2 = (0, 10, 0, 0)
P3 = (1/2, 1/2, 6, 3)
On a donc : P = (5a + c/2, 3a + 10b + c/2, 3/2a + 6c, a/2 + 3c)
On cherche (a, b, c) tel que P soit le plus proche de (3, 3, 3, 1) par les moindres carrés.
On minimise alors z = (5a + c/2 - 3)^2 + (3a + 10b + c/2 - 3)^2 + (3/2a + 6c - 3)^2 + (a/2 + 3c - 1)^2.
On résout avec excel ^^ :
[CENTER]
[/CENTER]par Matnul » 03 Jan 2015, 12:22
Génial, Cliffe. J'ai pu reproduire sur mon tableur.
Une petite question me turlupine néanmoins. Est-ce que Eriadrim s'est trompé dans sa solution ? Il parle de minimiser P = |3-a| ... alors que dans la solution de Cliffe, il me semble que l'on minimise a-3 (au carré) ?
En vous remerciant tous encore !
Une petite question me turlupine néanmoins. Est-ce que Eriadrim s'est trompé dans sa solution ? Il parle de minimiser P = |3-a| ... alors que dans la solution de Cliffe, il me semble que l'on minimise a-3 (au carré) ?
En vous remerciant tous encore !
par Cliffe » 03 Jan 2015, 13:12
Tout dépend ce que tu veux minimiser.
Tu as un vecteur P = (p1, p2, p3, p4) qui doit s'approcher au mieux du vecteur S = (3, 3, 3, 1), dans l'idéal on veux avoir P = S ou encore X = P - S = 0 (vecteur nul).
Pour avoir X "proche" du vecteur nul on peut prendre, par exemple :
____- la norme :
et donc on minimise 
____- la différence de chaque composantes :
____- la différence de chaque composantes au carrée (moindre carrée) :
____- etc ...
Dans tous les cas, minimiser z revient à obtenir P = S.
L'avantage des moindres carrés est de minimiser les grandes erreurs.
exemple : on préféré avoir deux erreurs de 5 (5^2 + 5^2 = 50) plutôt que une erreur de 10 (10^2 = 100)
PS : tu m'a demandé pk ce n'est pas linéaire. Les fonction racine carrée, valeur absolue et x^2 ne sont pas linéaire.
Tu as un vecteur P = (p1, p2, p3, p4) qui doit s'approcher au mieux du vecteur S = (3, 3, 3, 1), dans l'idéal on veux avoir P = S ou encore X = P - S = 0 (vecteur nul).
Pour avoir X "proche" du vecteur nul on peut prendre, par exemple :
____- la norme :
____- la différence de chaque composantes :
____- la différence de chaque composantes au carrée (moindre carrée) :
____- etc ...
Dans tous les cas, minimiser z revient à obtenir P = S.
L'avantage des moindres carrés est de minimiser les grandes erreurs.
exemple : on préféré avoir deux erreurs de 5 (5^2 + 5^2 = 50) plutôt que une erreur de 10 (10^2 = 100)
PS : tu m'a demandé pk ce n'est pas linéaire. Les fonction racine carrée, valeur absolue et x^2 ne sont pas linéaire.
10 messages
- Page 1 sur 1
Qui est en ligne
Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 35 invités
Tu pars déja ?
Fais toi aider gratuitement sur Maths-forum !
Créé un compte en 1 minute et pose ta question dans le forum ;-)
Identification
Pas encore inscrit ?
Ou identifiez-vous :