Registres canoniques. Forme canonique d'un problème de programmation linéaire. Méthode graphique pour résoudre un problème de programmation linéaire

Introduction 3

1 Le problème de l'affectation. méthode hongroise 4

1.1 Problème d'affectation 4

1.2 Méthode hongroise pour résoudre le problème d'affectation 7

2 Résoudre le problème d'affectation à l'aide de la méthode hongroise 15

Conclusion 20

Références 21

Le problème d'affectation est un cas particulier du problème de transport classique et, par conséquent, est un problème de type transport.

Le problème des transports est le problème le plus économiquement le transport d'un produit homogène ou interchangeable du point de production (stations de départ) aux points de consommation (stations de destination) est la tâche particulière la plus importante programmation linéaire, qui a de nombreuses applications pratiques non seulement pour les problèmes de transport.

Par rapport au problème d'affectation méthode simplexe n'est pas efficace, puisque l'une de ses solutions de base admissibles est dégénérée. Les spécificités du problème d'affectation ont permis de développer méthode efficace sa solution est connue sous le nom de méthode hongroise.

Supposons qu'il y ait n travaux divers, dont chacun peut être exécuté par n'importe lequel des n attiré des artistes. Le coût de l'exécution du ième travail j - m est connu de l'interprète et est égal à C i j (en unités monétaires conventionnelles). Il est nécessaire de répartir les interprètes entre les œuvres (attribuer un interprète à chaque œuvre) de manière à minimiser les coûts totaux associés à la mise en œuvre de l'ensemble des œuvres.

En recherche opérationnelle, le problème formulé ci-dessus est connu sous le nom de problème d’affectation. Introduisons les variables X ij , où X ij prend la valeur 1 dans le cas où le i-ième travail est effectué jème interprète, et la valeur est 0 dans tous les autres cas, i,j = 1, n. Alors la limitation

garantit que chaque œuvre est exécutée par un seul interprète, limitation

garantit que chaque interprète n’effectuera qu’un seul travail. Le coût de l'exécution de l'ensemble des travaux est égal à

Ainsi, le problème d’affectation peut s’écrire comme suit :

Le problème d'affectation (1) est un cas particulier du problème de transport classique, dans lequel il faut mettre. Dans ce cas, la condition signifie la satisfaction de l'exigence que les variables x et j soient entières. Cela est dû au fait que les puissances de toutes les sources et de tous les puits sont égales à l'unité, ce qui signifie que dans les limites autorisées solution entière Les valeurs des variables ne peuvent être que 0 et 1.

Comment cas particulier problème de transport classique, le problème d'affectation peut être considéré comme problème de programmation linéaire. Donc dans dans ce cas utiliser la terminologie et les résultats théoriques de la programmation linéaire.

Dans le problème d'affectation, les variables x et j peuvent prendre la valeur 0 ou 1. De plus, d'après (1), dans toute solution admissible seulement n les variables peuvent prendre la valeur 1. Ainsi, toute solution de base réalisable au problème d'affectation sera dégénérée.

Dans la pratique, il existe des problèmes d'affectation dans lesquels le paramètre est compris comme l'efficacité de l'exécution du ième travail j - m interprète. Dans ces cas, il est nécessaire de répartir le travail entre les interprètes de manière à ce que l'efficacité totale de leur mise en œuvre soit maximale, c'est-à-dire

(2)

lorsque le maximum est recherché dans le cadre des restrictions spécifiées au (1).

Possibilités Les problèmes d'affectation (1) peuvent être commodément représentés par la matrice , appelée matrice des coûts. Supposons que Et AVEC= (c i j) - deux matrices de coûts dont les éléments sont liés comme suit :

où sont quelques constantes. Ainsi, pour obtenir la matrice AVEC* nécessaire pour les éléments de chaque i-ème ligne de la matrice AVEC ajouter le nombre d,-, et aux éléments de chacun j - G o colonne - nombre C. Dans ce cas, si X - solution acceptable satisfaisant aux restrictions de (1), et

alors, compte tenu des restrictions de (1) sur le type d'égalité, nous avons

Ainsi, pour toute solution réalisable X les valeurs de fonction correspondantes différeront d'une constante oui, qui ne dépend pas de X . Par conséquent, s’il y a deux problèmes d’affectation avec le même ensemble G des solutions réalisables et fonctions cibles En conséquence, leurs solutions optimales coïncident. Il est facile de vérifier que le problème classique du transport a une propriété similaire.

Si le problème d'affectation est un problème de maximisation, c'est-à-dire le maximum est recherché fonction objectif sur un plateau G solutions admissibles, qui sont spécifiées par le système de restrictions de (1), puis son problème de minimisation équivalent

(3)

ne peut formellement être classé comme un problème d'affectation, puisque les coefficients de sa fonction objectif ne sont pas positifs. Cet écart peut être surmonté en remplaçant (3) par le problème équivalent

(4)

dans lequel

parce que dans ce cas pour tout le monde il y a des inégalités.

1.2 Méthode hongroise pour résoudre le problème d'affectation

Lors de la discussion de la formulation du problème d'affectation, il a été noté que ce problème est un cas particulier du problème de transport classique et, par conséquent, est un problème de type transport. Lorsqu'elle est appliquée au problème d'affectation, la méthode du simplexe n'est pas efficace, puisque toute solution de base réalisable est dégénérée. Les spécificités du problème d'affectation ont permis de développer une méthode efficace pour le résoudre, connue sous le nom de méthode hongroise.

L'essence de la méthode hongroise est la suivante : en ajoutant des nombres trouvés d'une certaine manière à certaines colonnes et en leur soustrayant certains nombres, on obtient un système de zéros dits indépendants. Un ensemble de zéros est appelé un système de zéros indépendants si deux zéros (ou plus) ne se trouvent pas sur la même ligne (dans une ligne ou une colonne). Si le nombre de zéros indépendants est égal à n, alors, en prenant les variables correspondantes x ij égales à 1 et toutes les autres égales à 0, selon l'énoncé 2, nous obtenons le plan d'affectation optimal.

