Suche nach Unbekannter - Lösung mit Hilfe linearer Optimierung?

15.04.2014, 00:49

Seminarulix

Suche nach Unbekannter - Lösung mit Hilfe linearer Optimierung?

Guten Abend Zusammen,

im Rahmen einer Studienarbeit bin ich beim Weiterentwickeln eines etablierten Konzepts aus der Forschung auf ein Problem gestoßen eine Unbekannte zu ermitteln. Leider weiß ich nicht weiter wie ich diese Ermitteln kann, oder ob die überhaupt möglich ist. Im folgenden habe ich versucht das ganz auf das Nötigste herunter zu brechen. Mich würde es sehr freuen, wenn jemand mir einen Denkanstoß geben könnte wie ich ich im Folgenden Vorgehen könnte.

Gegeben seien Elemente i={1,...,n}

bekannt sind:
$\begin{eqnarray*} s_{i} a_{i} d_{i} q_{i} y_{i} \end{eqnarray*}$

gesucht ist
$\begin{eqnarray*} z_{i} \end{eqnarray*}$

wobei
$\begin{eqnarray*} p_{i} = y_{i} * z_{i} s_{i} + p_{i} \geq a_{i} s_{i} + p_{i} \leq d_{i} \sum\limits_{i=1}^n p_{i} = 0 \sum\limits_{i=1}^n y_{i} \leq 1 s_{i} + p_{i} = q_{i} \sum\limits_{i=1}^n q_{i} = \sum\limits_{i=1}^n s_{i} \end{eqnarray*}$

Würde mich sehr freuen, wenn jemand einen Hinweis hat!

Vielen Dank!

Beste Grüße
Seminarulix

15.04.2014, 01:20

Nobundo

Auf diesen Beitrag antworten »

RE: Suche nach Unbekannter - Lösung mit Hilfer linearer Optimierung?

Zitat:

bekannt sind:
$\begin{eqnarray*} s_{i} a_{i} d_{i} q_{i} y_{i} \end{eqnarray*}$

gesucht ist
$\begin{eqnarray*} z_{i} \end{eqnarray*}$

wobei
$\begin{eqnarray*} p_{i} = y_{i} * z_{i} s_{i} + p_{i} = q_{i} \end{eqnarray*}$

Steht es damit nicht schon quasi da? Die zweite Gleichung kann man umstellen und in die erste einsetzen:

$\begin{eqnarray*} p_i=q_i-s_i\Rightarrow q_i-s_i=y_i\cdot z_i\Rightarrow z_i=\frac{q_i-s_i}{y_i} \end{eqnarray*}$

zumindest solange $\begin{eqnarray*} y_i\neq 0 \end{eqnarray*}$

Gruß
Nobundo

15.04.2014, 10:45

Seminarulix

Auf diesen Beitrag antworten »

RE: Suche nach Unbekannter - Lösung mit Hilfer linearer Optimierung?
Vielen Dank für die schnelle Rückmeldung!

Ich befürchte, da habe ich mich nicht richtig ausgedrückt gehabt, bzw. ist mir wohl ein Tippfehler unterlaufen...es tut mir sehr Leid!

Korrekt/vollständig heißt es:
$\begin{eqnarray*} s_{i} a_{i} d_{i} y_{i} \end{eqnarray*}$

gesucht ist
$\begin{eqnarray*} z_{i} p_{i} q_{i} \end{eqnarray*}$

wobei
$\begin{eqnarray*} p_{i} = y_{i} * z_{i} s_{i} + p_{i} \geq a_{i} s_{i} + p_{i} \leq d_{i} \sum\limits_{i=1}^n p_{i} = 0 \sum\limits_{i=1}^n y_{i} \leq 1 s_{i} + p_{i} = q_{i} \sum\limits_{i=1}^n q_{i} = \sum\limits_{i=1}^n s_{i} \end{eqnarray*}$

Würde mich erneut sehr freuen, wenn jemand einen Hinweis hat!

Vielen Dank noch mal!

Beste Grüße
Seminarulix

15.04.2014, 11:35

HAL 9000

Auf diesen Beitrag antworten »

Ok, die letzten beiden Gleichungen (und damit überhaupt die $\begin{eqnarray*} q_i \end{eqnarray*}$ ) kann man erstmal aus dem Spiel nehmen:

Mit $\begin{eqnarray*} q_i:=s_i+p_i \end{eqnarray*}$ folgt wegen $\begin{eqnarray*} \sum_{i=1}^n p_i = 0 \end{eqnarray*}$ automatisch $\begin{eqnarray*} \sum_{i=1}^n q_i = \sum_{i=1}^n s_i \end{eqnarray*}$ .

