Optimierungsaufgabe

[horst1]

Hallo,

Meine Aufgabe ist es einen Bedarf aus einer Menge von Beständen zu decken.

Bsp: Bedarf: 30

Bestände: 28,17,16,15,7,3,2,1,1

Lösungen:

28,2

28,1,1

16,7,3,2,1,1

17,7,3,2,1

Gibt es einen schlanken Algorithmus, der so etwas berechnet.

Und wenn ja, gibt er dann auch bei einer großen Anzahl von Beständen (mehrere Hundert) Lösungen in vertretbarer Zeit aus?

Vielen Dank schon mal!

[flashpixx]

Du kannst eine einfache Greedy-Strategie verwenden.

Aber das Problem, was Du nennst, ist als Rucksackproblem ? Wikipedia bekannt und NP vollständig, d.h. nicht effizient lösbar.

Evtl wäre es sinnvoll Randbedingungen zu kenne, denn je besser Du das Problem beschreiben kannst, um so besser kann man eine Heuristik nennen, die eine "gute" Lösung findet

[horst1]

Vielen Dank für die Antwort!

Es geht darum eine möglichst optimale Zusammenstellung zur Deckung des Bedarfs zu finden. Die Bestände haben alle noch ein Attribut "Standort". Jetzt könnte z.B. ein Ziel sein, den Bedarf nur mit Beständen aus einem Standort zu decken. Oder möglichst wenig Bestände zu verwenden.

Wie sähe denn der Algorithmus aus um alle Lösungen zu erzeugen? Den bekomme ich schon gar nicht hin...

[MartinSt]

Hast du dir den Wikipediaartikel durchgelesen und verstanden? Inklusive der Mathematik die dahintersteht?

Wie komplex deine Kosten- und Nutzenfunktion ist, also z.B. dann wenn der Standort mit in die Kosten eingeht, ist mathematisch irrelevant.

[horst1]

Mir ist schon klar, dass die Gewichtsfunktion an und für sich keine Rolle spielt. Hier geht es vorrangig um die Berechnung der verschiedenen Zusammenstellungen. Die Bewertung ist nicht das Problem.

Mit einem Greedy hatte ich es schon probiert, aber da sind mir zu viele gute Lösungen verloren gegangen. Deshalb wäre es schön, wenn mir jemand einen Ansatz über einen anderen Algo geben könnte, da ich mir schwer tue, andere Optimierungsalgorithmen auf dieses Problem zu übertragen.

[MartinSt]

aber da sind mir zu viele gute Lösungen verloren gegangen

Kannst du das mal genauer quantifizieren?

[flashpixx]

Mit einem Greedy hatte ich es schon probiert, aber da sind mir zu viele gute Lösungen verloren gegangen. Deshalb wäre es schön, wenn mir jemand einen Ansatz über einen anderen Algo geben könnte, da ich mir schwer tue, andere Optimierungsalgorithmen auf dieses Problem zu übertragen.

Man kann sicherlich "besser" optimieren z.B. Ameisenalgos, genetische Algos, Funktionsoptimierung (sofern Das Problem funktional beschreibbar ist), evtl auch Fuzzy, Clustering, Dimensionsreduktion und Kombinationen aus den Verfahren usw. nur alle Optimierungsheuristiken sind im worst-case nicht besser als ein Random-Verfahren, die Kunst liegt eben darin, dass man eben Randbedingungen definiert, die den Problemraum einschränken.

Ein Greedy ist sicherlich nur eine von vielen Approximationsmöglichkeiten. Aber ohne dass Du die Rahmenbedingen und evtl mal das spezifische Problem nennst, wird hier auch keine bessere Lösung genannt werden können.

Wichtiger Faktor wäre schon mal, dass Du Dich mit einer "guten" Näherung zufrieden geben musst. Liefere mehr Informationen für das konkrete Problem, dann kann man weiter sehen

[Pointerman]

Moin!

