Sformułuj model | Próba i błąd | Rozwiąż model
Użyj solvera w Przewyższać znaleźć maksymalny przepływ od węzła S do węzła T w sieci skierowanej. 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 maksymalnym przepływem, odpowiedz na trzy poniższe pytania.
a. Jakie decyzje należy podjąć? Aby rozwiązać ten problem, potrzebujemy programu Excel, aby znaleźć przepływ na każdym łuku. Na przykład, jeśli przepływ na SB wynosi 2, komórka D5 jest równa 2.
b. Jakie są ograniczenia tych decyzji? Przepływ netto (wypływ - napływ) węzła A, B, C, D i E powinien być równy 0. Innymi słowy, wypływ = napływ. Ponadto każdy łuk ma stałą pojemność. Przepływ na każdym łuku powinien być mniejszy niż ta pojemność.
C. Jaka jest ogólna miara skuteczności tych decyzji? Ogólną miarą wydajności jest maksymalny przepływ, więc celem jest maksymalizacja tej ilości. Maksymalny przepływ jest równy przepływowi z węzła S.
2. Aby model był łatwiejszy do zrozumienia, utwórz następujące nazwane zakresy.
| Nazwa zakresu | Komórki |
|---|---|
| Z | B4:B15 |
| W celu | C4:C15 |
| Pływ | D4:D15 |
| Pojemność | F4:F15 |
| Prośba o zaopatrzenie | K5:K9 |
| Maksymalny przepływ | D17 |
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 A pierwsza funkcja SUMA.JEŻELI sumuje wartości w kolumnie Przepływ z literą „A” w kolumnie Od (Wypływ). Druga funkcja SUMA.JEŻELI sumuje wartości w kolumnie Przepływ z literą „A” w kolumnie Do (Przepływ). Maksymalny przepływ jest równy wartości w komórce I4, która jest wypływem z węzła S. Ponieważ węzły A, B, C, D i E mają przepływ netto równy 0, wypływ z węzła S będzie równy przepływowi w węźle T.
Próby i błędy
Dzięki tej formule analiza dowolnego rozwiązania próbnego staje się łatwa.
1. Na przykład ścieżka SADT z przepływem 2. Ścieżka SCT z przepływem 4. Ścieżka SBET z przepływem 2. Te ścieżki dają całkowity przepływ 8.
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ź MaximumFlow dla celu.
3. Kliknij Maks.
4. Wprowadź Flow dla zmieniających się komórek zmiennych.
5. Kliknij Dodaj, aby wprowadzić następujące ograniczenie.
6. Kliknij Dodaj, aby wprowadzić następujące ograniczenie.
7. Zaznacz 'Make Unconstrained Variables jako nieujemne' i wybierz 'Simpleks LP'.
8. Na koniec kliknij Rozwiąż.
Wynik:
Optymalne rozwiązanie:
Wniosek: ścieżka SADT z przepływem 2. Ścieżka SCT z przepływem 4. Ścieżka SBET z przepływem 2. Ścieżka SCET z przepływem 2. Ścieżka SACET z przepływem 1. Ścieżka SACDT z przepływem 1. Te ścieżki dają maksymalny przepływ 12.
