Kürzeste-Weg-Problem

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 Knoten genannt (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.

Wie finden Sie die Standardabweichung in Excel?

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 sich ein Bogen auf dem kürzesten Weg befindet 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 und einen eingehenden Bogen haben, wenn sich der Knoten auf dem kürzesten Weg (Net Flow = 0) oder keinem Flow (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 Folgendes: benannte Bereiche .

3. Fügen Sie die folgenden Funktionen ein.

Erklärung: 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. Gesamtdistanz gleich der Summenprodukt von Distance and 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 die zu laden Solver-Add-In .

Geben Sie die Solver-Parameter ein (lesen Sie weiter). Das Ergebnis sollte mit dem Bild unten übereinstimmen.

Wie gehe ich zur nächsten Zeile in Excel in der gleichen Zelle Mac

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.

wie man ein Histogramm in Excel macht

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.