Wäre der Simplex-Algorithmus brauchbar für Dich?

Simplex-Verfahren ? Wikipedia

[flashpixx]

Wäre der Simplex-Algorithmus brauchbar für Dich?

ergänzend Lineare Optimierung ? Wikipedia

was z.B. mit dem Tool gut zu bearbeiten wäre Zimpl

[casio]

Ich hab da mal was geschrieben, vielleicht hilft es dir, jedenfalls komme ich zu deinem Ergebnis

Man müsste auch andere Fälle testen, um zu sagen, okay, das funktioniert so, wie ich es will ^^

int[] bestand = new int[] { 28, 17, 16, 15, 7, 3, 2, 1, 1 };

int bedarf = 30;


int r = 0;

string s = "";

for( int a = 0; a < bestand.Length-1; a++ ) {

	r = bestand[a];

	s = bestand[a] + " ";

	for( int b = a+1; b < bestand.Length; b++ ) {

		if( r + bestand[b] > bedarf ) {

			s = bestand[a] + " ";

			r = bestand[a];

		} else if( r + bestand[b] == bedarf ) {

			s = s + bestand[b] + " ";

			Console.WriteLine( s );

			r = bestand[a];

			s = bestand[a] + " ";		

		} else {

			s = s + bestand[b] + " ";

			r = r + bestand[b];

		}

	}				

}


[/PHP]

[casio]

seit wann kann man hier nicht editieren?? ...

letzte version hat bei anderen beständen nicht so funktioniert, wie sie sollte, hier eine überarbeitung ^^

int[] bestand = new int[] { 28, 17, 16, 15, 7, 3, 2, 1, 1 };

int bedarf = 30;


int r = 0;

string s = "";

for( int a = 0; a < bestand.Length-1; a++ ) {

	r = bestand[a];

	s = bestand[a] + " ";

	for( int b = a+1; b < bestand.Length; b++ ) {

	r = bestand[a];

	s = bestand[a] + " ";					

		for( int c = b; c < bestand.Length; c++ ) {

			if( r + bestand[c] > bedarf ) {

				s = bestand[a] + " ";

				r = bestand[a];

			} else if( r + bestand[c] == bedarf ) {

				s = s + bestand[c] + " ";

				Console.WriteLine( s );

				r = bestand[a];

				s = bestand[a] + " ";		

			} else {

				s = s + bestand[c] + " ";

				r = r + bestand[c];

			}						

		}

	}	

}

[/PHP]

Das thema ist komplexer als man denkt, für die menge "28, 2, 17, 16, 15, 7, 10, 3, 2, 1, 1" wird wieder nicht alles berücksichtigt... :/

Bearbeitet 27. Mai 2010 von casio

[flashpixx]

Das thema ist komplexer als man denkt, für die menge "28, 2, 17, 16, 15, 7, 10, 3, 2, 1, 1" wird wieder nicht alles berücksichtigt... :/

Ich wiederhole mich nur ungern, aber um die beste Lösung zu ermitteln, musst Du alle Lösungen durchrechnen (Tipp Rekursion). Bei n Zahlen ist das aber ein exponentieller Aufwand, so dass das eben nicht mehr effizient geht.

Wie schon mehrfach gesagt, definiere einmal Randparameter und was die Lösung sein soll. Optimierungsheuristiken gibt es sehr viele und je mehr Informationen über Dein Problem bekannt sind, um so besser kann man etwas entsprechendes finden

[wolfgang-11]

Hi

Ich mache mal einen Vorschlag, ist allerdings VB-Code

Private Sub bestand()

  Dim arrBestand

  arrBestand = Array(28, 17, 16, 15, 7, 3, 2, 1, 1)

  Dim i As Integer

  For i = LBound(arrBestand) To UBound(arrBestand)

    Call bestandSum(arrBestand, 30, 0, i, "")

  Next

End Sub


