Ganzzahlige Optimierung

Operations Research 2

Das Kapitel Ganzzahlige Optimierung in unserem Online-Kurs Operations Research 2 besteht aus folgenden Inhalten:

1. Ganzzahlige Optimierung

   Ganzzahlige Optimierung

   

   ... Lösungen resultieren. Hierzu wird die ganzzahlige Optimierung herangezogen. Diese schließt nicht-ganzzahlige Lösungen aus und lässt demnach nur ganzzahlige Lösungen zu. Der Unterscheid zur linearen Optimierung besteht darin, dass innerhalb der Nebenbedingungen die Zusatzbedingungen der Ganzzahligkeit für alle oder einige Variablen eingeführt wird. Es ist auch möglich, dass die Variablen nur die Werte 0 und 1 annehmen dürfen. Will ein Unternehmen ...

2. Grafisches Verfahren

   Ganzzahlige Optimierung > Grafisches Verfahren

   

   Das im ersten Kapitel Wiederholung OR 1 eingeführte lineare Programm und die dort vorgestellte grafische Lösung des Maximierungsproblems hatte eine ganzzahlige Lösung zum Ergebnis. Dies ist allerdings nicht immer gegeben, denn häufig werden bei linearen Programme nicht ganzzahlige Lösungen ermittelt. In diesem Abschnitt soll die grafische Lösung eines Maximierungsproblems im Hinblick auf die Ganzzahligkeitsbedingung aufgezeigt werden.Die grafischen Lösung von linearen ...

3. Verfahren von Gomory

   Ganzzahlige Optimierung > Verfahren von Gomory

   

   ... das Einfügen der Schlupfvariablen um das ganzzahlige Optimierungsproblem in die Normalform zu überführen:Das Video wird geladen...(Verfahren von Gomory - Schlupfvariablen einfügen (2 von 7)) 3. Auswahl der Pivotspalte und Pivotzeile:Das Video wird geladen...(Verfahren von Gomory - 1. primaler Simplexschritt (3 von 7)) 4. Der erste primale Simplexschritt wird durchgeführt:Das Video wird geladen...(Verfahren von Gomory - Simplexschritt (4 von 7)) 5. Der zweite ...

4. Branch-and-Bound-Verfahren

   Ganzzahlige Optimierung > Branch-and-Bound-Verfahren

   

   Das Branch-and-Bound Verfahren zählt zu den Entscheidungsbaumverfahren und wird zur Lösung von ganzzahligen Optimierungsproblemen herangezogen. Das Branch-and-Bound-Verfahren untersucht nicht alle möglichen Lösungen bezüglich des Optimums, sondern verfolgt solche Äste nicht weiter die - hinsichtlich bestimmter Kriterien- das Optimum ausschließen.Das Branch-and-Bound-Verfahren ist im Hinblick auf das Gomory-Verfahren bei wenigen Variablen die günstigere Alternative, ...

5. Branch-and-Bound: Maximierungsprobleme

   Ganzzahlige Optimierung > Branch-and-Bound-Verfahren > Branch-and-Bound: Maximierungsprobleme

   

   In den folgenden Abschnitten werden zwei unterschiedliche Branch-and-Bound Verfahren zur Bestimmung der besten Lösung bei ganzzahligen Maximierungsproblemen aufgezeigt. Dabei werden die folgenden beiden Verfahren unterschieden:Branch-and-Bound am Ausgangsproblem. Hier wird von vornherein das ganzzahlige Maximierungsproblem (=Ausgangsproblem) betrachtet und anhand dessen die oberen und unteren Schranken aufgestellt.Branch-and-Bound am angepassten Problem. Hier wird zunächst für das ...

6. Branch-and-Bound am Maximierungsproblem

   Ganzzahlige Optimierung > Branch-and-Bound-Verfahren > Branch-and-Bound: Maximierungsprobleme > Branch-and-Bound am Maximierungsproblem

   

   Es wird zunächst das Branch-and-Bound Verfahren für ein Maximierungsproblem aufgezeigt, wobei das gegebene ganzzahlige Maximierungsproblem betrachtet wird. Es wird also bei dem in den nächsten 3 Abschnitten vorgestellten Branch-and-Bound Verfahren vorher keine Optimallösung ermittelt. Im Abschnitt Branch-and-Bound am angepassten Problem (optimale Lösung) wird dann gezeigt, wie das Branch-and-Bound Verfahren durchgeführt wird, wenn zunächst eine optimale Lösung ...

