[Probabilités]Répartition (RESOLUT)

[Khorrigan]

Bonjour à tous,

Ce que je viens proposer là n'est pas vraiment une enygme mais un cas concret d'application mathématique sur lequel je me casse la tête depuis quelques heures sans savoir où se trouve l'erreur dans mon raisonnement.
Dans ma scolarité (école d'ingénieur) j'ai fait des proba, mais c'est déjà loin. Je ne suis pas vraiment un geek dans le domaine.

Je vous présente le cas et les calculs que j'en ai tiré en espérant que vous pourrez me venir en aide.
Excusez-moi si je suis un peu long mais je vais essayer d'être le plus didactique possible.

Il s'agit d'un petit véhicule (navette) qui se déplace sur un rail et dessert des bases, c'est-à-dire des supports sur lesquels il vient faire des prises ou des déposes de charges. Le véhicule prend une charge sur une base et la dépose sur une autre base. Certaines bases sont exclusivement des bases de prises, d'autres exclusivement des bases de dépose et d'autres encore peuvent servir à la prise ou la dépose.

Donc, le cycle normal de ce véhicule est
Etape 1- prendre une charge
Etape 2- se déplacer jusqu'à la position de dépose (mouvement en charge)
Etape 3- déposer la charge
Etape 4- se déplacer jusqu'à la position de prise suivante (mouvement à vide)

Le but de l'étude est de connaitre la durée d'activité du véhicule en fonction du nombre de charges à transporter.

Pour cela, en plus des caractéristiques mécaniques du véhicule, je dispose des flux (c'est-à-dire du nombre de charges/h transportées) de chaque points de prises à chaque points de dépose, sous forme d'un tableau carré nommé fort logiquement tableau des flux.
Le nombre de lignes et de colonnes est égal au nombre de base. Dans chaque case est inscrit le nombre de charges transportées de chaque base de prise à chaque base de dépose.

D'un autre côté, je peux calculer sans problème le temps mis par le véhicule pour aller de chaque base à une autre ainsi que les temps pour prendre ou déposer une charge.

Le tableau des flux et ces calculs de temps de trajet me permette de calculer, par simple multiplication et cumul, le temps consommé par le véhicule pour réaliser les étapes 1 à 3 de ses cycles.

En revanche, pour calculer les temps cumulés représentés par l'étape 4 du cycle (les mouvements à vide), j'ai besoin de créer un tableau des mouvements à vide, comparable au tableau des flux (qui correspond aux mouvements chargés).

C'est là que les probabilités entre en jeu (on y vient enfin).

Donc ce tableau est composé d'un nombre de lignes et de colonnes égaux aux nombre de bases.

On part du principe que lorsque la navette a terminé un mouvement de dépose, elle se déplace vers la demande de prise la plus ancienne (c'est-à-dire qu'on ne favorise pas la proximité géographique, une priorité particulière ou tout autre critère).

Pour calculer le nombre de mouvements/heure à vide allant d'une base de dépose (d) à une base de prise (p), j'obtiens la formule suivante :

V(d,p) = D(d) x P(p) / P

avec :
V(d,p) : nombre de mouvement / h à vide pour allant de la dépose sur la base (d) à la prise sur la base (p).
D(d) : somme des mouvements/h de dépose sur la base (d)
P(p) : somme des mouvements/h de prise sur la base (p)
;)P : somme de tous les mouvements de prises (qui est aussi la somme des mouvements de dépose puisque

En clair, le nombre de mouvement à vide de (d) à (p) est égal au nombre de dépose sur (d) multiplier par la probabilité pour que la prochaine prise soit sur (p).
La probabilité pour que la prochaine prise soit sur (p) est égal au nombre de prises sur (p) divisé par le nombre de prises total.

Jusque là, ça va.
J'utilise cette formule depuis longtemps et tout se passe bien. Elle a pu être testée et éprouvée. Nous la considéront comme fiable.

Mais

Drnièrement m'a été formulée une demande nouvelle.
Pour une installation particulière, il s'avère que la navette après avoir déposé sur une base, ne peut pas faire immédiatement une prise sur cette même base.

En terme mathématique, pour reprendre la notation utilisée plus haut, on peut noter ça ainsi :
Si d=p alors V(d,p)=0

Cette nouvelle hypothèse imposée met la pagaille dans mes belles statistiques. Et c'est là que je coince, ou plutôt que j'aboutis à une formule qui ne me satisfait pas.

si d différent de p alors V(d,p) = D(d) x P(p) / (;)P - P(d))

J'attire votre attention sur le fait que le nouveau terme est bien P(d), c'est-à-dire la somme des mouvements/h de prise sur la base (d) sur laquel a été faite la dépose

En clair, on a toujours le nombre de mouvement à vide de (d) à (p) est égal au nombre de dépose sur (d) multiplier par la probabilité pour que la prochaine prise soit sur (p).
La nouveauté c'est que la probabilité pour que la prochaine prise soit sur (p) est égal au nombre de prises sur (p) divisé par la somme des mouvements de prise sur les autres bases que (d) celle où vient d'être faite la dépose.

D'un autre côté, si on prend le résonnement à l'envers, par les points de prise, on obtient la formule :

si d différent de p alors V(d,p) = P(p) x D(d) / (;)D - D(p))

