Formulieren Sie das Modell | Versuch und Irrtum | Lösen Sie das Modell
Verwenden Sie den Solver in Excel um die zu finden maximaler Durchfluss von Knoten S zu Knoten T in einem gerichteten Netzwerk. Punkte in einem Netzwerk werden als Knoten bezeichnet (S, A, B, C, D, E und T). Linien in einem Netzwerk werden als Bögen bezeichnet (SA, SB, SC, AC usw.).
Formulieren Sie das Modell
Das zu lösende Modell sieht in Excel wie folgt aus.
1. Um dies zu formulieren Problem mit maximalem Durchfluss, beantworten Sie die folgenden drei Fragen.
A. Welche Entscheidungen sind zu treffen? Für dieses Problem benötigen wir Excel, um den Fluss auf jedem Bogen zu finden. Wenn beispielsweise der Fluss auf SB 2 ist, ist Zelle D5 gleich 2.
B. Welche Einschränkungen gibt es bei diesen Entscheidungen? Der Nettofluss (Flow Out – Flow In) der Knoten A, B, C, D und E sollte gleich 0 sein. Mit anderen Worten, Flow Out = Flow In. Außerdem hat jeder Lichtbogen eine feste Kapazität. Der Durchfluss bei jedem Bogen sollte kleiner als diese Kapazität sein.
C. Was ist das Gesamtleistungsmaß für diese Entscheidungen? Das Gesamtmaß der Leistung ist der maximale Durchfluss, daher besteht das Ziel darin, diese Menge zu maximieren. Der maximale Fluss entspricht dem Fluss aus Knoten S.
2. Um das Modell leichter verständlich zu machen, erstellen Sie die folgenden benannten Bereiche.
| Bereichsname | Zellen |
|---|---|
| Aus | B4: B15 |
| Zu | C4: C15 |
| Fluss | D4: D15 |
| Kapazität | F4:F15 |
| AngebotNachfrage | K5: K9 |
| Maximaler Durchfluss | D17 |
3. Fügen Sie die folgenden Funktionen ein.
Erläuterung: Die SUMIF-Funktionen berechnen den Nettofluss jedes Knotens. Für Knoten A summiert die erste SUMIF-Funktion die Werte in der Spalte Flow mit einem "A" in der Spalte Von (Flow Out). Die zweite SUMIF-Funktion summiert die Werte in der Spalte Flow mit einem "A" in der Spalte To (Flow In). Der maximale Fluss entspricht dem Wert in Zelle I4, dem Fluss aus Knoten S. Da Knoten A, B, C, D und E einen Nettofluss von 0 haben, entspricht Fluss aus Knoten S dem Fluss aus Knoten T.
Versuch und Irrtum
Mit dieser Formulierung wird es einfach, jede Versuchslösung zu analysieren.
1. Zum Beispiel der Pfad SADT mit einem Fluss von 2. Der Pfad SCT mit einem Fluss von 4. Der Pfad SBET mit einem Fluss von 2. Diese Pfade ergeben einen Gesamtfluss von 8.
Es ist nicht notwendig, Versuch und Irrtum zu verwenden. Wir werden als nächstes beschreiben, wie die Excel-Löser verwendet werden, um schnell die optimale Lösung zu finden.
Lösen Sie das Modell
Um die optimale Lösung zu finden, führen Sie die folgenden Schritte aus.
1. Klicken Sie auf der Registerkarte Daten in der Gruppe Analysieren auf Solver.
Hinweis: Sie können die Solver-Schaltfläche nicht finden? Klicken Sie hier, um das Solver-Add-In zu laden.
Geben Sie die Solver-Parameter ein (lesen Sie weiter). Das Ergebnis sollte mit dem Bild unten übereinstimmen.
Sie haben die Wahl, die Bereichsnamen einzugeben oder auf die Zellen in der Tabelle zu klicken.
2. Geben Sie MaximumFlow für das Ziel ein.
3. Klicken Sie auf Max.
4. Geben Sie den Fluss für die sich ändernden Variablenzellen ein.
5. Klicken Sie auf Hinzufügen, um die folgende Einschränkung einzugeben.
6. Klicken Sie auf Hinzufügen, um die folgende Einschränkung einzugeben.
7. Aktivieren Sie „Make Unconstrained Variables Non-Negative“ und wählen Sie „Simplex LP“.
8. Klicken Sie abschließend auf Lösen.
Ergebnis:
Die optimale Lösung:
Fazit: der Pfad SADT mit einem Fluss von 2. Der Pfad SCT mit einem Fluss von 4. Der Pfad SBET mit einem Fluss von 2. Der Pfad SCET mit einem Fluss von 2. Der Pfad SACET mit einem Fluss von 1. Der Pfad SACDT mit einem Fluss von 1. Diese Pfade ergeben einen maximalen Fluss von 12.
