Ungleichungssystem mit 6 Unbekannten

04.08.2015, 16:03

Hinokami

Ungleichungssystem mit 6 Unbekannten

Meine Frage:

Hallo allerseits,

Ich beschäftige mich mit der Mathematik zurzeit freizeitlich und mach mich zurzeit mit folgender Aufgabe schwer:

Ich möchte basierend auf folgenden Angaben die möglichen Werte der 6 vorgegebenen Variablen bestimmen, wobei $\begin{eqnarray*} x_{5} \end{eqnarray*}$ unabhängig von den anderen Variablen eingegrenzt werden soll und die restlichen Variablen von den jeweils oberen abhängig sein darf:

$\begin{eqnarray*} x_{2} \end{eqnarray*}$
$\begin{eqnarray*} x_{1} \end{eqnarray*}$
$\begin{eqnarray*} x_{3} \end{eqnarray*}$
$\begin{eqnarray*} x_{4} \end{eqnarray*}$
$\begin{eqnarray*} x_{6} \end{eqnarray*}$

Folgende geltende Funktionen sind gegeben:

$\begin{eqnarray*} x_{1}-x_{4}+1/2x_{5}-1/2x_{6}>0 \end{eqnarray*}$

$\begin{eqnarray*} x_{2}+1/2x_{3}-1/2x_{4}-x_{5}>0 \end{eqnarray*}$

$\begin{eqnarray*} 1/2x_{2}+x_{3}-1/2x_{5}-x_{6}>0 \end{eqnarray*}$

$\begin{eqnarray*} -x_{1}-1/2x_{2}+x_{4}+1/2x_{6}>0 \end{eqnarray*}$

$\begin{eqnarray*} 1/2x_{1}-x_{2}-1/2x_{3}+x_{5}>0 \end{eqnarray*}$

$\begin{eqnarray*} x_{1}+x_{2}+x_{3}+x_{4}+x_{5}+x_{6}=1 \end{eqnarray*}$

zudem sind alle möglichen Werte für die Variablen positive reelle Zahlen.

Da ich vorher mit Excel gearbeitet habe und das Dateiformat nicht unterstützt wird kann ich meine Vorgehensweise, die ich unten beschreibe, nicht in einem ansehnlichen Format beifügen.

Falls mir hierbei jemand helfen kann, wäre ich überaus dankbar.

Meine Ideen:
Meine Vorgehensweise bis jetzt war sehr umständlich: Ich habe zuerst die letzte Gleichung auf $\begin{eqnarray*} x_{6} \end{eqnarray*}$ umgestellt und diese dann in die Ungleichungen eingesetzt. Danach habe ich alle Ungleichungen, bei denen es möglich ist, nach $\begin{eqnarray*} x_{4} \end{eqnarray*}$ umgestellt. Dann habe ich alle Ungleichungen, bei denen $\begin{eqnarray*} x_{4} \end{eqnarray*}$ größer ist mit allen Ungleichungen abgeglichen, wo die Variable kleiner ist. Diesen Vorgang habe ich mit $\begin{eqnarray*} x_{3} \end{eqnarray*}$ wiederholt. Da diese Vorgehensweise jedoch sehr umständlich ist und sie sowohl leicht zu Fehlern führen kann und ich mir zudem nicht im Klaren bin, ob diese Vorgehensweise überhaupt etwas bringt, wende ich mich nun an alle, die mir hierbei weiterhelfen können.

04.08.2015, 17:22

HAL 9000

Auf diesen Beitrag antworten »

Die Lösungsmenge dieses Ungleichungssystems kann man als zulässiges Gebiet eines Linearen Optimierungsproblems auffassen (LOP), und die Zielfunktion wäre dann schlicht $\begin{align*} x_5 \end{align*}$ , zu minimieren sowie (in einem zweiten Verfahren) zu maximieren.

Zunächst mal ist aber zu ermitteln, ob dieses Gebiet überhaupt nichtleer ist. (EDIT: Es ist nichtleer, d.h. es existieren Lösungen)

Zitat:

Original von Hinokami
Ich möchte basierend auf folgenden Angaben die möglichen Werte der 6 vorgegebenen Variablen bestimmen, wobei $\begin{eqnarray*} x_{5} \end{eqnarray*}$ unabhängig von den anderen Variablen eingegrenzt werden soll und die restlichen Variablen von den jeweils oberen abhängig sein darf:

$\begin{eqnarray*} x_{2} \end{eqnarray*}$
$\begin{eqnarray*} x_{1} \end{eqnarray*}$
$\begin{eqnarray*} x_{3} \end{eqnarray*}$
$\begin{eqnarray*} x_{4} \end{eqnarray*}$
$\begin{eqnarray*} x_{6} \end{eqnarray*}$

So verständlich das Ansinnen ist: Abgesehen von der ersten Zeile für $\begin{align*} x_5 \end{align*}$ sowie der letzten Zeile, die ja einfach $\begin{align*} x_6=1-x_1-x_2-x_3-x_4-x_5 \end{align*}$ ist, werden die Zwischenzeilen wirklich eklig, mit jeder Menge Fallunterscheidungen je nach vorherigem Parametersatz, Die ganze Lösungsmenge der $\begin{align*} (x_1,x_2,x_3,x_4,x_5) \end{align*}$ (wenn wir mal x_6 ausklammern, weil sich das aus den anderen 5 ergibt) ist ein fünfdimensionales Polyeder, und dessen Seitenflächen (zumindest die meisten) sind gewiss nicht senkrecht zu irgendeiner der Koordinatenachsen.

04.08.2015, 19:47

Hinokami

Auf diesen Beitrag antworten »

Also könnte es schwer werden eine einfachere Vorgehensweise zu finden als diejenige, die ich bis jetzt anwende? Ich bin mir sicher, dass es mindestens eine Lösung gibt, da diese Variablen im Grunde nur der Input für 6 weitere Variablen sind ( $\begin{eqnarray*} y_{1} ; y_{2} ; y_{3} ; y_{4} ; y_{5} ; y_{6} \end{eqnarray*}$ ), die sozusagen der Output des ganzen sind, ich eine Rückrechnung aufgestellt habe, welche die x-Variablen von den y-variablen abhängig macht anstatt andersherum und ich danach Stichproben mit extrem niedrigen Prozentwerten gemacht habe. Ich editiere Mal meinen ersten Post, damit auch alle Infos vorhanden sind.

04.08.2015, 20:50

Hinokami

Auf diesen Beitrag antworten »

Folgende geltende Funktionen sind gegeben:

$\begin{eqnarray*} y_{1}=x_{1}-x_{4}+1/2x_{5}-1/2x_{6}>0 \end{eqnarray*}$

$\begin{eqnarray*} y_{2}=x_{2}+1/2x_{3}-1/2x_{4}-x_{5}>0 \end{eqnarray*}$

$\begin{eqnarray*} y_{3}=1/2x_{2}+x_{3}-1/2x_{5}-x_{6}>0 \end{eqnarray*}$

$\begin{eqnarray*} y_{4}=-x_{1}-1/2x_{2}+x_{4}+1/2x_{6}>0 \end{eqnarray*}$

$\begin{eqnarray*} y_{5}=1/2x_{1}-x_{2}-1/2x_{3}+x_{5}>0 \end{eqnarray*}$

$\begin{eqnarray*} x_{1}+x_{2}+x_{3}+x_{4}+x_{5}+x_{6}=1 \end{eqnarray*}$

zusätzlich gilt noch $\begin{eqnarray*} y_{6}=-1/2x_{1}-x_{3}+1/2x_{4}+x_{6} \end{eqnarray*}$ aber da diese Funktion keine weiteren Beschränkungen hat kann man hiermit glaube nicht viel anfangen.

05.08.2015, 10:00

HAL 9000

Auf diesen Beitrag antworten »

Anscheinend ist dir noch nicht so richtig klar, was ich mit

Zitat:

Original von HAL 9000
werden die Zwischenzeilen wirklich eklig, mit jeder Menge Fallunterscheidungen je nach vorherigem Parametersatz.

gemeint habe. Ich will das mal an einem deutlich einfacher strukturierten Beispiel erläutern: Man beschreibe die Lösungsmenge des Ungleichungssystems

$\begin{align*} 2x_1 + 2x_2 - 3x_3 &\geq 0 \\ -4x_1 + 6x_2 + x_3 &\geq 0 \\ 2x_1 - 2x_2 + x_3 &\geq 0 \\ x_1 + x_2 + x_3 &= 1 \end{align*}$ .

Die letzte Gleichung $\begin{align*} x_3=1-x_1-x_2 \end{align*}$ mal ausgeklammert ergibt sich als $\begin{align*} (x_1,x_2) \end{align*}$ - Lösungsmenge die Dreiecksfläche

Das bedeutet letztendlich

$\begin{align*} 0.2 \leq x_1\leq 0.8 \end{align*}$
$\begin{align*} 0.6-x_1\leq x_2\leq \frac{x_1+1}{3} \end{align*}$ für $\begin{align*} 0.2\leq x_1\leq 0.4 \end{align*}$
$\begin{align*} x_1-0.2\leq x_2\leq \frac{x_1+1}{3} \end{align*}$ für $\begin{align*} 0.4\leq x_1\leq 0.8 \end{align*}$ .

Nimmt man zuerst $\begin{align*} x_2 \end{align*}$ , ist es auch nicht besser, auch hier benötigt man eine Fallunterscheidung zur Beschreibung der Lösungsmenge:

$\begin{align*} 0.2\leq x_2\leq 0.6 \end{align*}$

