Cas concret

[gwlegion]

bonjour.

voici mon probleme du moment

soit un couple ayant tout les deux des tickets restaurants ( A et B) de valeurs differents
Il me faut determiner combien je dois donner de A et de B pour approcher au plus pret le montant a payer.

apres, je compte en faire un programme... mais ca je me debrouillerais.

[zygomatique]

salut

pb classique de pa + qb aussi proche de m (montant) avec p et q entiers naturels ....

[gwlegion]

Bonjour.

merci d'avoir reformule mon probleme... mais j'ai toujours aucune idee sur la facon de le resoudre...

[zygomatique]

le problème est le mot approcher ...

ou encore on veut que |m - (pa + qb)| soit minimal

l'informatique permet alors de résoudre ce problème ... en testant tous les cas ... convenables

p et q sont positifs

il existe donc un pmax et un qmax tels que m < pmax * a et m < qmax * b

...

[gwlegion]

Du coup, si a et b sont connus, j'ai tout interretba me faire une matrice avec tout les resultats possibles et faire une recherche dedans...

Apres tout, m depassera rarement 200 et surement jamais 500...

Ca me fais moins de 100 valeurs en x et y dans ma matrice...

[Razes]

Parfois tu peux trouver plusieurs solutions , voir aussi si d'autres contraintes sont imposées.

Par exemples des classes d’élèves et leurs encadrants vont au restaurant, on ne vas pas prendre que des tickets élèves, peut être aussi des tickets adultes?

[gwlegion]

Je n'aurais pas ce genres de contraintes dans mon cas precis... par contre, je peux avoir plusieurs resultats pertinnents....

[zygomatique]

je ne pense pas qu'une matrice de tous les résultats soit le plus efficace ...

par contre on peut réfléchir un peu plus loin ...

a et b sont connus et on veut payer au plus près de m (par valeur inférieure ? supérieure ?)

déjà si d divise a et b alors d divise toute combinaison linéaire de a et b et donc en particulier pa + qb est multiple du pgcd de a et b (à développer ...)


ensuite même tout simplement je raisonnerais plutôt sur l'algorithme suivant :

je suppose que a < b et soit b = aq + r la division euclidienne de b par a donc aq < b < (a + 1)q (donc je suppose b non multiple de a)