Private Sub bestandSum(arrBestand, intBedarf As Integer, _

                       intSum As Integer, intNextElmt As Integer, _

                       strResultList As String)

  Dim i As Integer

  Dim sumH As Integer

  For i = intNextElmt To UBound(arrBestand)

    sumH = intSum + arrBestand(i)

    If sumH = intBedarf Then

      Debug.Print strResultList & arrBestand(i)

    Else

      If sumH < intBedarf Then _

        Call bestandSum(arrBestand, intBedarf, sumH, i + 1, _

                        strResultList & arrBestand(i) & ", ")

    End If

  Next

End Sub

Und der erzeugt folgende Werte:

28, 2

28, 1, 1

17, 7, 3, 2, 1

17, 7, 3, 2, 1

16, 7, 3, 2, 1, 1

17, 7, 3, 2, 1

17, 7, 3, 2, 1

16, 7, 3, 2, 1, 1

16, 7, 3, 2, 1, 1

Und das müssten alle Lösungen sein.

Herzliche Grüße

Wolfgang

[flashpixx]

Und das müssten alle Lösungen sein.

Bitte bestimme einmal von Deinem Code die Komplexität und berechne das für ein beliebig großes Array.

NP-Schwere ? Wikipedia

NP-Vollständigkeit ? Wikipedia

Rucksackproblem ? Wikipedia

siehe:

Sie gehört zur Liste der 21 klassischen NP-vollständigen Probleme, von denen Richard Karp 1972 die Zugehörigkeit zu dieser Klasse zeigen konnte.

[wolfgang-11]

Bitte bestimme einmal von Deinem Code die Komplexität und berechne das für ein beliebig großes Array.

Habt ihr doch schon gemacht, oder?

Sie gehört zur Liste der 21 klassischen NP-vollständigen Probleme,

Richtig und sie gehört darüber hinaus auch zur Liste der Hausaufgaben eines Schülers und das oben ist die Lösung. In der Realität kommt niemand auf die Idee, dass nach einer Lieferung ein Lager geräumt sein muss - also Warenbestand 0 hat. Wenn ich bei den Lagerbeständen 30 Einheiten liefern sollte, dann würde ich in der Praxis die Zahl der Lieferungen klein halten, weil genau das die Kosten senkt. Also ich würde vielleicht 2*15 liefern aus der Liste der ersten 4 Lager.

Was zwingt mich - in der Realität - möglichst viele Läger auf Lagerbestand 0 zu setzen? Kann ich dann da die Heizung ausmachen und Strom sparen?

[MartinSt]

gehört darüber hinaus auch zur Liste der Hausaufgaben eines Schülers

Aha :uli

Welche Schule, welche Klassenstufe? Inkl. der mathematischen Theorie?

[wolfgang-11]

Aha :uli

Welche Schule, welche Klassenstufe? Inkl. der mathematischen Theorie?

Sorry falls ich mich vertan haben sollte aber das ist eine typische Aufgabe in der Schule ...

[flashpixx]

Richtig und sie gehört darüber hinaus auch zur Liste der Hausaufgaben eines Schülers und das oben ist die Lösung.

Also wenn ein Lehrer eine solche Aufgabe ausgibt, unterstelle ich ihm, dass er nicht weiß was die NP Klassen sind. Denn die Umsetzung eines solchen Problems erfordert mehr als die "Hau-Drauf-Methode" (rekursiv alles berechnen).

Wenn ein Lehrer eine solche Aufgabe stellt, ohne den Hinweis zu geben, dass man es so nicht (!) macht, zweifel ich stark das mathematische und algorithmische Wissen an. Es geht nicht darum etwas zu "coden", sondern sich vorher (!) Gedanken zu machen, wie man einen sinnvollen Lösungsalgorithmus entwickeln kann. Ein Erster, wie auch schon hier diskutierter Ansatz, wäre eine Greedy-Strategie. Sie liefert zwar nicht das Optimum, aber schon meine gute Näherung. Dieses Problem sprengt wohl jeden Rahmen eines Schulunterrichts, sowohl einmal aus Theorie, wie auch aus praktischer Sicht. Es gehört vielleicht dazu, dass man hier eben die Komplexitätsklassen erläutern kann und eben die Aussagen, dass man es nicht ohne Hintergrundwissen "gut" lösen kann. Aber eine Lösung im Rahmen des vorhandenen Schulstoffes (inkl. mathematischer Theorie) zu entwickeln, ist nicht mit Schulwissen nicht durchführbar.