7. Festlegung der oberen/unteren Schranke, Prioritätenfestlegung

   Ganzzahlige Optimierung > Branch-and-Bound-Verfahren > Branch-and-Bound: Maximierungsprobleme > Branch-and-Bound am Maximierungsproblem > Festlegung der oberen/unteren Schranke, Prioritätenfestlegung

   

   ... aufgeführt.Hierzu wird das folgende ganzzahlige Optimierungsproblem herangezogen:$f(x_1, x_2) = 2x_1 +  x_2$    $\rightarrow$   max!u.d.N.(1) $3x_1 + 2x_2 \le 6 $   (2) $5x_1 + 2 x_2 \le 8$    $x_1, x_2 \ge 0$    und ganzzahligDas Problem liegt in der Standardform vor und die Ganzzahligkeitsbedingung ist gegeben. Obere Schranke bestimmenEs wird zunächst eine obere Schranke für beide Variablen bestimmt. Eine obere ...

8. Entscheidungsbaum für das Maximierungsproblem

   Ganzzahlige Optimierung > Branch-and-Bound-Verfahren > Branch-and-Bound: Maximierungsprobleme > Branch-and-Bound am Maximierungsproblem > Entscheidungsbaum für das Maximierungsproblem

   

   Nachdem die Vorüberlegungen getroffen worden sind, wird als nächstes der Entscheidungsbaum aufgestellt. Dabei wird die obere Ebene mit der Variable $x_1$ belegt. Das bedeutet, dass die Variable $x_1$ nur in der 1. Ebene variiert wird. Für die weitere Ebene wird $x_1$ konstant gehalten und nur $x_2$ variiert. Die Aufstellung des Entscheidungsbaums erfolgt für das folgenden im vorherigen Abschnitt aufgeführte ganzzahlige Maximierungsproblem:$f(x_1, x_2) = 2x_1 +  x_2$ ...

9. Beispiel: Branch and Bound am Maximierungsproblem

   Ganzzahlige Optimierung > Branch-and-Bound-Verfahren > Branch-and-Bound: Maximierungsprobleme > Branch-and-Bound am Maximierungsproblem > Beispiel: Branch and Bound am Maximierungsproblem

   

   In diesem Abschnitt soll das Branch-and-Bound-Verfahren am Ausgangsproblem anhand eines ganzzahligen Maximierungsproblems dargestellt werden, welches bereits im Abschnitt Verfahren von Gomory aufgeführt worden ist.Gegeben sei das folgende ganzzahlige Maximierungsproblem:$f(x_1, x_2) = x_1 +  2x_2$    $\rightarrow$   max!u.d.N.(1) $6x_1 + 5x_2 \le 30$   (2) $4x_1 + 9 x_2 \le 36$    Obere Schranken bestimmenEs wird zunächst die obere Schranke der ...

10. Branch-and-Bound am Maximierungsproblem (optimale Lösung)

    Ganzzahlige Optimierung > Branch-and-Bound-Verfahren > Branch-and-Bound: Maximierungsprobleme > Branch-and-Bound am Maximierungsproblem (optimale Lösung)

    

    In diesem Abschnitt wird das Branch-and-Bound Verfahren für ein ganzzahliges Maximierungsproblem dargestellt. Die obere Schranke wird für das hier vorgestellte Verfahren aber nicht anhand des Ausgangsproblems $P_0$ ermittelt, sondern anhand des angepassten Problems $P'_0$. Für das angepasste Problem wird die Ganzzahligkeitsbedingung vernachlässigt und zunächst mittels Simplex-Algorithmus (oder grafisch) für jeden Ast und seine Teilprobleme $P_i$ die optimale Lösung ...

11. Beispiel: Branch and Bound am Maximierungsproblem (optimale Lösung)

    Ganzzahlige Optimierung > Branch-and-Bound-Verfahren > Branch-and-Bound: Maximierungsprobleme > Branch-and-Bound am Maximierungsproblem (optimale Lösung) > Beispiel: Branch and Bound am Maximierungsproblem (optimale Lösung)

    

    Das Branch-and-Bound-Verfahren am angepassten Problem soll in diesem Abschnitt anhand des Maximierungsproblems aus dem Abschnitt: Ganzzahlige lineare Optimierung veranschaulicht werden.Gegeben sei das folgenden Ausgangsproblem $P_0$:$f(x_1, x_2) = 2x_1 +  x_2$    $\rightarrow$   max!u.d.N.(1) $3x_1 + 2x_2 \le 6 $   (2) $5x_1 + 2 x_2 \le 8$    $x_1, x_2 \ge 0$    und ganzzahligUntere SchrankeDie untere globale Schranke liegt ...

12. Branch-and-Bound: Minimierungsprobleme

    Ganzzahlige Optimierung > Branch-and-Bound-Verfahren > Branch-and-Bound: Minimierungsprobleme

    

    In den folgenden Abschnitten werden zwei unterschiedliche Branch-and-Bound Verfahren zur Bestimmung der besten Lösung bei ganzzahligen Minimierungsproblemen aufgezeigt. Dabei werden die folgenden beiden Verfahren unterschieden:Branch-and-Bound am Ausgangsproblem. Hier wird von vornherein das ganzzahlige Minimierungsproblem (=Ausgangsproblem) betrachtet und anhand dessen die oberen und unteren Schranken aufgestellt.Branch-and-Bound am angepassten Problem. Hier wird zunächst für das ...

