Prolemstellung 5 Türme



  • Hi, sry für den nicht so treffenden Titel.

    Ich bin dabei ein programm zu schreiben welches 2 Größen, in meinem Fall Eisen und Titan einliest.
    Ich habe 5 Türme zur Auswahl, alle benötigen verschieden viele Rohstoffe.
    Jetzt will ich mit den Größen ausrechnen wie meine beste Zusammensetzung der Türme auszusehen hat um möglichst so wenig wie möglich an titan und eisen noch übrig zu haben.

    Ich habe es mit 5 For schleifen probiert, aber wenn man da etwas größere Werte für Eisen und Titan angibt, kommt das ergebnis erst sehr spät bzw. garnicht. 😞

    Ich lasse alle schleifen so lange hochzählen bis keine türme(der jeweiligen schleife) mit den verfügbaren ressis mehr gebaut werden können. Vergleich das immer mit den anderen, so werden alle variationen durchgelaufen und mit der restberechnung dann die genommen wo am wenigsten über bleibt. Bei 5 Schleifen(5 Türme) kann das natürlich dauern wenn man 1mio. Rohstoffe eingibt. ein Turm braucht ja nur 100 oder so...

    Gibt es da vielleicht einen kleinen trick in der Mathematik um das schneller zu lösen?



  • Wenn du etwas mehr Infos rüber wachsen lässt.
    Z.B. über die Berechnungsvorschriften, etc.



  • Ich habe z.B. 1mio. Eisen und 800.000 Titan zur verfügung.
    Turm 1 benötigt: Eisen: 500 Titan: 100
    Turm 2 benötigt: Eisen: 1000 Titan: 250
    Turm 3 benötigt: Eisen: 3000 Titan: 600
    Turm 4 benötigt: Eisen: 5000 Titan: 6000
    Turm 5 benötigt: Eisen: 7500 Titan: 2000

    Jetzt möchte ich ausrechnen wieviel ich von jedem Turm bauen muss um möglichst wenig von den Eisen und Titan übrig zu haben.
    Hoffe das es jetzt deutlich ist...
    Mit meinen 5 FOR - Schleifen funtioniert das schon, nur dauert es eben viel zu lang.... 😞



  • Stichwort: Mathematische Optimierung



  • Das ganze lässt sich als lineares Programm formulieren, allerdings nur als ganzzahliges. Die sind aber leider nicht so leicht zu lösen, zumindest allgemein nicht. Du kannst aber natürlich versuchen eine normales lineares Programm zu lösen und das zu runden. Damit bekommst Du eine approximative Lösung. Alternativ könntest Du auch versuchen ähnlich wie beim KNAPSACK-Problem mit einem dynamischen Programm eine optimale Lösung zu bestimmen.



  • Danke, ich hab mir das mal durchgeschaut und irgendwie blick ich diese Formeln nicht... nagut, vielleicht auch noch etwas zu früh. 😞
    schade, aber thx



  • http://de.wikipedia.org/wiki/Subset_Sum

    Das ist doch genau dein Problem, oder nicht?

    Habe den Thread jetzt nur kurz ueberflogen.



  • Jester schrieb:

    Du kannst aber natürlich versuchen eine normales lineares Programm zu lösen und das zu runden.

    Zufälligerweise kommt bei den gegebenen Werten sogar eine ganzzahlige Lösung heraus, wenn man es als Standard Lineares Optimierungsproblem formuliert. 😉



  • Jo, aber ich versteh diese Formeln in Wikipedia nicht. 😞
    vielleicht kann mir wer diese hier kurz übersetzen damit ichs auch versteh? Wäre echt ein netter zug. Sry, hab bis jetzt wenig mit sowas zu tun, aber ich bin lernwillig und würde solche formeln gern verstehn...

    http://de.wikipedia.org/wiki/Subset_Sum

    Gruß



  • Gustl schrieb:

    [...]

    http://de.wikipedia.org/wiki/Subset_Sum

    Das ist nicht so richtig das was du suchst, in Bezug auf deine "Aufgabe" suchst du Folgendes http://de.wikipedia.org/wiki/Ganzzahlige_lineare_Optimierung. Um besser zu verstehen woher das kommt solltest du dich mit http://de.wikipedia.org/wiki/Lineare_Optimierung beschäftigen.

    Bücher die sich eingehend mit der Lösung solcher Probleme beschäftigen sind:

    Operations research : quantitative Methoden zur Entscheidungsvorbereitung / von Werner Zimmermann
    Operations Research : Einführung / von Frederick S. Hillier und Gerald J. Lieberman

    Wenn dir lineare Gleichungssysteme, Matrizen, Vektoren usw. nichts sagen schau z.B. in folgendes Buch:

    Lineare Algebra : Einführung, Grundlagen, Übungen / Howard Anton

    Falls dir das Summenzeichen grundsätzlich nichts sagt:

    http://de.wikipedia.org/wiki/Summe.
    http://www.mathe-online.at/materialien/klaus.berger/files/Summen/rechenregelnsummen.pdf



  • Meine interpretation der Geschichte ist, dass es dadurch, dass 5 Variablen auf 2 Gleichungen verteilt sind, davon abhängig wird, welche Art von Türmen bevorzugt wird.

    Also folgende Gleichungen habe ich:
    http://img406.imageshack.us/img406/7565/mathejj0.png

    Und als 3-D Graph:
    http://img360.imageshack.us/img360/4400/mathe2pw5.png

    Nun kann man die Formel jeweil nach einer Variablen ableiten und den Hochpunkt bestimmen, jedoch bleibt es dabei, dass es keine feste Lösung gibt.
    Vielleicht sollte man eine Art "Bewertungsgleichung" zusätzlich einfügen, oder die Zahl der Türme begrenzen, da man auf der o.g. Ebene einen beliebigen Punkt für eine Lösung wählen kann.



  • Hi,

    was du da plottest sind verschiedene seitenflächen eines 5-dimensionalen polyeders, nämlich des polyeders in dem deine lösungen drin sind.

    sei x_i die anzahl der Türme vom Typ i, E_i eisen für turm vom typ i und T_i eisen vom Typ i. Dann soll gelten:

    alle x_i ganzzahlig
    x_i >= 0 für alle i
    Summe x_iE_i <= GesamtEisen
    Summe x_i
    T_i <= GesamtTitan

    das beschreibt ein 5-dimensionales polyeder bei 5 verschiedenen turmtypen. Jetzt müssen wir noch sagen, was wir optimieren wollen. beispielweise

    minimiere f(x) = Summe GesamtEisen-Summe(x_i*E_i) + GesamtTitan - Summe(x_i*T_i)

    lässt du das x_i ganzzahlig weg, so gibt es standard-verfahren um solche optimierungsprobleme zu lösen (--> Lineare Programmierung). Allerdings ist die Lösung dann unter Umständen nicht mehr ganzzahlig. Aber du kannst die Anzahl der Türme für jeden Typ ja einfach abrunden. Dadurch wird's vermutlich nicht so viel schlechter. In Deiner speziellen Instanz scheint sich laut TheTester ja sogar automatisch eine ganzzahlige Lösung zu ergeben.



  • wurst schrieb:

    Meine interpretation der Geschichte ist, dass es dadurch, dass 5 Variablen auf 2 Gleichungen verteilt sind, davon abhängig wird, welche Art von Türmen bevorzugt wird.

    Also folgende Gleichungen habe ich:
    http://img406.imageshack.us/img406/7565/mathejj0.png

    Und als 3-D Graph:
    http://img360.imageshack.us/img360/4400/mathe2pw5.png

    Nun kann man die Formel jeweil nach einer Variablen ableiten und den Hochpunkt bestimmen, jedoch bleibt es dabei, dass es keine feste Lösung gibt.
    Vielleicht sollte man eine Art "Bewertungsgleichung" zusätzlich einfügen, oder die Zahl der Türme begrenzen, da man auf der o.g. Ebene einen beliebigen Punkt für eine Lösung wählen kann.

    Differenzieren bringt hier nichts da nur positive, ganzzahlige Lösungen zulässig sind. Und ich denke nicht, dass man die Differentialrechnung in geeigneter Weise auf die natürlichen Zahlen verallgemeinern kann.



  • Da danke ich euch für die qualifizierten Antworten, super Forum. 🙂
    Muss mich jetzt nur ausgiebig damit befassen, damit ich das auch wirklich verstehen kann, wie gesagt, ist Neuland für mich.

    MfG
    Gustl



  • @wurst:
    Wie kommst du von den b=-100d+12000-10e
    auf 1/2b + 50d + 5e - 6000 = 0 ?
    muss man da nicht einfach nur -b machen?



  • und wie rechne ich dann mit den 3 unbekannten b,d und e weiter?

    soll ich da dann 3 schleifen durchführen wo die gleichung dann annähernd 0 ergibt?

    ist ja auch mehr oder weniger glück das sich c hier rauskürzt.
    aber wie rechne ich dan a aus wenn ich c nicht hab... oh weh oh weh 😮 😞



  • vergiss den ansatz, der bringt dich nicht wirklich weiter. für die linearen Programme (das was ich vorgeschlagen hatte) gibt es Standardsoftware, die sowas lösen kann. Etwa lpsolve um ein freies zu nennen. Da kannst Du das mehr oder weniger so eingeben und kriegst die lösung rausgespuckt.



  • Ich weiß auch nicht so recht, was ich da gemacht habe. Außerdem habe ich am anfang willkürlich a gleichgesetzt und c hat sich "glücklicherweise" auf beiden Seiten aufgelöst.

    Wie bereits von den anderen Gesagt, die Sache ist viel zu Variabel, man muss weitere Bedingungen einfügen, damit man da irgendetwas Sinnvoll lösen kann.

    PS: Ableitung einer linearen gleichung? Wat hab ik denn geraucht?



  • PPS:

    Gustl schrieb:

    @wurst:
    Wie kommst du von den b=-100d+12000-10e
    auf 1/2b + 50d + 5e - 6000 = 0 ?

    Ich hab da "einfach" mit nem Program rechtsklich Solve to b und d gemacht und bei der eigentlichen gleichung auf Simplify geklickt...



  • wurst schrieb:

    PPS:

    Gustl schrieb:

    @wurst:
    Wie kommst du von den b=-100d+12000-10e
    auf 1/2b + 50d + 5e - 6000 = 0 ?

    Ich hab da "einfach" mit nem Program rechtsklich Solve to b und d gemacht und bei der eigentlichen gleichung auf Simplify geklickt...

    spanisch? 😃


Log in to reply