Formule obténue selon une logique identique à la précédente.
Or, les deux formules ne donnent pas le même résultats. Et aucune des deux ne donne de résultats satisfaisant. :mur:

Dans le cas de la première, si l'on fait la somme de tous les mouvements à vide se rendant vers un point de prise, on s'aperçoit qu'il n'est pas égal à la somme des mouvements chargés partant de ce point de prise. Ce qui est totalement illogique (ça voudrait dire pour certaines charges, le charriot est reparti chargé d'une base vers laquelle il n'est jamais allé à vide).

Par contre, pour la somme des mouvements à vides partant de chaque base de dépose, elle correspond bien au nombre de mouvements chargés arrivant sur chacune de ces bases.

Pour la deuxième formule c'est bien sûr exactement l'inverse.


J'espère qu'il y aura parmi vous quelqu'un de plus pointu que moi dans le domaine des probabilités et qui saura trouver où mon raisonnement à déraillé. Si en plus il pouvait trouver une formule fiable pour faire ce calcul de mouvements à vide selon les hypothèses décrites, je lui en serais très reconnaissant. :jap:


Je vous remercie déjà d'avoir pris la peine de lire mes longues explications et j'espère que quelqu'un pourra m'aider.

Merci d'avance.

[nodjim]

Bonjour Khorrigan.
Quand on connait, dans un laps de temps donné T:
-Le nombre de mouvements m(pi,di) entre pi donné et di donné.
-Le temps élémentaire ti du mouvement pi vers di.
Le temps "productif" est la somme des produits ti * m(pi,di).
Le temps à vide Tv est donc la différence T-ti*m(pi,di).
Et le nombre de mouvements à vide est Tv/tv, tv étant le temps moyen d'un mouvement.
Maintenant, vu la manière dont est programmée la machine, qui va directement à la base de prise où se trouve la charge la plus ancienne, il me semble que le nombre de mouvements à vide est très majoritaire, la proportion de mouvements augmentant avec le nombre de bases. Et donc que le fait d'interdire certaines prises ne doit beaucoup changer la donne. Mais bon, je n'ai peut être pas tout compris.

[Ben314]

Salut,
Perso, en tentant une modélisation à l'aide de graphes probabilistes, une solution qui me semble "raisonable" serait simplement :

