Gozintograph

Der Gozintograph 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 als Urheber den (fiktiven) italienischen Mathematiker Zepartzat Gozinto an, was nichts anderes bedeutet als „the part that goes into“. 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

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.

$A=100+1\cdot{B}$	$B=200\,\!$	$C=50+1\cdot{B}$	$D=1\cdot{A}$	$E=1\cdot{A}$	$F=1\cdot{B}$
$G=1\cdot{C}$	$H=1\cdot{C}$	$I=2\cdot{E}$	$J=5\cdot{E}+3\cdot{G}$	$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:

A = 300	B = 200	C = 250	D = 300	E = 300	F = 200
G = 250	H = 250	I = 600	J = 2.250	K = 1.100

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

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

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

$\begin{array}{|ccccccccccc|} 1&-1&0&0&0&0&0&0&0&0&0\\ 0&1&0&0&0&0&0&0&0&0&0\\ 0&-1&1&0&0&0&0&0&0&0&0\\ -1&0&0&1&0&0&0&0&0&0&0\\ -1&0&0&0&1&0&0&0&0&0&0\\ 0&-1&0&0&0&1&0&0&0&0&0\\ 0&0&-1&0&0&0&1&0&0&0&0\\ 0&0&-1&0&0&0&0&1&0&0&0\\ 0&0&0&0&-2&0&0&0&1&0&0\\ 0&0&0&0&-5&0&-3&0&0&1&0\\ 0&0&0&0&-2&0&-2&0&0&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\\0\\0\\0\\0\\0\\0\\0\\0\end{array}$

oder in Matrixschreibweise:

$\mathbf{T}*\vec{g}=\vec{p}$

Dabei stellt der Spaltenvektor $\vec{p}$ den sog. Primärbedarf dar. Seine Komponenten p_i sind die Vorgaben für die Absatzmengen und/oder den geplanten Lageraufbau der Komponenten i. Im obigen Beispiel ist p₁ = 100, p₂ = 200, p₃ = 50, alle anderen p_i sind 0. Der Spaltenvektor $\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 sog. Direktbedarfsmatrix D aufstellen: Die Werte der Matrixelemente D_i,j sind die Zahlen, die im Gozintographen jeweils an dem von Komponente i nach Komponente j führenden Pfeil stehen. Alle D_i,j für die es im Gozintographen keinen Pfeil gibt, erhalten den Wert Null. Mit anderen Worten: D_i,j is the number of parts i that goes into one part j. D ist daher vom Typ n x 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.

$\mathbf{D}=\begin{array}{|ccccccccccc|} 0&1&0&0&0&0&0&0&0&0&0\\ 0&0&0&0&0&0&0&0&0&0&0\\ 0&1&0&0&0&0&0&0&0&0&0\\ 1&0&0&0&0&0&0&0&0&0&0\\ 1&0&0&0&0&0&0&0&0&0&0\\ 0&1&0&0&0&0&0&0&0&0&0\\ 0&0&1&0&0&0&0&0&0&0&0\\ 0&0&1&0&0&0&0&0&0&0&0\\ 0&0&0&0&2&0&0&0&0&0&0\\ 0&0&0&0&5&0&3&0&0&0&0\\ 0&0&0&0&2&0&2&0&0&0&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 $\vec{p}$ wieder der Primärbedarf und $\vec{a}$ der für die Herstellung des Primärbedarfs entstehende abgeleitete Bedarf ist (seine Komponenten a_i sind die Mengen aller für die Deckung des Primärbedarfs erforderlichen Halbfabrikate und Rohstoffe), dann ist der Gesamtbedarfsvektor $\vec{g}$ definiert als:

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

Anhand des Beispiels überzeugt man sich leicht davon, dass

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

Aus (1) und (2) folgt dann wieder

(3)  $\mathbf{(E-D)}*\vec{g} = \mathbf{T}*\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 $\vec{g}$ auflösen:

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

Für unser Beispiel ergibt sich für (E − D) ^{− 1}:

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

Dadurch lässt sich für einen gegebenen Primärbedarf $\vec{p}$ der Gesamtbedarf $\vec{g}$ sowie mittels (1) auch der abgeleitete Bedarf $\vec{a}$ berechnen. Die Matrix (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.