Optimisation Algo recursif

Le
borbag Hors ligne
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
Questions / Réponses high-tech
Vidéos High-Tech et Jeu Vidéo
Téléchargements
Vos réponses
Gagnez chaque mois un abonnement Premium avec GNT : Inscrivez-vous !
Trier par : date / pertinence
Olivier Miakinen
Le #24648851
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
Marc
Le #24648841
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 ;)



http://fr.wikipedia.org/wiki/Optimisation_quadratique
Marc Boyer
Le #24648891
Le 20-07-2012, 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.



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.

Genre
V1= [ 0.1 ; 0.4 ; 0.6 ]
V2= [ 0.1 ; 0.0 ; 0.1 ]
et le vecteur "eau"
V0 = [ 0 ; 0 ; 0 ]

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
espie
Le #24648981
In article Marc Boyer
Le 20-07-2012, 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.



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.

Genre
V1= [ 0.1 ; 0.4 ; 0.6 ]
V2= [ 0.1 ; 0.0 ; 0.1 ]
et le vecteur "eau"
V0 = [ 0 ; 0 ; 0 ]

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.



"Recherche operationnelle"
"Methode du simplexe".
Samuel DEVULDER
Le #24649141
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).

http://fr.wikipedia.org/wiki/Optimisation_lin%C3%A9aire

max c1*p1 + c2*p2 + c3*p3 + .... cN*pN

a11*p1 + a12*pN + ... a1N*pN <= b1
a21*p1 + a22*pN + ... a2N*pN <= b2
...
aM1*p1 + aM2*pN + ... aMN*pN <= bM

Si la fonction à optimiser est un polynôme du 2nd degré,

max c1*p1 + c2*p2 + c3*p3 + .... cN*pN
+ q11*p1*p1 + q12*p1*p2 + .. q1N*p1*pN
+ q12*p2*p2 + .. q1N*p2*pN
+ ....
+ qNN*pN*pN

alors il faut utiliser la programmation quadratique.

http://fr.wikipedia.org/wiki/Optimisation_quadratique

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:

http://cours.ensem.inpl-nancy.fr/cours-dm/graphes/Proglin.pdf

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 #24649191
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.
borbag Hors ligne
Le #24649771
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.
Publicité
Poster une réponse
Anonyme