Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Branch and Bound

Branch and Bound

Universität / Fachhochschule

Sonstiges

Tags: Ganzzahligkeit

Klisa aktiv_icon

16:21 Uhr, 09.02.2018

Hallo zusammen,
beim Punkt 6 ist z= -23,8 x=0, y= 7
ist somit die Ganzzahligkeit erfüllt oder muss z auch noch ganzzahlig sein?

LG

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

anonymous

16:44 Uhr, 09.02.2018

Hallo
Du bist ja lustig.
Na ja, es ist ja auch Fasching...
Nichts desto trotz - willst du uns noch ein klein wenig von der Aufgabenstellung verraten?
Helau!

Klisa aktiv_icon

16:58 Uhr, 09.02.2018

Sorry ich wollte mich bei dieser Aufgabe mit dem Branch and Bound kontrollieren.
Jetzt wusst ich gerade nicht mehr, ob die Ganzzahligkeit erfüllt ist wenn z nicht ganzzahlig ist und nur x und y.

anonymous

17:15 Uhr, 09.02.2018

Und was verstehst du unter "z" ??
Narri - Narro -

Klisa aktiv_icon

17:16 Uhr, 09.02.2018

den Zielfunktionswert

Klisa aktiv_icon

17:16 Uhr, 09.02.2018

den Zielfunktionswert

Klisa aktiv_icon

17:16 Uhr, 09.02.2018

den Zielfunktionswert

anonymous

18:17 Uhr, 09.02.2018

Also vermutlich meinst du die Zielfunktion

z = 7 \cdot x + 3.4 \cdot y

Diese Festlegung "z" hast du selbst getroffen.

a)

Deshalb musst du sie auch erklären.

b)

Aus dem Grund ist auch in der Aufgabenstellung nirgends die Rede von "z".
Und deshalb ist das auch keine Forderung der Aufgabenstellung, deine willkürliche Festlegung "z" ganzzahlig zu halten...

ledum aktiv_icon

18:26 Uhr, 09.02.2018

Hallo
wie kommst du mit

x, y > 0

auf negative

z

Werte?
Gruß ledum

Klisa aktiv_icon

18:31 Uhr, 09.02.2018

Hallo ich glaube wir reden aneinander vorbei.
Bei Aufgabenteil a ist ein relaxiertes Problem zu betrachten.
Bei Aufgabenteil B ist die eigentliche Aufgabenstellung mit x,y ∊ Z gefragt das bedeutet hier wird eine Lösung mit Ganzzahligkeit abgefragt so wie ich das verstehe? Ich möchte nur wissen, ob die Ganzzahligkeitsbedingung von Branch and Bound erfüllt ist, wenn der Zielfunktionswert, nicht ganzzahlig ist, sondern lediglich x und y

Klisa aktiv_icon

18:32 Uhr, 09.02.2018

ich habe das min zu einem max Problem gemacht in dem ich mal -1 multipliziert habe.

Klisa aktiv_icon

18:32 Uhr, 09.02.2018

ich habe das min zu einem max Problem gemacht in dem ich mal -1 multipliziert habe.

anonymous

18:37 Uhr, 09.02.2018

"Ich möchte nur wissen, ob die Ganzzahligkeitsbedingung von Branch and Bound erfüllt ist, wenn der Zielfunktionswert, nicht ganzzahlig ist, sondern lediglich

x

und y"

Wenn du dir einfach nochmals
"Und deshalb ist das auch keine Forderung der Aufgabenstellung, deine willkürliche Festlegung "z" ganzzahlig zu halten..."
durchlesen und berücksichtigen willst, dann wirst du auch erkennen, das das schon genau die Antwort auf deine Frage war.

Klisa aktiv_icon

18:50 Uhr, 09.02.2018

Ui ui ui, sorry. Vielen Dank!

Könnt ihr noch Blick auf meine Lösungen werfen, von allen Teilaufgaben

Teilfaufgabe c:
x=2; y=3; z=-24,2

Die Lösung ist unzulässig, da x,y nicht im Lösungsbereich liegt

Teilfaufgabe d:
Dies ist eigentlich dasselbe wie Teilaufgabe C aber das kann doch nicht sein wenn mann Teilaufgabe a: x=1,7 und y=3,027 auf x=2 und y=3 rundet dann ist x, y nicht im Lösungsbereich

