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
 

LP-Relaxation

Lässt man bei einem ganzzahligen linearen Optimierungsmodell die Forderung nach Ganzzahligkeit weg, so ergibt sich ein LP-Modell (mit reellwertigen Variablen), das sich z.B. mit dem Simplex-Algorithmus lösen lässt. Diese Art der Relaxation wird als LP-Relaxation bezeichnet. Betrachten wir als Beispiel das Knapsack- Problem, so entsteht die LP-Relaxation dadurch, dass die Binärbedingungen (für j = 1, ..., n) zu abgeschwächt werden. Die optimale Lösung der Relaxation lässt sich hierbei leicht durch Berechnen und absteigendes Sortieren relativer Nutzenwerte pro Gewichtseinheit des Rucksacks bestimmen. Die Gegenstände werden in dieser Reihenfolge in den Rucksack aufgenommen; falls einer dabei nicht mehr vollständig hineinpasst, wird er mit dem größtmöglichen Anteil eingeplant. Der zugehörige optimale Zielfunktionswert der LPRelaxation liefert eine obere Schranke für den optimalen Zielfunktionswert des Knapsack-Problems. Die Tabelle zeigt die Daten einer Beispielinstanz mit n = 3 Gegenständen. Das maximale Rucksackgewicht beträgt G = 15. Anhand der relativen Nutzenwerte ergibt sich die Reihenfolge 3, 1, 2. Die Lösung der Relaxation ist x = (1, 2/3, 1), woraus eine obere Schranke von 5 + 4 + 8 = 17 ergibt.

Das LP-Modell, das aus einem IP-Modell entsteht, wenn man dessen Ganzzahligkeitsbedingungen weglässt, heisst zugehörige LP-Relaxation. Im Branch-and-Bound/Cut-Algorithmus wird zu jedem Teilmodell die zugehörige LP-Relaxation gelöst. Insbesondere wird zu Beginn die LP-Relaxation des Original-Modells gelöst. Siehe auch   Optimierungsmodelle, mathematische (mit Literaturangaben).

Vorhergehender Fachbegriff: LP-Preprocessing | Nächster Fachbegriff: LP-Relaxation eines IP-Modells



  Diesen Artikel der Redaktion als fehlerhaft melden & zur Bearbeitung vormerken

   
 
 

   Weitere Begriffe : Portfoliodiversifikation | Stimmverbot | Postponement-Prinzip

   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


     © 2023-2024 Wirtschaftslexikon24.com       All rights reserved.      Home  |  Datenschutzbestimmungen  |  Impressum  |  Rechtliche Hinweise
Aktuelles Wirtschaftslexikon