Empfehlungen
A   B   C   D   E   F   G   H   I   J   K   L   M   N   O   P   Q   R   S   T   U   V   W   X   Y   Z  
  Home Top 10 Fachbereiche News Hilfe & FAQ
 

Simplex-Algorithmus, primaler

Der primale Simplex-Algorithmus (pSA) ist ein Verfahren zur Lösung von LP-Modellen. Er nutzt die Tatsache aus, dass der Lösungsraum durch eine endliche Anzahl von Eckpunkten (Basislösungen) aufgespannt wird, es handelt sich um ein konvexes, für die im Folgenden verwendeten Begriffe s. LP-Modell). In jedem Eckpunkt liegt eine zulässige Basislösung (BL) vor. Der pSA startet mit einer zulässigen BL und geht in jeder Iteration zu einer benachbarten BL über, falls diese einen höheren Zielfunktionswert aufweist. Gibt es einen solchen benachbarten Eckpunkt nicht, so ist eine optimale Lösung erreicht. Der Übergang von einer BL zu einer benachbarten erfolgt durch Austausch einer Basisvariablen (BV) gegen eine Nichtbasisvariable (NBV), d.h. durch eine entsprechende Transformation des Gleichungssystems, so dass der Zielfunktionswert möglichst stark ansteigt. Bei Handrechnungen wird der pSA mit Hilfe eines Tableaus durchgeführt, das neben dem Gleichungssystem in kanonischer Form auch eine Variable F für den Zielfunktionswert und eine Gleichung für die Zielfunktion (aufgelöst nach F) enthält. In moderner Optimierungssoftware wird der so genannte revidierte pSA eingesetzt, bei dem lediglich ein Teil des Tableaus gespeichert und transformiert werden muss. Die Vorgehensweise des pSA sei an einer Modellinstanz skizzenhaft erläutert (für die Daten s. LP-Modell). Das Starttableau enthält die Daten der kanonischen Form, die BV sind als Zeilenköpfe vermerkt. Die letzte Zeile enthält die Zielfunktion, in der die Zielfunktionskoeffizienten cj der Variablen xj mit negativem Vorzeichen eingetragen werden. In der ersten Iteration wird x2 als neue BV ausgewählt, da ihre Aufnahme in die Basis eine Steigerung des Zielfunktionswertes um c2 = 2 pro Einheit des neuen Wertes von x2 ermöglicht, die höher ist als die (Einheits-) Steigerung für x1 um c1 = 1. Somit wird als so genannte Pivotspalte t = 2 gewählt. Wegen des Steigerungspotenzials soll der Wert von x2 möglichst groß sein. Dabei darf jedoch keine bisherige BV negativ werden. Um dies zu gewährleisten, berechnet man die Quotienten qi = bi/ait für alle Zeilen i = 1,...,m. Der kleinste dieser Werte ist der maximal zulässige Wert für x2. Die in der Pivotzeile s = 3 befindliche BV x5 verlässt die Basis, da sie durch die Erhöhung von x2 zu 0 wird. Nun wird das Tableau durch lineare Transformationen so umgeformt, dass es nach der aktuellen Basis aufgelöst ist. Dazu muss unter der neuen BV x2 ein Einheitsvektor entstehen mit der 1 an der Stelle des Pivotelements (s,t), das im Starttableau mit eckigen Klammern markiert ist. Um dies zu erreichen, wird die Pivotzeile durch das Pivotelement geteilt. Von der ersten Zeile wird die Pivotzeile subtrahiert, von der zweiten wird das 9fache der Pivotzeile subtrahiert, und zur F-Zeile wird das 2-fache der Pivotzeile addiert. Tab. 3 zeigt das entstehende sowie ein weiteres Tableau. Die im Endtableau ablesbare Basislösung x =(30,60,10,0,0) mit F(x) = 150 ist optimal, da die F-Zeile keine negative Eintragung mehr enthält, also kein Basistausch eine weitere Verbesserung verspricht.

Vorhergehender Fachbegriff: Simplex-Algorithmus, dualer | Nächster Fachbegriff: Simplex-Methode



  Diesen Artikel der Redaktion als fehlerhaft melden & zur Bearbeitung vormerken




   
 
 

   Weitere Begriffe : Zins-Dumping | öffentliche Versorgungsunternehmen | öl

   Praxisnahe Definitionen

Nutzen Sie die jeweilige Begriffserklärung bei Ihrer täglichen Arbeit. Jede Definition ist wesentlich umfangreicher angelegt als in einem gewöhnlichen Glossar.

  Marketing

  Definition

  Konditionenpolitik

   Fachbegriffe der Volkswirtschaft

Die Volkswirtschaftslehre stellt einen Grossteil der Fachtermini vor, die Sie in diesem Lexikon finden werden. Viele Begriffe aus der Finanzwelt stehen im Schnittbereich von Betriebswirtschafts- und Volkswirtschaftslehre.

  Investitionsrechnungen

  Marktversagen

  Umsatzsteuer

   Beliebte Artikel

Bestimmte Erklärungen und Begriffsdefinitionen erfreuen sich bei unseren Lesern ganz besonderer Beliebtheit. Diese werden mehrmals pro Jahr aktualisiert.

  Cash Flow

  Bausparen

  Fremdwährungskonto


     © 2015 Wirtschaftslexikon24.com       All rights reserved.      Home  |  Datenschutzbestimmungen  |  Impressum  |  Rechtliche Hinweise
Aktuelles Wirtschaftslexikon