Problème de minimisation de coût

Version imprimable

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:

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 :ccool:

07/01/2011, 14h51
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,
08/01/2011, 00h28
ToTo13

Citation:

Envoyé par prgasp77

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é.
08/01/2011, 12h11
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?
09/01/2011, 01h13
ToTo13

Citation:

Envoyé par kululu

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.
10/01/2011, 13h04
kululu

Citation:

Envoyé par ToTo13

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 :aie: )
10/01/2011, 16h46
250rgv

Citation:

Envoyé par kululu

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 :aie: )

Ben tu peut au minimum, limiter à un nombre d'itérations et/ou une durée de calcul.
10/01/2011, 18h45
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 ?
10/01/2011, 20h05
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.
12/01/2011, 10h04
kululu

Merci à tous pour vos réponses ;D

Donc je continue à cogiter :aie: 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?
12/01/2011, 14h07
Nebulix

Citation:

Envoyé par kululu

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

8O
Comment les rentres-tu dans ton ordinateur ?
13/01/2011, 10h17
kululu

Citation:

Envoyé par Nebulix

8O
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
13/01/2011, 12h42
Nebulix

Citation:

Envoyé par kululu

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 ?
13/01/2011, 18h12
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.
14/01/2011, 11h26
prgasp77

Conclusion : méthode russe !

Citation:

Envoyé par Nebulix

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!
14/01/2011, 14h48
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
14/01/2011, 18h12
prgasp77

Citation:

Envoyé par kululu

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

:D 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).

Citation:

Envoyé par kululu

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é.