Suite et fonction Max: cas reel en entreprise

[vanhoa]

Bonjour a tous!

Je pose sur ce forum (Salon mathematique) car je ne savais pas trop si c’etait niveau Lycee ou Superieur. Ca fait quelques temps que je n’ai plus fait de maths (depuis ma prepa, soit 11 ans!!).
Je vais essayer de respecter au mieux les notations, excusez moi par avance si je fais des erreurs.
Je vais commencer par proposer mon debut de solution (car oui j’ai quand meme cherche avant) et je vous montrerai la ou je bloque.

Situation:
Une entreprise e-commerce recoit chaque jour des commandes clients a preparer et a envoyer (comme Amazon).
En debut de chaque journee, il peut parfois y avoir un certain nombre de commandes qui n’ont pas pu etre envoyees la veille, on appelle ca le “backlog”.
L'entreprise a une capacite d'envoi, c'est a dire un quantite maximale de commande qu'elle peut envoyer, elle est fixe.
Par exemple. Le jour i-1 j’ai recu 100 commandes, mais ma capacite maximale est 80, j’en ai donc envoye 80, et alors, le jour i j’ai 20 de backlog.
L'entreprise s'engage a envoye la commande au maximum 2 jours apres creation. Donc si un client fait une commande le Lundi, Mercredi au maximum, c'est envoye


Notations et remarques:
(l'editeur d'equation n'a pas l'air de marcher pour moi, j'en suis desole)
d[i] = la quantite de nouvelles commande le jour i (d[i] > ou = 0)
B[i] = le backlog au jour i (B[i] > ou = 0)
B[0] = 0 effectivement, il n'y a pas de backlog le premier jour
Q[i] = la quantite de commandes a envoyer le jour i
C = la capacite, la quantite maximale de commandes que l'entreprise peut envoyer par jour (C>0)

On a donc les relations suivantes:
B[i] = max(Q[i-1]-C ; 0) effectivement, le backlog du jour i c'est le maximum entre la quantite de commandes qu'on devait traiter le jour precedent moins la capacite et zero!
Q[i] = d[i]+B[i]
= d[i]+max(Q[i-1]-C ; 0)
= max(Q[i-1]+d[i]-C ; d[i])

Question:
quelle est, en fonction des d[i], la capacite minimale C necessaire pour respecter l'engagement d'envoyer une commande au plus tard 2 jours apres jour de creation?

Mon debut de solution:

En gros, il faut que chaque Q[i] soit < ou = a 3C:
Q[i] = max(Q[i-1]+d[i]-C ; d[i]) <= 3C
On a donc une suite Q[i]

La facon dont j'ai procede est de commencer par Q[0], puis Q[1] etc... pour voir si on pouvait generaliser une formule a Q[n]. Je trouve une relation qui peut se demontrer facilement par recurrence:

Q[n] = max(d[n]+d[n-1]+...+d[1]-(n-1)C ; d[n]+d[n-1]+...+d[2]-(n-2)C ; ... ; d[n]+d[n-1]-C ; d[n])
ca donne donc: (pour que ce soit plus lisible je mets une image)


c'est donc une fonction max avec n termes a comparer:
1er terme: d[n]+d[n-1]+...+d[1]-(n-1)C
2eme terme: d[n]+d[n-1]+...+d[2]-(n-2)C
...
n-1eme terme: d[n]+d[n-1]-C
neme terme: d[n]

Sachant ca il faut ensuite comparer chaque Q[i] a 3 fois la capacite C:
Q[1]<=3C
Q[2]<=3C
...
Q[n]<=3C
pour respecter l'engagement il faut donc prendre la maximum de ces Q[i], ainsi, l'engagement sera toujours respecte.
Mais je coince, j'ai exprime mon Q[n] mais je ne sais pas comment trouver mon C en fonction des d[i].

Merci de votre aide!!

Vanhoa

[leo06]

Bonjour,

A "vue de nez", il semblerait que, si le nombre de commandes journalières est trop important , il ne soit pas possible de respecter les engagements de livraison
En effet, si pour tout i > 1, B(i) est trop grand par rapport à C , il faudrait commencer par expédier la partie la plus ancienne du backlog, le reliquat étant intégré dans le backlog suivant; on accumule donc le retard de livraison.
Plus précisément,
Supposons que le backlog soit toujours strictement positif , auquel cas
B(i) = Q(i-1) -C et donc
Q(i) = d(i) + Q(i-1) -C => Q(i) = d(i) + d(i-1)+ ...+ d(1) - (i-1) C
pour i>1, B(i) = Q(i-1) -C = d(i-1)+... +d(1) - iC
si par exemple d(i) = iL ( croissance linéaire des commandes)
B(i) = i(i-1)L/2 -iC , pour que B(i) soit supérieur à 3C par exemple, il suffit que
pour tout i > 1 , L > = max( 2(3+i) C / [i(i-1)] ) , le max étant pris pour i>1.

Autrement dit , pour tout C, une croissance trop importante des commandes par rapport à la capacité C (cf l'exemple ci-dessus) mettra à mal l'objectif de livraison .

Bien cordialement

[vanhoa]

Tout d'abord, merci beaucoup leo06 pour avoir pris le temps de lire et repondre au probleme.

Deuxiemement, je pense avoir oublie de preciser quelques details.

Concernant les d(i):
Ce sont des variables pour moi, ce sont des projections du futur. Mais dans mon application, je dois les connaitre. Par exemple, je vais avoir tous les di quotidien de l'annee 2019. Je souhaite donc avoir une formule generale pour calculer mon C minimal qui me permet de respecter l'engagement. Si pour une certaine raison, les projections de 2019 changent, alors le C va automatiquement changer car je l'evalue avec une formule generale.

Concernant le backlog B(i):
"B(i) est trop grand par rapport à C, il faudrait commencer par expédier la partie la plus ancienne du backlog, le reliquat étant intégré dans le backlog suivant; on accumule donc le retard de livraison."
effectivement, B(i) peut parfois etre plus grand que C, mais le point important pour moi est qu'on doit justement determiner C pour que dans chaque cas, chaque d(i) soit envoye au max 2 jours apres creation.

Par rapport a u debut de solution trouve:
Dans le cas ou on a Q(i), i allant de 1 a n:
-chaque Q(i) est un max de i termes
-une fois le max trouve pour chaque Q(i), il faudra faire le max de ces n solutions pour savoir le C
Donc cela signifie que je peux regrouper tous les termes de tous les Qi sous un seul max, non?
J'aurais donc au final un max de (1+n)*n/2 termes (de Q(1) a Q(n)) que je dois comparer a 3C
donc ensuite, est ce que je peux comparer chaque terme a 3C, en deduire le C pour chaque terme, et prendre le C maximum parmis les "(1+n)*n/2" C que j'aurais calcule?

J'ai fait un cas avec 4 jours, c.f. image ci-dessous:



Si c'est correct, comment generaliser cette formule? Car avec 4 jours, manuellement c'est possible, mais si j'ai 2 annees... trop complique

[vanhoa]

Je pense avoir trouve une facon de formuler la formule, c.f. image ci-dessous. Est ce que c'est correct? il y a t il une facon plus simple de l'exprimer? Merci!

[leo06]

Bonjour,

Deux remarques : si un jour donné le backlog est nul, tout recommence comme au premier jour;
il suffit donc de regarder les situations où il n'est jamais nul , auquel cas
Q(n) = d(n) +..+ d(1) - (n-1) C

Si Q(n) <= 2C pour tout n de 1 à D
( D numéro du dernier jour considéré) , ( condition suffisante , necessaire ? )
les commandes en instance le jour n seront expédiées à la fin du jour n+1 et donc dans ton tableau, seule la première colonne importe.

Cela simplifie sérieusement l'expression que tu as obtenue et un calcul tout bête avec un tableur donne le résultat une fois rentrés les d(i).

Bien cordialement

[vanhoa]

Oui, si un jour le backlog est a zero, c'est comme si on repartait du premier jour. Mais il faut que je connaisse mon C pour savoir ceci.

J'ai modifie ma formule:



La condition que je me fixe c'est 2 jours apres le jour de creation, donc pour chaque i, Q(i)<=3C.
Meme si je prends 2C, en reprenant:
"Si Q(n) <= 2C pour tout n de 1 à D
( D numéro du dernier jour considéré) , ( condition suffisante , necessaire ? )
les commandes en instance le jour n seront expédiées à la fin du jour n+1"
en fait le jour n+1, si C < Q(n) alors le backlog B(n+1)>0 et donc mon C devra etre compare a cette quantite B(n+1)+Q(n+1).

Selon les configurations, toutes les colonnes (donc chaque terme des max) sont importantes. Exemple (c.f. image ci-dessous) ou la solution apparait dans la 3eme colonne:



Merci leo pour votre aide!
Bonne journee!
Vanhoa

[leo06]

Bien vu !...

Pour faire plus simple, reprenons un peu différemment
Pour fixer les notations , S(i) = d(i) + .... + d(1) ( le nombre total des commandes du jour 1 au jour i )

Si S(i) <= (i+2)C ,
toutes les commandes passées jusqu'au jour i seront donc expédiées le jour i+2 , en particulier celles qui été passées le jour i ( on suppose que les commandes les plus anciennes ont la priorité ).

Si on impose cette condition à tous les i , on s'assure donc que toutes les commandes d'un jour donné seront expédiées au plus tard deux jours après.

et donc le C le plus petit pour lequel ce sera vérifié pour i <=D (D dernier jour ) est

C = max [ S(i)/(i+2) ] pour i <= D

ATTENTION : en raisonnant ainsi, on ne tient pas compte du fait qu'il n'y a pas de report de la capacité d'expédition non employée d'un jour au jour suivant; on fait comme si elle avait été complètement utilisée chaque jour.
Il faut donc refaire le calcul en démarrant du jour 2 puis 3 ce jusqu'à D et prendre la plus grande des valeurs de C obtenues.

Enfin une dernière remarque : le symbole "sigma" et la fonction max sont bien utile pour écrire des expressions arithmétiques "closes" ou "compactes" mais se prêtent mal au calcul formel.

Bien cordialement

[vanhoa]

Oui, pour le fait qu'il n'y ait pas de report de capacite passe par la definition du backlog: B[i] = max(Q[i-1]-C ; 0).
Et pour resoudre le C, poser chaque i et prendre le max de tous:
Q[1]<=3C
Q[2]<=3C
...
Q[n]<=3C
avec
Q[i] = d[i]+max(Q[i-1]-C ; 0) <= 3C (donc le non report du reliquat de capacite est bien present)
puis les je continue les etapes que j'avais decrites pour arriver a ma formulation de C