Fragen zu Aufgabe 1 3/04 und Aufgabe 2 9/05

View all featured content
D

dado

Dr Franke Ghostwriter
Fragen zu Aufgabe 1 (3/04) und Aufgabe 2 (9/05)

Hi!

bei folgenden Aufgaben komme ich nicht weiter:

Klausur 03/04 Aufgabe 1

Die Zielfunktion lautet hier:
Min 4x_1 + 5x_2 - x_3

die kanonische Form kann ja nun zwei Lösungen annehmen:
1) Max H - 4x_1 - 5_x2 - x_3
2) Max (-H) +4x_1 + 5x_2 - x_3 (wobei am Ende des Simplexverfahrens der Zielfunktionswert mit -1 multipliziert werden muss)

Leider komme ich mit den beiden Zielfunktionswerten zu unterschiedlichen Lösungen. Nun weiss ich nicht ob dies normal ist oder ob ich mirch verrechnet habe.


Die nächste Frage bezieht sich auf die Aufgabe2 aus 09/05

die Frage bezieht sich hierbei auf die Teilaufgabe c+d. Wie löse ich hier den Branch und Bound ausgehend von z=918,3 (111,6; 120). Ich komme hier einfach nicht auf die Lösung.


Danke für die hilfe
Gruß
Dado
 
Nach Datum sortieren Nach Stimmen sortieren
Dado,

ich glaube ich versehe Dein Problem zur Simplex nicht ganz.

Die Zielfunktion lautet ja:
Min 4x_1 + 5x_2 - x_3
und da unser Algorithmus nur maximiert:
max - 4x_1 - 5_x2 + x_3 (nicht -x_3, wie bei dir)
U.d.N. usw.

Ich habe hierzu auf die Schnelle das Ergebnis X_0= -95 (Lösung des Algorithmus war logischweise +95); X_1=7,5; X_2=0; X_3=12,5; S_1=0; S_2=0 allerdings verrechne ich mich gerne mal bei diesen Aufgaben. Möglicherweise kannst Du das Ergebnis aber in einer Newsgroup checken.

Ciao Carsten

P.S. zu der Anderen Aufgabe schaue ich später mal nach
 
Positive Stimme 0 Negative Stimme
dado schrieb:
Die nächste Frage bezieht sich auf die Aufgabe2 aus 09/05

die Frage bezieht sich hierbei auf die Teilaufgabe c+d. Wie löse ich hier den Branch und Bound ausgehend von z=918,3 (111,6; 120). Ich komme hier einfach nicht auf die Lösung.
Zum Vergrößern anklicken....

In dem von Dir beschriebenen Knoten ist die 120 ja schon ganzzahlig...die 111,6 aber noch nicht...nun wird die Verzweigung zu 111,6 gebildet:
a) [tex]x \leq 111[/tex]
oder
b) [tex]x \geq 112[/tex]

Auf dem a)-Zweig z=915 - das ist schlechter als ein ganzzahliges Ergebnis, das Du schon hast (nämlich 112,119 mit z=917), also ist dies terminiert

Auf dem b)-Zweig musst Du feststellen, dass diese Lösung nicht möglich ist, da hier die Nebenbedingung [tex]6x_2+7x_3\leq 1.510[/tex] verletzt ist
 
Positive Stimme 0 Negative Stimme
@ yara: vielen Dank, jetzt habe ich es verstanden.

@Nasenär: Mein Problem ist folgendes. Ich weiss, dass der Algorithmus nur maximiert --> min ist in ein Maximum umzuwandeln. Für die Umwandlung sehe ich aber zwei Möglichkeiten:

Min H = 4x_1 + 5x_2 - x_3 lässt sich schreiben als

1) Max (-H) + 4x_1 + 5x_2 - x_3 --> am ende muss dann der Zielfunktionswert mit der -1 multipliziert werden oder

2) Max H - 4x_1 - 5x_2 + x_3 --> am ende wird der Zielfunktionswert nicht mehr mit -1 multipliziert

Bei den beiden Verfahren bekomme ich aber unterschiedliche Lösungen. Habe ich mich verrechnet oder ist ein Lösungsverfahren falsch?

Gruß
Dado
 
Positive Stimme 0 Negative Stimme
Dado,

da ich das Glück hatte (wegen meines Erststudiums) nie Mathe belegen zu müssen, kenne ich das ganze Vorgeplänkel und die Theorie nicht richtig. Ich habe mir nur aus der Aufgabe B0402 von der Homepage des Lehrstuhls den Lösungsweg abgeschaut. Dort wird aus:
min xo = 3x_1 - 5x_2 - 2x_3 + 3
- max xo = -3x_1 + 5x_2 + 2x_3 - 3.

Du hingegen setzt hier xo auch noch mit ins Negative😕 , ich vermute, dass daher Deine unterschiedlichen Ergebnisse kommen.

Sicherlich gibt es für den Weg tolle Gründe, mir reicht für die KV einfach nur die Methode. :daumen:
Ciao Carsten
 
Positive Stimme 0 Negative Stimme
Antworten
Oben