Sonstige Aufgaben Überdeckungsproblem KE 853, Beispiel 5.4

Ein fröhliches "Moin!" in die Runde,
da ich bei einigen Aufgaben doch etwas unsicher bin, möchte ich meine Überlegungen hier niederschreiben und zur Diskussion stellen, denn die formale Schreibweise der Regeln kann ich noch nicht in konkrete Schritte "übersetzen".
Seite 80, KE 853, Beispiel 5.4:
a) Erste Reduktion aufgrund Regel 2 leuchtet mir ein (dies ist wohl auch die einfachste aller Regeln ;) ).
b) Zweite Reduktion nach Regel 3: gestrichen werden sollen Zeile i=2 und i= 10. Aber weshalb?
b1) Zeile 10 und Zeile 8 sind identisch. Nachvollziehbar, dass die sich überdecken. Aber weshalb streiche ich nun ausgerechnet Zeile 10 und nicht Zeile 8? Wie lege ich also konkret i* fest?
b2) Wenn Zeile 4 erfüllt ist, muss auch Zeile 2 erfüllt sein, dann bliebe in Zeile 2 nur noch eine eins übrig, deshalb Zeile 2 streichen.
c) Dritte Reduktion: Aufgrund 4Ü wird Spalte 5 gestrichen. Nun könnte man doch aber auch Spalte 2 streichen, schließlich hat Spalte 2 auch nur eine eins. Ich habe mir das nun so zusammengereimt, dass die Spalte mit dem größeren C-Wert gestrichen wird: In Spalte 5 c= 8, in Spalte 2 c=3)
d) vierte Reduktion ist wieder Regel 2
e) letzte Reduktion, hier greift nun wieder 4Ü, und (wenn ich das eben richtig verstanden habe, wird die Spalte mit dem höheren c-Wert gestrichen, eben Spalte 2) Allerdings ist die Beschriftung dieser Reduktion vertauscht, cj und ij müssten genau anders dort stehen.

Wie habt ihr diese Regeln "für normalsterbliche-übersetzt"? Das Anwenden ist ja halb so wild, wenn man mal verstanden hätte, was die genau besagen sollen... bin für Hilfe deshalb sehr dankbar!

Gruß

C.

Crix schrieb:

b1) Zeile 10 und Zeile 8 sind identisch. Nachvollziehbar, dass die sich überdecken. Aber weshalb streiche ich nun ausgerechnet Zeile 10 und nicht Zeile 8? Wie lege ich also konkret i* fest?

Zum Vergrößern anklicken....

Ich habe in solchen Fällen für mich beschlossen, dass ich i mit der kleineren Zahl belegt habe also i*. Welche der beiden Bedingungen übrig bleibt, ist vermutlich egal.

Crix schrieb:

b2) Wenn Zeile 4 erfüllt ist, muss auch Zeile 2 erfüllt sein, dann bliebe in Zeile 2 nur noch eine eins übrig, deshalb Zeile 2 streichen.

Zum Vergrößern anklicken....

Bei mir ist i*=2 und i=4 oder i=6. Das geht mit beiden. Wenn a_4k = 1, dann ist auch a_2k = 1 (gilt für k=2 und k=3). Wenn a_6k = 1, dann ist auch a_2k = 1 (gilt für k=3 und k=4). Es wird dann immer die komplette Zeile i* gestrichen. Bei i=4 ist a_44 = 0 und damit findet die Regel 3 keine Anwendung, denn die Voraussetzung a_44=1 ist nicht erfüllt.

Crix schrieb:

c) Dritte Reduktion: Aufgrund 4Ü wird Spalte 5 gestrichen. Nun könnte man doch aber auch Spalte 2 streichen, schließlich hat Spalte 2 auch nur eine eins. Ich habe mir das nun so zusammengereimt, dass die Spalte mit dem größeren C-Wert gestrichen wird: In Spalte 5 c= 8, in Spalte 2 c=3)

Zum Vergrößern anklicken....

Für Anwendung der Regel 4Ü müssen die Spalten der a-Elemente, sowie der entsprechenden Kosten verglichen werden. Wenn k=2, dann ist der erste Teil der Regel nur für j=5 erfüllt, denn nur dann ist a_5 >= a_2. Bei Anwendung des zweiten Teils kommen dann die Kosten ins Spiel und da ist der zweite Teil der Regel nicht mehr erfüllt, da c_5 nicht <=c_2 ist. Es ist ja eine Minimierungsaufgabe und daher müssen Elemente mit hohen Kosten gestrichen werden.
Es kann sein, dass für die Anwendung der Regel mehr als eine Spalte auf der "Summenseite" herangezogen werden müssen.

Crix schrieb:

e) letzte Reduktion, hier greift nun wieder 4Ü, und (wenn ich das eben richtig verstanden habe, wird die Spalte mit dem höheren c-Wert gestrichen, eben Spalte 2) Allerdings ist die Beschriftung dieser Reduktion vertauscht, cj und ij müssten genau anders dort stehen.

Zum Vergrößern anklicken....

Ja, das sehe ich auch so.