Weiter geht's: Die $\begin{eqnarray*} y_i \end{eqnarray*}$ sind laut deinem letzten Posting gegeben - dann erfüllen sie die Bedingung $\begin{eqnarray*} \sum_{i=1}^n y_i \leq 1 \end{eqnarray*}$ von vornherein oder eben nicht. Mit diesen $\begin{eqnarray*} y_i \end{eqnarray*}$ kann man bei ermittelten $\begin{eqnarray*} p_i \end{eqnarray*}$ dann auch die $\begin{eqnarray*} z_i \end{eqnarray*}$ bestimmen über $\begin{eqnarray*} z_i = \frac{p_i}{y_i} \end{eqnarray*}$ .

Auch die $\begin{eqnarray*} s_i \end{eqnarray*}$ kann man eliminieren, wenn man $\begin{eqnarray*} b_i:=a_i-s_i,c_i:=d_i-s_i \end{eqnarray*}$ setzt, dann bleibt als Kernproblem übrig:

Zitat:

gegeben: $\begin{eqnarray*} b_i, c_i \end{eqnarray*}$

gesucht: $\begin{eqnarray*} p_i \end{eqnarray*}$ mit $\begin{eqnarray*} b_i \leq p_i \leq c_i \end{eqnarray*}$ und $\begin{eqnarray*} \sum_{i=1}^n p_i = 0 \end{eqnarray*}$

Notwendig für die Existenz von Lösungen ist offenbar $\begin{eqnarray*} \sum_{i=1}^n b_i \leq 0 \leq \sum_{i=1}^n c_i \end{eqnarray*}$ .

Falls bei beiden < sogar < gilt, gibt es unendlich viele Lösungstupel $\begin{eqnarray*} (p_1,\ldots,p_n) \end{eqnarray*}$ .

Bisher ist es also kein LOP, sondern allenfalls der zulässige Bereich eines LOP - es fehlt sozusagen eine Zielfunktion. Augenzwinkern

15.04.2014, 13:13

Seminarulix

Auf diesen Beitrag antworten »

Vielen Dank für Deine Antwort!

Ich glaube ich konnte Deinen Ausführungen mehr oder weniger folgen Augenzwinkern

Aus "praktischer" Sicht des Problems, dass ich mir dort untersuche wäre es denkbar $\begin{eqnarray*} p_i \end{eqnarray*}$ zu minimieren bzw. möglichst klein zu halten. Wie wäre denn dann eine Formulierung einer Zielfunktion möglich?

Erneut ein großes Dankeschön!

VG
Seminarulix

15.04.2014, 14:25

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Seminarulix
Aus "praktischer" Sicht des Problems, dass ich mir dort untersuche wäre es denkbar $\begin{eqnarray*} p_i \end{eqnarray*}$ zu minimieren bzw. möglichst klein zu halten.

Für alle Tupel im bisher zulässigem Gebiet ist die Summe der $\begin{eqnarray*} p_i \end{eqnarray*}$ gleich Null. Was meinst du daher damit, die $\begin{eqnarray*} p_i \end{eqnarray*}$ zu "minimieren"? Gemeinsam geht das aufgrund dieser Summenbedingung nicht - vielleicht meinst du die Summe der Beträge? verwirrt

15.04.2014, 15:52

Seminarulix

Auf diesen Beitrag antworten »

Ja, richtig: die Summe der Beträge sollte minimiert sein!

15.04.2014, 16:59

HAL 9000

Auf diesen Beitrag antworten »

Bei nochmaliger Überlegung fürchte ich, dass auch dieses Kriterium i.a. keine eindeutige Lösung liefert. verwirrt

Man könnte zuerst für jedes $\begin{eqnarray*} i \end{eqnarray*}$ ein $\begin{eqnarray*} p_i' \end{eqnarray*}$ folgendermaßen wählen:

a) $\begin{eqnarray*} p_i'=0 \end{eqnarray*}$ , falls $\begin{eqnarray*} b_i\leq 0\leq c_i \end{eqnarray*}$

b) $\begin{eqnarray*} p_i'=b_i \end{eqnarray*}$ , falls $\begin{eqnarray*} 0 < b_i\leq c_i \end{eqnarray*}$

c) $\begin{eqnarray*} p_i'=c_i \end{eqnarray*}$ , falls $\begin{eqnarray*} b_i\leq c_i < 0 \end{eqnarray*}$

