Johnson-Algorithmus

In diesem Kurstext behandeln wir den Algorithmus von Prim, welcher einen minimalen Spannbaum für ungerichtete, kantengewichtete und zusammenhängend endlichen Graphen ermittelt.Beim Prim-Algorithmus wird von einem zufälligen Punkt ausgehend jeweils die nächste Kante mit dem niedrigsten Kantengewicht hinzugefügt, bis ein minimaler Spannbaum entsteht.Der Prim-Algorithmus gehört zu den Greedy Algorithmen der Graphentheorie.Greedy-Algorithmen zeichnen sich dadurch aus, dass ...

Wir wollen im weiteren die sehr einfachen Greedy-Algorithmen (auch: gierige Algorithmen) betrachten. Bei Greedy-Algorithmen wird sukzessiv derjenige Folgezustand gewählt, der zum Zeitpunkt der Auswahl das beste Ergebnis verspricht. Der Greedy-Algorithmus betrachtet also die aktuelle Situation und wählt aus dieser die beste Lösung aus. Dabei werden voherige und spätere Entscheidungen nicht berücksichtigt. Der Vorteil beim Greedy-Algorithmus ist, dass er schnell ...

In diesem Kurstext behandeln wir den Algorithmus von Kruskal, welcher einen minimalen Spannbaum für ungerichtete,kantengewichtete und zusammenhängend endlichen Graphen ermittelt.Der Kurskal-Algorithmus gehört zu den Greedy Algorithmen der Graphentheorie.Greedy-Algorithmen zeichnen sich dadurch aus, dass sie schrittweise denjengen Folgezustand auswählen, der zum Zeitpunkt der Wahl das beste Ergebnis verspricht.Der Kruskal-Algorithmus wurde 1956 in der Zeitschrift ...

Der Algorithmus von Dijkstra löst das Problem der kürzesten Wege für einen gegebenen Startknoten. Der Algorithmus berechnet einen kürzesten Weg zwischen dem gegebenen Startknoten und den anderen Knoten in einem kantengewichteten, gerichteten Graphen.Der Dijkstra-Algorithmus gehört zu den Greedy Algorithmen der Graphentheorie.Greedy-Algorithmen zeichnen sich dadurch aus, dass sie schrittweise denjengen Folgezustand auswählen, der zum Zeitpunkt ...

Das Optimierungsproblem aus dem Abschnitt Beispiel: Vielzahl an beschränkten Variablen, welches mit dem Algorithmus für die oberen Schranken gelöst worden ist, kann auch einfach und schnell mit dem revidierten Simplexalgorithmus gelöst werden. Gegeben sei das folgende Optimierungsproblem:$f(x_1, x_2, x_3, x_4) = 4x_1 + 6x_2 + 3x_3 + x_4$   $\rightarrow$  max!u.d.N.$x_1 + 2x_2 + 4x_3 + x_4 \le 80$$2x_1 + x_2 + x_3           \le 60$$x_1 \le ...

Das Nord-West-Ecken-Verfahren führt zu einer zulässigen Ausgangslösung für Transportprobleme. Hierbei wird die Mengenmatrix herangezogen. Das Ziel dieses Verfahrens ist es, die Angebotsmenge so auf die Warenhäuser zu verteilen, dass deren Nachfrage komplett abgedeckt wird. Die Kosten des Transports werden hierbei nicht berücksichtigt. Die Minimierung der Kosten erfolgt dann später bei den Optimierungsverfahren. Die Mengenmatrix für das Beispiel sieht wie folgt ...

In diesem Abschnitt wird der FIFO-Algorithmus zur Bestimmung von kürzesten Wegen in Graphen ausführlich behandelt.Gegeben sei ein Diagraph mit $n$ Knoten und einem Startknoten. Es werden alle kürzesten Wege zwischen dem Startknoten und allen anderen Knoten gesucht.FIFO-AlgorithmusGegeben sei ein Diagraph mit $n$ Knoten und einem Startknoten $a$. Alle Pfeile seien mit $k(i,j)$ bewertet. Gesucht wird der kürzeste Weg zwischen dem Startknoten und allen anderen Knoten des Diagraphen.Sei ...

