KE 853, Kap. 5, ÜA 5.1

dummerweise hänge ich genau an dieser Stelle, die Du oben beschrieben hast. Nur sehe ich meinen Fehler nicht. Da Du den Knoten ja offensichtlich gesprengt hast wäre es super, wenn Du mir kurz auf die Sprünge helfen könntest. Vielen Dank dafür!

Wie schnell man doch Gelerntes wieder verdrängt ... 😉
Ich hoffe, ich bekomme das noch richtig auf die Reihe. Also, das Partitionsproblem hat keine zulässige Lösung, da Pj geschnitten Pk keine leere Menge ergibt. Nur als Überdeckungsproblem ist die Lösung zulässig. x5 mit c= 7 hatten wir uns oben schon gemerkt; und bei der verbleibenden Matrix nimmst Du jetzt lediglich die x, die zu geringstmöglichen Kosten überdecken; in diesem Fall x1 und x4. Ergibt: 7 + 3 + 3 = 13
VG, ratte98

ich habe da mal eine Frage zur Anwendung von Ü3. (Ich saß auch etwas länger an der Aufgabe). Da Ratte immer Zeilen streicht, wenn eine Zeile eine "dominante Zeile" zu einer anderen ist, würde mich interessieren, ob der Schirtt Ü3 immer die Dominanz voraussetzt, also für i* kein Nullelement existiert, das nicht ebenfalls in i vorhanden ist?

Richtig. Oder wie es im Buch steht: wenn aik=1 dann muss ai*k =1 sein, damit i* gestrichen werden kann. Heißt ai*k kann und darf mehr 1en enthalten als aik.

@addup: So wie ich das sehe, muss für jede "1" in Zeile i auch eine "1" in Zeile i* stehen. Wenn in Zeile i eine "0" steht und in Zeile i* an der entsprechenden Stelle eine "1", kann man das ignorieren. i* muss gestrichen werden.

@Ratte98: So wirklich hilft mir das nicht weiter. Denn im letzten Tableau, das Du oben beschrieben hast, dominieren P1 und P4 ja nicht über P8. Wie kommst Du an diesem Punkt weiter?

Ratte98 schrieb:

Wie schnell man doch Gelerntes wieder verdrängt ... 😉
Ich hoffe, ich bekomme das noch richtig auf die Reihe. Also, das Partitionsproblem hat keine zulässige Lösung, da Pj geschnitten Pk keine leere Menge ergibt. Nur als Überdeckungsproblem ist die Lösung zulässig. x5 mit c= 7 hatten wir uns oben schon gemerkt; und bei der verbleibenden Matrix nimmst Du jetzt lediglich die x, die zu geringstmöglichen Kosten überdecken; in diesem Fall x1 und x4. Ergibt: 7 + 3 + 3 = 13
VG, ratte98

Zum Vergrößern anklicken....

Lassen sich diese denn nicht auch durch Anwendung der Regeln bestimmen?
Ich würde bei dem oben angegebenen Tableu erst einmal Schritt 4 anwenden und Spalte 8 streichen. Dann bleibt:
x_1 x_4
0 1
1 1
1 0

Hier wende ich Ü2 für Zeile 1 an. Also Streichen Spalte 4 und setze x_4=1. Desweiteren Streichen von Zeile 1 und 2. Dem nächsten Tableu wird die Zielfkt. aufgesetzt. Also:
x_1
3=c_1
1
Hier lese ich nun x_1=1 ab.

Ah, danke für eure schnelle Hilfe. Ich habe mich öfters mit Ü3 verzettelt, da ich einfach eine Zeile gesucht habe die in der gleichen Spalte ebenfalls eine 1 hat und dann einfach eine der beiden gestrichen. Aber nun weiß ich ja worauf es ankommt.

Ich hätte jetzt gerne noch weiterdiskutiert, muss jetzt aber leider außer Haus.

Wie gesagt Partition setzt voraus, dass die Lösung (bildlich gesprochen) in jeder Zeile nur ein 1-er Element haben darf. Überdeckung hingegen muss in jeder Zeile mindestens ein 1er-Element haben. Bei der Lösung zum Überdeckungsproblem können zum Schluß x1 und x4, x1 und x8 oder x1 und x8 die restlichen Zeilen überdecken. Hier entscheiden die Kosten; dabei deckt die Kombination x1 und x4 die restlichen Zeilen am günstigen ab.

Damit kann die Kombination aus x1 und x4 (beide mit c=3) also x8 überdecken (mit c=9). Bislang dachte ich, dass immer nur eine Spalte eine andere überdecken kann, sofern sich in ihr mind. die gleichen Argumente ("1") in den identischen Zeilen befinden, die Kosten aber geringer sind. Dass auch eine Kombination von zwei oder mehr Spalten eine weitere Spalte überdecken kann, war mir nicht klar. Wenn das so ist, dann ist die Lösung natürlich offensichtlich. Vielen Dank dafür!