L'algorithme de la méthode hongroise consiste à étape préliminaire et pas plus de (n-2) itérations répétées séquentiellement. Au stade préliminaire, si un problème maximum est résolu, il est converti en un problème minimum équivalent. Au même stade, un système de zéros indépendants est identifié. Chaque itération suivante vise à augmenter le nombre de zéros indépendants d'au moins 1. Dès que le nombre de zéros indépendants k devient égal à la dimension matricielle (k=n), le problème est résolu.

Plan optimal l'affectation sera déterminée par la position des zéros indépendants à la dernière itération.

1. Volkov I.K., Zagoruiko E.A. Recherche opérationnelle : Proc. pour les universités. 2ème bride / Edité par V.S. Zarubina, A.P. Krischenko. – M. : Uzd-vo MSTU im. N.E. Bauman, 2002. – 436 p.

2. Zaichenko Yu.P. Recherche opérationnelle : Proc. manuel pour les étudiants universitaires. – 2e éd., révisée. et supplémentaire – Kyiv : école Vishcha. Maison d'édition principale, 1979. 392 p.

3. I.A. Akulich. Programmation mathématique dans des exemples et des problèmes. - M. : « Lycée », 1986.- 319 p.

4. Sakovitch V.A. Recherche opérationnelle (méthodes et modèles déterministes) : un guide de référence. - Mn. : Plus haut. école, 1984.-256p.

5. Taha H. Introduction à la recherche opérationnelle : en deux livres. Livre 1,2 Per. de l'anglais - M. : Mir, 1985.

6. Khazanova L.E. Programmation mathématique en économie : Tutoriel. – M. : Maison d'édition BEK, 1998. – 141 p.

Algorithme de solution :

1. Nous résolvons le problème au minimum. Cible cette étape- obtenir le nombre maximum possible de zéros dans la matrice C. Pour ce faire, on retrouve l'élément minimum de la matrice C dans chaque ligne et on le soustrait de chaque élément de la ligne correspondante. De même, dans chaque colonne, nous soustrayons l'élément minimum correspondant.

Si non précisé matrice carrée, puis nous le rendons carré, en mettant les coûts égaux au nombre maximum dans la matrice donnée.

2. Si, après avoir terminé la première étape, il est possible d'effectuer des affectations, c'est-à-dire de sélectionner un élément nul dans chaque ligne et colonne, alors la solution résultante sera optimale. Si les rendez-vous n’ont pu être pris, passez alors à la troisième étape.

3. En utilisant le nombre minimum de lignes, on barre tous les zéros de la matrice et, parmi les éléments non barrés, on sélectionne le minimum, on l'ajoute aux éléments se trouvant à l'intersection des lignes et on le soustrait de tous les non barrés éléments. Ensuite, passez à l'étape 2.

La méthode hongroise est la plus efficace pour résoudre des problèmes de transport avec des volumes entiers de production et de consommation.

Exemple

Le problème d'affectation est un cas particulier du problème de transport, dans lequel ai = bj = 1. Par conséquent, il peut être résolu par des algorithmes de problème de transport. Considérons une autre méthode, plus efficace, compte tenu des spécificités modèle mathématique. Cette méthode s'appelle l'algorithme hongrois.

Il comprend les étapes suivantes :

1) transformation des lignes et des colonnes de la matrice ;

2) détermination du but ;

3) modification de la matrice transformée.

1ère étape. Le but de cette étape est d'obtenir le maximum possible d'éléments nuls dans la matrice C. Pour cela, soustrayez l'élément minimum de la ligne correspondante de tous les éléments de chaque ligne, et soustrayez l'élément minimum de la colonne correspondante de tous les éléments de chaque colonne.

2ème étape. Si, après avoir effectué la 1ère étape, un élément nul peut être sélectionné dans chaque ligne et chaque colonne de la matrice C, alors la solution résultante sera une affectation optimale.

3ème étape. Si une solution admissible composée de zéros n'a pas été trouvée, nous traçons alors le nombre minimum de lignes à travers certaines colonnes et lignes afin que tous les zéros soient barrés. Sélectionnez le plus petit élément non croisé. Nous soustrayons cet élément de chaque élément non barré et l'ajoutons à chaque élément se trouvant à l'intersection des lignes tracées.

Si après la 3ème étape solution optimale n'est pas atteint, alors la procédure de tracé de lignes droites doit être répétée jusqu'à ce qu'une solution acceptable soit obtenue.

Exemple.

Répartissez les ressources entre les objets.

Solution. 1ère étape. Les valeurs des éléments minimaux des lignes 1, 2, 3 et 4 sont respectivement 2, 4, 11 et 4. En soustrayant la valeur minimale correspondante des éléments de chaque ligne, on obtient

Les valeurs des éléments minimaux des colonnes 1, 2, 3 et 4 sont respectivement 0, 0, 5, 0. En soustrayant la valeur minimale correspondante des éléments de chaque colonne, on obtient

2ème étape. Aucun rendez-vous complet non reçu, il faut modifier la matrice des coûts.

3ème étape. Rayez la colonne 1, la ligne 3, la ligne 2 (ou la colonne 2). La valeur de l'élément minimum non croisé est 2 :

On le soustrait de tous les éléments non barrés et, en l'ajoutant à tous les éléments situés à l'intersection de deux lignes, on obtient

Répondre. Nous dirigeons la première ressource vers le 3ème objet, la seconde - vers le 2ème objet, la quatrième - vers le 1er objet, la troisième ressource - vers le 4ème objet. Coût de destination : 9 + 4 + 11 + 4 = 28.

Remarques. 1. Si la matrice d'origine n'est pas carrée, vous devez alors introduire des ressources fictives ou des objets fictifs pour rendre la matrice carrée.

Considérez l'exemple suivant. Soit cinq personnes pour effectuer cinq tâches différentes. Grâce aux données des rapports, nous savons combien de temps il faut à chacun pour terminer chaque tâche. Ces données sont présentées dans le tableau.

