Formulieren Sie das Modell | Versuch und Irrtum | Lösen Sie das Modell
Verwenden Sie den Solver in Excel um die zu finden kürzester Weg von Knoten S zu Knoten T in einem ungerichteten 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 Kürzeste-Weg-Problem, beantworten Sie die folgenden drei Fragen.
A. Welche Entscheidungen sind zu treffen? Für dieses Problem benötigen wir Excel, um herauszufinden, ob ein Bogen auf dem kürzesten Weg liegt oder nicht (Ja = 1, Nein = 0). Wenn SB beispielsweise Teil des kürzesten Pfads ist, ist Zelle F5 gleich 1. Wenn nicht, ist Zelle F5 gleich 0.
B. Welche Einschränkungen gibt es bei diesen Entscheidungen? Der Nettofluss (Flow Out – Flow In) jedes Knotens sollte gleich Angebot/Nachfrage sein. Knoten S sollte nur einen ausgehenden Bogen haben (Net Flow = 1). Knoten T sollte nur einen eingehenden Bogen haben (Net Flow = -1). Alle anderen Knoten sollten einen ausgehenden Bogen und einen eingehenden Bogen haben, wenn sich der Knoten auf dem kürzesten Weg (Net Flow = 0) oder keinem Fluss (Net Flow = 0) befindet.
C. Was ist das Gesamtleistungsmaß für diese Entscheidungen? Das Gesamtmaß der Leistung ist die Gesamtstrecke des kürzesten Wegs, daher besteht das Ziel darin, diese Größe zu minimieren.
2. Um das Modell leichter verständlich zu machen, erstellen Sie die folgenden benannten Bereiche.
| Bereichsname | Zellen |
|---|---|
| Aus | B4: B21 |
| Zu | C4: C21 |
| Distanz | D4: D21 |
| gehen | F4:F21 |
| NetFlow | I4:I10 |
| AngebotNachfrage | K4:K10 |
| Gesamtstrecke | F23 |
3. Fügen Sie die folgenden Funktionen ein.
Erläuterung: Die SUMIF-Funktionen berechnen den Nettofluss jedes Knotens. Für Knoten S summiert die SUMIF-Funktion die Werte in der Spalte Go mit einem "S" in der Spalte From. Daher kann nur die Zelle F4, F5 oder F6 1 sein (ein ausgehender Bogen). Für Knoten T summiert die SUMIF-Funktion die Werte in der Go-Spalte mit einem "T" in der To-Spalte. Als Ergebnis kann nur die Zelle F15, F18 oder F21 1 sein (ein eingehender Bogen). Bei allen anderen Knoten sucht Excel in den Spalten Von und Bis. Die Gesamtdistanz entspricht dem Summenprodukt von Distanz und Go.
Versuch und Irrtum
Mit dieser Formulierung wird es einfach, jede Versuchslösung zu analysieren.
1. Zum Beispiel hat der Pfad SBET eine Gesamtdistanz von 16.
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 TotalDistance für das Ziel ein.
3. Klicken Sie auf Min.
4. Geben Sie Go für die sich ändernden Variablenzellen ein.
5. Klicken Sie auf Hinzufügen, um die folgende Einschränkung einzugeben.
6. Aktivieren Sie „Make Unconstrained Variables Non-Negative“ und wählen Sie „Simplex LP“.
7. Klicken Sie abschließend auf Lösen.
Ergebnis:
Die optimale Lösung:
Fazit: SADCT ist mit einer Gesamtstrecke von 11 der kürzeste Weg.
