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



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.