Problème de livraison

[MangaII]

Bonjour,
dans le cadre d'un projet d'études, je dois réaliser un programme pour trouver le meilleur prix !
J'ai un niveau correct en math, mais là, je manque d'idée ...

Je vais essayer d'exposer le problème le plus clairement possible :

On dispose de plusieurs produits (P) et et de plusieurs fournisseurs (F) qui sont susceptibles de livrer les produits P.
Chaque fournisseur propose la totalité des produits P mais à des tarifs différents. Chaques fournisseurs facture en sus des frais de ports (différents). Mais certains fournisseurs peuvent faire des remises sur les frais de port au delà d'un certain montant !

Le but est de trouver l'option la plus avantageuse pour le client (en utilisant 1 ou plusieurs fournisseurs).

Cas concret 3 fournisseurs (F1, F2, F3) et 3 produits (P1, P2, P3):

[PHP]
. F1 F2 F3
P1 2€ 3€ 4€
P2 19€ 17€ 9€
P3 8€ 9€ 5€

F1 Port : 12€
F2 Port : 14€ gratuit à partir de 25€
F3 Port : 40€
[/PHP]

Le client choisit :
P1 x 10
P2 x 5
P3 x 2

Total chez le fournisseur 1 : 131€+12€ : 143 €
Total chez le fournisseur 2 : 133€ + 0 : 133 €
Total chez le fournisseur 3 : 95€ + 35€ : 130€

A priori, le plus intéressant est le fournisseur 3 SAUF QUE :
En prenant P2 et P3 chez F3 et P1 chez F2 on obtient :
chez F2 (P1): 10x3 (port gratuit > 25) soit 30€
chez F3 (P2+P3): 9x5 + 5x2 +35 = 90€

L'option la plus intéressante est donc celle ci pour un total de 120€

P1 serait encore moins cher chez F1 mais avec les frais de ports ca dépasse le montant chez F2

Il est donc parfois plus intéressant d'utiliser plusieurs fournisseurs pour réduire le cout au client.
Mon soucis est de faire calculer la meilleure option à l'ordinateur.
Dans le cas de 3 fournisseur et 3 produits c'est jouable.
Il faut imaginer qu'il puisse y avoir 50 produits et 25 fournisseurs avec des quantités et des prix très variables.
Le nombre de combinaisons se compte dessuite en milliards ...
Même si l'ordinateur est rapide, je ne peux pas me permettre de perdre beaucoup de temps sur ce calcul !

Quelqu'un aurait-il une solution pour calculer rapidement la meilleure option (sans tester toutes les combinaisons) ?


Merci de votre patiente !

Nicolas

[MangaII]

A priori, pas grand monde n'a d'iée ...

Je cherche si il est possible d'utiliser un algorithme de pathfinding, mais je ne suis pas sur que ce soit très applicable !
Si quelqu'un en sait quelque chose ...

Nico

[Patastronch]

Modélise ton problème avec un programme linéaire et fait un simplex.

[MangaII]

euh ... merci ... mais là, je vois pas trop comment faire çà !
Je n'ai jamais fait de simplex et pour la modélisation linéaire, je ne vois pas trop ce que ca peut donner dans ce cas de figure.

[Patastronch]

L'algorithme du simplex permet de résoudre efficacement (bien qu'il ne soit pas polynomial) les programmes linéaire convexe.

Pour modéliser ton problème en programme linéaire il te faut fixer ta fonciton objective, en l'occurence ici sera le cout cumulé de chaque produit commandé chez les fournisseurs ajouté aux frais de ports (j'ai pas réfléchis pour les frais de port, mais ca demande surement un peu de reflexion, car la fonction objective doit être une fonction linéaire idéalement, sinon ca demande l'usage d'un algo plus lent).

Ensuite tu modélises tes contraintes qui sont ici tres simple.

Exemple sans les frais de ports (j'ai pas la motivation de me pencher sur cette question désolé) :

Fonction objective : minimiser la fonction => x1 * 2 + x2 * 19 + x3 * 8 + x4 * 3 + x5 * 17 + x6 * 9 + x7 * 4 + x8 * 9 + x9 * 5

sous les contraintes suivantes :
x1+x4+x7 > n1
x2+x5+x8 > n2
x3+x6+x9 > n3

Où n1, n2 et n3 sont les quantité désirées pour les produits P1,P2 et P3
Bon, ensuite il te faudra peut etre utiliser une autre variante algorithmique que le simplex, car tu cherches une solution entiere, c'est a dire que tu interdis d'acheter 1.3 produits P1 chez le fournisseur 1.

Enfin bon, l'idée est la, modéliser ton probleme sous forme d'un programme linéaire (voir quadratique si on ne peut vraiment pas linéariser les frais de ports) et utiliser un algorithme de résolution en fonction de tes contrinte comme le simplex (mais je crois que c'est uniquement dans le cas des variables continue, donc il faudra surment en utiliser un autre, surtout si les frais de port ne se linéarisent pas).

Bon courage.