Gozintograph

Der Gozintograph (auch Gozinto-Graph) ist ein gerichteter Graph, der beschreibt, aus welchen Teilen sich ein oder mehrere Produkte zusammensetzen. Der Produktionsprozess kann dabei mehrstufig sein, wobei der Input aus Rohstoffen, Halb- und Fertigteilen besteht. Im Gozintographen ist aufgeführt, wie diese Teile gegebenenfalls mengenmäßig verflochten sind. Dabei bezeichnen die Knoten die Teile und die gerichteten Kanten geben an, wie viele Einheiten eines Teiles in eine Einheit eines nachgelagerten Teiles einfließen.

Der Name dieses Graphen ist eine scherzhafte Verballhornung: Der Mathematiker Andrew Vazsonyi gab 1962 als Urheber den fiktiven italienischen Mathematiker Zepartzat Gozinto an, was nichts anderes bedeutet als the part that goes into.^[1] Diese Bezeichnung ist mittlerweile allgemein akzeptiert.

Der Gozintograph wird vor allem im Bereich der Produktionsplanung und -steuerung für die Auflösung von Stücklisten angewendet. Die Inhalte des Graphen können in ein lineares Gleichungssystem eingebracht werden. Es ergeben sich dann meistens sehr große, dünnbesetzte Koeffizientenmatrizen, die je nach Struktur unterschiedliche Lösungsverfahren ermöglichen.

Beispiel

Im folgenden stark vereinfachten Beispiel sollen für einen Heimwerkermarkt 200 Verlängerungskabel, 100 Stecker und 50 Dosen produziert werden. Die Endprodukte setzen sich aus verschiedenen Teilen zusammen, Stiften, Schrauben, Schellen, Innenteile, Deckel usw. In der folgenden Tabelle sind die einzelnen Teile aufgelistet:

Gozintograph für die Erstellung der Elektroartikel

Die Verflechtungen können in ein Gleichungssystem überführt werden. Es wird zunächst anhand des Gozintographen aufgeführt, wie viele Einheiten von jedem Teil gebraucht werden.

Variante 1

Aufgrund der einfachen Struktur dieses Beispiels können die einzelnen Gleichungen sukzessive gelöst werden. Es wird benötigt:

Um eine Koeffizientenmatrix für das Gleichungssystem zu erstellen, wandelt man die Gleichungen entsprechend um, z. B.:

${\displaystyle 1\,A=100+1\,B\Leftrightarrow {1\,A-1\,B=100}}$

Die Koeffizienten dieses linearen Gleichungssystems bilden dann die so genannte Technologiematrix T:

${\displaystyle {\begin{array}{|ccccccccccc|}1&-1&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}\\\color {Gray}{0}&1&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}\\\color {Gray}{0}&-1&1&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}\\-1&\color {Gray}{0}&\color {Gray}{0}&1&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}\\-1&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&1&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}\\\color {Gray}{0}&-1&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&1&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}\\\color {Gray}{0}&\color {Gray}{0}&-1&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&1&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}\\\color {Gray}{0}&\color {Gray}{0}&-1&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&1&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}\\\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&-2&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&1&\color {Gray}{0}&\color {Gray}{0}\\\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&-5&\color {Gray}{0}&-3&\color {Gray}{0}&\color {Gray}{0}&1&\color {Gray}{0}\\\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&-2&\color {Gray}{0}&-2&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&1\end{array}}\cdot {\begin{array}{|c|}A\\B\\C\\D\\E\\F\\G\\H\\I\\J\\K\end{array}}={\begin{array}{|c|}100\\200\\50\\\color {Gray}{0}\\\color {Gray}{0}\\\color {Gray}{0}\\\color {Gray}{0}\\\color {Gray}{0}\\\color {Gray}{0}\\\color {Gray}{0}\\\color {Gray}{0}\end{array}}}$

oder in Matrixschreibweise:

${\displaystyle \mathbf {T} \cdot {\vec {g}}={\vec {p}}}$

Dabei stellt der Spaltenvektor ${\displaystyle {\vec {p}}}$ den sog. Primärbedarf dar. Seine Komponenten ${\displaystyle p_{i}}$ sind die Vorgaben für die Absatzmengen und/oder den geplanten Lageraufbau der Komponenten i. Im obigen Beispiel ist ${\displaystyle p_{1}=100}$, ${\displaystyle p_{2}=200}$, ${\displaystyle p_{3}=50}$, alle anderen ${\displaystyle p_{i}}$ sind 0. Der Spaltenvektor ${\displaystyle {\vec {g}}}$ ist der Gesamtbedarf (Primärbedarf plus abgeleiteter Bedarf) für diese Produktion.

Variante 2

