Lineare Optimierung 2

22.10.2013, 00:30

stud1989

Auf diesen Beitrag antworten »

RE: Lineare Optimierung

Weils so schön ist, gehts mit ner neuen Aufgabe weiter:

$\begin{eqnarray*} <br /> max \sum\limits_{j=1}^n c_{j} x_{j} <br /> \sum\limits_{j=1}^n x_{j} = \pi n^2<br /> x_{i} \geq 0, i=1,...,n<br /> \end{eqnarray*}$

Wie viele Basislösungen gibt es?

Das lässt sich doch durch den Binomialkoeffizienten berechnen, ne!? Wenn ich jetzt n Variablen habe, aber nur eine Zeile, ist das
$\begin{eqnarray*} <br /> \begin{pmatrix} n \\ 1 \end{pmatrix} = n?!<br /> \end{eqnarray*}$

Oder kann man den Binomialkoeff. nur für die Anzhal ZULÄSSIGER Basislösungen nehmen, finde in meinen Aufzeichnungen nichts.

22.10.2013, 02:05

mYthos

Auf diesen Beitrag antworten »

RE: Lineare Optimierung
Weils NICHT so schön ist, eine neue Aufgabe in einem bestehenden Thread anzuhängen, wird diese abgetrennt und damit ein neuer Thread erstellt.
Bitte in Hinkunft darauf zu achten, der Thread wird ansonsten dadurch schnell unübersichtlich.

Neue Aufgabe --> neuer Thread

(!)

mY+

23.10.2013, 11:23

stud1989

Auf diesen Beitrag antworten »

RE: Lineare Optimierung
ok, danke für den Hinweis. Trotzdem wäre es ganz nett, wenn mir bei der Aufgabe jemand helfen könnte ;-)

23.10.2013, 12:14

Kasen75

Auf diesen Beitrag antworten »

Hallo,

wenn ich die Aufgabe richtig verstanden habe, dann ist $\begin{eqnarray*} x_i \in R_0^+ \end{eqnarray*}$ . Das kann ja auch gar nicht anders sein, da auf der rechten Seite der Faktor $\begin{eqnarray*} \Pi \end{eqnarray*}$ steht.

Wenn dem so ist, dann ist bei n=2 die Nebenbedingung:

$\begin{eqnarray*} x_1+x_2=4\cdot \Pi \end{eqnarray*}$

Und hier gibt es unendlich viele Lösungen. Somit gibt es für $\begin{eqnarray*} n\geq 2 \end{eqnarray*}$ unendlich viele Lösungen.

Kann aber auch sein, dass ich die Aufgabe falsch verstanden habe.

Grüße.

23.10.2013, 15:34

stud1989

Auf diesen Beitrag antworten »

Nein, ich will doch die Anzahl von Basislösungen

23.10.2013, 15:49

Kasen75

Auf diesen Beitrag antworten »

Und ist für n=2, $\begin{eqnarray*} x_1=x_2=2\Pi \end{eqnarray*}$ keine Basislösung ?

Anzeige

24.10.2013, 10:16

stud1989

Auf diesen Beitrag antworten »

es gibt n Variablen, aber nur eine Nebenbedingung, das hat doch irgendwas damit zu tun

24.10.2013, 10:54

Kasen75

Auf diesen Beitrag antworten »

Ich habe jetzt nochmal nachgedacht. Ich muss dir zustimmen. Es gibt n Variablen und 1 Gleichung. Somit gibt es n Basislösungen.

Diese müssten auch alle zulässig sein, da alle Basislösungen größer Null sind.

24.10.2013, 12:36

stud1989

Auf diesen Beitrag antworten »

danke. Und das berechne ich doch mit dem Binomialkoeffizienten!?
D.h. wenn ich zwei Nebenbedingungen hätte, gäbe es doch nur noch n über 2 Basislösungen, hab ich das richtig verstanden?

24.10.2013, 12:58

Kasen75

Auf diesen Beitrag antworten »

Genau.

smile

24.10.2013, 13:11

stud1989

Auf diesen Beitrag antworten »

Supi. Und die Anzahl ZULÄSSIGER Basislösungen? Da gibts aber keine Formel oder? Da muss man nur gucken, ob diese die Nebenbedingungen erfüllen!?

24.10.2013, 13:32

Kasen75

Auf diesen Beitrag antworten »

Richtig. Sobald die Basislösung sich nicht im Lösungsraum befindet ist sie nicht zulässig. Wobei die zulässigen Basislösungen auf einem Eckpunkt des Lösungsraumes befinden.

24.10.2013, 13:48

stud1989

Auf diesen Beitrag antworten »

gut, dieser Teil wäre geklärt. Jetzt hab ich da aber noch die Frage: Geben Sie eine optimale Lösung an und zeigen Sie die Optimalität dieser Lösung.

ich könnte jetzt zwar immer $\begin{eqnarray*} x_{1} = x_{2} = ...= x_{n} =n\cdot \pi \end{eqnarray*}$ setzen, aber das muss ja dann nicht optimal sein, da ich die cj oben nicht ja kenne!?
c1 könnte ja 10 sein und der Rest 0, dann hätte eine Lösung $\begin{eqnarray*} x1=\pi *n^2 \end{eqnarray*}$ (alle anderen x dann 0) wäre mein Zielfunktionswert größer.
usw. und so fort

