Exercices corrigés sur les problèmes d’affectation

La page présente plusieurs exercices corrigés sur les problèmes de planification et d’ordonnancement automatisés, en particulier sur les problèmes d’affectation.

problèmes d'affectation

Exercise 1

Le réseau de la côte atlantique déssert quatre villes. La direction veut attribuer quatre usines aux villes. Le prix pour envoyer de l’énergie d’une usine à chaque ville est décrit ci-dessous :

 

Raleigh

Atlanta

Durham

Clemson

Plant A

210

90

180

160

Plant B

100

70

130

200

Plant C

175

105

140

170

Plant D

80

65

105

120

Une usine ne peut mériter qu’une seule ville, et une ville ne peut tirer des énergies que d’une seule usine. Trouvez la meilleure mission au moindre coût.

Solution

Après la première réduction :

 

R

TO

D

VS

TO

105

0

55

15

B

15

0

25

75

VS

35

0

0

10

D

0

0

5

0

Puis :

 

R

TO

D

VS

TO

90

0

40

0

B

0

0

10

60

VS

55

15

0

10

D

0

15

5

0

Solution : 90+100+140+120=450.

Exercise 2

Permuter les colonnes d’une matrice carrée de manière à minimiser la somme des éléments sur la diagonale principale.

8

16

15

91

64

83

42

93

75

27

76

95

75

81

50

20

42

96

90

24

38

28

2

15

81

Solution

Trouvez une solution d’affectation à cette matrice. Réorganisez les colonnes de façon à ce que la solution forme une diagonale.

Exercise 3

Trois robots {a,b,c} doivent terminer trois tâches {t1, t2, t3} dans la grille suivante. Il faut une journée à un robot pour passer d’une cellule à l’une de ses voisines.

corrected exercises automated planning and scheduling problems assignment problems

Dans le tableau suivant, nous listons les jours où chaque robot peut terminer chaque tâche seul. Les tâches doivent être terminées dès que possible.

corrected exercises automated planning and scheduling problems assignment problems

Solution

Ajoutez la distance de Manhattan en jours au dernier tableau. Résoudre le problème d’affectation.

Exercise 4

Braneast Airlines doit doter en personnel les vols défaillants entre New York et Chicago indiqués dans le tableau ci-dessous. Chacun des équipages de Braneast vit à New York ou à Chicago. Chaque jour, un équipage doit effectuer un vol NY-Chicago et un vol Chicago-NY avec au moins une heure d’arrêt entre les vols.

Braneast veut programmer les équipes pour minimiser le temps d’arrêt total. Élaborez un problème d’affectation qui peut être utilisé pour atteindre cet objectif. Bien sûr, certaines affectations ne sont pas possibles. Trouvez les affectations de vol qui minimisent le temps d’arrêt total. Combien d’équipages devraient être basés dans chaque ville ? Supposons qu’à la fin de la journée, chaque équipage doit être dans sa ville d’origine.

corrected exercises automated planning and scheduling problems assignment problems

Solution

Le tableau d’affectation est construit comme suit : pour le premier vol au départ de Chicago, compte tenu de l’heure d’arrivée à NY, combien de temps l’équipage doit attendre à l’aéroport. Par exemple pour le premier vol de Chicago, il arrive à 10h :

Flight

1

2

3

4

5

6

7

Leave New York

7

8

10

12

14

16

18

Waiting time

impossible

impossible

impossible

2

4

6

8

Nous notons que les vols 4, 5, 6, 7 de Chicago ne peuvent pas être le point de départ, nous calculons donc le temps d’attente depuis le vol de New York. Notez que le vol 7 de NY ne peut pas être un point de départ, nous calculons donc le temps d’attente depuis le vol de Chicago. De chacun des éléments du tableau, nous retenons la valeur la plus basse calculée (pour les vols depuis Chicago et NY).

corrected exercises automated planning and scheduling problems assignment problems

