Diskussion:Zyklenmethode

Alte Diskussion

Das angeführte Beispiel wurde aber nicht optimal gelöst!

Hätte man die Matrixminimummethode angewandt (auch Least-Cost-Verfahren) zur Erzeugung einer Startlösung, hätte man dort bereits eine Lösung hervorgebracht, die besser ist, als die Lösung nach der letzten Iteration!

Die Lösung sieht so aus:

   |B 1| B2| B3 |
---------------------
A1 |7/ |4/ |3/ |
   |  0|  6|  6| 12
---------------------
A2 |5/ |5/ |6/ | 
   |  4|  4|  0|  8
---------------------
   |  4| 10|  6| 20

Mit dieser Lösung komme ich auf Gesamtkosten von 82.

Hatte mich verhauen, wahrscheinlich nicht alles korrekt aus dem Konzept abgeschrieben. Mit diesem Editor hier werde ich immer ganz hibbelig. Müsste jetzt stimmen, danke. Es mag sein, dass die Matrixminimummethode effizienter ist. Sie war aber nicht der Gegenstand des Artikels. Gruß --Philipendula 11:21, 10. Mär. 2007 (CET)

Der Editor macht mich auch wahnsinnig, lass mal ;) Es scheint jetzt zu stimmen. Es geht auch nicht darum, dass die Matrixminimummethode effizienter ist. Es ging mir viel mehr darum, dass das Beispiel nicht korrekt durchgezogen war, da die Stepping-Stone-Methode als iteratives Lösungsverfahren ja versuchen soll, ein lineares Optimierungsproblem optimal zu lösen und wenn ich selbst mit einem normalen Verfahren schon eine Initiallösung erzeuge, die besser ist, als die angeblich optimale Lösung nach zig Iterationen, kann die Iteration nicht korrekt gewesen sein ;)

Natürlich war sie nicht korrekt. Ich hatte ja den letzten Schritt vergessen. Man darf halt nicht übersehen, dass diese Methode zu den ersten Verfahren in dieser Richtung gehört. Sie wird heute vor allem zu Demonstrationszwecken verwendet, weil sie auch für den Laien nachvollziehbar ist. Speziell das vorliegende Beispiel war ja auch sehr popelig, da ist es kein Wunder, wenn ein effizienter Algorithmus das in Null-Komma-nix rauskriegt. --Philipendula 17:04, 10. Mär. 2007 (CET)

Hey, das war wirklich nicht böse gemeint oder so :) Ich hatte selber neulich Probleme mit dem Stepping-Stone-Verfahren (weil ich es beim MODI-Verfahren benutze) und ich bin da auf einen sehr interessanten Teil gestoßen, der selten in Literatur zu finden ist: Es kann nämlich passieren, dass diese Pfade nicht die Form eines Rechteckes haben sondern "verschnörkelt" sind, weil im Grunde sehr viel im Tableau gesprungen werden muss, um einen Pfad zu finden. Sollte man das vielleicht auch mit erwähnen oder wäre das zuviel?

Bin ja nicht eingeschnappt :). Das mit dem Verschnörkeln stimmt. Ist sicher erwähnenswert. Aber das könnte man eigentlich nur mit einem Beispiel wirklich anschaulich erklären. Aus dem Stand fällt mir keins dazu ein, es sei denn, man klaut eins. Ich hab mal eine dürre Bemerkung dazu gemacht. Übrigens kannst du mit --~~~~ unterschreiben. Das erscheint dann in Klarschrift als Signatur. Gruß --Philipendula 17:55, 10. Mär. 2007 (CET)

Okay, wollte mich nicht streiten oder dergleichen :) Ich hätte ein Beispiel parat, wo das passieren kann, allerdings entstammt dieses Beispielproblem (also nur die Zahlenwerte für die Kosten, Nachfrage und Angebote) aus einer Diplomarbeit, die ich nicht geschrieben habe. Das Verschnörkeln tritt in diesem Beispiel genau dann auf, wenn ich die Lösung des Matrixminimumverfahrens als Startlösung wähle und danach iteriere. Dies ist aber in der Diplomarbeit nicht so zu finden, dort wurden andere Verfahren gewählt wo es durch Glück nicht passiert. Soll ich die Zahlenwerte versuchen anpassen? Kannst du das dann schön formatieren, ich tue mich hier sehr schwer.--Andreas

Ich habe zwei Lehrbücher, wo das auftaucht. Ich habe nur Bedenken, dass es vielleicht ein Plagiat sein könnte, wenn man das übernimmt. Ich denke, das Entstehen einer Schleife ist Zufall. Es kommt wohl auch darauf an, wie die Zellen angeordnet sind, damit so eine Schleife entsteht. Vielleicht ginge es, ein bestehendes Beispiel, etwa mit 3 Zeilen und 4 Spalten zu nehmen. Dann könnte man mal versuchen, Zeilen und Spalten zu tauschen. Möglicherweise ergibt sich dann aus einem Kreis von selber so eine Acht. Ich könnte es schon formatieren, werde aber vielleicht vor nächstem Donnerstag nicht dazu kommen. --Philipendula 19:43, 10. Mär. 2007 (CET)