Irgendwas passt da doch nicht?

Teilaufgabe a u. b wurde grafisch gelöst siehe Anhang:

anonymous

19:10 Uhr, 09.02.2018

Gehen wir doch Schritt für Schritt vor.

1)

Ich hoffe, wir sind uns einig:
Die nicht-ganzzahlige Lösung lautet:

x = \frac{63}{37}

y = \frac{112}{37}

2)

Dann hast du vermutlich gerundet, um ganzzahlig zu werden.
So kommen wir auf:
x_rund

= 2

y_rund

= 3

Du sagst, das sei "unzulässig, da

x, y

nicht im Lösungsbereich liegt".
Das habe ich nicht recht verstanden.
Was soll daran unzulässig sein?

Klisa aktiv_icon

19:50 Uhr, 09.02.2018

Bei der Teilaufgabe B bin ich wie folgt vorgegangen:

Ich hab ein Z angenommen, also in meinem Fall z=10. Dann habe ich habe ich x und y Null gesetzt um die Schnittpunkte mit der x und y-Achse der Zielfunktion zu erhalten. Diese gerade habe ich eingezeichnet und geschaut, wo Sie durch einen ganzzahligen Punkt durchgeht wenn ich sie parallel verschiebe und habe darauf geachtet, dass der Zielfunktionswert hierbei maximal wird also die Negativität möglichst klein.

Durch die Nebenbedingungen wird doch ein Bereich festgelegt, in welchem ich die Ganzzahlige Lösung suchen muss oder ? Oder sehe ich das gänzlich falsch. Ich habe das so, interpretiert, dass dieser zwischen den geraden ist oberhalb y=4.

Muss ich da anders vorgehen?

Wie würdest du die Aufgabe angehen?

Vielen Dank für deine Mühe!

anonymous

22:38 Uhr, 09.02.2018

"ich glaube wir reden aneinander vorbei."
Jetzt bin ich es, der glaubt, wir reden aneinander vorbei.
Also, deine Grafik von

18 : 50 h

ließ eigentlich grafisch schon Hoffnung, Ansatz und Sprößlinge keimen.
Aber wie ich deine Ausführungen zuletzt verstehen oder auch nur ansatzweise mit dem Bild in Einklang bringen soll ist mir ein buntes Rätsel.
Vielleicht ist es besser, wir gehen auf den Karneval und besaufen uns.

Goggelores - Giggerigie !

Enano

02:13 Uhr, 10.02.2018

"Aber wie ich deine Ausführungen zuletzt verstehen oder auch nur ansatzweise mit dem Bild in Einklang bringen soll ist mir ein buntes Rätsel."

Also ich kann keinen Widerspruch zwischen Klisas Grafik und Rechnung von

18 : 50

Uhr und ihrer Beschreibung zur Vorgehensweise bei der Lösung zu

b)

erkennen.

Enano

02:58 Uhr, 10.02.2018

"Durch die Nebenbedingungen wird doch ein Bereich festgelegt, in welchem ich die Ganzzahlige Lösung suchen muss oder ?"

Ja, das stimmt.

"Ich habe das so, interpretiert, dass dieser zwischen den geraden ist oberhalb y=4."

Nicht nur zwischen den Geraden, denn weil die beiden Nebenbedingungen vom Typ "

\geq

" bzw. "

\leq

" sind, kommen auch x-y-Kombinationen infrage, die auf den Unter- bzw. Obergrenzen liegen,

z . B

. einer der Eckpunkte als nicht nur zulässiger, sondern auch optimaler Lösung (hier:

x = 0, y = 7)

.

"Muss ich da anders vorgehen?"

Nein, grundsätzlich nicht.

"Teilfaufgabe

c : x = 2; y = 3; z = - 24,2

Die Lösung ist unzulässig, da

x, y

nicht im Lösungsbereich liegt"

Nein, wie kommst du darauf, dass diese Kombination nicht im zulässigen Bereich liegt? Das ist zwar nicht die optimale, aber eine zulässige Lösung, weil die Nebenbedingungen erfüllt sind.

Klisa aktiv_icon

23:59 Uhr, 10.02.2018

Hey Enano,
Vielen vielen Dank für deine Hilfe!
Ich tue mir nach wie vor noch ein wenig schwer bei der Teilaufgabe c und d

