OIG KE2: Transporttableau: Schleife und Kontenpotentiale

View all featured content
U

UBIT

Dr Franke Ghostwriter
Optimierung in Graphen KE2, Seite 55-58

Im Prinzip verstehe ich den Alogrithmus, habe jedoch Probleme in zwei Punkten:

UMVERTEILUNGSSCHLEIFE
Wie ist die Markierung der Felder der Umverteilungsschleife rein aus dem Tableau ersichtlich?
- Ausgangspunkt ist ja (h,k)
- von dort bewegt man sich dann entweder waagrecht oder senkrecht bis zum nächsten Basisfeld; von diesem geht es dann wieder waagrecht (wenn man durch eine senkrechte Bewegung auf das Feld gekommen ist) bzw. senkrecht (wenn man durch eine waagrechte Bewegung auf das Feld gekommen ist) zum nächsten Basisfeld. Dies erfolgt solange bis sich ein Kreis schließt.
- Allerdings habe ich nicht ganz verstanden, nach welcher Systematik genau diese Bewegung erfolgt: Ist es einfach so, dass wenn man in Tab. 7.9. von (2|1) ausgehend senkrecht nach unten fahren würde in (3|1) auf kein Basisfeld stoßen würde und deswegen nur quasi nur der Weg nach oben zu (1|1) bleibt usw.?
- In Tab. 10 könnte man sich ja nun von (1|2) auch waagrecht nach links auf das Basisfeld (1|3) bewegen, allerdings würde man danach in der senkrechten Bewegung nach unten auf kein Basisfeld mehr treffen, weswegen dies dann nicht der richtige Weg sein kann?

KNOTENPOTENTIALE
Wie sind die Teilbäume aus dem Tableau ersichtlich?
- Laut Algorithmus hätte ich in Tab. 7.9 lediglich uk = uk - chk vorgenommen, also u1' = u1' - c21 = -10 + 8 = - 2; warum wird auch noch von u3' und u1 -8 substrahiert?
In Tab. 7.10. das gleiche Spiel: Laut Algorithmus hätte ich uh = uh + chk vorgenommen, also u1 = u1 - 4 = 2 - 4 = -2. Warum zusätzlich noch die Addition von -4 zu u3'?

Schon einmal Danke im Voraus für Eure Hilfe.
 
Nach Datum sortieren Nach Stimmen sortieren
UBIT schrieb:
Optimierung in Graphen KE2, Seite 55-58

Im Prinzip verstehe ich den Alogrithmus, habe jedoch Probleme in zwei Punkten:

UMVERTEILUNGSSCHLEIFE
Wie ist die Markierung der Felder der Umverteilungsschleife rein aus dem Tableau ersichtlich?
- Ausgangspunkt ist ja (h,k)
- von dort bewegt man sich dann entweder waagrecht oder senkrecht bis zum nächsten Basisfeld; von diesem geht es dann wieder waagrecht (wenn man durch eine senkrechte Bewegung auf das Feld gekommen ist) bzw. senkrecht (wenn man durch eine waagrechte Bewegung auf das Feld gekommen ist) zum nächsten Basisfeld. Dies erfolgt solange bis sich ein Kreis schließt.
- Allerdings habe ich nicht ganz verstanden, nach welcher Systematik genau diese Bewegung erfolgt: Ist es einfach so, dass wenn man in Tab. 7.9. von (2|1) ausgehend senkrecht nach unten fahren würde in (3|1) auf kein Basisfeld stoßen würde und deswegen nur quasi nur der Weg nach oben zu (1|1) bleibt usw.?
- In Tab. 10 könnte man sich ja nun von (1|2) auch waagrecht nach links auf das Basisfeld (1|3) bewegen, allerdings würde man danach in der senkrechten Bewegung nach unten auf kein Basisfeld mehr treffen, weswegen dies dann nicht der richtige Weg sein kann?

KNOTENPOTENTIALE
Wie sind die Teilbäume aus dem Tableau ersichtlich?
- Laut Algorithmus hätte ich in Tab. 7.9 lediglich uk = uk - chk vorgenommen, also u1' = u1' - c21 = -10 + 8 = - 2; warum wird auch noch von u3' und u1 -8 substrahiert?
In Tab. 7.10. das gleiche Spiel: Laut Algorithmus hätte ich uh = uh + chk vorgenommen, also u1 = u1 - 4 = 2 - 4 = -2. Warum zusätzlich noch die Addition von -4 zu u3'?

Schon einmal Danke im Voraus für Eure Hilfe.
Zum Vergrößern anklicken....

Zur Umverteilungsschleife kann ich dir helfen. Bei den Potentialänderungen nicht so richtig. Habe noch kein Schema gefunden, womit Änderungen der ui, uj und c_quer einfach zu absolvieren gehen. Ich "behelfe" mich damit, indem ich die ui, uj und c_quer einfach neu berechne wie im Schritt 2 des Algorithmus. Man kann mit u1'=0 oder mit dem Wert der Pot.änd. beginnen. Letztlich sind die c_quer die entscheidenden Werte.
Es geht allerdings auch gem. Abschn. 7.1.6 mit der Zeichung eines Basisbaumes. Aber hier habe ich den Mut zur Lücke.