il existe un entier p tel que : pb < m < (p + 1)b (rem si m multiple de b c'est évidemment fini)

et je pose d_g = m - pb (distance gauche) et d_d = (p + 1)b - m (distance droite)

à partir de là je me rapproche de m en enlevant des b et en rajoutant des a

(p - 1)b + qa < pb < m < qa + pb < (p + 1)b (bien entendu je teste que c'est vrai

ensuite à gauche j'ajoute un maximum de a tout en restant inférieur m
et à droite j'enlève un maximum de a tout en restant supérieur ainsi on obtient des entiers q' et q"

(p - 1)b + q'a < m < pb + (q'' + 1)a

à chaque fois que j'obtiens l'inégalité "maximale" mg < m < md je la garde en mémoire en conservant aussi les nombres d'_g = m - mg et md - m = d'_d (distance à m)

puis je recommence avec cette inégalité "max" : j'enlève un b de chaque côté que je remplace par une certaine quantité de a "au mieux" pour essayer d'avoir une inégalité du type :

(p - 2)b + q'''a < m < (p - 1)b + (q"'' + 1)a

ensuite je compare les nouvelles distances gauche et droite obtenu et je compare avec la configuration précédente gardées en mémoire : à chaque fois que j'obtiens mieux (soit à gauche, soit à droite, soit les deux je conserve la nouvelle configuration max)

puis je recommence ...

[gwlegion]

ho la ... j'ai pas tout compris a ton explication ... mais je crois comprendre qu'on s'approche de quelque chose que je peux tranformer en algo ...
du coup, je vais reprendre point par point


-a et b sont connus et on veut payer au plus près de m (par valeur inférieure ? supérieure ?)
les deux valeures peuvent etre interessantes... il est parfoit plus facile de donner un ticket de plus et perdre quelques centimes ... surtout si on a pas la monaie !

-déjà si d divise a et b alors d divise toute combinaison linéaire de a et b et donc en particulier pa + qb est multiple du pgcd de a et b (à développer ...)
en l'etat, je suis d'accord ...mais j'ai un doute sur ce que tu apelle "toute combinaison linéaire"...

-je suppose que a < b et soit b = aq + r la division euclidienne de b par a donc aq < b < (a + 1)q (donc je suppose b non multiple de a)
si a=b, y'a plus de probleme ... c'est une simple division avec reste
si a -NEQ b, alors soit a>b soit a<b ... prennons n'importe lequel des deux, je peux inverser les deux valeurs a loisir.
Dans mon cas, a n'est pas multiple de b, et il y a peu de chances que ca arrive...
le coup de la division euclidienne, je le comprends pas du tout ...

-il existe un entier p tel que : pb < m < (p + 1)b (rem si m multiple de b c'est évidemment fini)
du coup, si je fais la meme chose avec a, j'ai les valeurs max pour p et q ...

-et je pose d_g = m - pb (distance gauche) et d_d = (p + 1)b - m (distance droite)
-à partir de là je me rapproche de m en enlevant des b et en rajoutant des a
-(p - 1)b + qa < pb < m < qa + pb < (p + 1)b (bien entendu je teste que c'est vrai
-ensuite à gauche j'ajoute un maximum de a tout en restant inférieur m
-et à droite j'enlève un maximum de a tout en restant supérieur ainsi on obtient des entiers q' et q"
-(p - 1)b + q'a < m < pb + (q'' + 1)a
-à chaque fois que j'obtiens l'inégalité "maximale" mg < m < md je la garde en mémoire en conservant aussi les nombres -d'_g = m - mg et md - m = d'_d (distance à m)
-puis je recommence avec cette inégalité "max" : j'enlève un b de chaque côté que je remplace par une certaine quantité de -a "au mieux" pour essayer d'avoir une inégalité du type :
-(p - 2)b + q'''a < m < (p - 1)b + (q"'' + 1)a
-ensuite je compare les nouvelles distances gauche et droite obtenu et je compare avec la configuration précédente gardées -en mémoire : à chaque fois que j'obtiens mieux (soit à gauche, soit à droite, soit les deux je conserve la nouvelle -configuration max)
-puis je recommence ...

je pense qu'avec ca, j'ai un algo qui peut donner quelque chose, quels que soient a et b ...

est il important que a>b ?

donc je calcul le nombre max de B , j'enregistre m-qb et m-(q+1)b.
Ensuite j'enleve 1 b, je rajoute 1 a et je refais mon calul m-qb+pa et m-(q+1)b+pa et j'enregistre les resultats si ils sont inferieurs aux precendents ...
puis je recommence jusqu'a ce qu'il n'y ai plus de B ...
C'est bien ca ?

[fatal_error]

variante:

soit M l'objectif, tu veut trouver a et b tq
f(a,b) = abs(M-aA+bB)
soit minimale.

ca peut se reduire en PLNE (programmation linéaire en nombre entier) sous la formulation suivante:

(d'apres par ex http://cedric.cnam.fr/~porumbed/rcp104/main.pdf)
minimiser la fonction objective :
f(x) = y
(x est le vecteur [a,b])
sous contrainte:
M - (x(1)A+x(2)B)<= y
(-M +x(1)A+x(2)B)<= y
x(1)>=0
x(2)>=0

[gwlegion]

autant la derniere solution proposée, je comprenais les grandes lignes, et je pouvais echafauder un algo qui tienne la route, mais la, je saurais meme pas le resoudre a la main ...

Decidement, j'me dis que j'ai vraiement un train de retard en math ...

[gwlegion]

@zygomatique:

ta resolution n'est pas tout a fait juste :
en prenant a<b (j'ai compris l'importance de ce fait), on calcule le nombre de b max, et on demare l'algo (en admetant que m n'est pas multiple de a ou b)

le probleme c'est qu'a un moment le reste sera suppieur a a, il faut tester a chaque boucle et en rajouter 1 si necessaire ...
avec quelques ajustements, je pense pouvoir pondre un truc qui marche...

[Razes]

bonjour.

voici mon probleme du moment

soit un couple ayant tout les deux des tickets restaurants ( A et B) de valeurs differents
Il me faut determiner combien je dois donner de A et de B pour approcher au plus pret le montant a payer.

apres, je compte en faire un programme... mais ca je me debrouillerais.

Tu cherche une solution ou toutes les solutions? Car tu parles de remplir une matrice avec les solutions, c'est pour quoi faire?

[gwlegion]

Pour faire simple, je compte en faire un programme... pour savoir combien moi et ma chérie devons donner de ticket pour payer le resto...
je ferais ça sur mon téléphone (sur un emulateur ti 89)
ce qu'il me manque c'est une façon compatible d'aborder le problème...

la matrice de toute les solution possibles etais une facon d'aborder le problème... pas la plus élégante je l'avoue

[fatal_error]

@Razes
je présume que c'est pour ne pas rater la meilleure solution (le couple (a,b) de tickets tq la somme se rapproche le plus du montant à payer).

@gwlegion
ben ici sortir la PLNE c'est ptet overkill, mais bon, ca épargne qq cheveux...

en utilisant octave/gplk

Code: Tout sélectionner

%https://www.gnu.org/software/octave/doc/v4.0.0/Linear-Programming.html
goal = 100;
ticketA = 3;
ticketB = 8;
c = [0,0,1]'; %tickets value are respectively 3€ and 8€
A = [
    -ticketA, -ticketB, -1;
    ticketA, ticketB, -1
];
b = [-goal, goal]';
lb = [0, 0, 0]';
ub = [];
ctype = "UU";
vartype = "III";
s = 1;

param.msglev = 1;
param.itlim = 100;

[xmin, fmin, status, extra] = glpk (c, A, b, lb, ub, ctype, vartype, s, param);
disp('nb tickets A'), disp(xmin(1))
disp('nb tickets B'), disp(xmin(2))
disp('amount'), disp(xmin(1)*ticketA+xmin(2)*ticketB)



output:

Code: Tout sélectionner

nb tickets A
 4
nb tickets B
 11
amount
 100


[gwlegion]

j'ai redigé ca ... il reste a le programmer !

Code: Tout sélectionner

tickets A et B
montant M

verif A<B
   sinon inverser A et B
   
verif mod(M/A) -NEQ 0
   sinon A multiple de M implique solution sur A/M => goto solution A
verif mod(M/B) -NEQ 0
   sinon B multiple de M implique solution sur B/M => goto solution B
   
Calcul max B
   MB=int(M/B)

tB = MB         ::valeurs de test pour nA et nB
tA = 0
S = 100000      ::rest maxi ...
routine:
   if tB -NEQ 0            :: tant que tB est diff de 0, on continue
      then
         if m-((tB*B)+(tA*A)) -GT S         
            then
               if m-((tB*B)+(tA*A)) -GT A      ::si le reste est supp a a, on rajoute un a
                  then tA = tA+1
                     goto routine
                  else   
                     tA = tA+1
                     tB = tB-1
                     goto routine
               END
            else                        ::si le restant des valeurs test est inf a l'essai le plus
               S = m-((tB*B)+(tA*A))         :: concluant, on sauvegarde les valeurs et on passe au test
               nA = tA                     :: suivant
               nB = tB                     
               tA = tA+1
               tB = tB-1
               goto routine
         END
               
      else                              ::=> tB = 0 tout les test on ete fais
      echo resultats
   END
   

[Razes]

@Razes
je présume que c'est pour ne pas rater la meilleure solution (le couple (a,b) de tickets tq la somme se rapproche le plus du montant à payer).

Merci pour ta réponse, je sais ça . Mais lors de la résolution, on peut trouver plusieurs solutions, bien sur on peut retenir juste la 1ère solution. Ceci dépends du besoin de gwlegion. Ce que tu propose est intéressant, d'autant plus je ne savais qu'il existait un solveur GNU online.

@gwlegion
Tu programme en quel langage? Tu cherche une solution ou toutes les solutions?

[gwlegion]

je cherche une solution ...

comme dit precedement, je vais programmer sur un emulateur TI89 ... ca se raproche du basic

[Razes]

Voici le code à tester sur TI89:

Code: Tout sélectionner

Prompt A,B,M    “Prendre A>B”
E(M/A)→K      “Nombre maxi de A“
M→R                 “Initialisation Reste, Temporaire“
0→I                 “Quantité de A, Temporaire“
0→J                 “Quantité de B, Temporaire “
0→QA         “Quantité de A, stocké“
0→QB         “Quantité de B, stocké“
M→RMINI      “Initialisation Reste minimum, stocké”

While I≤K
          E(M/B)→J
          M-J*B→R
          If R< RMINI
          Then
               I→QA
               J→QB
               R→RMINI
          End
          I+1→I
          M-B→M
End
Disp QA
Disp QB
Disp R

il se peut qu'il y est des erreurs car je viens juste de découvrir la programmation de la TI89

[gwlegion]

bonne idée de prendre M en tant que R mini.C'est moins arbitraire que ce que j'avais fait.
sinon c'est grosso modo ce que j'avais en tete ...

par contre j'ai des doutes au niveau mathematique (la syntaxe j'en fais mon affaire) :
E(M/B)→J (ou est passé A ? en admetant que E soit la partie entierre de ton resulat)
M-B→M (pourquoi ?)


je vais faire ca dans les jours a venir. Le programme fini vous interessera ?