Ersatznebenbedingung < Operations Research < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 15:37 Fr 20.03.2015 | | Autor: | David15 |
| Aufgabe | Gegeben ist das folgende binäre lineare Optimierungsproblem (B).
max z = [mm] -6x_{1}-3x_{2}-4x_{3}-8x_{4}-1x_{5}
[/mm]
s.d.
[mm] -2x_{1}-6x_{2}-8x_{3}-2x_{4}+2x_{5}\le-12
[/mm]
[mm] -8x_{1}-2x_{2}+2x_{3}-0x_{4}-4x_{5}\le-6
[/mm]
[mm] -4x_{1}+2x_{2}+2x_{3}-4x_{4}+2x_{5}\le-4
[/mm]
[mm] x_{1},\ldots,x_{5}\in(0;1)
[/mm]
Die optimale Lösung der LP-Relaxation von B lautet [mm] x^{T}=(1,\bruch{1}{7},1,\bruch{4}{7},0).
[/mm]
Die Nebenbedingung [mm] -8x_{1}-3x_{2}-5x_{3}-8x_{4}+5x_{5}\le-18 [/mm] ist zudem beste Ersatznebenbedingung für obiges binäres Problem (B).
Aufgabe: Überprüfen Sie, welche Variablen anhand der gegebenen Ersatznebenbedingung fixiert werden können und geben Sie deren Werte explizit an. |
Hallo zusammen!
Zur Lösung der Aufgabe suche ich mal wieder euren Rat.
Wenn ich davon ausgehe, dass diejenigen Werte in der LP-Relaxation, die sowieso schon den Wert 1 oder den Wert 0 haben, direkt in die ENB eingesetzt werden, hätte ich ja folgende Ungleichung:
[mm] -3x_{2}-8x_{4}\le-5.
[/mm]
Nun muss ich ja noch die -5 unterbieten. Dies erreiche ich, indem ich [mm] x_{4}=1 [/mm] setze:
[mm] -3x_{2}\le3\gdw{x_{2}}\ge-1
[/mm]
Konkret würde ich als wie folgt fixieren:
[mm] x_{1}=x_{3}=x_{4}=1
[/mm]
[mm] x_{5}=0
[/mm]
[mm] x_{2} [/mm] bliebe demnach unfixiert. Wie würdet ihr in diesem Fall vorgehen? Stimmt meine Vorgehensweise? Danke im Voraus!
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:20 So 22.03.2015 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
