Verschoben! Basislösung, nicht zulässige in zulässige Basislösung umwandeln

Neue Frage »

Bobby16 Auf diesen Beitrag antworten »
Basislösung, nicht zulässige in zulässige Basislösung umwandeln
Meine Frage:
Gegeben ist die Menge {x:Ax=b} mit



Der Vektor x=(1,1,1,1)^T ist zulässig, aber keine Basislösung. Wandeln Sie diese Lösung in eine zulässige Basislösung um.

Meine Ideen:
Ok, dass s=(1,1,1,1)^T keine zulässige Basislösung ist, ist klar.

Habe eine Anleitung im Skript wie das angeblich funktionieren soll aber verstehe das nicht:

Angenommen x1>0,....xp>0 und xp+1=0,....xn=0 und die Spalten {a1,...ap} von A sind linear abhängig. Dann gibt es y ungleich 0, sodass A*y=0. Damit ist x(t):=x+ty für genügend kleine t ebenfalls zulässig. Der Parameter t wird dann so gewählt, dass zumindest eine weitere Komponente von x(t) Null wird. Dies wird iteriert, bis eine Basislösung erreicht wird.

Wäre sehr dankbar, wenn mir jemand helfen könnte. smile
Elvis Auf diesen Beitrag antworten »

Ich verstehe das auch nicht, aber Du weißt offensichtlich mehr als ich. Du sagst ja, es sei Dir klar, dass x=(1,1,1,1)^T keine zulässige Basislösung ist. Könntest Du mir bitte erklären, was eine "zulässige Lösung", eine "Basislösung" und eine "zulässige Basislösung" ist ?
python_15 Auf diesen Beitrag antworten »

Hallo!

Hier geht es vermutlich um Lineare Optimierung.
Sei und sei eine Menge von Spaltenindizes. Eine Lösung des Systems heißt Basislösung, wenn die Untermatrix , bestehend aus den Spalten B, invertierbar ist.
Eine Lösung heißt zulässig, wenn alle Komponenten der Lösung .

Nun zur Aufgabe: Die Lösung soll in eine Basislösung umgewandelt werden.

Zitat:
Angenommen x1>0,....xp>0 und xp+1=0,....xn=0 und die Spalten {a1,...ap} von A sind linear abhängig.

Dies trifft zu, mit . Die ersten vier Spalten der Matrix A sind sicher linear abhängig.

Zitat:
Dann gibt es y ungleich 0, sodass A*y=0. Damit ist x(t):=x+ty für genügend kleine t ebenfalls zulässig. Der Parameter t wird dann so gewählt, dass zumindest eine weitere Komponente von x(t) Null wird.

Suche dir nun ein mit . Hast du dieses , so wähle den Parameter folgendermaßen: .
Bildest du nun , so wird mindestens eine weitere Komponente von Null, und die Lösung ist noch immer zulässig. Ist nun Basislösung, so bist du fertig, ansonsten führst du diese Schritte nochmal durch, bis du eine Basislösung erhalten hast!
python_15 Auf diesen Beitrag antworten »

@Bobby16:
Übrigens ist der Titel dieses Beitrages unpassend/verwirrend, denn die gegebene Lösung ist sehr wohl zulässig, allerdings keine Basislösung. Korrekt wäre "zulässige Lösung in zulässige Basislösung umwandeln", nur so nebenbei.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »