Discussion :

[Roncevaux]

Bonjour,

Voila bien longtemps que je suis sorti de mes études, j'approche plutôt de la retraite.
Néanmoins j'ai gardé ce coté curiosité et j'aime comprendre.
Mais l'âge aidant je n'arrive plus à me rappeler de tout ce que j'ai appris...

Je me passionne pour un jeu de gestion et je voudrais optimiser mes décisions.

Typiquement le problème consiste :

Un atelier A fabrique des objets "a" en un temps par exemple de 21 minutes
Mais pour les fabriquer il lui faut :
Des objets "b" fabriqués en 36 minutes dans un atelier B et des objets "c" fabriqués en 15 minutes dans un autre atelier C.
Pour fabriquer 1 objet A il me faut 1 objet b ET 1 objet C


Mon problème est d'arriver à produire de manière continue, en faisant le moins de stock possible d'avance de "b" et de "c", mais en permettant que "a" soit produit sans être ralenti par la production des autres éléments constitutifs.
Autrement formulé, combien d'atelier A écouleront la production des ateliers B et C sans que je ne fasse trop de stocks de b et c.
Par évidence les ateliers sont en nombre entiers.
Intuitivement j'ai trouvé une solution à base de courbes, mais je voudrais généraliser.
Dans ce cas, approximativement, 4 ateliers A écoulent la production de 7 ateliers B et 3 atelier C.

Je me rappelle de cours de recherche opérationnelle, et de programmation linéaire, mais je n'arrive pas à refaire la mise en équation. (C'est pas beau de vieillir !)
Dans le jeu il y a toute une foultitude d'autres productions interdépendantes
Je suis arrivé empiriquement à trouver une solution par des courbes, mais je voudrais généraliser le raisonnement.

Merci

Roncevaux

[Flodelarab]

Bonjour

Soit Q_A, Q_B, Q_C, les quantités de produits et n_A, n_B, n_C, les quantités d'ateliers. Et t le temps écoulé.
On a:
Q_A=Q_B=Q_C
Q_A=n_A x t/21
Q_B=n_B x t/36
Q_C=n_C x t/15

On calcule donc:
n_A x t/21 = n_B x t/36 = n_C x t/15
n_A/n_C=21/15=7/5 et n_B/n_C=36/15=12/5

Pour 5 ateliers C, il faut 12 ateliers B et 7 ateliers A.

Cela fournira en 21 heures, soit 1260 minutes, 420 pièces de B et 420 pièces de C et 420 pièces de A consumant les pièces B et C précités.

Pour ton jeu, il faut laisser 36 minutes d'avance (1 tour) aux ateliers B pour avoir du stock et ne pas casser la production.

[dourouc05]

Juste par curiosité, de quel jeu s'agit-il ?

Sinon, pour ta formulation en MILP (à mon avis, les variables binaires seront difficiles à éliminer, ici), je pense directement à ces variables :

• vaut le nombre de machines produisant i démarrées à l'instant t ;
• donne la quantité stockée de i à l'instant t ;
• est le nombre de machines produisant du i.

La discrétisation temporelle devrait correspondre au plus petit commun diviseur entre tous les temps de production (ici, trois minutes). Dans les contraintes, j'imposerais qu'au plus machines peuvent démarrer dans toute période de longueur correspondant au temps de production.

C'est encore loin d'une formulation complète . Est-ce que ça te débloque ? (Ça, c'est vraiment pour l'approche optimisation mathématique, comme tu en as parlé.)

[Roncevaux]

Bonjour à tous, et merci pour vos réponses.
Elles me rassurent, car par moment je me dis que je suis fou de me prendre la tête comme ça, mais en même temps je vois que vous me proposez des solutions...

Le jeu est bien connu il s'agit d'Anno.

La réponse de Flodelarab est une solution concrète.
Sur une réponse sur 1260 minutes, je peux extrapoler sur un temps plus court qui m'intéresse et qui correspond aux moyens de transports que j'ai entre entrepôts et marchés.