13. Branch-and-Bound am Minimierungsproblem

    Ganzzahlige Optimierung > Branch-and-Bound-Verfahren > Branch-and-Bound: Minimierungsprobleme > Branch-and-Bound am Minimierungsproblem

    

    Es wird zunächst das Branch-and-Bound Verfahren für ein Minimierungsproblem aufgezeigt, wobei das gegebene ganzzahlige Minimierungsproblem betrachtet wird. Es wird also bei dem in den nächsten 3 Abschnitten vorgestellten Branch-and-Bound Verfahren vorher keine Optimallösung ermittelt. Im Abschnitt Branch-and-Bound am angepassten Problem (optimale Lösung) wird dann gezeigt, wie das Branch-and-Bound Verfahren durchgeführt wird, wenn zunächst eine optimale ...

14. Festlegung der unteren/oberen Schranke, Prioritätenfestlegung

    Ganzzahlige Optimierung > Branch-and-Bound-Verfahren > Branch-and-Bound: Minimierungsprobleme > Branch-and-Bound am Minimierungsproblem > Festlegung der unteren/oberen Schranke, Prioritätenfestlegung

    

    Es wird zunächst das Branch-and-Bound Verfahren für ein Minimierungsproblem betrachtet. Dabei wird von dem gegebenen ganzzahligen Minimierungsproblem ausgegangen. Das ganzzahlige Minimierungsproblem muss in der folgenden Form vorliegen oder in diese Form überführt werden:Die Voraussetzungen für das Branch-and-Bound -Verfahren eines Minimierungsproblems seien im Folgenden aufgeführt:- Das Problem muss in der folgenden Form vorliegen: Minimierungsproblem, Nichtnegativitätsbedingung- ...

15. Entscheidungsbaum für das Minimierungsproblem

    Ganzzahlige Optimierung > Branch-and-Bound-Verfahren > Branch-and-Bound: Minimierungsprobleme > Branch-and-Bound am Minimierungsproblem > Entscheidungsbaum für das Minimierungsproblem

    

    Nachdem die Vorüberlegungen getroffen worden sind, wird als nächstes der Entscheidungsbaum aufgestellt. Dabei wird die obere Ebene mit der Variable $x_2$ belegt. Das bedeutet, dass die Variable $x_2$ nur in der 1. Ebene variiert wird. Für die untere Ebene wird $x_2$ konstant gehalten und nur $x_1$ variiert. Die Aufstellung des Entscheidungsbaums erfolgt für das folgenden im vorherigen Abschnitt aufgeführte ganzzahlige Minimierungsproblem:$f(x_1, x_2) = 2x_1 +  x_2$ ...

16. Beispiel: Branch and Bound am Minimierungsproblem

    Ganzzahlige Optimierung > Branch-and-Bound-Verfahren > Branch-and-Bound: Minimierungsprobleme > Branch-and-Bound am Minimierungsproblem > Beispiel: Branch and Bound am Minimierungsproblem

    

    XXXXXDie Aufstellung des Entscheidungsbaums soll anhand des folgenden Beispiels dargestellt werden. Es sei das folgende ganzzahlige Maximierungsproblem gegeben:$f(x_1, x_2) = 10 - x_1 -  2x_2$    $\rightarrow$   min!u.d.N.(1) $2x_1 +6 x_2 \le 15 $   (2) $6x_1 + 4 x_2 \le 21$    $x_1, x_2 \ge 0$    und ganzzahligEs ist sinnvoll das hier gegebene Problem in ein Maximierungsproblem umzuwandeln, da die Nebenbedingungen bereits alle $\le$ enthalten. ...

17. Branch-and-Bound am Minimierungsproblem (optimale Lösung)

    Ganzzahlige Optimierung > Branch-and-Bound-Verfahren > Branch-and-Bound: Minimierungsprobleme > Branch-and-Bound am Minimierungsproblem (optimale Lösung)

    

    Es soll im folgenden das Branch-and-Bound Verfahren anhand eines ganzzahligen Minimierungsproblems dargestellt werden. Es wird hier zur Festlegung der Schranken nicht das Ausgangsproblem $P_0$ betrachtet, sondern das angepasste Problem $P'_0$. Dazu wird für das gegebene ganzzahlige Minimierungsproblem die Ganzzahligkeitsbedingung vernachlässigt und zunächst mittels Simplex-Algorithmus oder grafisch die optimale Lösung für jedes Teilproblem $P_i$ ermittelt. Diese ermittelte ...