Dann ist auf alle Fälle $\begin{eqnarray*} m=\sum_{i=1}^n |p_i'| \end{eqnarray*}$ minimal unter der Bedingung $\begin{eqnarray*} p_i'\in [b_i,c_i] \end{eqnarray*}$ , allerdings wird die Summenbedingung $\begin{eqnarray*} S':=\sum_{i=1}^n p_i' \stackrel{?}{=}0 \end{eqnarray*}$ i.a. noch nicht erfüllt sein. Das kann man so korrigieren:

Ist $\begin{eqnarray*} S'<0 \end{eqnarray*}$ , dann suchen wir diejenigen $\begin{eqnarray*} i \end{eqnarray*}$ mit $\begin{eqnarray*} p_i'<c_i \end{eqnarray*}$ (also aus a) oder b)) zusammen und erhöhen eine oder mehrerer dieser $\begin{eqnarray*} p_i'\to p_i \end{eqnarray*}$ soweit, bis die veränderte Summe $\begin{eqnarray*} S'\to S=0 \end{eqnarray*}$ ergibt. Ist die notwendige Voraussetzung $\begin{eqnarray*} \sum_{i=1}^n c_i\geq 0 \end{eqnarray*}$ erfüllt, ist das stets möglich.

Analog geht man im Fall $\begin{eqnarray*} S'<0 \end{eqnarray*}$ vor: Hier nehmen wir die $\begin{eqnarray*} i \end{eqnarray*}$ mit $\begin{eqnarray*} p_i'>b_i \end{eqnarray*}$ (also aus a) oder c)) und verringern die entsprechend, bis auch hier $\begin{eqnarray*} S=0 \end{eqnarray*}$ erreicht ist.

Für alle anderen in diesem Prozess unverändert gebliebenen $\begin{eqnarray*} p_i' \end{eqnarray*}$ setzt man einfach $\begin{eqnarray*} p_i:=p_i' \end{eqnarray*}$ .

Welche genau man nun erhöht bzw. verringert, ist eigentlich egal, es führt so oder so auf denselben Minimumwert $\begin{eqnarray*} \min \sum_{i=1}^n |p_i| = m+|S'| \end{eqnarray*}$ unter NB $\begin{eqnarray*} \sum_{i=1}^n p_i = 0 \end{eqnarray*}$ .

15.04.2014, 17:51

Seminarulix

Auf diesen Beitrag antworten »

Zitat:

Analog geht man im Fall $\begin{eqnarray*} S'<0 \end{eqnarray*}$ vor

müsste es nicht vll. eher $\begin{eqnarray*} S'>0 \end{eqnarray*}$ heißen?

Zitat:

Welche genau man nun erhöht bzw. verringert, ist eigentlich egal, es führt so oder so auf denselben Minimumwert $\begin{eqnarray*} \min \sum_{i=1}^n |p_i| = m+|S'| \end{eqnarray*}$ unter NB $\begin{eqnarray*} \sum_{i=1}^n p_i = 0 \end{eqnarray*}$ .

Mh, so ganz egal ist es aus "praktischer Anwendungssicht" leider nicht, welche man verringert oder erhöht. Gibt es denn da keine eindeutige Aussage, oder habe ich das falsch verstanden?

Vielen Dank erneut!

15.04.2014, 17:54

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Seminarulix

Zitat:

Analog geht man im Fall $\begin{eqnarray*} S'<0 \end{eqnarray*}$ vor

müsste es nicht vll. eher $\begin{eqnarray*} S'>0 \end{eqnarray*}$ heißen?

Ja klar - ein dummer Copy+Paste-Fehler von mir. Hammer

Zitat:

Original von Seminarulix
Mh, so ganz egal ist es aus "praktischer Anwendungssicht" leider nicht

Es ist egal, wenn man nur an einer Lösung des Optimierungsproblems $\begin{eqnarray*} \sum_{i=1}^n |p_i| \to \min \end{eqnarray*}$ interessiert ist.

Anders sieht es vermutlich bei dem "ähnlich" gelagerten

$\begin{eqnarray*} \sum_{i=1}^n p_i^2 \to \min \end{eqnarray*}$

aus - wie meist bei diesen MKQ-Problemen dürfte dieses eine eindeutige Minimumstelle haben.

15.04.2014, 18:50

Seminarulix

Auf diesen Beitrag antworten »

Alles klar, vielen Dank!

Ich würde das Ganze noch einmal sacken lassen und versuchen umzusetzen. Ich würde mich dann vermutlich morgen noch mal melden, ob ich mit dem Vorgehen zu Recht komme/es für die Fragestellung passt!

Neue Frage »

Antworten »

Suche nach Unbekannter - Lösung mit Hilfe linearer Optimierung?

Verwandte Themen