Problème d’affectation dans la programmation linéaire: introduction et modèle d’affectation

Le problème d’affectation est un type particulier de problème de programmation linéaire qui traite de l’affectation individuelle des différentes ressources aux différentes activités. Il le fait de telle sorte que le coût ou le temps nécessaire au processus soit minimal et que le profit ou la vente soit maximal. Bien que ces problèmes puissent être résolus par la méthode simplex ou par la méthode de transport, le modèle d’affectation offre une approche plus simple de ces problèmes.

Dans une usine, un superviseur peut avoir six travailleurs disponibles et six emplois à licencier. Il devra décider quel travail devrait être confié à quel travailleur. Problème forme une à une base. C'est un problème de mission.

1. Modèle d'affectation:

Supposons qu'il y a n facilités et n emplois, il est clair que dans ce cas, il y aura n assignations. Chaque établissement ou chaque travailleur peut effectuer chaque travail, un à la fois. Mais il devrait exister une procédure précise selon laquelle la cession devrait être effectuée de manière à maximiser le profit ou à minimiser le coût ou le délai.

Dans le tableau, Co _ij est défini comme le coût lorsque le j ^e travail est attribué au i ^e travailleur. On peut noter ici qu'il s'agit d'un cas particulier de problème de transport lorsque le nombre de lignes est égal au nombre de colonnes.

Formulation mathématique:

Toute solution réalisable de base d’un problème d’affectation consiste en (2n - 1) variables dont les variables (n - 1) sont zéro, n est le nombre d’emplois ou le nombre d’installations. En raison de cette forte dégénérescence, si nous résolvons le problème par les moyens de transport habituels, la tâche sera longue et complexe. Ainsi, une technique distincte est dérivée pour cela. Avant de passer à la méthode absolue, il est très important de formuler le problème.

Supposons que x _jj soit une variable définie comme

1 si le ^ième travail est attribué à la j ^ème machine ou installation

0 si le ^ième travail n'est pas affecté à la j ^ième machine ou installation.

Maintenant, lorsque le problème se pose, une base ou un travail doit être attribué à une installation ou à une machine.

Le coût total de la mission sera donné par

La définition ci-dessus peut être développée en modèle mathématique comme suit:

Déterminez x _ij > 0 (i, j = 1, 2, 3… n) afin de

Soumis à des contraintes

et x _ij est zéro ou un.

Méthode pour résoudre le problème (technique hongroise):

Considérons la fonction objectif du type de minimisation. Les étapes suivantes sont impliquées dans la résolution de ce problème d’affectation,

1. Localisez le plus petit élément de coût dans chaque ligne du tableau de coûts donné en commençant par la première ligne. Maintenant, ce plus petit élément est soustrait de chaque élément de cette ligne. Nous aurons donc au moins un zéro dans chaque ligne de cette nouvelle table.

2. Après avoir construit la table (comme à l'étape 1), prenez les colonnes de la table. À partir de la première colonne, localisez le plus petit élément de coût dans chaque colonne. Maintenant, soustrayez ce plus petit élément de chaque élément de cette colonne. Après avoir exécuté les étapes 1 et 2, nous obtiendrons au moins un zéro dans chaque colonne du tableau des coûts réduits.

3. Maintenant, les affectations sont effectuées pour la table réduite de la manière suivante.

(i) Les lignes sont examinées successivement jusqu'à ce que la ligne avec exactement un (zéro) zéro soit trouvée. Une assignation est faite à ce zéro unique en mettant un carré □ autour de lui et dans la colonne correspondante, tous les autres zéros sont barrés (x) car ils ne seront pas utilisés pour effectuer une autre assignation dans cette colonne. L'étape est effectuée pour chaque ligne.

(ii) L'étape 3 (i) est maintenant effectuée sur les colonnes comme suit: - les colonnes sont examinées successivement jusqu'à ce qu'une colonne contenant exactement un zéro soit trouvée. Désormais, l'attribution à ce zéro unique est effectuée en mettant le carré autour de celui-ci et, en même temps, tous les autres zéros des lignes correspondantes sont barrés (x). Une étape est effectuée pour chaque colonne.

(iii) Les étapes 3, (i) et 3 (ii) sont répétées jusqu'à ce que tous les zéros soient marqués ou barrés. Maintenant, si le nombre de zéros marqués ou les assignations effectuées sont égaux au nombre de lignes ou de colonnes, la solution optimale a été atteinte. Il y aura exactement une seule affectation dans chaque colonne ou des colonnes sans aucune assignation. Dans ce cas, nous allons passer à l’étape 4.

4. A ce stade, tracez le nombre minimum de lignes (horizontales et verticales) nécessaires pour couvrir tous les zéros de la matrice obtenue à l'étape 3. La procédure suivante est adoptée:

(i) Coche (

(ii) Maintenant, cochez (

(iii) Cochez maintenant toutes les lignes qui ne sont pas déjà marquées et qui ont une affectation dans les colonnes marquées.

(iv) Toutes les étapes, à savoir (4 (i), 4 (ii), 4 (iii)) sont répétées jusqu'à ce qu'il ne soit plus possible de marquer des lignes ou des colonnes.

(v) Maintenant, tracez des lignes droites qui passent à travers toutes les lignes non marquées et les colonnes marquées. On peut aussi remarquer que dans une matrice nxn, toujours moins de 'n' lignes couvriront tous les zéros s'il n'y a pas de solution entre eux.

5. À l’étape 4, si le nombre de lignes dessinées est égal à n ou au nombre de lignes, c’est la solution optimale sinon, passez à l’étape 6.

6. Sélectionnez le plus petit élément parmi tous les éléments non couverts. Maintenant, cet élément est soustrait de tous les éléments non couverts et ajouté à l'élément qui se trouve à l'intersection de deux lignes. C'est la matrice pour les nouvelles affectations.

7. Répétez la procédure à partir de l'étape (3) jusqu'à ce que le nombre d'affectations devienne égal au nombre de lignes ou au nombre de colonnes.