Formuła programu Excel do optymalizacji trasy, w której każdy wiersz reprezentuje inną „stację”, która może wykonywać różne czynności

Question

Nie byłem pewien, jak sformułować to pytanie.

Oto minimalny realny przykład:

• Jane może zrobić A, B, D. Jest 1 km stąd.
• Jack może zrobić B, D, F. Jest 1,5 km stąd.
• Marszałek może zrobić E, F, A. Jest 20 km stąd.
• Polly może zrobić E, D, C. Jest 10 km stąd.
• James może zrobić C, F, B. Jest 15 km stąd.

Arkusz zawiera wiersze dla każdej osoby i kolumny dla każdej czynności, AF.

Chcę dowiedzieć się, jaką kombinację osób muszę przejść, aby ukończyć A, C, F przy minimalnej liczbie odwiedzonych osób. Jeśli dwie kombinacje są prawidłowe, chciałbym tę z najmniejszą odległością.

(Więc rozwiązaniem powyższego są Jane i James)

W pierwszym rzędzie mam pola wyboru dla każdej rzeczy: A, B, C, D, E, F. Wybrałem A, C, F.

Jakiej formuły użyłbym do wyróżnienia lub oznaczenia kolorami osób, które powinienem odwiedzić? Jeśli nie można tego zrobić w programie Excel, jak nazwałby się algorytm rozwiązywania tego problemu, abym mógł go zaimplementować za pomocą języka programowania?

Answer 1

Zrobione!

Pojęcie

Brutalna siła. Oblicz odległość trasy dla każdej kombinacji odwiedzanych osób. Zignoruj ​​kombinacje, które nie oferują wszystkich wymaganych zadań (AF). Wybierz trasę o najmniejszej odległości.

Realizacja

Chodzi o to, aby użyć reprezentacji binarnej, aby zmniejszyć wymaganą matematykę. Powiedzmy, że każdej osobie przypisany jest 1 bit w liczbie całkowitej, np. 1001 oznacza wizytę osoby 1 i osoby 4. Więc jeśli mamy 8 osób, mamy 2 ^ 8-1 = 255 kombinacji osób do odwiedzenia. Zrobimy kombinacje w wierszach o numerach 1..255.

Teraz robimy to samo dla przydzielonych zadań każdej osobie. Zadanie A to bit 1, B to bit 2 ... itd. Więc jeśli osoba 010 oferuje zadania z maską zadań (TM) 0101, to osoba 2 oferuje A i C, a osoba 001 z TM 1000 oferuje tylko D.

Jeśli planujemy odwiedzić osoby 011 (001 i 010), to oferujemy połączone zadania

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

Połączone zadania oferowane dla każdego są

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

Aby więc stwierdzić, jakie zadania oferuje jakaś losowa kombinacja osób x, musimy BITOROWAĆ razem tylko odpowiednie bazy TM:

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

gdzie xi to i-ty bit w x

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

Podobnie, aby określić całkowitą odległość dla kombinacji osób / trasy x

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

Teraz, aby ustalić, czy dla osób x z TM y wszystkie wymagane zadania z można wykonać (tj. Poprawna trasa):

=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 ""

Teraz oblicz to dla każdej możliwej kombinacji, np. (1..255) i poszukaj minimalnej prawidłowej odległości trasy za pomocą MIN (...) , a następnie znajdź najlepszą trasę x za pomocą MATCH (MIN (...), kolumna odległości trasy , 0), który odpowiada tej minimalnej odległości trasy. Podziel x na bity x0 ... x7 i użyj formatowania warunkowego, aby wyróżnić każdą osobę najlepszą trasą.