V(d,p) = P(p,d)
avec :
V(d,p) : nombre de mouvement / h à vide allant de la dépose sur la base (d) à la prise sur la base (p).
P(p,d) : nombre de mouvement / h à plein allant de la prise sur la base (p) à la dépose sur la base (d) (connu via le tableau de "flux" et, il me semble qu'on doit évidement avoir évidement P(p,d)=0 lorsque p=d)

[Khorrigan]

Tout d'abord, merci à tous les deux d'avoir pris le temps d'étudier mon problème. C'est très gentil de votre part.
Cependant, à mon grand regret, je dois dire que les réponses données ne peuvent être satifaisantes.

Je vais expliquer pourquoi.

Le temps "productif" est la somme des produits ti * m(pi,di).

Jusque-là, je suis à peu près d'accord.
Je dit "à peu près", car il faudrait plutôt parler de temps "chargé" plutôt que de temps "praductif" dans la mesure où le déplacement à vide est également, d'une certaine façon productif puisqu'il fait partie du cycle de fonctionnement du véhicule.

Le temps à vide Tv est donc la différence T-ti*m(pi,di).

Je suppose que T représente le temps total ? (c'est-à-dire une heure si l'on parle de flux horaire).
Dans ce cas, je ne suis plus d'accord avec le raisonnement.

Comme je le disais, le temps de trajet à vide fait parti du cycle de fonctionnement du véhicule. On ne peut pas le considérer comme un temps "inutile" ou plutôt "improductif" (voir ma remarque ci-dessus).

En fait, le temps "improductif" est celui que le chariot passe immobile à ne faire aucun mouvement (dans la mesur où, s'il n'a pas de charge prète à être prise, il ne se déplace pas et ne vas pas, par exemple, vers une position de "garage").

Donc, le temps improductif (qui est effectivement le but final du calcul) est :
X = T - (t(pi,di) * M(pi,di)) - (t(di,pi) * m(di,pi))
avec :
T = 1 h
pi : points de prise
di : points de dépose
t(pi,di) : temps pour aller de pi à di
M(pi,di) : nombre de charges à transporter par heure entre pi et di
m(di,pi) : nombre de mouvements à vide par heure entre pi et di

Ceci permettant de calculer l'engagement du véhicule et de savoir s'il peut réaliser le flux donné.

Tous ces termes sont soit des données (T, M), soit aisément calculables (t), sauf m, le nombre de mouvements à vide.
C'est tout l'objet de ce sujet.

Et le nombre de mouvements à vide est Tv/tv, tv étant le temps moyen d'un mouvement.

On ne peut pas calculer un temps moyen de mouvement puisque il n'y a pas équirépartition des mouvements. Pour connaitre le temps moyen, il faudrait plndérer chaque temps élémentaire de l'occurence que ce mouvement ait lieu. Or, c'est justement ce que je recherche.

Maintenant, vu la manière dont est programmée la machine, qui va directement à la base de prise où se trouve la charge la plus ancienne, il me semble que le nombre de mouvements à vide est très majoritaire, la proportion de mouvements augmentant avec le nombre de bases.

Le nombre de mouvement à vide est globalement identique à celui des mouvements chargés puisque le véhicule enchaine des cycles qui se composent d'un mouvement à vide et d'un mouvement en charge. Au final, leur nombre est donc obligatoirement identique.

J'ai bien dit "globalement" (c'est-à-dire la somme de chaque mouvements élémentaires). Car dans le détail, il n'y a pas égalité au niveau de chaque mouvements élémentaires.

Et donc que le fait d'interdire certaines prises ne doit beaucoup changer la donne. Mais bon, je n'ai peut être pas tout compris.