Zur Umverteilungsschleife:
Man braucht eine ungerade Anzahl Baisfelder >=3 und natürlich das Feld h,k mit negat. c_quer_hk (insg. also mind. 4 Felder). Von diesem mit Plus gekennzeichneten Feld sucht man sich Basisfelder, die in hor. oder vert. Richtung immer direkt erreichbar sind. Dabei gibt es m.E. keine Systematik, man muss nur eine "Rundreise" über die Basisfelder finden. Findet man keine Rundreise über 3 Basisfelder, muss man es mit 5 oder mehr Feldern probieren.

Hat man bei der heuristischen Eröffnung des Transportplans (Ausgangslösung) auf die Anzahl der Basisfelder geachtet (m+n-1), dann klappt das auch.
 
Positive Stimme 0 Negative Stimme
Danke. - Habe heute noch einmal ein, zwei Beispiele durchgerechnet und denke, dass es so ist, wie von Dir beschrieben und es beim Fluss keine weiteren Kniffe mehr gibt. Also einfach probieren.

Bei den Potentialen verstehe ich das jetzt so, dass man zunächst entweder ui oder uj so anpasst, dass cij_quer im neuen Basisfeld null wird. Anschließend schaut man, ob noch andere ui/uj angepasst werden müssen, damit auch dort die cij_quer null bleiben (Das ist dann der Fall wenn in i bzw. j neben dem neuen auch noch alte Basisfelder sind).

Zum Beispiel in Tab. 7.9.:
- 21' ist neues Basisfeld.
==> Erhöhung von u1', damit c21'_quer null wird (3-1-10 = -8 +8 = 0)
==> c11'_quer wäre jetzt ungleich null
==> zum Ausgleich muss daher u1 auch um 8 erhöht werden
==> c11'_quer bleibt nun gleich 0
==> c13'_quer wäre durch die Erhöhung von u1 nun nicht mehr gleich null
==> zum Ausgleich muss also auch u3' um 8 erhöht werden
==> c13'_quer bliebt nun ebenfalls gleich null

Da in Spalte u3' keine weiteren Basisfelder mehr liegen, müssen keine weiteren Potentiale ausgeglichen werden.

Allerdings müssen noch die cij_quer der Nichtbasisfelder in den Zeilen/Spalten neu berechnet werden, in denen eine Potentialänderung stattgefunden hat.
==> in Zeile 1 sinken die cij_quers in allen Nichtbasisfeldern um acht.
==> in den Spalten 1' und 3' steigen die cij_quers aller Nichtbasisfelder um acht.

Hoffe, dass ist a) verständlich und b) richtig.
 
Positive Stimme 0 Negative Stimme
Das ist meiner Meinung nach frei wählbar, man muss sich nur für eines von beiden entscheiden:

Im Algorithmus steht ja
v) Ändere die Knotenpotentiale
Berechne ENTWEDER
uh = uh + chk
ODER
uk = uk - chk
Zum Vergrößern anklicken....

Es müsste also genauso möglich sein, u2 um 8 zu senken
==> c21_quer = 3-(1-8)-10 = 3 + 7 - 10 = 0
==> c24'_quer nicht mehr gleich null
==> Senkung von u4' um 8 auf -13
==> c24'_quer wieder gleich null (6 + 7 - 13 = 0)
==> c34'_quer nicht mehr gleich null
==> Senkung von u3 auf um 8 auf -11
==> c34'_quer wieder gleich null (2 + 11- 13 = 0)
==> c32'_quer nicht mehr gleich null
==> Senkung von u2' um 8 auf -19
==> c32'_quer wieder gleich null (8 + 11 - 19 = 0)

Anpassen aller cij_quer in den Nichtbasisfeldern in den Zeilen/Spalten mit geändertem Potential muss zum gleichen Ergebnis wie in Tab. 7.10 führen.
Die Potentiale an sich haben ja keinen festen Wert, es ist nur wichtig, dass ihre Differenz zueinander immer die gleiche bleibt.

Hoffe, das hilft.
 
Positive Stimme 0 Negative Stimme
UBIT schrieb:
Das ist meiner Meinung nach frei wählbar, man muss sich nur für eines von beiden entscheiden:

Im Algorithmus steht ja


Es müsste also genauso möglich sein, u2 um 8 zu senken
==> c21_quer = 3-(1-8)-10 = 3 + 7 - 10 = 0
==> c24'_quer nicht mehr gleich null
==> Senkung von u4' um 8 auf -13
==> c24'_quer wieder gleich null (6 + 7 - 13 = 0)
==> c34'_quer nicht mehr gleich null
==> Senkung von u3 auf um 8 auf -11
==> c34'_quer wieder gleich null (2 + 11- 13 = 0)
==> c32'_quer nicht mehr gleich null
==> Senkung von u2' um 8 auf -19
==> c32'_quer wieder gleich null (8 + 11 - 19 = 0)

Anpassen aller cij_quer in den Nichtbasisfeldern in den Zeilen/Spalten mit geändertem Potential muss zum gleichen Ergebnis wie in Tab. 7.10 führen.
Die Potentiale an sich haben ja keinen festen Wert, es ist nur wichtig, dass ihre Differenz zueinander immer die gleiche bleibt.

Hoffe, das hilft.
Zum Vergrößern anklicken....

Danke, das hilft mir sehr weiter. Mit diesem Problem habe ich mich schon länger herum geschlagen.
 
Positive Stimme 0 Negative Stimme
Antworten
Oben