En effet j'ai des navires qui joignent mes iles "de production" à l'ile principale qui est "habitée".
Je sais combien mes habitants consomment.
Je sais que mes transports mettent 20 minutes, et peuvent transporter de 60 à 190 matières consommables.

Le challenge est de faire en sorte que ceux ci soient utilisés au mieux pour ne pas faire de stock et répondre à la demande, tout en ayant leurs soutes les plus pleines possible.

Si je rapporte le calcul de 1260 à 20 minutes, avec les mêmes répartitions je produit 40 "a", si ma demande est le double je vais poser 14 ateliers A, 24 B et 10 C, ce qui me permet de remplir un navire de 80 places.


Quant à ta réponse, dourouc05, elle va vers ce que je cherche vraiment : généraliser....

Parce que dans le jeu on produit des dizaines de matières interdépendantes pour une bonne partie d'entre elles.
Donc mon but (et ma prise de tête) est d'arriver à utiliser peu ou prou un tableur Excel pour calculer avec le solveur pour déterminer en fonction des matériaux nécessaires pour un objet, les contraintes apportées par les deux composants dont il a besoin.

Dans ce que tu dis, je ne suis pas obligé de démarrer immédiatement les machines qui fournissent les composants et celle qui fabrique le produit fini. Donc peut être nul. A moi de démarrer l'atelier final au bon moment.
Pour ce qui est du le but est de ne pas en faire....

Reste l'important, traité par Flodelarab quel est

Ce que je veux dire est que s'il est nécessaire d'avoir Start i et Stock i pourquoi pas, mai sinon c'est une gestion manuelle à faire.

Il me reste à me plonger dans la "discrétisation temporelle"...

Je m'y attèle mais veux bien votre aide quand même.

Cordialement

Roncevaux

[Flodelarab]

Mouai. Il y a la théorie et la pratique.

Si tu veux partir en vacances, tu peux calculer une proportion théorique qui ne fait aucun stock (c'est ce qu'on a fait).

Mais dans ce genre de jeu, tu es en déséquilibre permanent. Et tu donnes des coups de pattes, par ci, par là, pour recadrer les choses.

De plus, tu sembles oublier la politique. Tu fais comme s'il existait une solution optimale. Mais l'expérience prouve qu'il ne faut pas faire la même chose si tu veux axer ton empire vers le commerce, ou la guerre ou le bonheur de tes citoyens, etc. Et ça, ce sont des choix politiques. Que l'on ne résout pas par équation.

[Roncevaux]

Mouai. Il y a la théorie et la pratique.

Mais l'expérience prouve qu'il ne faut pas faire la même chose si tu veux axer ton empire vers le commerce, ou la guerre ou le bonheur de tes citoyens, etc. Et ça, ce sont des choix politiques. Que l'on ne résout pas par équation.

Certes Flodelarab,

C'est le cas de la plupart des jeux de gestion en concurrence. Mais la version d'Anno, n'intègre ni guerre, ni rivaux, ni tracas de ce genre.
Le bonheur de mes citoyens est directement lié à ce qu'ils sont approvisionnés au mieux.

Si j'ai du surplus de matières consommables, je peux toujours les vendre sur le marché général aux autres joueurs, ça me rapporte pour acheter moi même ce que je ne produis pas.

Par contre si mes navires font leurs aller-retour à moitié pleins, ou si je ne produis pas assez pour "nourrir" mes habitants je dépense des ressources "pour rien".
En cela j'en reviens donc à des équations.

Mais tu as raison. Un équilibre parfait est illusoire, on peut seulement tendre vers lui, comme dans la vraie vie.

Amitiés

[dourouc05]

Quant à ta réponse, dourouc05, elle va vers ce que je cherche vraiment : généraliser...

Dans ce cas, je me permets de faire ma pub : http://tcuvelier.developpez.com/tuto...nception-jeux/. Ça parle notamment d'Excel pour résoudre ce genre de problèmes (justement dans le contexte de jeux ).

