imported>Sokrates 399: Typografie.

2026-02-02T09:17:40Z

Typografie.

Neue Seite

Die '''Zyklenmethode''' bzw. '''Stepping-Stone-Methode''' ist ein [[Numerische Mathematik|numerisches]] Verfahren, mit dem man (bei gegebener Ausgangs-[[Basislösung]]) ein Standard-[[Transportproblem]] lösen kann.

Es sind für ein Gut eine bestimmte Anzahl <math>n</math> Anbieter <math>A_i</math> <math>(i = 1, \dotsc , n)</math> und eine bestimmte Anzahl <math>m</math> Empfänger <math>B_j</math> <math>(j = 1, \dotsc , m)</math> gegeben. Im Standardfall ist die gesamte nachgefragte Menge gleich der gesamten angebotenen. Für den Transport einer Einheit <math>x_{ij}</math> zwischen <math>A_i</math> und <math>B_j</math> fallen Kosten <math>c_{ij}</math> an. Das Problem besteht darin, die von <math>A_i</math> nach <math>B_j</math> gelieferte Menge <math>x_{ij}</math> so festzulegen, dass die Gesamttransportkosten minimiert werden.

Da es sich um ein [[Verbesserungsverfahren]] handelt, wird zunächst mit einem Eröffnungsverfahren (z. B. dem [[Matrixminimumverfahren]], dem [[Nord-West-Ecken-Verfahren]], dem [[Zeilenfolgeverfahren|Zeilen-]] oder [[Spaltenfolgeverfahren]], der [[Zeilen-Spalten-Sukzession]], der [[Vogelsche Approximationsmethode|Vogelschen Approximationsmethode]] oder der [[Russell’schen Approximationsmethode]]) eine zulässige Anfangsbasislösung <math>x \in \mathbb{R}^{mn}</math> bestimmt. Variablen der Basislösung, die im Eröffnungsverfahren a priori gleich Null gesetzt wurden, sind die Nichtbasisvariablen, die restlichen die Basisvariablen des zu Grunde liegenden Gleichungssystems. Die Stepping-Stone-Methode verringert dann iterativ durch Austausch einer Nichtbasisvariablen mit einer Basisvariablen die Gesamtkosten. Kann keine Verbesserung mehr erzielt werden, ist eine Optimallösung gefunden.

== Geschichte ==

Als Urheber der Zyklenmethode gelten [[Abraham Charnes]] und [[William W. Cooper]].<ref>Theodor Ellinger: ''Operations Research: Eine Einführung'', Auflage 6, S. 79.</ref>

== Verfahren ==
Das Optimierungsverfahren wird iterativ durchgeführt. In jedem Schritt werden alle Nichtbasisvariablen im Hinblick auf das Kostensenkungspotential überprüft. Für jede Nichtbasisvariable <math>x_{ij}</math> wird dazu analysiert, wie sich die Gesamtkosten ändern würden, wenn eine Einheit des Gutes von <math>A_i</math> nach <math>B_j</math> transportiert werden würde. Dazu wird zu der Zelle <math>(i,j)</math> einer jeden Nichtbasisvariablen <math>x_{ij}</math> zusammen mit den Zellen der Basisvariablen ein elementarer Kreis bestimmt. Die Zellen <math>z_1</math> bis <math>z_k</math> <math>(k \geq 5)</math> bilden dabei einen elementaren Kreis, wenn <math>z_1 = z_k</math>, zwei aufeinanderfolgende Zellen <math>z_i</math> und <math>z_{i+1}</math> in der gleichen Zeile oder Spalte des Tableau liegen und in jeder Spalte und Zeile höchstens zwei Zellen des elementaren Kreises sind. Seien jetzt die Zellen <math>(i,o),(p,o),(p,q),\cdots , (v,j)</math> der Basisvariablen, die zusammen mit der Zelle <math>(i,j)</math> der Nichtbasisvariablen <math>x_{ij}</math> einen elementaren Kreis beschreiben, bestimmt. Dann lassen sich die Gesamtkosten um <math>k_{ij}:=c_{ij}-c_{io}+c_{po}-c_{pq}+ \cdots -c_{vj}</math> pro zusätzlicher von <math>A_i</math> nach <math>B_j</math> transportierter Einheit verbessern. Ist <math>k_{ij}</math> positiv, würde dies zu einer Erhöhung der Gesamtkosten führen, ist <math>k_{ij}</math> gleich Null, würden sich die Gesamtkosten nicht ändern. Um mit möglichst wenig Iterationen zur Optimallösung zu kommen wird deswegen die Nichtbasisvariable <math>x_{ij}</math> mit dem negativsten <math>k_{ij}</math> als neue Basisvariable aufgenommen und mit der wertmäßig kleinsten Basisvariable <math>x_{ab}</math>, deren Kosten bei der Bestimmung von <math>k_{ij}</math> mit negativem Faktor einging, ersetzt. Die Nichtbasisvariable <math>x_{ij}</math> wird neue Basisvariable mit dem Wert von <math>x_{ab}</math> und <math>x_{ab}</math> wird neue Nichtbasisvariable mit Wert Null. Damit die neue Basislösung zulässig bleibt, werden die übrigen Basisvariablen des elementaren Kreises um den Wert der ursprünglichen Basisvariable <math>x_{ab}</math> erhöht bzw. (wenn die zugehörigen Kosten bei der Bestimmung von <math>k_{ij}</math> mit negativem Faktor eingingen) verringert. Alle anderen Variablen <math>x_{kl}</math> bleiben unverändert. Das Verfahren wird solange wiederholt, bis alle (in jeder Iteration neu zu bestimmenden) <math>k_{ij}</math> größer oder gleich Null sind, die Gesamtkosten also nicht mehr verringert werden können und die Lösung damit optimal ist.

