Branch & Bound: Unterschied zwischen den Versionen

Aus Operations-Research-Wiki
Wechseln zu: Navigation, Suche
[unmarkierte Version][unmarkierte Version]
(→‎Vorlesung)
Zeile 29: Zeile 29:
  
 
:(b) Zusätzlich zu den bisherigen Restriktionen gilt die upper bound '''u<sub>r</sub> = b<sub>r</sub> - f<sub>r</sub>) &le;  BV<sub>r</sub>''' .  
 
:(b) Zusätzlich zu den bisherigen Restriktionen gilt die upper bound '''u<sub>r</sub> = b<sub>r</sub> - f<sub>r</sub>) &le;  BV<sub>r</sub>''' .  
−
:::Daher muss BV<sub>r</sub> durch ''' \overline{BV}<sub>r</sub> = u<sub>r</sub> - BV<sub>r</sub>''' erstetzt werden.  
+
:::Daher muss BV<sub>r</sub> durch '''   BV<sub>r</sub>&oline; = u<sub>r</sub> - BV<sub>r</sub>''' erstetzt werden.  
 
:::Die neue rechte Zeile berechnet sich nach den Regeln für das Einrechen einer Obergrenze: '''b<sub>r</sub><sup>neu</sup>=u<sub>r</sub> - b<sub>r</sub>''' und alle a<sub>rj</sub> wechseln das Vorzeichen.
 
:::Die neue rechte Zeile berechnet sich nach den Regeln für das Einrechen einer Obergrenze: '''b<sub>r</sub><sup>neu</sup>=u<sub>r</sub> - b<sub>r</sub>''' und alle a<sub>rj</sub> wechseln das Vorzeichen.
−
:::Die Quellzeile wird also durch  '''\overline{BV}<sub>r</sub> - &sum; (a<sub>rj</sub>*NBV<sub>r</sub>) = - f<sub>r</sub>''' erstetzt.
+
:::Die Quellzeile wird also durch  '''BV<sub>r</sub>&oline; - &sum; (a<sub>rj</sub>*NBV<sub>r</sub>) = - f<sub>r</sub>''' erstetzt.
  
 
: Für jedes dieser Teilprobleme muss nun versucht werden die ganzzahlige Optimallösung zu finden, in dem man auf jedes diesen Algorithmus anwendet, also zu Schritt (1) geht. Mit welchem der Teilprobleme man beginnt, ist egal.
 
: Für jedes dieser Teilprobleme muss nun versucht werden die ganzzahlige Optimallösung zu finden, in dem man auf jedes diesen Algorithmus anwendet, also zu Schritt (1) geht. Mit welchem der Teilprobleme man beginnt, ist egal.
Zeile 116: Zeile 116:
  
 
(b) zusätzlich zu den bisherigen Restriktionen gilt die upper bound x<sub>2</sub> &le; 2
 
(b) zusätzlich zu den bisherigen Restriktionen gilt die upper bound x<sub>2</sub> &le; 2
−
  x<sub>2</sub> muss durch /overline{x}<sub>2</sub> ersetzt werden
+
  x<sub>2</sub> muss durch x<sub>2</sub>&oline; ersetzt werden
  
 
neue Zeile von x<sub>2</sub>: /overline{x}<sub>2</sub>+1/9*y<sub>1</sub>-2/9*y<sub>2</sub> = -4/9
 
neue Zeile von x<sub>2</sub>: /overline{x}<sub>2</sub>+1/9*y<sub>1</sub>-2/9*y<sub>2</sub> = -4/9
Zeile 132: Zeile 132:
 
|align="center"|'''x<sub>1</sub>'''||align="center"|4/9||align="center"|1/9||align="center"|47/9
 
|align="center"|'''x<sub>1</sub>'''||align="center"|4/9||align="center"|1/9||align="center"|47/9
 
|-valign="middle"  
 
|-valign="middle"  
−
|align="center"|'''/overline{x}<sub>2</sub>'''||align="center"|1/9||align="center"|-2/9||align="center"|-4/9
+
|align="center"|'''x<sub>2</sub>&oline;'''||align="center"|1/9||align="center"|-2/9||align="center"|-4/9
 
