recherche aide pour une mise en équation

[divervince]

bonjour, je ne sais pas si je suis au bon endroit mais je bute sur un sujet de mise en équation, je suis sur que ce n'est pas sorcier mais je n'arrive pas a y arriver, certainement que je ne prend pas les choses par le bon bout...


je recherche comment calculer à partir d'un code de 5 données sous la forme (A ; B ; C ; D ;E ) qui sont des entiers positifs, le nombre d'objet qu'il faut
pour ce faire j'ai 13 possibilités qui correspondent chacune à 1 ou 2 données de (A ; B ; C ; D ;E )
A B C D E
a 0 0 0 1 0
b 0 0 0 0 1
c 1 0 0 0 0
d 0 1 0 0 0
e 0 0 1 0 0
f 0 1 0 0 0
g 0 0 2 0 0
h 1 0 0 0 2
i 0 4 0 0 0
j 4 0 0 0 0
k 0 0 1 0 2
l 0 0 0 5 3
m 3 0 5 0 0

j'arrive pas à trouver comment mettre en équation le truc pour pouvoir trouver l'ensemble des solution à la suite de (A ; B ; C ; D ;E )

d'avance merci pour vos futures réponses

ex pour le code (0-18-11-17-10) = 17a + 10b + 18d + 11e.

pour ce qui est des variable qui ne sont que dans 1 seule partie de (A ; B ; C ; D ;E ) c'est simple la ou je sèche c'est comment faire quand c'est dans 2... (et ainsi trouver les équations totales)


d'avance merci pour vos remarques...

j’espère que je suis bien dans la bonne partie
-----

[ansset]

ex pour le code (0-18-11-17-10) = 17a + 10b + 18d + 11e.

tu es sur que c'est une bonne traduction d'une partie du code, parce qu'il peut y en avoir plusieurs !
et pour moi , je ne vois pas d'équation !? il n'y a de = qcq chose nul part.
cordialement.

[divervince]

merci d'avoir répondu

pour l'exemple (0-18-11-17-10) => 17a + 10b + 18d + 11e., c'est une des possibilités de réponse mais il y en a d'autre.

je vais donner le contexte ca aidera peut etre...

en fait le problème que j'ai c'est de trouver l'ensemble des possibilité pour pouvoir choisir la solution la plus rentable en fonction d'autre paramètres qui sont dépendant des possibilités

dans un jeu sur internet (les royaumes renaissants) il y a des maladies, qui sont représenté par un code sous la forme (A ; B ; C ; D ;E ).
pour la soigner il faut fabriquer une essence curative qui doit avoir exactement ce code, et ce a partir des 13 potions de bases qui ont chacune des caractéristiques dans 1 ou 2 partie du code je les ai résumé dans le tableau:
les potions :
A B C D E
a 0 0 0 1 0
b 0 0 0 0 1
c 1 0 0 0 0
d 0 1 0 0 0
e 0 0 1 0 0
f 0 1 0 0 0
g 0 0 2 0 0
h 1 0 0 0 2
i 0 4 0 0 0
j 4 0 0 0 0
k 0 0 1 0 2
l 0 0 0 5 3
m 3 0 5 0 0

donc comme j'ai dit il y a plusieurs possibilité pour arriver au même code, mais chaque potion a des prix mini max et d'achat moyen différents, il faut donc arriver a trouver pour une liste de prix donnés, la solution optimum.

j'ai déjà fait un tableau sur excel qui permet de choisir la solution la plus adapté au cas, mais j'ai besoin d'entrer l'ensemble des possibilité qui répondent au code de la maladie sous peine de pouvoir passer a travers de la solution optimum. et de plus actuellement, je recherche chaque possibilité a la main par tâtonnement (ce qui n'a rien de scientifique et n'écarte pas la possibilité de loupé)
arriver a mettre en équation me permettrai de ne pas louper de possibilité et de gagner du temps avec les futures maladie.

voila je sais pas si ca avance...

encore merci a ceux qui m'aideront a avancer sur ce projet...

[divervince]

pour l'exemple (0-18-11-17-10) => 17a + 10b + 18d + 11e., c'est une des possibilités de réponse mais il y en a d'autre.
Citation : potion 1
18 d +11 e + 17 a + 10 b
Citation : potion 2
2 a + 1 b + 1 e 2 f + 4 i + 3l
Citation : potion 3
2 a + 1 b + 11 e + 2f + 4 i + 3l