artistes interprètes ou exécutants
besoins

Dans ce cas, les valeurs​​représentent le temps passé par chaque employé à effectuer chacune des tâches, et les valeurs​​sont égales à 1 ou 0, et sont égales à 1 si l'employé i est affecté à travail j, et 0 dans tous les autres cas. Le problème se réduit donc à minimiser la fonction. programmation linéaire des itinéraires de coûts

sous réserve des restrictions suivantes.

Il est clair que si nous supprimons la dernière condition et la remplaçons par la condition

Il en résulte un problème de transport dans lequel tous les besoins et toutes les ressources sont égaux. Dans la solution optimale, tous sont soit un nombre entier, soit zéro, un étant le seul nombre entier possible. Ainsi, résoudre le problème des transports dans ces conditions conduit toujours à l’égalité.

Cependant, en raison de la dégénérescence des méthodes de résolution tâches de transport en cas de problèmes d'affectation, ils s'avèrent inefficaces. Pour toute affectation, les approvisionnements par ligne coïncident toujours automatiquement avec la demande par colonne et donc, au lieu de 2n-1, on obtient n valeurs non nulles. À cet égard, il est nécessaire de remplir la matrice avec n-1 valeurs de e, et il peut s'avérer que des valeurs non nulles déterminent la solution optimale, mais le contrôle ne la détecte pas, puisque les valeurs ​​de e sont mal placés.

La méthode de résolution du problème d'affectation repose sur deux théorèmes assez évidents. Le premier d’entre eux stipule que la solution ne changera pas si une constante est ajoutée ou soustraite d’une colonne ou d’une ligne de la matrice. Ce théorème est précisément formulé comme suit :

Théorème 1.

Si minimise

pour tout le monde, comme

puis minimise également la fonctionnalité

où devant tout le monde

Théorème 2.

Si tout est possible, il est possible de trouver un ensemble tel que

alors cette solution est optimale.

Le deuxième théorème est évident. Pour prouver le premier théorème, notons que

Du fait que les quantités soustraites de Z pour obtenir ne dépendent pas, elle atteint un minimum chaque fois que Z est minimisé, et vice versa.

La méthode de solution développée consiste à ajouter des constantes aux lignes et aux colonnes et à les soustraire des lignes et des colonnes jusqu'à ce qu'un nombre suffisant de valeurs devienne zéro, ce qui donne une solution égale à zéro.

Trouver une solution commence par soustraire le plus petit élément de chaque ligne puis de chaque colonne. Le tableau montre les résultats de l'exemple ci-dessus.

Tableau A)

artistes interprètes ou exécutants		déduit

Tableau B)

artistes interprètes ou exécutants
déduit

Au total, 10 unités ont été soustraites des colonnes et des lignes. Par conséquent, pour évaluer correctement toute solution obtenue à l'aide du tableau (B), il est nécessaire d'ajouter 10 unités au résultat

Tout d’abord, ils s’efforcent de trouver une solution qui inclut uniquement les cellules du tableau (B) qui contiennent zéro élément, car une telle solution, si elle peut être trouvée, sera la meilleure de toutes possibles. Il existe cependant des cas où plusieurs solutions ont la même qualité. Une solution acceptable est indiquée dans le tableau (B) entre parenthèses. Cependant, afin de déterminer si la solution peut être améliorée, l’algorithme suivant est appliqué.

Notons d'abord que toute soustraction supplémentaire d'une ligne ou d'une colonne, même si elle peut conduire à l'apparition de nouveaux zéros, conduit inévitablement à l'apparition d'éléments négatifs, de sorte que la solution zéro n'est plus nécessairement optimale. Cependant, les éléments négatifs peuvent être éliminés en ajoutant les numéros correspondants aux lignes ou aux colonnes. Par exemple, si vous soustrayez 2 de la colonne 1 du tableau (B), alors l'élément 2 apparaîtra dans la ligne 1. Si vous ajoutez maintenant 2 à la ligne 1, vous obtiendrez à nouveau une matrice avec des éléments non négatifs. Le défi est d'obtenir de nouveaux zéros de la manière spécifiée, mais en même temps, obtenez finalement une matrice contenant une solution composée uniquement de zéros. Il peut être prouvé que l’algorithme décrit ci-dessous apporte une solution à ce problème.

1. Tracez le nombre minimum de lignes horizontales et verticales se coupant le long au moins une fois tous les zéros. L'exécution de cette étape sur le tableau (B) donne le résultat dans le tableau 1.

Tableau 1

Notez que dans ce cas, seules quatre lignes sont utilisées et que les cellules nulles ne contiennent donc pas la solution optimale.

• 2. Sélectionnez le plus petit élément à travers lequel aucune ligne n'est tracée. Dans l'exemple, il s'agit de 1 dans la cellule (5,2).
• 3. Soustrayez ce nombre de tous les éléments à travers lesquels aucune ligne n'est tracée et ajoutez-le à tous les éléments à travers lesquels deux lignes sont tracées. Cet exemple produit le résultat présenté dans le tableau 2.

Tableau 2

Cette étape devrait entraîner l’apparition d’un zéro dans une cellule où il n’y en avait pas auparavant. Dans l'exemple considéré, il s'agit de la cellule (5,2).

4. Déterminez s’il existe une solution parmi le nouvel ensemble de zéros. Si aucune solution n'est trouvée (dans cet exemple, il n'y en a pas), revenez à l'étape 1 et effectuez toutes les étapes suivantes jusqu'à ce qu'une solution soit trouvée. En continuant à considérer cet exemple, nous obtenons le résultat présenté dans le tableau 3.

Tableau 3

Ce tableau contient déjà une solution, marquée entre parenthèses, qui a une valeur de 13, soit 1 de mieux que la solution réalisable d'origine. , .

Exemple 2.

Quatre étudiants et quatre types de travaux ont été présentés. Le tableau suivant correspond à la matrice de coûts de ce problème.