|}
 
|}
 
Abb 4: Tableau 1b
 
Abb 4: Tableau 1b
Zeile 160: Zeile 160:
 
| width="40"|
 
| width="40"|
 
! width="40" align="center"|y<sub>1</sub>'  
 
! width="40" align="center"|y<sub>1</sub>'  
−
! width="40" align="center"|/Overline{x}<sub>2</sub>
+
! width="40" align="center"|x<sub>2</sub>&oline;
 
| width="40"|
 
| width="40"|
 
|- valign="middle"  
 
|- valign="middle"  
Zeile 187: Zeile 187:
 
Sie können Sich zu diesem Themengebiet eine Vorlesung ansehen.  
 
Sie können Sich zu diesem Themengebiet eine Vorlesung ansehen.  
  
−
===09.01.2007===
+
====Wintersemester 2007/2008====
−
[http://www-bior.wiwi.uni-kl.de/bior/lehre/vorles/OR_winter/OR_Plan_Wiki/wp/simplex_bb_090107/simplex_bb_090107.zip Branch&Bound 09.01.2007 (Download)]
+
−
<br>[http://www-bior.wiwi.uni-kl.de/bior/lehre/vorles/OR_winter/OR_Plan_Wiki/wp/simplex_bb_090107/20070109b.svg Branch&Bound 09.01.2007 (Stream)]
+
−
<br>[http://www-bior.wiwi.uni-kl.de/bior/lehre/vorles/OR_winter/OR_Plan_Wiki/wp/simplex_bb_090107/20070109b_scale.svg Branch&Bound 09.01.2007  (scaled Stream)]
+
  
−
===16.01.2007===
+
[[media:Slides_07_BranchBound.wmv | Vorlesungsmitschnitt zum Thema Branch&Bound
−
[http://www-bior.wiwi.uni-kl.de/bior/lehre/vorles/OR_winter/OR_Plan_Wiki/wp/simplex_bb_160107/simplex_bb_160107.zip Branch&Bound 16.01.2007 (Download)]
+
−
<br>[http://www-bior.wiwi.uni-kl.de/bior/lehre/vorles/OR_winter/OR_Plan_Wiki/wp/simplex_bb_160107/20070116.svg Branch&Bound 16.01.2007 (Stream)]
+
−
<br>[http://www-bior.wiwi.uni-kl.de/bior/lehre/vorles/OR_winter/OR_Plan_Wiki/wp/simplex_bb_160107/20070116_scale.svg Branch&Bound 16.01.2007  (scaled Stream)]
+
  
−
Achtung: die Dateien können fehlerhaft sein! Sobald dies möglich ist, werden aktuelle Mitschnitte aus dem WS 07/08 zur Verfügung gestellt.<br>
+
====Wintersemester 2006/2007====
 +
 
 +
*09.01.2007
 +
:*[http://www-bior.wiwi.uni-kl.de/bior/lehre/vorles/OR_winter/OR_Plan_Wiki/wp/simplex_bb_090107/simplex_bb_090107.zip Branch&Bound 09.01.2007 (Download)]
 +
:*[http://www-bior.wiwi.uni-kl.de/bior/lehre/vorles/OR_winter/OR_Plan_Wiki/wp/simplex_bb_090107/20070109b.svg Branch&Bound 09.01.2007 (Stream)]
 +
:*[http://www-bior.wiwi.uni-kl.de/bior/lehre/vorles/OR_winter/OR_Plan_Wiki/wp/simplex_bb_090107/20070109b_scale.svg Branch&Bound 09.01.2007  (scaled Stream)]
 +
 
 +
*16.01.2007
 +
:*[http://www-bior.wiwi.uni-kl.de/bior/lehre/vorles/OR_winter/OR_Plan_Wiki/wp/simplex_bb_160107/simplex_bb_160107.zip Branch&Bound 16.01.2007 (Download)]
 +
:*[http://www-bior.wiwi.uni-kl.de/bior/lehre/vorles/OR_winter/OR_Plan_Wiki/wp/simplex_bb_160107/20070116.svg Branch&Bound 16.01.2007 (Stream)]
 +
:*[http://www-bior.wiwi.uni-kl.de/bior/lehre/vorles/OR_winter/OR_Plan_Wiki/wp/simplex_bb_160107/20070116_scale.svg Branch&Bound 16.01.2007  (scaled Stream)]
 +
 
 +
Achtung: die Dateien aus dem WS 06/07 können fehlerhaft sein! <br>
 
Bitte beachten Sie die [[Operations-Research-Wiki:Portal#Hinweise zur Vorlesungsaufzeichnung|Hinweise zum Betrachten]] der Vorlesung.
 
Bitte beachten Sie die [[Operations-Research-Wiki:Portal#Hinweise zur Vorlesungsaufzeichnung|Hinweise zum Betrachten]] der Vorlesung.

Version vom 31. Januar 2008, 18:15 Uhr

Idee

Die Idee dieses Verfahrens besteht darin, das Problem in mehrere Teilprobleme aufzuspalten. Die Teilprobleme sind einfacher als das ursprüngluiche Problem und daher schneller zu lösen. Die Lösung des Gesamtproblems ergibt sich aus den Lösungen der Teilprobleme.

Vorgehensweise

Vor dem ersten Schritt sollten alle Ungleichungen durch den jeweils größten gemeinsamen Teiler aller aij der Zeile geteilt werden. Dabei wird die rechte Seite auf den nächstkleineren ganzzahligen Wert gerundet.

Die beste bereits gefundene Lösung vor dem Durchführen des Algorithmus ist 0.

(1) Bounding

Es wird das kontinuierliche Optimum des aktuellen (Teil-)Problems ermittelt. Dieses Optimum stellt eine Obergrenze für alle ganzzahligen Lösungen dar, für dieses (Teil-)Problem gefunden werden kann.
  • Wenn diese Lösung ganzzahlig ist, hat man die optimale (Teil-)Lösung gefunden --> Schritt (3)
  • Falls das kontinuierliche Optimum größer ist als die beste bisher gefundene Lösung --> Schritt (2)
  • Falls das kontinuierliche Optimum kleiner ist als die beste bisher gefundene Lösung oder wenn keine Lösung gefunden werden kann, ist die optimale Lösung des Gesamtproblems nicht in diesem Teilproblem enthalten. Es wird mit der Berechnung eines anderen Teilproblems bei Schritt (1) weitergemacht.

(2) Branching

Das Problem wird anhand einer nicht.ganzzahligen Zeile in 2 Teilprobleme aufgespalten. Als Quellzeile wird wie beim Cutting-Plane Verfahren die Zeile mit dem größten nicht-ganzzahligen Anteil gewählt.
Die Quellezeile r hat die folgende Struktur: BVr + ∑(arj*NBVr) = br mit br ∉ Z.
br lässt sich in einen ganzzahligen gr und einen nicht-ganzzahligen Anteil fr aufteilen.
Da BVr ganzzahlig sein soll, muss entweder br + (1- fr) ≥ BVr oder br- fr ≤ BVr gelten.
Daher spaltet man das Problem in folgende Teilprobleme auf:
(a) Zusätzlich zu den bisherigen Restriktionen gilt die lower bound lr = br + (1- fr) ≥ BVr .
Daher muss BVr durch BV'r = BVr - lr erstetzt werden.
Die neue rechte Seite berechnet sich nach den Regeln für das Einrechen einer Untergrenze: brneu = br - lr
Die Quellzeile wird also durch BV'r + ∑ (arj*NBVr) = -(1- fr) ersetzt.
(b) Zusätzlich zu den bisherigen Restriktionen gilt die upper bound ur = br - fr) ≤ BVr .
Daher muss BVr durch BVr‾ = ur - BVr erstetzt werden.
Die neue rechte Zeile berechnet sich nach den Regeln für das Einrechen einer Obergrenze: brneu=ur - br und alle arj wechseln das Vorzeichen.
Die Quellzeile wird also durch BVr‾ - ∑ (arj*NBVr) = - fr erstetzt.
Für jedes dieser Teilprobleme muss nun versucht werden die ganzzahlige Optimallösung zu finden, in dem man auf jedes diesen Algorithmus anwendet, also zu Schritt (1) geht. Mit welchem der Teilprobleme man beginnt, ist egal.

(3) Ist die gefundene Teillösung besser als die beste bisher gefundene Lösung, so ist sie die neue beste bisher gefundene Lösung.

  • Sind noch unbearbeitete Teilprobleme vorhanden, wird deren bei Schritt (1) beginnend berechnet.
  • Sind alle Teilprobleme gelöst ist die aktuelle beste bisher gefundene Lösung die Optimallösung des Gesamtproblems.


Beispiel

max G = 5x1 + 2x2
u.d. NB 4xi-2x2 ≤17
2x1+8x2 ≤31
x1,x2 ≥0 & ganzzahlig

(0) wenn möglich Runden

1.NB: 4xi-2x2 ≤17 |:2
(Pfeil) 2xi-1x2 ≤8
2.NB: 2x1+8x2 ≤31 |:2
(Pfeil) 1x1+4x2 ≤31

(1) Simplex-Tableau erstellen und kontinuierliches Optimum berechnen

Anfangstableau:

x1 x2
z -5 -2 0
y1 2 -1 8
y2 1 4 15

Abb 1: Anfangstableau

Nach 2 Simplex-Iteration kommt man auf folgendes kontinuierliche Optimum :

y1 y2
z 2 1 31
x1 4/9 1/9 47/9
x2 -1/9 2/9 22/9

Abb 2: kontinuierliches Optimum

Die Lösung ist nicht ganzzahlig --> Schritt (2)

(2) Als Quellzeile für das Branchen wählt man die Zeile von x2.

Quellzeile: x2 + y1* -1/9 +y2* 2/9 = 22/9

(a) zusätzlich zu den bisherigen Restriktionen gilt die lower bound x2 ≥ 3 

x2 muss durch x2' ersetzt werden

neue Zeile von x2: x2' - 1/9*y1 + 2/9*y2 = -5/9

Resultierendes Simplex-Tableau:

y1 y2
z 2 1 31
x1 4/9 1/9 47/9
x2' -1/9 2/9 -5/9

Abb 3: Tableau 1a

(b) zusätzlich zu den bisherigen Restriktionen gilt die upper bound x2 ≤ 2 

x2 muss durch x2‾ ersetzt werden

neue Zeile von x2: /overline{x}2+1/9*y1-2/9*y2 = -4/9

Resultierendes Simplex-Tableau:

y1 y2
z 2 1 31
x1 4/9 1/9 47/9
x2‾ 1/9 -2/9 -4/9

Abb 4: Tableau 1b


Die beiden Tableaus haben negative Elemente auf der rechten Seite --> Schritt (1): Optimum berechnen


Man erhält die folgenden beiden Optimallösungen:

x2' y2
z 18 5 21
x1 4 1 3
y1 -9 -2 5

Abb 5: Optimallösung zu Tableau 1a


y1' x2‾
z 5/2 9/2 29
x1 1/2 1/2 5
y2 1/2 -9/2 2

Abb 6: Optimallösung zu Tableau 1b


Beide Tableaus sind ganzzahlig --> keine weitere Anwendung des Algorithmus mötig.

Der Zielfunktionswert des Tablaus 1b (29) ist größer als der des Tableaus 1a (21)

--> Das Tableau 1b stellt die Optimallösung dar.




Vorlesung

Sie können Sich zu diesem Themengebiet eine Vorlesung ansehen.

Wintersemester 2007/2008

[[media:Slides_07_BranchBound.wmv | Vorlesungsmitschnitt zum Thema Branch&Bound

Wintersemester 2006/2007

  • 09.01.2007
  • 16.01.2007

Achtung: die Dateien aus dem WS 06/07 können fehlerhaft sein!
Bitte beachten Sie die Hinweise zum Betrachten der Vorlesung.

Von „https://www.wiwi.uni-kl.de/bisor-orwiki/index.php?title=Branch_%26_Bound&oldid=1686“