# 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 Vázsonyi gab 1962 als Urheber den fiktiven italienischen Mathematiker Zepartzat Gozinto an, was nichts anderes bedeutet als „the part that goes into“. Diese Bezeichnung ist mittlerweile etabliert. Als Entitätsmengengraph spielt der Gozintograph in der Graphentheorie und im Operations Research eine Rolle. Seine heutige Anwendungen liegen vorwiegend in der Betriebswirtschaftslehre, im Besonderen in der Materialbedarfsermittlung.
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:
| 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&\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:
    $\mathbf {T} \cdot {\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_{1}=100$, $p_{2}=200$, $p_{3}=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 sogenannte 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}$ ist die Anzahl der Komponenten $i$, die in Komponente $j$ landen. D ist daher vom Typ $n\times 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|}\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 ${\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} \cdot {\vec {g}}={\vec {a}}$
Aus (1) und (2) folgt dann wieder
(3) $\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 ${\vec {g}}$ auflösen:
${\vec {g}}=\mathbf {(E-D)^{-1}} \cdot {\vec {p}}=\mathbf {T^{-1}} \cdot {\vec {p}}$
Für unser Beispiel ergibt sich für $(E-D)^{-1}$:
    ${\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 ${\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.