18. Beispiel: Branch and Bound am Minimierungsproblem (optimale Lösung) 1

    Ganzzahlige Optimierung > Branch-and-Bound-Verfahren > Branch-and-Bound: Minimierungsprobleme > Branch-and-Bound am Minimierungsproblem (optimale Lösung) > Beispiel: Branch and Bound am Minimierungsproblem (optimale Lösung) 1

    

    Gegeben sei das folgende Ausgangsproblem $P_0$:$f(x_1, x_2) = 2x_1 +  x_2$    $\rightarrow$   min!u.d.N.(1) $4x_1 +4 x_2 \ge 10 $   (2) $2x_1 +11 x_2 \ge 11$    (3) $-4x_1 + 2x_2  \le 1$$x_1, x_2 \ge 0$    und ganzzahligObere SchrankeDie obere globale Schranke liegt in diesem Fall bei einem Zielfunktionswert von $\underline{F} = \infty$. Der Zielfunktionswert soll zwar minimiert werden, aber eine genaue obere Schranke kann nicht gegebenen ...

19. Beispiel: Branch and Bound am Minimierungsproblem (optimale Lösung) 2

    Ganzzahlige Optimierung > Branch-and-Bound-Verfahren > Branch-and-Bound: Minimierungsprobleme > Branch-and-Bound am Minimierungsproblem (optimale Lösung) > Beispiel: Branch and Bound am Minimierungsproblem (optimale Lösung) 2

    

    ... nun das Branch-and-Bound-Verfahren für das ganzzahlige Optimierungsproblem angewandt. Nach Anwendung des Simplexalgorithmus auf das angepasste Problem $P'_0$ resultierte die folgende optimale Lösung:$x_1 = 0,67$ und $x_2 = 1,83$ mit dem Zielfunktionswert:$F = 3,167$.Die untere Schranke für das Problem $P_0$ ist dabei die optimale Lösung des angepassten Problems $P'_0$:$\underline{F}_0 = 3,167$Diese untere Schranke resultierte für nichtganzzahlige Variablen und ist deshalb ...

20. Beispiel: Branch and Bound am Minimierungsproblem (optimale Lösung) 3

    Ganzzahlige Optimierung > Branch-and-Bound-Verfahren > Branch-and-Bound: Minimierungsprobleme > Branch-and-Bound am Minimierungsproblem (optimale Lösung) > Beispiel: Branch and Bound am Minimierungsproblem (optimale Lösung) 3

    

    Für das grafische Verfahren wird das Ausgangsproblem herangezogen:$f(x_1, x_2) = 2x_1 +  x_2$    $\rightarrow$   min!u.d.N.(1) $4x_1 +4 x_2 \ge 10 $   (2) $2x_1 +11 x_2 \ge 11$    (3) $-4x_1 + 2x_2  \le 1$$x_1, x_2 \ge 0$    und ganzzahligDie Grafik für das Ausgangsproblem ergibt sich wie folgt:In der obigen Grafik sind die Restriktionen (1) bis (3) eingezeichnet. Die Pfeile geben an, in welche Richtung die Restriktionen gelten. ...

21. Branch-and-Bound: Knapsack-Problem

    Ganzzahlige Optimierung > Branch-and-Bound-Verfahren > Branch-and-Bound: Knapsack-Problem

    

    Bei einem Knapsack-Problem (auch: Rucksack-Problem) soll ein knappes Gut optimal verteilt werden. Knappsack-Probleme haben häufig nur eine einzige $\le$-Nebenbedingung gegeben, in welcher sich alle Entscheidungsvariablen befinden. Die Anzahl der Entscheidungsvariablen ist häufig sehr hoch. Ein Knapsack-Problem lässt sich auf ein binäres Problem zurückführen. In diesem Abschnitt soll gezeigt werden, wie man ein solches Problem mittels Branch-and-Bound-Verfahren lösen ...

22. Branch-and-Bound: Knapsack-Problem (Alternative)

    Ganzzahlige Optimierung > Branch-and-Bound-Verfahren > Branch-and-Bound: Knapsack-Problem (Alternative)

    

    In diesem Abschnitt soll eine alternative Vorgehensweise für das Branch-and-Bound Verfahren anhand eines Knapsack-Problems dargestellt werden. Gegeben sei das folgende Knapsack-Problem:$F(x) = 14x_1 + 20x_2 + 18x_3 + 26x_4  $\rightarrow $ max!u.d.N.$8x_1 + 8x_2 + 6x_3 + 6x_4 \le 14$$ x_j =\left\{\begin{array}{cl} 1 \\ 0 \end{array}\right. $Es wird zunächst die Prioritätenreihenfolge festgelegt.PrioritätenreihenfolgeBevor mit der Aufstellung des Entscheidungsbaumes begonnen ...