PROBLEME
D’AFFECTATION
MEZIANE ABDERRAOUF / BERKAT ANES
PFE
fac.png
UNIVERSITÉ BENYOUCHEF BENKHEDDA
L3 MathApp
2023/2024
Table des matières
1 Optimisation combinatoire et méthodes de résolution 3
1.1 Introduction à l’optimisation combinatoire . . . . . . . . . . . 3
1.1.1 Définition : . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1.2 Importance et domaines d’application : . . . . . . . . . 3
1.1.3 Exemples de problèmes d’optimisation combinatoire : 4
1.2 Méthodes exactes de résolution . . . . . . . . . . . . . . . . . 4
1.2.1 Avantages et inconvénients des méthodes exactes . . . 5
1.3 Méthodes approchées de résolution . . . . . . . . . . . . . . . 6
1.3.1 Avantages et inconvénients des méthodes
approchées : . . . . . . . . . . . . . . . . . . . . . . . . 7
1.3.2 Comparaison entre méthodes exactes et approchées : . 7
2 PROBLEME D’AFFECTATION 9
2.1 Introduction à la problématique : . . . . . . . . . . . . . . . . 9
2.1.1 Définition du problème d’affectation : . . . . . . . . . . 9
2.1.2 Importance et applications du problème d’affectation : 9
2.2 Histoire du problème d’affectation . . . . . . . . . . . . . . . 11
2.2.1 Origines et évolution du problème d’affectation : . . . . 11
2.2.2 Contributions majeures à la résolution du
problème : . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.3 Méthodes de résolution du problème : . . . . . . . . . . . . . . 12
2.3.1 Méthodes exactes : . . . . . . . . . . . . . . . . . . . . 13
2.3.2 Méthodes approchées : . . . . . . . . . . . . . . . . . . 13
3 Méthode Hongroise 15
3.1 Définition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.2 Minimisation : . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.2.1 Exemple : . . . . . . . . . . . . . . . . . . . . . . . . . 16
1
3.3 Maximisation : . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.3.1 Exemple : . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.4 Codage en python . . . . . . . . . . . . . . . . . . . . . . . . . 22
2
Chapitre 1
Optimisation combinatoire et
méthodes de résolution
1.1 Introduction à l’optimisation combinatoire
1.1.1 Définition :
L’optimisation combinatoire est une branche des mathématiques et de
l’informatique ,qui étudie les problèmes dans le but de trouver la meilleure
solution parmi un ensemble fini de possibilités. Généralement , dans des
situations où il y a un nombre exponentiel de combinaisons possibles. Ces
problèmes sont souvent caractérisés par une recherche de solutions optimales,
basée sur des critères spécifiques et des contraintes définies.
1.1.2 Importance et domaines d’application :
1. Recherche opérationnelle : L’optimisation combinatoire est large-
ment utilisée dans la recherche opérationnelle pour améliorer les proces-
sus de décision et de gestion dans divers domaines tels que la logistique,
la planification de la production, la gestion des stocks, etc.
2. Informatique : Dans le domaine de l’informatique, l’optimisation
combinatoire est essentielle pour la conception et l’analyse d’algorithmes,
la conception de réseaux, l’ordonnancement de tâches, la conception de
circuits, etc.
3. Ingénierie : De nombreux problèmes d’ingénierie peuvent être for-
3
mulés comme des problèmes d’optimisation combinatoire, tels que la
conception de réseaux de télécommunications, la conception de sys-
tèmes de transport, la conception de systèmes énergétiques, etc.
4. Finance : En finance, l’optimisation combinatoire est utilisée pour la
gestion de portefeuille, l’optimisation des investissements, la tarification
des produits financiers, etc.
5. Biologie : Dans des domaines tels que la bio-informatique et la géno-
mique, l’optimisation combinatoire est utilisée pour résoudre des pro-
blèmes tels que l’alignement de séquences génétiques, la prédiction de
structures de protéines, etc.
1.1.3 Exemples de problèmes d’optimisation combina-
toire :
1. Problème du voyageur de commerce (PVC) : Le problème du
voyageur de commerce consiste à trouver le chemin le plus court pas-
sant par toutes les villes données une fois et revenant à la ville de
départ. C’est un problème d’optimisation combinatoire classique avec
de nombreuses applications pratiques dans la planification de tournées,
la logistique, etc.
2. Problème du sac à dos (Knapsack problem) : Ce problème consiste
à choisir un sous-ensemble d’objets ayant une valeur maximale tout en
respectant la contrainte de capacité du sac à dos. Il existe plusieurs
variantes de ce problème, chacune avec ses propres règles et objectifs.
3. Problème d’affectation (Assignment problem) : Ce problème
consiste à affecter un ensemble d’objets à un autre ensemble d’objets de
manière à maximiser ou minimiser une certaine fonction d’utilité ou de
coût. Par exemple, l’affectation de tâches à des travailleurs, l’affectation
de ressources à des projets, etc...
1.2 Méthodes exactes de résolution
Les méthodes exactes en optimisation combinatoire sont des approches al-
gorithmiques qui garantissent de trouver la solution optimale d’un problème
donné. Contrairement aux méthodes heuristiques, qui peuvent fournir des
solutions approximatives en temps raisonnable, les méthodes exactes visent
4
à trouver la meilleure solution possible en explorant systématiquement l’en-
semble des solutions candidates, parmi ces méthodes :
1. Méthode de séparation et évaluation (Branch/Bound) :
(a) Principe : L’algorithme explore l’ensemble des solutions possibles
en divisant le problème initial en sous-problèmes plus petits (bran-
chement).
(b) Évaluation : Pour réduire le nombre de solutions à évaluer, cer-
taines branches de l’arbre de recherche sont stérilisées en utilisant
des bornes inférieures et supérieures.
2. Programmation dynamique :
(a) Principe : Cette méthode consiste à résoudre un problème en com-
binant des solutions de sous-problèmes déjà résolus.
(b) Optimalité : Elle garantit l’optimalité de la solution trouvée, à
condition que le problème puisse être décomposé en sous-problèmes
et que les solutions de ces sous-problèmes puissent être combinées
pour résoudre le problème global.
1.2.1 Avantages et inconvénients des méthodes exactes
1. Avantages :
(a) Optimalité : Garantissent la solution optimale du problème. Fia-
bilité : Fournissent des résultats fiables et reproductibles.
(b) Validation : Permettent de valider les solutions obtenues par d’autres
méthodes.
2. Inconvénients :
(a) Complexité : La recherche exhaustive peut devenir rapidement
impraticable pour des problèmes de grande taille en raison de la
croissance exponentielle du nombre de solutions à évaluer.
(b) Temps de calcul : Les méthodes exactes peuvent nécessiter beau-
coup de temps de calcul, rendant l’approche impraticable pour
certains problèmes réels.
(c) Mémoire : Elles peuvent nécessiter une grande quantité de mé-
moire pour stocker toutes les solutions candidates et les informa-
tions associées.
5
En conclusion, les méthodes exactes en optimisation combinatoire sont
des approches algorithmiques puissantes qui garantissent l’obtention de la
solution optimale d’un problème. Cependant, elles peuvent être limitées en
termes de taille de problème qu’elles peuvent résoudre en raison de leur com-
plexité, de leurs besoins en temps de calcul et en mémoire. Malgré ces limita-
tions, elles restent indispensables pour de nombreux problèmes où l’obtention
d’une solution optimale est cruciale.
1.3 Méthodes approchées de résolution
Les méthodes approchées en optimisation combinatoire sont des tech-
niques algorithmiques conçues pour trouver des solutions de qualité à des
problèmes complexes en un temps raisonnable, sans garantir l’obtention de
la solution optimale. Elles se distinguent des méthodes exactes qui visent
à explorer exhaustivement l’ensemble des solutions possibles. Les méthodes
approchées utilisent des stratégies heuristiques, probabilistes ou métaheuris-
tiques pour guider la recherche vers des solutions satisfaisantes, parmi ces
méthodes :
1. Algorithmes génétiques :
(a) Principe : Inspirés de la théorie de l’évolution, les algorithmes
génétiques simulent le processus de sélection naturelle mais elles
ne garantissent pas l’optimalité à un problème donné.
(b) Opérations : Ils utilisent des opérations telles que la sélection, le
croisement et la mutation pour explorer l’espace des solutions et
évoluer vers des solutions de meilleure qualité.
2. Recuit simulé (Simulated Annealing) :
(a) Principe : Le recuit simulé est une technique de recherche proba-
biliste inspirée du processus de recuit en métallurgie. Il permet
d’échapper aux optimaux locaux en explorant l’espace des solu-
tions de manière aléatoire et contrôlée.
(b) Température : La température est utilisée comme paramètre pour
réguler l’exploration de l’espace des solutions. Elle permet des
mouvements aléatoires initialement et est réduite progressivement
pour converger vers une solution optimale ou quasi-optimale.
6
1.3.1 Avantages et inconvénients des méthodes
approchées :
1. Avantages :
(a) Efficacité : Les méthodes approchées sont souvent plus rapides que
les méthodes exactes et peuvent fournir des solutions de bonne
qualité en un temps raisonnable.
(b) Adaptabilité : Elles peuvent être adaptées à différents types de
problèmes et contraintes, rendant leur application plus flexible et
versatile.
(c) Évolutivité : Elles peuvent être utilisées pour résoudre des pro-
blèmes de grande taille ou complexes, pour lesquels les méthodes
exactes sont impraticables ou trop coûteuses en termes de temps
et de ressources.
2. Inconvénients :
(a) Qualité de la solution : Contrairement aux méthodes exactes, les
méthodes approchées ne garantissent pas l’obtention de la solution
optimale, mais plutôt des solutions de qualité variable.
(b) Validation : La qualité des solutions obtenues peut varier en fonc-
tion des paramètres, des stratégies et des conditions initiales uti-
lisées, nécessitant une évaluation et une validation approfondies.
(c) Complexité : Certains algorithmes approchés peuvent être diffi-
ciles à mettre en œuvre, à ajuster et à optimiser en fonction du
problème spécifique à résoudre.
1.3.2 Comparaison entre méthodes exactes et appro-
chées :
7
Critères de comparai- Méthodes exactes Méthodes approchées
son
Qualité de la solution Garantissent l’obtention de Fournissent des solutions de
la solution optimale, sous qualité variable, générale-
réserve de la résolution com- ment de bonnes solutions
plète du problème. mais pas nécessairement op-
timales.
Temps de calcul Peuvent être très gour- Généralement plus rapides
mandes en temps de cal- que les méthodes exactes,
cul, surtout pour les pro- adaptées pour les problèmes
blèmes de grande taille, en de grande taille ou les appli-
raison de la complexité ex- cations nécessitant des ré-
ponentielle de l’exploration sultats en temps réel.
de l’espace des solutions.
Robustesse Peuvent être sensibles aux Souvent plus robustes aux
variations des paramètres variations et aux erreurs,
du problème ou aux erreurs grâce à leur capacité à ex-
de modélisation, ce qui peut plorer l’espace des solutions
affecter la qualité et la vali- de manière flexible et adap-
dité de la solution obtenue. tative.
8
Chapitre 2
PROBLEME
D’AFFECTATION
2.1 Introduction à la problématique :
2.1.1 Définition du problème d’affectation :
Le problème d’affectation est un problème d’optimisation combinatoire
qui consiste à assigner un ensemble d’objets à un autre ensemble d’objets
de manière à maximiser ou minimiser une certaine fonction d’utilité ou de
coût, tout en respectant certaines contraintes. Chaque objet doit être assigné
exactement une fois, et chaque objet source doit être assigné à un objet cible
unique. Le but est de trouver une affectation qui optimise l’objectif spécifique
du problème, comme maximiser le profit, minimiser le coût, ou équilibrer la
charge de travail.
2.1.2 Importance et applications du problème d’affec-
tation :
Le problème d’affectation est un problème fondamental qui se retrouve
dans de nombreux domaines et applications réels en raison de sa pertinence
et de sa capacité à modéliser divers scénarios d’optimisation. Voici quelques
domaines où le problème d’affectation joue un rôle crucial :
9
1. Logistique :
(a) Planification de la distribution : Le problème d’affectation est uti-
lisé pour optimiser la distribution de marchandises entre les entre-
pôts et les points de vente, en minimisant les coûts de transport
et en maximisant l’efficacité.
(b) Gestion des stocks : Il est utilisé pour affecter les articles dispo-
nibles aux différents emplacements de stockage afin de maximiser
la disponibilité des produits tout en minimisant les coûts de sto-
ckage et de manutention.
2. Transport :
(a) Planification des itinéraires : Le problème d’affectation est utilisé
pour affecter les véhicules à des itinéraires spécifiques afin de mini-
miser les distances parcourues, les coûts de carburant et les temps
de trajet.
(b) Affectation de conducteurs : Il est utilisé pour affecter les conduc-
teurs aux véhicules ou aux itinéraires de manière optimale en te-
nant compte des compétences, des disponibilités et des préférences
des conducteurs.
3. Affectation de ressources :
(a) Gestion de projet : Le problème d’affectation est utilisé pour af-
fecter les tâches, les équipements et les ressources humaines aux
différents projets ou activités de manière à maximiser l’efficacité
et à respecter les contraintes de temps et de capacité.
(b) Planification des horaires : Il est utilisé pour affecter les employés
aux différents postes de travail, aux shifts ou aux horaires de ma-
nière à équilibrer la charge de travail, à respecter les contraintes
de disponibilité et à maximiser la satisfaction des employés.
4. Optimisation des réseaux :
(a) Affectation de fréquences : Le problème d’affectation est utilisé
en télécommunications pour affecter les fréquences radio aux sta-
tions de manière à optimiser la qualité du signal, à minimiser les
interférences et à maximiser la capacité du réseau.
(b) Gestion des routes : Il est utilisé dans la planification du trafic
routier pour affecter les voies, les intersections et les points de
contrôle de manière à minimiser les congestions, à améliorer la
fluidité du trafic et à optimiser l’utilisation des infrastructures
routières.
10
2.2 Histoire du problème d’affectation
2.2.1 Origines et évolution du problème d’affectation :
Le problème d’affectation est l’un des problèmes d’optimisation combina-
toire les plus fondamentaux et a une histoire riche qui s’étend sur plusieurs
siècles. Bien que ses origines exactes ne soient pas clairement définies, des
formes primitives du problème d’affectation peuvent être identifiées dans di-
vers contextes historiques et pratiques, bien avant son formalisme mathéma-
tique et son étude algorithmique.
1. Origines :
(a) XVIIIe siècle : Les premières manifestations du problème d’affec-
tation peuvent être retracées dans le contexte des mathématiques
et de la géométrie combinatoire du XVIIIe siècle, où des problèmes
similaires d’affectation et de correspondance ont été abordés dans
des études sur les permutations, les combinaisons et les arrange-
ments.
(b) XIXe siècle : Au cours du XIXe siècle, avec l’émergence de la
théorie des graphes et la formalisation de problèmes d’optimisa-
tion combinatoire, le problème d’affectation a commencé à être
étudié sous diverses formes et variantes, jetant les bases pour son
développement et son analyse mathématique.
2. Évolution :
(a) Années 1950 : Le véritable essor du problème d’affectation en tant
que problème distinct et formel a eu lieu dans les années 1950 avec
le développement de l’algorithme hongrois par Harold Kuhn et
James Munkres en 1955. Cet algorithme, basé sur la programma-
tion linéaire, a révolutionné la résolution du problème d’affecta-
tion en fournissant une méthode efficace pour trouver une solution
optimale en temps polynomial.
(b) Années 1960-1970 : Au cours des années 1960 et 1970, avec l’avè-
nement de l’informatique et l’évolution des algorithmes et des mé-
thodes de résolution, le problème d’affectation a gagné en com-
plexité et en diversité, donnant lieu à de nombreuses variantes,
extensions et généralisations qui ont élargi sa portée et son appli-
cabilité dans divers domaines et applications.
11
(c) Années 1980-1990 : Les années 1980 et 1990 ont été marquées
par l’émergence de nouvelles méthodes, techniques et approches
pour résoudre le problème d’affectation, y compris les méthodes
de programmation linéaire, les algorithmes génétiques, le recuit
simulé, les méthodes tabou, les algorithmes de recherche locale
et bien d’autres, qui ont enrichi la résolution du problème et ont
contribué à son développement et à son application continue dans
divers contextes réels et académiques.
2.2.2 Contributions majeures à la résolution du
problème :
1. Algorithme hongrois (1955) : Développé par Harold Kuhn et James
Munkres, l’algorithme hongrois est l’une des premières méthodes exactes
pour résoudre le problème d’affectation. Il utilise une approche de pro-
grammation linéaire et a révolutionné la résolution du problème en
fournissant une méthode efficace pour trouver une solution optimale en
temps polynomial.
2. Méthodes de programmation linéaire : Les méthodes de program-
mation linéaire, telles que le simplexe, la programmation entière et la
programmation dynamique, ont été largement utilisées pour résoudre
le problème d’affectation en formulant le problème comme un modèle
de programmation linéaire et en utilisant des algorithmes de résolution
efficaces.
3. Algorithmes génétiques et recuit simulé : Les algorithmes géné-
tiques et le recuit simulé, inspirés par la théorie de l’évolution et la
thermodynamique, ont été adaptés et appliqués au problème d’affecta-
tion en utilisant des techniques de sélection, de croisement, de mutation
et de recherche probabiliste pour évoluer vers des solutions optimales
ou quasi-optimales.
2.3 Méthodes de résolution du problème :
Le problème d’affectation est un problème d’optimisation combinatoire
pour lequel il existe plusieurs méthodes exactes et approchées pour le ré-
soudre. Voici une présentation des méthodes les plus couramment utilisées
pour aborder ce problème :
12
2.3.1 Méthodes exactes :
Les méthodes exactes garantissent de trouver la solution optimale du
problème, mais elles peuvent être très coûteuses en termes de temps de calcul
pour les problèmes de grande taille, et parmis ces méthodes :
1. Algorithme hongrois : Spécifiquement conçu pour résoudre le pro-
blème d’affectation quadratique, cet algorithme utilise une recherche
de chemins augmentants dans un graphe biparti pondéré pour trouver
la solution optimale.
2. Programmation linéaire en nombres entiers (PLNE) : Le pro-
blème d’affectation peut être formulé comme un problème de PLNE
où l’objectif est de minimiser ou maximiser une fonction objectif sous
des contraintes linéaires. Des solveurs tels que CPLEX, Gurobi ou IBM
ILOG CP Optimizer peuvent être utilisés pour résoudre ces problèmes.
3. Programmation par contraintes : Le problème d’affectation peut
être résolu en utilisant des techniques de programmation par contraintes
où les variables, les domaines et les contraintes sont explicitement dé-
finis pour le problème. Des solveurs comme MiniZinc, Choco ou IBM
ILOG CP Optimizer peuvent être utilisés pour résoudre ces problèmes.
4. Méthodes basées sur les réseaux de flots : Le problème d’affecta-
tion peut être résolu en modélisant le problème comme un problème de
flot maximum dans un réseau. Des algorithmes comme l’algorithme de
Ford-Fulkerson ou l’algorithme de Edmonds-Karp peuvent être utilisés
pour trouver la solution optimale.
2.3.2 Méthodes approchées :
Les méthodes approchées ne garantissent pas de trouver la solution op-
timale, mais elles sont généralement plus rapides et peuvent fournir des so-
lutions de qualité acceptable pour les problèmes de grande taille, parmis ces
methodes on a :
1. Méthodes heuristiques : Les méthodes heuristiques cherchent des
solutions "bonnes" mais pas nécessairement optimales en explorant ra-
pidement l’espace des solutions. Parmi les méthodes heuristiques, on
trouve les algorithmes gloutons et la recherche locale.
2. Métaheuristiques : Les métaheuristiques sont des techniques d’op-
timisation qui combinent des éléments de différentes méthodes heuris-
13
tiques pour explorer efficacement l’espace des solutions. Parmi les mé-
taheuristiques couramment utilisées pour le problème d’affectation, on
trouve le recuit simulé, la recherche tabou, les algorithmes génétiques
et l’algorithme de colonies de fourmis.
3. Algorithmes gloutons : Les algorithmes gloutons construisent une
solution étape par étape en choisissant à chaque étape la meilleure
option locale. Bien que ces algorithmes ne garantissent pas une solution
optimale, ils sont efficaces pour résoudre des problèmes simples et de
grande taille.
14
Chapitre 3
Méthode Hongroise
3.1 Définition
La méthode hongroise, également connue sous le nom d’algorithme hon-
grois ou méthode d’assignation hongroise, est un algorithme utilisé pour ré-
soudre les problèmes d’assignation ou d’affectation. Elle est principalement
appliquée dans les domaines de l’optimisation combinatoire et de la théorie
des graphes. Cette méthode permet de trouver la meilleure correspondance
entre des éléments d’un ensemble source et d’un ensemble cible, tout en mi-
nimisant ou maximisant une fonction de coût spécifique. Elle est largement
utilisée dans divers domaines tels que la logistique, l’affectation de tâches, la
planification de production, etc...
3.2 Minimisation :
1. Matrice initiale :
Soit C une matrice carrée n × m, où n est le nombre de lignes et
m est le nombre de colonnes. Chaque élément Cij représente le coût
d’assigner la tâche i à l’agent j.
2. Soustraction de lignes et colonnes : Pour chaque ligne de la ma-
trice, soustrayez le plus petit élément de cette ligne à tous les éléments
de la ligne (ij = ij - min).
15
Pour chaque colonne, soustrayez le plus petit élément de cette colonne
à tous les éléments de la colonne (ij = ij - min).
3. Marquage des Zéros :
Trouvez une affectation initiale en marquant les zéros dans la matrice
réduite. Si le nombre minimum de lignes ou de colonnes marquées est
égal au l’ordre de la matrice, passez à l’étape suivante. Sinon, continuez
à marquer des zéros jusqu’à ce que cela soit le cas .
4. Recherche de Chemin Augmentant :
Si le nombre de lignes marquées est égal au l’ordre de la matrice ,
l’algorithme est terminé. Sinon, trouvez un chemin augmentant (un
chemin alternant de zéros et de marques) dans la matrice réduite. Mar-
quez les zéros non inclus dans le chemin augmentant et démarquez les
zéros inclus dans le chemin.
5. Mise à Jour des Coûts :
Trouvez la valeur minimale parmi les éléments non marqués de la ma-
trice réduite (appelée “valeur minimale non couverte”).
Soustrayez cette valeur minimale de tous les éléments non marqués et
ajoutez-la à tous les éléments marqués deux fois.
Répétez les étapes 3 à 6 jusqu’à ce que vous ayez une affectation opti-
male.
3.2.1 Exemple :
Supposons que nous ayons trois robots (P1, P2, P3, P4) et trois tâches
(C1, C2, C3, C4) à accomplir dans une grille. Chaque robot peut terminer
chaque tâche en un certain nombre de jours, comme indiqué dans le tableau
ci-dessous :
1. ETAPE 1 : Réduction du tableau initial :
16
On soustrait à chaque ligne du tableau
Capture8.png initial, le plus petit élément de la ligne
On fait de même avec les colonnes.
(a) Réduction des lignes :
Capture9.png Capture10.png
17
(b) Réduction des colonnes :
Capture11.png Capture12.png
2. ETAPE 2 : Encadrer et barrer les zeros :
Capture13.png
3. ETAPE 3 : Modification du taleau :
Les cases non traversées par un trait constituent un tableau partiel On
retranche à toutes les cases de ce tableau partiel le plus petit élément
de celui-ci On ajoute ce même élément à toutes les cases du tableau
initial barrées deux fois On obtient alors un nouveau tableau sur lequel
on pourra répéter la succession des étapes 1 à 3
18
Capture14.png Capture15.png
Capture16.png Capture17.png
Capture18.png
19
4. Solution optimale :
Ainsi, dans l’exemple, la valeur de l’affectation minimale est :
60+200+180+90 =530
Capture19.png
3.3 Maximisation :
La "méthode hongroise de maximisation"est utilisée pour résoudre des
problèmes d’optimisation dans lesquels vous devez affecter des ressources li-
mitées à des tâches de manière à maximiser le rendement ou minimiser le
coût, en respectant certaines contraintes.
Max ni=1 ui + nj=1 vj
P P
ui + vj ≤ cij pour i = 1, . . . , n
et j = 1, . . . , n
1. Etape 1 : Transformation du tableau initial :
(a) Identifier ’MAX’ le plus grand élément du tableau
(b) Pour chaque élément ’e’ du tableau initial faire :
e = MAX - e
2. Etape 2 : Meme étapes du minisation :
faire les meme étapes de la minimisation exactement .
3.3.1 Exemple :
Voici le tableau initial : r1.png
20
1. Etape 1 : Transformation du tableau initial :
(a) Identifier ’MAX’ le plus grand élément du tableau
(b) Pour chaque élément ’e’ du tableau initial faire :
e = MAX - e
MAX = 60. r2.png
2. Etape 2 : Meme étapes du minisation :
(a) Réduction du tableau :
r3.png r4.png
(b) Encadrer et barrer des zeros :
r5.png
(c) Solution Optimale :
r5.png r2.png
la valeur de l’affectation minimale est 40+16+40+60+60 =216
21
3.4 Codage en python
Le langage de programmation Python, réputé pour sa simplicité et sa po-
lyvalence, est un outil puissant pour développer des algorithmes complexes
et créer des interfaces graphiques conviviales. Dans ce chapitre, nous allons
explorer l’implémentation de la méthode hongroise en Python.
22
