Einsendeaufgabe 2

Ich könnte bei Aufgabe 1 Hilfe gebrauchen. Wenn ich folgnde Restriktionen setze: x4 <=1, x2 <=2, x1<=0, x3>=1, dann erhalte ich im nächsten Tableau s1 = 7/6 und damit x1 = -7/6, was aber aufgrund der nichtnegativitätsbedingung falsch ist. Setze ich zuvor x1=0, und streiche die entsprechende Spalte, dann ist die nächste Restriktion x3=0, was zu einem ganzzahligen Ergebnis führt. Ich setze dann wieder bei der Restriktion x2 an und formuliere dieses mal x2>=3. Als Ergebnis bekomme ich dann x2 = 3 und x4 = /710. Das nächste z wäre dann kleiner als 28. Damit kann ich doch dort abbrechen, bevor ich das neue Tableau durchgerechnet habe, oder? Dann habe ich noch durchgeprüft, wie es mit der Restriktion x1>= 1 weitergeht. Hier hänge ich aber wieder, da dananch s2 zur aufspaltung dient und ich mit den dann folgenden ergebnissen nichts anfangen kann - ich komme bei s2<=1 auf x= (1,2,0,9/10), was nicht richtig sein kann.Bei s2>= 1 bekäme ich dann s1=1/2, s2=0 (was ja gar nicht sein kann), x3=0, s4=0 und damit x = (3/2, 2,0, 1). Wie geht man denn mit einer Aufspaltung dmittels s um??? Wie habt ihr die Aufgabe gelöst? Ich sitze bereits Stunden an dieser einen Aufgabe, das muss doch irgendwie schneller gehen

Mark78, welches Problem löst du in der Aufgabe 1? Hier geht es doch um ein Rucksackproblem, oder irre ich mich? Ich bin bei der Lösung ähnlich wie im Beispiel 2.1, S. 23 vorgegangen. Als Lösung habe ich dann x1=0, x2=0, x3=1, x4=1, xo=26

Hm, ok. Vermutlich habe ich mir das Leben wieder selbst schwer gemacht und die Vorgehensweise wie bei Aufgabe 2.1 ist schneller und einfacher (und wahrscheinlich auch so vorgesehen). Allerdings habe ich als Ergebnis x0= 28 mit x=(0,2,0,1), was wohl mit ziemlicher Sicherheit auch richtig ist.
Ich habe das Ausgangsproblem nach dem Algorithmus auf S. 33f. gelöst (oder auch nicht) und habe daher 10 unterschiedliche Probleme zu behandeln gehabt, wobei ich bei zwei Problemen zu einer unzulässigen Lösung kam, da ich irgendetwas falsch mache, wenn in den vorherigen Problem ein s anstatt einem x ungerade wird (s. ÜB 2.5).
Gut, zumindest habe ich gesehen, wo ich noch Probleme habe. Clever war mein Lösungsweg aber nicht. Danke für den Hinweis!

Algorithmus auf der Seite 33f. ist für gemischte ganzzahlige Probleme mit mehreren Nebenbedingungen bestimmt. In der Aufgabe 1 ist aber das Rücksackproblem mit nur einer n.B. gestellt, deswegen, denke ich, ist der Algorithmus auf der Seite 23f hier richtig. Und bei diesem Verfahren setztst du als Nebenbediengung 0<=xj<=1. In diesem Fall kann xj nicht = 2 sein, sondern entweder 0, oder 1, oder?

Das Ausgangsproblem ist aber nicht binär. Welchen Sinn macht es eine suboptimale Lösung zu finden? Daher glaube ich, dass man den Algorithums von S. 23f. modifizieren muss indem man auch x>1 in Betracht zieht, was aber wieder zu umfangreichen Einzelproblemen führt. Hier bin ich sehr auf die Musterlösung gespannt. Die umwandlung in ein binäres Problem ist m.E. nicht zulässig und führt dann ja auch zu einem suboptimalen Ergebnis.

saui schrieb:

Hallo zusammen,ich habe hier mal meine Lösungen für die 3 Aufgaben hochgeladen. Da ich mir bei den Ergebnissen nicht wirklich sicher bin, wäre eine rege Fehlersuche vielleicht angebracht. Was sagt ihr zu den Lösungen?Viele GrüßeSaui

Zum Vergrößern anklicken....

Meine Lösung zu Aufgabe 3 : F(1,1) = F(1,2) = 2; F(2,1) = F(2,2) = 4, der Rest = 0. Bei j(1,1), j(2,1), j(1,2), j(2,2) habe ich je = 1. damit ist x1 = 2 und x2 = 0 und x0=4

Mark78,

Aufgabe 3 habe ich genauso, nur die F(k,y) Tabelle umgedreht: F(1,1)=F(2,1)= 2, F(1,2)=F(2,2)=4. Bei der Aufgabe 1 hattest du Recht, ich habe sie noch Mal angeschaut, da muss es anders gehen: ich habe P0 x4=19/10 x0=30,4; P1: x4=1, x2=9/4 xo=29,5; P2:keine lösung, P3 x4=1, x2=2, x1=1/6 x0=29,33, P4: keine lösung P5: x4=1, x2=2, x1=0 x0=28; P6 keine Lösung, Also die optimale Lösung P5 x2=2, x4=1, x0=28.
Wie hast die die Aufgabe 2b gelöst? Ich verstehe die Regel 3 gar nicht, kann auch aus dem Beispiel 5.4 nicht nachvolziehen wieso Zeile 2 gestriehen wurde. Ich mache es irgendwie und werde hoffen, dass die Punkten bei den anderen Aufgaben reichen um die EA zu bestehen.

Mark78,
ups, ich habe deine Antwort zum Thema Aufgabe 2 zu spät gesehen. Ich danke dir vielmals, Jetzt verstehe ich wie das geht. So, umgesetzt lautet dann meine Lösung: 1. Nach Regel 3 wird die Zeile 3 gestriechen und nach 3P Spalte 4 gestriechen, 2. Nach Regel 2 wird x3=1 und Spalte 3 und Zeilen 4 und 2 gestrichen, Nach Regel 2P wird Spalte 1 gestriechen. Verbleibt nur Spalte 2, also die Lösung ist x2=x3=1, x1=x4=0, Z=3.
Noch mal vielen Dank und viel Erfolg bei der Klausur!