Probleme d'affectation

Probleme d'affectation

Problème d'affectation

Le problème d'affectation est un problème classique de recherche opérationnelle. L'objectif est de déterminer un couplage maximum dans un graphe biparti valué.

Applications pratiques

L'application la plus classique de ce problème est l'affectation de n employés à n tâches. Chaque employé ne peut être affecté qu'à une seule tâche et il a un degré de compétence différent pour chacune d'entre elles. On cherche à trouver l'affectation qui maximise la compétence totale des employés sur les tâches.

Méthodes de résolution

L'algorithme hongrois permet de résoudre ce problème avec une complexité de O(n3)

Exemple d'utilisation en Turbo Pascal

USES crt, dos;
(************************************
fichier : affect.pas

*   METHODE D'AFFECTATION           *
Application de l'algorithme Hongrois
Valeur en % des preferences
de 4 candidats … 4 postes de travail*
            Postes
            1  2  3  4
            ----------
candidat 1  10 20 80 60
candidat 2  10 30 70 20
candidat 3  60 30 80 20
candidat 4  50 60 80 40
---------------------------------
Contenu du fichier "affect01.txt"
--------------------------------
Nb de postes
4
Matrice de marquage des affectations
10;20;80;60;
10;30;70;20;
60;30;80;20;
50;60;80;40;
--------------------------------
solution d'affectation
         candidat 1  => poste 2
         candidat 2  => poste 1
         candidat 3  => poste 4
         candidat 4  => poste 3
************************************)
CONST Maxi = 32767;
VAR
	NP	{ NOMBRES DE POSTES }
		: INTEGER;
	C,	{ COUT D'AFFECTATION DU POSTE INDICE }
	M	{ MATRICE DE MARQUAGE DES AFFECTATIONS }
		: ARRAY[0..10, 0..10] OF INTEGER;

(***********************)
PROCEDURE Affiche_Entete;
(***********************)
BEGIN
     CLRSCR;
	WRITELN('MODELE D''AFFECTATION');
	WRITELN; WRITELN;
END;

(*****************)
PROCEDURE Infile ;
(*****************)
CONST	Separ = ';';
VAR		CodeErr  		: INTEGER;
		Ligne		: STRING;
		x, col, lig	: BYTE;
		affectationDataFile : TEXT;
BEGIN
	ASSIGN(affectationDataFile ,   'affect01.txt');
	RESET(affectationDataFile);
	WHILE NOT EOF (affectationDataFile) DO
	BEGIN
		READLN(affectationDataFile ,   Ligne);	{ pour les commentaires }
	     WRITE(Ligne);
	     READLN(affectationDataFile ,   Ligne);
	     VAL(Ligne ,   NP ,   CodeErr);		{ N = nb de postes }
	     WRITELN('  :  ' ,   NP);
	
	     READLN(affectationDataFile ,   Ligne);	{ pour les commentaires }
	     WRITELN(Ligne);

	     FOR lig := 1 TO NP DO
          BEGIN
               READLN(affectationDataFile ,   Ligne);
			FOR col := 1 TO NP DO
			BEGIN
               	x := POS(Separ, Ligne);
				VAL(COPY(Ligne,1 , x - 1) , C[lig, col] , CodeErr);
				Ligne := COPY(Ligne, x + 1, LENGTH(Ligne) - x);
				WRITE(C[lig, col]:5);
			END;
               WRITELN;
          END;
     END;
     WRITELN;
	CLOSE(affectationDataFile);
END;
(**************************)
PROCEDURE COUT_AFFECTATION;
(**************************)
{ saisie directe de la matrice }
VAR	i, j : BYTE;
BEGIN

	WRITE('Nb de postes : ');
	READLN(NP);


	WRITELN;
	WRITELN('Cout d''affectation des candidats');
	FOR I := 1 TO NP DO
	BEGIN
		WRITELN('Candidat N. ', I);
		FOR J := 1 TO NP DO
		BEGIN
			WRITE('  AFFECTATION POSTE ', J, ' ');
			READLN(C[I, J]);
		END;
		WRITELN;
	END;

END;	{ COUT_AFFECTATION }
(*****************************)
PROCEDURE ALGORITHME_HONGROIS;
(*****************************)
VAR
	Z		{ DRAPEAU DE MARQUAGE D'UN ZERO }
          : BOOLEAN;
     F,		{ FLAG DE FIN; AFFECTATION 0PTI. TROUVEE }
	MIN		{ DETECTION D'UNE VALEUR MINIMALE }
		: INTEGER;
	(**************)
	PROCEDURE ZEROS;
	(**************)
	VAR i, j : BYTE;
	BEGIN
		WRITELN('Zeros');
		Z := FALSE;
		FOR I := 1 TO NP DO
		BEGIN
			MIN := C[I, 1];
			FOR J := 1 TO NP DO
			BEGIN
				IF C[I, J] = 0 THEN Z := TRUE;
				IF C[I, J] < MIN THEN MIN := C[I, J];
			END; { FOR J }

			IF (Z = TRUE) THEN
				Z := FALSE
			ELSE
				FOR J := 1 TO NP DO C[I, J] := C[I, J] - MIN;
		END; { FOR I }

		FOR J := 1 TO NP DO
		BEGIN
			MIN := C[1, J];
			FOR I := 1 TO NP DO
			BEGIN
				IF C[I, J] = 0 THEN Z := TRUE;
				IF C[I, J] < MIN THEN MIN := C[I, J];
			END; {FOR I }

			IF Z = TRUE THEN
				Z := FALSE
			ELSE
				FOR I := 1 TO NP DO C[I, J] := C[I, J] - MIN;
		END; { FOR J }
	END; { ZEROS }
	(*****************)
	PROCEDURE AFFECTER;
	(*****************)
	VAR	i, j, k,
		ZI, ZJ	{ COORDONNEES DE LA CAGE AFFECTEE }
			: BYTE;
		MiniZeros, 	{ AFFECTATION D'UN ZERO LIE AVEC LE MINIMUM DES ZEROS }
		NZ		{ CALCUL DU NOMBRE DE ZEROS }
			: INTEGER;
	BEGIN
		WRITELN('Affecter');
		FOR I := 1 TO NP DO
		BEGIN
			FOR J := 1 TO NP DO BEGIN M[I, J] := 0; C[0, J] := 0; END;
			C[I, 0] := 0;
		END; { FOR I }

		FOR I := 1 TO NP DO
		BEGIN
			MiniZeros := Maxi;
			FOR J := 1 TO NP DO
			BEGIN
				IF NOT ((C[I, J] <> 0) OR (M[I, J] <> 0)) THEN
				BEGIN
					NZ := 0;
					FOR K := 1 TO NP DO IF C[K, J] = 0 THEN NZ := NZ + 1;
					IF NZ < MiniZeros THEN BEGIN MiniZeros := NZ; ZI := I; ZJ := J; END;
				END;
			END; { FOR J }
			M[ZI, ZJ] := 1;

			FOR K := 1 TO NP DO
				IF (C[K, ZJ] = 0) AND (M[K, ZJ] = 0) THEN M[K, ZJ] := -1;

			FOR K := 1 TO NP DO
				IF (C[ZI, K] = 0) AND (M[ZI, K] = 0) THEN M[ZI, K] := -1;
		END; { FOR I }

		F := 0;
		FOR I := 1 TO NP DO
			FOR J := 1 TO NP DO IF M[I, J] = 1 THEN F := F + 1;

	END; { AFFECTER }
	(****************)
	PROCEDURE MARQUER;
	(****************)
	VAR i, j	: BYTE;
		N1, M1 	{ PRESENCE D'UN ZERO MARQUE }
			: BYTE;
	BEGIN
          WRITELN('Marquer');
		REPEAT
               M1 := 0;
               FOR I := 1 TO NP DO
			BEGIN
				N1 := 0;
				FOR J := 1 TO NP DO IF M[I, J] = 1 THEN N1 := 1;

				IF (N1 = 0) AND (C[I, 0] = 0) THEN
                       BEGIN C[I, 0] := 1; M1 := 1; END;
			END; { FOR i }

			FOR J := 1 TO NP DO
				FOR I := 1 TO NP DO
					IF (M[I, J] = -1) AND (C[I, 0] = 1) AND (C[0, J] = 0) THEN
					   BEGIN C[0, J] := 1; M1 := 1; END;

			FOR I := 1 TO NP DO
				FOR J := 1 TO NP DO
					IF (M[I, J] = 1) AND (C[0, J] = 1) AND (C[I, 0] = 0) THEN
					   BEGIN	C[I, 0] := 1; M1 := 1; END;
		UNTIL (M1 = 0);
	END; { MARQUER }
	(*****************)
	PROCEDURE SOUS_ADD;
	(*****************)
	VAR	i, j : BYTE;
		MIN, 		{ DETECTION D'UNE VALEUR MINIMALE }
		A, B 		{ SERVENT AUX CHANGEMENTS D'AFFECTATIONS }
			: INTEGER;
	BEGIN
		WRITELN ('Sous_Add');
		MIN := Maxi;

		FOR I := 1 TO NP DO
			FOR J := 1 TO NP DO
			BEGIN
				A := C[I, 0]; B := C[0, J];
				IF (A = 1) AND (B = 0) AND (C[I, J] < MIN) THEN MIN := C[I, J];
			END; {FOR J , FOR I }

		FOR I := 1 TO NP DO
			FOR J := 1 TO NP DO
			BEGIN
				A := C[I, 0]; B := C[0, J];
				IF (A = 1) AND (B = 0) THEN C[I, J] := C[I, J] - MIN;
				IF (A = 0) AND (B = 1) THEN C[I, J] := C[I, J] + 2 * MIN;
			END; {FOR J, FOR I }
	END;
(********************)
BEGIN
     WRITELN('Resolution par l''algorithme Hongrois');
	REPEAT
		ZEROS;
		AFFECTER;
		MARQUER;
		SOUS_ADD;
		AFFECTER;
	UNTIL (F = NP);
END;
(*****************************)
PROCEDURE EDITION_AFFECTATION;
(*****************************)
VAR i, j : BYTE;
BEGIN
     WRITELN;
     WRITELN('Solution');
	FOR I := 1 TO NP DO
	BEGIN
		FOR J := 1 TO NP DO
			IF M[I, J] = 1 THEN WRITELN('CANDIDAT ', I, ' => POSTE ', J);
	END;
END; {EDITION_AFFECTATION }

BEGIN
     Affiche_Entete;
	InFile;
	(* COUT_AFFECTATION; *)
	ALGORITHME_HONGROIS;
	EDITION_AFFECTATION;

		READLN;
END.
Ce document provient de « Probl%C3%A8me d%27affectation ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Probleme d'affectation de Wikipédia en français (auteurs)

Игры ⚽ Нужна курсовая?

Regardez d'autres dictionnaires:

  • Problème d'affectation — Le problème d affectation est un problème classique de recherche opérationnelle. L objectif est de déterminer un couplage maximum dans un graphe biparti valué. Le problème d affectation peut être résolu en temps polynomial par l algorithme… …   Wikipédia en Français

  • Probleme SAT — Problème SAT On nomme problème SAT un problème de décision visant à savoir s il existe une solution à une série d équations logiques données. En termes plus précis : une valuation sur un ensemble de variables propositionnelles[1] telle qu… …   Wikipédia en Français

  • Probleme des lecteurs et des redacteurs — Problème des lecteurs et des rédacteurs Le problème des lecteurs et des rédacteurs est un problème classique en théorie informatique, qui permet de modéliser les accès à des bases de données. Il fut énoncé sous cette forme par Edsger Dijkstra,… …   Wikipédia en Français

  • Problème SAT — On nomme problème SAT un problème de décision visant à savoir s il existe une solution à une série d équations logiques données. En termes plus précis : une évaluation sur un ensemble de variables propositionnelles[1] telle qu une formule… …   Wikipédia en Français

  • Problème des lecteurs et des rédacteurs — Le problème des lecteurs et des rédacteurs est un problème classique en théorie informatique, qui permet de modéliser les accès à des bases de données. Il fut énoncé sous cette forme par Edsger Dijkstra, qui est également à l origine du problème… …   Wikipédia en Français

  • SAT (problème) — Problème SAT On nomme problème SAT un problème de décision visant à savoir s il existe une solution à une série d équations logiques données. En termes plus précis : une valuation sur un ensemble de variables propositionnelles[1] telle qu… …   Wikipédia en Français

  • Algorithme hongrois — L algorithme hongrois ou méthode hongroise (parfois appelé aussi algorithme de Kuhn) est un algorithme d optimisation combinatoire, qui résout le problème d affectation en temps polynomial. Il a été proposé en 1955 par le mathématicien américain… …   Wikipédia en Français

  • Méthode de l'entropie croisée — Traduction à relire Cross entropy method → …   Wikipédia en Français

  • Optimisation multi-objectif — L optimisation multiobjectif est branche de l optimisation combinatoire dont la particularité est de chercher à optimiser simultanément plusieurs objectifs d un même problème (contre un seul objectif pour l optimisation combinatoire classique).… …   Wikipédia en Français

  • Optimisation multiobjectif — L optimisation multiobjectif est une branche de l optimisation combinatoire dont la particularité est de chercher à optimiser simultanément plusieurs objectifs d un même problème (contre un seul objectif pour l optimisation combinatoire… …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”