== Beispiel ==

Es liegt folgendes, tabellarisch zusammengefasstes Transportproblem vor, wobei es zwei Angebote <math>A_1</math> und <math>A_2</math> und drei Bedarfsanmeldungen <math>B_1</math>, <math>B_2</math> und <math>B_3</math> gibt und <math>x_{ij}</math> hier die von <math>i</math> nach <math>j</math> gelieferte Menge bezeichnet.

<math>
\begin{array}{c|ccc|c}
& B_1 & B_2 & B_3 \\ \hline
A_1 & x_{11} & x_{12} & x_{13} & 12 \\
A_2 & x_{21} & x_{22} & x_{23} & 8\\ \hline
& 4 & 10 & 6 & 20
\end{array}
</math>

Die Kosten <math>c_{ij}</math>, die für den Transport einer Einheit von <math>i</math> nach <math>j</math> entstehen, sind in der folgenden Tabelle aufgeführt.

<math>
\begin{array}{c|ccc|c}
c_{ij} & B_1 & B_2 & B_3 \\ \hline
A_1 & 7 & 4 & 3 & 12 \\
A_2 & 5 & 5 & 6 & 8 \\ \hline
& 4 & 10 & 6 & 20
\end{array}
</math>

Für die praktische Durchführung werden die Transportmengen in die Tabelle eingetragen und die entsprechenden Kosten werden in jeder Zelle oben links mit aufgeführt. Es wurde hier als Anfangslösung das [[Nord-West-Ecken-Verfahren]] verwendet. Es ergibt sich also

<math>
\begin{array}{c|ccc|c}
& B_1 & B_2 & B_3 \\ \hline
A_1 & 7/4 & 4/8 & 3/0 & 12 \\
A_2 & 5/0 & 5/2 & 6/6 & 8 \\ \hline
& 4 & 10 & 6 & 20
\end{array}
</math>

und man erhält Gesamtkosten von

:<math>4 \cdot 7 + 8 \cdot 4 + 0 \cdot 3 + 0 \cdot 5 + 2 \cdot 5 + 6 \cdot 6 = 106 </math>.

Es wird nun versuchsweise der Inhalt von Zelle 13 (soll bedeuten: (A1|B3)) um Eins erhöht. Man sieht, wie sich die Änderungen kreisförmig fortpflanzen.

<math>
\begin{array}{c|ccc|c}
& B_1 & B_2 & B_3 \\ \hline
A_1 & 7/4 & 4/\,\mathit{-1}\;8 & 3/\,\mathit{+1}\;\mathbf{0} & 12 \\
A_2 & 5/0 & 5/\,\mathit{+1}\;2 & 6/\,\mathit{-1}\;6 & 8 \\ \hline
& 4 & 10 & 6 & 20
\end{array}
</math>

Ebenso ändern sich die Kosten pro Einheit:

:<math>dc_{13} = + 3 - 4 + 5 -6 = -2.
</math>

Es würden also die Kosten um 2 Euro sinken, wenn <math>A_1</math> eine Einheit zu <math>B_3</math> transportieren würde.

Eine Analyse von Zelle 21 ergibt:

<math>
\begin{array}{c|ccc|c}
& B_1 & B_2 & B_3 \\ \hline
A_1 & 7/\,\mathit{-1}\;4 & 4/\,\mathit{+1}\;8 & 3/0 & 12 \\
A_2 & 5/\,\mathit{+1}\;0 & 5/\,\mathit{-1}\;2 & 6/6 & 8 \\ \hline
& 4 & 10 & 6 & 20
\end{array}
</math>

Die Kosten pro Einheit ändern sich um

:<math>dc_{21} = + 5 - 5 + 4 - 7 = -3</math>.

Es würden also die Kosten um 3 Euro sinken, wenn <math>A_2</math> eine Einheit zu <math>B_1</math> transportieren würde. Man sieht, dass die letztere Änderung die Kosten mehr senkt. Es wird nun so viel wie erlaubt in Zelle 21 transferiert, wobei die [[Vorzeichen (Zahl)|Vorzeichen]] der Einsen angeben, ob der Betrag addiert oder subtrahiert wird.

