Simplex - Ecken bestimmen < Sonstiges < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 14:13 Sa 12.07.2008 | | Autor: | error1 |
| Aufgabe | Bestimmen Sie alle Eckpunkte der folgenden Ungleichungssysteme mit Hilfe des Sim-
plexalgorithmus. Untersuchen Sie, ob ausgeartete Ecken existieren und ob der Zulassig-
keitsbereich beschrankt ist. Geben Sie im Fall der Unbeschranktheit die Kegelerzeugenden
an.
[mm] -3x_{1} [/mm] + [mm] x_{2} \le [/mm] 1
[mm] -x_{1} [/mm] + [mm] x_{2} \le [/mm] 2
[mm] x_{1} [/mm] - [mm] 3x_{2} \le [/mm] 3
[mm] x_{1}, x_{2} \ge [/mm] 0
|
Hallo,
also wenn ich die aufgabe zeichne erkenne ich die ecken. Jedoch soll hier mithilfe des simpexalgorithmus gearbeitet werden. Bekomme die Ecken auch raus wenn ich lange genug nach allem Pivotiere.
1. Frage. Gibt es irgendein vorgehen sodass ich sofort immer richtig iteriere oder gilt hier nur probieren?
2.Oohne es aufzuzeichnen, wie weiss ich wieviele ecken es gibt?
3.Wie erkenne ich das etwas eine ausgeartete ecke ist(rechnerisch).
4. Hier ist der zulässigkeitsbereich unbeschränkt wie komme ich auf den positiven kegel?
Danke
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 20:16 Sa 12.07.2008 | | Autor: | koepper |
Hallo error,
> Bestimmen Sie alle Eckpunkte der folgenden
> Ungleichungssysteme mit Hilfe des Sim-
> plexalgorithmus. Untersuchen Sie, ob ausgeartete Ecken
> existieren und ob der Zulassig-
> keitsbereich beschrankt ist. Geben Sie im Fall der
> Unbeschranktheit die Kegelerzeugenden
> an.
>
> [mm]-3x_{1}[/mm] + [mm]x_{2} \le[/mm] 1
> [mm]-x_{1}[/mm] + [mm]x_{2} \le[/mm] 2
> [mm]x_{1}[/mm] - [mm]3x_{2} \le[/mm] 3
>
> [mm]x_{1}, x_{2} \ge[/mm] 0
>
> Hallo,
> also wenn ich die aufgabe zeichne erkenne ich die ecken.
> Jedoch soll hier mithilfe des simpexalgorithmus gearbeitet
> werden. Bekomme die Ecken auch raus wenn ich lange genug
> nach allem Pivotiere.
dafür gibt's keine Garantie.
> 1. Frage. Gibt es irgendein vorgehen sodass ich sofort
> immer richtig iteriere oder gilt hier nur probieren?
Bringe das UGS in Gleichungsform durch Hinzufügen von Schlupfvariablen, so wie im Simplex-Algo.
Aus den dann 5 Variablen wähle alle ${5 [mm] \choose [/mm] 3}$ Basen und prüfe jede von ihnen auf Zulässigkeit.
Die Menge der zulässigen Basen entspricht genau der Menge der Ecken.
Tauchen Ecken mehrfach auf, sind sie entartet.
> 2.Oohne es aufzuzeichnen, wie weiss ich wieviele ecken es
> gibt?
s.o., zählen.
> 3.Wie erkenne ich das etwas eine ausgeartete ecke
> ist(rechnerisch).
s.o.
> 4. Hier ist der zulässigkeitsbereich unbeschränkt wie
> komme ich auf den positiven kegel?
Ermittle den Kern der Matrix. Die positiven Vektoren aus dem Kern sind es.
Überlege auch warum 
LG
Will
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 22:31 Sa 12.07.2008 | | Autor: | error1 |
ok danke bis hierhin.
bestätigt das nicht genau das was ich sagte? Ich iteriere solange durch bis ich durch alle ecken bin. das wäre hier ja 10(?) ("ecken" wobei diese gleich sein können). Dies ist eine klausuraufgabe und ist mit 20 pkten bewertet -> also 20 min bearbeitungszeit. Das erscheint mir doch etwas hoch. Im endeffekt sind doch nur einige wenige ecken interessant (da im zulässigkeitsbereich).diese möchste ich auf schnellsten weg erreichen.
danke
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 13:18 So 13.07.2008 | | Autor: | koepper |
Hallo,
> ok danke bis hierhin.
> bestätigt das nicht genau das was ich sagte? Ich iteriere
was meinst du mit "iterieren"?
Wenn du den Simplex-Algorithmus meinst, dann ist dazu eine Zielfunktion erforderlich.
Und dann wirst du auf dem Weg zum optimalen Punkt nur in den allerseltensten Fällen vorher durch alle Ecken kommen.
> solange durch bis ich durch alle ecken bin. das wäre hier
> ja 10(?) ("ecken" wobei diese gleich sein können). Dies ist
10 Ecken ist richtig. Wobei einige davon unzulässig sein werden,
d.h. außerhalb des Polyeders liegen.
> eine klausuraufgabe und ist mit 20 pkten bewertet -> also
> 20 min bearbeitungszeit. Das erscheint mir doch etwas hoch.
> Im endeffekt sind doch nur einige wenige ecken interessant
> (da im zulässigkeitsbereich).diese möchste ich auf
> schnellsten weg erreichen.
Um per Iteration zu allen möglichen Ecken zu kommen,
müßtest du eine Baumstruktur traversieren, indem du von jeder Basis zu jeder anderen möglichen übergehst.
LG
Will
|
|
|
|
