Finden optimaler Lösung

10.11.2017, 15:13

LuciaSera

Finden optimaler Lösung

Mein Beispiel:

20b) Überlegen Sie wie die jeweils optimale Lösung von folgenden Linearen Problemen lautet.

max x1 + x2 + x3 + x4 + x5
unter 2x1 + 4x2 + 5x3 + 6x4 + 7x5 <= 13
0 <= xi <= 1 für i = 1,...,5.

Unsere Argumentation stützt sich auf den Hauptsatz der Linearen Optimierung, welcher besagt, dass es genau dann eine optimale zulässige Lösung gibt, wenn es eine optimale Basislösung gibt. Da dieses Problem eine 1x6-Matrix ist, muss die Untermatrix für die Basislösung eine 1x1-Matrix sein.

Dafür führen wir die Schlupfvarialbe x6 ein. Dann gilt:

2x1 + 4x2 + 5x3 + 6x4 + 7x5 + x6 = 13

Es gibt aber keine Basislösung, welche dieses Gleichungssystem erfüllt, wenn meine xi höchstens die Zahl 1 annehmen darf.

Stimmt das oder haben wir einen Denkfehler?

Freue mich über jede Antwort. Danke Hammer

10.11.2017, 15:21

HAL 9000

Auf diesen Beitrag antworten »

Liegt da der Irrtum?

Zitat:

Original von LuciaSera
Es gibt aber keine Basislösung, welche dieses Gleichungssystem erfüllt, wenn meine xi höchstens die Zahl 1 annehmen darf.

Dir ist aber schon klar, dass deine extra eingeführte Schlupfvariable $\begin{align*} x_6 \end{align*}$ nicht nach oben durch 1 beschränkt ist? Für die wird lediglich Nichtnegativität, d.h., $\begin{align*} x_6\geq 0 \end{align*}$ gefordert. Augenzwinkern

10.11.2017, 15:27

LuciaSera

Auf diesen Beitrag antworten »

Diese Vermutung habe ich auch schon aufgestellt. Wo ich mir dann unklar bin ist, was dann mit meiner Zielfunktion passiert.

Wird diese Schlupfvariable in meiner Zielfunktion berücksichtigt? Wenn ich sage, dass meine Zielfunktion dann:

x1+x2+x3+x4+x5+x6

lautet, ist alles klar. Wenn nun aber x6 nur als 0*x6, also

x1+x2+x3+x4+x5+0*x6

vorkommt, wäre ja meine Zielfunktion trotzdem 0. Ist das dann trotzdem eine optimale Lösung?

10.11.2017, 15:29

HAL 9000

Auf diesen Beitrag antworten »

Ich kann deine Gedanken irgendwie nicht nachvollziehen. Die optimale Lösung ist doch hier ziemlich offensichtlich:

Den $\begin{align*} x_i \end{align*}$ mit den "kleinen" Vorfaktoren in der NB gibt man volle Ladung 1, solange es eben geht (d.h. man noch unter 13 bleibt). Dem $\begin{align*} x_i \end{align*}$ am Übergang gibt man den "Rest".

Konkret: $\begin{align*} x_1=x_2=x_3=1,x_4=\frac{1}{3},x_5=0 \end{align*}$ mit Zielfunktionswert $\begin{align*} \frac{10}{3} \end{align*}$ .

10.11.2017, 15:31

LuciaSera

Auf diesen Beitrag antworten »

Das wäre doch "nur" eine zulässige Lösung, doch woher weiß ich nun, dass das die optimalste zulässige Lösung ist?

10.11.2017, 15:37

HAL 9000

Auf diesen Beitrag antworten »

Da du meine Argumentation nicht nachvollziehen kannst, musst du dir das Ergebnis wohl selbst bestätigen, indem du deine üblichen Verfahren durchziehst (Simplex, oder was weiß ich). Bin äußerst gespannt, ob du einen größeren Zielfunktionswert schaffst - dann werde ich natürlich in gebührender Weise Abbitte tun. Augenzwinkern

OK, eine Erklärung: Seien $\begin{align*} a_1=2,a_2=4,a_3=5,a_4=6,a_5=7 \end{align*}$ die Vorfaktoren in der Ungleichungs-NB. Klar ist, dass es keine optimale Lösung mit $\begin{align*} x_i\leq 1-\varepsilon \end{align*}$ und $\begin{align*} x_j\geq \varepsilon \end{align*}$ für irgendein Indexpaar $\begin{align*} (i,j) \end{align*}$ mit $\begin{align*} 1\leq i<j\leq 5 \end{align*}$ sowie $\begin{align*} \varepsilon>0 \end{align*}$ geben kann:

In dem Fall würde man nämlich das Tupel dahingehend abändern: $\begin{align*} x_i':=x_i+\varepsilon, x_j':=x_j-\frac{a_i}{a_j}\varepsilon \end{align*}$

Die NB wäre nach wie vor erfüllt, denn diese Abänderung liefert $\begin{align*} \sum_{k=1}^5 a_kx_k' =\sum_{k=1}^5 a_kx_k \leq 13 \end{align*}$ , aber der Zielfunktionswert ist $\begin{align*} \sum_{k=1}^5 a_kx_k' = \sum_{k=1}^5 a_kx_k + \varepsilon\left(1-\frac{a_i}{a_j}\right) > \sum_{k=1}^5 a_kx_k \end{align*}$ , Widerspruch zur Maximalität.

Folgerung: Es muss irgendein $\begin{align*} k \end{align*}$ geben mit $\begin{align*} 1=x_1=\ldots=x_{k-1} > x_k\geq x_{k+1} = \ldots = x_5 = 0 \end{align*}$ , und das führt dann ja direkt zu meinem angegebenen optimalen Punkt.

14.11.2017, 16:24

LuciaSera

Auf diesen Beitrag antworten »

Haben zu diesem Beispiel eine Lösung gefunden. Wir haben uns mit den Verhältnisse zwischen Zielfunktion und Nebenbedingung auseinandergesetzt und so die Lösung gefunden.

Trotzdem danke für deine Hilfe!

14.11.2017, 16:35

LuciaSera

Auf diesen Beitrag antworten »

Okay eine Frage hätte ich noch:

21) Gegeben seien reelle Zahlen c1 > c2 > ... > cn und folgendes Lineare Programm:

$\begin{eqnarray*} max c^{t}x unter \sum\limits_{i=1}^{n} x_{i} = 3 0 \leq x_{i} \leq 1, i = 1,...,n \end{eqnarray*}$

Überlegen Sie, wie die optimale Lösung des Problems lautet.

Kann ich meine c's nicht beliebig groß wählen?

14.11.2017, 16:44

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von LuciaSera
Trotzdem danke für deine Hilfe!

Bedeutet "trotzdem", dass du meine Lösung für falsch hältst? Augenzwinkern

Zitat:

Original von LuciaSera
Kann ich meine c's nicht beliebig groß wählen?

Die c's sind vorgegeben! Da hast du nix zu wählen. Das Maximum der Zielfunktion wird hinsichtlich $\begin{align*} x_1,\ldots,x_n \end{align*}$ gebildet!

Und es gibt sicher auch noch die Vorgabe $\begin{align*} n\geq 3 \end{align*}$ , ansonsten ist nämlich die NB gar nicht erfüllbar.

28.12.2017, 09:51

LuciaSera

Auf diesen Beitrag antworten »

Nein! Deine Antwort war goldrichtig! Freude

Ich habe das Beispiel dann nur etwas anders gelöst als du, deswegen meinte ich "trotzdem" Augenzwinkern

Bei den c's meinte ich nur, dass sie keine konkreten Werte haben.

Neue Frage »

Antworten »

Finden optimaler Lösung

Verwandte Themen