rajout (dsl j'ai pas pu éditer le message)

[A voir en vidéo sur Futura]

[ansset]

les coûts sont a b , c, d ... ?

[divervince]

j'ai mis en A B C D E (les majuscules) les différentes constituantes du codes de la maladie

j'ai mis en minuscule de a à m les potions de bases qui permette par addition de former le code de la maladie

ex si la maladie est (1 -0- 3- 1-0) on peut le résoudre par (normalement ce ne sont que les 2 possibilités)
1c + 1e + 1g + 1a
1c + 3e + 1a

les prix en question sont des variables qui changent constamment et qui sont introduit dans mes calculs qu'une fois que je sais le nombre de chaque potion nécessaire car il est nécessaire pour le calculer d'avoir le prix de la plante ainsi que le tarif que l'on décide pour une journée de travail

[acx01b]

wiki/Branch_and_cut

(ce n'est pas de ton niveau mais je crois que c'est la solution générale à ton problème)

ce qui est de ton niveau par contre c'est de trouver un programme C++ ou python ou java qui le fasse, et de l'utiliser (via excel ou le langage que tu préfères)

[divervince]

acx01b, merci pour votre message,

Par contre je ne suis pas sûr de bien comprendre le "branch and cut", dans tout ce que j'ai lut sur le sujet, c'est pour trouver une optimisation dans la relation entre 2 schémas de production par exemple

or ce que je recherche c'est trouver l'ensemble des solutions permettant de répondre à une condition (ou série de condition, je ne suis pas familier avec les termes mathématiques) et non pas la solution optimisé.

ou alors j'ai rien compris au truc...

[acx01b]

tu as des vecteurs de base :
a 0 0 0 1 0
b 0 0 0 0 1
c 1 0 0 0 0
d 0 1 0 0 0
e 0 0 1 0 0
f 0 1 0 0 0
g 0 0 2 0 0
h 1 0 0 0 2
i 0 4 0 0 0
j 4 0 0 0 0
k 0 0 1 0 2
l 0 0 0 5 3
m 3 0 5 0 0

chacun a un prix,
tu cherches à trouver la combinaison linéaire à coefficient entiers positifs de ces vecteurs qui donne
[n,o,p,r,s] et dont le coût soit minimum

pour moi c'est exactement un programme linéaire à coefficients entiers

après si tu sais à l'avance les [n,o,p,r,s] possibles qu'on te demandera de générer avec tes vecteurs de base,
tu peux pré-calculer pour chaque [n,o,p,r,s] les combinaisons linéaires à coefficient entiers positifs possibles (en écrivant un programme qui le fasse ?)

[divervince]

après si tu sais à l'avance les [n,o,p,r,s] possibles qu'on te demandera de générer avec tes vecteurs de base,
tu peux pré-calculer pour chaque [n,o,p,r,s] les combinaisons linéaires à coefficient entiers positifs possibles (en écrivant un programme qui le fasse ?)

c'est dans ce sens que je vais aller fouiller... merci

[acx01b]

il faut que tu précises les données du problème (pour estimer le temps de calcul et la taille mémoire)
combien de "maladies" différentes, quel est l'ordre de grandeur des coefficients

[divervince]

pour ce qui est des maladies, on connais le code.

actuellement il y a 3 maladie qui on était découvertes,
La grippe alexandrine ( 4-16-4-7-17 )
La maladie de Nagazudi ( 0-18-11-9-8 )
La Glairette BMG ( 0-18-11-17-10 )

mais je ne comprend pas en quoi le nb de maladie est un facteur vu que la maladie est connue à l'avance, seul la composition peut être différente... et c'est ce que je recherche savoir l'ensemble des possibilités je ne sais pas si ca aide...

[ansset]

en fait, c'est un jeu ?
comment est définie une maladie au départ ?
par un de ces codes possibles, mais qu'il faut optimiser ?

[divervince]

oui c'est pour un jeu (les royaumes renaissants)

la maladie est fixé par les administrateur et implanté dans le jeu sous la forme d'un code (A ; B ; C ; D ;E ) avec chaque lettre qui correspond a :
1er chiffre = Fièvre ( A )
2ème chiffre = Fatigue ( B )
3ème chiffre = Troubles respiratoires ( C )
4ème chiffre = Courbatures (D )
5ème chiffre = Maux de tête ( E )


pour pouvoir soigner la maladie, il faut préparer une essence a l'aide de potion issus de plante (pour simplifier je vous mets les plantes necessaire pour fabriquer les potions) qui permettent de soigner une partie ou 2 de la maladie. c'est en combinant X plantes que l'on arrive a faire l'essence curative.

brin de marjolaine => a => 0 0 0 1 0
fleurs de partenelle=> b=>0 0 0 0 1
feuille de tilleul=> c=>1 0 0 0 0
branche de celeri =>d=>0 1 0 0 0
brin de lavande=> e=>0 0 1 0 0
brin de romarin=> f=>0 1 0 0 0
branche de thym =>g=>g 0 0 2 0 0
morceau d'ecorce de saule blanc=> h=> 1 0 0 0 2
brin d'angelique =>i=> 0 4 0 0 0
fleurs de bourrache=> j=>4 0 0 0 0
feuilles de menthe=> k=>0 0 1 0 2
fleurs de camomille=> l=> 0 0 0 5 3
baie de sureau noir=> m=>3 0 5 0 0

pour "une" maladie en particulier, il existe qu'un code sous la forme (A ; B ; C ; D ;E ) que l'on connais, par contre on peut faire n'importe quel potion qui correspond a ce code.
comme j'ai mis en exemple si la maladie est (1 -0- 3- 1-0) on peut le résoudre par (normalement ce ne sont que les 2 possibilités)
potion 1) 1c + 1e + 1g + 1a
potion 2) 1c + 3e + 1a

