Recherche opérationnelle

Les statistiques de la qualité :


Une simulation d'usinage pour relier dessin de définition et les statistiques de la qualité.

Un nouvel ordonnancement utilisant la méthode OPT les PQR arbres et les algorithmes génétiques


Le wap : transmètre des informations sur le terrain
recherche opérationnelle
Algorithme hongrois (Konig Egervary). Affectation de personnes à des tâches avec minimisation du coût total.

Les files d'attente
Les files d'attente


présentez moi
votre projet

algo hongrois

Cet algorithme est prévu pour minimiser une somme.

Exemple de problème affectation de coût minimal Un conseil municipal a décidé de favoriser trois entrepreneurs A, B et C susceptibles de fournir des produits x, y et z, à des prix donnés par le tableau suivant :
Produit x Produit y Produit z
A 1 MF 2 MF 3 MF
B 1 MF 4 MF 4 MF
C 1 MF 3 MF 5 MF
Comment acheter les produits au moindre coût ? On cherche à associer un produit différent à chaque entrepreneur de façon à minimiser la somme des coûts : il s'agit donc de choisir 3 éléments dans la matrice
1 2 3
1 4 4
1 3 5
de façon que chaque ligne et chaque colonne contienne un élément choisi, et que la somme des éléments choisis soit la plus petite possible.

détail de l'algorithme :

1 on soustrait ligne par ligne et colonne par colonne le plus petit élément.

2 si on peut affecter un zéro par ligne et par colonne on a la solution optimale

3 sinon on choisit au hasard une affectation de 0. Ces 0 choisis sont dits 0 encadrés ; les autres sont dits 0 barrés

4 marquer toute ligne n'ayant pas de 0 encadré.

5 marquer toute colonne ayant un 0 barré dans une ligne marquée

6 marquer toute ligne ayant un 0 encadré dans une colonne marquée

7 revenir à 4 jusqu'à marquage impossible

8 tracer un trait sur les lignes non marquées et les colonnes marquées

9 prendre le plus petit chiffre du tableau restant et le retrancher de tous les éléments non rayés et l'ajouter aux éléments rayés deux fois.

10 reprendre à 2

Utilisation d'excel

J'ai créé un classeur Excel utilisant cet algorithme d'affectation pour une matrice de 10*10. C'est un document semi automatique : il fait le marquage et les calculs et vous faites l'étape 2 simplement à la souris.

La première chose à faire est de remplir la matrice des coûts. Les valeurs saisies il faut choisir un format pour les cellules qui seront solution (c'est ici la cellule rouge). Tout est prêt alors on se lance en choisissant le bouton minimiser ou maximiser.

Ce lancement copie les valeurs dans l'onglet intermédiaire et alors on se trouve devant un écran comme celui-ci.

Les points représentent les 0 à choisir. Il ne doit y en avoir qu'un seul par ligne et par colonne. Pour effacer les surnuméraires, il suffit de cliquer dans la cellule. Le choix est souvent simple. Par exemple dans la colonne 1 il y a deux possibilités, mais on voit que dans la cinquième ligne, il y a plusieurs points donc on va effacer le premier.

Après quelques boucles on trouve une solution (on remarque le coût indiqué en bas à droite) :

Pour télécharger le classeur, utilisez le système ci-dessous. C'est un outil de micro-paiement qui, en vous faisant appeler un numéro surtaxé vous permet d'obtenir un code d'accès au document pour moins de deux euros. Cela me permet de rentabiliser en partie la maintenance de mon site, merci.
Le document chargé est modifiable, les macros sont visibles et il ne contient aucun mot de passe.

Ce document contient aussi un onglet faisant des calculs relatifs aux files d'attente.

Logo
United States
Entrez votre code d'accès - Enter your access code


If your country is not listed, click here
AlloPass http://www.allopass.com

compilation qualité

Contactez-moi pour tout projet du plus modeste au plus évolué.

files d'attente

les files d'attente

cas de présence des files d'attente : un péage d'autoroute ou les caisses d'un supermarché la poste ou la sécurité sociale
les paramètres sont nombreux :

  • les caisses d'un supermarché,
  • les péages d'autoroute,
  • les guichets SNCF, Poste...

Mais cela peut être aussi :

  • un service de maintenance,
  • un atelier de production,
  • les appels entrants dans un centre d'appel

Le cas présenté ici est le cas classique où le taux d'arrivée est constant et ou le nombre d'entrées ou de sorties par unité de temps suit une loi de poisson.

La première chose à fair lorsque l'on va faire une étude de files d'attentes c'est de définir une unité de temps : seconde, minute, heure, jour...

Une autre chose importante c'est de considérer des périodes de temps où le nombre d'unités se présentant dans le système reste le plus stable possible.

Mettons nous dans le cas d'un magasin où il rentre 10 clients par minute sur une période de 4 heures tous les jours : combien de caissières doit il faire travailler pendant cette période. Prenons comme référence l'heure, il rentre donc 600 clients / heure, on reporte ce nombre L2C1. Il faut maintenant estimer combien une caissière est capable de servir de clients en une heure. Pour ce faire il faut prendre garde à dire : hier elle a travaillé 4 heures et servi 120 clients donc elle sert 30 clients à l'heure. En effet, si elle a effectivement servi 120 clients en 4 heures il ne s'est pas présenté de clients pendant 3 périodes de 5 minutes, son taux de service est donc 120/3,75=32 . Une autre manière de parvenir à ce chiffre est de calculer le temps moyen de service d'un client puis de diviser 1 heure par ce temps en heures. Ce nombre va être mis en L2C2. Vous savez maintenant que vous devez ouvrir au moins : 600/32 = 18.75 soit 19 caisses pour éviter l'engorgement.

Que sait-on dans ce cas là :

le nombre de caisses où il n'y a personne est de 0.25/19 ce qui correspond à peu près à 50secondes par caisse et par heure.

Le nombre de personnes dans la file d'attente est de 70 L6C3 (3,68/caisse) auquel il faut rajouter la personne en train de se faire servir pour avoir le nombre total d'unités dans le système L7C3.

et le nombre de personnes dans la file va donner le temps moyen d'attente L8C3 ici 7 minutes.

Maintenant voyons un application de ce tableau :

Supposons que si le temps d'attent est trop grand 10 minutes par exemple (soit 10/60=0.166 heures L13C3) alors une proportion de clients 1/3=0.33333 L15C3 déposent leurs achats et quittent le magasion celui-ci perd sa marge de 11F L12C3

L2c1 le taux d'arrivée le nombre moyen de voitures arrivant dans la zone de péage par unité de temps.

L2C2 : le débit moyen d'un poste de péage

L2C3 : le nombre de postes de péages,

L3C2 : L2C1/L2C2 = nombre d'arrivants/débit d'un poste = nombre moyen de postes occupés

L4C2 : la probabilité qu'il ny ait aucune voiture à tous les postes de péage

L5C3 le nombre moyen de péages inoccupés

L6C3 : le nombre moyen de personnes attendant de payer.

le taux d'arrivée dans le système l
la longueur de la filev
le nombre de stations (guichets) s le taux de service est considéré le même pour chaque station
m=1/temps moyen de service d'une station
la probabilitéqu'une unité soit servie courbe 3d

courbe 3d