Simplexalgorithmus < Operations Research < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 09:23 Mi 05.12.2018 | | Autor: | Noya |
Hallo ihr Lieben,
ich habe eine Frage zum Simplexalgorithmus.
Phase 1:
1. Bestimme Subsystem Ax=b , [mm] x\ge [/mm] 0 von A'x [mm] \le [/mm] b' [mm] x\ge [/mm] 0, so dass Restriktionspolyeder unverändert bleibt und die Zusatzvor. rg A=m = Zeilenanzahl von A < Spaltenanzahl von A erfüllt ist (falls möglich)
2. Bestimmte zulässige Basis [mm] A_B [/mm] von A, und Nichtbasis [mm] A_B
[/mm]
3. Brechne
[mm] A_B^{-1}, [/mm]
[mm] \overline{A}=A_B^{-1}A_N, [/mm]
[mm] \overline{b}=A_B^{-1}b
[/mm]
[mm] \overline{c}^T=c_N^T-c_B^TA_B^{-1}A_N [/mm] (=reduzierte Kosten)
[mm] c_0=c_B^T \overline{b}
[/mm]
Phase 2:
1.Schritt
Gilt [mm] \overline{c_i} \le [/mm] 0 für i=1,..,n-m so ist aktuelle Basislösung optimal. Gib den Vektor x mit [mm] x_B=\overline{b} [/mm] und [mm] x_N=0 [/mm] aus. Der Optimalwert ist [mm] c_0.
[/mm]
STOP!
Falls [mm] \overline{c_i}>0 [/mm] für ein i [mm] \in \{1,...,n-m} [/mm] gehe zu Schritt2.
2.Schritt
Wähle ein s [mm] \in \{1,...,n-m\} [/mm] mit [mm] \overline{c_s}>0
[/mm]
Schritt3:
Gilt [mm] \overline{A_{\circ,s}}\le [/mm] 0, so ist lineares Programm unbeschränkt.
STOP
Falls [mm] \overline{a_{is}}>0 [/mm] für ein i [mm] \in [/mm] {1,...,m} gehe zu Schritt4
Schritt4:
Berechne [mm] \lambda_0=min \{\bruch{\overline{b_i}}{\overline{a_{is}}}: \overline{a_{is}} >0, i=1,...,m\}
[/mm]
usw.
In der zweiten Phase kommt man ja, falls die reduzierten Kosten > 0 sind und das Problem nicht unbeschränkt ist zur "Bestimmung der Schrittweite"(Schritt4)
"Berechne [mm] \lambda_0=min \{\bruch{\overline{b_i}}{\overline{a_{is}}}: \overline{a_{is}} >0, i=1,...,m\}"
[/mm]
Meine Frage ist : was passiert wenn [mm] \lambda_0=0 [/mm] bzw [mm] \overline{b_i}=0 [/mm] ist? Wann kann das passieren?Und was bedeutet das?
[mm] \overline{b_i} [/mm] ist ja die i-zeile von [mm] \overline{b}
[/mm]
und
[mm] \overline{b}=A_B^{-1}b
[/mm]
Entweder ist die Inverse der zulässigen Basis =0 oder die rechte Seite b=0.
Liebe Grüße und vielen Dank
Noya
|
|
| |
|
| Status: |
(Frage) überfällig | | Datum: | 09:49 Fr 07.12.2018 | | Autor: | Noya |
Hallo!
Ah. Ich glaub ich weiß was das dann bedeutet und zwar
Heißt eine basislösung x zu [mm] A_B [/mm] nichtentartet wenn [mm] x_B=A_B^{-1}b =\overline{b}>0
[/mm]
Und somit wenn [mm] \lambda_0=0 [/mm] ist [mm] \overline{b}=0 [/mm] und somit ist die Basis entartet?
aber ich hab noch nicht ganz verstanden was entartet bedeutet! Kann mir das jemand erklären?
Vielen Dank!
Noya
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 10:20 Mo 10.12.2018 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 10:20 Sa 08.12.2018 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