Effectuons la première étape de l'algorithme.

Nous soustrayons maintenant les coûts minimaux des éléments des lignes correspondantes.

Lors de la deuxième étape de l'algorithme, nous trouvons les valeurs minimales des colonnes et les soustrayons des éléments des colonnes correspondantes. En conséquence, nous obtenons la matrice présentée dans le tableau suivant.

DANS dernière matrice la disposition des éléments zéro ne permet pas d'attribuer un travail à chaque enfant. Par exemple, si nous chargeons Dasha de nettoyer le garage, la première colonne est exclue de tout examen ultérieur et il n’y aura alors aucun élément nul dans la ligne d’Alla.

• 1) Dans la dernière matrice, nous traçons le nombre minimum de lignes horizontales et verticales le long des lignes et des colonnes afin de rayer tous les éléments nuls.
• 2) Trouvez le plus petit élément non barré et soustrayez-le des éléments non barrés restants et ajoutez-le aux éléments situés à l'intersection des lignes tracées.

Dans le problème cet exemple trois lignes droites sont nécessaires, cela conduit au tableau suivant :

Le plus petit élément non barré est égal à 1. On soustrait cet élément des éléments non barrés restants et on l'ajoute aux éléments situés à l'intersection des lignes. En conséquence, nous obtenons la matrice présentée dans le tableau suivant.

La solution optimale présentée dans le tableau suggère que Dasha nettoie le garage, Katya tond la pelouse, Alla lave la voiture et Sasha promène les chiens. Valeur correspondante la fonction objectif est 1+10+5+5=21. La même valeur peut être obtenue en additionnant les valeurs de et et la valeur de l'élément le plus petit parmi tous ceux non barrés.

Il s'est avéré - graphique. Les sommets de gauche sont les développeurs, les sommets de droite sont les technologies (tâches). Les bords qui les relient indiquent à quel point le développeur le comprend. Ces chiffres, c'est-à-dire Le degré de maîtrise du développeur avec cette technologie est très important, mais nous y reviendrons un peu plus tard. En attendant, nous avons déjà correctement indiqué la direction dans laquelle ce problème est effectivement résolu :

3. Graphiques

Les bases mêmes des graphiques ont été décrites dans l'article (), je vais donc immédiatement passer à la terminologie liée à cette tâche :

Graphique biparti– un graphe dans lequel il existe une telle partition de l'ensemble des sommets en deux parties (parts) que les extrémités de chaque arête appartiennent à des parties différentes. Dans notre tâche, il existe également une division claire : certains sommets sont des développeurs, d'autres sont des tâches, et les connexions (efficacité de propriété) n'existent qu'entre les développeurs et les tâches.
Correspondance d'un graphe non orienté G est un sous-ensemble M de ses arêtes E, choisi de telle sorte qu'aucune arête de M ne soit adjacente, c'est-à-dire n'ont pas de sommet commun. En ce qui concerne notre problème, un synonyme pour cela sera "rendez-vous", afin que chaque développeur impliqué assume une tâche distincte. Et il ne s’est pas avéré que deux développeurs travaillaient sur un seul problème ou qu’un « pauvre garçon » était responsable de deux tâches.

En théorie des graphes, notre problème, curieusement, s'appelle Tâche sur les affectations (ZN). =) C'est un cas particulier du problème de trouver la correspondance maximale. En fait, nous nous efforçons d'utiliser les ressources autant que possible afin de pouvoir travailler simultanément sur nombre maximum technologies, donc, en termes de graphiques - nous essayons de trouver la « correspondance maximale », de créer quantité maximale paire développeur-tâche.

4. Correspondance maximale

Pour nous faciliter la vie, nous ne prêtons pas encore attention aux capacités des gens. Nous voulons juste trouver un emploi pour tout le monde. Ce ne sera pas un problème de proposer aux premiers développeurs qui se présenteront de travailler avec la technologie qu’ils connaissent. En continuant dans le même esprit, nous répartirons plusieurs tâches supplémentaires, mais il est peu probable que l'appariement ainsi construit soit maximal. Une situation comme celle représentée sur la figure est possible :

Comment augmenter les matchings (affectations) ?

Sélectionnons un développeur inactif à qui aucune tâche n'a encore été assignée. Voyons ce qu'il pourrait gérer, c'est-à-dire technologies qui lui sont familières. Si vous en trouvez un gratuit parmi eux, tant mieux, c’est ce que nous recherchions. Nous nommons. Que se passe-t-il si la tâche est déjà « prise » par un autre développeur ? Essayons qu'un développeur occupé trouve une autre technologie gratuite, car dans ce cas, nous attribuerions celle-ci à notre service inactif. En général, du haut du développeur inactif ou du développeur à qui on essaie de réattribuer une tâche, on parcourt toutes les technologies qui lui sont familières pour les gratuites :

• si vous en trouvez un gratuit, la recherche est terminée
• si la tâche a déjà été confiée à quelqu'un, alors après avoir parcouru ce bord correspondant, nous essaierons de « réattribuer » la technologie au développeur participant à cette mission

Lors de ce parcours du graphe, on tente de passer d’un « développeur peu impliqué » à une « tâche libre ». Ainsi, la recherche « s’étend » dans l’arborescence suivante :

Ajoutons un peu plus de terminologie issue de la théorie des graphes, en termes simples :

Dessus exposé– il s’agit d’un sommet qui n’est pas impliqué dans la correspondance en cours. Ceux. soit "développeur non engagé" soit "tâche gratuite".
Chaîne alternée est une chaîne dont les bords se trouvent alternativement ou non dans une correspondance. (... - maîtrise de la technologie - tâche assignée - maîtrise de la technologie - tâche assignée - ...)
Arbre alternatif– un arbre constitué de chaînes alternées
Chaîne augmentée– il s’agit d’une telle chaîne alternée dont les sommets initial et final sont exposés. C'est le nom de ce que nous recherchons ! =)
Arbre d'augmentation- respectivement, un arbre dont au moins une des branches est une chaîne augmentée.

