Sformułuj model | Próba i błąd | Rozwiąż model
Użyj solvera w Przewyższać znaleźć najkrótsza droga od węzła S do węzła T w sieci nieskierowanej. 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 itp.).
Sformułuj model
Model, który rozwiążemy, wygląda w Excelu w następujący sposób.
1. Aby to sformułować problem z najkrótszą ścieżką, odpowiedz na trzy poniższe pytania.
a. Jakie decyzje należy podjąć? W przypadku tego problemu potrzebujemy programu Excel, aby dowiedzieć się, czy łuk znajduje się 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 (wypływ - napływ) każdego węzła powinien być równy podaży/popytowi. Węzeł S powinien mieć tylko jeden łuk wychodzący (przepływ netto = 1). Węzeł T powinien mieć tylko jeden łuk przychodzący (przepływ netto = -1). Wszystkie inne węzły powinny mieć jeden łuk wychodzący i jeden łuk przychodzący, jeśli węzeł znajduje się na najkrótszej ścieżce (przepływ netto = 0) lub brak przepływu (przepływ netto = 0).
C. Jaka jest ogólna miara skuteczności 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, utwórz następujące nazwane zakresy.
| Nazwa zakresu | Komórki |
|---|---|
| Z | B4:B21 |
| W celu | 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.
Objaśnienie: Funkcje SUMA.JEŻELI obliczają przepływ netto każdego węzła. W przypadku węzła S funkcja SUMA.JEŻELI sumuje wartości w kolumnie Idź z literą „S” w kolumnie Od. W rezultacie tylko komórka F4, F5 lub F6 może mieć wartość 1 (jeden łuk wychodzący). W przypadku węzła T funkcja SUMA.JEŻELI sumuje wartości w kolumnie Przejdź z literą „T” w kolumnie Do. W rezultacie tylko komórka F15, F18 lub F21 może mieć wartość 1 (jeden łuk wejściowy). W przypadku wszystkich pozostałych węzłów program Excel szuka w kolumnie Od i Do. Całkowita odległość równa się iloczynowi sumy odległości i drogi.
Próby i błędy
Dzięki tej formule analiza dowolnego rozwiązania próbnego staje się łatwa.
1. Na przykład ścieżka SBET ma całkowitą odległość 16.
Nie jest konieczne stosowanie prób i błędów. Opiszemy dalej, w jaki sposób Solver Excel można wykorzystać 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 Solver.
Uwaga: nie możesz znaleźć przycisku Solver? Kliknij tutaj, aby załadować dodatek Solver.
Wprowadź parametry solvera (czytaj dalej). Wynik powinien być zgodny z poniższym obrazkiem.
Możesz wpisać nazwy zakresów lub kliknąć komórki w arkuszu kalkulacyjnym.
2. Wprowadź TotalDistance dla celu.
3. Kliknij Min.
4. Wpisz Go, aby zmienić komórki zmiennych.
5. Kliknij Dodaj, aby wprowadzić następujące ograniczenie.
6. Zaznacz 'Make Unconstrained Variables jako nieujemne' i wybierz 'Simpleks LP'.
7. Na koniec kliknij Rozwiąż.
Wynik:
Optymalne rozwiązanie:
Wniosek: SADCT to najkrótsza ścieżka o łącznej odległości 11.