In diesem Abschnitt sollen kürzesten Wege in Graphen bestimmt werden. Der Algorithmus von Dijkstra und der Fifo-Algorithmus bestimmen die kürzester Entfernung von einem vorgegebenen Startknoten zu allen anderen Knoten des Graphen.  In den folgenden Abschnitten werden die beiden Verfahren ausführlich behandelt. Dabei beschränken sich die folgenden Ausführungen auf Diagraphen.Diagraphen enthalten keine Schlingen und keine parallelen Kanten bzw. Pfeile.

In den folgenden Abschnitten wird ausführlich beschrieben, wie das Simplex-Verfahren angewandt wird. Der Simplex-Algorithmus dient der Bestimmung der Entscheidungsvariablen eines linearen Optimierungsproblems unter Berücksichtigung von Nebenbedingungen. Damit das Simlpex-Verfahren angwandt werden kann, muss das lineare Optimierungsproblem in Normalform vorliegen (siehe vorherigen Abschnitt).Das Simplex-Verfahren untersucht den Rand des zulässigen Bereichs (siehe grafische Lösung) ...

Herzlich Willkommen in Ihrem Kurs Operations Research. Wir freuen uns, dass Sie sich dazu entschlossen haben sich mit Hilfe dieses Kurses in die sehr interessante, jedoch nicht ganz einfache Thematik von Optimierungsmodellen einzuarbeiten. Der Kurs beginnt mit der linearen Programmierung. Innerhalb dieses Kapitels werden Maximierungs- und Minimierungsprobleme behandelt und Ihnen gezeigt wie diese mittels primalem und dualem Simplex-Algorithmus sowie der Big-M Methode gelöst werden können. Es ...

In den folgenden Abschnitten wird gezeigt, wie man das primale Simplexverfahren anwendet. Es muss aber zunächst festgelegt werden, wann der primale Simplex-Algorithmus angewandt werden kann.Vorausetzung für die Anwendung des primalen Simplex-VerfahrensEs muss die Standardform vorliegen (Maximierungsproblem, Kleiner/Gleich-Nebenbedingung, Nichtnegativitätsbedingung)Die Standardform muss dann in die Normalform überführt werden (Gleichheitsbedingung) mittels Einführung ...

In diesem Abschnitt wird der revidierte Simplexalgorithmus aufgezeigt. Dieser wird angewandt, wenn die Anzahl der Variablen in einem linearen Optimierungsproblem wesentlich größer ist, als die Anzahl der Nebenbedingungen. Es wird im folgenden der revidierte Simplexalgorithmus für ein in kanonischer Form (Maximierungsproblem, kleiner/gleich-Nebenbedingungen, Nichtnegativitätsbedingung, positive Werte der rechten Seite) vorliegendes Problem aufgezeigt.Gegeben sei das folgende lineare ...

Zu den weiteren Eröffnungsverfahren zählen die Rangfolgeverfahren (Spaltenfolgeverfahren, Zeilenfolgeverfahren, Matrixminimumverfahren). Diese Verfahren haben das Ziel eine zulässige Ausgangslösung für Transportprobleme zu finden.Bei diesen Verfahren wird die Mengenmatrix benötigt. In die Mengenmatrix werden am oberen rechten Rand die Kosten eingetragen. Im Gegensatz zum Nord-West-Ecken-Verfahren werden die Kosten für diese Verfahren benötigt. Sie sind also ...

Bei der linearen Programmierung geht es darum eine Zielfunktion unter Einhaltung von Nebenbedingungen zu maximieren (Gewinnfunktion) bzw. zu minimieren (Kostenfunktion). Möchte ein Unternehmen z.B. die optimale Menge verschiedener Produkte mit dem Ziel der Gewinnmaximierung bestimmen, so müssen Kapazitätsbeschränkungen und Absatzbedingungen berücksichtigt werden. Angenommen ein Transportunternehmen will die Anzahl der transportierten Güter maximieren, jedoch beschränken ...

Es ist immer sinnvoll ein Optimierungsproblem in Standardform (Maximierungsproblem, kleiner/gleich Ungleichungen, Nichtnegativitätsbedingung) vorliegen zu haben. Die grafische Lösung kann in diesem Fall dann so vorgenommen werden, wie es in den vorherigen Abschnitten gezeigt wurde. Aber auch für die Aufstellung des in den folgenden Abschnitten aufgeführten Simplex-Algorithmus ist das Vorliegen der Standardform sinnvoll. In diesem Abschnitt wird ausführlich beschrieben, wie ...