Alle weiteren Optimierungsmöglichkeiten kommen auf den konkreten Fall an, denn Du bist bisher davon ausgegangen, dass die einzelnen Teile atomar sind, wenn es mir aber erlaubt ist ein Teil, das ich einstecken möchte zu teilen, dann wird das Problem schnell wesentlich komplexer, da ich nun nicht mehr auf der Zahlenmenge N, sondern auf R+ operiere. Wenn ich dann weiterhin als Bedingung hinzufüge, dass jedes Teil einen gewissen Wert hat und ich den Wert maximieren möchte, dann wird noch einmal schwieriger.

So einfach, dass man es mal eben schnell für eine handvoll Zahlen ausprobiert, ist dieses Problem nicht.

In der Realität kommt niemand auf die Idee, dass nach einer Lieferung ein Lager geräumt sein muss - also Warenbestand 0 hat. Wenn ich bei den Lagerbeständen 30 Einheiten liefern sollte, dann würde ich in der Praxis die Zahl der Lieferungen klein halten, weil genau das die Kosten senkt. Also ich würde vielleicht 2*15 liefern aus der Liste der ersten 4 Lager.

Was zwingt mich - in der Realität - möglichst viele Läger auf Lagerbestand 0 zu setzen? Kann ich dann da die Heizung ausmachen und Strom sparen?

Alles das nennt sich Nebenbedingungen, die man, wenn es sich um ein linear zu optimierendes Problem handelt, einsetzen kann, da aber innerhalb des Thread keine Randbedingungen genannt wurden, kann man somit dazu nichts aussagen.

Bearbeitet 10. Juni 2010 von flashpixx

[wolfgang-11]

Also wenn ein Lehrer eine solche Aufgabe ausgibt, unterstelle ich ihm, dass er nicht weiß was die NP Klassen sind.

Willst du damit implizit sagen, das sei eine Aufgabe aus der Relatität? Das kann ich mir nicht vorstellen.

Denn die Umsetzung eines solchen Problems erfordert mehr als die "Hau-Drauf-Methode" (rekursiv alles berechnen).

Warum? Natürlich werden solche Probleme in der Praxis so gelöst. Man weiß, dass Sie kritisch sind und beschränkt die Feldgröße und in dem Fall die Zahl der Lager. Die Zahl der Lager einer Firma zum Zeitpunkt x ist bekannt und damit klar, ob der Algorithmus brauchbar ist oder nicht.

Und das der Algorithmus zeitkritisch werden kann, das streite ich ja gar nicht ab. Hier in der Liste hatte nur eine Konkrete Lösung gefehlt zu den Codes hieß es nur "Der Code zeigt nicht alle Lösungen" und so habe ich einfach mal den Code geliefert. Wo ist jetzt dein Problem? Die Aufgabe hatte mich an früher erinnert und ich wollte noch wissen, ob ich den Code hinbekomme. Noch einmal: Wo ist das Problem?

Es geht nicht darum etwas zu "coden", sondern sich vorher (!) Gedanken zu machen, wie man einen sinnvollen Lösungsalgorithmus entwickeln kann.

Mir schon. Es war danach gefragt, keiner hatte es hinbekommen also habe ich es mal probiert.

Ein Erster, wie auch schon hier diskutierter Ansatz, wäre eine Greedy-Strategie.

