Optimierung von Zahlenreihen < Optimierung < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
Hallo,
ich habe eine Menge von Zahlenreihen, welche ich analysieren moechte. Hierbei habe ich auf der x-Achse eine prozentuale Verteilung von 0 - 100 %. Auf der y-Achse habe ich einen Funktionswert, welcher zu optimieren ist. Nun habe ich n verschiedene Funktionen, welche so zu optimieren sind, dass die Summe der x-Werte gleich 100 % ist und moeglichst das Maximum der Funktionswerte in Summe erreicht wird.
Ich denke, dass es ein Optimierungsansatz ist, welcher entweder ueber die klassische Extremwertberechnung geht oder aber ueber numerische oder stochastische Optimumsberechnung.
Vielleicht hat ja jemand hier im Forum einen geeigneten Ansatz!
Ich habe diese Frage auch in folgenden Foren auf anderen Internetseiten gestellt: http://www.gute-mathe-fragen.de
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 13:58 Di 21.05.2013 | | Autor: | wieschoo |
Ich persönlich kann mir noch recht wenig darunter vorstellen. Ich glaube auch, dass viele, die den Text hier nur überfliegen, auch nicht gerade genug Informationen erhalten. Vielleicht kannst du es ja noch konkreter formulieren.
Was heißt auf nder x-Achse eine prozentuale Verteilung?
Kann aber auch nur mich betreffen. Vielleicht versteht es jemand anderes.
|
|
|
| |
|
Hallo,
danke erst einmal fuer dein Feedback. Sorry, dass es so weit nicht ganz verstaendlich war. Wenn man so gruebelt, dann ist man in einer eigenen Welt! 
Ich versuche nochmals das Modell zu beschreiben.
Die vorliegende Aufgabenstellung ist aus dem Gebiet des Operations Research. Es handelt sich dabei um eine Gewinnmaximierung.
Gegeben sind n verschiedene Kunden, die einen prozentualen Marktanteil
Die angesprochene prozentuale Verteilung auf der x-Achse ist der Marktanteil eines Produkts. Wenn wir davon ausgehen, dass es n Kunden gibt, so muss die Summe aller verkaufter Produkte gleich 100 % sein.
Die Kunden nun bezahlen unterschiedliche Preise, wobei die Preise, respektive der Gewinn der Funktionswert der jeweiligen Anteile darstellt.
Haben wir beispielsweise 3 Kunden mit den Funktionen f(x1) = 2x + 1, f(x2) = 7x-4 und f(x3) =3x -4 mit 0<= xi <= 100 und Summe(f(xi)) = 100.
Ich habe mal weitergeschaut und den Simples-Algorithmus gefunden, sowie ein Derivat dessen, dass Preprocessing (http://de.wikipedia.org/wiki/Simplex-Verfahren).
Vielleicht kennst du ein geeigneteres Verfahren hierzu.
Gruss
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 23:31 Di 21.05.2013 | | Autor: | wieschoo |
>
> Hallo,
>
> danke erst einmal fuer dein Feedback. Sorry, dass es so
> weit nicht ganz verstaendlich war. Wenn man so gruebelt,
> dann ist man in einer eigenen Welt!
Das sind wir alle
>
> Ich versuche nochmals das Modell zu beschreiben.
Ich versuche es mal so zu schreiben, was ich verstanden habe, in der Hoffnung das es stimmt. Es ist noch ziemlich wirr, weil du vom Marktanteil eines Kunden und eines Produktes sprichst.
Du hast n Kunden [mm] $k_1.k_2,\ldots,k_n$. [/mm] Und meinetwegen $m$ Produkte [mm] $P_1,P_2,\ldots ,P_m$, [/mm] die bei den Kunden unterschiedliche Nachfragen hervorrufen? Die Marktanteile der Produkte sind unabhängig vom Kunden gegeben durch [mm] $x_1,x_2,\ldots,x_m\in [/mm] [0,1]$ mit [mm] $\sum_{i=1}^m x_i=1$.
[/mm]
Jetzt wrd es komisch. Mir ist nocht nicht klar, wie deine x-Achse wirklich aussieht. U. a. sind auch ein paar Sätze unvollständig. Im Lückentext war ich nie gut.
Du hast kundenspezifische Gewinne. Ist der Marktanteil [mm] $x_i$ [/mm] gegeben so hat Kunde [mm] $k_j$ [/mm] die Nachfrage bzw. verursacht den Gewinn [mm] $f_j(x_i)$??
[/mm]
Und du möchtest die beste Verteilung der [mm] $x_i$ [/mm] berechnen?
Also
[mm] $\max_{x\in\IR^n} \sum_{j=1}^m \sum_{i=1}^n f_j(x_i)$ [/mm] u.d.Nb. [mm] $\sum_{i=1}^n x_i=1$ [/mm] und [mm] $x_i\in [/mm] [0,1]$
So jetzt sind deine [mm] $f_j$ [/mm] affin linear. Also Kannst du aus den vielen [mm] $f_j$ [/mm] eine gesamte Funktion bauen. Da fehlt also noch etwas. Sonst ist da nichts zu optimieren.
Wenn ich vielleicht noch einmal soetwas, wie ein MickeyMouse Beispiel vorschlagen kann. Ein kleines Beispiel für das Verständnis.
Simplex ist schon einmal gut. Da man alles linear schreiben kann. Bis jetzt ist es aber nur ein LGS.
Desweiteren ist bis jetzt auch die Verteilung der [mm] $x_i$ [/mm] für die Lösung irrelevant.
|
|
|
| |
|
Hallo,
die erwaehnte x-Achse soll eine Variable fuer den Produktanteil eines Kunden darstellen. Die Variable ist dann der prozentuale Anteil, welcher von 0 bis 100 geht. Wenn ich den Prozentsatz des Produktes dieses Kunden variiere, dann wird der zugehoerige Funktionswert, der Gewinn, sich auch verändern.
Graphisch sehe ich bei n Kunden n verschiedene Graphen im Koordinatensystem. Ich moechte nun die Koeffizienten der Anteile der verschiedenen Kunden an dem Produkt ermitteln. Dabei kann ich stets nur 100 % des Produkts verteilen. Und ich moechte gerne dieses Produkt am besten so verteilen, dass der Gewinn moeglichst hoch ist.
Ein trivialer Fall ist, dass einer der Kunden unabhängig von der gekauften Menge stets den hoechsten Preis bezahlt. Somit würde der Zielvektor (100,0,..,0)x sein.
Es kann jedoch auch sein, dass ein Kunde bei geringen Absaetzen einen sehr hohen Preis bezahlt und bei hohen Absaetzen einen geringeren Preis. Wenn bei einem anderen Kunden nun die Preisgestaltung anders ist, kann man dem einen Kunden x1 Prozent und dem anderen Kunden x2 Prozent des Produktes geben, so dass durch die Kummulation der beiden Gewinne das Optimum erreicht wird.
Gruss
|
|
|
| |
|
Hallo,
gerne wuerde ich die Konversation per Mail oder am Telefon weiterführen.
Gerne kannst du mich anmailen unter ica.erki@gmail.com.
Gruss
|
|
|
| |
|
Hallo,
das Thema ist etwas komplexer und nicht so einfach in Formeln oder formalen Beschreibungen hineinzupassen.
Das, was ich beschrieben habe ist so ziemlich alles, was die Anforderung hergibt. Vielleicht ist es auch nur eine triviale Kleinigkeit, die ich vergessen habe zu erwaehnen.
Aus dem Kontext heraus kann ich dazu sagen, dass ich das fuer ein Projekt brauche, wo es fachlich um die Ermittlung von Umsaetzen geht.
Es gibt in einem Land verschiedene Kunden, welche ueber einen prozuentalen Anteil des Verkehrs einen bestimmten Umsatz machen.
Das heisst, dass du in einem Land 3 Kunden hast, welche insgesamt 100 % Verkehr ausmachen.
Ich lasse nun in einer Funktion den Verkehr von 0 bis 100 % des Verkehrs gleiten. Somit erhalte ich entsprechende Umsatzwerte.
Wenn ich nun alle 3 Kurven uebereinander halte, so moechte ich ueber das Simplexverfahren gerne die bestmoegliche Verteilung erhalten.
Ich moechte spaeter die Algorithmik in Oracle umsetzen und habe dort die Funktion UTL_NLA.LAPACK_GESV gefunden. Vielleicht kennst du dich mit den Data Mining-Funktionen von Oracle auch aus.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 12:36 Di 28.05.2013 | | Autor: | wieschoo |
>
> Hallo,
>
> das Thema ist etwas komplexer und nicht so einfach in
> Formeln oder formalen Beschreibungen hineinzupassen.
> Das, was ich beschrieben habe ist so ziemlich alles, was
> die Anforderung hergibt. Vielleicht ist es auch nur eine
> triviale Kleinigkeit, die ich vergessen habe zu erwaehnen.
> Aus dem Kontext heraus kann ich dazu sagen, dass ich das
> fuer ein Projekt brauche, wo es fachlich um die Ermittlung
> von Umsaetzen geht.
> Es gibt in einem Land verschiedene Kunden, welche ueber
> einen prozuentalen Anteil des Verkehrs einen bestimmten
> Umsatz machen.
> Das heisst, dass du in einem Land 3 Kunden hast, welche
> insgesamt 100 % Verkehr ausmachen.
entspricht $ [mm] \sum_{k=1}^3x_{kp}=1\quad \forall [/mm] p $
Alle Anteile [mm] $x_{kp}$ [/mm] der ganzen Produkte summieren sich zu 1 auf.
> Ich lasse nun in einer Funktion den Verkehr von 0 bis 100
> % des Verkehrs gleiten. Somit erhalte ich entsprechende
> Umsatzwerte.
> Wenn ich nun alle 3 Kurven uebereinander halte, so moechte
> ich ueber das Simplexverfahren gerne die bestmoegliche
> Verteilung erhalten.
Sofern die Funktionen [mm] $f_t$ [/mm] aus meiner Antwort linear, geht das. Die Zielfunktion ist doch:
$ [mm] \max_{x\in \IR^{1\times pk}} \sum_{k=1}^n\sum_{p=1}^m f_k(x_{kp}) [/mm] $
Dabei suchst du einen Vektor (trotz der zwei Indizies, kann man x als Vektor auffassen) [mm] $x\in \IR^{1\times pk}$ [/mm] mit [mm] $p\cdot [/mm] k$ Einträgen, die alle zwischen 0 und 1 sind.
Der Eintrag [mm] $x_{14}$ [/mm] gibt den Anteil des Kunde $1$ am Produkt $4$. Eventuell muss man noch Nebenbedingungen ergänzen.
> Ich moechte spaeter die Algorithmik in Oracle umsetzen und
> habe dort die Funktion UTL_NLA.LAPACK_GESV gefunden.
> Vielleicht kennst du dich mit den Data Mining-Funktionen
> von Oracle auch aus.
|
|
|
| |
|
Wenn ich jetzt noch einmal drüber nachdenke meinst du mit Marktanteil der Kunden bestimmt die Nachfrage des Kundens.
Wir bezeichnen mit [mm]x_{kp}\in [0,1][/mm] den Nachfrageanteil (zwischen 0=0% und 1=100%) von Kunden [mm]k[/mm] beim Produkt [mm]p[/mm] mit [mm]k=1,\ldots,n[/mm] und [mm]p=1,\ldots,m[/mm].
Es gilt nach deinen Einschränkungen [mm]\sum_{k=1}^nx_{kp}=1\quad \forall p[/mm] und [mm]x_{kp}\ge 0[/mm] (sprich das Produkt wird völlig weggekauft von allen Kunden und man kann nur nichtnegative Anteile erwerben).
Der Kunde [mm]k[/mm] bezahlt den Preis [mm]f_k(x)[/mm], wobei [mm]x[/mm] der Anteil des Kundens ist und [mm] $f_k$ [/mm] irgendeine "Preishemmschwellenfunktion" vom Kunden k ist.
Dann ist das Optimierungsproblem gegeben durch
[mm]\max \sum_{k=1}^n\sum_{p=1}^m f_k(x_{kp})[/mm]
u.d.N [mm]\sum_{k=1}^n x_{kp}=1[/mm]
[mm]x_{kp}\ge 0[/mm]
Sind deine Zielfunktionen [mm] $f_k$ [/mm] linear in $x$, so kannst du mit nen Simplex drauf loschlagen. Sobald die nichtlinear sind hilft eine Rechenschlacht mit Karush-Kuhn-Tucker und der Lagrangefunktion weiter.
Ist das so, wie du das meinst? Oder gibt es noch weitere Einschränkungen. Das ist wohl die bestmögliche Antwort die man bei dem WirrWarr geben kann.
Gruß
wieschoo
|
|
|
| |
|
Hallo wieschoo,
die Antwort ist schon sehr praezise und ich denke, dass ich mit diesem Ansatz sicherlich weiterkomme.
Wenn ich die Matrizen fuer den Simples-Algorithmus aufstelle, so sehe ich bei 3 Kunden 4 Gleichungen mit
x1+x2+x3=100 (Prozent)
ax1+0x2+0x3=u
0x1+bx2+0x3=v
0x1+0x2+cx3=w
Diese Darstellung indiziert doch eine linear unabhängige Matrix. Wie ist dann hierbei der geeignete Lösungsweg?
Gruss
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 13:02 Di 28.05.2013 | | Autor: | wieschoo |
Die Nebenbedingungen ausgeschrieben sind doch bei 3 Kunden und 2 Produkten
[mm] $x_{11}+x_{21}+x_{31}=1 [/mm] $
[mm] $x_{12}+x_{22}+x_{32}=1 [/mm] $
[mm] $x_{ij}\ge [/mm] 0$
Du musst natürlich die Zielfunktion
$ [mm] \max_{x\in \IR^{1\times p\cdot k}} \sum_{k=1}^n\sum_{p=1}^m f_k(x_{kp}) [/mm] $
dann ausgeschreiben.
|
|
|
|
