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\u00fchrt wird:<\/p>\n
Einsparungen<\/strong><\/p>\n Die weiteren Zellen\u00a0 – z. B. Standard zwischen 1 und 1 oder Standard zwischen 3 und 2 – sind nicht gef\u00fcllt 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\u00fcrden sich die Kosten f\u00fcr Hin- und R\u00fcckweg unterscheiden, m\u00fcsste man nat\u00fcrlich auch den R\u00fcckweg mit in die Betrachtung einbeziehen.<\/p>\n Die Frage ist also:<\/p>\n Auf welchen Knoten kann ich den Standard einf\u00fchren, um die gr\u00f6\u00dften Einsparungen zu erzielen<\/em>?<\/p><\/blockquote>\n Und in diesem Moment hei\u00dft die Antwort noch: An allen!<\/p>\n Und warum? Weil wir noch keine Kosten f\u00fcr die Einf\u00fchrung definiert haben. W\u00e4re ja auch zu sch\u00f6n gewesen, wenn man irgendwo Einsparungen realisieren kann, ohne Kosten zu haben. Die Minimierungsfunktion w\u00e4re in diesem Fall ziemlich witzlos. Aber daf\u00fcr das Ergebnis recht eindeutig. It’s something.<\/p>\n Kosten<\/strong><\/p>\n K\u00fcmmern wir uns daher um die Kosten. Diese sind f\u00fcr die 4 Knoten:<\/p>\n Und jetzt k\u00f6nnen wir die Frage erneut stellen:<\/p>\n Auf welchen Knoten kann ich den Standard einf\u00fchren, um die gr\u00f6\u00dften Einsparungen zu erzielen<\/em>?<\/p><\/blockquote>\n Aber die Antwort ist hier nicht mehr so einfach.<\/p>\n Versuchen wir dennoch unser Gl\u00fcck. F\u00fchren 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?<\/p>\n Aber daf\u00fcr k\u00f6nnen wir unsere Frage etwas pr\u00e4ziser stellen:<\/p>\n Auf welchen Knoten muss ich den Standard einf\u00fchren, um bei den geringsten Kosten die gr\u00f6\u00dften Einsparungen zu erzielen<\/em>?<\/p><\/blockquote>\n Unwichtiges streichen<\/strong><\/p>\n Um jetzt ein Modell aufzustellen, m\u00fcssen wir uns klar machen, dass wir bei $$4$$ Knoten insgesamt $$4!=24$$ Kombinationsm\u00f6glichkeiten haben. Obwohl z. B. die Permutationen $$1,2$$ und $$2,1$$ unterschiedlich sind, haben wir kein Interesse an ihnen. Denn das Ergebnis w\u00e4re gleich (Kosten: $$300+475=775$$ EUR gegen\u00fcber $$475+300=775$$ EUR). Das gilt nat\u00fcrlich auch f\u00fcr die Permutation $$1,2,3,4$$ und $$4,3,2,1$$. Auch an der Einf\u00fchrung des Standards auf einem einzigen Knoten ist nicht spannend, also streichen wir auch das. Nehmen wir das mal St\u00fcck f\u00fcr St\u00fcck auseinander:<\/p>\n Die Kombination $$k$$ aus $$n$$ ohne Wiederholung ist der Binomialkoeffizient und wird mit folgender Formel ausgedr\u00fcckt:<\/p>\n $${{n!} \\over {k!(n-k!)}} = \\dbinom{n}{k}$$<\/p><\/blockquote>\n Wir suchen uns die Kombinationen 2, 3 und 4. Setzen wir das in die Formel ein, so landen wir bei:<\/p>\n $$\\dbinom{4}{2} = 6$$<\/p>\n $$\\dbinom{4}{3} = 4$$<\/p>\n $$\\dbinom{4}{4} = 1$$<\/p><\/blockquote>\n Es sind also 11 Kombinationen zu berechnen (Kosten minus Einsparung = Ergebnis). Pr\u00fcfen wir, ob’s wirklich 11 sind:<\/p>\n Ja, sind 11. Ab hier ist zu sehen, dass das beste Kosten \/ Einsparungs-Verh\u00e4ltnis die Einf\u00fchrung 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\u00f6nnen aber nicht so sch\u00f6n rechnen.<\/p>\n Das Modell<\/strong><\/p>\n Aber wie gie\u00dfen wir unsere Erkenntnis in ein Modell? Wir brauchen Entscheidungsvariablen $$x_i$$, die uns anzeigen, ob der Standard an Knoten $$i$$ etabliert ist. Das bef\u00e4higt uns dazu die Parameter Kosten $$c_i$$ und Einsparungen $$s_{ij}$$ (wenn Standard an Knoten $$i$$ und $$j$$ eingef\u00fchrt wurde ist) auszurechnen.<\/p>\n 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\u00fcr unser WENN \/ DANN – Konstrukt die Entscheidungsvariable $$x_i$$, wenn der Standard auf Knoten $$i$$ eingef\u00fchrt 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.<\/p>\n Das w\u00e4re der erste Teil der Minimierungsfunktion aus dem Skript:<\/p>\n $$\\sum\\limits_{i=1}^n c_i x_i$$<\/p><\/blockquote>\n Vereinfachen wir als Beispiel unsere Rechnung und probieren das mal mit zwei Knoten aus. Standard eingef\u00fchrt auf Knoten 1 und 2:\u00a0$$x_1$$ und $$x_2 = 1$$. Kosten:\u00a0$$c_1 + c_2 = 300 + 475 = 775$$ (und Einsparungen\u00a0$$s_{12} = 800$$). Sieht gut aus.<\/p>\n $$\\sum\\limits_{i=1}^2 c_i x_i = 300*1 + 475*1 = 775$$<\/p><\/blockquote>\n Das Problem hier ist, dass wir damit nur die Kosten f\u00fcr die Einf\u00fchrung des Standards aufsummiert haben. Wenn wir das minimieren f\u00fchrt uns das nur dazu, dass wir wissen an welchen Knoten wir mit den geringsten Kosten den Standard einf\u00fchren k\u00f6nnen. Die Relation zu den Einsparungen fehlt uns noch!<\/p>\n Das w\u00e4re der 2. Teil aus dem Skript:<\/p>\n $$\\sum\\limits_{i=1}^{n-1} \\sum\\limits_{j=i+1}^{n} s_{ij} z_{ij}$$<\/p><\/blockquote>\n Der ist ein bisschen aufw\u00e4ndiger.\u00a0Lasst euch von dem 2. Summenzeichen nicht irritieren, das ist nur eine Doppelsumme. Diese k\u00f6nnen wir auch ausschreiben. Sieht nur dann nicht mehr so fancy aus.<\/p>\n Exkurs: Doppelsumme<\/strong><\/p>\n $$\\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}$$<\/p><\/blockquote>\n Probieren wir das einfach mal an $$n=3$$.<\/p>\n Beispiel<\/strong>:\u00a0$$\\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}$$<\/p><\/blockquote>\n Bevor wir den 2. Teil der Minimierungsfunktion im Detail auseinander nehmen, m\u00fcssen wir uns \u00fcber die folgende Relation im klaren sein (Achtung, wichtig!): Wenn wir den Standard an Knoten $$i$$ und $$j$$ nicht einf\u00fchren, 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<\/em> betrachtet werden k\u00f6nnen.<\/p>\n Beispiel<\/strong>: Einf\u00fchrung 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\u00fchrung des Standards auf den beiden Knoten ergibt keine direkten Kosten, aber entgangene Einsparungen von 800 EUR. Damit sind wir 25 EUR im Minus.<\/p>\n Unsere Rechnung der vollst\u00e4ndigen Kosten (direkt und indirekt) m\u00fcsste im Falle der Standard-Einf\u00fchrung so aussehen: 300*1 + 475*1 + 0*800 = 775.<\/p>\n F\u00fchren wir den Standard nicht ein, haben wir:\u00a0300*0 + 475*0 + 1*800 = 800 an indirekten Kosten durch entgangene Einsparung.<\/p><\/blockquote>\n Der Bezug von Kosten zu entgangenen Einsparungen wird durch die Verbindung der Entscheidungsvariablen $$x_i$$ und $$z_{ij}$$ erreicht. Sind $$x_i$$ und\u00a0$$x_j = 1$$ (Standard wird eingef\u00fchrt), so ist die Entscheidungsvariable\u00a0$$z_{ij} = 0$$ (uns entgehen keine Einsparungen, es entstehen aber direkte Kosten).\u00a0Sind $$x_i$$ und\u00a0$$x_j = 0$$ (Standard wird nicht eingef\u00fchrt), so ist die Entscheidungsvariable\u00a0$$z_{ij} = 1$$ (uns entgehen Einsparungen und damit entstehen indirekte Kosten). Und da wir Interesse haben unsere gesamten<\/strong> Kosten zu minimieren, f\u00fchren wir beides nun zusammen.<\/p>\n $$\\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}$$<\/p><\/blockquote>\n Bei $$n=4$$ w\u00fcrde die ausgeschriebene Funktion wie folgt aussehen:<\/p>\n Das erste Summenzeichen: $$c_1x_1+c_2x_2+c_3x_3+c_4x_4$$ (direkte Kosten)<\/p>\n 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)<\/p>\n Zusammen:<\/p>\n $$c_1x_1+c_2x_2+c_3x_3+c_4x_4+s_{12}z_{12}+s_{13}z_{13}+s_{23}z_{23}+$$<\/p>\n $$s_{14}z_{14}+s_{24}z_{24}+s_{34}z_{34}$$<\/p><\/blockquote>\n Und das ist unsere ganze Minimierungsfunktion f\u00fcr 4 Knoten. Setzen wir die Kosten und Einsparungen mal ein.<\/p>\n Min $$300x_1+475x_2+513x_3+987x_4+800z_{12}+100z_{13}+217z_{23}+$$<\/p>\n $$315z_{14}+278z_{24}+165z_{34}$$<\/p><\/blockquote>\n Wir sind fast fertig. Uns fehlt nur noch eines.<\/p>\n Nebenbedingungen<\/strong><\/p>\n Wir haben diese zwar schon in Prosa formuliert, m\u00fcssen das aber in mathematischer Notation noch nachholen und eine kleine Ungenauigkeit beseitigen. Rekapitulieren wir: Folgende zwei Bedingungen sind zu formulieren:<\/p>\n Wir haben folgende F\u00e4lle zu unterscheiden:<\/p>\n Hier greift das Skript in die mathematische Trickkiste und formuliert alle 4 Bedingungen mit Hilfe einer gro\u00dfen, positiven Konstante $$M$$.<\/p>\n $$x_i + x_j >= 2 – M{z_{ij}}$$ (NB 1.5)<\/p><\/blockquote>\n Wenn wir f\u00fcr alle m\u00f6glichen F\u00e4lle die Werte in die Nebenbedingung einsetzen, muss die Nebenbedingung folgende F\u00e4lle abfangen und folgende Ergebnisse zur\u00fcckliefern:<\/p>\n $$1+1 >= 2 – (1000*0) = true$$ $$1+1 >= 2 – (1000*1) = true$$ Und das macht sie auch, rechnet das ruhig nach.<\/p>\n Bleibt nur noch NB 1.6. Aber die ist – das wollte ich immer schon einmal sagen – trivial.<\/p>\n $$x_i \\in\\{0,1\\}, z_{ij} \\in\\{0,1\\}, i=1,…,n, j = 1,…,n, i < j$$ (NB 1.6)<\/p>\n Sie sagt nichts weiter aus, als dass unsere Variablen bin\u00e4r sind und unser Z\u00e4hler $$i$$ kleiner als $$j$$ sein muss (w\u00e4re $$i\\leq j$$, so g\u00e4be es z. B. $$s_{11}$$, d. h. einen Einsparungsbetrag von Knoten 1 zu Knoten 1).<\/p>\n <\/p>\n","protected":false},"excerpt":{"rendered":" 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 … <\/p>\n\n
\n
\n
\n
\n
\n
\n
\n
\n
\n
\nDamit muss $$z_{ij}=1$$ (indirekte Kosten sind entstanden) sein. Ist\u00a0$$z_{ij}=0$$, so darf die NB nicht erf\u00fcllt sein.<\/li>\n
\n$$1+0 >= 2 – (1000*1) = true$$
\n$$0+1 >= 2 – (1000*1) = true$$
\n$$0+0 >= 2 – (1000*1) = true$$<\/p>\n
\n$$1+0 >= 2 – (1000*0) = false$$
\n$$0+1 >= 2 – (1000*0) = false$$
\n$$0+0 >= 2 – (1000*0) = false$$<\/p><\/blockquote>\n