Nochmal Frage zu Branch&Bound - Wann schreibe ich "keine Lösung"?

Nochmal Frage zu Branch&Bound - Wann schreibe ich "keine Lösung"?

Hallo ihr Lieben, ich bin zwar inzeischen einigermaßen hinter das Branch&Bound Verfahren gesteigen, aber mir ist noch eine Sache unklar:

Woran erkenne ich, dass bestimmte P's keine Lösung haben?
Erkenne ich das über meine bisherigen Restriktionen - weil das dann evtl einen Widerspruch gegen diese darstellt? Oder rechne ich irgendwie mit Simplex und komme da auf keine Lösung? - was wäre denn die einfachste variante?

Ich habe mal die unklaren Punkte in einer Übungsaufgabe vom Lehrstuhl rot markiert

Ich bin dankbar für jeden hinweis,
liebe grüße

Die Gleichungen gehen nicht auf. Bei P 4 muss X1 >= 10 und X2 >= 1 sein. Setzt Du das in die Nebenbedingung ein 5*10 + 2*1 =52 es dürfen aber höchstens 51 sein.

Danke für die erklärung Anna-dMd .... war ja eigentlich ganz simpel =)

Gerngeschehen

Mein Problem im obigen Beispiel ist, warum ich bei P7 und P8 aufhören kann zu rechnen.
Kann mir jemand einen Tip geben?

Bei jeder Verzweigung kann der Zielfunktionswert nur niedriger werden. Bei P7 hat man mit 69 (9;2) eine zulässige ganzahlige Lösung gefiunden. Da 61,5<69 ist terminiert man P8

Also ich habe bei dieser Aufgabe auch mal eine Frage und hoffe es kann mir wer weiterhelfen.
P7: wenn hier nicht bereits (9; 2) und z= 69 gegeben wäre, und man müsste die Werte selbst bestimmen, dann würde hier (9,4 und 2) und z= 71,8! Müsste man in diesem Fall x1 auf 9 stellen damit die obige Restriktion x < 9 eingehalten wird???? -

selbiges bei P5, hier errechnet man x1= 10 und x2= 0,5
Heißt auch hier da 0,5 nicht erlaubt aufgrund der oberen Restriktion x2 <0 - sehe ich das richtig?
danke für Hilfe

Scheli schrieb:

Also ich habe bei dieser Aufgabe auch mal eine Frage und hoffe es kann mir wer weiterhelfen.
P7: wenn hier nicht bereits (9; 2) und z= 69 gegeben wäre, und man müsste die Werte selbst bestimmen, dann würde hier (9,4 und 2) und z= 71,8! Müsste man in diesem Fall x1 auf 9 stellen damit die obige Restriktion x < 9 eingehalten wird???? -

selbiges bei P5, hier errechnet man x1= 10 und x2= 0,5
Heißt auch hier da 0,5 nicht erlaubt aufgrund der oberen Restriktion x2 <0 - sehe ich das richtig?
danke für Hilfe

Zum Vergrößern anklicken....

Ja, siehst Du richtig, der "Entscheidungsbaum" muss von oben nach unten durchgängig sein, d.h. eine Begrenzung einer Größe im oberen Bereich darf unten nicht überschritten werden.

Gruß
Thorben