\( %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Mes commandes %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \newcommand{\multirows}[3]{\multirow{#1}{#2}{$#3$}}%pour rester en mode math \renewcommand{\arraystretch}{1.3}%pour augmenter la taille des case \newcommand{\point}[1]{\marginnote{\small\vspace*{-1em} #1}}%pour indiquer les points ou le temps \newcommand{\dpl}[1]{\displaystyle{#1}}%megamode \newcommand{\A}{\mathscr{A}} \newcommand{\LN}{\mathscr{N}} \newcommand{\LL}{\mathscr{L}} \newcommand{\K}{\mathbb{K}} \newcommand{\N}{\mathbb{N}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\R}{\mathbb{R}} \newcommand{\C}{\mathbb{C}} \newcommand{\M}{\mathcal{M}} \newcommand{\D}{\mathbb{D}} \newcommand{\E}{\mathcal{E}} \renewcommand{\P}{\mathcal{P}} \newcommand{\G}{\mathcal{G}} \newcommand{\Kk}{\mathcal{K}} \newcommand{\Cc}{\mathcal{C}} \newcommand{\Zz}{\mathcal{Z}} \newcommand{\Ss}{\mathcal{S}} \newcommand{\B}{\mathbb{B}} \newcommand{\inde}{\bot\!\!\!\bot} \newcommand{\Proba}{\mathbb{P}} \newcommand{\Esp}[1]{\dpl{\mathbb{E}\left(#1\right)}} \newcommand{\Var}[1]{\dpl{\mathbb{V}\left(#1\right)}} \newcommand{\Cov}[1]{\dpl{Cov\left(#1\right)}} \newcommand{\base}{\mathcal{B}} \newcommand{\Som}{\textbf{Som}} \newcommand{\Chain}{\textbf{Chain}} \newcommand{\Ar}{\textbf{Ar}} \newcommand{\Arc}{\textbf{Arc}} \newcommand{\Min}{\text{Min}} \newcommand{\Max}{\text{Max}} \newcommand{\Ker}{\text{Ker}} \renewcommand{\Im}{\text{Im}} \newcommand{\Sup}{\text{Sup}} \newcommand{\Inf}{\text{Inf}} \renewcommand{\det}{\texttt{det}} \newcommand{\GL}{\text{GL}} \newcommand{\crossmark}{\text{\ding{55}}} \renewcommand{\checkmark}{\text{\ding{51}}} \newcommand{\Card}{\sharp} \newcommand{\Surligne}[2]{\text{\colorbox{#1}{ #2 }}} \newcommand{\SurligneMM}[2]{\text{\colorbox{#1}{ #2 }}} \newcommand{\norm}[1]{\left\lVert#1\right\rVert} \renewcommand{\lim}[1]{\underset{#1}{lim}\,} \newcommand{\nonor}[1]{\left|#1\right|} \newcommand{\Un}{1\!\!1} \newcommand{\sepon}{\setlength{\columnseprule}{0.5pt}} \newcommand{\sepoff}{\setlength{\columnseprule}{0pt}} \newcommand{\flux}{Flux} \newcommand{\Cpp}{\texttt{C++\ }} \newcommand{\Python}{\texttt{Python\ }} %\newcommand{\comb}[2]{\begin{pmatrix} #1\\ #2\end{pmatrix}} \newcommand{\comb}[2]{C_{#1}^{#2}} \newcommand{\arrang}[2]{A_{#1}^{#2}} \newcommand{\supp}[1]{Supp\left(#1\right)} \newcommand{\BB}{\mathcal{B}} \newcommand{\arc}[1]{\overset{\rotatebox{90}{)}}{#1}} \newcommand{\modpi}{\equiv_{2\pi}} \renewcommand{\Re}{Re} \renewcommand{\Im}{Im} \renewcommand{\bar}[1]{\overline{#1}} \newcommand{\mat}{\mathcal{M}} \newcommand{\und}[1]{{\mathbf{\color{red}\underline{#1}}}} \newcommand{\rdots}{\text{\reflectbox{$\ddots$}}} \newcommand{\Compa}{Compa} \newcommand{\dint}{\dpl{\int}} \newcommand{\intEFF}[2]{\left[\!\left[#1 ; #2\right]\!\right]} \newcommand{\intEFO}[2]{\left[\!\left[#1 ; #2\right[\!\right[} \newcommand{\intEOF}[2]{\left]\!\left]#1 ; #2\right]\!\right]} \newcommand{\intEOO}[2]{\left]\!\left]#1 ; #2\right[\!\right[} \newcommand{\ou}{\vee} \newcommand{\et}{\wedge} \newcommand{\non}{\neg} \newcommand{\implique}{\Rightarrow} \newcommand{\equivalent}{\Leftrightarrow} \newcommand{\Ab}{\overline{A}} \newcommand{\Bb}{\overline{B}} \newcommand{\Cb}{\overline{C}} \newcommand{\Cl}{\texttt{Cl}} \newcommand{\ab}{\overline{a}} \newcommand{\bb}{\overline{b}} \newcommand{\cb}{\overline{c}} \newcommand{\Rel}{\mathcal{R}} \newcommand{\superepsilon}{\varepsilon\!\!\varepsilon} \newcommand{\supere}{e\!\!e} \makeatletter \newenvironment{console}{\noindent\color{white}\begin{lrbox}{\@tempboxa}\begin{minipage}{\columnwidth} \ttfamily \bfseries\vspace*{0.5cm}} {\vspace*{0.5cm}\end{minipage}\end{lrbox}\colorbox{black}{\usebox{\@tempboxa}} } \makeatother \def\ie{\textit{i.e. }} \def\cf{\textit{c.f. }} \def\vide{ { $ {\text{ }} $ } } %Commande pour les vecteurs \newcommand{\grad}{\overrightarrow{Grad}} \newcommand{\Vv}{\overrightarrow{v}} \newcommand{\Vu}{\overrightarrow{u}} \newcommand{\Vw}{\overrightarrow{w}} \newcommand{\Vup}{\overrightarrow{u'}} \newcommand{\Zero}{\overrightarrow{0}} \newcommand{\Vx}{\overrightarrow{x}} \newcommand{\Vy}{\overrightarrow{y}} \newcommand{\Vz}{\overrightarrow{z}} \newcommand{\Vt}{\overrightarrow{t}} \newcommand{\Va}{\overrightarrow{a}} \newcommand{\Vb}{\overrightarrow{b}} \newcommand{\Vc}{\overrightarrow{c}} \newcommand{\Vd}{\overrightarrow{d}} \newcommand{\Ve}[1]{\overrightarrow{e_{#1}}} \newcommand{\Vf}[1]{\overrightarrow{f_{#1}}} \newcommand{\Vn}{\overrightarrow{0}} \newcommand{\Mat}{Mat} \newcommand{\Pass}{Pass} \newcommand{\mkF}{\mathfrak{F}} \renewcommand{\sp}{Sp} \newcommand{\Co}{Co} \newcommand{\vect}[1]{\texttt{Vect}\dpl{\left( #1\right)}} \newcommand{\prodscal}[2]{\dpl{\left\langle #1\left|\vphantom{#1 #2}\right. #2\right\rangle}} \newcommand{\trans}[1]{{\vphantom{#1}}^{t}{#1}} \newcommand{\ortho}[1]{{#1}^{\bot}} \newcommand{\oplusbot}{\overset{\bot}{\oplus}} \SelectTips{cm}{12}%Change le bout des flèches dans un xymatrix \newcommand{\pourDES}[8]{ \begin{itemize} \item Pour la ligne : le premier et dernier caractère forment $#1#2$ soit $#4$ en base 10. \item Pour la colonne : les autres caractères du bloc forment $#3$ soit $#5$ en base 10. \item A l'intersection de la ligne $#4+1$ et de la colonne $#5+1$ de $S_{#8}$ se trouve l'entier $#6$ qui, codé sur $4$ bits, est \textbf{\texttt{$#7$}}. \end{itemize} } \)

Problème d'affectation

Outils de la théorie des graphes

Définition

On dira qu'un graphe orienté $ \G$ est biparti si il existe deux sous-ensembles $ A$ et $ B$ de $ \Som(\G)$ vérifiant :

$ A\neq \varnothing$ , $ B\neq\varnothing$ , $ A\cap B=\varnothing$ et $ A\cup B=\Som(\G)$
$ \forall (x,y) \in \Arc(\G),\quad (x\in A\wedge y\in B)$ .

Le graphe ci-contre est biparti. En effet en posant $ A=\{1 ; 3 ; 4\}$ et $ B=\{2 ; 5 ; 6\}$ on observe que les conditions précédentes sont vérifiées. \[ \xymatrix@R=0.1cm@C=0.1cm{ &&&4\ar[dl]\\ 1\ar[rr]\ar[dd]&&2&\\ &6&&\\ 5&&3\ar[uu]\ar[ll]\ar[lu]& } \]

Définition

On défini le graphe biparti complet $ \Kk_{n,m}$ comme le graphe avec sa première partie $ A$ de cardinalité $ n$ , sa seconde partie $ B$ de cardinalité $ m$ et tel que pour chaque sommet de $ A$ il existe un arc vers n'importe quel sommet de $ B$ .

Considérons la matrice booléenne $ M$ d'un graphe biparti. Notons $ A$ sa première partie et $ B$ sa seconde partie. En réordonnant les sommets, précisément en plaçant les sommets de $ A$ d'abord et les sommets de $ B$ ensuite on peut se ramener à une matrice triangulaires blocs stricte. Précisément, puisque qu'il n'y a pas d'arc de $ A$ vers $ A$ , de $ B$ vers $ B$ et de $ B$ vers $ A$ , il est toujours possible de se ramener à une matrice de la forme \[ \begin{array}{c||ccc|ccc} &\cdots&A&\cdots&\cdots&B&\cdots\\\hline\hline \vdots&\ddots&\vdots&&\ddots&\vdots&\\ A&\cdots&0&\cdots&\cdots&*&\cdots\\ \vdots&&\vdots&\ddots&&\vdots&\ddots\\\hline \vdots&\ddots&\vdots&&\ddots&\vdots&\\ B&\cdots&0&\cdots&\cdots&0&\cdots\\ \vdots&&\vdots&\ddots&&\vdots&\ddots \end{array} \]

Définition

Soit $ \G$ un graphe biparti de première partie $ A$ et de seconde partie $ B$ . On appel matrice réduite la matrice booléenne $ M$ de $ \G$ où l'on a supprimé les colonnes des sommets de $ A$ et les lignes des sommets de $ B$ .

La matrice réduite associé au graphe biparti dont une représentation sagittale est \[ \xymatrix@R=0cm{ &A\ar[rdd]&B\ar[dd]\ar[ldd]\\ E\ar[rd]\ar@/^0.319pc/[rrd]&&\\ &D&C } \] est \[ \begin{array}{c||cc} &C&D\\\hline\hline A&1&0\\ B&1&1\\ E&1&1 \end{array} \]

Algorithme hongrois

L'entreprise Lune Nette fabrique des lunettes astronomiques et pour ce faire utilise trois types de matière premières : du métal (M), du plastique (P) et du verre (V). Lune Nette fait appel à trois usines pour se fournir. Chaque usine affiche des prix différents résumés dans le tableau suivant en millier d'euro par kilogramme

	1	2	3
M	3	5	3
P	1	2	2
V	2	2	1

Mais les lois sur la compétitivité oblige Lune Nette a respecter les règles antitrust : on ne peut commander à une usine qu'une seule matière première. La question qui se pose alors est de savoir comment choisir quelle matière première une usine enverra et ce au cout le plus petit possible ? Il s'agit d'un problème d'affectation. L'objet que nous manipulons est un graphe biparti (dans notre exemple les usines d'un coté et les matières premières de l'autre) avec autant de sommet dans la première partie que dans la seconde. En d'autre terme la matrice réduite est carré. Il s'agit de plus d'un graphe valué car chaque arc a un poids. La question est donc de sélectionner les arcs pour que le poids total (c'est à dire la somme des arcs sélectionnés) soit le plus petit possible. Autrement dis : il faut, dans la matrice réduite augmenté par la valuation, sélection une et une seule case par ligne et colonne. Un outil pour y arriver est l'algorithme hongrois (aussi appelé algorithme de Kuhn-Munkres) qui permet, en un temps de calcul polynomiale, de déterminer l'affection de poids minimal.

Étape 1 - Apparition de 0.

On fait apparaitre un zéro par ligne et par colonne par le procédé suivant :

Pour chaque ligne on soustrait à tous les coefficients de la ligne sa valeur minimale.
Pour chaque colonne on soustrait à tous les coefficients de la colonne sa valeur minimale.

On passe ensuite à l'étape 2.

Étape 2 - Sélection de 0.

Si

il existe un 0 qui n'est pas sur une ligne ou une colonne d'un 0 sélectionné, on le sélectionne et on recommence l'étape 2.

Sinon

Si

toutes les colonnes (ou ligne) possède un 0 sélectionné, l'algorithme prend fin.

Sinon

on va à l'étape 3

Etape 3 - Couverture de 0.

Initialisation.

On couvre toutes les colonnes avec un 0 sélectionné.

Marquage.

il existe un 0 non couvert, on le marque.

il existe un 0 sélectionné dans la ligne du 0 marqué on couvre la ligne et on découvre la colonne. On recommence l'étape 3Marquage.

Sinon

on procède à la numérotation des 0.

On note $ 0_0$ le dernier 0 marqué.
On note $ 0_1$ le 0 sélectionné sur la même colonne du $ 0_0$ .
On note $ 0_2$ le 0 marqué sur la même ligne du $ 0_1$ .
On note $ 0_3$ le 0 sélectionné sur la même colonne du $ 0_2$ .
On note $ 0_4$ le 0 marqué sur la même ligne du $ 0_3$ .
...
On note $ 0_{2x+1}$ le 0 sélectionné sur la même colonne du $ 0_{2x}$ .
...
On note $ 0_{2y}$ le 0 marqué sur la même ligne du $ 0_{2y-1}$ .
...

Une fois fait tous les $ 0_{paire}$ deviennent des 0 sélectionnés et les $ 0_{impaire}$ deviennent non sélectionnés puis on retourne à l'étape 2.

Sinon

on va à l'étape 4.

Etape 4 - Nouveaux 0.

Soit $ m$ le plus petit coefficient parmi ceux non couvert à l'étape 3.

On ajoute $ m$ à toutes les lignes couvertes.
Puis, on soustrait $ m$ à toutes les colonnes non couvertes.

On retourne à l'étape 2.

Faisons tourner cet algorithme sur la matrice réduite suivante. \[ \begin{array}{cccccc} 9&8&6&4&6\\ 3&6&6&7&4\\ 4&9&8&3&6\\ 7&6&4&4&7\\ 2&8&3&5&6 \end{array} \]

Étape 1.: Apparition de 0 sur les lignes, en soustrayant de chaque ligne son plus petit coefficient. \[ \begin{array}{cccccc} 5&4&2&0&2\\ 0&3&3&4&1\\ 1&6&5&0&3\\ 3&2&0&0&3\\ 0&6&1&3&4 \end{array} \] Apparition de 0 sur les colonnes, en soustrayant de chaque colonne son plus petit coefficient. \[ \begin{array}{cccccc} 5&2&2&0&1\\ 0&1&3&4&0\\ 1&4&5&0&2\\ 3&0&0&0&2\\ 0&4&1&3&3 \end{array} \]
Étape 2.: Pour signaler la sélection des 0, on les encadres. \[ \begin{array}{cccccc} 5&2&2&\boxed{0}&1\\ \boxed{0}&1&3&4&0\\ 1&4&5&0&2\\ 3&\boxed{0}&0&0&2\\ 0&4&1&3&3 \end{array} \]

Étape 3.

On choisi de marquer les 0 en les soulignant et de couvrir les lignes et colonnes en plaçant une croix devant la ligne ou colonne concernée.

Initialisation.: \[ \begin{array}{c||cccccc} &✘&✘&&✘&\\\hline\hline &5&2&2&\boxed{0}&1\\ &\boxed{0}&1&3&4&0\\ &1&4&5&0&2\\ &3&\boxed{0}&0&0&2\\ &0&4&1&3&3 \end{array} \]
Itération 1.: Il existe un 0 dans la zone de la matrice qui n'est pas couverte. On le marque. Comme ce 0 est sur la même ligne qu'un 0 sélectionné, on couvre la ligne et découvre la colonne de ce 0 sélectionné. \[ \begin{array}{c||cccccc} &✘&&&✘&\\\hline\hline &5&2&2&\boxed{0}&1\\ &\boxed{0}&1&3&4&0\\ &1&4&5&0&2\\ ✘&3&\boxed{0}&\underline{0}_{}&0&2\\ &0&4&1&3&3 \end{array} \]
Itération 2.: Il existe un 0 dans la zone de la matrice qui n'est pas couverte. On le marque. Comme ce 0 est sur la même ligne qu'un 0 sélectionné, on couvre la ligne et découvre la colonne de ce 0 sélectionné. \[ \begin{array}{c||cccccc} &&&&✘&\\\hline\hline &5&2&2&\boxed{0}&1\\ ✘&\boxed{0}&1&3&4&\underline{0}_{}\\ &1&4&5&0&2\\ ✘&3&\boxed{0}&\underline{0}_{}&0&2\\ &0&4&1&3&3 \end{array} \]
Itération 3.: Il existe un 0 dans la zone de la matrice qui n'est pas couverte. On le marque. \[ \begin{array}{c||cccccc} &&&&✘&\\\hline\hline &5&2&2&\boxed{0}&1\\ ✘&\boxed{0}&1&3&4&\underline{0}_{}\\ &1&4&5&0&2\\ ✘&3&\boxed{0}&\underline{0}_{}&0&2\\ &\underline{0}_{}&4&1&3&3 \end{array} \]

Ce dernier 0 marqué n'est pas sur une ligne avec un 0 sélectionné. On procède donc à la numérotation des 0.

Numérotation $ 0$ .: On note $ 0_0$ le 0 que nous venons de marquer : \[ \begin{array}{c||cccccc} &&&&✘&\\\hline\hline &5&2&2&\boxed{0}&1\\ ✘&\boxed{0}&1&3&4&\underline{0}_{}\\ &1&4&5&0&2\\ ✘&3&\boxed{0}&\underline{0}_{}&0&2\\ &\underline{0}_{0}&4&1&3&3 \end{array} \]
Numérotation $ 1$ .: On note $ 0_1$ le 0 sélectionné sur la colonne du $ 0_0$ : \[ \begin{array}{c||cccccc} &&&&✘&\\\hline\hline &5&2&2&\boxed{0}&1\\ ✘&\boxed{0_1}&1&3&4&\underline{0}_{}\\ &1&4&5&0&2\\ ✘&3&\boxed{0}&\underline{0}_{}&0&2\\ &\underline{0}_{0}&4&1&3&3 \end{array} \]
Numérotation $ 2$ .: On note $ 0_2$ le 0 marqué sur la ligne du $ 0_1$ : \[ \begin{array}{c||cccccc} &&&&✘&\\\hline\hline &5&2&2&\boxed{0}&1\\ ✘&\boxed{0_1}&1&3&4&\underline{0}_{2}\\ &1&4&5&0&2\\ ✘&3&\boxed{0}&\underline{0}_{}&0&2\\ &\underline{0}_{0}&4&1&3&3 \end{array} \]
Fin de la numérotation.: Il n'existe pas de $ 0$ sélectionné dans la colonne du $ 0_2$ , on arête la numérotation. Les 0 avec un indice paire deviennent sélectionnés et les 0 avec un indice impaire sont désélectionnés. \[ \begin{array}{c||cccccc} &&&&✘&\\\hline\hline &5&2&2&\boxed{0}&1\\ ✘&{0}&1&3&4&\boxed{0}\\ &1&4&5&0&2\\ ✘&3&\boxed{0}&\underline{0}_{}&0&2\\ &\boxed{0}&4&1&3&3 \end{array} \] On retourne à l'étape 2.

Étape 2.

La matrice est \[ \begin{array}{cccccc} 5&2&2&\boxed{0}&1\\ {0}&1&3&4&\boxed{0}\\ 1&4&5&0&2\\ 3&\boxed{0}&{0}&0&2\\ \boxed{0}&4&1&3&3 \end{array} \] On ne peut pas sélectionner de nouveau 0. On passe à l'étape 3.

Étape 3.

Initialisation.: \[ \begin{array}{c||cccccc} &✘&✘&&✘&✘\\\hline\hline &5&2&2&\boxed{0}&1\\ &{0}&1&3&4&\boxed{0}\\ &1&4&5&0&2\\ &3&\boxed{0}&{0}&0&2\\ &\boxed{0}&4&1&3&3 \end{array} \]
Itération 1.: Il existe un 0 dans la zone de la matrice qui n'est pas couverte. On le marque. Comme ce 0 est sur la même ligne qu'un 0 sélectionné, on couvre la ligne et découvre la colonne de ce 0 sélectionné. \[ \begin{array}{c||cccccc} &✘&&&✘&✘\\\hline\hline &5&2&2&\boxed{0}&1\\ &{0}&1&3&4&\boxed{0}\\ &1&4&5&0&2\\ ✘&3&\boxed{0}&\underline{0}_{}&{0}&2\\ &\boxed{0}&4&1&3&3 \end{array} \]
Fin du marquage.: Il n'existe plus de 0 dans la partie non couverte. On va à l'étape 4.

Étape 4.

Le plus petit coefficient de la partie non couverte est $ 1$ . On ajoute donc $ 1$ à chaque coefficient sur les lignes couvertes : \[ \begin{array}{c||cccccc} &✘&&&✘&✘\\\hline\hline &5&2&2&\boxed{0}&1\\ &{0}&1&3&4&\boxed{0}\\ &1&4&5&0&2\\ ✘&4&\boxed{1}&{1}&{1}&3\\ &\boxed{0}&4&1&3&3 \end{array} \] Puis on soustrait $ 1$ à tous les coefficients des colonnes non couvertes : \[ \begin{array}{c||cccccc} &✘&&&✘&✘\\\hline\hline &5&1&1&\boxed{0}&1\\ &{0}&0&2&4&\boxed{0}\\ &1&3&4&0&2\\ ✘&4&\boxed{0}&{0}&{1}&3\\ &\boxed{0}&3&0&3&3 \end{array} \] On retourne à l'étape 2.

Étape 2.

La matrice est \[ \begin{array}{cccccc} 5&1&1&\boxed{0}&1\\ {0}&0&2&4&\boxed{0}\\ 1&3&4&0&2\\ 4&\boxed{0}&{0}&{1}&3\\ \boxed{0}&3&0&3&3 \end{array} \] On ne peut pas sélectionner de nouveau 0. On passe à l'étape 3.

Étape 3.

Initialisation.: \[ \begin{array}{c||cccccc} &✘&✘&&✘&✘\\\hline\hline &5&1&1&\boxed{0}&1\\ &{0}&0&2&4&\boxed{0}\\ &1&3&4&0&2\\ &4&\boxed{0}&{0}&{1}&3\\ &\boxed{0}&3&0&3&3 \end{array} \]
Itération 1.: Il existe un 0 dans la zone de la matrice qui n'est pas couverte. On le marque. Comme ce 0 est sur la même ligne qu'un 0 sélectionné, on couvre la ligne et découvre la colonne de ce 0 sélectionné. \[ \begin{array}{c||cccccc} &✘&&&✘&✘\\\hline\hline &5&1&1&\boxed{0}&1\\ &{0}&0&2&4&\boxed{0}\\ &1&3&4&0&2\\ ✘&4&\boxed{0}&\underline{0}_{}&{1}&3\\ &\boxed{0}&3&0&3&3 \end{array} \]
Itération 2.: Il existe un 0 dans la zone de la matrice qui n'est pas couverte. On le marque. Comme ce 0 est sur la même ligne qu'un 0 sélectionné, on couvre la ligne et découvre la colonne de ce 0 sélectionné. \[ \begin{array}{c||cccccc} &✘&&&✘&\\\hline\hline &5&1&1&\boxed{0}&1\\ ✘&{0}&\underline{0}_{}&2&4&\boxed{0}\\ &1&3&4&0&2\\ ✘&4&\boxed{0}&\underline{0}_{}&{1}&3\\ &\boxed{0}&3&0&3&3 \end{array} \]
Itération 3.: Il existe un 0 dans la zone de la matrice qui n'est pas couverte. On le marque. Comme ce 0 est sur la même ligne qu'un 0 sélectionné, on couvre la ligne et découvre la colonne de ce 0 sélectionné. \[ \begin{array}{c||cccccc} &&&&✘&\\\hline\hline &5&1&1&\boxed{0}&1\\ ✘&{0}&\underline{0}_{}&2&4&\boxed{0}\\ &1&3&4&0&2\\ ✘&4&\boxed{0}&\underline{0}_{}&{1}&3\\ ✘&\boxed{0}&3&\underline{0}_{}&3&3 \end{array} \]
Fin du marquage: . Il n'existe plus de 0 dans la partie non couverte. On va à l'étape 4.

Etape 4.

Le plus petit coefficient de la partie non couverte est $ 1$ . On ajoute $ 1$ à chaque coefficient sur les lignes couvertes : \[ \begin{array}{c||cccccc} &&&&✘&\\\hline\hline &5&1&1&\boxed{0}&1\\ ✘&{1}&1&3&5&\boxed{1}\\ &1&3&4&0&2\\ ✘&5&\boxed{1}&1&{2}&4\\ ✘&\boxed{1}&4&1&4&4 \end{array} \] Puis on soustrait $ 1$ à tous les coefficients des colonnes non couvertes : \[ \begin{array}{c||cccccc} &&&&✘&\\\hline\hline &4&0&0&\boxed{0}&0\\ ✘&{0}&0&2&5&\boxed{0}\\ &0&2&3&0&1\\ ✘&4&\boxed{0}&0&{2}&3\\ ✘&\boxed{0}&3&0&4&3 \end{array} \] On retourne à l'étape 2.

Étape 2.

La matrice est \[ \begin{array}{cccccc} 4&0&0&\boxed{0}&0\\ {0}&0&2&5&\boxed{0}\\ 0&2&3&0&1\\ 4&\boxed{0}&0&{2}&3\\ \boxed{0}&3&0&4&3 \end{array} \] On ne peut pas sélectionner de nouveau 0. On passe à l'étape 3.

Étape 3.

Initialisation.

\[ \begin{array}{c||cccccc} &✘&✘&&✘&✘\\\hline\hline &4&0&0&\boxed{0}&0\\ &{0}&0&2&5&\boxed{0}\\ &0&2&3&0&1\\ &4&\boxed{0}&0&{2}&3\\ &\boxed{0}&3&0&4&3 \end{array} \]

Itération 1.

Il existe un 0 dans la zone de la matrice qui n'est pas couverte. On le marque. Comme ce 0 est sur la même ligne qu'un 0 sélectionné, on couvre la ligne et découvre la colonne de ce 0 sélectionné. \[ \begin{array}{c||cccccc} &✘&✘&&&✘\\\hline\hline ✘&4&0&\underline{0}_{}&\boxed{0}&0\\ &{0}&0&2&5&\boxed{0}\\ &0&2&3&0&1\\ &4&\boxed{0}&0&{2}&3\\ &\boxed{0}&3&0&4&3 \end{array} \]

Itération 2.

Il existe un 0 dans la zone de la matrice qui n'est pas couverte. On le marque. Comme ce 0 est sur la même ligne qu'un 0 sélectionné, on couvre la ligne et découvre la colonne de ce 0 sélectionné. \[ \begin{array}{c||cccccc} &✘&&&&✘\\\hline\hline ✘&4&0&\underline{0}_{}&\boxed{0}&0\\ &{0}&0&2&5&\boxed{0}\\ &0&2&3&0&1\\ ✘&4&\boxed{0}&\underline{0}_{}&{2}&3\\ &\boxed{0}&3&0&4&3 \end{array} \]

Itération 3.

Il existe un 0 dans la zone de la matrice qui n'est pas couverte. On le marque. Comme ce 0 est sur la même ligne qu'un 0 sélectionné, on couvre la ligne et découvre la colonne de ce 0 sélectionné. \[ \begin{array}{c||cccccc} &✘&&&&\\\hline\hline ✘&4&0&\underline{0}_{}&\boxed{0}&0\\ ✘&{0}&\underline{0}_{}&2&5&\boxed{0}\\ &0&2&3&0&1\\ ✘&4&\boxed{0}&\underline{0}_{}&{2}&3\\ &\boxed{0}&3&0&4&3 \end{array} \]

Itération 4.

Il existe un 0 dans la zone de la matrice qui n'est pas couverte. On le marque. Comme ce 0 est sur la même ligne qu'un 0 sélectionné, on couvre la ligne et découvre la colonne de ce 0 sélectionné. \[ \begin{array}{c||cccccc} &&&&&\\\hline\hline ✘&4&0&\underline{0}_{}&\boxed{0}&0\\ ✘&{0}&\underline{0}_{}&2&5&\boxed{0}\\ &0&2&3&0&1\\ ✘&4&\boxed{0}&\underline{0}_{}&{2}&3\\ ✘&\boxed{0}&3&\underline{0}_{}&4&3 \end{array} \]

Itération 5.

Il existe un 0 dans la zone de la matrice qui n'est pas couverte. On le marque. \[ \begin{array}{c||cccccc} &&&&&\\\hline\hline ✘&4&0&\underline{0}_{}&\boxed{0}&0\\ ✘&{0}&\underline{0}_{}&2&5&\boxed{0}\\ &\underline{0}_{}&2&3&0&1\\ ✘&4&\boxed{0}&\underline{0}_{}&{2}&3\\ ✘&\boxed{0}&3&\underline{0}_{}&4&3 \end{array} \] Ce dernier 0 marqué n'est pas sur une ligne avec un 0 sélectionné. On procède donc à la numérotation des 0.

Numérotation 0.: On note $ 0_0$ le 0 que nous venons de marquer. \[ \begin{array}{c||cccccc} &&&&&\\\hline\hline ✘&4&0&\underline{0}_{}&\boxed{0}&0\\ ✘&{0}&\underline{0}_{}&2&5&\boxed{0}\\ &\underline{0}_{0}&2&3&0&1\\ ✘&4&\boxed{0}&\underline{0}_{}&{2}&3\\ ✘&\boxed{0}&3&\underline{0}_{}&4&3 \end{array} \]
Numérotation 1.: On note $ 0_1$ le 0 sélectionné sur la colonne de $ 0_0$ . \[ \begin{array}{c||cccccc} &&&&&\\\hline\hline ✘&4&0&\underline{0}_{}&\boxed{0}&0\\ ✘&{0}&\underline{0}_{}&2&5&\boxed{0}\\ &\underline{0}_{0}&2&3&0&1\\ ✘&4&\boxed{0}&\underline{0}_{}&{2}&3\\ ✘&\boxed{0_1}&3&\underline{0}_{}&4&3 \end{array} \]
Numérotation 2.: On note $ 0_2$ le 0 marqué sur la ligne de $ 0_1$ . \[ \begin{array}{c||cccccc} &&&&&\\\hline\hline ✘&4&0&\underline{0}_{}&\boxed{0}&0\\ ✘&{0}&\underline{0}_{}&2&5&\boxed{0}\\ &\underline{0}_{0}&2&3&0&1\\ ✘&4&\boxed{0}&\underline{0}_{}&{2}&3\\ ✘&\boxed{0_1}&3&\underline{0}_{2}&4&3 \end{array} \]
Fin de la numérotation.: Il n'existe pas de $ 0$ sélectionné dans la colonne du $ 0_2$ , on arête la numérotation. Les 0 avec un indice paire deviennent sélectionnés et les 0 avec un indice impaire sont désélectionnés. \[ \begin{array}{c||cccccc} &&&&&\\\hline\hline ✘&4&0&\underline{0}_{}&\boxed{0}&0\\ ✘&{0}&\underline{0}_{}&2&5&\boxed{0}\\ &\boxed{0}&2&3&0&1\\ ✘&4&\boxed{0}&\underline{0}_{}&{2}&3\\ ✘&0&3&\boxed{0}&4&3 \end{array} \] On retourne à l'étape 2.

Étape 2.

La matrice est \[ \begin{array}{cccccc} 4&0&\underline{0}_{}&\boxed{0}&0\\ {0}&\underline{0}_{}&2&5&\boxed{0}\\ \boxed{0}&2&3&0&1\\ 4&\boxed{0}&\underline{0}_{}&{2}&3\\ 0&3&\boxed{0}&4&3 \end{array} \] Il y a exactement un 0 sélectionné sur chaque ligne et chaque colonne. L'algorithme prend fin et on a trouvé l'affection optimale. Précisément si l'on reprend la matrice initiale en conservant les affectations \[ \begin{array}{cccccc} 9&8&6&\boxed{4}&6\\ 3&6&6&7&\boxed{4}\\ \boxed{4}&9&8&3&6\\ 7&\boxed{6}&4&4&7\\ 2&8&\boxed{3}&5&6 \end{array} \] on trouve que l'affection minimale a un poids de $ 4+4+4+6+3=21$ .

Exercice

%Résoudre le problème pour l'entreprise Lune Nette. %