Die Aufgabe aus der Einsendeaufgabe 1 erinnert stark an Simplex. Im Grunde geht es um die Frage, ob die Mitglieder eines Netzwerks einem bestimmten Standard folgen sollen, oder nicht. Und wie alles in Netzwerken wird auch das Anhand von Transaktionskosten zwischen den beteiligten Knoten entschieden. Dazu hat EA1 eine Tabelle aufgestellt, die anzeigt wie viel zwischen den Knoten 1 und 2 eingespart wird, wenn der neue Standard zwischen 1 und 2 eingeführt wird:
Einsparungen
- Standard eingeführt zwischen 1 und 2: 800 EUR Einsparung
- Standard eingeführt zwischen 1 und 3: 100 EUR Einsparung
- Standard eingeführt zwischen 1 und 4: 314 EUR Einsparung
- Standard eingeführt zwischen 2 und 3: 217 EUR Einsparung
- Standard eingeführt zwischen 2 und 4: 278 EUR Einsparung
- Standard eingeführt zwischen 3 und 4: 165 EUR Einsparung
Die weiteren Zellen – z. B. Standard zwischen 1 und 1 oder Standard zwischen 3 und 2 – sind nicht gefüllt weil die Betrachtung der Kommunikation zwischen Knoten 1 und 1 unsinnig ist und der Kommunikationsweg zwischen 3 und 2 der Gleiche ist, wie zwischen 2 und 3. Es reicht also nur einen Weg zu betrachten. Würden sich die Kosten für Hin- und Rückweg unterscheiden, müsste man natürlich auch den Rückweg mit in die Betrachtung einbeziehen.
Die Frage ist also:
Auf welchen Knoten kann ich den Standard einführen, um die größten Einsparungen zu erzielen?
Und in diesem Moment heißt die Antwort noch: An allen!
Und warum? Weil wir noch keine Kosten für die Einführung definiert haben. Wäre ja auch zu schön gewesen, wenn man irgendwo Einsparungen realisieren kann, ohne Kosten zu haben. Die Minimierungsfunktion wäre in diesem Fall ziemlich witzlos. Aber dafür das Ergebnis recht eindeutig. It’s something.
Kosten
Kümmern wir uns daher um die Kosten. Diese sind für die 4 Knoten:
- Kosten für die Einführung des Standards auf Knoten 1: 300 EUR
- Kosten für die Einführung des Standards auf Knoten 2: 475 EUR
- Kosten für die Einführung des Standards auf Knoten 3: 513 EUR
- Kosten für die Einführung des Standards auf Knoten 4: 987 EUR
Und jetzt können wir die Frage erneut stellen:
Auf welchen Knoten kann ich den Standard einführen, um die größten Einsparungen zu erzielen?
Aber die Antwort ist hier nicht mehr so einfach.
Versuchen wir dennoch unser Glück. Führen wir einfach auf jedem Knoten den Standard ein, so haben wir folgende Kosten: $$300+475+513+987=2275$$ EUR bei Einsparungen von $$800+100+314+217+278+165=1875$$ EUR. Lohnt sich nicht auf den ersten Blick, oder?
Aber dafür können wir unsere Frage etwas präziser stellen:
Auf welchen Knoten muss ich den Standard einführen, um bei den geringsten Kosten die größten Einsparungen zu erzielen?
Unwichtiges streichen
Um jetzt ein Modell aufzustellen, müssen wir uns klar machen, dass wir bei $$4$$ Knoten insgesamt $$4!=24$$ Kombinationsmöglichkeiten haben. Obwohl z. B. die Permutationen $$1,2$$ und $$2,1$$ unterschiedlich sind, haben wir kein Interesse an ihnen. Denn das Ergebnis wäre gleich (Kosten: $$300+475=775$$ EUR gegenüber $$475+300=775$$ EUR). Das gilt natürlich auch für die Permutation $$1,2,3,4$$ und $$4,3,2,1$$. Auch an der Einführung des Standards auf einem einzigen Knoten ist nicht spannend, also streichen wir auch das. Nehmen wir das mal Stück für Stück auseinander:
- $$4^1=4$$ (Kombination: 1 aus 4: Einführung Standard nur auf einem Knoten) – kein Interesse
- $$4^2=16$$ (Kombination: 2 aus 4: Einführung Standard auf zwei Knoten) – kein Interesse an der Reihenfolge, wie z. B. bei $$1,2$$ und $$2,1$$ sowie an $$1,1$$ oder $$2,2$$. Bleiben hier nur noch 6 spannende Paare: $$1,2$$ – $$1,3$$ – $$1,4$$ – $$2,3$$ – $$2,4$$ – $$3,4$$
- $$4^3=64$$: (Kombination: 3 aus 4: Einführung Standard auf drei Knoten) – hier gilt das gleiche wie bei $$4^2$$. Es bleiben nur die Tripel $$1,2,3$$ – $$1,2,4$$ – $$1,3,4$$.
- $$4^3=64$$: (Kombination: 4 aus 4: Einführung Standard auf vier Knoten) – das wird am einfachsten. Was bleibt, ist die Einführung auf allen 4 Knoten $$1,2,3,4$$.
Die Kombination $$k$$ aus $$n$$ ohne Wiederholung ist der Binomialkoeffizient und wird mit folgender Formel ausgedrückt:
$${{n!} \over {k!(n-k!)}} = \dbinom{n}{k}$$
Wir suchen uns die Kombinationen 2, 3 und 4. Setzen wir das in die Formel ein, so landen wir bei:
$$\dbinom{4}{2} = 6$$
$$\dbinom{4}{3} = 4$$
$$\dbinom{4}{4} = 1$$
Es sind also 11 Kombinationen zu berechnen (Kosten minus Einsparung = Ergebnis). Prüfen wir, ob’s wirklich 11 sind:
- $$1,2$$ = $$775 – 800 = -25$$
- $$1,3$$ = $$813 – 100 = 713$$
- $$1,4$$ = $$1287 – 315 = 972$$
- $$2,3$$ = $$988 – 217 = 771$$
- $$2,4$$ = $$1462 – 287 = 1184$$
- $$3,4$$ = $$1500 – 165 = 1335$$
- $$1,2,3$$ = $$1288 – 1117 = 171$$
- $$1,2,4$$ = $$1762 – 1393 = 369$$
- $$1,3,4$$ = $$1800 – 580 = 1220$$
- $$2,3,4$$ = $$1975 – 660 = 1315$$
- $$1,2,3,4$$ = $$2275 – 1875 = 400$$
Ja, sind 11. Ab hier ist zu sehen, dass das beste Kosten / Einsparungs-Verhältnis die Einführung des Standards auf Knoten $$1$$ und $$2$$ bietet und uns einen „Gewinn“ (negative, indirekte Kosten) von 25 EUR beschert. Es sieht zwar was doof aus, da wir Kosten + Einsparung rechnen, aber das ist eine Minimierungsfunktion, die wir aufstellen wollen. Wenn wir das umdrehen (Einsparung – Kosten), haben wir eine Maximierungsfunktion, können aber nicht so schön rechnen.
Das Modell
Aber wie gießen wir unsere Erkenntnis in ein Modell? Wir brauchen Entscheidungsvariablen $$x_i$$, die uns anzeigen, ob der Standard an Knoten $$i$$ etabliert ist. Das befähigt uns dazu die Parameter Kosten $$c_i$$ und Einsparungen $$s_{ij}$$ (wenn Standard an Knoten $$i$$ und $$j$$ eingeführt wurde ist) auszurechnen.
Das bedeutet: WENN $$x_i = x_j = 1$$ (Standard ist an Knoten $$i$$ und $$j$$ etabliert), sind die Kosten $$c_i + c_j$$ und die Einsparungen $$s_{ij}$$. Wie euch aufgefallen ist, nutzen wir für unser WENN / DANN – Konstrukt die Entscheidungsvariable $$x_i$$, wenn der Standard auf Knoten $$i$$ eingeführt wurde. Wenn Die Entscheidungsvariable 1 ist, so werden die Kosten mit 1 multipliziert. Ansonsten ist sie 0, die Kosten werden mit 0 multipliziert, sind also nicht vorhanden.
Das wäre der erste Teil der Minimierungsfunktion aus dem Skript:
$$\sum\limits_{i=1}^n c_i x_i$$
Vereinfachen wir als Beispiel unsere Rechnung und probieren das mal mit zwei Knoten aus. Standard eingeführt auf Knoten 1 und 2: $$x_1$$ und $$x_2 = 1$$. Kosten: $$c_1 + c_2 = 300 + 475 = 775$$ (und Einsparungen $$s_{12} = 800$$). Sieht gut aus.
$$\sum\limits_{i=1}^2 c_i x_i = 300*1 + 475*1 = 775$$
Das Problem hier ist, dass wir damit nur die Kosten für die Einführung des Standards aufsummiert haben. Wenn wir das minimieren führt uns das nur dazu, dass wir wissen an welchen Knoten wir mit den geringsten Kosten den Standard einführen können. Die Relation zu den Einsparungen fehlt uns noch!
Das wäre der 2. Teil aus dem Skript:
$$\sum\limits_{i=1}^{n-1} \sum\limits_{j=i+1}^{n} s_{ij} z_{ij}$$
Der ist ein bisschen aufwändiger. Lasst euch von dem 2. Summenzeichen nicht irritieren, das ist nur eine Doppelsumme. Diese können wir auch ausschreiben. Sieht nur dann nicht mehr so fancy aus.
Exkurs: Doppelsumme
$$\sum\limits_{i=1}^{n-1} \sum\limits_{j=i+1}^{n} s_{ij} z_{ij} = \sum\limits_{i=1}^{n-1} s_{i2} z_{i2}+s_{i3} z_{i3}+ … + s_{in} z_{in}$$
Probieren wir das einfach mal an $$n=3$$.
Beispiel: $$\sum\limits_{i=1}^{2} \sum\limits_{j=i+1}^{3} s_{ij} z_{ij} = \sum\limits_{i=1}^{2} s_{i2} z_{i2}+s_{i3} z_{i3} = s_{12} z_{12}+s_{23} z_{23}$$
Bevor wir den 2. Teil der Minimierungsfunktion im Detail auseinander nehmen, müssen wir uns über die folgende Relation im klaren sein (Achtung, wichtig!): Wenn wir den Standard an Knoten $$i$$ und $$j$$ nicht einführen, entstehen uns zwar direkt keine Kosten $$c_i$$ und $$c_j$$, aber uns entgehen auch die damit verbundenen Einsparungen $$s_{ij}$$, die als indirekte Kosten betrachtet werden können.
Beispiel: Einführung den Standards auf Knoten 1 und 2 ergibt Kosten von 775 EUR und Einsparungen von 800 EUR, so dass wir unter’m Strich mit 25 EUR nach Hause gehen. Die Nicht-Einführung des Standards auf den beiden Knoten ergibt keine direkten Kosten, aber entgangene Einsparungen von 800 EUR. Damit sind wir 25 EUR im Minus.
Unsere Rechnung der vollständigen Kosten (direkt und indirekt) müsste im Falle der Standard-Einführung so aussehen: 300*1 + 475*1 + 0*800 = 775.
Führen wir den Standard nicht ein, haben wir: 300*0 + 475*0 + 1*800 = 800 an indirekten Kosten durch entgangene Einsparung.
Der Bezug von Kosten zu entgangenen Einsparungen wird durch die Verbindung der Entscheidungsvariablen $$x_i$$ und $$z_{ij}$$ erreicht. Sind $$x_i$$ und $$x_j = 1$$ (Standard wird eingeführt), so ist die Entscheidungsvariable $$z_{ij} = 0$$ (uns entgehen keine Einsparungen, es entstehen aber direkte Kosten). Sind $$x_i$$ und $$x_j = 0$$ (Standard wird nicht eingeführt), so ist die Entscheidungsvariable $$z_{ij} = 1$$ (uns entgehen Einsparungen und damit entstehen indirekte Kosten). Und da wir Interesse haben unsere gesamten Kosten zu minimieren, führen wir beides nun zusammen.
$$\sum\limits_{i=1}^n c_i x_i + \sum\limits_{i=1}^{n-1} \sum\limits_{j=i+1}^{n} s_{ij} z_{ij}$$
Bei $$n=4$$ würde die ausgeschriebene Funktion wie folgt aussehen:
Das erste Summenzeichen: $$c_1x_1+c_2x_2+c_3x_3+c_4x_4$$ (direkte Kosten)
Die zwei weiteren Summenzeichen: $$s_{12}z_{12}+s_{13}z_{13}+s_{23}z_{23}+s_{14}z_{14}+s_{24}z_{24}+s_{34}z_{34}$$ (indirekte Kosten durch entgangene Einsparungen)
Zusammen:
$$c_1x_1+c_2x_2+c_3x_3+c_4x_4+s_{12}z_{12}+s_{13}z_{13}+s_{23}z_{23}+$$
$$s_{14}z_{14}+s_{24}z_{24}+s_{34}z_{34}$$
Und das ist unsere ganze Minimierungsfunktion für 4 Knoten. Setzen wir die Kosten und Einsparungen mal ein.
Min $$300x_1+475x_2+513x_3+987x_4+800z_{12}+100z_{13}+217z_{23}+$$
$$315z_{14}+278z_{24}+165z_{34}$$
Wir sind fast fertig. Uns fehlt nur noch eines.
Nebenbedingungen
Wir haben diese zwar schon in Prosa formuliert, müssen das aber in mathematischer Notation noch nachholen und eine kleine Ungenauigkeit beseitigen. Rekapitulieren wir: Folgende zwei Bedingungen sind zu formulieren:
- Wenn der Standard auf Knoten 1 und 2 eingeführt wurden, so sind uns direkte Kosten entstanden, aber gleichzeitig Einsparungen erzielt worden (oder nicht, siehe Fallunterscheidung). Ist der Standard nicht eingeführt worden, sind uns in Form von entgangenen Einsparungen indirekte Kosten entstanden. Da wir diesen Sachverhalt bereis in den Entscheidungsvariablen $$x_i, x_j$$ und $$z_{ij}$$ festgehalten haben, müssen wir deren Beziehung nun mathematisch formulieren.
Wir haben folgende Fälle zu unterscheiden:
- Eingeführt auf Knoten $$x_i$$, aber nicht auf Knoten $$x_j$$. Es entstanden also nur Kosten für Knoten $$x_i$$. Einsparungen dürfen keinesfalls vorhanden sein, da uns für die Kommunikation der Knotenpartner fehlt.
Damit muss $$z_{ij}=1$$ (indirekte Kosten sind entstanden) sein. Ist $$z_{ij}=0$$, so darf die NB nicht erfüllt sein.- Gleiches gilt anders herum für die Einführung nur bei $$x_j$$.
- Gar keine Einführung. Es muss gelten: $$z_{ij}=1$$ (indirekte Kosten sind entstanden). Wenn wir $$z_{ij}=0$$ setzen, darf die NB nicht erfüllt sein.
- Einführung bei beiden Knoten. Hier räumen wir die Ungenauigkeit aus (danke an die Kursbetreuung für den Hinweis!): Obwohl der Standard eingeführt wurde, heißt es nicht, dass man ihn auch nutzen muss. Man darf!Bedeutet: Obwohl wir direkte Kosten für die Einführung hatten, müssen wir die Einsparungen nicht realisieren (auch wenn das natürlich sinnlos wäre) und können uns ökonomisch sinnfrei direkte und indirekte Kosten aufhalsen, d. h. die beiden Fälle $$z_{ij}=1$$ (keine Nutzung des Standards = keine Einsparungen = indirekte Kosten) und $$z_{ij}=0$$ (Nutzung des Standards = Einsparungen realisiert = keine indirekten Kosten) sind beide erlaubt, auch wenn der Standard an beiden Knoten eingeführt wurde. Die NB muss daher in beiden Fällen „true“ zurückliefern.
Hier greift das Skript in die mathematische Trickkiste und formuliert alle 4 Bedingungen mit Hilfe einer großen, positiven Konstante $$M$$.
$$x_i + x_j >= 2 – M{z_{ij}}$$ (NB 1.5)
Wenn wir für alle möglichen Fälle die Werte in die Nebenbedingung einsetzen, muss die Nebenbedingung folgende Fälle abfangen und folgende Ergebnisse zurückliefern:
$$1+1 >= 2 – (1000*0) = true$$
$$1+0 >= 2 – (1000*1) = true$$
$$0+1 >= 2 – (1000*1) = true$$
$$0+0 >= 2 – (1000*1) = true$$$$1+1 >= 2 – (1000*1) = true$$
$$1+0 >= 2 – (1000*0) = false$$
$$0+1 >= 2 – (1000*0) = false$$
$$0+0 >= 2 – (1000*0) = false$$
Und das macht sie auch, rechnet das ruhig nach.
Bleibt nur noch NB 1.6. Aber die ist – das wollte ich immer schon einmal sagen – trivial.
$$x_i \in\{0,1\}, z_{ij} \in\{0,1\}, i=1,…,n, j = 1,…,n, i < j$$ (NB 1.6)
Sie sagt nichts weiter aus, als dass unsere Variablen binär sind und unser Zähler $$i$$ kleiner als $$j$$ sein muss (wäre $$i\leq j$$, so gäbe es z. B. $$s_{11}$$, d. h. einen Einsparungsbetrag von Knoten 1 zu Knoten 1).
