Ganzzahlige Optimierung < Optimierung < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 10:53 Di 25.09.2012 | | Autor: | Drestro |
| Aufgabe | Hallo Leute, hoffe ihr könnt mir (mal wieder) helfen :)
Aufgabenbeschreibung:
Wir haben eine Tabelle.
Die Gesamtanzahl der Zeilen ist gegeben (n [mm] \in \IN).
[/mm]
Um die Sache verständlicher zu machen, sollte man sich die Zeilen als verschiedene Produkte vorstellen.
In den Spalten der Tabelle sind die verschiedenen Produktparameter für die jeweiligen Produkte gelistet.
Die Anzahl der Spalten, lässt sich natürlich auch einfach berechnen und befindet sich ebenfalls in den natürlichen Zahlen (m [mm] \in \IN)
[/mm]
Meine Aufgabe:
Wir legen nun die maximale Anzahl der Produktparameter fest. Sagen wir schränken die Spaltenanzahl auf 15 ein.
Zu berechnen ist nun, wieviele und welche Produkte aus der Tabelle entfernt werden um die restlichen Produkte wieder mit 15 Produktparameter darstellen zu können. |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Meine Frage:
Wie mache ich das? Ich habe mittlerweile meinen BSc in Wirtschaftsmathe nur habe ich die Vorlesung "Ganzzahlige Optimierung" nie gehört. Ich versuche mich momentan durch verschiedene Websites schlau zu lesen.
Bevor ich aber eigenhändig ohne große Vorkenntnisse(LOpt kann ich noch ja...) versuche mir irgendwas auszudenken, könntet ihr mir BITTE auf die Sprünge helfen.
Hoffe die Aufgabenstellung war in soweit verständlich.
Schonmal Vielen Dank im Vorraus
Drestro
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 20:06 Mi 26.09.2012 | | Autor: | Stoecki |
> Hallo Leute, hoffe ihr könnt mir (mal wieder) helfen :)
>
>
> Aufgabenbeschreibung:
>
> Wir haben eine Tabelle.
> Die Gesamtanzahl der Zeilen ist gegeben (n [mm]\in \IN).[/mm]
> Um
> die Sache verständlicher zu machen, sollte man sich die
> Zeilen als verschiedene Produkte vorstellen.
>
> In den Spalten der Tabelle sind die verschiedenen
> Produktparameter für die jeweiligen Produkte gelistet.
> Die Anzahl der Spalten, lässt sich natürlich auch
> einfach berechnen und befindet sich ebenfalls in den
> natürlichen Zahlen (m [mm]\in \IN)[/mm]
>
> Meine Aufgabe:
>
> Wir legen nun die maximale Anzahl der Produktparameter
> fest. Sagen wir schränken die Spaltenanzahl auf 15 ein.
> Zu berechnen ist nun, wieviele und welche Produkte aus der
> Tabelle entfernt werden um die restlichen Produkte wieder
> mit 15 Produktparameter darstellen zu können.
> Ich habe diese Frage in keinem Forum auf anderen
> Internetseiten gestellt.
> Meine Frage:
> Wie mache ich das? Ich habe mittlerweile meinen BSc in
> Wirtschaftsmathe nur habe ich die Vorlesung "Ganzzahlige
> Optimierung" nie gehört. Ich versuche mich momentan durch
> verschiedene Websites schlau zu lesen.
ich vermute hier einfach mal, dass die anzahl der produkte maximiert werden soll?
>
> Bevor ich aber eigenhändig ohne große Vorkenntnisse(LOpt
> kann ich noch ja...) versuche mir irgendwas auszudenken,
> könntet ihr mir BITTE auf die Sprünge helfen.
>
> Hoffe die Aufgabenstellung war in soweit verständlich.
>
> Schonmal Vielen Dank im Vorraus
>
> Drestro
überlege dir folgendes: zu entscheiden ist, was die variablen darstellen. in deinem fall geht es darum zu entscheinden, ob ein produkt (oder eine zeile) behalten wird oder nicht. also hast du n variablen, die die werte 0 oder 1 annehmen können. zu maximieren wäre dann die summe dieser variablen.
zu den nebenbedingungen:
die sind etwas tricki:
ein ansatz wäre es änlich wie bei der standardlinearisirung von quadratischen 0-1 problemen zu machen. sagen wir es gibt k produkte, die das item i enthalten. dann gelte [mm] y_i \ge (\sum_{j \in P(i)} \frac{x_j}{k}) [/mm] - 1 , wobei P(i) die menge aller indices von produkten ist, die i benötigen. [mm] y_i \in \{0, 1\}
[/mm]
zudem muss dann noch gelten, dass [mm] \sum_{l=1}^{m}y_l \le [/mm] 15 (also maximal 15 produkte sollen verwendet werden. das y steht demnach dafür, ob ein vorprodukt verwendet wird oder nicht
dieses IP wird dein problem zumindest schon mal lösen, allerdings warne ich schon mal, dass es numerisch etwas unschön ist und deswegen wahrscheinlich eine relativ lange berechnungsdauer haben wird. daher würde ich in deiner stelle, wenn du das lösen willst erstmal versuchen eine sehr gute primale lösung zu finden (mittels heuristik). das wird die rechenzeit ziemlich sicher um einiges drücken können
gruß bernhard
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 10:28 Do 27.09.2012 | | Autor: | Drestro |
Hallo Bernhard,
danke für deine Antwort :)
Ich habe das Problem gestern nachmittag sehr ähnlich gelöst.
Als erstes, habe ich wie du die einzelnen Zeilen/Produkte als 0/1 Variablen „definiert“ und dann durch Maximieren ihrer Summe die Zielfunktion hergeleitet. Meine Nebenbedingungen sahen deinen auch recht ähnlich.
Da ich die mathematischen Verfahren (oder Lösungsansätze) dazu nicht kannte, habe ich mich dann allerdings für eine doch sehr… unmathematische Herangehensweise entschieden.
Zuerst wollte ich überhaupt eine Lösung finden, die vielleicht nicht optimal war, allerdings vom der/einer Optimallösung schon recht nah dran sein könnte oder zumindest äußerst selten weit davon entfernt, lag(nun weiß ich, dass man das Heuristik nennt :P).
Dazu folgendes:
Über die Items/Produktparameter/Spalten-Anzahl m, sowie deren jeweiligen Häufigkeit [mm]\sum_{i=1}^{n}x_{ij}\forall[/mm] j [mm] \in [/mm] m (i entspricht der Zeile, j der Spalte) und dem Wissen, dass m-15 Spalten wegfallen mussten, konnte ich eine erste Lösung generieren. Natürlich entschied ich mich, für m-15 Spalten mit der geringsten Häufigkeit.
Durch diese erste Lösung ermittelte ich eine Zeilenanzahl n_opt, die meine ursprüngliche Lösungsmenge hoffentlich stark verkleinern könnte (Lösungsmenge = [mm] \frac {m!}{15!*(m-15)!} [/mm].
Für jede Spalte [mm] m_i [/mm] muss gelten: Anzahl der Einträge [mm] m_i [/mm] < n_opt, da ansonsten keine optimalere Lösung mit dieser Spalte zu erzielen war( bei = könnte man höchstens eine äquivalent gute Lösungen finden und dies kostet zuviel Rechenzeit).
Mit dieser neuen Anzahl an Spalten hatte ich eine neue Lösungsmenge gefunden, welche nach obiger Formel berechnet wurde.
Der Rest war dann rein iterativ:
Nehme Spalte [mm] x_1 [/mm] aus Kombination [mm] c_1, [/mm] schaue ob die Summe aller Spalteneinträge <n_opt ist
Wenn ja, addiere Spalte [mm] x_2 [/mm] aus Kombination [mm] c_1, [/mm] und schaue ob die Summe aller Spalteneinträge < n_opt. Wenn ja, nächste Spalte
Wenn nein, Kombination keine optimalere Lösung => Kombination verwerfen, nächste Kombination
Wenn durch aufaddieren aller Spalten einer Kombination die Summe aller Spalteneinträge immer noch < n_opt war, hatten wir eine neue optimale Lösung gefunden.
Die restlichen Kombinationen wurden dann nach demselben Schema behandelt nur, dass nun zuerst in jeder Kombination die Bedingung „Summe Spalteneinträge < n_opt“ überprüft wurde.
Grüße
Andreas
P.S.
Keine Ahnung OB die Lösung gut ist, Sie funktioniert halt. Wenn du oder ein anderer User eine bessere Idee hat, bitte melden.
P.P.S.
Tut mir leid, aber nach 10 minuten durchlesen und ausprobieren, klappte es mit den Formeln IMMER noch nicht. Hoffe es ist dennoch verständlich
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:08 Do 27.09.2012 | | Autor: | Stoecki |
wenn du die exakte lösung haben möchtest benötigst du ein branch and bound (oder branch and cut) verfahren. das kann dir dann auch die optimale lösung berechnen. allerdings ist die rechenzeit exponentiell. schau für libraries zum beispiel mal auf coin-or.org. dort gibts open source software
gruß bernhard
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:13 Do 27.09.2012 | | Autor: | Drestro |
Hey Bernhard,
also so wie ich das sehe, berechnet mir mein Algorithmus schon eine/die optimale Lösung.
Für mich war halt nur die Frage, ob ich das noch schneller machen kann, als ich es gerade tue.
Ich habe nur soviel erklärenden Text geschrieben, weil ich auf die schnelle meinen Gedankenvorgang nicht in Matheformeln packen konnte.
|
|
|
|