Ich mache mal einen Vorschlag: Ich poste ein modifiziertes Beispiel hier und wie jetzt eine Schleife entstehen kann, okay?

   |B 1 | B2 | B3 | B4
---------------------
A1 |10/ |10/ |23/ |29/ |
   |   6|   6|  -1|  -1| 12
---------------------------
A2 |7/  |16/ |7/  |16/ |
   |  10|  -1|  -1|  -1| 10
---------------------------
A3 |21/ |11/ |18/ |15/ |
   |  -1|   0|  10|   8| 18
---------------------------
   |  16|   6|  10|   8| 40

Diese Lösung wurde mit dem Matrixminimumverfahren erstellt und es können immer wieder, egal bei welchem Verfahren, solche Fälle eintreten. Alles wo diesmal -1 steht, das sind die Nichtbasisvariablen, weil wir mit 0 in Zelle A3B1 eine degenerierte Basisvariable haben. Schaut man nun drüber, so ergibt sich an Stelle A2B3 eine Zelle, in die Einheiten transferiert werden können, um die Kosten zu minimieren. Da der Pfad aber nur aus einer Nichtbasisvariable bestehen kann, nämlich unsere Zelle A2B3, und der Rest Basisvariablen sein müssen, können wir diesmal kein Rechteck erzeugen. Diesmal geht der Pfad so: Wir beginnen bei A2B3, gehen dann südlich zu A3B3, dann westlich zu A3B2, dann nördlich zu A1B2, dann wieder westlich zu A1B1, dann südlich zu A2B1 und dann östlich zu A2B3. Schon haben wir eine Schleife gezogen. --Andreas

Mir ist nicht recht klar, warum man hier die Nicht-Basisvariablen mit -1 bezeichnen muss. Warum die Variablen Null sind, ist doch eigentlich für die Entstehung der Schleife unerheblich. Gruß --Philipendula 09:55, 13. Mär. 2007 (CET)

Man kann sie auch mit -2 bezeichnen, das ist egal ;) Es geht bloß um einen besonderen Fakt. Beim Stepping-Stone Verfahren darf nur eine einzige Variable eines Pfades eine Nichtbasisvariable sein. Dies ist per Definition auch immer die Variable, die eben eine Kostensenkung herbeiführt und somit eben die erste Variable eines Pfades. Weiter darf keine weitere Nichtbasisvariable direkt bei einem Pfad betreten werden. In der Zelle A3B2 haben wir jetzt einen Sonderfall. Hierbei handelt es sich um eine so genannte degenerierte Basisvariable, da sie den Wert 0 trägt und somit ansich gar keinen Wert beisteuert. Allerdings ist die Existenz dieser Basisvariable notwendig, da die Anzahl der Basisvariablen immer, bei n Zeilen und m Spalten, n+m-1 beträgt. Da wir nun aber diese degenerierte Basisvariable von einer Nichtbasisvariable unterscheiden müssen, sollten der Übersicht halber die Nichtbasisvariablen einen anderen Wert als >= 0 haben. --Andreas

Ich denke, wir sollten, wenn es um die reine Verdrillung des Kreises geht, ein Beispiel wählen, dass nicht auch noch die Verkomplizierung durch die Degeneration enthält. Das erschwert die Verständlichkeit. Man könnte ev. in einem eigenen Beispiel auf die Degeneration eingehen. Gruß --Philipendula 11:54, 14. Mär. 2007 (CET)--Philipendula 11:54, 14. Mär. 2007 (CET)

Das stimmt, da haste Recht. Ich habe mal schnell das Beispiel etwas geändert, sollte jetzt hinkommen.

   |B 1 | B2 | B3 | B4
---------------------
A1 |10/ |10/ |23/ |29/ |
   |   6|   6|   0|   0| 12
---------------------------
A2 |7/  |16/ |7/  |16/ |
   |  10|   0|   0|   0| 10
---------------------------
A3 |21/ |11/ |18/ |15/ |
   |   0|   1|  10|   8| 19
---------------------------
   |  16|   7|  10|   8| 40

Der Pfad usw. bleibt alles derselbe und für die Startlösung das Matrixminimumverfahren zu nutzen, sollte die gleiche Lösung hervorbringen. --Andreas

Oki, danke. Ich schaus mir bei Gelegenheit mal an. Gruß --Philipendula 14:05, 14. Mär. 2007 (CET)

Unvollständig

Es fehlen noch folgende Punkte:

• Maximierung statt Minimierung. (Bei der Iteration wird die größte Bewertung und nicht kleinste Bewertung genommen)
• Einführen von "Dummy" Anbietern, Nachfragern bei Angebot Überschuss/Mangel. (Kostenkoeff 0 bei Minimierungsproblem, Kostenkoeff. M bei Maximimierungsproblem)
• Bestimmte Routen dürfen nicht genutzt werden (bei Minimierungproblem Kostenkoeff. M) Bei Maximierungproblem Kostenkoeff 0.--Harald321 (Diskussion) 23:00, 10. Aug. 2015 (CEST)