<math>
\begin{array}{c|ccc|c}
& B_1 & B_2 & B_3 \\ \hline
A_1 & 7/2 & 4/10 & 3/0 & 12 \\
A_2 & 5/2 & 5/0 & 6/6 & 8 \\ \hline
& 4 & 10 & 6 & 20
\end{array}
</math>

Es konnten nur maximal zwei Einheiten in die Zelle 21 transferiert werden, weil sonst die Zelle 22 negativ geworden wäre. Die Zelle 21 ist jetzt Basisvariable, die Zelle 22 Nichtbasisvariable.

Es werden nun wieder alle Nichtbasisvariablen untersucht. Für die Zelle 13 ergibt sich jetzt der Kreis der Zellen 13 - 11 - 21 - 23, denn Zelle 22 ist Nichtbasisvariable und kann nicht simultan mit Zelle 13 geändert werden. Zelle 22 wird also übersprungen. Man erhält dann

:<math>dc_{13} = 3 - 7 + 5 - 6 = -5</math>

und

:<math>dc_{22} = 5 - 4 + 7 -5 > 0</math>.

Hier steigen die Kosten bei Änderung von Zelle 22. Es wird also Zelle 13 verändert. Es können maximal zwei Einheiten nach Zelle 13 transferiert werden und man erhält nun

<math>
\begin{array}{c|ccc|c}
& B_1 & B_2 & B_3 \\ \hline
A_1 & 7/0 & 4/10 & 3/2 & 12 \\
A_2 & 5/4 & 5/0 & 6/4 & 8 \\ \hline
& 4 & 10 & 6 & 20
\end{array}
</math>

Es werden wieder alle Nichtbasisvariablen untersucht. Für die Zelle 11 ergibt sich jetzt der Kreis der Zellen 11 - 13 - 23 - 21, denn Zelle 22 ist Nichtbasisvariable und wird übersprungen. Man erhält dann

:<math>dc_{11} = 7 - 3 + 6 - 5 > 0</math>.

Die Nichtbasisvariable in Zelle 22 erzeugt hingegen

:<math>dc_{22} = 5 - 4 + 3 -6 = -2</math>.

Es wird also Zelle 22 verändert. Es können maximal vier Einheiten nach Zelle 22 transferiert werden und man erhält

<math>
\begin{array}{c|ccc|c}
& B_1 & B_2 & B_3 \\ \hline
A_1 & 7/0 & 4/6 & 3/6 & 12 \\
A_2 & 5/4 & 5/4 & 6/0 & 8 \\ \hline
& 4 & 10 & 6 & 20
\end{array}
</math>

Eine neue Iteration ergibt nur noch Kostensteigerungen, also ist das Verfahren beendet. Man erhält Gesamtkosten von

:<math>0 \cdot 7 + 6 \cdot 4 + 6 \cdot 3 + 4 \cdot 5 + 4 \cdot 5 + 0 \cdot 6 = 82</math>

im Gegensatz zu 106 der Startlösung.

== Bemerkungen ==

* Ist die gesamte nachgefragte Menge kleiner als die gesamte angebotene Menge, kann durch Einführen eines fiktiven Nachfragers <math>B_{m+1}</math>, der das überschüssige Angebot nachfragt und Transportkosten <math>c_{i,m+1}=0</math> für alle Anbieter <math>A_i</math> hat, das Transportproblem in ein Standardtransportmodell transformiert werden und damit ebenfalls mit der Stepping-Stone-Methode gelöst werden.
* Ist bei der Optimallösung eine mögliche Kostenveränderung <math>k_{ij}</math> bei Aufnahme der Variable <math>x_{ij}</math> gleich Null, bedeutet dieses, dass der Wert der zugehörige Nichtbasisvariable mit dem einer Basisvariablen ausgetauscht werden kann, ohne dass sich die Gesamtkosten ändern und die Optimallösung damit nicht eindeutig ist.
* Eine ähnliche Methode zur Verbesserung einer Anfangsbasislösung und finden der Optimallösung ist die [[MODI-Methode]]. Dabei werden die Kostenveränderungen <math>k_{ij}</math> mit geringerem Rechenaufwand (aber identischen Werten) als bei der Stepping-Stone-Methode bestimmt.
* Gibt es mehrere negative <math>k_{ij}</math> kann statt des betragsmäßig größten auch jene zugehörige Nichtbasisvariable ausgewählt werden, die zu einer maximalen Verbesserung der Kostensumme führt oder eine zufällig davon ausgewählt werden.

== Einzelnachweise ==
<references />

[[Kategorie:Optimierungsalgorithmus]]
[[Kategorie:Transportproblem]]

Zyklenmethode - Versionsgeschichte

imported>Sokrates 399: Typografie.