Nous avons donc trouvé un moyen d’augmenter la correspondance, en essayant d’obtenir le maximum. Il faut construire un arbre alterné. Lorsqu'il devient augmenté, recherchez les chaînes augmentées de « développeur non impliqué » à « tâche gratuite », puis « réaffectez » les tâches le long de celles-ci. Ceci est bénéfique car augmente le nombre de « tâches en traitement » de 1 :

Maintenant nous pouvons utiliser le plus grand nombre technologies dans le projet. Il est temps de prendre en compte une autre condition importante du problème qui nous est posé : l'efficacité de la propriété technologique. Nous voulons vraiment optimal attribuer des tâches à tout le monde.

5. Méthode hongroise.

Trouver une solution avec une efficacité totale maximale (coût). Cela ressemble, dans un sens, au problème de emballage optimal sac à dos Ça me fait réfléchir. Maintenant, si seulement nous avions la possibilité d’agir selon le principe des « algorithmes gloutons ».

Nous commencerions par attribuer des tâches à tous les développeurs, jusqu'en bas, en fonction de leurs capacités maximales. Si tous les développeurs parvenaient à répartir immédiatement les tâches, tant mieux. Mais cela n'arrive pas souvent. Et si deux personnes possédaient une connaissance optimale de la même technologie, qui l’obtiendrait et que faire dans cette situation ? L'un des développeurs devra trouver une autre tâche gratuite qui correspond également le mieux à ses capacités. Si à l'heure actuelle ( exigences maximales) conditions il n'y a pas de tâche gratuite, nous devrons alors essayer d'en trouver une parmi les tâches, en réduisant d'abord un peu nos exigences. Comment réduire artificiellement les capacités des développeurs dans le graphique. Si dans de telles conditions nous trouvons une tâche gratuite, nous obtiendrons un arbre d'augmentation. "Changeons" le long de la chaîne correspondante, après quoi ce sera +1. Et nous continuerons à nommer de cette manière optimale jusqu'à ce que nous trouvions du travail pour tout le monde.

La stratégie est claire.

Nous avons presque compris le principe de l'algorithme hongrois. Mais comment construire une solution basée sur le principe des « algorithmes gloutons » : attribuer des capacités maximales jusqu'au bout, puis baisser légèrement les capacités et ajouter de nouvelles tâches à la considération, les attribuer jusqu'au bout, les baisser... etc. ? Comment évaluer les capacités et l’optimalité de la mission en cours ?

Tout le « truc » de cet algorithme est le suivant. Le graphique ne nous donne qu'un seul paramètre - l'efficacité du développeur à résoudre un certain problème, qui est indiqué sur les bords. Cette valeur est attribuée aux paires développeur-tâche. Nous allons « diviser » (séparer les paires) ces quantités en deux. Ajoutons artificiellement deux paramètres supplémentaires. Certaines valeurs seront attribuées aux sommets des tâches, d'autres aux sommets des développeurs.

Je vais essayer de donner cette interprétation :

• nous les indiquerons aux développeurs "capacités", disons en unités de « forces », indiquant simplement avec quelle efficacité nous pouvons les utiliser ou les avons utilisées.
• pour les tâches nous les indiquerons "étudié", ou, pour ainsi dire, « excès d’attention ». Nous mesurerons également ce paramètre en « force ». Une surabondance d’attention portée à une tâche se produit dans la situation suivante. Si nous avons « sous-chargé » un développeur, c'est-à-dire il est capable de résoudre un problème avec 5, mais il n'en a obtenu que 3. Il lui reste alors 2 « forces » qu'il peut, en principe, consacrer à certaines des tâches qui lui sont familières. Courir entre les bureaux, consulter par téléphone, donner des conseils aux acteurs de la technologie qu'il aime.

Ainsi, on « divise » les valeurs​​indiquées sur les arêtes en 2 valeurs attribuées aux sommets : efficacité de résolution du problème = capacité du développeur + connaissance du problème. En principe, c'est logique. Plus le développeur est compétent ou plus la technologie est connue, mieux cette partie du projet sera mise en œuvre. Plus efficace.

Au final, une fois la solution trouvée, nous ne prendrons bien sûr en compte que les valeurs sur les bords, mais maintenant cette « astuce » va nous aider à trouver la solution. =)

6. Description de l'algorithme

Initialisons le graphique. Être " optimistes obstinés», pour chaque développeur nous calculerons sa « capacité » maximale pour les technologies qui lui sont familières, et lui attribuerons ce numéro. Chacun aime faire le genre de travail pour lequel il est le mieux adapté. On ne sait encore rien des tâches, on initialise donc leur « connaissance » à zéro.

Lors de la recherche d’une « tâche gratuite » pour un « développeur non impliqué », nous allons désormais nous limiter aux seuls (appelons-les) les bords optimaux du graphe, c’est-à-dire ceux pour lesquels l’égalité vaut : efficacité de résolution de problèmes (edge) = capacité du développeur (sommet) + connaissance du problème (sommet).

Ensuite, nous procédons de la même manière que lors de la recherche de la correspondance maximale. Nous récupérons les développeurs inactifs un par un et, à la recherche de tâches gratuites pour eux, nous construisons un arbre alterné (constitué de chaînes alternées), mais uniquement le long des bords optimaux. Il y a alors 2 situations possibles :

• Nous avons réussi à trouver une tâche gratuite. L'arbre est devenu augmenté. Nous « réaffectons » les tâches et augmentons la correspondance. Nous recommençons à construire l'arbre alterné, car on ne sait jamais comment le décompte a changé
• Nous n’avons pas trouvé (n’avons pas atteint) de problème de bord optimal libre. Et ça existe, parce que Après tout, nous avons commencé en tant que développeur libre et dans notre rubrique nous avons le même nombre de tâches et de développeurs. L'arbre alterné résultant devient ce qu'on appelle hongrois(l'ensemble de la méthode s'appelle de la même manière). Dans ce cas, nous devrons réduire légèrement nos exigences envers les développeurs et recommencer notre recherche. L’échec est simplement l’occasion de recommencer, cette fois plus intelligemment (c).

