Übungsaufgabe B0507 - Branch&Bound

Die Lösung, die bei P3 rauskommen soll, kommt bei mir bei P6 raus (anstelle: keine Lösung).

51/5=10,2
33/2= 16,5
Kleinster von den beiden Werten ist 10,2.

Somit muss es bei P3 auf der linken Seite: 10,2/0 heißen.

Setzt man dies oben ein, ergibt es z=71,4

mein_traum wrote:

Hallo zusammen,

ich habe gerade versucht, die Ergebnisse nachzurechnen. Leider scheitere ich immer im Punkt P3 - ich komme einfach nicht auf das Ergebnis, obwohl die Rechnung ja "eindeutig" erscheint. Man muss doch einfach nur die 2 Bedingungen (x1>=10 und x2<=0) hinzufügen und wieder Simplex-Verfahren ausführen... Kann es sein dass die Lösung falsch ist oder steh ich völlig auf dem Schlauch?

Amber-Ann,

ich glaube, ich bin total überlernt... Ich habe heute die Aufgabe x-mal gerechnet und kam nicht auf das Ergebnis - obwohl ich Simplex jetzt nicht sooo schwer finde, jetzt denk ich - das kann doch nicht sein (weil du meintest das sei richtig) und habe es einfach zum 1001 Mal gemacht - auf einmal passt es... :eek:

Einen Fehler habe ich allerdings vorher immer gemacht: ich habe beim Dividieren der RHS (um das Pivotelement zu finden) immer gedacht, es müsste der minimalste positive Wert sein, aber OHNE Null. Soweit ich jetzt aber über diese Aufgabe herausgefunden habe, gehört die Null dazu, sprich wenn ich nach dem Dividieren 0 herausbekomme, bestimmt diese Zeile die Pivotzeile...

Wieso wendest du hier Simplex an?
War es da direkt gefordert?
Ich setze es immer in die Nebenbedingungen ein und erhalte so fix das Ergebnis.

Ich machs auch über die NBD. Dachte auch immer der minimalste positive Wert...

Weil ich die Ergebnisse nachrechnen / nachvollziehen wollte und das geht doch nur über Simplex oder?! hm...? Täusch ich mich?

Weiß jetzt jemand, wie das mit Simplex und der null ist? Weil Winnie auch sagt, der minimalste positive, so wie ich das auch dachte, allerdings führt das halt bei der Aufgabe nur dann zum Ergebnis, wenn man die null nimmt...

mein_traum wrote:

Weiß jetzt jemand, wie das mit Simplex und der null ist? Weil Winnie auch sagt, der minimalste positive, so wie ich das auch dachte, allerdings führt das halt bei der Aufgabe nur dann zum Ergebnis, wenn man die null nimmt...

:confused::confused::confused: Was für ne Null? Da kommt doch keine Null vor.
Und kleiner Null wie du unten geschrieben hast, erst recht nicht.
Ich weiß nicht, was du machst, deshalb kann ich dir auch nicht helfen.

Ich rede von dem Wert der RHS, der mir zeigt, dass bei dem bestimmten Wert der RHS dies die PivotZEILE ist. Darf dieser Wert (geteilt durch die möglichen Pivotelemente) auch 0 sein oder muss es zwingend der kleinste positive Wert (ohne 0) sein? In dem Simplex, der bei mir zur Lösung führte musste ich nämlich den 0-Wert nehmen, obwohl ich bislang dachte, dass es der kleinste minimale positive Wert (ohne 0) sei. :)

Sorry, das ist auch etwas umständlich zu erklären.

Verstehe nur Bahnhof.:confused::confused:

Null und minus darfst du natürlich nicht nehmen. Null ist kein Wert.

mein_traum wrote:

Weil ich die Ergebnisse nachrechnen / nachvollziehen wollte und das geht doch nur über Simplex oder?! hm...? Täusch ich mich?

Ja du täuschst dich. Wenn eine der beiden Variablen durch die an den Branches stehenden Bedingungen fixiert ist, kannst du die andere - wie ja schon von Amber-Ann beschrieben - durch Einsetzen der fixierten Variablen in sämtliche Nebenbedingungen mit minimalem Zeitaufwand bestimmen.

@mein_traum & Amber-Ann

Basierend auf der (unrichtigen) Meinung, dass ein Subproblem im Rahmen B&B stets komplett als LP hingeschrieben und anschließend [U]nur[/U] mit Simplex gelöst werden kann, hat mein_traum die B0507 in dieser Manier nachgerechnet. Hierbei beinhaltete eines der Subprobleme die Branchbedingung "x2 <= 0". Dies führt dann zu der Gleichung x2 + Schlupfvariable = [COLOR=red][B]0[/B][/COLOR]. Übertragen ins Simplex-Tableau ist jetzt folgende Situation entstanden, die [U]z. B.[/U] wie folgt aussehen könnte:

Der Spaltenvektor der Pivotspalte (ohne Zielfkt.-Zeile(n)) habe die Werte (1,2,3). Der Spaltenvektor der rechten Seite (ohne Zielfkt.-Zeile(n)) habe die Werte (4,5,[COLOR=red][B]0[/B][/COLOR]). Als Pivotzeile wird jetzt die Zeile ausgewählt, für die das Minimum der Quotienten 4/1, 5/2 und [COLOR=red][B]0[/B][/COLOR]/3 angenommen wird. Das ist in diesem Fall natürlich die Zeile, in der auf der rechten Seite die [COLOR=red][B]0[/B][/COLOR] steht.

Falls noch bei mein_traum Zweifel bestehen: Das Skript, Wikipedia oder jedes beliebige OR-Lehrbuch hernehmen. Bei der Auswahl der Pivotzeile ist nirgendwo ausgeschlossen, dass der ZÄHLER des Quotienten auch den Wert 0 besitzen darf.

Anders verhält es sich ja bekanntermaßen mit dem NENNER des Quotienten. Ist der Nenner Null oder kleiner als Null, so darf dieser Quotient ja nicht gebildet werden und die betreffende Zeile kann somit auf keinen Fall Pivotzeile werden.

Wann weiß ich, ob ich in Branch und Bound nicht mehr weiterrechnen muss?