Gozintograph

Der Gozintograph (auch Gozinto-Graph) ist ein gerichteter Graph, der beschreibt, aus welchen Teilen sich ein oder mehrere Produkte zusammensetzen.^[1] 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 Vázsonyi gab 1962 als Urheber den fiktiven italienischen Mathematiker Zepartzat Gozinto an, was nichts anderes bedeutet als „the part that goes into“.^[1][2][3] Diese Bezeichnung ist mittlerweile allgemein akzeptiert.
Als Entitätsmengengraph spielt der Gozintograph in der Graphentheorie und im Operations Research eine Rolle.^[4] Seine heutige Anwendungen liegen vorwiegend in der Betriebswirtschaftslehre, im Besonderen in der Materialbedarfsermittlung.^[5]

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 als Terme in linearen Gleichungssystemen, 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 wie Stiften, Schrauben, Schellen, Innenteilen, Deckeln usw. zusammen. In der folgenden Tabelle sind die einzelnen Teile aufgelistet:

Gozintograph für die Erstellung der Elektroartikel

Symbol	Index	Teil
A	1	Stecker
B	2	Verlängerungskabel
C	3	Steckdose
D	4	Deckelsatz Stecker
E	5	Korpus Stecker
F	6	Kabel
G	7	Korpus Dose
H	8	Deckelsatz Dose
I	9	Stift
J	10	Schraube
K	11	Schelle

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.

${\displaystyle A=100+1\cdot {B}}$	${\displaystyle B=200\,\!}$	${\displaystyle C=50+1\cdot {B}}$	${\displaystyle D=1\cdot {A}}$	${\displaystyle E=1\cdot {A}}$	${\displaystyle F=1\cdot {B}}$
${\displaystyle G=1\cdot {C}}$	${\displaystyle H=1\cdot {C}}$	${\displaystyle I=2\cdot {E}}$	${\displaystyle J=5\cdot {E}+3\cdot {G}}$	${\displaystyle K=2\cdot {E}+2\cdot {G}}$

Variante 1

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

${\displaystyle A=300}$	${\displaystyle B=200}$	${\displaystyle C=250}$	${\displaystyle D=300}$	${\displaystyle E=300}$	${\displaystyle F=200}$
${\displaystyle G=250}$	${\displaystyle H=250}$	${\displaystyle I=600}$	${\displaystyle J=2{.}250}$	${\displaystyle K=1{.}100}$

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 ${\displaystyle 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 ${\displaystyle i}$ nach Komponente ${\displaystyle 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 ${\displaystyle i}$, die in Komponente ${\displaystyle j}$ landen. D ist daher vom Typ ${\displaystyle n\times n}$, wenn der Gozintograph ${\displaystyle n}$ Knoten hat. Im Beispiel ist ${\displaystyle 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. Hans-Otto Günther und Horst Tempelmeier: Produktion und Logistik. 9. Auflage. Springer Verlag, Heidelberg; Dordrecht; London; New York 2012, ISBN 978-3-642-25164-1, S. 187 ff.
2. Heiner Müller-Merbach: Operations Research. 3. Auflage. Franz Vahlen, München 1973, ISBN 3-8006-0388-8, S. 259.
3. Heiner Müller-Merbach: Datenorganisation. 2. Auflage. Walter de Gruyter, Berlin / New York 1972, ISBN 3-11-004151-0 (Müller-Merbach verweist auf folgende Veröffentlichung: A. Vazsonyi: Die Planungsrechnung in Wirtschaft und Industrie (Übers. ins Deutsche). Wien/München 1962).
4. Heiner Müller-Merbach: A systems perspective: entity set graphs. In: Tomas Gal, Harvey J. Greenberg (Hrsg.): Advances in sensitivity analysis and parametric programming. (= International Series in Operations Research & Management Science; Bd. 6) Springer, New York 1997, ISBN 978-1-4613-7796-2, S. 2-1 – 2-45, darin auf S. 2-18 ff.
5. Heiner Müller-Merbach, Wolfgang P. Schmidt: Der Gozinto-Graph und seine praktische Anwendung für die Teilebedarfsermittlung. In: Zeitschrift für wirtschaftliche Fertigung. (ISSN 0044-3743) 63. Jg., H. 12 (1968), S. 643–646.