Discussion :

[kululu]

Bonjour et bonne année 2011 à tout le forum

J'expose directement mon problème :

Le but est de retourner le résultat le moins couteux pour un nombre de jour et une distance donnée

J'ai 3 paramètres
_le prix
_un nombre de jours associé à une distance
_et le prix au km supplémentaire

Résumé avec exemple

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
 
Une personne veut louer pour 4 jours et parcourir 1200km
 
Les tarifs sont:
50e -> pour 1jour et 100km -> 1e km/sup
80e -> pour 2jours et 150km -> 0,95 km/sup
350e -> pour 5jours et 500km -> 0,90 km/sup
 
Quel sera la combinaison la plus avantageuse pour le client?

C'est juste un exemple je ne souhaite pas que l'on me le résolve mais juste savoir quel algo je dois utiliser

J'avais pensé au "problème de sac à dos" mais le problème c'est que cet algo ne me donnera la combinaison égal (avec de la chance) ou strictement inférieur à la demande du client (on cherche à satisfaire totalement la demande du client au risque de lui proposer plus de jours ou de km mais toujours le plus compétitif)

Merci pour votre aide

[prgasp77]

Bonjour,
si tu n'as qu'un faible nombre de "menus", le plus simple reste de calculer pour un client donné les différents tarifs pour chacun de ces "menus" et de lui facturé le plus avantageux.

Cordialement,

[ToTo13]

si tu n'as qu'un faible nombre de "menus", le plus simple reste de calculer pour un client donné les différents tarifs pour chacun de ces "menus" et de lui facturé le plus avantageux.

C'est la version exhaustive de la recherche des solutions. Comme c'est marqué, cela ne fonctionne que pour les "petits" problèmes.
Sinon il faut se tourner vers algorithmes d'optimisation comme les méthodes Tabou et de Recuit Simulé.

[kululu]

Merci pour vos réponses
En effet c' est juste un exemple que j' ai cité et donc mon algo doit pouvoir fonctionner avec n tarif (n tendant vers l'infini )

je sais pas si avec la méthode du simplex je pourrais m' en sortir?

[ToTo13]

je sais pas si avec la méthode du simplex je pourrais m' en sortir?

Mmm... dans ce cas il me semble que les méthodes d'optimisation que j'ai cité sont spécialement adaptées.

[kululu]

Mmm... dans ce cas il me semble que les méthodes d'optimisation que j'ai cité sont spécialement adaptées.

Je me suis renseigné un peu sur l'algo de recherche taboue et le recuit, le "grand défaut" pour mon utilisation, c'est la condition d'arrêt, je ne la connais pas en avance (forcément je la cherche :p ) et mon but est de proposer nécessairement au client l'offre la plus intéressante (pas celle qui s'en rapproche le plus )

[250rgv]

le "grand défaut" pour mon utilisation, c'est la condition d'arrêt, je ne la connais pas en avance (forcément je la cherche :p ) et mon but est de proposer nécessairement au client l'offre la plus intéressante (pas celle qui s'en rapproche le plus )

Ben tu peut au minimum, limiter à un nombre d'itérations et/ou une durée de calcul.

[Nebulix]

Chaque calcul est tellement simple que tu peux en faire des millions sans constater de délai (en moins d'1sec). Pourquoi se compliquer la vie ?

[ToTo13]

S'il te faut LA meilleure solution, alors tu dois tester toutes les combinaisons. Dans le meilleur des cas tu pourras en partie élaguer l'arbre de recherche en fonction des contraintes de ton problème.
Sinon, c'est les méthodes que je propose.
Il faut savoir que dans des problèmes très complexes, on donne souvent la meilleure des solutions trouvée, mais sans certitude que ce soit la meilleure.
Donc on lance plusieurs fois l'algorithme si nécessaire et on règle les paramètres pour que la méthode cherche longtemps.

[kululu]

Merci à tous pour vos réponses ;D

Donc je continue à cogiter en testant différents truc

Pour l'énumération de toutes les solutions en effet c'est une des solution mais pas envisageable si on a une liste énorme de tarif (en plus mon algo doit être facilement évolutif...)

Donc je m'étais dit :
Je prends l'algo du sac à dos et pour les km manquants -si il y en a- je les ajoutes avec le meilleur tarif "km/sup" de tous les tarifs que le client aura choisi (je sais pas si je suis clair) j'aurais donc forcément la meilleure solution,
Mon raisonnement est-il correct?

[Nebulix]

... si on a une liste énorme de tarifs ...

Comment les rentres-tu dans ton ordinateur ?

[kululu]

Comment les rentres-tu dans ton ordinateur ?

C'est une bd alimentée depuis des années, je pense pas qu'il y en ai des milliards mais entre 1000~2000 tarifs c'est probable

[Nebulix]

C'est une bd alimentée depuis des années, je pense pas qu'il y en ai des milliards mais entre 1000~2000 tarifs c'est probable

Donc un calcul bête devrait prendre environ 1 milliseconde. C'est grave ?

[Nebulix]

Précision : Je me suis toujours placé dans l'hypothèse que tu n'appliquais qu'un seul tarif pour toute la durée de la location.

[prgasp77]

Donc un calcul bête devrait prendre environ 1 milliseconde. C'est grave ?

En fait, à partir d'une certaine précision voulue (qui est assez faible), la méthode russe est la meilleur. En effet, le calcul des tarifs pour chaque "menu" n'est que très peu plus lourd (2-3 fois) que le simple parcourt de tous les "menus".

De plus, sauf si tu es dans un cas embarqué, le temps de calcul total sera négligeable par rapport à l'extraction dans la base de données. Mais si tu veux t'amuser un peu parce que tu en as marre de faire tout le temps la même chose avec <ton_langage_favori>, tu devrais pouvoir créer une fonction dans ton SGDB qui te retourne automatiquement le meilleur menu .

Enjoy!

[kululu]

La méthode Russe? je connaissais l'algorithme Hongrois je vais me renseigner

Mais ce que j'ai dit est erroné? Le fait de résoudre un problème de sac a dos avec l'addition des km sup stratégiquement

@Nebulix : a priori le client aura le droit de combiner plusieurs tarifs, il peut prendre par exemple 3 fois le "tarif 1" et un "tarif3" les km manquant (si il y en a) seront additionnés avec le km/sup le plus compétitif entre le tarif 3 et 1

[prgasp77]

La méthode Russe? je connaissais l'algorithme Hongrois je vais me renseigner

c'est un surnom pour la bruteforce / la solution bourine / ... en rapport avec la technologie russe qui est souvent la plus pragmatique (le crayon dans l'espace ou les moteurs des chars sovietiques étant les seuls à supporter le carburant russe lors de la seconde guerre mondiale, etc).

Mais ce que j'ai dit est erroné? Le fait de résoudre un problème de sac a dos avec l'addition des km sup stratégiquement

@Nebulix : a priori le client aura le droit de combiner plusieurs tarifs, il peut prendre par exemple 3 fois le "tarif 1" et un "tarif3" les km manquant (si il y en a) seront additionnés avec le km/sup le plus compétitif entre le tarif 3 et 1

Ha ! ça complique complètement le problème en effet. Et forcément, le sac à dos semble tout de suite plus justifié.