En fait si car les mouvements qui ne sont pas possibles sont ceux pour lesquels les mouvements à vide ont une durée nulle (le prise se faisant au même endroit que la dépose précédente, il n'y a pas physiquement de mouvement).
Donc, dans la formule de calcul du temps total, si la pondération m(di,pi) est plus importante pour des mouvements plus longs et nulle pour des des mouvements de durée 0, cela modifie énormément le résultat final.

Perso, en tentant une modélisation à l'aide de graphes probabilistes, une solution qui me semble "raisonable" serait simplement :

V(d,p) = P(p,d)
avec :
V(d,p) : nombre de mouvement / h à vide allant de la dépose sur la base (d) à la prise sur la base (p).
P(p,d) : nombre de mouvement / h à plein allant de la prise sur la base (p) à la dépose sur la base (d) (connu via le tableau de "flux" et,

Ce que je recherche n'est pas une approximation "raisonnable" mais la valeur précise. Je n'ai pas vraiment envie qu'un cas particulier s'éloigne "déraisonnablement" de la valeur calculée et que l'écart entraine un contentieux de centaines de milliers d'€ avec un client (avec sans doute mon licenciement en prime).

La formule que tu donnes me semble un peu trop simple.
Elle serait parfaite si c'était la bonne, mais qu'elle soit acceptable, il faudrait qu'elle soit le résultat d'une démontration.

il me semble qu'on doit évidement avoir évidement P(p,d)=0 lorsque p=d)

Effectivement, cela fait partie des hypothèses de départ.


Donc, le problème reste ouvert.
Merci quand même à ceux qui ont essayé.

[Ben314]

Le problème tel que tu le pose corresponnd mathématiquement à un graphe probabiliste que l'on suppose en position stable :
Les sommets (en quantité égales au double du nombre de bases) sont de type (S1) correspondants à vide->base->plein et de type (S2) correspondant à plein->base->vide.
Les proba des différents sommets sont connues via la quantité de charge/décharge associée à chaque base.
La moitié des arrêtes vont d'un sommet de type S1 à un S2 : trajets à pleins dont la proba est connus via le tableau des flux, l'autre moitié va de sommets de type S2 à un S1 : trajets à vide dont la proba est à determiner.
Tout cela conduit à un gentil système linéaire (d'inconnues les proba de trajets à vide), sauf qu'il y a beaucoup trop d'inconnues par rapport au nombre d'équations et donc qu'il y a une (trés grosse), infinité de solution au problème, c'est à dire qu'il y a des tas de façons (différentes) de remplir les consignes imposées (ce qui explique mon succin "une solution qui me semble raisonable...")

Si, comme tu semble le penser, ton problème n'a qu'une seule solution, c'est qu'il y a des données que tu ne nous as pas donné. Plus précisément, ta phrase :

On part du principe que lorsque la navette a terminé un mouvement de dépose, elle se déplace vers la demande de prise la plus ancienne (c'est-à-dire qu'on ne favorise pas la proximité géographique, une priorité particulière ou tout autre critère).

semblerait sous entendre que les charges "apparaissent" dans les bases, mais comme tu ne précise pas quelle est la loi qui régie l'apparition des charge dans le différentes bases, je ne vois pas vraiment comment utiliser cette information...

[Khorrigan]

Plus précisément, ta phrase :semblerait sous entendre que les charges "apparaissent" dans les bases, mais comme tu ne précise pas quelle est la loi qui régie l'apparition des charge dans le différentes bases

C'est le tableau des flux qui indique la probabilité d'apparition des charges sur une base de prise.

Le tableau des flux donne le nombre de mouvement de charges entre une base de prise et une base de dépose.

Je donne un exemple : un système qui dispose de 3 bases de prise (p1 à p3) et de 3 bases de dépose (d1 à d3).

On peut avoir comme tableau de flux :

[FONT=Courier New]
____p1__p2__p3
d1__0___2___3
d2__1___0___5
d3__4___1___0
[/FONT]
Il signifie qu'il y a, par exemple, 4 charge/h qui sont prises en p1 pour être déposées en d3.
Cela veut aussi dire, par exemple, que 5 charges / h "apparaissent" sur la base de prise p1 (1 ch de p1 à d2 et 4 c/h de p1 à d3).
Cela veut aussi dire, par exemple, que 6 charges / h "disparaissent" de la base de dépose d2 (1 ch de p1 à d2 et 5 c/h de d2 à p3).

Si l'on ne tient pas compte de la règle interdisant de faire des mouvements à vide de la base de dépose Dx à la base de prise Px, la probabilité des mouvement à vide se calcule ainsi :
V(d,p) = D(d) x P(p) / P
avec :
V(d,p) : nombre de mouvement / h à vide pour allant de la dépose sur la base (d) à la prise sur la base (p).
D(d) : somme des mouvements/h de dépose sur la base (d)
P(p) : somme des mouvements/h de prise sur la base (p)
;)P : somme de tous les mouvements de prises (qui est aussi la somme des mouvements de dépose puisque

Pour donner un exemple :
Il y a 5 c/h qui sont déposer en d3.
Lorsque la navette est en d3, la probabilité pour qu'elle se rende vers une position de prise est proportionnelle à la quatité de palettes à y prendre, donc 5/16 pour aller en p1, 3/16 pour aller en p2 et 8/16 pour aller en p3.
Donc, le nombre de mouvements à vide de d3 à p1 sera 1,56 mvt/h.

Cela donne un tableau des mouvements à vide suivant :

[FONT=Courier New]
______p1______p2______p3
d1___1,563___0,947___2,5
d2___1,875___1,125___3
d3___1,563___0,947___2,5
[/FONT]
Comme on le voit, la somme des mouvements à vide se terminant sur une base de prise est égal au nombre de mouvements à plein partant de cette base et vice-versea pour les base de dépose.

Cette règle fonctionne bien et a pu être vérifiée sur de nombreuses installations au cours de plusieurs années.

Maintenant, pour une installation précise, on impose qu'il ne doit pas y avoir de mouvement à vide partant d'une base de dépose et allant vers une base ayant le même indice.
C'est-à-dire, par exemple, qu'il ne peut pas y avoir de mouvements à vide de la base de dépose 2 vers la base de prise 2.
Cette règle n'est pas une simple lubbie mais a une raison très concrète.

Donc, donc la tableau des mouvements à vide, toutes les cases de la diagonale (x,x) ont une valeur 0.

Cette règle remet en question toutes les probabilités pour les autres cases.
C'est la règle pour calculer les mouvements à vides des autres cases que je n'arrive pas à déterminer (plus exactement, celle que j'ai calculée ne convient pas).

[nodjim]

Le nombre de mouvement à vide est globalement identique à celui des mouvements chargés puisque le véhicule enchaine des cycles qui se composent d'un mouvement à vide et d'un mouvement en charge. Au final, leur nombre est donc obligatoirement identique.

Je voulais parler des trajets entre une dépose et une prise, et tu confirmes bien que presque tous ces trajets se font à vide. (heureusement que ce ne sont pas des camions avec des longs parcours)

[nodjim]

Pour moi, le temps gagné ,en pourcentage, en temps normal par les trajets de longueur nulle est la somme des produits Pi= (mvi/MV)*(mci/MC).
mvi: flux à vide de la base i.
MV: total des flux à vide.
mci: flux en charge vers la base i.
MC: total des flux en charge.
Pour les bases particulières, il suffit d'ôter son produit Pi de la somme pour déduire le nouveau ratio de production.

[Ben314]

Bon, aprés moultes calculs sur un graphe probabiliste, j'arrive à ça :

Soit
S = P(i) = D(i)
et K la constante définie par :
1/K = S + [P(i)D(i)/(S-P(i)-D(i))]

Alors, pour tout d différent de p, on a:
V(d,p) = K x D(d) x P(p) x [ 1 + P(d)/(S-P(d)-D(d)) + D(p)/(S-P(p)-D(p)) ]

[Khorrigan]

BRAVOOOO !!! :++:

Et aussi MERCI !!! :lettre:

Je serais incapable de vérifier les calculs eux-même; mais j'ai mis la formule dans un petit tableau Excel pour vérifier par l'exemple et.... CA MARCHE !!!
J'ai pu vérifier que
- la somme des mouvements à vide est la même que celle des mouvements chargés
- la somme des mouvements à vide partant d'une base de dépose est égale à la somme des mouvements chargés arrivants à cette base
- la somme des mouvements à vide arrivant à une base de prise est égale à la somme des mouvements chargés partant de cette base.

Ca tombe nickel pil-poil ! :happy2:

Je suis franchement super-content. Je désespérais que quelqu'un puisse obtenir un résultat qui soit aussi satisfaisant.
J'imagine que ça a du représenté un gros boulot et je te remercie du fond du coeur. :+++:

Merci aussi à tous les autres qui se sont intéressés à ce problème et on tenté de trouver une solution. :++:

[nodjim]

Oui, c'est un sacré boulot qu'il a fait là ! Chapeau! je ne l'aurais jamais sortie cette formule.