Kurs:Algorithmen und Datenstrukturen/Vorlesung/Simplex Verfahren Basis&Basislösung

Aus Wikiversity



Basis und Basislösung[Bearbeiten]

Auf dieser Seite werden die Basen und Basislösungen beim Simplex Verfahren behandelt. Gegeben ist ein lineares Gleichungssystem Dann bilden m lineare unabhängige Spaltenvektoren aus A eine Basis von A. Diese wird mit bezeichnet. B enthält die Indices der Basisvektoren. N enthält die Indices der Nichtbasisvektoren. Die Basislösung ist gegeben durch: dies gilt genau dann wenn: . ist eine zulässige Basis von A, wenn gilt . Wenn ist, dann ist es eine zulässige Basislösung von A.

Beispiel 1[Bearbeiten]

Nicht-Basisvariablen werden stets auf 0 gesetzt. Die zulässige Basislösung von A, die man durch einsetzen erhällt ist dann (0,0,200,300,400).

Beispiel 2[Bearbeiten]

Die zulässige Basislösung von A, die man durch einsetzen erhällt ist dann (0,0,200,300,400) mit dem Zielfunktionswert 200.

Basen von A[Bearbeiten]

Hier gibt es eine Übersicht der Basen von A mit dessen zulässigen Lösungen.

x

Basen von A- mit unzulässigen Lösung[Bearbeiten]

Hier gibt es eine Übersicht der Basen von A mit unzulässigen Lösungen.

x

Diese Basen haben keine zulässige Lösungen, da negative Werte enthält.

Die Teilmengen von A sind keine Basen von A, da die Vektoren jeweils linear abhängig sind.

Discussion