Network Flow Verfahren |
| 25.11.2019, 09:06 | Florian1994 | Auf diesen Beitrag antworten » |
| Network Flow Verfahren wir haben gerade das Network Flow Problem in der Optimierungsvorlesung definiert und anschließend ein Beispiel mit Hilfe des einfachen Simplex-Algorithmus gelöst. Die Vorgehenweise ist mir soweit klar, ich habe allerdings ein paar Fragen dazu. Das Problem wurde bei uns folgendermaßen aufgestellt: Dabei beschreibt K die Menge der Knoten und ij beschreibt die gerichtete Kante. Jede Kante besitzt eine maximale Kapazität und ein Kantengewicht c_ij. Jetzt streicht man eine Knotenbilanz, indem man die Bilanz eines Knoten nach einer Kante auflöst und erhält ein Problem, welches um eine Dimension erniedrigt wurde. Im Vorlesungsbeispiel haben wir jetzt bei einem Problem mit einem Angebotsknoten, einem Bedarfsknoten und zwei Umladeknoten und insgesamt fünf Kanten schließlich zwei Kanten als Nichtbasisvariablen gewählt und drei Kanten als Basisvariablen. Man kann dann relativ einfach eine gültige Lösung berechnen und dann fortfahren... Frage: Wovon hängt die Anzahl der Nichtbasisvariablen bei Network Flow Problem ab? Habe ich immer nur zwei Nichtbasisvariablen oder kann ich das anhand des Graphen erkennen? Kann es sein, dass es mit der Anzahl der Freiheitsgrade zusammenhängt. Angenommen wir haben ein Netzwerk mit 5 Knoten (ein Angebotsknoten, ein Bedarfsknoten und drei Umladeknoten) und insgesamt 7 Kanten. Nach Streichung einer Knotenbilanz reduziert sich das Problem auf vier Knotenbilanzen mit sechs Variablen. Ich habe nun zwei Freiheitsgrade, diese Variablen bilden meine Nichtbasisvariablen und können laut Definition auf ihren minimalen oder maximalen Wert festgelegt werden. Damit müssten doch die verbleibenden vier Variablen bestimmbar sein oder? Kann man dies verallgemeinern? Also sagen wir bei einem Problem mit n Knoten und m Kanten. Nach Streichung einer Knotenbilanz habe ich noch n-1 Nebenbedingungen und m-1 Kanten bzw. Unbekannte. Meine Freiheitsgrade hängen nun von n und m ab, z.B. bei n = 8 und m = 12 würde gelten: 4 Nichtbasisvariablen?! Leider sehe ich noch das Problem mit den Kapazitätsbeschränkungen auf den Kanten, da komme ich in der Praxis häufig noch nicht zu einer Lösung. Manchmal muss ich mehr Variablen festlegen als nur die Freihitsgrade - kann das sein oder stelle ich mich einfach doof an? Danke Zwei Beiträge zusammengefasst. Steffen |
||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