Nous arrivons donc au dernier moment de la méthode hongroise, pourquoi tous ces options supplémentaires et les « capacités » ont été réfléchies. Supposons qu'en faisant pousser l'arbre alterné, nous obtenions finalement l'arbre hongrois. Considérons quels sommets tomberont dans cet arbre :

• Développeurs peu impliqués, car c'est d'eux qu'on commence à coûter un arbre
• Développeurs et tâches pouvant être atteintes le long des bords optimaux par des développeurs non impliqués. Parce que C'est par leur « réaffectation » que l'on tente d'employer ces derniers.

En dehors de cet arbre, le graphique restant contiendra :

• Développeurs et tâches qui sont en correspondance mais non accessibles à partir de sommets libres (développeurs). Nous leur avons trouvé un travail, il n’y a rien qui les touche pour l’instant.
• Les tâches inaccessibles en utilisant des bords optimaux sont celles auxquelles nous devrons parvenir. Par conséquent, lors de la construction d’un arbre, nous marquerons les sommets que nous avons réussi à atteindre. Et ces tâches ne resteront donc pas marquées.

Ensuite, dans la boucle, nous parcourrons la « frontière » de l'arborescence : le long des bords qui relient les développeurs non impliqués ou les développeurs accessibles depuis eux (ils peuvent peut-être être « réaffectés ») avec les tâches adjacentes (le long des bords non optimaux). En utilisant ces arêtes, nous calculerons le minimum sur moment actuel« inadéquation » des capacités du développeur pour qu'il puisse commencer cette tâche : delta = min(capacité du développeur (sommet) + connaissance du problème (sommet) - efficacité de résolution du problème (bord)).

Puis à l’intérieur de l’arbre hongrois nous :

• Abaissons les capacités des développeurs de delta afin de « attacher » de la manière la moins indolore au moins un bord à l'arbre alterné, le long duquel la prochaine fois nous continuerons à rechercher un problème gratuit
• Augmentons la « connaissance » des problèmes sur delta afin que les arêtes du graphe d'augmentation déjà construit restent optimales. Ceux. pour que l'égalité soit préservée : efficacité de résolution du problème (edge) = capacité du développeur (vertex) + connaissance du problème (vertex)

Mini-interprétation : on baisse les capacités des développeurs pour ensuite « attacher » au moins l'un d'entre eux. Nous lui trouverons un emploi, mais il ne travaillera pas selon ses qualifications. Il pourrait faire plus. Il se libère ainsi du temps pour conseiller ses collègues sur la tâche dans laquelle il est le plus compétent. Elle devient plus étudiée dans l'équipe. Ceci, à son tour, a probablement été géré par un autre développeur, qui pourra désormais également le remplacer si quelque chose arrive. Vous pouvez également réduire sa compétence en termes de connaissance de la tâche. Et ainsi de suite, « tout au long de la chaîne » dans l'équipe, la « connaissance » des tâches augmente et la capacité des développeurs à leur trouver des missions diminue légèrement.

Tous. Toutes les étapes cette méthode révisé. On continue dans le même esprit... Le succès n’est pas définitif, l’échec n’est pas fatal : c’est le courage de continuer qui compte.

7. Algorithme en mots, très brièvement

Maintenant, rassemblons tout cela :

• Initialisation. Développeurs - capacités maximales. Les tâches n'ont pas été étudiées.
• Tous les développeurs n'ont pas encore reçu de tâches.
  • Jusqu'à présent, il est possible de construire un arbre d'augmentation (trouver des tâches gratuites) en utilisant les bords optimaux
    • « Réaffecter » les tâches en augmentant les matchings
  • Je n'ai pas atteint la tâche gratuite. Arbre hongrois.
    • Réduire les capacités des développeurs d'un montant minimum

8. Inscription

Le code, bien sûr, sera plus court que toute ma description. =)

Je l'ai pris. À mon avis, une très bonne mise en œuvre. La seule différence est que l'auteur fournit le code d'une méthode de minimisation des missions (si, par exemple, il y a un salaire sur les bords), et dans l'article nous avons réparti les tâches afin d'obtenir efficacité maximale. Ainsi, après avoir légèrement modifié le code, je vais donner ci-dessous l'implémentation de la méthode maximum :

entier n;
vecteur< vector> une ; // Matrice de performances a[développeur][tâche]
vecteur xy, yx; // Correspondances : xy[développeur], yx[tâche]
vecteur vx, vy; // Arbre alterné vx[développeur], vy[tâche]
vecteur maxrow, mincol; // Capacités, connaissances