also x1 und x4 überdecken mit ihren 1en am günstigen die noch nicht belegten Zeilen...
Das Tableau oben ist bereits das Endtableau. Da greift m.W. auch keine der Reduktionsregeln mehr ... Insofern würde ich Deine Aussage so nicht (ganz) unterschreiben wollen 🙂 Aber - wie gesagt - ich stehe auch nicht mehr ganz im Thema. Mir fällt nur gerade das Beispiel unten ein, wo Deine Aussage nicht ganz passen würde, aber die Kosten von x1+x2 verglichen mit x3+x4 letztendlich über die Lösung entscheiden.
VG,

Beispiel:
x1 x2 x3 x4
1 0 1 0
0 1 0 1
0 1 1 0
1 0 0 1

Ok, damit habe ich die Lösung verstanden. Danke nochmal.

alter ist der Stoff crazy 😀 ...muss wohl noch etwas dran knobbeln

Ratte98 schrieb:

...
3.) Spalte 2 (wegen Spalte 8), 3 und 6 (wegen Spalte 9),
...

Zum Vergrößern anklicken....

Warum streichst du denn als dritten Schritt jetzt Spalten? Und dann die 2 im Vergleich zur 8? Steh grad glaub ich voll aufm Schlauch...

Stell' Dir vor, es werden Mitarbeiter für eine Projekt gesucht. Für das Projekt kommt nur eine gewisse Anzahl an Mitarbeiter in Betracht (Spalten; hier 9). Für die erfolgreiche Bearbeitung des Projektes müssen die Mitarbeiter bestimmte Fähigkeiten mitbringen (Zeilen). Das Tableau gibt nun an, welcher MA (Spalte) über welche dieser Fähigkeiten verfügt (Zeile). 1 = MA hat die Fähigkeit, 0 = MA hat sie nicht.
C gibt an, was der MA kostet.
Grundsätzlich muß das Projektteam aber zum Schluß über alle erforderlichen Fähigkeiten verfügen.
Partitionsprobelm heißt nun: eine Fähigkeit darf im ganzen Projektteam nur einmal vorkommen;
Überdeckungsproblem heißt die Fähigkeit darf ruhig mehrmals vorhanden sein.

So, jetzt geht es los:
Wenn eine Zeile nur Nullen hat, dann besitzt keiner der vorhandenen MA die Fähigkeit, die zur Bearbeitung des Projektes erforderlich ist. (Regel 1). Es gibt dann keine LÖsung.

Wenn in einer Zeile nur eine 1 vorkommt, so muß dieser MA genommen werden, weil kein anderer über diese Fähigkeit verfügt. --> Zeile streichen. Spalte streichen und Mitarbeiter notieren. Sofern dieser Mitarbeiter über noch weitere Fähigkeiten verfügt (sprich: weitere 1en in der Spalte stehen hat), sind diese Zeilen ebenfalls zu streichen, da diese Fähigkeiten ja auch von ihm bedient werden können. (Regel 2). Im Partitionsfall sind zudem alle diejenigen Mitarbeiter zu streichen, die auch eine dieser Fähigkeiten besitzt, weil die Fähigkeit im Projektteam nur einmal vorkommen darf (Regel 2P).

Regel 3 gibt an, wenn sich z.B. 4 Mitarbeiter durch Teamfähigkeit auszeichnen (4 1en in einer Zeile) aber drei davon zudem durch Kritikfähigkeit, dann kann Teamfähigkeit als (dominierendes) Kriterium gestrichen werden, denn die drei verbleibenden sind team- und kritikfähig. Im Partionsfall kommen dann auch die Mitarbeiter, die nicht kritikfähig sind nicht mehr in Betracht und werden gestrichen.

Regel 4: wenn zwei Mitarbeiter die identischen Eigenschaften besitzen, entscheiden die Kosten. Regel 4Ü: MA j besitzt mehr Eigenschaften als MA k und j kostet zudem weniger als k, dann kann k gestrichen werden.

Nun zu Deiner Frage 😉: Mitarbeiter 2 kann in diesem Fall gestrichen werden, weil (upps! Da habe ich mich wohl in den Spalten verzählt!!) Mitarbeiter 7 mehr Eigenschaften mitbringt und weniger kostet.(Jetzt hoffe ich nicht, dass ich mir die Arbeit umsonst gemacht habe und Du nur über den Verzähler gestolpert bist... :confused

Hey Ratte 😉

Erst einmal vielen Dank für die gute Erklärung! Jetzt hat es endlich "klick" gemacht...ich glaub, ich werd langsam zu alt für sowas

wem sachste das?? :cool

super Erklärung