Viel einfacher ist die Forderung vor der Berechnung die Lager nach Größe zu sortieren. Das erhöht die Geschwindigkeit meines Verfahrens enorm - ohne die Ornung zu ändern. Oder anders: Größere Feldgrößen sind drin.

wenn es mir aber erlaubt ist ein Teil, das ich einstecken möchte zu teilen, dann wird das Problem schnell wesentlich komplexer, da ich nun nicht mehr auf der Zahlenmenge N, sondern auf R+ operiere.

Das ist das gleiche Verfahren, liefert nur mehr Lösungen. Und durch den Wechsel von N -> R+ wird nur der Aufwand für einen Vergleich und die Summe etwas größer. Das ist nur ein Konstanter Faktor, der nichts an O(...) ändert.

Es gehört vielleicht dazu, dass man hier eben die Komplexitätsklassen erläutern kann und eben die Aussagen, dass man es nicht ohne Hintergrundwissen "gut" lösen kann.

Das habe ich an keiner Stelle bestritten ...

Ich habe nur - weil der gezeigte Code nicht funktioniert - einen Code geliefert, der funktioniert.

So einfach, dass man es mal eben schnell für eine handvoll Zahlen ausprobiert, ist dieses Problem nicht.

Doch es ist eine Lösung für das in der Frage genannte Beispiel.

Ich meine: Was du mir wirklich vorwerfen kannst - habe ich eben gesehen - ist dass meine Lösung falsch ist. Aber wenn Ihr nicht dran interessiert seid, dann brauche ich es auch nicht zu korrigieren.

Bearbeitet 10. Juni 2010 von wolfgang-11

[flashpixx]

Noch einmal: Wo ist das Problem?

Dass hier eine Pseudo-Lösung präsentiert wird, denn Dein Beispiel hat eine sehr geringe Anzahl von Daten, erweitere das ganze auf 1000, 10.000 oder 1.000.000 Elemente.

Mir schon. Es war danach gefragt, keiner hatte es hinbekommen also habe ich es mal probiert.

Auch hier hatte ich mehrfach geschrieben, dass es diverse Lösungsansätze für das Problem gibt, z.B. wäre für ein paar tausend Elemente das ganze gut mit Ameisenalgorithmen zu lösen. Zusätzlich hatte ich das Programm Zimpel verlinkt, das man auch zur Lösung verwenden kann, wenn es sich hier um ein duales Rucksackproblem bezieht.

Das ist das gleiche Verfahren, liefert nur mehr Lösungen. Und durch den Wechsel von N -> R+ wird nur der Aufwand für einen Vergleich und die Summe etwas größer. Das ist nur ein Konstanter Faktor, der nichts an O(...) ändert.

Das ganze kann auch unendlich viele Lösungen liefern, sofern nicht klar ist, wie ich die Partition eines Elementes betrachte. Wenn ich es allgemein Formuliere, dann ist jedes Element unendlich oft auf R+ partitionierbar.

Auch der Algorithmus für eine "gute" Partitionierungsstrategie ist ebenfalls eine Optimierungsheuristik, z.B. kann man so etwas über Guillotine-Schnitte mit Hilfe Genetischer Algorithmen lösen.

Das habe ich an keiner Stelle bestritten ...

Ich habe nur - weil der gezeigte Code nicht funktioniert - einen Code geliefert, der funktioniert. [...]

Ich meine: Was du mir wirklich vorwerfen kannst - habe ich eben gesehen - ist dass meine Lösung falsch ist. Aber wenn Ihr nicht dran interessiert seid, dann brauche ich es auch nicht zu korrigieren.

Wie schon gesagt, es geht nicht darum "Code" zu liefern, denn wenn ich das Problem so auffasse, dass man die Elemente auch partitionieren darf, würde Dein Code weiter ein gültiges und gutes Ergebnis liefern.

Ameisenalgorithmen und auch genetische Algorithmen konvergieren immerhin in ein lokales Optimum, was macht Dein Code?