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



Basis und BasislösungBearbeiten

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 1Bearbeiten

 

 

   

 

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 2Bearbeiten

 

 

   

 

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 ABearbeiten

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

      x
       
       
       
       
       

 

Basen von A- mit unzulässigen LösungBearbeiten

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.