Ensait - A3 - Recherche Opérationnelle

Date: DS du 14/11/2003

Durée : 2 heures. Tous documents autorisés.
L'usage d'un ordinateur (et des programmes indiqués en cours) est recommandé.
Le listing des calculs fait sur ordinateur sera joint (deux pages par feuille, folioté).
Le commentaire écrit fera des références précises à cette feuille de calcul.

1 Optimisation en dimension 2

Une entreprise peut fabriquer deux sortes de tissus : X et Y, à partir de fils C1, C2, T. Les stocks permettent de faire bobines pour le fil C1, bobines pour le fil C2 et bobines pour le fil T. Produire cent mètres du premier tissu utilise bobines de fil C1, bobines de fil C2 et bobines de fil T. Produire cent mètres du deuxième tissu utilise bobines de fil C1, bobines de fil C2 et bobines de fil T. On se demande quelle est la production optimale en estimant que les ventes permettront de dégager un bénéfice de 4 € par mètre pour le tissu X et de 5 €  par mètre pour le tissu Y.

1. Écrire les inéquations décrivant les contraintes. Représenter l'ensemble des fabrications possibles.
   1. On prend pour inconnue les quantités produites (unité = cent mètres). La question posée revient à déterminer
      

   2. On utilise les utilitaires fournis pour tracer l'ensemble des points acceptables. Comme il se doit, cet ensemble est convexe.

   Figure 1: L'ensemble des points acceptables.

   

2. Résoudre le problème par la méthode du simplexe (détailler les étapes).
   1. On commence par numéroter les variables, obtenant :
      

   2. Puis on met en équations, introduisant de nouvelles variables.
      

   3. Comme l'origine est un point acceptable pour le système initial, il n'est pas nécessaire d'introduire des variables spéciales et l'algorithme ne comportera qu'une seule phase. On part donc de l'origine:
      

   4. On déroule les calculs:
      
      
      
      

   5. Le résultat final est donc :
      
      La décision recommandée est donc : mètres du premier tissu, mètres du second. Et le bénéfice espéré est 5400 € .

   Figure: La décision recommandée.

   

3. Déterminer quelles sont, parmi les contraintes du problème, celles qui sont réellement limitatives quant aux bénéfices possibles. Déterminer quel est le prix maximal acceptable pour la relaxation de l'une de ces contraintes ?
   1. Les contraintes effectivement contraignantes sont celles qui déterminent le sommet optimal. Ici, les contraintes 3 et 4, portant sur C1 et C2.
   2. Pour déterminer la valeur de rachat de la contrainte (3), on maximise le système obtenu en supprimant cette contrainte. On obtient les résultats suivant (dans lesquels les variables auxiliaires ont été renumérotées) :
      
      
      
      

   3. On procède de même pour la contrainte (4).
      
      
      
      
      
      
      

   4. En résumé: la relaxation de la première contrainte permettrait un bénéfice supplémentaire de 100 €, et la relaxation de la deuxième contrainte un bénéfice supplémentaire de 363 €. Cette relaxation ne vaut évidemment pas plus que le bénéfice supplémentaire attendu.
      

   5. Une étude sérieuse devrait prendre en compte les "risques commerciaux", c'est à dire utiliser une description probabiliste des bénéfices (qui dépendent des prix auxquels se feront les ventes futures) et non pas un chiffrage déterministe.
4. Après coup, on constate que les deux tissus se sont vendus en dégageant un bénéfice de 6 €  par mètre. A-t-on lieu d'être satisfait de la décision prise à la question 2 ?
   1. La question n'est pas de constater que le bénéfice réel est supérieur au bénéfice espéré, mais de se demander si ce bénéfice n'aurait pas été supérieur avec une autre décision.
   2. Graphiquement, on constate que les droites sont parallèles à l'un des côtés du simplexe. Maximiser la constante s'obtient en choisissant n'importe quel point entre , et : la décision proposée reste la décision optimale.

2 Optimisation en dimension 3

Maximiser :

1. On numérote les variables et le système devient:
   

2. La mise en équations fait apparaître 5 variables associées aux contraintes et deux variables spéciales (puisque deux contraintes ne sont pas vérifiées par l'origine du système). L'objectif de la première phase est d'arriver en , c'est à dire à un point vérifiant toutes les contraintes.
   
   En appliquant l'algorithme, il vient :
   
   
   
   

3. L'objectif de la première phase était de localiser un sommet tel que , c'est à dire un sommet faisant partie du domaine acceptable du problème posé (ici, le point 4, 6, 7). On réécrit le problème sans les variables spéciales, obtenant :
   
   On constate que les dérivées partielles de la fonction de bénéfice sont toutes négatives : le maximum est atteint et il n'y a plus rien à faire.
   Remarque : l'algorithme utilise un tirage au sort chaque fois qu'il y a une décision à prendre. Une autre exécution donnerait une répartition différente du travail entre les deux phases.
4. Finalement, la décision recommandée est , et le bénéfice espéré se monte à .

3 Optimisation d'une file d'attente

Dans une certaine entreprise, la valeur ajoutée par ouvrier et par heure est de 100 €. La journée de travail est de 7 heures. Les ouvriers doivent passer de temps à autre au service du personnel. On modélise leurs inter-arrivées par un processus de Markov avec (quatre arrivées par heure en moyenne). Le temps de traitement de leur demande par l'employé présent est modélisé par un processus de Markov avec (cinq traitements par heure en moyenne). Le salaire journalier d'un employé est 72 €.

1. Quel est le temps moyen de passage d'un ouvrier au service du personnel ? Le débit résiduel est . Donc le temps passé total est de une heure.
2. Quel est le coût journalier du processus pour l'entreprise ? Salaire de l'employé : €(par jour). Il y a en moyenne visites, soit heures de production en moins, et un coût de €par jour.
3. On se propose d'optimiser ce processus en embauchant un ou plusieurs employés supplémentaires. Déterminer la fonction de coût pour l'entreprise. En déterminer le minimum.
   1. En appelant le nombre total d'employés et en assimilant le service à un serveur unique, de débit , on obtient  :
      
      
      
   2. On détermine le minimum par essais successifs.
      .

      1	2	3	4	5
      2872	611	470	463	493

      .
4. Quelle est la décision "industrielle" à prendre ?
   1. Porter le service à trois personnes, en y affectant deux nouvelles personnes.
   2. Autant, en effet, l'hypothèse Markov sur les inter-arrivées semble réaliste, autant la même hypothèse sur les traitements est discutable. Il est bien rare qu'un service soit réellement markovien. En particulier, il est clair que l'indépendance supposée entre les arrivées et les services est un moyen de simplifier les calculs plus qu'une réalité. Enfin, le regroupement de plusieurs services markoviens n'est pas réellement markovien.
   3. Les incertitudes de modélisation ne permettent donc pas d'affirmer que est meilleur que . Un choix "conservatif" est donc à recommander.
5. Quel sera alors le taux d'occupation des employés du service ? Comparer avec le taux actuel.
   1. Avec un employé, la capacité de traitement est 5 par heure. Le nombre de cas effectivement traités dépend des arrivées et vaut 4 par heure, soit .
   2. Avec trois employés, la capacité de traitement passe à par heure, tandis que le nombre de cas à traiter reste inchangé. Le taux d'occupation devient .
   3. Le dimensionnement des services ne doit donc pas se fonder sur le taux d'occupation de ces services, mais sur une rentabilisation de l'ensemble du processus.