Gozintograph

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
Dieser Artikel oder nachfolgende Abschnitt ist nicht hinreichend mit Belegen (beispielsweise Einzelnachweisen) ausgestattet. Die fraglichen Angaben werden daher möglicherweise demnächst entfernt. Bitte hilf der Wikipedia, indem du die Angaben recherchierst und gute Belege einfügst. Näheres ist eventuell auf der Diskussionsseite oder in der Versionsgeschichte angegeben. Bitte entferne zuletzt diese Warnmarkierung.

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 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[Bearbeiten]

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&\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\\500\\\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 × 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.

Einzelnachweise[Bearbeiten]

  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