bool dotry (int je) (
if (vx[i]) renvoie false ;
vx[i] = vrai ;
pour (int j=0; j si (a[i][j]-maxrow[i]-mincol[j] == 0)
vy[j] = vrai ;
pour (int j=0; j if (a[i][j]-maxrow[i]-mincol[j] == 0 && yx[j] == -1) (
xy[je] = j;
yx[j] = je;
renvoie vrai ;
}
pour (int j=0; j if (a[i][j]-maxrow[i]-mincol[j] == 0 && dotry (yx[j])) (
xy[je] = j;
yx[j] = je;
renvoie vrai ;
}
retourner faux ;
}

int main() (

// ... lire un ...

Mincol.assign(n, 0);
minrow.assign(n, 0);
pour (int je=0; je pour (int j=0; j maxrow[i] = max(maxrow[i], a[i][j]);

Xy.assign(n, -1);
yx.assign(n, -1);
pour (int c=0; c vx.assign(n, 0);
vy.assign(n, 0);
entier k = 0 ;
pour (int je=0; je si (xy[i] == -1 && dotry (i))
++k;
c + = k;
si (k == 0) (
int z = INF ;
pour (int je=0; je si(vx[i])
pour (int j=0; j si (!vy[j])
z = min (z, maxrow[i]+mincol[j]-a[i][j]);
pour (int je=0; je si (vx[i]) maxrow[i] -= z;
si (vy[i]) mincol[i] += z;
}
}
}

entier ans = 0 ;
pour (int je=0; je ans += a[i]];
printf("%d\n" , ans);
pour (int je=0; je printf ("%d " , xy[i]+1);
}

* Ce code source a été mis en évidence avec Source Code Highlighter.

9. Totale

Si quelqu'un voit du hongrois pour la première fois. Et après avoir lu la description, puis la liste, vous aurez l'impression confiante "oui, même à partir de la liste, même sans ces descriptions, tout est clair qu'il y avait quelque chose qui n'allait pas". J'espère toujours qu'au moins en partie la description a permis de mieux comprendre le fonctionnement de l'algorithme. Je serai sincèrement heureux pour vous! et, en retour, cela me fera un peu sentir que je l’ai probablement écrit pour une raison. =)

Balises :

• problème d'affectation
• Algorithme hongrois
• L'algorithme de Kuhn

Ajouter des balises

Étape préliminaire .

Étape 1. À maximiser la fonction objectif AVEC trouvez l'élément maximum et soustrayez chaque élément de cette colonne du maximum. À minimiser la fonction objectif(somme des indicateurs d’efficacité des prescriptions) dans chaque colonne de la matrice AVEC trouvez l’élément minimum et soustrayez-le de chaque élément de cette colonne.

AVEC avec des éléments non négatifs. Dans chaque colonne de la matrice AVEC il y a au moins un zéro.

Étape 2. Dans chaque ligne de la matrice AVEC trouvez l'élément minimum et soustrayez-le de chaque élément de cette chaîne.

En conséquence, une matrice se forme AVEC 0 avec des éléments non négatifs. Dans chaque colonne et chaque ligne de la matrice AVEC 0 il y a au moins un zéro chacun.

Étape 3. Marquez tout zéro dans la première colonne avec un astérisque. En commençant par la deuxième colonne, visualisez chaque colonne de la matrice AVEC 0 et marquez d'un astérisque le zéro situé dans la ligne où il n'y a pas de zéro avec un astérisque. Un seul zéro peut être marqué d'un astérisque dans chaque colonne. Évidemment, les zéros de la matrice AVEC 0 marqués d'un astérisque sont indépendants par construction. Ceci conclut la phase préliminaire.

( k + 1)ème itération . Supposons que k-ème itération a déjà été effectuée et la matrice est ainsi obtenue AVEC k . Si dans la matrice AVEC k il y a exactement n des zéros avec un astérisque, le processus de résolution se termine. Si le nombre de zéros avec un astérisque est inférieur n, puis nous allons à ( k+ 1)ème itération.

Chaque itération commence par la première et se termine par la deuxième étape. Entre elles, quelques étapes peuvent être effectuées plusieurs fois : troisième - première. Avant de commencer l'itération, le signe « + » est utilisé pour mettre en évidencecolonnes matricesAVEC k , qui contiennent des zéros suivis d'un astérisque.

Première étape . Voir désélectionné colonnes de la matrice AVEC k. S'il n'y a pas d'éléments nuls parmi eux, alors allez à troisième étape.

Si le zéro non sélectionné de la matrice AVEC k détecté, alors l'un des deux cas suivants est possible :

cette ligne ne contient pas de zéro suivi d'un astérisque.

DANS premier cas Marquez le zéro non sélectionné avec un tiret Et sélectionner une ligne , dans lequel il est contenu, en plaçant un signe « + » à sa droite. Alors détruisez le signe "+" en l'encerclantà ce sujet colonne , dont l'intersection avec cette ligne sélectionnée contient un zéro avec un astérisque.

 Si tel zéro est trouvé et c'est le seul dans la colonne, alors note son accident vasculaire cérébral Et sélectionner une ligne (les lignes) contenant ce(s) zéro(s) sont marquées d’un signe « + ». Parcourez ensuite cette ou ces lignes en recherchant un zéro contenant un astérisque.

 Si tel zéro se trouve dans la colonne, mais ce n'est pas le seul dans la colonne, alors parmi ces zéros vous devez sélectionner :

tout d'abord, un tel zéro, dans la même ligne avec laquelle il n'y a pas de 0* ;

deuxièmement, un zéro dans la même ligne avec laquelle il y a un 0*, mais dans la même colonne avec ce 0* il y a un zéro non sélectionné ;

enfin, un tel zéro, dans une ligne avec laquelle il y a un 0*, mais dans une colonne avec ce 0* il n'y a pas de zéro non sélectionné ;

Ce processus, un nombre fini d'étapes, se termine par l'un des résultats suivants :

Résultat 1. Tous les zéros de la matrice AVEC k en surbrillance, c'est-à-dire situé dans les lignes ou colonnes sélectionnées. Dans ce cas passer à la troisième étape;

Exode 2. Il y a un zéro non sélectionné dans une chaîne où il n'y a pas de zéro avec un astérisque. Alors passer à la deuxième étape, marquer le dernier zéro dans l'ordre avec un trait .

Dans deuxième cas , après avoir marqué d'un trait le zéro non sélectionné, passez immédiatement à la deuxième étape.

Deuxième étape . Construire la chaîne suivante d'éléments matriciels AVEC k: un zéro non significatif avec un nombre premier, un zéro avec un astérisque situé dans la même colonne que le premier, un zéro avec un nombre premier situé dans la même ligne qu'un zéro précédent avec un astérisque, etc. la chaîne est formée par le mouvement de 0" à 0* par colonne, de 0* à 0" par ligne etc.

Il peut être prouvé que l'algorithme décrit pour construire une chaîne est sans ambiguïté et fini. En même temps la chaîne commence et se termine toujours zéro avec un nombre premier . Ensuite, placez des astérisques au-dessus des éléments de la chaîne qui se trouvent aux endroits impairs (0"), en les détruisant au-dessus des éléments pairs (0*). Détruisez ensuite tous les traits au-dessus des éléments de la matrice. AVEC k et les signes "+". Dans ce cas, le nombre de zéros indépendants sera augmenté d'un. (k + 1)ème itération terminée.

Troisième étape . Vous devriez passer à cette étape après la première étape au cas où tous les zéros de la matrice AVEC k mis en évidence, c'est-à-dire qu'ils se trouvent dans des lignes ou des colonnes sélectionnées. Dans ce cas, parmi les éléments non sélectionnés de la matrice AVEC k choisir élément minimum et marque-le h > 0.

soustraire h de tous éléments matrices AVEC k , situé dans des lignes non sélectionnées , Et

ajouter hà tout le monde éléments matrices AVEC k , situés dans des colonnes dédiées .

Le résultat est une nouvelle matrice équivalente à AVEC k .

Puisque parmi les éléments non sélectionnés de la matrice
de nouveaux zéros apparaîtront (selon la définition), vous devriez passer à la première étape, et à la place de la matrice AVEC k regarde la matrice
.

Après avoir terminé la première étape ou aller à deuxième étape , si le zéro non sélectionné est dans une chaîne qui ne contient pas de zéro astérisque, ou revenir à la troisième étape , si à la suite de la première étape tous les zéros de la matrice
sera mis en valeur.

Dans le premier cas après la deuxième étape l'itération se termine.

Dans le deuxième cas, après la troisième étape, la matrice est obtenue
~
~AVEC k. Dans la matrice
Des zéros non sélectionnés apparaîtront et toute la séquence d'opérations, à partir de la première étape, devra être répétée. Après un nombre fini de répétitions, la première étape suivante se terminera nécessairement par une transition à la deuxième étape , pendant lequel le nombre de zéros indépendants augmentera de un, et après quoi (k+ 1)ième l'itération se termine.

Exemple 9. Résolvons le problème en utilisant la méthode hongroise :

Le navire de combat de surface dispose de 5 armes à feu anti-aériennes (ASF). Un raid aérien ennemi simultané d'un montant de 5 unités est effectué sur le navire. L’incroyable potentiel de chacun je-ème AIA j-ème avion ennemi est égal à (nombre de potentiellement détruits j–x avions lors de l’attaque du NK par un avion). On suppose que n’importe quel AAM peut tirer sur n’importe quelle cible.

Répartir la protection de l'environnement sur l'ensemble du CC de manière à ce que le potentiel dommageable total soit maximum, dans les conditions suivantes :

Un seul ZOS peut être affecté à un CC ;

toutes les cibles doivent être visées par l'AIA.

Solution :

Étape préliminaire .





Première itération .

Première étape .

+ +



DANS

+ +

deuxième étape .



Deuxième itération .

P.

+ +

première étape .



Puisque tous les zéros de la matrice AVEC 1 sont en surbrillance, vous devez passer à la troisième étape.

Troisième étape .

+ +

+ +

h =1 

Première étape .



Deuxième étape .



En résolvant le problème d’affectation à l’aide de la méthode hongroise, nous avons constaté que la séquence
=4,
=4,
=3,
=2,
=2 donne la valeur maximale de la fonction objectif =15. Il s'ensuit que pour repousser une attaque aérienne ennemie, l'option la plus efficace sera l'option suivante d'attribution d'un AOC au CC :

Exercices .

Trouver le plan de référence du problème de transport à l'aide des méthodes « Coin Nord-Ouest », « Moindre coût », « Vogel » :

						un je
Applications b j

Résolvez le problème de transport de la tâche 1 en utilisant la méthode de distribution.

Résolvez le problème de transport de la tâche 1 en utilisant la méthode du potentiel.

Utilisation de la méthode hongroise pour résoudre le problème d'affectation lors de la recherche du maximum :

Utilisation de la méthode hongroise pour résoudre le problème d'affectation lors de la recherche du minimum :

Questions de sécurité :

Donner la formulation du problème de programmation linéaire des transports.

En quoi un problème de transport équilibré diffère-t-il d’un problème de transport déséquilibré ?

Combien de variables de base devrait-il y avoir dans un problème de transport équilibré ?

Définir les concepts : plan, plan réalisable, plan réalisable de référence, plan optimal, utilisés pour résoudre le problème de transport.

Formuler un algorithme pour trouver le plan de référence en utilisant la méthode du coin nord-ouest.

Formuler un algorithme pour trouver le plan de référence en utilisant la méthode du moindre coût.

Formuler un algorithme pour trouver un plan de référence en utilisant la méthode Vogel.

Formulez un algorithme pour trouver le plan optimal à l'aide de la méthode de distribution.

Formuler un algorithme pour trouver le plan optimal en utilisant la méthode du potentiel.

Donnez la formulation du problème d’affectation.

Comment une matrice carrée d'affectations est-elle formée dans le problème d'affectation pour différents nombres d'objets et de moyens ?

Formuler un algorithme pour résoudre le problème d'affectation en utilisant la méthode hongroise.

Comment la matrice d'affectation initiale est-elle formée au stade préliminaire lors de la maximisation de la fonction objectif ?

Comment est constituée la matrice d'affectation initiale au stade préliminaire lors de la minimisation de la fonction objectif ?

Quelle est l'essence de la première étape de résolution du problème d'affectation à l'aide de la méthode hongroise ?

Quelle est l'essence de la deuxième étape de résolution du problème d'affectation à l'aide de la méthode hongroise ?

Quelle est l'essence de la troisième étape de résolution du problème d'affectation à l'aide de la méthode hongroise ?

Combien de première, deuxième et troisième étapes peut-il y avoir dans une itération de résolution du problème d'affectation à l'aide de la méthode hongroise ?

Combien de zéros indépendants doit-il y avoir dans la matrice d'affectation pour décider que l'affectation optimale des fonds aux objets a été trouvée ?