Najkrótsza ścieżka problemu w programie Excel

Sformułuj model | Trial i błąd | Rozwiąż model

Użyj solver w Przewyższać znaleźć najkrótsza droga z węzła S do węzła T w sieci nieokierunkowanej. Punkty w sieci nazywane są węzłami (S, A, B, C, D, E i T). Linie w sieci nazywane są łukami (SA, SB, SC, AC itd.).

Sformułuj model

Model, który zamierzamy rozwiązać, wygląda następująco w Excelu.

1. Aby sformułować to najkrótszy problem z trasą, odpowiedz na następujące trzy pytania.

za. Jakie decyzje należy podjąć? W przypadku tego problemu potrzebujemy Excela, aby dowiedzieć się, czy łuk jest na najkrótszej ścieżce, czy nie (Tak = 1, Nie = 0). Na przykład, jeśli SB jest częścią najkrótszej ścieżki, komórka F5 jest równa 1. Jeśli nie, komórka F5 jest równa 0.

b. Jakie są ograniczenia tych decyzji? Przepływ netto (Flow Out - Flow In) każdego węzła powinien być równy Supply / Demand. Węzeł S powinien mieć tylko jeden łuk wyjściowy (Przepływ netto = 1). Węzeł T powinien mieć tylko jeden łuk wejściowy (Przepływ netto = -1). Wszystkie pozostałe węzły powinny mieć jeden łuk wyjściowy i jeden łuk, jeśli węzeł znajduje się na najkrótszej ścieżce (przepływ netto = 0) lub brak przepływu (przepływ netto = 0).

do. Jaka jest ogólna miara wydajności dla tych decyzji? Ogólną miarą wydajności jest całkowita odległość najkrótszej ścieżki, więc celem jest zminimalizowanie tej ilości.

2. Aby model był łatwiejszy do zrozumienia, nazwij następujące zakresy.

Nazwa zakresu	Komórki
Z	B4: B21
Do	C4: C21
Dystans	D4: D21
Udać się	F4: F21
Przepływy netto	I4: I10
Prośba o zaopatrzenie	K4: K10
Całkowity dystans	F23

3. Wstaw następujące funkcje.

Wyjaśnienie: Funkcje SUMAI obliczają przepływ netto każdego węzła. Dla węzła S funkcja SUMAF sumuje wartości w kolumnie Przejdź z literą "S" w kolumnie Od. W rezultacie tylko komórki F4, F5 lub F6 mogą mieć wartość 1 (jeden łuk wyjściowy). Dla węzła T funkcja SUMAF sumuje wartości w kolumnie Przejdź z literą "T" w kolumnie Do. W rezultacie tylko ogniwo F15, F18 lub F21 może mieć wartość 1 (jeden łuk wejściowy). W przypadku wszystkich innych węzłów program Excel wyszukuje kolumnę Od i Do. Całkowita odległość równa się sumproduct Distance and Go.

Trial i błąd

Dzięki takiemu preparatowi łatwo jest przeanalizować każde rozwiązanie próbne.

1. Na przykład ścieżka SBET ma całkowitą odległość 16.

Nie ma potrzeby używania prób i błędów. Opiszemy dalej, jak Excel Solver może być użyty do szybkiego znalezienia optymalnego rozwiązania.

Rozwiąż model

Aby znaleźć optymalne rozwiązanie, wykonaj następujące kroki.

1. Na karcie Dane w grupie Analiza kliknij opcję Rozwiązywanie problemów.

Uwaga: nie można znaleźć przycisku Solver? Kliknij tutaj, aby załadować dodatek Solver.

Wprowadź parametry solwera (czytaj). Wynik powinien być zgodny z poniższym obrazkiem.

Masz wybór wpisywania nazw zakresów lub klikania komórek w arkuszu kalkulacyjnym.

2. Wprowadź TotalDistance dla celu.

3. Kliknij Min.

4. Wprowadź Go, aby zmienić zmienne komórki.

5. Kliknij przycisk Dodaj, aby wprowadzić następujące ograniczenie.

6. Zaznacz "Nieograniczające zmienne bez zmian" i wybierz "Simplex LP".

7. Na koniec kliknij Rozwiąż.

Wynik:

Optymalne rozwiązanie:

Wniosek: SADCT jest najkrótszą ścieżką o całkowitej odległości 11.