In diesem Abschnitt soll das Spaltenfolgeverfahren aufgezeigt werden. Das Spaltenfolgeverfahren ist ein Eröffnungsverfahren für Transportprobleme und hat eine zulässige Ausgangslösung als Ergebnis. Die Vorgehensweise sei im Folgenden beschrieben:SpaltenfolgeverfahrenZu Beginn des Verfahrens sind alle Zeilen unmarkiert. Die Iteration erfolgt von $j = 1, .., n$ ($j$ = Spalte).1. Es wird das kleinste Element der Spalte $j$ ausgewählt. Bei mehreren gleich kleinen Elemente, wird ...

In diesem Abschnitt soll das Zeilenfolgeverfahren aufgezeigt werden.Zeilenfolgeverfahren - DefinitionDas Zeilenfolgeverfahren ist ein Eröffnungsverfahren für Transportprobleme und hat eine zulässige Ausgangslösung zum Ergebnis. Die Vorgehensweise sei im Folgenden beschrieben:ZeilenfolgeverfahrenZu Beginn des Verfahrens sind alle Spalten unmarkiert. Die Iteration erfolgt von $i = 1, .., n$ ($i$ = Zeile).1. Es wird das kleinste Element der Zeile $i$ ausgewählt. Bei mehreren ...

Der Johnson-Algorithmus liefert für den 2-Maschinen-Fall eine optimale Reihenfolge der jeweiligen Aufträge, die beide Maschinen in derselben Reihenfolgen durchlaufen. Die Bestimmung der optimale Reihenfolge der Aufträge erfolgt, indem die minimale Bearbeitungszeit als Entscheidungskriterium herangezogen wird. Dies soll anhand eines Beispiels dargestellt werden.Beispiel: Johnson-AlgorithmusGegeben seien folgende Aufträge $A_i$ und ihre Bearbeitungszeiten $p_{ij}$ ...

... und gezeigt werden, wie man diese mittels Johnson-Algorithmus für ein zwei-Maschinen-Fall lösen kann. 

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 ...

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 ...

... Im weiteren wird zur Veranschaulichung der Johnson-Algorithmus vorgestellt, bei dem die Bestimmung der optimalen Reihenfolge aufgrund der minimalen Zykluszeit erfolgt. 

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 ...

In diesem Abschnitt soll das Verfahren von Gomory aufgezeigt werden. Hierbei handelt es sich um ein Schnittebenenverfahren, bei welchem eine ganzzahlige Lösung des linearen Optimierungsproblems resultiert. In diesem Abschnitt soll aufgezeigt werden, wie ein lineares Maximierungsproblem mit Ganzzahligkeitsbedingung mittels primalen und dualen Simplexalgorithmus und dem Schnittebenenverfahren von Gomory gelöst werden kann. Der primale und duale Simplex-Algorithmus sollte bereits aus dem Kurs ...

Zwei Vektoren im R³Zwei Vektoren $\vec{a_1}$ und  $\vec{a_2}$ sind genau dann linear abhängig, wenn sich der Nullvektor durch eine Linearkombination der Vektoren erzeugen lässt:$\lambda_1 \vec{a_1} + \lambda_2 \vec{a_2} = \vec{0}$mit$\lambda_1, \lambda_2 \in \mathbb{R}$Nehmen beide $\lambda_i$ den Wert null an, so sind die Vektoren voneinander unabhängig. Demnach gilt für die lineare Abhängigkeit, dass nicht beide $\lambda_i$ den Wert null annehmen dürfen.Sinnvoll ...

Eine Matrix $\ A $ mit  $n \ x \ n$  Elementen heißt invertierbar, wenn eine Matrix $\ A^{-1}$ mit  $(n \ x \ n)$  Elementen existiert, so dass gilt:$\ A^{-1} \cdot A = A \cdot A^{-1} = E_n $$\ A^{-1}$ ist die Inverse Matrix von A. Es existiert genau eine Inverse $A^{-1}$ zu einer invertierbaren Matrix $A$, deren Multiplikation mit $A$ die Einheitsmatrix $E_n$ ergibt. Erfüllt eine Matrix nicht diese Voraussetzung, so nennt man diese singulär. Zum ...

