Résolu : Problème complexe d'optimisation combinatoire

[Jubei1]

Bonjour à tous, je crée cette discussion 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 ?
Je mets en pièce-joint une tableau.
La finalité est de le trouver une combinaison sur les 95 départements.

 

[Dranreb]

Re : Problème complexe d'optimisation combinatoire

Bonjour.
Vous voulez quelle système.
1) - Un des deux critère est prioritaire et il faut retenir le minimum de l'autre parmi les minima identiques du premier
2) - Il existe une valeur possible aussi fâcheuse de l'autre qu'une certaine fixée du premier et tout est proportionnel à cela.
Dans ce dernier cas c'est le minimum de la somme des carrés des deux, chacun étant affecté d'un coefficient.
C'est une question de distance minimale au point X=0, Y=0 des points de coordonnées X,Y étant les deux critères, sur des échelles d'axes équitables.

 

[Jubei1]

Re : Problème complexe d'optimisation combinatoire

Bonjour Dranreb, et merci pour la réponse.

Je suis désolé mais j'ai pas très bien compris ce que tu m'as expliqué. Je pense que le système qu'il faut c'est le deuxième, mais je saurais pas appliquer ce que tu conseilles. Aurais tu un exemple ???

 

[Dranreb]

Re : Problème complexe d'optimisation combinatoire

La disposition des données n'est pas très pratique pour faire des formules simples.
=D4^2+E4^2 forme un critère global pour le transport 1, transporteur 1.
À supposer toutefois qu'un accroissement de 1 du délai est aussi ennuyeux qu'un accroissement de 1 du coût, sinon il faut un coefficient correcteur à l'un des deux critères.
Il ne reste qu'à chercher le transporteur qui à le critère global le plus petit.

 

[Jubei1]

Re : Problème complexe d'optimisation combinatoire

J'ai fait ce que tu m'as expliqué. J'ai mis aucune pondération sur aucun critère. J'obtiens cec en PJ.


Penses tu que c'est la solution optimale ??

 

[Dranreb]

Re : Problème complexe d'optimisation combinatoire

Oui. C'est bien ce à quoi je pensais.
En reportant les points sur un graphique ayant les Délais et Coûts pour axes, ça retiendrait le point le plus proche de 0, 0 si les axes ont la même échelle. La racine de cette somme des carrés (dont on n'avait pas besoin puisqu'on cherchait seulement le minimum) donnerait cette distance minimale à 0. (Cf: le théorème de Pythagore)

 

[Jubei1]

Re : Problème complexe d'optimisation combinatoire

Ce qui veut dire qu'il faudrait faire un graphique avec pour absice le délais et pour ordonnée le cout et on placerai les points avec par exemple pour coordonnée de géodis pour le département du 61 (48;85,1) ?
Pourquoi c'est nécessaire de comparer la somme des carrés et non la somme tout court alors? A part pour connaitre la racine et donc la distance de 0 ?
J'ai pas compris encore je crois là lol.

 

[Dranreb]

Re : Problème complexe d'optimisation combinatoire

C'est après tout une affaire de conviction
La somme des critères donne équivalentes les combinaisons situées sur une même droite du graphique.
Tandis que la somme des carrés des critères donne équivalentes les combinaisons situées sur un même cercle de centre 0, 0
Ça me parait plus juste de tenir de moins en moins compte d'un des critères à mesure qu'il devient de plus en plus bas par rapport à l'autre. Car c'est bien l'autre alors qui persiste à maintenir la combinaison loin de l'idéal où c'est instantané et que ça ne coute rien. Rêvons un peu…

 

[Jubei1]

Re : Problème complexe d'optimisation combinatoire

D'accord, je suis entrin de suivre ton idée et la reporte sur l'intégralité des transports.
A la base je compté partir sur l'algorithme du simplexe mais je pense pas que ce soit adapter, puisqu'il n'y a pas de contraintes.

 

[Jubei1]

Re : Problème complexe d'optimisation combinatoire

Bon sur les 420 transports j'ai sorti la liste des meilleurs transporteurs sur le délais et la liste des meilleurs transporteurs sur le cout. J'obtiens les résultats suivants :
liste meilleur délais = gain délais : 173 jours ; perte cout : 2108€
liste meilleur cout = perte délais : 57 jours ; gain cout : 3525€

Ensuite j'ai sorti la liste sur les carré miminal par transport, j'obtiens les résultats suivante :
gain délais : 90 jours ; gains cout : 2990€

Qu'en penses tu, est-ce la solution, optimum ?

 

[Dranreb]

Re : Problème complexe d'optimisation combinatoire

Je le pense, toujours sous réserve qu'un euro de moins compense bien 1 jour de délai en plus, et vice versa.
Cela dit je n'ai pas compris par rapport à quelle base (commune j'espère) tu a mesuré les gains et pertes. Mais peu importe.

 

[Jubei1]

Re : Problème complexe d'optimisation combinatoire

1 euros compense 1 heure ( le délai était exprimé en heure).

Les 3 simulations (délai, cout, cout/délai) ont été faite sur les mêmes transports si c'est bien ce que tu demandes. Ces transports sont la totalité des transport de l'année 2012 de mon entreprise.

 

[Jubei1]

Re : Problème complexe d'optimisation combinatoire

J'ai réalisé le graphique je le met en pièce jointe.
Pourrais-tu me dire stp si c'est bien ce à quoi tu pensais ?

 

[Dranreb]

Re : Problème complexe d'optimisation combinatoire

Bonjour.
Oui c'est bien ça. Encore qu'on pourrait mettre tous les points pour un transport avec une marque particulière plus grand pour le transporteur retenu afin qu'on voie visuellement que c'est bien le meilleur. Mais cette visualisation ne serait convaincante que si les axes avaient la même échelle.

 

[Jubei1]

Re : Problème complexe d'optimisation combinatoire

Je te fais part du rapide changement et te remercie par la même occasion.