https://wiki-de.moshellshocker.dns64.de/index.php?action=history&feed=atom&title=LP-RelaxationLP-Relaxation - Versionsgeschichte2026-05-24T16:49:16ZVersionsgeschichte dieser Seite in Wikipedia (Deutsch) – Lokale KopieMediaWiki 1.43.8https://wiki-de.moshellshocker.dns64.de/index.php?title=LP-Relaxation&diff=1199230&oldid=previmported>BumbleMath: Link hinzugefügt2023-12-11T17:54:18Z<p>Link hinzugefügt</p>
<p><b>Neue Seite</b></p><div>Als '''LP-Relaxation''' (abgeleitet von [[Lineare Programmierung]]) wird bezeichnet, wenn bei einem Problem der<br />
[[Ganzzahlige lineare Optimierung|ganzzahligen linearen Optimierung]] die Forderung der Ganzzahligkeit aufgegeben wird.<br />
<br />
So ersetzt man z.&nbsp;B. [[Nebenbedingung]]en der Gestalt<br />
:<math>x_i\in\{0,1\}</math><br />
des originalen ganzzahligen [[Optimierungsproblem|Optimierungsproblems]] durch die ''relaxierten'' Nebenbedingungen<br />
:<math>0 \le x_i \le 1.</math><br />
<br />
Das Problem („Programm“) lässt sich in der relaxierten Form mit Hilfe der [[Lineare Optimierung|linearen Optimierung]] lösen. Die so entstandene reelle Lösung erfüllt nur in Ausnahmefällen die Ganzzahligkeitsbedingungen des ursprünglichen Problems, mit ihrer Hilfe können jedoch Schlüsse über die Lösung des ursprünglichen Problems gezogen werden. Die Lösung des relaxierten Problems kann auch als Näherungslösung für einen Algorithmus zur ganzzahligen Optimierung verwendet werden.<br />
<br />
Dies ist von Interesse, da durch die LP-Relaxation ein [[NP-schwer]]es (ganzzahliges) Optimierungsproblem in ein verwandtes (reelles) Problem transferiert wird, welches in [[Polynomialzeit|polynomialer Zeit]] gelöst werden kann.<br />
<br />
Die Methode wurde von [[Shmuel Agmon]] im Jahr 1954 beschrieben.<br />
<br />
Von einer ''Relaxation'' im Kontext eines Optimierungsproblems (z.&nbsp;B. Maximierung einer Zielfunktion) wird allgemein dann gesprochen, wenn die Menge zulässiger Lösungen vergrößert wird. Hierdurch wird der maximale Zielfunktionswert nicht verkleinert.<br />
<br />
== Beispiel ==<br />
Ein ausführliches und illustratives Beispiel mit Skizze wird im Artikel [[Ganzzahlige lineare Optimierung#Beispiele|ganzzahlige lineare Optimierung]] angegeben.<br />
<br />
== Literatur ==<br />
*{{Literatur|Autor=Shmuel Agmon|Titel=The relaxation method for linear inequalities|Sammelwerk=Canadian Journal of Mathematics|Band=6|Jahr=1954|Seiten=382–392|DOI=10.4153/CJM-1954-037-2}}<br />
<br />
{{SORTIERUNG:Lp-Relaxation}}<br />
[[Kategorie:Lineare Optimierung]]<br />
[[Kategorie:Wirtschaftsmathematik]]</div>imported>BumbleMath