matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenDiskrete OptimierungGanzzahlige Optimierung
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Informatik • Physik • Technik • Biologie • Chemie
Forum "Diskrete Optimierung" - Ganzzahlige Optimierung
Ganzzahlige Optimierung < Optimierung < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Diskrete Optimierung"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Ganzzahlige Optimierung: Aufgabe
Status: (Frage) beantwortet Status 
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

        
Bezug
Ganzzahlige Optimierung: Antwort
Status: (Antwort) fertig Status 
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

Bezug
                
Bezug
Ganzzahlige Optimierung: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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


Bezug
                        
Bezug
Ganzzahlige Optimierung: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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

Bezug
                                
Bezug
Ganzzahlige Optimierung: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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.

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Diskrete Optimierung"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.matheraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]