dans le cas de cette maladie qui n'existe pas mais simple à gérer au niveaux des possibilités,on voit par exemple que dans ce cas il faudrait faire la potion 1 car elle n'utilise que 4 "potion de bases) et ce serai vrai si il n'y avais pas d'autre contrainte comme le fait que chaque plantes à des valeurs d'achat différentes ( a à e prix de 1 a 5,95; f,g,h de 5 a 10,95, i,j,k de 7 a 12.95 et l et m de 20 a 25.95) et que pour transformer une plante en potion de base, il faut 1 journée de travail pour 20 plante max par jour (donc encore un salaire de 15 a 25 en fonction des joueurs).
toutes ces variables je sais les calculer une fois que j'ai les composition des potions qu'il faut trouver mais c'est bien sur les compositions que je bloque...

[acx01b]

tu détailles des trucs qui n'ont aucun intérêt mathématique

3 maladies avec somme des composantes < 60, 14 vecteurs de base dont certains ont des 1,
ça doit aller pour l'algorithme récursif naïf je pense

en gros tu dois choisir un nombre entre 1 et 60 pour le vecteur 1,
puis un nombre entre 1 et 60 pour le vecteur 2 (c'est une boucle for)
etc.
à chaque étape tu as fais la somme partielle
-si une des composantes est déjà trop grande pour le vecteur cible, tu reviens en arrière
- si toutes les composantes sont bonnes : tu as trouvé une combinaison, tu l'affiches
- sinon tu continues avec le vecteur suivant (appel récursif)

si tu ne comprends rien à ce que je dis ce n'est pas grave, apprends à programmer (récursivité, combinaisons avec répétitions)

note : pour une fois le langage prolog pourrait être adapté à ce problème

[acx01b]

une grosse optimisation (si l'algo est trop lent) serait de travailler composante par composante (tout en gardant toutes les contraintes) plutôt que vecteur par vecteur,
vu que la matrice des vecteurs est très sparse

[divervince]

je ne cherche pas a avoir UNE possibilité mais L'ENSEMBLE des possibilités.

si on avait pas les possibilités h, k, l, m, je saurais faire car ça serai en math comment résoudre :
A = c + 4j
B = d + f +4i
C = e + 2g
D = a
E = b

or ce qui me pose pb c'est comment intégrer les autres qui sont dans 2 "lettre majuscules" je suis sûr que je me prend la tete pour rien et que la réponse est super simple mais j'arrive pas à la voir...

[ansset]

pardon,
mais tu cherches A,B,C..en fct de a,b,c,...
ou l'inverse qui correspond à tes premiers messages.?

[divervince]

je recherche l'ensemble des possibilité a,b,c,d,[...] m qui correspondent a un code (A,B,C,D,E) que je connais... et comment ecrire mathématiquement la relation entre les 2...

et ce qui me pose pb plus particulierement c'est comment mettre en équation les 4 "minuscules" qui correcpondent a 2 partie de (A,B,C,D,E),

je suis dsl si je me suis mal exprimé dans mes messages mais il me semble que c'est ce que je demande depuis le début...

[ansset]

oui au début,
mais c'est ton dernier mess
A=
B= ... qui m'a fait douter.
en fait ce n'est pas simple.
A fait intervenir ( c,j,h,m)
B ( f/d ou i) ( f et d identique mais peut être pas en prix par exemple )
C( m,e,g,k)
D(a,l)
E(h,k,l,b)
donc seul B est isolé
sont liées
A et E
A et C
C et E
D et E
il faut donc construire un arbre
en commençant par B
les seules solutions sont pour obtenir kB ( k1*(f ou d)+(k2/4)*i)
il n'y a pas une infinité de possibilité et tu élimines déjà B et aussi les composant f,d, et

ensuite la branche peut commencer par voir les possibilités pour D qui n'interfère qu'avec E ( via a et l )
pour chaque possibilité tu dois voir les hypothèses possibles sur les autres composants.

[acx01b]

ansset c'est en gros l'algo que j'ai décrit, donc on est d'accord.
je n'ai pas le courage d'essayer de le faire à la main (pas sûr que ça soit faisable ?), et ça me parait plus intéressant pour notre ami qu'il apprenne à le programmer.

[ansset]

je suis d'accord.
de toute façon le raisonnement est un "algo" en lui même.
très enrichissant à faire d'ailleurs.
cordialement.

[divervince]

merci pour vos réponses, je pense que je vais le faire comme j'ai fait jusque la c'est a dire trouver les solutions par tâtonnement avec les solutions les plus simples...

en tout cas merci de vous etres exprimer sur le sujet

ps je comprend mieux pourquoi j'y arrivait pas je ne cherchait pas du bon coté en voulant m'acharner a mettre en équation un truc impossible...

[ansset]

si tes nombres initiaux ne sont pas trop grand ( en particulier pour D ) alors on peux réduire le nb de solutions.
la combinatoire augmente très vite avec la hauteur des doses voulues (A,B,C,D,E)
il n'y a que B qui soit assez simple à résoudre.

[divervince]

comme ca je dirai de 1 a 20...

je suis en train de construire tout les arbres de possibilité pour A, B, C, D, E de manière indépendante, ce qui me permet d'avoir toutes les solutions par recoupement je pense pour ce qui est de 0-0-0-0-0 a 20-20-20-20-20 ce qui sera suffisant j'espère...

j'ai trouvé pour
A:1172 possibilités dif
B: 540
les autres sont en cours...

[acx01b]

supposons qu'on a 4 vecteurs :
[0,1,1]
[2,0,1]
[1,2,2]
[0,3,0]

et qu'on veuille trouver une combinaison linéaire à coefficients entier positifs qui donne [18,15,14]


alors ce code prolog

sont_dans_interval(a,b,c,d,A,B,C) :-vA is 2*b + c is, vB is a + 2*c + 3*d, vC is a+b+2*c is,
                                         vA >= 0, vB >=0, vC =< 0, vA =< C, vB =< B, vC =< C
combinaison(a,b,c,d,A,B,C) :- 2*b + c is A, a + 2*c + 3*d is B, a+b+2*c is C, print([a,b,c,d])
combinaison(a,b,c,d,A,B,C) :- sont_dans_interval(a,b,c,d,A,B,C), a_plus_1 is a + 1, 
                                         combinaison(a_plus_1,b,c,d)
combinaison(a,b,c,d,A,B,C) :- sont_dans_interval(a,b,c,d,A,B,C), b_plus_1 is b + 1, 
                                         combinaison(a,b_plus_1,c,d)
combinaison(a,b,c,d,A,B,C) :- sont_dans_interval(a,b,c,d,A,B,C), c_plus_1 is c + 1, 
                                         combinaison(a,b,c_plus_1,d)
combinaison(a,b,c,d,A,B,C) :- sont_dans_interval(a,b,c,d,A,B,C), d_plus_1 is d + 1, 
                                         combinaison(a,b,c,d_plus_1)

? combinaison(0,0,0,0,18,15,14)

va afficher par magie toutes les combinaisons possibles, c'est trop cool

[divervince]

je crois que je vais me mettre a étudier un peu comment ça marche, par contre est ce que je pourrais mettre le code que j'ai trouvé pour vérif? (je sais j'en demande beaucoup)

[ansset]

comme ca je dirai de 1 a 20...
............
j'ai trouvé pour
A:1172 possibilités dif
B: 540
les autres sont en cours...

je pense que tu va faire exploser ta combinatoire comme ça.
soit tu prend un algo type acx01b , soit tu suis une démarche heuristique si tes nombres ne sont pas grands.
ds ce cas.
soit A,B,C,D,E, les doses voulues.
par ailleurs f et d sont équivalents, donc tu choisi le plus favorable dès le début ( je suppose d par exemple )

le cas de B: ( ingrédient d ou i )
si B<=4 , sol Bd
si 4<=B<8 sol Bd ; i+(B-4)d
si 8<=B<12 sol Bd ; i+(B-4)*d ; 2i+(B-8)d
si 12<=B<16 sol Bd ; i+(B-4)*d ; 2i+(B-8)d ; 3i+(B-12)d
si 16<=B<20 sol Bd ; i+(B-4)*d ; 2i+(B-8)d ; 3i+(B-12)d ; 4i +(B-16)d
si B=20 sol 20d ; i+16*d ; 2i+12d ; 3i+8d ; 4i +4d ; 5i
21 possibilités mais au total, beaucoup moins quand tu as le chiffre B ( max =6 )

passons à D: ( ingrédient a ou l )
si D<=5 , sol Da
si 5<=D<10 sol Da ; l+(D-5)a ( si E>=3)
si 10<=D<15 sol Da ; l+(D-5)a ( si E>=3) ; 2l+(D-10)a ( si E>=6 )
si 15<=D<20 sol Da ; l+(D-5)a ( si E>=3) ; 2l+(D-10)a ( si E>=6 ) ; 3l+(D-15)a (si E>=9 )
si D=20 sol Da ; l+15a ( si E>=3) ; 2l+10a ( si E>=6 ) ; 3l+5a (si E>=9 ) ; 4i ( si E>=12 )
idem quand tu connais D ( max solutions =5 )

reste A,C,E ou seul un algorithme type acx01b devient nécessaire.
mais avec moins de variables et d'ingrédients.
attention le choix pour D impact le reste de E à pourvoir.

en fait j'ai écris cela pour voir à l'œil jusqu'ou on pouvait aller de manière heuristique.
cordialement à vous deux.

[ansset]

juste une question subsidiaire:
dans tes exemples ( à part le tout premier ), on est loin d'être entre 0 et 20 !!! ( voir ton post #14)
entre 0 et 5 par exemple, une démarche totalement heuristique est envisageable.
un peu plus lourdingue entre 0 et 10, mais jouable.

[divervince]

actuellement il y a 3 maladie qui on était découvertes,
La grippe alexandrine ( 4-16-4-7-17 )
La maladie de Nagazudi ( 0-18-11-9-8 )
La Glairette BMG ( 0-18-11-17-10 )

ca se sont les maladies qui existent actuellement et qui ont été découverte... donc on est bien dans la fourchette 0 - 20

de plus j'ai pris arbitrairement 0-20 comme fourchette car pour transformer les plantes en potion (qui ont les valeur des lettres en minuscules) il faut 1 journée de travail pour 20 potion max par jour (en partant du principe que 1 plante => 1 POTION)

je ne connais pas le terme heuristique, mais je pense que c'est ce que je fait actuellement, je recherche à la main des possibilités et je regarde quand c'est bon j'avance, quand j'ai une contrainte qui est fausse je reviens en arrière et je recommence avec une autre possibilité.

j'ai mis un exemple "facile" à faire en rappelant dans le poste 14 que celle ci n'existe pas encore mais est simple a faire de tete.

ex si la maladie est (1 -0- 3- 1-0) on peut le résoudre par (normalement ce ne sont que les 2 possibilités)
1c + 1e + 1g + 1a
1c + 3e + 1a