Bei Teilaufgabe C würde ich schreiben, dass sie im zulässigen Bereich liegt, so wie du bereits sagtest aber das durch die Rundung keine optimale Lösung mehr vorliegt, aber dennoch die Nebenbedingungen erfüllt sind. Wenn man die Zielfunktionswerte vergleicht, muss festgestellt werden dass a nach dem Rundungsvorgang einen kleineren Zielfunktionswert aufweist als b.

So würde ich es hin schreiben.

Kannst du mir evtl. bei der Teilaufgabe d nochmal helfen und die Lösung begründen?

Das wäre super lieb von dir!

LG

Enano

03:02 Uhr, 11.02.2018

Hallo Klisa,

"Bei Teilaufgabe

C

würde ich schreiben,..."

wenn du dazu noch deine zuvor genannten Resultate für

x, y

und

Z

hinzufügst, sollte

c)

damit richtig und vollständig beantwortet sein.

"Kannst du mir evtl. bei der Teilaufgabe

d

nochmal helfen und die Lösung begründen?"

Wird der x-Wert aus

a)

nicht auf 2 aufgerundet, sondern auf 1 abgerundet und der y-Wert
anstatt auf 3 abgerundet, auf 4 aufgerundet, ist der Zielfunktionswert noch niedriger als bei

a) (7 \cdot 1 + 3,4 \cdot 4 = 20,6),

aber dadurch, dass die 2. Nebenbedingung nicht erfüllt ist

(7 \cdot 1 + 3 \cdot 4 = 19 < 21),

liegt dieser Punkt im unzulässigen Bereich.

Gruß
Enano

Klisa aktiv_icon

10:01 Uhr, 11.02.2018

Hey Enano, ich hoffe ich strapaziere nicht deine Nerven! Jedoch bin ich mal wieder verwirrt, denn die 2.NB ist doch erfüllt wenn 19<21 ist?

Was sehe ich schon wieder falsch? Sorry das ich so schwer von Begriff bin, es tut mir wirklich leid und vielen Dank für deine Hilfe!!!

LG Lisa

Enano

10:42 Uhr, 11.02.2018

"ich hoffe ich strapaziere nicht deine Nerven!"

Nein, im Gegenteil, ich finde es gut und es ist richtig, dass du nachfragst, wenn dir etwas nicht klar ist.
Ich neige manchmal auch dazu, Fehler zu machen. ;-)

"die 2.NB ist doch erfüllt wenn

19 < 21

ist?"

Die 2. Nebenbedingung lautet doch gem. Aufgabentext:

7 x + 3 y \geq 21

19

ist aber nicht

\geq 21,

sondern kleiner, folglich ist diese Bedingung nicht erfüllt.

Die erste Bedingung

4 x + 7 y \geq 28

wird erfüllt, denn

4 \cdot 1 + 7 \cdot 4 = 32

ist größer als

28

.

Bei

c)

ist es anders, da werden beide Bedingungen erfüllt, denn

7 \cdot 2 + 3 \cdot 3 = 23

ist größer als

21

und

4 \cdot 2 + 7 \cdot 3 = 29

ist größer als

28

Klisa aktiv_icon

11:15 Uhr, 11.02.2018

Vielen Dank für deine Hilfe du hast mir sehr geholfen! Ich würde dir gerne eine gute Bewertung abgeben, nur leider kann ich dich bei der Bewertung nicht auswählen, es wird lediglich der erst Helfer aufgeführt, kannst du mir vlt. auch hierzu einen Tipp geben wie ich das anstellen kann?

Enano

11:30 Uhr, 11.02.2018

Du warst vielleicht verwirrt, weil du das Minimierungsproblem in ein Maximierungsproblem umgewandelt hast und durch die Multiplikation der Zielfunktion und der NB mit

- 1 u . a

. für die 2. NB

- 7 x - 3 y \leq - 21

erhalten hast.

Aber auch wenn du hier für

x = 1

und für

y = 4

einsetzt, ist NB nicht erfüllt, denn

- 7 \cdot 1 - 3 \cdot 4 = - 19

und das ist nicht kleiner oder gleich

- 21

.

"kannst du mir vlt. auch hierzu einen Tipp geben wie ich das anstellen kann?"

Danke, aber das weiß ich leider nicht. ;-)

Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.

1414428

1414192

	Status: nicht eingeloggt	Noch nicht registriert?