un ami m'a demandé de lui faire un programme qui ferait la chose suivante :
on veut mélanger N produits qui se distinguent par leurs taux en alcools, sucres, acidité etc.. de manière à répondre à un cahier des charges donnant les taux maximums et minimums de chacune de ces propriétés, et optionnellement une valeur cible dont il serait bon de se rapprocher.
Mon programme doit donc donner le pourcentage de chaque produit à introduire afin de répondre au mieux à la problématique.
ce que j'ai fait :
- une simple fonction récursive avec un for qui part du pourcentage de liquide déjà introduit jusqu'à 0, de manière à tester toutes les possibilités. Par exemple pour N = 3 on testera [100%, 0%, 0%], [99%, 0%, 1%], [99%, 1%, 0%], ... , [0%, 0%, 100%]
- un test de continuité, qui stop la récursivité si la solution partielle courante ne peut aboutir à un résultat cohérent (si en ne rajoutant que de l'eau on est encore trop concentré, ou si en ne rajoutant que le produit le plus concentré on est encore trop dilué)
Ce petit test de continuité m'a permis pour N=5 de passer de 1-2h de calcul à 3-4 min, donc j'étais plutôt content de moi, mais en faisant le test avec N=10 (le logiciel doit pouvoir gérer entre 5 et 10 produits) j'ai vu que ça pouvait prendre au moins un mois de calcul, ce qui n'est bien sur pas envisageable.
Je crois qu'il y a en tout N-1 parmi 200+N-1 possibilités (je marche par pas de 0.5) ce qui fait un gros morceau pour N=10 !
Je voulais donc savoir si il existe des méthodes générales pour améliorer mon algo, ou si vous avez une idée qui pourrait me faire avancer un peu, parce que je vais finir par manquer de feuilles de brouillon à force de réfléchir ;)
Cette action est irreversible, confirmez la suppression du commentaire ?
Signaler le commentaire
Veuillez sélectionner un problème
Nudité
Violence
Harcèlement
Fraude
Vente illégale
Discours haineux
Terrorisme
Autre
Olivier Miakinen
Bonjour,
Le 20/07/2012 16:27, borbag a écrit :
un ami m'a demandé de lui faire un programme qui ferait la chose suivante :
on veut mélanger N produits qui se distinguent par leurs taux en alcools, sucres, acidité etc.. de manière à répondre à un cahier des charges donnant les taux maximums et minimums de chacune de ces propriétés, et optionnellement une valeur cible dont il serait bon de se rapprocher.
Mon programme doit donc donner le pourcentage de chaque produit à introduire afin de répondre au mieux à la problématique.
[...]
Je suis persuadé que cet algorithme existe déjà, mais tu n'es pas dans le bon groupe (fr.comp.lang.c) pour poser la question. Ce serait mieux dans fr.comp.algorithmes ou fr.sci.maths.
Malheureusement, comme tu passes par une passerelle web-news de GNT média pour accéder aux groupes usenet, tu ne sauras pas forcément trouver le bon site web correspondant à ces groupes plus appropriés.
Si tu as déjà accès à usenet avec un vrai lecteur de nouvelles (que ce soit MesNews, Thunderbird, ou même Outlook Express), alors c'est le plus simple. Si non, tu peux au moins passer par Google groupes. C'est une solution très laide, mais bon, ça devrait fonctionner.
Ce groupe : https://groups.google.com/forum/?hl=fr&fromgroups#!forum/fr.comp.lang.c
Ceux que je te conseille : https://groups.google.com/forum/?hl=fr&fromgroups#!forum/fr.comp.algorithmes https://groups.google.com/forum/?hl=fr&fromgroups#!forum/fr.sci.maths
Cordialement, -- Olivier Miakinen
Bonjour,
Le 20/07/2012 16:27, borbag a écrit :
un ami m'a demandé de lui faire un programme qui ferait la chose suivante :
on veut mélanger N produits qui se distinguent par leurs taux en alcools,
sucres, acidité etc.. de manière à répondre à un cahier des charges donnant les
taux maximums et minimums de chacune de ces propriétés, et optionnellement une
valeur cible dont il serait bon de se rapprocher.
Mon programme doit donc donner le pourcentage de chaque produit à introduire
afin de répondre au mieux à la problématique.
[...]
Je suis persuadé que cet algorithme existe déjà, mais tu n'es pas dans
le bon groupe (fr.comp.lang.c) pour poser la question. Ce serait mieux
dans fr.comp.algorithmes ou fr.sci.maths.
Malheureusement, comme tu passes par une passerelle web-news de GNT
média pour accéder aux groupes usenet, tu ne sauras pas forcément
trouver le bon site web correspondant à ces groupes plus appropriés.
Si tu as déjà accès à usenet avec un vrai lecteur de nouvelles (que
ce soit MesNews, Thunderbird, ou même Outlook Express), alors c'est
le plus simple. Si non, tu peux au moins passer par Google groupes.
C'est une solution très laide, mais bon, ça devrait fonctionner.
Ce groupe :
https://groups.google.com/forum/?hl=fr&fromgroups#!forum/fr.comp.lang.c
Ceux que je te conseille :
https://groups.google.com/forum/?hl=fr&fromgroups#!forum/fr.comp.algorithmes
https://groups.google.com/forum/?hl=fr&fromgroups#!forum/fr.sci.maths
un ami m'a demandé de lui faire un programme qui ferait la chose suivante :
on veut mélanger N produits qui se distinguent par leurs taux en alcools, sucres, acidité etc.. de manière à répondre à un cahier des charges donnant les taux maximums et minimums de chacune de ces propriétés, et optionnellement une valeur cible dont il serait bon de se rapprocher.
Mon programme doit donc donner le pourcentage de chaque produit à introduire afin de répondre au mieux à la problématique.
[...]
Je suis persuadé que cet algorithme existe déjà, mais tu n'es pas dans le bon groupe (fr.comp.lang.c) pour poser la question. Ce serait mieux dans fr.comp.algorithmes ou fr.sci.maths.
Malheureusement, comme tu passes par une passerelle web-news de GNT média pour accéder aux groupes usenet, tu ne sauras pas forcément trouver le bon site web correspondant à ces groupes plus appropriés.
Si tu as déjà accès à usenet avec un vrai lecteur de nouvelles (que ce soit MesNews, Thunderbird, ou même Outlook Express), alors c'est le plus simple. Si non, tu peux au moins passer par Google groupes. C'est une solution très laide, mais bon, ça devrait fonctionner.
Ce groupe : https://groups.google.com/forum/?hl=fr&fromgroups#!forum/fr.comp.lang.c
Ceux que je te conseille : https://groups.google.com/forum/?hl=fr&fromgroups#!forum/fr.comp.algorithmes https://groups.google.com/forum/?hl=fr&fromgroups#!forum/fr.sci.maths
Cordialement, -- Olivier Miakinen
Marc
borbag wrote:
un ami m'a demandé de lui faire un programme qui ferait la chose suivante :
on veut mélanger N produits qui se distinguent par leurs taux en alcools, sucres, acidité etc.. de manière à répondre à un cahier des charges donnant les taux maximums et minimums de chacune de ces propriétés, et optionnellement une valeur cible dont il serait bon de se rapprocher.
Mon programme doit donc donner le pourcentage de chaque produit à introduire afin de répondre au mieux à la problématique.
[...]
Je voulais donc savoir si il existe des méthodes générales pour améliorer mon algo, ou si vous avez une idée qui pourrait me faire avancer un peu, parce que je vais finir par manquer de feuilles de brouillon à force de réfléchir ;)
un ami m'a demandé de lui faire un programme qui ferait la chose suivante :
on veut mélanger N produits qui se distinguent par leurs taux en alcools,
sucres, acidité etc.. de manière à répondre à un cahier des charges donnant les
taux maximums et minimums de chacune de ces propriétés, et optionnellement une
valeur cible dont il serait bon de se rapprocher.
Mon programme doit donc donner le pourcentage de chaque produit à introduire
afin de répondre au mieux à la problématique.
[...]
Je voulais donc savoir si il existe des méthodes générales pour améliorer mon
algo, ou si vous avez une idée qui pourrait me faire avancer un peu, parce que
je vais finir par manquer de feuilles de brouillon à force de réfléchir ;)
un ami m'a demandé de lui faire un programme qui ferait la chose suivante :
on veut mélanger N produits qui se distinguent par leurs taux en alcools, sucres, acidité etc.. de manière à répondre à un cahier des charges donnant les taux maximums et minimums de chacune de ces propriétés, et optionnellement une valeur cible dont il serait bon de se rapprocher.
Mon programme doit donc donner le pourcentage de chaque produit à introduire afin de répondre au mieux à la problématique.
[...]
Je voulais donc savoir si il existe des méthodes générales pour améliorer mon algo, ou si vous avez une idée qui pourrait me faire avancer un peu, parce que je vais finir par manquer de feuilles de brouillon à force de réfléchir ;)
un ami m'a demandé de lui faire un programme qui ferait la chose suivante :
on veut mélanger N produits qui se distinguent par leurs taux en alcools, sucres, acidité etc.. de manière à répondre à un cahier des charges donnant les taux maximums et minimums de chacune de ces propriétés, et optionnellement une valeur cible dont il serait bon de se rapprocher.
Si je reformule, tu as M dimensions (Alcool, Sucre, Acide => M=3), et un ensemble de N vecteurs avec leurs caractéristiques entre 0 et 1.
Et du cherches N coefficients C1,...CN tels que V = (Sum_i Ci * Vi) / Sum_i Ci se rapproche le plus d'un objectif donné.
Si c'est ça le problème, ça me semble un problème d'espace vectoriel assez simple: il faudrait identifier une base, et faire une projection de l'objectif sur la base.
Je ne me souviens plus comment on fait, mais je me souviens avoir fait ça vers BAC+1 / BAC+2.
Marc Boyer -- À mesure que les inégalités regressent, les attentes se renforcent. François Dubet
Le 20-07-2012, borbag <nospam_remi.delassus@gmail.com.invalid> a écrit :
Bonjour à tous.
un ami m'a demandé de lui faire un programme qui ferait la chose suivante :
on veut mélanger N produits qui se distinguent par leurs taux en alcools,
sucres, acidité etc.. de manière à répondre à un cahier des charges donnant les
taux maximums et minimums de chacune de ces propriétés, et optionnellement une
valeur cible dont il serait bon de se rapprocher.
Si je reformule, tu as M dimensions (Alcool, Sucre, Acide => M=3),
et un ensemble de N vecteurs avec leurs caractéristiques entre 0 et 1.
Et du cherches N coefficients C1,...CN tels que
V = (Sum_i Ci * Vi) / Sum_i Ci
se rapproche le plus d'un objectif donné.
Si c'est ça le problème, ça me semble un problème d'espace vectoriel
assez simple: il faudrait identifier une base, et faire une projection
de l'objectif sur la base.
Je ne me souviens plus comment on fait, mais je me souviens avoir fait
ça vers BAC+1 / BAC+2.
Marc Boyer
--
À mesure que les inégalités regressent, les attentes se renforcent.
François Dubet
un ami m'a demandé de lui faire un programme qui ferait la chose suivante :
on veut mélanger N produits qui se distinguent par leurs taux en alcools, sucres, acidité etc.. de manière à répondre à un cahier des charges donnant les taux maximums et minimums de chacune de ces propriétés, et optionnellement une valeur cible dont il serait bon de se rapprocher.
Si je reformule, tu as M dimensions (Alcool, Sucre, Acide => M=3), et un ensemble de N vecteurs avec leurs caractéristiques entre 0 et 1.
Et du cherches N coefficients C1,...CN tels que V = (Sum_i Ci * Vi) / Sum_i Ci se rapproche le plus d'un objectif donné.
Si c'est ça le problème, ça me semble un problème d'espace vectoriel assez simple: il faudrait identifier une base, et faire une projection de l'objectif sur la base.
Je ne me souviens plus comment on fait, mais je me souviens avoir fait ça vers BAC+1 / BAC+2.
Marc Boyer -- À mesure que les inégalités regressent, les attentes se renforcent. François Dubet
Si c'est ça le problème, ça me semble un problème d'espace vectoriel assez simple: il faudrait identifier une base, et faire une projection de l'objectif sur la base.
Je ne me souviens plus comment on fait, mais je me souviens avoir fait ça vers BAC+1 / BAC+2.
"Recherche operationnelle" "Methode du simplexe".
In article <jubtfs$sr0$1@news.cict.fr>,
Marc Boyer <Marc.Boyer@cert.onera.fr.invalid> wrote:
Si c'est ça le problème, ça me semble un problème d'espace vectoriel
assez simple: il faudrait identifier une base, et faire une projection
de l'objectif sur la base.
Je ne me souviens plus comment on fait, mais je me souviens avoir fait
ça vers BAC+1 / BAC+2.
Si c'est ça le problème, ça me semble un problème d'espace vectoriel assez simple: il faudrait identifier une base, et faire une projection de l'objectif sur la base.
Je ne me souviens plus comment on fait, mais je me souviens avoir fait ça vers BAC+1 / BAC+2.
"Recherche operationnelle" "Methode du simplexe".
Samuel DEVULDER
Le 20/07/2012 16:27, borbag a écrit :
Bonjour à tous.
un ami m'a demandé de lui faire un programme qui ferait la chose suivante :
on veut mélanger N produits qui se distinguent par leurs taux en alcools, sucres, acidité etc.. de manière à répondre à un cahier des charges donnant les taux maximums et minimums de chacune de ces propriétés, et optionnellement une valeur cible dont il serait bon de se rapprocher.
Quelles sont les relations entre les pourcentages de chacun des produits (p_i) et la valeur cible?
Si la valeur cible est une fonction linéaire des p_i et que les contraintes sont elles mêmes linéaires (style 0.2*p1 - 0.3*p2 >= 0.4 0.5*p1+0.7*p2 <= 0.6 ..) alors la solution réside dans ce qu'on appelle la *programmation lineaire*. Bien que le mot "programmation" soit présent, cela n'a rien à voir avec ce que l'on entend habituellement dans ce newsgroup (sens plus économique que technologique il me semble).
Les programmation linéaires et quadratiques sont très générales car on peut représenter beaucoup de problèmes d'optimisation de variables continues avec elles. En outre les algorithmes de résolution sont bien connus (simplexe, méthode par points intérieurs), assez anciens, très étudiés mathématiquement, très performants et implémentés de façon efficaces dans pleins de langages. Ces techniques sont très utilisées dans l'industrie (chimie, optimisation de ressources dans la production industrielle en général, etc.) Quelques exemples de petits problèmes sont présents ici:
Mais en pratique dans l'industrie on l'utilise pour pour optimiser des équations avec plusieurs centaines de milliers de variables et contraintes et même bien plus que la mémoire de l'ordinateur ne saurait contenir (méthodes out-of-core).
Du coup si tu n'as que 10 produits, c'est vraiment une tache triviale pour ces algorithmes, et un petit outil comme lpsolve
http://lpsolve.sourceforge.net/5.5/
devrait facilement en venir à bout. C'est même réalisable à la main sans trop de soucis (élimination de fourier-motzkin; méthode des tableaux).
sam.
Le 20/07/2012 16:27, borbag a écrit :
Bonjour à tous.
un ami m'a demandé de lui faire un programme qui ferait la chose suivante :
on veut mélanger N produits qui se distinguent par leurs taux en alcools,
sucres, acidité etc.. de manière à répondre à un cahier des charges donnant les
taux maximums et minimums de chacune de ces propriétés, et optionnellement une
valeur cible dont il serait bon de se rapprocher.
Quelles sont les relations entre les pourcentages de chacun des
produits (p_i) et la valeur cible?
Si la valeur cible est une fonction linéaire des p_i et que les
contraintes sont elles mêmes linéaires (style 0.2*p1 - 0.3*p2 >= 0.4
0.5*p1+0.7*p2 <= 0.6 ..) alors la solution réside dans ce qu'on
appelle la *programmation lineaire*. Bien que le mot "programmation"
soit présent, cela n'a rien à voir avec ce que l'on entend
habituellement dans ce newsgroup (sens plus économique que
technologique il me semble).
Les programmation linéaires et quadratiques sont très générales car
on peut représenter beaucoup de problèmes d'optimisation de variables
continues avec elles. En outre les algorithmes de résolution sont
bien connus (simplexe, méthode par points intérieurs), assez anciens,
très étudiés mathématiquement, très performants et implémentés de façon
efficaces dans pleins de langages. Ces techniques sont très utilisées
dans l'industrie (chimie, optimisation de ressources dans la production
industrielle en général, etc.) Quelques exemples de petits problèmes
sont présents ici:
Mais en pratique dans l'industrie on l'utilise pour pour optimiser des
équations avec plusieurs centaines de milliers de variables et
contraintes et même bien plus que la mémoire de l'ordinateur ne saurait
contenir (méthodes out-of-core).
Du coup si tu n'as que 10 produits, c'est vraiment une tache triviale
pour ces algorithmes, et un petit outil comme lpsolve
http://lpsolve.sourceforge.net/5.5/
devrait facilement en venir à bout. C'est même réalisable à la main
sans trop de soucis (élimination de fourier-motzkin; méthode des
tableaux).
un ami m'a demandé de lui faire un programme qui ferait la chose suivante :
on veut mélanger N produits qui se distinguent par leurs taux en alcools, sucres, acidité etc.. de manière à répondre à un cahier des charges donnant les taux maximums et minimums de chacune de ces propriétés, et optionnellement une valeur cible dont il serait bon de se rapprocher.
Quelles sont les relations entre les pourcentages de chacun des produits (p_i) et la valeur cible?
Si la valeur cible est une fonction linéaire des p_i et que les contraintes sont elles mêmes linéaires (style 0.2*p1 - 0.3*p2 >= 0.4 0.5*p1+0.7*p2 <= 0.6 ..) alors la solution réside dans ce qu'on appelle la *programmation lineaire*. Bien que le mot "programmation" soit présent, cela n'a rien à voir avec ce que l'on entend habituellement dans ce newsgroup (sens plus économique que technologique il me semble).
Les programmation linéaires et quadratiques sont très générales car on peut représenter beaucoup de problèmes d'optimisation de variables continues avec elles. En outre les algorithmes de résolution sont bien connus (simplexe, méthode par points intérieurs), assez anciens, très étudiés mathématiquement, très performants et implémentés de façon efficaces dans pleins de langages. Ces techniques sont très utilisées dans l'industrie (chimie, optimisation de ressources dans la production industrielle en général, etc.) Quelques exemples de petits problèmes sont présents ici:
Mais en pratique dans l'industrie on l'utilise pour pour optimiser des équations avec plusieurs centaines de milliers de variables et contraintes et même bien plus que la mémoire de l'ordinateur ne saurait contenir (méthodes out-of-core).
Du coup si tu n'as que 10 produits, c'est vraiment une tache triviale pour ces algorithmes, et un petit outil comme lpsolve
http://lpsolve.sourceforge.net/5.5/
devrait facilement en venir à bout. C'est même réalisable à la main sans trop de soucis (élimination de fourier-motzkin; méthode des tableaux).
sam.
Samuel DEVULDER
Le 20/07/2012 21:12, Samuel DEVULDER a écrit :
Les programmation linéaires et quadratiques sont très générales car on peut représenter beaucoup de problèmes d'optimisation de variables continues avec elles.
Par exemple, si dans ton cas, en appelant p1 p2 p3 les ratios (pourcentages) des différents produits chimiques et que du veuille que
0.5*p1 - 0.3*p2 + 0.7*p2
soit le plus proche de A = 0.8 sachant que les ratios sont soumis aux contraintes suivantes:
p1+0.7*p2-p3 >= 0.4 p1 - p2 <= 0.6 p2 - p1 >= 0.1
0<=p1<=1, 0<=p2<=1, 0<=p3<=1
Cela revient à minimiser o1 + o2
sachant que 0.5*p1 - 0.3*p2 + 0.7*p3 - A - o1 + o2 = 0 A = 0.8
p1 + 0.7*p2 - p3 - B = 0.4 p1 - p2 + C = 0.6 -p1 + p2 - D = 0.1 p1 + E = 1 p2 + F = 1 p3 + G = 1
p1, p2, p3, o1, o2, A, B, C, D, E, F, G >= 0
C'est un beau petit programme linéaire. Le truc c'est que l'erreur entre la valeur atteinte et l'objectif est exprimée comme la soustraction de deux nombres positifs. Donc plus la somme de ces deux deux nombres positif est petite, plus l'erreur l'est en valeur absolue.
sam.
Le 20/07/2012 21:12, Samuel DEVULDER a écrit :
Les programmation linéaires et quadratiques sont très générales car
on peut représenter beaucoup de problèmes d'optimisation de variables
continues avec elles.
Par exemple, si dans ton cas, en appelant p1 p2 p3 les ratios
(pourcentages) des différents produits chimiques et que du veuille que
0.5*p1 - 0.3*p2 + 0.7*p2
soit le plus proche de A = 0.8 sachant que les ratios sont soumis aux
contraintes suivantes:
p1+0.7*p2-p3 >= 0.4
p1 - p2 <= 0.6
p2 - p1 >= 0.1
0<=p1<=1, 0<=p2<=1, 0<=p3<=1
Cela revient à
minimiser o1 + o2
sachant que
0.5*p1 - 0.3*p2 + 0.7*p3 - A - o1 + o2 = 0
A = 0.8
p1 + 0.7*p2 - p3 - B = 0.4
p1 - p2 + C = 0.6
-p1 + p2 - D = 0.1
p1 + E = 1
p2 + F = 1
p3 + G = 1
p1, p2, p3, o1, o2, A, B, C, D, E, F, G >= 0
C'est un beau petit programme linéaire. Le truc c'est que l'erreur
entre la valeur atteinte et l'objectif est exprimée comme la
soustraction de deux nombres positifs. Donc plus la somme de ces deux
deux nombres positif est petite, plus l'erreur l'est en valeur
absolue.
Les programmation linéaires et quadratiques sont très générales car on peut représenter beaucoup de problèmes d'optimisation de variables continues avec elles.
Par exemple, si dans ton cas, en appelant p1 p2 p3 les ratios (pourcentages) des différents produits chimiques et que du veuille que
0.5*p1 - 0.3*p2 + 0.7*p2
soit le plus proche de A = 0.8 sachant que les ratios sont soumis aux contraintes suivantes:
p1+0.7*p2-p3 >= 0.4 p1 - p2 <= 0.6 p2 - p1 >= 0.1
0<=p1<=1, 0<=p2<=1, 0<=p3<=1
Cela revient à minimiser o1 + o2
sachant que 0.5*p1 - 0.3*p2 + 0.7*p3 - A - o1 + o2 = 0 A = 0.8
p1 + 0.7*p2 - p3 - B = 0.4 p1 - p2 + C = 0.6 -p1 + p2 - D = 0.1 p1 + E = 1 p2 + F = 1 p3 + G = 1
p1, p2, p3, o1, o2, A, B, C, D, E, F, G >= 0
C'est un beau petit programme linéaire. Le truc c'est que l'erreur entre la valeur atteinte et l'objectif est exprimée comme la soustraction de deux nombres positifs. Donc plus la somme de ces deux deux nombres positif est petite, plus l'erreur l'est en valeur absolue.
sam.
borbag
Le vendredi 20 Juillet 2012 à 16:25 par borbag :
Bonjour à tous.
un ami m'a demandé de lui faire un programme qui ferait la chose suivante :
on veut mélanger N produits qui se distinguent par leurs taux en alcools, sucres, acidité etc.. de manière à répondre à un cahier des charges donnant les taux maximums et minimums de chacune de ces propriétés, et optionnellement une valeur cible dont il serait bon de se rapprocher.
Mon programme doit donc donner le pourcentage de chaque produit à introduire afin de répondre au mieux à la problématique.
ce que j'ai fait : - une simple fonction récursive avec un for qui part du pourcentage de liquide déjà introduit jusqu'à 0, de manière à tester toutes les possibilités. Par exemple pour N = 3 on testera [100%, 0%, 0%], [99%, 0%, 1%], [99%, 1%, 0%], ... , [0%, 0%, 100%] - un test de continuité, qui stop la récursivité si la solution partielle courante ne peut aboutir à un résultat cohérent (si en ne rajoutant que de l'eau on est encore trop concentré, ou si en ne rajoutant que le produit le plus concentré on est encore trop dilué)
Ce petit test de continuité m'a permis pour N=5 de passer de 1-2h de calcul à 3-4 min, donc j'étais plutôt content de moi, mais en faisant le test avec N (le logiciel doit pouvoir gérer entre 5 et 10 produits) j'ai vu que ça pouvait prendre au moins un mois de calcul, ce qui n'est bien sur pas envisageable. Je crois qu'il y a en tout N-1 parmi 200+N-1 possibilités (je marche par pas de 0.5) ce qui fait un gros morceau pour N !
Je voulais donc savoir si il existe des méthodes générales pour améliorer mon algo, ou si vous avez une idée qui pourrait me faire avancer un peu, parce que je vais finir par manquer de feuilles de brouillon à force de réfléchir ;)
Merci de m'avoir lu. Cordialement, Borbag
@Olivier Miakinen : Je ne savais pas que c'était un newsGroupe, merci de m'avoir averti, je ne trouvais pas d'onglet algo, j'avais bien vu que mon problème n'était pas propre au C ^^ Je vais de ce pas poser ma question chez les algorithmi[ciens ?], merci.
@Marc Boyer : ta représentation vectorielle m'a l'air intéressante à utiliser, et très pertinente, cependant je ne sais pas du tout manier ce genre de choses !
@Samuel Devulder : avec les pourcentages de chaque produit je fais une simple somme pondérée des Sucres, devant etre supérieur aux sucres mini, inférieur au sucre maxi, et se rapprocher de la valeur cible si elle existe ; idem avec le TAV, les tanins, l'acidité, l'alcool etc.. Il n'y a donc pas de contrainte entre les différents produits.
Le vendredi 20 Juillet 2012 à 16:25 par borbag :
Bonjour à tous.
un ami m'a demandé de lui faire un programme qui ferait la chose
suivante :
on veut mélanger N produits qui se distinguent par leurs taux en
alcools, sucres, acidité etc.. de manière à
répondre à un cahier des charges donnant les taux maximums et
minimums de chacune de ces propriétés, et optionnellement une
valeur cible dont il serait bon de se rapprocher.
Mon programme doit donc donner le pourcentage de chaque produit à
introduire afin de répondre au mieux à la problématique.
ce que j'ai fait :
- une simple fonction récursive avec un for qui part du pourcentage de
liquide déjà introduit jusqu'à 0, de manière
à tester toutes les possibilités. Par exemple pour N = 3 on
testera [100%, 0%, 0%], [99%, 0%, 1%], [99%, 1%, 0%], ... , [0%, 0%, 100%]
- un test de continuité, qui stop la récursivité si la
solution partielle courante ne peut aboutir à un résultat
cohérent (si en ne rajoutant que de l'eau on est encore trop
concentré, ou si en ne rajoutant que le produit le plus concentré
on est encore trop dilué)
Ce petit test de continuité m'a permis pour N=5 de passer de 1-2h de
calcul à 3-4 min, donc j'étais plutôt content de moi, mais
en faisant le test avec N=10 (le logiciel doit pouvoir gérer entre 5 et
10 produits) j'ai vu que ça pouvait prendre au moins un mois de calcul,
ce qui n'est bien sur pas envisageable.
Je crois qu'il y a en tout N-1 parmi 200+N-1 possibilités (je marche par
pas de 0.5) ce qui fait un gros morceau pour N=10 !
Je voulais donc savoir si il existe des méthodes générales
pour améliorer mon algo, ou si vous avez une idée qui pourrait me
faire avancer un peu, parce que je vais finir par manquer de feuilles de
brouillon à force de réfléchir ;)
Merci de m'avoir lu.
Cordialement,
Borbag
@Olivier Miakinen :
Je ne savais pas que c'était un newsGroupe, merci de m'avoir averti, je ne trouvais pas d'onglet algo, j'avais bien vu que mon problème n'était pas propre au C ^^ Je vais de ce pas poser ma question chez les algorithmi[ciens ?], merci.
@Marc Boyer : ta représentation vectorielle m'a l'air intéressante à utiliser, et très pertinente, cependant je ne sais pas du tout manier ce genre de choses !
@Samuel Devulder : avec les pourcentages de chaque produit je fais une simple somme pondérée des Sucres, devant etre supérieur aux sucres mini, inférieur au sucre maxi, et se rapprocher de la valeur cible si elle existe ; idem avec le TAV, les tanins, l'acidité, l'alcool etc.. Il n'y a donc pas de contrainte entre les différents produits.
un ami m'a demandé de lui faire un programme qui ferait la chose suivante :
on veut mélanger N produits qui se distinguent par leurs taux en alcools, sucres, acidité etc.. de manière à répondre à un cahier des charges donnant les taux maximums et minimums de chacune de ces propriétés, et optionnellement une valeur cible dont il serait bon de se rapprocher.
Mon programme doit donc donner le pourcentage de chaque produit à introduire afin de répondre au mieux à la problématique.
ce que j'ai fait : - une simple fonction récursive avec un for qui part du pourcentage de liquide déjà introduit jusqu'à 0, de manière à tester toutes les possibilités. Par exemple pour N = 3 on testera [100%, 0%, 0%], [99%, 0%, 1%], [99%, 1%, 0%], ... , [0%, 0%, 100%] - un test de continuité, qui stop la récursivité si la solution partielle courante ne peut aboutir à un résultat cohérent (si en ne rajoutant que de l'eau on est encore trop concentré, ou si en ne rajoutant que le produit le plus concentré on est encore trop dilué)
Ce petit test de continuité m'a permis pour N=5 de passer de 1-2h de calcul à 3-4 min, donc j'étais plutôt content de moi, mais en faisant le test avec N (le logiciel doit pouvoir gérer entre 5 et 10 produits) j'ai vu que ça pouvait prendre au moins un mois de calcul, ce qui n'est bien sur pas envisageable. Je crois qu'il y a en tout N-1 parmi 200+N-1 possibilités (je marche par pas de 0.5) ce qui fait un gros morceau pour N !
Je voulais donc savoir si il existe des méthodes générales pour améliorer mon algo, ou si vous avez une idée qui pourrait me faire avancer un peu, parce que je vais finir par manquer de feuilles de brouillon à force de réfléchir ;)
Merci de m'avoir lu. Cordialement, Borbag
@Olivier Miakinen : Je ne savais pas que c'était un newsGroupe, merci de m'avoir averti, je ne trouvais pas d'onglet algo, j'avais bien vu que mon problème n'était pas propre au C ^^ Je vais de ce pas poser ma question chez les algorithmi[ciens ?], merci.
@Marc Boyer : ta représentation vectorielle m'a l'air intéressante à utiliser, et très pertinente, cependant je ne sais pas du tout manier ce genre de choses !
@Samuel Devulder : avec les pourcentages de chaque produit je fais une simple somme pondérée des Sucres, devant etre supérieur aux sucres mini, inférieur au sucre maxi, et se rapprocher de la valeur cible si elle existe ; idem avec le TAV, les tanins, l'acidité, l'alcool etc.. Il n'y a donc pas de contrainte entre les différents produits.