In diesem Abschnitt zeigen wir dir, wie eine Matrix diagonalisiert werden kann.Anwendungsbeispiel 3: Diagonalisierbarkeit$A = \begin{pmatrix} -2 & - 2 & 1 \\ 2 & 3 & -2 \\ 0 & 0 & -1 \end{pmatrix}$Ist die Matrix $A$ diagonalisierbar? Wenn ja, diagonalisiere die Matrix $A$ (ermittele die Diagonalmatrix $B$)!1. Schritt: Bestimmung des charakteristischen Polynoms$\chi_A(\lambda) = det(A - \lambda E) $$(A-\lambda E) = \begin{pmatrix} -2-\lambda & - 2 & 1 \\ 2 ...

In diesem Abschnitt überprüfen wir, ob die algebraische Vielfachheit mit der geometrischen Vielfachheit in der Beispielmatrix übereinstimmt.Anwendungsbeispiel 2: Diagonalisierbarkeit$A = \begin{pmatrix} 9 & 0 & -6 \\ 18 & 6 & 0 \\ 0 & 0 & 6 \end{pmatrix}$Ist die obige Matrix diagonalisierbar?1. Schritt: Berechnung des charakteristischen PolynomsBerechnung des charakteristischen Polynoms mittels Regel von Sarrus:$\chi_A(\lambda) = det(A-\lambda E) = \begin{vmatrix} ...

Definition: VektorraumDie Elemente eines Vektorraums $\mathcal V$ heißen Vektoren. Sie können addiert oder mit Skalaren multipliziert werden. Das Ergebnis ist wieder ein Vektor desselben Vektorraums $\mathcal V$.Addition von VektorenEine Bedingung ist, dass die Vektoren miteinander addiert werden können. Sind also $\vec{a_1}, \vec{a_2}, ... , \vec{a_n}$ Vektoren aus $\mathcal V$, also $\vec{a_1}, \vec{a_2}, ... , \vec{a_n} \in \mathcal V$, dann muss es möglich sein, ihre ...

Der Johnson-Algorithmus liefert für den 2-Maschinen-Fall eine optimale Reihenfolge der jeweiligen Aufträge, die beide Maschinen in derselben Reihenfolgen durchlaufen. Die Bestimmung der optimale Reihenfolge der Aufträge erfolgt, indem die minimale Bearbeitungszeit als Entscheidungskriterium herangezogen wird. Dies soll anhand eines Beispiels dargestellt werden.Beispiel: Johnson-AlgorithmusGegeben seien folgende Aufträge $A_i$ und ihre Bearbeitungszeiten $p_{ij}$ auf den Maschinen ...

... Im weiteren wird zur Veranschaulichung der Johnson-Algorithmus vorgestellt, bei dem die Bestimmung der optimalen Reihenfolge aufgrund der minimalen Zykluszeit erfolgt. 

In diesem Abschnitt behandeln wir als nächstes ein Beispiel zum Drehwinkelverfahren, in welchem neben den Knotendrehungen auch Knotenverschiebungen infolge Stabdrehungen berücksichtigt werden. Wir müssen in diesem Fall zusätzlich das Verschiebegleichgewicht berücksichtigen.Ziel ist die Ermittlung der Momentenlinie eines statisch unbestimmten Systems mittels Drehwinkelverfahren.Beispiel: Drehwinkelverfahren - Knotenverschiebungen infolge StabdrehungenDrehwinkelverfahren ...

Beim Schallemissionsverfahren wird die Eigenschaft genutzt, dass Gefügeänderungen im Bauteil oder Werkstoffen zu Schallemissionen führen. Diese Änderungen können infolge von mechanischen, chemischen oder thermischen Belastungen auftreten. Erfasst werden können: Risse im EntstehungsstadiumPlastische Verformungen,Versetzungsbewegungen, KorrosionReibungsvorgängeAblauf des SchallemissionsverfahrenIm Gegensatz zu Messungen mit Ultraschall, liegen die Schallwellen ...

In unserer bisherigen Betrachtung sind wir immer von analogen Reglern ausgegangen. Nun wollen wir jedoch dem Wirkprinzip von digitalen Reglern auf die Spur gehen. Wir erinnern uns:Das Wirkprinzip von analogen Reglern sieht vor, aus einem analogen Wert (vorliegende Regeldifferenz) auf analoge Weise die Reglerausgangsgröße zu bestimmen. Das entsprechende Regelkreisschema siehst du nachfolgend:Regelkreis mit analoger RegelungDass diese Variante funktioniert ist ja nicht bestreitbar, ...