Grundlagen des Operations Research 1

Operations Research 2

Das Kapitel Grundlagen des Operations Research 1 in unserem Online-Kurs Operations Research 2 besteht aus folgenden Inhalten:

1. Grundlagen des Operations Research 1

   Grundlagen des Operations Research 1

   

   In diesem Kapitel werden zunächst die wichtigstens für die folgenden Kapitel benötigten Verfahren aus dem Online-Kurs Operations Research 1 aufgeführt. Hierzu zählen vor allem der primale bzw. der duale Simplexalgorithmus um eine optimale Lösung bzw. eine zulässige Lösung zu erhalten. Die Anwendung dieser ist Voraussetzung für zum Beispiel das Gomory-Verfahren und für die Anwendung des Branch-and-Bound Verfahrens (zulässige Ausgangsl&oum...

2. Operations Research 2: Überblick

   Grundlagen des Operations Research 1 > Operations Research 2: Überblick

   

   ... 2.Der Kurs beginnt zunächst mit den Grundlagen des Operations Research 1. Hier werden die wichtigsten Themen der linearen Programmierung, wie zum Beispiel der primale und duale Simplexalgorithmus, zusammengefasst. Das 2. Kapitel beschäftigt sich mit der ganzzahligen Optimierung. Ziel der ganzzahligen Optimierung ist die Bestimmung einer besten Lösung, welche nur ganzzahlige Werte enthält. Es werden unterschiedliche Verfahren wie das grafische Verfahren, das ...

3. Definition: Lineares Programm

   Grundlagen des Operations Research 1 > Definition: Lineares Programm

   

   Ein lineares Programm besteht zunächst einmal aus einer zu maximierenden bzw. zu minimierenden linearen Zielfunktion:$f(x_1, x_2, ... , x_n) = c_1 x_1 + c_2 x_2 + ... c_3 x_n = \sum_{j = 1}^n c_j x_j$    $\rightarrow $   max / minDie in der Zielfunktion auftretenden Variablen $(x_1, x_2, ..., x_n)$ nennt man Entscheidungsvariablen.Es müssen zusätzlich die linearen Nebenbedingungen (=Restriktionen) berücksichtigt werden:$a_{ij} x_j + ... + a_{in} x_n ...

4. Standardform: Maximierungsproblem

   Grundlagen des Operations Research 1 > Standardform: Maximierungsproblem

   

   Im vorangegangenen Abschnitt ist zunächst das allgemeine lineare Programm aufgestellt worden. Hierbei sind alle Nebenbedingungen (mit Ungleichungen $\le$, $\ge$ sowie ohne Ungleichungen $=$) berücksichtigt worden. Bei der Lösung von linearen Optimierungsmodellen, muss dieses allerdings in Standardform gegegeben sein. Von der Standardform ist die Rede, wenn ein Maximierungsproblem vorliegt (Maximierung der Zielfunktion), die Nebenbedingungen die Ungleichungen $\le$ enthalten ...

5. Grafische Lösung des Maximierungsproblems

   Grundlagen des Operations Research 1 > Standardform: Maximierungsproblem > Grafische Lösung des Maximierungsproblems

   

   In diesem Abschnitt soll aufgezeigt werden, wie man ein lineares Optimierungsproblem grafisch löst. Dazu muss die Standardform         maximiere $f(x) = c^Tx$u.d.N.                      $Ax \le b$                      $x \ge 0$gegeben sein. Die grafische Lösung ist für Optimierungsprobleme mit zwei Entscheidungsvariablen geeignet. Es wird das folgende ...

6. Primaler Simplexalgorithmus

   Grundlagen des Operations Research 1 > Primaler Simplexalgorithmus

   

   Voraussetzung für die Anwendung des primalen Simplex-Verfahrens:Es muss die Standardform vorliegen (Maximierungsproblem, Kleiner/Gleich-Nebenbedingung, Nichtnegativitätsbedingung).Die Standardform muss dann in die Normalform überführt werden (Gleichheitsbedingung) mittels Einführung von Schlupfvariablen.Es liegen keine negativen Koeffizienten auf der Rechten-Seite der Nebenbedingungen vor ($b_i \ge 0$). Das Problem ist also in kanonischer Form gegeben.Der ...

7. Lösung des Maximierungsproblems mittels primalen Simplexalgorithmus

   Grundlagen des Operations Research 1 > Primaler Simplexalgorithmus > Lösung des Maximierungsproblems mittels primalen Simplexalgorithmus

   

   In diesem Abschnitt wird das im vorherigen Abschnitt grafisch gelöste Optimierungsproblem mittels primalen Simplexverfahren gelöst. Es müssen folgenden Voraussetzungen vorliegen, damit das primale Simplexverfahren angwandt werden kann:Es muss die Standardform vorliegen (Maximierungsproblem, Kleiner/Gleich-Nebenbedingung, Nichtnegativitätsbedingung)Die Standardform muss dann in die Normalform überführt werden (Gleichheitsbedingung) mittels Einführung von Schlupfvariablen.Es ...

8. Dualer Simplexalgorithmus

   Grundlagen des Operations Research 1 > Dualer Simplexalgorithmus

   

   Voraussetzung für die Anwendung des dualen Simplex-Verfahrens:Es muss die Standardform vorliegen (Maximierungsproblem, Kleiner/Gleich-Nebenbedingung, Nichtnegativitätsbedingung)Die Standardform muss dann in die Normalform überführt werden (Gleichheitsbedingung) mittels Einführung von Schlupfvariablen.Es liegen negative Koeffizienten auf der Rechten-Seite der Nebenbedingungen vor ($b_i \le 0$).Das duale Simplexverfahren wird angewandt, wenn das Optimierungsproblem ...

9. Umformung in die Standardform

   Grundlagen des Operations Research 1 > Umformung in die Standardform

   

   Für die in den vorherigen beiden Abschnitten aufgeführten Simplexalgorithmen wird die Standardform benötigt. In diesem Abschnitt wird aufgezeigt, wie man ein gegebenes Optimierungsproblem in Standardform umformen kann. Es existieren vier mögliche Gründe für die Abweichung von der StandardformVariablen ohne Nichtnegativitätsbedingung,Gleichheitsbedingungen statt Ungleichheitsbedingungen undGrößer/gleich-Ungleichungen statt Kleiner/gleich-Ungleichungen.Die ...

10. Umformung in die Normalform

    Grundlagen des Operations Research 1 > Umformung in die Normalform

    

    Die Normalform lässt sich ganz einfach aus der Standardform (siehe vorherige Kapitel) ableiten und wird zum Beispiel für die Anwendung der Simplex-Algorithmen benötigt. Die Normalform ist wie folgt definiert:             maximiere    $f(x_1, x_2, ... , x_n) = c x_1 + c x_2 + ... c x_n = \sum_{j = 1}^n c_j x_j$ u.d.N (unter den Nebenbedingungen)$a_{ij} x_j + ... + a_{in} x_n = b_i$        $i = ...