Discussion :

[FrancisSourd]

Effectivement, rien n'est dit sur la manière de traver le δ (i, j) de coût minimal.

Je pense que tu peux légitimement demander à ton prof de vous expliquer comment trouver cela. A mon avis, cela ne s'invente pas (ou alors tu as de très bonnes dispositions pour faire de la recherche!)

[andjeo]

Effectivement, rien n'est dit sur la manière de traver le δ (i, j) de coût minimal.

Je pense que tu peux légitimement demander à ton prof de vous expliquer comment trouver cela. A mon avis, cela ne s'invente pas (ou alors tu as de très bonnes dispositions pour faire de la recherche!)

J'ai compris comment trouver cela mais impossible de le transcrire dans un algorithme. Mon prof n'est pas un prof d'info donc à mon avis il sera pas quoi me dire.

[andjeo]

Je n'ai pas compris le calcul de δ (A, 4)

Pour savoir si cette solution constitue l’optimum, on va considérer une par une chacune des cases n’ayant pas reçues d’affectation (0) et calculer la différence de prix de transport (ou coût marginal) qui résulterait de l’affectation d’une unité dans cette case.
Si l’on affecte par exemple une unité dans la case (A, 4), il faut alors en retirer une de la case (A, 3), en ajouter une dans la case (B, 3) et finalement en retirer une dans la case (B, 4).
Cet échange d’une unité fait varier le coût total d’une quantité :
δ (A, 4) = 6-2+3-5=2 (bilan positif)
Si le bilan financier est positif, cela veut dire que cette opération créerait une dépense supplémentaire et n’est donc pas intéressante.

Les 6 2 3 5 du calcul proviennent d'un tableau de prix. les + et - du calcul correspondent en fait au +1 et -1 que je cherche.

[FrancisSourd]

[quote="andjeo"]

J'ai compris comment trouver cela mais impossible de le transcrire dans un algorithme. Mon prof n'est pas un prof d'info donc à mon avis il sera pas quoi me dire.

Tu es capable de le faire sur de petites instances mais je pense que tu auras plus de mal à le faire sur des plus grosses matrices. Par exemple, il me semble que la seule "preuve" que tu es capable de donner pour dire qu'une solution est optimale est "je ne suis pas capable de trouver un δ (i, j) négatif".

Est-ce ton prof qui te demande de l'implanter ou est-ce toi qui veut le faire pour ton plaisir?
Si c'est ton prof et qu'il n'est pas informaticien pour un poil, c'est mal barré (c'est comme si un prof de stat redemandait à ces étudiant de coder Excel...)
Si c'est pour toi, lis un bouquin sur les graphes et les flots (je suis têtu)

[andjeo]

Tu es capable de le faire sur de petites instances mais je pense que tu auras plus de mal à le faire sur des plus grosses matrices. Par exemple, il me semble que la seule "preuve" que tu es capable de donner pour dire qu'une solution est optimale est "je ne suis pas capable de trouver un δ (i, j) négatif".

Est-ce ton prof qui te demande de l'implanter ou est-ce toi qui veut le faire pour ton plaisir?
Si c'est ton prof et qu'il n'est pas informaticien pour un poil, c'est mal barré (c'est comme si un prof de stat redemandait à ces étudiant de coder Excel...)
Si c'est pour toi, lis un bouquin sur les graphes et les flots (je suis têtu)

C'est sur qu'en cours on l'a vu sur de petites instances comme tu dis et c'était déjà très long à calculer tous les delta.
Il est exact que dès lors qu'il n'y a plus de delta négatif la solution est optimale.
Le sujet que l'on m'a donné est écris au dessus et lorsque le prof me l'a donné, il m'a dit qu'on l'avait vu en cours et j'ai demandé si c'était la méthode du stepping-stone et il m'a répondu oui.
Je pense qu'il doit avoir des connaissances en informatique mais ce que je veux dire c'est que ce n'est pas un prof d'informatique.