Solution :

corrected exercises automated planning and scheduling problems assignment problems

Commence à New York : (1,3), (2,4), (3,5), (5,6), (6,7).

Commence à Chicago : (4,1), (7,2).

Temps d’arrêt total = 25h.

corrected exercises automated planning and scheduling problems assignment problems

Exercise 5

Considérez les données du tableau ci-dessous. Si un équipage basé à Mumbai arrive à Delhi sur un vol donné, il doit retourner à Mumbai sur un vol ultérieur. Supposons que pour tout appariement donné, l’équipage sera basé dans la ville qui entraîne la plus petite escale.

Le problème est de trouver les appariements de manière à minimiser le temps au sol loin du domicile, sous réserve d’un intervalle minimum d’une heure entre l’arrivée et le départ. Compte tenu des couples de vols, où les équipages doivent-ils être basés ?

corrected exercises automated planning and scheduling problems assignment problems

Solution

Comme dans l’exercice précédent, calculez d’abord les matrices de temps d’escale, l’une pour l’escale à Mumbai et l’autre pour Delhi.

corrected exercises automated planning and scheduling problems assignment problems

Nous calculons maintenant le minimum des valeurs pour les 36 paires et construisons le tableau ci-dessous. Par exemple (7,2) est le minimum entre (7,2) dans la première matrice et (2,7) dans la seconde.

corrected exercises automated planning and scheduling problems assignment problems

La solution de ce problème est les paires (7,3) de Mumbai, (8,4) de Mumbai, (9,2) de Delhi, (10,5) de Mumbai, (11,6) de Delhi, (12, 1) depuis Delhi avec un temps d’arrêt total = 18h.

Exercise 6

Résoudre le problème suivant comme un problème d’affectation.

Minimiser     4X11+ 6X12+ 5X13+ 5X14+ 7X21+ 4X22+ 5X23+ 6X24  + 4X31+ 7X32+ 6X33+ 4X34  + 5X41+ 3X42+ 4X43+ 7X44

St. X11+ X12+ X13+ X14=1

X21+ X22+ X24+ X24=1

X31+ X32+ X33+ X34=1

X41+ X42+ X43+ X44=1

X11+ X21+ X31+ X41=1

X12+ X22+ X32+ X42=1

X13+ X23+ X33+ X43=1

X14+ X24+ X34+ X44=1

Solution

Vous devez résoudre le problème d’affectation :

corrected exercises automated planning and scheduling problems assignment problems

Exercise 7

Résoudre le problème suivant comme un problème d’affectation.

corrected exercises automated planning and scheduling problems assignment problems

Solution

Le problème d’affectation est décrit dans le tableau ci-dessous :

 

1

2

3

1

5

9

inf

2

inf

2

inf

3

inf

1

1

Exercise 8

Le Département d’histoire de l’art souhaite proposer six cours par semestre. Il y a sept professeurs dans le département, dont chacun ne peut enseigner que certains cours, comme indiqué dans le tableau. Est-il possible d’attribuer les six cours aux professeurs afin qu’aucun professeur n’enseigne plus d’un cours ?

corrected exercises automated planning and scheduling problems assignment problems

Solution

Le problème d’affectation est décrit dans le tableau ci-dessous :

 

Ant

Bat

Cat

Dodo

Frog

Gnat

Hog

Antique

1

1

1

1

inf

inf

inf

Renaissance

1

inf

inf

inf

1

1

inf

Baroque

1

inf

inf

inf

1

inf

inf

Impressionism

inf

inf

inf

inf

1

1

inf

Modern

inf

inf

1

inf

inf

1

1

Contemporary

1

inf

inf

inf

inf

1

inf

dummy

1

1

1

1

1

1

1

Afin de trouver une mission, il est préférable d’utiliser la méthode du stepping stone au lieu de la méthode hongroise.

To share
en_GBEN
%d bloggers like this: