Lin. Opt. / Optimalitätskrit. < Sonstiges < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 13:41 Do 29.10.2009 | | Autor: | Docy |
Hallo alle zusammen,
ich habe hier ein Ausschnitt aus dem Buch Lineare und Netzwerkoptimierung von H. Hamacher, wo ich ein paar Verständisprobleme habe. Es geht um den folgenden Satz:
Sei [mm] (x_B, x_N) [/mm] eine zulässige Basislösung. Wenn [mm] c_N(j)-c_{B}*A_{B}^{-1}A_N(j)\ge0 \forall [/mm] j=1....n-m, dann ist x Optimallösung.
Bew.:
[mm] cx=...=c_{B}*A_{B}^{-1}*b+(c-c_{B}*A_{B}^{-1}*A_N)x_N
[/mm]
Da in der augenblicklichen Basislösung [mm] x_N=0 [/mm] ist, ist der Zielfunktionswert [mm] c_{B}x_B=c_{B}*A_{B}^{-1}*b. [/mm]
(*Bis hierhin ist noch alles verständlich, da Basislösung ja heisst, dass [mm] x_N=0 [/mm] und [mm] x_B=A_{B}^{-1}*b [/mm] *)
Für alle anderen Lösungen ergibt sich eine Änderung des Zielfunktionswertes um [mm] (c_N-c_{B}*A_{B}^{-1}*A_N)x_N. [/mm] Erhöhen wir den Wert von [mm] x_N(j)=0 [/mm] auf [mm] x_N(j)=\delta, \delta>0, [/mm] so ändert sich der Zielfunktionswert um [mm] \delta*(c_N(j)-c_{B}*A_{B}^{-1}*A_N(j)). [/mm] Also wird der Zielfunktionswert der gegebenen Basislösung größer, falls [mm] c_N(j)-c_{B}*A_{B}^{-1}*A_N(j)>0 [/mm] und kleiner, falls [mm] c_N(j)-c_{B}*A_{B}^{-1}*A_N(j)<0.
[/mm]
(*So hier habe ich ein Verständnisproblem und zwar wird ja z.B. gesagt, dass der Zielfunktionswert von [mm] cx=c_{B}*A_{B}^{-1}*b+(c-c_{B}*A_{B}^{-1}*A)x_N [/mm] kleiner wird, wenn [mm] c_N(j)-c_{B}*A_{B}^{-1}*A_N(j)<0 [/mm] ist und man [mm] x_N(j) [/mm] auf [mm] \delta [/mm] erhöht. D.h. hier wird gesagt, dass sich der Zielfunktionswert der gegebenen Basislösung dadurch vermindert. Aber wenn man doch nur [mm] x_N(j) [/mm] erhöht und in [mm] c_{B}*A_{B}^{-1}*b+(c-c_{B}*A_{B}^{-1}*A)x_N [/mm] sonst alles gleich lässt (was ja getan wird), dann ist x doch keine Basislösung mehr, weil ja eben nicht mehr n-m Einträge gleich 0 sind, was ja nötig wäre, d.h. man hat [mm] x_N(j) [/mm] einfach erhöht, ohne dafür ein [mm] x_B(i) [/mm] auf 0 zu setzen, oder verstehe ich das ganze falsch??? Weil wenn ich das richtig verstehe, dann macht für mich die Argumentation, "der Zielfunktionswert der Basislösung wird erniedrigt" gar keinen Sinn, weil das x keine Basislösung ist.
Ich hoffe, mir kann jemand weiterhelfen.
Gruß Docy
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:55 Do 29.10.2009 | | Autor: | piet.t |
Hallo,
> Für alle anderen Lösungen ergibt sich eine Änderung des
> Zielfunktionswertes um [mm](c_N-c_{B}*A_{B}^{-1}*A_N)x_N.[/mm]
> Erhöhen wir den Wert von [mm]x_N(j)=0[/mm] auf [mm]x_N(j)=\delta, \delta>0,[/mm]
> so ändert sich der Zielfunktionswert um
> [mm]\delta*(c_N(j)-c_{B}*A_{B}^{-1}*A_N(j)).[/mm] Also wird der
> Zielfunktionswert der gegebenen Basislösung größer,
> falls [mm]c_N(j)-c_{B}*A_{B}^{-1}*A_N(j)>0[/mm] und kleiner, falls
> [mm]c_N(j)-c_{B}*A_{B}^{-1}*A_N(j)<0.[/mm]
>
Die Formulierung "...Zielunktionswert der gegebenen Basislösung..." ist etwas unglücklich. Besser wäre vielleicht "... wird der Zielfunktionswert im Vergleich zur gegebenen Basislösung größer/kleiner".
Was passiert ist folgendes:
1.) [mm] $x_n(j)$ [/mm] wird ausgehend von 0 vergößert
2.) Alle anderen Nichtbasisvariablen bleiben =0
3.) Alle Basisvariablen werden so angepast, dass immer noch $Ax = b$ gilt. Daraus ergibt sich ja gerade die Formel für die Änderung des Zielfunktionswerts.
Mit [mm] $x_N(j) [/mm] > 0$ hat man natürlich keine Basislösung mehr. Geometrisch gesprochen verläßt die betrachtete Lösung eine Ecke (= Basislösung) des Simplex und bewegt sich längs einer Kante.
In einer normalen Simplex-Iterationmarrschiert man so lange weiter, bis man auf die nächste Ecke tifft, also eine neue Basislösung gefunden hat. Das interessiert in dieser Situation allerdings nicht. Alles was hier untersucht ist ist: wie verhält sich die Zielfunktion, wenn man die Lösung von der gegebenen Ecke ein klein wenig längs einer Kante verschiebt.
Gruß
piet
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:11 Do 29.10.2009 | | Autor: | Docy |
Hallo piet,
vielen Dank für die Antwort, die hat mir sehr geholfen, es gibt nur noch eine Kleinigkeit, die ich nicht ganz nachvollziehen kann und zwar, sagst du:
1.) $ [mm] x_n(j) [/mm] $ wird ausgehend von 0 vergößert
2.) Alle anderen Nichtbasisvariablen bleiben =0
3.) Alle Basisvariablen werden so angepast, dass immer noch Ax = b gilt. Daraus ergibt sich ja gerade die Formel für die Änderung des Zielfunktionswerts.
Woher weisst du, dass man die Basisvariablen so anpassen kann, dass immer noch Ax=b gilt? Tut mir Leid, aber ich bin da in diesem Gebiet noch nicht so ganz drin, deshalb sehe ich vielleicht das Offensichtliche noch nicht. Wenn du mir hier noch helfen könntest, wäre ich dir sehr dankbar.
Gruß Docy
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:35 Do 29.10.2009 | | Autor: | piet.t |
Hallo,
>
> Woher weisst du, dass man die Basisvariablen so anpassen
> kann, dass immer noch Ax=b gilt?
Sagen wir es mal andersum: wenn wir versuchen, die Basisvariablen so anzupassen, dass die Bedingung Ax=b weiterhin erfüllt ist, dann kommt genau die Formel für die Anpassung der Zielfunktion raus.
Teilt man A und x in Basis und Nichtbasisteil auf, dann folgt ja aus Ax=b, dass
[mm] $A_Bx_B [/mm] + [mm] A_Nx_N [/mm] = b$
und löst man das nach [mm] $x_B$ [/mm] auf hat man (*)
[mm] $x_B [/mm] = [mm] A_B^{-1}b [/mm] - [mm] A_B^{-1}A_Nx_N$
[/mm]
Schreibt man die Zielfunktion genauso und setzt den obigen Ausdruck ein, dann hat man:
[mm]
z = c_Bx_B + c_Nx_N
=c_B(A_B^{-1}b - A_B^{-1}A_Nx_N) + c_Nx_N
=c_bA_B^{-1}b + (c_N-c_BA_B^{-1}A_N)x_N
[/mm]
Der erste Summand hängt ja nicht von x ab, da tut sich also nichts wenn man an den Werten schraubt. Die Klammer im zweiten Summanden gibt aber an, um wie viel sich die Zielfunktion ändert, wenn man [mm] x_N [/mm] verändert. Erhöht man nun nur [mm] x_N(j) [/mm] und lässt alle anderen Nichtbasisvariablen konstant, dann ändert sich z ja um [mm] $(c_N(j)-c_BA_B^{-1}A_N(j))x_N(j)$.
[/mm]
Und weil wir (*) verwendet haben bedeutet das, dass bei dieser Änderung von z schon berücksichtigt ist, dass sich mit [mm] x_N(j) [/mm] auch die Basisvariablen entsprechend ändern.
Das war jetzt viel Rechnerei, aber ich hoffe du siehst totzdem etwas klarer.
Gruß
piet
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:42 Do 29.10.2009 | | Autor: | Docy |
Hi piet,
jetzt ist alles klar, vielen vielen Dank für deine Mühe.
Gruß Docy
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 00:43 Sa 31.10.2009 | | Autor: | Docy |
Hallo nochmal,
ich möchte nur gerne bestätigt bekommen, ob ich das alles jetzt so halbwegs richtig verstanden habe:
Unsere Zielfunktion sieht ja wie folgt aus, nachdem man die Bedingung Ax=b hinzugefügt hat: [mm] cx=c_{B}\cdot{}A_{B}^{-1}\cdot{}b+(c_N-c_{B}\cdot{}A_{B}^{-1}\cdot{}A_N)x_N. [/mm] Da anfangs x noch eine zulässige Basislösung ist, gilt [mm] cx=c_{B}\cdot{}A_{B}^{-1}\cdot{}b. [/mm] (Da ja Ax=b gilt, und [mm] x_N=0 [/mm] ist, sind wir in einer Ecke des Zulässigkeitsbereiches)
Sollte jetzt [mm] c_N(j)-c_{B}\cdot{}A_{B}^{-1}\cdot{}A_N(j)<0 [/mm] sein, für ein [mm] N(j)\in [/mm] N, dann kann man [mm] x_N(j) [/mm] auf [mm] \delta [/mm] erhöhen, wodurch sich der Zielfunktionswert verringert. Geometrisch stelle ich mir das so vor, dass man in die [mm] x_N(j) [/mm] Richtung um den Wert [mm] \delta [/mm] geht, also auf einer Kante des Zulässigkeitsbereiches. (Die normalen Variablen UND die Schlupfvariablen ergeben ja einen Mehrdimensionalen Zulässigkeitsbereich).
Ist das soweit richtig?
Gruß Docy
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 12:13 Sa 31.10.2009 | | Autor: | piet.t |
Hallo,
ich würde sagen das ist so weit korrekt.
Gruß
piet
|
|
|
|