24.10.2013, 15:21

Kasen75

Auf diesen Beitrag antworten »

Allgemeiner formuliert:

Man ermittelt den maximalen Wert der Koeffizienten der Zielfunktion:

$\begin{eqnarray*} Max \{c_1, \ldots , c_j , \ldots , c_n \} =c^* \end{eqnarray*}$

Dann ist der optimale Zielfunktionswert $\begin{eqnarray*} Z^*=c^* \cdot n^2 \cdot \Pi \end{eqnarray*}$

Jetzt ist es ja irgendwie logisch, wenn man einer Variablen einen positiven Wert zuordnet, dessen Zielkoeffizienten kleiner als $\begin{eqnarray*} c^* \end{eqnarray*}$ ist, die Zielfunktion kleiner als $\begin{eqnarray*} Z^* \end{eqnarray*}$ ist.

Wie man dies formal aufschreibt, müsste man sich noch überlegen.

30.10.2013, 00:02

stud1989

Auf diesen Beitrag antworten »

hmm, kann man vllt auch mithilfe des Optimalitätskriteriums zeigen, dass $\begin{eqnarray*} \pi *n^{2} \end{eqnarray*}$ für ein x eine Optimallösung ist?

30.10.2013, 12:09

Kasen75

Auf diesen Beitrag antworten »

Man könnte anhand des Simplexalgorithmus zeigen, dass $\begin{eqnarray*} x_m=n^2 \cdot \Pi \end{eqnarray*}$ eine Optimallösung ist.

$\begin{eqnarray*} \begin{tabular}[ht]{|l||l|l|l|l|l||l|} \hline & $x_1$ & $\ldots$ & $x_m$ & $\ldots$ & $x_n$ & RS \\ \hline & $-c_1$ & $\ldots$ & $-c_m$ & $\ldots$ & $-c_n$ & 0 \\ \hline & 1 & $\ldots$ & 1 & $\ldots$ & 1 & $ n^2 \cdot \Pi$ \\ \hline \end{tabular} \end{eqnarray*}$

Annahme: $\begin{eqnarray*} |-c_m| \geq |-c_i| \end{eqnarray*}$

Dann ist $\begin{eqnarray*} a_{1m} \end{eqnarray*}$ Pivotelement.

$\begin{eqnarray*} \begin{tabular}[ht]{|l||l|l|l|l|l||l|} \hline & $x_1$ & $\ldots$ & $x_m$ & $\ldots$ & $x_n$ & RS \\ \hline & $-c_1-{\frac{-c_m \cdot 1}{1}}$ & $\ldots$ & $0$ & $\ldots$ & $0-c_n-{\frac{-c_m \cdot 1}{1}}$ & $-\frac{-c_m \cdot n^2 \cdot \Pi}{1}$ \\ \hline & 1 & $\ldots$ & 1 & $\ldots$ & 1 & $ n^2 \cdot \Pi$ \\ \hline \end{tabular} \end{eqnarray*}$

Damit ist die Optimallösung erreicht, da alle Zielkoeffizienten nicht-negativ sind. Und die Optimallösung ist

$\begin{eqnarray*} x_i= n^2 \cdot \Pi \end{eqnarray*}$ ,wenn $\begin{eqnarray*} i=m \end{eqnarray*}$ und

$\begin{eqnarray*} x_i=0 \end{eqnarray*}$ , wenn $\begin{eqnarray*} i \neq m \end{eqnarray*}$

30.10.2013, 12:46

stud1989

Auf diesen Beitrag antworten »

stimmt, ist eig. gar nicht so kompliziert.
Aber welche Lösung ist nun richtig, wenn da steht "beweisen Sie die Optimalität"? Oder geht beides?

30.10.2013, 15:04

stud1989

Auf diesen Beitrag antworten »

muss ich eig immer den größten negativen Koeffizienten der Zielfunktion als Pivotspalte nehmen? In manchen Büchern hab ich das so gelesen, in der Vorlesung steht aber nur, dass es ein Wert kleiner als 0 sein muss (also nicht zwingend der größte negative)!?

30.10.2013, 15:38

Kasen75

Auf diesen Beitrag antworten »

Zitat:

Original von stud1989
stimmt, ist eig. gar nicht so kompliziert.
Aber welche Lösung ist nun richtig, wenn da steht "beweisen Sie die Optimalität"? Oder geht beides?

Ich würde es mehr oder weniger so formulieren, wie in meinem letzten Beitrag.

Zitat:

Original von stud1989
muss ich eig immer den größten negativen Koeffizienten der Zielfunktion als Pivotspalte nehmen?

Wenn man die "Steilster-Anstieg-Regel" verwendet, dann schon. Es gibt auch andere Regeln. Letztendlich kommt man aber immer zu Erfolg, sofern die Simplex-Methode greift, unabhängig welche Regel man verwendet. Wichtig ist nur, das der Zielkoeffizient der Pivotspalte kleiner 0 ist. Nur dann ist eine Verbesserung des Zielfunktionswertes möglich.

30.10.2013, 22:32

stud1989

Auf diesen Beitrag antworten »

Kann man das eig. auch dual lösen?

31.10.2013, 09:03

Kasen75

Auf diesen Beitrag antworten »

Sicher. Du musst das Problem nur umformulieren.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »