Probléme d'optimisation combinatoire prenant en compte 2 critères

[invited27f3387]

Bonjour à tous, je suis en en école sup de Logistique. Je viens de m'inscrire sur ce forum dans l'espoir que quelqu'un m'aide à trouver une solution à mon problème simple à comprendre mais compliqué à résoudre pour quelqu'un de mauvais en maths comme moi....

J'ai un coût et un délais proposé par 4 transport différents et 4 transporteurs différent.
Il faut choisir un transporteur par transport (n'importe le quel) qui permettra de minimiser à la fois le délai total et le coût du transport.
Quelqu'un aurait il une idée de la méthode à appliquer ? La méthode du simplexe se base sur des contraintes ici ce n'est pas le cas.

Je mets les données ci-dessous par transporteurs. Le département (dept) correspond au transport pour lequel il faut choisir un transporteur.


Géodis
dept Délais Coûts
61 48 85,1
92 24 33,25
26 24 160,28
07 24 20,65

Gefco
dept Délais Coûts
61 72 71,4
92 24 31,26
26 48 124,82
07 48 17,65

Thévenet
Dept Délais Coûts
61 48 76,92
92 48 30,98
26 48 134,61
07 72 15,67

NDD
Dept Délais Coûts
61 48 89,33
92 48 29,79
26 48 95,61
07 24 19,97
-----

[inviteea028771]

Quand il y a plusieurs paramètres à minimiser, il faut choisir une relation entre les paramètres, car la solution n'est pas forcément unique.

Par exemple, pour simplifier :

Pour livrer un produit, tu as le choix entre un transporteur qui livre en 7 jours pour 0€, et un transporteur qui livre en 1 heure pour 1000€, lequel est le meilleur?

Ici, ça dépend de quelque chose d'autre : quelle est l'importance relative des deux paramètres ?

Typiquement, si je dois me faire livrer un livre, je choisi le premier, si c'est pour me "livrer" à l’hôpital alors que je suis blessé, je choisi le second


Il faut donc définir une fonction d'utilité U, qui va associer une valeur à la combinaison des paramètres. Et alors on va chercher à minimiser U

Mais la solution va fortement dépendre de la fonction d'utilité que l'on va choisir.



Par exemple ici, pour la livraison dans le 61, Thévenet est meilleur que Géodis et NDD (moins cher pour le même temps de livraison), mais comment comparer Gefco et Thévenet? Est ce que les 24 heures en moins sur le temps de livraison valent les 13.7€ de différence?

La réponse va être "ça dépend"

[invited27f3387]

Bonjour Tryss, et merci pour la réponse.

En effet, je comprends ce que tu veux dire, ça va dépendre. C'est pour cela que j'ai développer un Userform indiquant le délai et le coût sur excel pour laisser le libre arbitre à l'utilisateur. Si la date de livraison est imminente il choisira le délai sinon il choisira le coût.

Le souci c'est que j'aimerai estimer le gain en coût et en délai de l'application sur l'historique en 2012. J'ai fais une simulation sur les transport en 2012 en privilégiant uniquement le coût . Le résulat : perte de 59 jours de délais et gain de 3525 €.
Puis j'ai fais une simulation en privilégiant le délai et en départageant sur le coût. Le résulat : gain de 152 jours et perte de 2000€.

Maintenant j'aimerai trouver un gain optimum entre coût et délai.

Le coût dépend du poids et du département (ça se base sur une grille tarifaire et il est difficile de trouver une equation exacte traduisant cette grille).
Le délai dépend du département.

Je comprends que la relation est difficile à trouver puisque ça va dépendre. Mais est il possible dans un monde théorique de trouver l'optimum avec pour relation 10 € = 1 heure par exemple?
Comment trouver la fonction U et la minimiser ?

[inviteea028771]

Bonjour Tryss, et merci pour la réponse.

En effet, je comprends ce que tu veux dire, ça va dépendre. C'est pour cela que j'ai développer un Userform indiquant le délai et le coût sur excel pour laisser le libre arbitre à l'utilisateur. Si la date de livraison est imminente il choisira le délai sinon il choisira le coût.

Le souci c'est que j'aimerai estimer le gain en coût et en délai de l'application sur l'historique en 2012. J'ai fais une simulation sur les transport en 2012 en privilégiant uniquement le coût . Le résulat : perte de 59 jours de délais et gain de 3525 €.
Puis j'ai fais une simulation en privilégiant le délai et en départageant sur le coût. Le résulat : gain de 152 jours et perte de 2000€.

Maintenant j'aimerai trouver un gain optimum entre coût et délai.

Le coût dépend du poids et du département (ça se base sur une grille tarifaire et il est difficile de trouver une equation exacte traduisant cette grille).
Le délai dépend du département.

Je comprends que la relation est difficile à trouver puisque ça va dépendre. Mais est il possible dans un monde théorique de trouver l'optimum avec pour relation 10 € = 1 heure par exemple?
Comment trouver la fonction U et la minimiser ?

Ici, tu peux juste optimiser sur chaque département en les considérant comme des problèmes indépendants, sauf si tu as des avantages à limiter le nombre total de transporteurs

Une fois que tu as défini une relation du type 10€ = 1heure, alors oui, il devient possible d'obtenir une minimisation.

Par exemple, si 10€=1 heure, alors on peut prendre

Il s'agira alors de minimiser cette fonction sur l'ensemble des possibilités.

Dans ton cas, tu semble être assez limité dans tes possibilités : tu as un ensemble fini de situations (et de petite taille), il suffit donc de calculer la valeur de la fonction pour chaque situation, et prendre la meilleure.



Pour reprendre tes données en exemple, pour la livraison dans le 61, les transporteurs obtiennent un "score" de :

Géodis : 48 + 85,1 / 10 = 56.51
Gefco : 72 + 71,4 /10 = 79.14
Thévenet : 48 + 76,92 /10 = 55.69
NDD : 48 + 89,33/10 = 56.93

(ici, plus le score est bas, mieux c'est)

On préférera donc Thévenet ici.


Après, on peut raffiner la fonction U, en prenant justement en compte d'autres paramètres, comme par exemple l'imminence de la date de la livraison. Par exemple, si le produit doit être livré dans 2 jours, le score d'une livraison en 3 jours va être très fortement dégradé, et le score d'une livraison en une journée pourra être amélioré (si on considère qu'avoir de la marge en cas de soucis du transporteur est une bonne chose).

Note que tu peux parfaitement définir la fonction U "par morceaux". Par exemple, en considérant qu'un jour de retard coute 1000, qu'un jour de livraison "normal" coute 30, et que livrer le jour même coute "double" (a cause de la possibilité accrue de retard en cas de problème) (t= temps de livraison en jours, c = cout de la livraison, d = jours avant que le produit doive être livré), la fonction U pourrait ressembler à ça :

U(t,c,d) = 1000*(t-d) + 30*d + c ; si t > d
U(t,c,d) = 30+30*t + c ; si t=d
U(t,c,d) = 30*t + c ; si t < d

[A voir en vidéo sur Futura]

[invited27f3387]

Ok impec, j'ai compris.
Par contre la difficulté va résider dans le coefficient à choisir ! comment justifier qu'un jour de retard coute 1000. Ca demande une analyse plus poussé pour connaître le coût d'un jour de retard pour livrer à l'entreprise.
A la base j'avais calculé la racine de la somme des carrés du délai et du coût. Cette racine me donnait la distance au point 0,0 (là où ça coute rien et où c'est instantané) sur un graphique d'axe de coût et de délai (d'échelle identique). Je prenai alors la valeur minimale.
Qu'en penses tu ??

[gg0]

Qu'est-ce que ça donne si tu décides de déterminer le délai en heures ?

Cordialement.

[invited27f3387]

Je comprends pas ce que tu veux dire, le délai est déjà en heure.

[Dlzlogic]

Qu'est-ce que ça donne si tu décides de déterminer le délai en heures ?

Cordialement.

Bonjour gg0,
Finalement, je dois pas être si mauvais, j'ai fait la même remarque.
http://www.maths-forum.com/probleme-...ire-140120.php

[invited27f3387]

Effectivement, vous êtes sur tous les fronts !
Non c'est un problème concret en entreprise. Cela changerai je pense si l'on met par exemple le délai en minute puisqu'une minute équivaudrai à un euros.

[Dlzlogic]

Je crois que toutes les réponses qu'on vous a faites convergent : il faut une relation entre le délai et le prix.
Si vous dites maintenant que 1 minute équivaut à 1€, voilà la relation, et il n'y a plus de problème.
Reste la difficulté éventuelle de transformer des heures en minutes, puis en € en tenant bien compte du signe

[invited27f3387]

Merci bien pour les réponses. Je pense que je vais pouvoir m'en sortir maintenant^^.

[gg0]

Je vais m'expliquer :


Si x et y sont d'unités différentes, un changement d'unités (passer d'heures en jours) sur x change la valeur de v de façon assez peu intéressante. Alors même que y ne change pas. Donc v dépend plus des unités que des valeurs.

Cordialement.
NB : Pour x en heures et y en euros, quelle est l'unité de x²+y² ???

[Dlzlogic]

NB : Pour x en heures et y en euros, quelle est l'unité de x²+y² ???

Réponse : des RTT ?
J'ai bon ?

[inviteea028771]

Je vais m'expliquer :


Si x et y sont d'unités différentes, un changement d'unités (passer d'heures en jours) sur x change la valeur de v de façon assez peu intéressante. Alors même que y ne change pas. Donc v dépend plus des unités que des valeurs.

Cordialement.
NB : Pour x en heures et y en euros, quelle est l'unité de x²+y² ???

Dépend des unités des constantes égales à 1 devant x² et y²

Non, parce que si on va par là, quelle est l'unité de 1+x+x² si x est une longueur?

[gg0]

Voila pourquoi on préfère les formules homogènes (en termes d'unités); ou travailler avec des nombres sans unités.