Hallo,
ich habe eine Frage. Wenn ich ein lineares Optimierungsproblem habe, die Ganzzahligkeitsbedingung weglasse und das Problem mit dem Simplex-Algorithmus löse, bekomme ich die relaxierte Lösung.
Genau, alles ganz relaxed
😉
Wie kann ich von der ausgehend die optimale ganzzahlige Lösung finden? Muss ich hierzu Branch & Bound anwenden?
Musst Du!
Wenn ja, wie sieht dann das Tableau aus zur Lösung?
Das Tabelau "sieht gar nicht aus". Es gibt kein Branch & Bound Tableau! Du machst eine Fallunterscheidung.
Angenommen Du hast x1 = 1,6 gefunden und x2 = 2,2.
Dann haben beide Variablen gegen die Ganzzahligkeit verstoßen. Du suchst Dir dann eine von den beiden aus, anhand jener Du nun verzweigst. Angenommen dies ist x1. Dann führst Du nun zusätzliche Nebenbedingungen ein.
Wenn x1 eben nicht den Wert 1,6 annehmen kann, könnte es ja den Wert 1 oder den Wert 2 annehmen. Eine solche Beschränkung der zulässigen Lösungsmenge ist allerdings zu restriktiv. Nur 1 und 2 zuzulassen würde verbieten auch 0 oder 3 oder 4 etc. zuzulassen.
Das heißt also:
Bei einem Zweig führst Du die Bedingung x1 <= 1 ein und an dem anderen x1 >= 2.
Die Nebenbedingung x1 <= 1 nimmst Du in dein Tableau auf und rechnest einen neuen Zielfunktionswert Z1 aus.
Jetzt hat man zwei "Philosophien", die zur Auswahl stehen. Entweder du verzweigst ausgehend von Z1 in die Tiefe (Baum nach unten wandern = Tiefensuche), oder Du rechnest erst noch x1 >= 2 aus (Achtung: Hier wäre dann der 2 Phasen angesagt!) und schaust dann (= Breitensuche).
Was ist nun besser? Nun, dass kann nicht endgültig beantwortet werden.
Fakt ist aber:
1.) Entlang einer Kanten, die ich entlang wandere sind immer alle Nebenbedingungen erfüllt.
Wenn z.B. x1 <=3 ganz weit oben gesetzt wurde und unten nochmal x1 >= 3 vorkommt, so muss natürlich x1 = 3 gelten.
2.) Je mehr Nebenbedingungen, desto schlechter mein Zielfunktionswert.
Das ist wichtig zu wissen, denn angenommen im fünften Knoten ergäbe sich x1 = 10; x2 = 4; Z = 95,2, womit man eine zulässige ganzzahlige Lösung hätte. Verzweigt man nun weiter (Knoten 6) und erhält x1 = 9,7; x2 = 3,1; Z = 94,1, dann wäre es nicht klug weiter zu verzweigen! Denn würde man Knoten 6 wieder gannzzahlig machen wollen, wird das Ergebnis kleiner als 94,1 sein.
Ich persönlich mache ja eher Breitensuche...
