duales Simplexverfahren < Operations Research < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 20:57 Sa 04.04.2009 | | Autor: | munch |
| Aufgabe | Hallo
Gegeben sei das lineare Optimierungsproblem
(P)
max [mm] 2x_1 [/mm] + [mm] 3x_2 [/mm] + [mm] 5x_3 [/mm]
bei
[mm] x_1 [/mm] + [mm] 2x_2 [/mm] + [mm] 5x_3 \le [/mm] -1
[mm] 6x_1 +2x_3 \le [/mm] 1
[mm] x_3 \le [/mm] 0
[mm] x_1 [/mm] + [mm] x_2 [/mm] + [mm] 3x_3 \le [/mm] -2
[mm] x_2 \le [/mm] 0
mit dem Optimalpunkt x* = (-1/2 , 0 , [mm] -1/2)^T
[/mm]
Bestimme mit Hilfe eines Satzes vom komplementären Schlupf einen Optimalpunkt des zu (P) dualen Problems |
Lösung
Das duale Problem lautet
(D) min [mm] -y_1 [/mm] + [mm] y_2 [/mm] - [mm] 2y_4
[/mm]
bei [mm] y_1 [/mm] + [mm] 6y_2 [/mm] + [mm] y_4 [/mm] = 2
[mm] 2y_1 [/mm] + [mm] y_4+y_5 [/mm] = 3
[mm] y_1 [/mm] + [mm] 2y_2 [/mm] + [mm] y_3 [/mm] + [mm] 3y_4 [/mm] = 5
[mm] y_i \ge [/mm] 0
Erste Frage: Warum gilt in den drei Gleichungen Gleichheit und nicht überall [mm] \ge?
[/mm]
x* ist Lösung von (P)
Die 2. und 3. Ungleichung sind nicht aktiv.
Daher folgt mit dem Satz des Komplementären Schlupfes [mm] y_2 [/mm] * = [mm] y_3 [/mm] * = 0
Zweite Frage: Weiß jemand, was es bedeutet, dass die 2. und 3. Ungleichung nicht aktiv sind?
Ich habe da nicht die geringste Ahnung, dachte erst, dass [mm] y_i [/mm] ganzzahlig (sogar größer gleich 0) sind und durch das [mm] 6y_2 [/mm] folgt, [mm] y_2 [/mm] muss = 0 sein, weil [mm] 6y_2 [/mm] = 6*1 > 2... Also dann wäre die eine Ungleichung nicht mehr erfüllt.
Ich sehe einfach nicht, wieso [mm] y_2 [/mm] und [mm] y_3 [/mm] gestrichen werden bzw. auf Null gesetzt werden. Kann mir das jemand erläutern?
Grüße, munch
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Frage) überfällig | | Datum: | 21:19 Mo 06.04.2009 | | Autor: | munch |
> Hallo
>
> Gegeben sei das lineare Optimierungsproblem
>
> (P)
>
> max [mm]2x_1[/mm] + [mm]3x_2[/mm] + [mm]5x_3[/mm]
>
> bei
>
> [mm]x_1[/mm] + [mm]2x_2[/mm] + [mm]5x_3 \le[/mm] -1
>
> [mm]6x_1 +2x_3 \le[/mm] 1
>
> [mm]x_3 \le[/mm] 0
>
> [mm]x_1[/mm] + [mm]x_2[/mm] + [mm]3x_3 \le[/mm] -2
>
> [mm]x_2 \le[/mm] 0
>
> mit dem Optimalpunkt x* = (-1/2 , 0 , [mm]-1/2)^T[/mm]
>
> Bestimme mit Hilfe eines Satzes vom komplementären Schlupf
> einen Optimalpunkt des zu (P) dualen Problems
> Lösung
>
> Das duale Problem lautet
> (D) min [mm]-y_1[/mm] + [mm]y_2[/mm] - [mm]2y_4[/mm]
>
> bei [mm]y_1[/mm] + [mm]6y_2[/mm] + [mm]y_4[/mm] = 2
>
> [mm]2y_1[/mm] + [mm]y_4+y_5[/mm] = 3
>
> [mm]y_1[/mm] + [mm]2y_2[/mm] + [mm]y_3[/mm] + [mm]3y_4[/mm] = 5
>
> [mm]y_i \ge[/mm] 0
>
> Erste Frage: Warum gilt in den drei Gleichungen Gleichheit
> und nicht überall [mm]\ge?[/mm]
>
> x* ist Lösung von (P)
> Die 2. und 3. Ungleichung sind nicht aktiv.
>
> Daher folgt mit dem Satz des Komplementären Schlupfes [mm]y_2[/mm] *
> = [mm]y_3[/mm] * = 0
>
> Zweite Frage: Weiß jemand, was es bedeutet, dass die 2. und
> 3. Ungleichung nicht aktiv sind?
>
> Ich habe da nicht die geringste Ahnung, dachte erst, dass
> [mm]y_i[/mm] ganzzahlig (sogar größer gleich 0) sind und durch das
> [mm]6y_2[/mm] folgt, [mm]y_2[/mm] muss = 0 sein, weil [mm]6y_2[/mm] = 6*1 > 2... Also
> dann wäre die eine Ungleichung nicht mehr erfüllt.
>
> Ich sehe einfach nicht, wieso [mm]y_2[/mm] und [mm]y_3[/mm] gestrichen werden
> bzw. auf Null gesetzt werden. Kann mir das jemand
> erläutern?
>
> Grüße, munch
>
> Ich habe diese Frage in keinem Forum auf anderen
> Internetseiten gestellt.
Weiß das denn wirklich keiner?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:21 Do 07.05.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:20 Di 05.05.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
