Construction d'un graphe

[juju78]

Bonjour

pour l'un de ses chantiers, une societé a des besoins en ouvriers qualifiés durant les mois de Janvier à Avril comme indiqué dans le tableau suivant

Mois______Janv___Fev___Mar___Avr
Ouvriers__4_______6____7_____4

Les ouvriers travaillent sur le chantier sur une base mensuelle. On supposera que 3 ouvriers qualifiés
sont déjà presents sur le chantier fin Decembre et que l'on doit conserver sur le chantier exactement 3 ouvriers qualifiés debut Mai.
Le probleme consiste à determiner le nombre d'ouviers qualifiés à avoir sur le chantier chaque mois de façon a minimiser les couts tout en respectant les conditions suivantes :

-regles et couts de transfert : la societé ne peut embaucher au maximum que 2 ouvriers supplémentaires en debut de chaque mois. De mme, elle ne peut débaucher qu'au plus 2 ouvriers en debut de chaque mois.
Embaucher un ouvrier sur le chantier cout 1000€ et le debaucher coute 2000€

-Excedent et déficit d'ouvrier : La société subit un cout de 2000€ par mois pour tout ouvrier excédentaire par rapport aux besoins. En cas de déficit, ce sont les ouvriers presents qui assurent les besoins par du travail supplémentaire. Cependant le temps de travail supplémentaire ne peut depasser 25% du travail régulier


On me demnde de formuler ce probleme comme une probleme de recherche de chemin de valeur minimale.
Indications : Definir pour chaque mois autant de sommets qu'il y a de possibilités en nombr d'ouvriers presents sur le chantier
On me demande de definir le graphe en omettant tout sommet inutile et de justifier

le probleme c'est que je suis perdue et je narrive pas a retenir les informations essentielles pour construire le graphe

[fatal_error]

salut,

donc ton graphe il a des noeuds et des arretes.
Posons J1, le noeud qui represente le mois de Janvier avec un seul ouvrier (c'est pas possible, mais c'est pour lexemple).
Posons J2, le noeud qui represente le mois de Janvier avec deux ouvriers.
etc...
Idem avec F1 (pour février).
La liaison evidente est que de J2 a F1, tu as killé un ouvrier. Donc sur l'arc, tu peux ecrire le cout de la transition. Jor la je crois que tu perds 2000 €.
(Bien sur en vrai, cette transition nest pas possible car tu ne peux pas avoir un seul ouvrier sur le chantier!(il en faut 6)).

Bref, les laisons, c'est les couts a lentreprise, et les noeuds, c'est le nombre d'ouvrier pour un certain mois.