Alternativ lässt sich unmittelbar aus dem Gozintographen die sogenannte Direktbedarfsmatrix D aufstellen: Die Werte der Matrixelemente ${\displaystyle D_{i,j}}$ sind die Zahlen, die im Gozintographen jeweils an dem von Komponente i nach Komponente j führenden Pfeil stehen. Alle ${\displaystyle D_{i,j}}$ für die es im Gozintographen keinen Pfeil gibt, erhalten den Wert Null. Mit anderen Worten: ${\displaystyle D_{i,j}}$ ist die Anzahl der Komponenten i, die in Komponente j landen. D ist daher vom Typ n × n, wenn der Gozintograph n Knoten hat. Im Beispiel ist n = 11. Rein mathematisch gesehen ist die Direktbedarfsmatrix somit nichts anderes als die Gewichtsmatrix des jeweiligen Gozintographen.

${\displaystyle \mathbf {D} ={\begin{array}{|ccccccccccc|}\color {Gray}{0}&1&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}\\\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}\\\color {Gray}{0}&1&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}\\1&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}\\1&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}\\\color {Gray}{0}&1&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}\\\color {Gray}{0}&\color {Gray}{0}&1&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}\\\color {Gray}{0}&\color {Gray}{0}&1&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}\\\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&2&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}\\\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&5&\color {Gray}{0}&3&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}\\\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&2&\color {Gray}{0}&2&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}\end{array}}}$

Die Spalten von D, die zu Rohmaterialien (Kaufteilen) j gehören, enthalten daher ausschließlich Nullen, ebenso die Zeilen von D, die zu Endprodukten i gehören, welche nicht zur Herstellung anderer Komponenten verwendet werden. Wenn ${\displaystyle {\vec {p}}}$ wieder der Primärbedarf und ${\displaystyle {\vec {a}}}$ der für die Herstellung des Primärbedarfs entstehende abgeleitete Bedarf ist (seine Komponenten ${\displaystyle a_{i}}$ sind die Mengen aller für die Deckung des Primärbedarfs erforderlichen Halbfabrikate und Rohstoffe), dann ist der Gesamtbedarfsvektor ${\displaystyle {\vec {g}}}$ definiert als:

(1)  ${\displaystyle {\vec {g}}={\vec {p}}+{\vec {a}}}$

Anhand des Beispiels überzeugt man sich leicht davon, dass

(2)  ${\displaystyle \mathbf {D} \cdot {\vec {g}}={\vec {a}}}$

Aus (1) und (2) folgt dann wieder

(3)  ${\displaystyle \mathbf {(E-D)} \cdot {\vec {g}}=\mathbf {T} \cdot {\vec {g}}={\vec {p}}}$

wobei E die Einheitsmatrix der Dimension n ist und (E - D) = T, die Technologiematrix aus Variante 1.

Anwendung

Durch Inversion der nach Variante 1 oder 2 aufgestellten Technologiematrix T lässt sich (3) nach ${\displaystyle {\vec {g}}}$ auflösen:

${\displaystyle {\vec {g}}=\mathbf {(E-D)^{-1}} \cdot {\vec {p}}=\mathbf {T^{-1}} \cdot {\vec {p}}}$

Für unser Beispiel ergibt sich für ${\displaystyle (E-D)^{-1}}$:

${\displaystyle {\begin{array}{|ccccccccccc|}1&1&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}\\\color {Gray}{0}&1&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}\\\color {Gray}{0}&1&1&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}\\1&1&\color {Gray}{0}&1&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}\\1&1&\color {Gray}{0}&\color {Gray}{0}&1&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}\\\color {Gray}{0}&1&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&1&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}\\\color {Gray}{0}&1&1&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&1&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}\\\color {Gray}{0}&1&1&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&1&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}\\2&2&\color {Gray}{0}&\color {Gray}{0}&2&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&1&\color {Gray}{0}&\color {Gray}{0}\\5&8&3&\color {Gray}{0}&5&\color {Gray}{0}&3&\color {Gray}{0}&\color {Gray}{0}&1&\color {Gray}{0}\\2&4&2&\color {Gray}{0}&2&\color {Gray}{0}&2&\color {Gray}{0}&\color {Gray}{0}&\color {Gray}{0}&1\end{array}}}$

Dadurch lässt sich für einen gegebenen Primärbedarf ${\displaystyle {\vec {p}}}$ der Gesamtbedarf ${\displaystyle {\vec {g}}}$ sowie mittels (1) auch der abgeleitete Bedarf ${\displaystyle {\vec {a}}}$ berechnen. Die Matrix ${\displaystyle (E-D)^{-1}}$ wird deswegen auch als Gesamtbedarfsmatrix G bezeichnet. Durch zusätzliche Berücksichtigung von vorhandenen Lagerbeständen kann man dann noch weiter vom hier betrachteten Bruttobedarf auf den Nettobedarf zurückrechnen.

Einzelnachweise

1. ↑ Heiner Müller-Merbach: Datenorganisation. 2., verbesserte Auflage. Walter de Gruyter, Berlin / New York 1972, ISBN 3-11-004151-0. – Hier verweist er auf A. Vazsonyi: Die Planungsrechnung in Wirtschaft und Industrie (deutsche Übersetzung). Wien/München 1962
   Heiner Müller-Merbach: Operations Research. 3. Auflage. Verlag Franz Vahlen, München 1973, ISBN 3-8006-0388-8, S. 259