$\begin{align*} 0.6-x_2 \leq x_1\leq x_2+0.2 \end{align*}$ für $\begin{align*} 0.2\leq x_2\leq 0.4 \end{align*}$
$\begin{align*} 3x_2-1 \leq x_1\leq x_2+0.2 \end{align*}$ für $\begin{align*} 0.4\leq x_2\leq 0.6 \end{align*}$ .

Vielleicht kannst du dir jetzt zumindest vage vorstellen, was das bei deinem Problem mit einer fünf- statt zweidimensionalen Lösungsmenge für einen Wust von Fallunterscheidungen in der von dir gewüschten Beschreibungskette

$\begin{align*} x_5 \to x_2 \to x_1 \to x_3 \to x_4 \end{align*}$

zur Folge hat. Augenzwinkern

P.S.: Was dein Problem betrifft: Mit LOP-Mitteln behandelt ermittelt man $\begin{align*} 0\leq x_5\leq \frac{1}{3} \end{align*}$ , zugehörige Eckpunkte des $\begin{align*} (x_1,x_2,x_3,x_4,x_5,x_6) \end{align*}$ -Polyeders sind $\begin{align*} \left( \frac{1}{3}, 0, \frac{2}{9}, \frac{2}{9}, 0, \frac{2}{9} \right) \end{align*}$ für das $\begin{align*} x_5 \end{align*}$ -Minimum und $\begin{align*} \left( 0, \frac{1}{5}, \frac{4}{15}, 0, \frac{1}{3}, \frac{1}{5} \right) \end{align*}$ für das $\begin{align*} x_5 \end{align*}$ -Maximum. Allerdings habe ich dabei all deine > in > umgewandelt, um einen abgeschlossenen zulässigen Bereich des LOP zu bekommen (wie es üblich ist).

EDIT: Die genannten Eckpunkte sind nicht eindeutig, offenbar sind also die Schnitte der Lösungsmenge mit den Hyperebenen $\begin{align*} x_5=0 \end{align*}$ bzw. $\begin{align*} x_5=\frac{1}{3} \end{align*}$ mindestens eindimensional, bestehen als nicht nur aus einem Punkt. Augenzwinkern

05.08.2015, 14:01

Hinokami

Auf diesen Beitrag antworten »

Ich habe mich an diese Aufgabe bis jetzt rein rechnerisch versucht, weshalb ich mir im Klaren darüber bin wie umfangreich die Anzahl an Beschränkungen ist, die sich aus den gegebenen Angaben erschließen. Allein bei $\begin{eqnarray*} x_{3} \end{eqnarray*}$ haben sich bei mir bis jetzt 8 verschiedene Eingrenzungen gezeigt und bei $\begin{eqnarray*} x_{1} \end{eqnarray*}$ sind es bei der Methode die ich anwende zurzeit 13. Die Frage die ich mir hierbei stelle ist schlichtweg, ob ich es mir auf die rein rechnerische Art vielleicht zu schwer mache und es Möglichkeiten gibt dieses Problem im Verlauf der Berechnungen übersichtlicher zu gestalten.

05.08.2015, 14:19

HAL 9000

Auf diesen Beitrag antworten »

Ok, du bist dir des von mir angesprochenen Problems anscheinend bewusst und willst dennoch diesen steinigen Weg der Darstellung der Lösungsmenge über

$\begin{align*} x_5 \to x_2 \to x_1 \to x_3 \to x_4 \end{align*}$

gehen? Dann viel Erfolg (mir fehlt da ein wenig die Motivation, das so zu tun), vielleicht kann dir ja wenigstens mein Hinweis auf LOP helfen, ein wenig mehr Systematik in die Betrachtungen zu bringen. Freude

05.08.2015, 15:00

Huggy

Auf diesen Beitrag antworten »

RE: Ungleichungssystem mit 6 Unbekannten
Ergänzung zu HAL:

Zitat:

Original von HinokamiDa ich vorher mit Excel gearbeitet habe

Solche Probleme lassen sich mit dem Solver von Excel lösen. Dabei gibt es allerdings aufgrund meiner sehr beschränkten Erfahrung mit ihm ein paar Feinheiten zu beachten, weil der Solver nicht speziell für die lineare Optimierung konzipiert ist.

Wenn dir ein speziell für lineare Optimierung gedachtes Programm zur Verfügung steht, solltest du nach meiner persönlichen Meinung besser dieses benutzen.

05.08.2015, 16:09

Hinokami

Auf diesen Beitrag antworten »

RE: Ungleichungssystem mit 6 Unbekannten
Ich hatte, bevor ich diesen Thread aufgemacht habe, nur diese Ungleichungen ohne irgendwelche thematischen Stichwörter, daher haben sie mir hier im Grunde super weitergeholfen.

Es gibt bestimmt auch online einen Rechner für LOPs ich werde mal danach Ausschau halten.

Danke

Neue Frage »

Antworten »

Ungleichungssystem mit 6 Unbekannten

Verwandte Themen