Überdeckungs- und Partitionsproblem

Also wenn ich das richtig kapiert habe läuft das so:

Regel3: Sind in einer Zeile A alle Elemente 1, die auch in einer Zeile B gleich 1 sind, dann kann Zeile A gestrichen werden.
Auf das Beispiel übertragen:
In Zeile 6 sind alle Elemente 1, die auch in Zeile 2 eine 1 besitzen, daher kann 1 weg. Zeile 10 kann weg, da diese mit Zeile 8 übereinstimmt. Man hätte alternativ vermutlich auch Zeile 8 löschen können.

Regel 4Ü erweitert nur Regel4, in Regel 4 muss die Anzahl der einsen zweier Spalten gleich sein, in Regel 4Ü gilt das ">=".
Bedeutet: Besitzen zwei Spalten gleichviele Einsen (Regel 4) oder eine Spalte A besitzt mehr Einsen als Spalte B (Regel 4Ü), so kann die Spalte gelöscht werden deren Kosten höher sind.

Ist noch alles ohne gewähr, aber so habe ich es verstanden und so geht das Beispiel auch auf.

Habe gerade die Aufgabe 1 der EA2 gemacht und komme dort auf x3=x9=1 und cTx=10.
Wenn das jemand bestätigen kann, würden o.g. Regeln stimmen.....wenn nicht, nehme ich alles oben geschriebene zurück

ich habe gerade die Aufgabe 1b) aus EA2 gemacht und bin ich zum gleichen Ergebnis gekommen. Zuerst habe ich die Regel 2 und 3 benutzt und dann die Regel 4Ü. Danach habe ich nochmals die Regel 2 und 3 benutzt.

Dann bin ich auf x3=x9=1 gekommen. c3=9 und c9=1 und das macht zusammen Zielfunktionswert cT=10.

Kannst du bitte mein Verfahren bestätigen?

Danke im Voraus.

RB.

Siehe meine Lösung in einer Excel-Tabelle.
----
17.6.
Nochmals und besser. Ich bin wahrscheinlich drauf gekommen,
dass ich in meiner Lösung, die ich gestern gepostet habe,
eine Fehler gehabt.

x2 = 1, x8=1, x9=1
cT 5+1+1 = 7

Aber hier bin ich auch nicht 100% sicher.
Ich füge meine Lösung ein.

RB

rbehan schrieb:

Hallo Chris,

x2 = 1, x8=1, x9=1
cT 5+1+1 = 7

Aber hier bin ich auch nicht 100% sicher.
Ich füge meine Lösung ein.

RB

Zum Vergrößern anklicken....

komme auf dasselbe mit gleichem Lösungsweg

ich habe das mit den reduktionen jetzt glaub ich langsam verstanden🙂 aber ich verstehe den letzten Schritt nicht ganz... bspw. im Beispiel 5.4 S. 81 wie kommt man da auf die Optimallösung x1=x3=x4=1 mit cx=12?? kann mir da bitte jemand weiter helfen??? es ist bestimmt ganz simpel und ich seh es einfach nicht... es hat doch was mit der Streichung der Spalten zu tun oder nicht ?? was ist mit x5 ???

ich bins nochmal🙂 kann mir jemand zufällig erklären wie man das Überdeckungsproblem der ÜA 5.1 Löst ??? Ich hab die Regeln wohl doch noch nicht so gut drauf.... habe hier schon in einem anderen Beitrag geschaut...aber da verstehe ich es auch nicht recht....

Je öfter man sich mit den Regeln beschäftigt, desto mehr versteht man auch.... =)

Ich rechne gerade alte Klausuren durch und bin auf Aufgabe 4 der Klausur März 2011 (Überdeckungsproblem) gestoßen.

Folgendes habe ich errechnet:

x0 = x1 + x2 + x6 = 1+3+2= 6

Kann das irgendwer nachrechnen und ggf. bestätigen?

WiWi_Master schrieb:

Je öfter man sich mit den Regeln beschäftigt, desto mehr versteht man auch.... =)
Ich rechne gerade alte Klausuren durch und bin auf Aufgabe 4 der Klausur März 2011 (Überdeckungsproblem) gestoßen.
Folgendes habe ich errechnet:
x0 = x1 + x2 + x6 = 1+3+2= 6
Kann das irgendwer nachrechnen und ggf. bestätigen?

Zum Vergrößern anklicken....

Habe mir die Aufgabe gerade angeschaut, komme allerdings auf:
x2=x3=1 und somit 3+6=9

Im ersten Schritt habe ich Regel 2 angewendet: Zeile 5,2,3 sowie Spalte 2 raus und x2 = 1

Dann R3, wodurch Zeile 4 gestrichen wird (wird von Zeile 1 überdeckt)

Im dritten Schritt dann Regel 4, wodurch Spalte 4,5,6,7,8,9 raus fliegen, da diese jeweils eine "1" enthalten, deren Kosten aber alle höher als die von Spalte 1 sind.

Dann wird noch einmal Regel 2 angewendet wodurch Zeile 6 und 1 gestrichen werden sowie Spalte 3. Es wird x3=1 gesetzt und Ende.

Somit ergibt sich x2=x3=1.....oder habe ich was falsch verstanden??

Die ersten beide Schritte habe ich genauso mit der ersten Festlegung x2=1.

Anschließend habe ich auch Regel 4 angewendet:

1) Habe ich Spalte 9 gestrichen, weil z.B. die Spalten 4 und 5 zusammen gleich hohe Kosten "c" (5=5) und gleiche viele "a" haben.
2) Habe ich Spalte 3 gestrichen, weil z.B. die Spalten 4 und 5 zusammen niedrigere Kosten "c" (5<6) und gleiche viele "a" haben.

In Zeile 6 bleibt dann nur noch eine 1 und daher wird x6=1 gesetzt.

In Zeile 4 habe ich das x mit den geringsten Kosten ausgewählt. Damit x1=1, weil Kostenvektor = 1.

Soweit mein Lösungsvorschlag...