En tout cas, tu fais bien de préciser que tu parles d'Anno ; moi, j'étais parti dans un contexte plus industriel . Dans ce cas, les variables n'ont pas de sens telles quelles : tu ne sais pas exactement quand débutes la production d'un bâtiment donné… Et il faut aussi tenir compte des délais d'acheminement vers l'entrepôt (y compris le temps qu'une charrette arrive).

(Bon, tu pourrais considérer tous ces paramètres comme incertains, puis partir sur une modélisation de type robuste, plutôt que stochastique avec une explosion combinatoire pour les scénarios à considérer… Il s'agirait donc de faire démarrer les "usines" au pire moment pour ta chaîne de production.)

N'empêche, je pense que ce genre d'approche est trop complexe pour ce cas-ci. Dans tous les cas, tu auras du mal à trouver une fonction objectif : ici, tu es plus intéressé par une solution réalisable (et il n'y en aura probablement pas beaucoup).

Je partirais plus sur un stock (au niveau de l'île) qui augmente chaque fois qu'un bâtiment produit, en considérant ce qui se passe en moyenne (par exemple, souvent, toutes les trois minutes, une charrette vient chercher 3 t de bière) : en t = 0, 0 t, valeur constante jusqu'en t = 3 min, 3 t (multiplié par le nombre de bâtiments de ce type). Tu procèdes de même pour les bâtiments consommateurs, qui consommeront le stock global du produit précédent et ajouteront un produit plus raffiné.
Pour moi, la notion de stock est indispensable pour faire communiquer les producteurs et les consommateurs.
Chaque bâtiment commence à opérer dès que possible : dès t = 0, toutes les matières premières ; ensuite, dès qu'il y a assez de matière dans le stock.
Ici, on néglige toutes les différences dans les instants où les bâtiments commencent à produire, les délais d'acheminement.

Il me reste à me plonger dans la "discrétisation temporelle"...

C'est un joli terme pour dire que tu considères le monde à seulement certains moments dans le temps (parce que tu ne peux pas le faire en continu). Par exemple, dans le jeu, la simulation considère probablement un pas de temps de 50 ms, quelque chose comme ça, pour savoir ce qu'il se passe à chaque image à afficher. Seulement, dans tes calculs, tu n'as pas besoin d'une telle précision.

De plus, tu sembles oublier la politique. Tu fais comme s'il existait une solution optimale. Mais l'expérience prouve qu'il ne faut pas faire la même chose si tu veux axer ton empire vers le commerce, ou la guerre ou le bonheur de tes citoyens, etc. Et ça, ce sont des choix politiques. Que l'on ne résout pas par équation.

Non, mais ces choix politiques peuvent s'interpréter selon une fonction objectif à maximiser/minimiser, ce que Roncevaux semble avoir posé dès le début (limiter les stocks).

[Roncevaux]

Bonjour douroucou,

J'ai dû prendre un peu de temps pour parcourir ton site que je trouve particulièrement intéressant.
Cela répond en grande partie à mes questions.

Il me reste néanmoins un souci de maitrise du solveur.
Quelques questions se posent dans son usage.

Comment bien formuler les contraintes, surtout qu'il ne peut y en avoir que sur les variables dans le cas où elle doivent être entières ?
Si on enregistre le solveur où le retrouver ?

N'hésite pas à me contacter si tu le souhaite, je ne veux pas être envahissant.

Cordialement.

Roncevaux

[dourouc05]

Tu peux mettre d'autres types de contraintes, bien sûr. Maintenant, Excel est assez limité pour leur entrée… Enfin, pour ce genre de détails, je te conseille de prendre la voie du forum Excel, rempli de gens bien plus capables que moi de t'aider à ce niveau .

AIMMS offre une interface graphique, mais j'ai personnellement du mal à le comprendre… Si tu veux programmer en Python, regarde du côté de Pyomo. Ce que j'utilise personnellement, c'est Julia avec JuMP. Tout ça, sans jamais toucher directement au solveur, donc il est assez facile de changer les algorithmes derrière la résolution.