Formule Excel pour optimiser un itinéraire où chaque ligne représente une «station» différente qui peut faire des choses différentes

Question

Je ne savais pas comment formuler cette question.

Voici un exemple minimum viable:

• Jane peut faire A, B, D. Shes à 1 km.
• Jack peut faire B, D, F. Il est à 1,5 km.
• Le maréchal peut faire E, F, A. Il est à 20 km.
• Polly peut faire E, D, C. Elle est à 10 km.
• James peut faire C, F, B. Il est à 15 km.

La feuille a des lignes pour chaque personne et des colonnes pour chaque action, AF.

Je veux trouver quelle combinaison de personnes je dois aller pour compléter A, C, F avec le nombre minimum de personnes visitées. Si deux combinaisons sont valides, j'aimerais celle avec la plus petite distance.

(Donc, la solution à ce qui précède est Jane et James)

Sur ma première rangée, j'ai des cases à cocher pour chaque chose: A, B, C, D, E, F.J'ai sélectionné A, C, F.

Quelle formule utiliserais-je pour mettre en évidence ou colorer les personnes que je devrais visiter? Si cela ne peut pas être fait dans Excel, comment s'appellerait un algorithme pour résoudre ce problème pour que je puisse l'implémenter en utilisant un langage de programmation?

Answer 1

C'est fait!

Concept

Force brute. Calculez la distance de l'itinéraire pour chaque combinaison de personnes à visiter. Ignorez les combinaisons qui n'offrent pas toutes les tâches requises (AF). Sélectionnez l'itinéraire avec la distance d'itinéraire la plus basse.

la mise en oeuvre

L'idée est d'utiliser la représentation binaire pour réduire les mathématiques requises. Disons que chaque personne reçoit 1 bit dans un nombre entier, par exemple 1001 signifie visiter la personne 1 et la personne 4. Donc, si nous avons 8 personnes, nous avons 2 ^ 8-1 = 255 combinaisons de personnes à visiter. Nous allons faire des combinaisons dans les lignes numérotées 1..255.

Maintenant, nous faisons la même chose pour les tâches assignées à chaque personne. La tâche A est le bit 1, B est le bit 2 ... etc. Ainsi, si la personne 010 propose des tâches avec un masque de tâches (TM) de 0101, alors la personne 2 propose A et C, et la personne 001 avec TM 1000 propose uniquement D.

Si nous prévoyons de rendre visite aux personnes 011 (001 ET 010), les tâches combinées proposées sont

=BITOR("TM for 001", "TM for 010") which will result in TM 1101 (tasks A, C, D)

Les tâches combinées proposées pour tous sont

=BITOR("TM for 001", BITOR("TM for 010", BITOR("TM for 100",... "TM for 10000000"))))))))

Donc, pour savoir quelles tâches sont offertes par une combinaison aléatoire de personnes x, nous devons BITORER ensemble uniquement les MT pertinentes:

=BITOR("TM for 001" * x0, BITOR("TM for 010" * x1, BITOR("TM for 100" * x2,... "TM for 10000000" * x7))))))))

où xi est le ième bit de x

=BITAND(1,BITRSHIFT(x,i))

De même pour déterminer la distance totale pour combinaison de personnes / itinéraire x

"Person 1 distance" * x0 + "Person 2 distance" * x1 +... "Person 8 distance" * x7

Maintenant, pour déterminer si, pour les personnes x avec TM y, toutes les tâches requises z peuvent être effectuées (c'est-à-dire une route valide):

=IF(BITAND(y,z) = z, "All tasks offered by x", "All tasks cannot be done")

And the distance for valid routes only

=IF(BITAND(y,z) = z, *distance calc above*,"") so invalid routes are blank ""

Calculez maintenant ceci pour chaque combinaison possible, par exemple (1..255) et recherchez la distance de route minimale valide avec MIN (...) , puis trouvez le meilleur itinéraire x avec MATCH (MIN (...), colonne de distances d'itinéraire , 0) qui correspond à cette distance d'itinéraire minimale. Divisez x en bits x0 .. x7 et utilisez la mise en forme conditionnelle pour mettre en évidence chaque personne dans le meilleur itinéraire.