Optimierung, Nachbar. exakt? < Sonstiges < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 11:06 So 26.10.2008 | | Autor: | guffel |
| Aufgabe | ˙
Es sei S := [mm] {s_1 , . . . , s_2n } [/mm] ⊆ . Gesucht ist eine Partition S = U ∪V , die den Ausdruck [mm] |\summe_{u\in U}^{} [/mm] u - [mm] \summe_{v\in V}^{} [/mm] v|minimiert. Definiere die Nachbarschaft N (U, V ) einer Partition als die Partitionen von S,
die man durch den Austausch je einer Zahl aus U und V erhält.
(a) Ist N exakt?
(b) Ist N exakt, wenn man nur Partitionen mit |U | = |V | = n betrachtet?
|
Hallo,
ich sitz grad vor der Aufgabe und komme nicht weiter. a) ist klar, da hab ich nen Gegenbeispiel. b) wird wohl richtig sein, mir gelingt der Beweis aber nicht. Wir hatten in der Vorlesung, dass N exakt ist, wenn jedes lokale Optimum auch globales Optimum ist. Also:
Sei [mm] P_1=U_1 \cup V_1, U_1= {s_1, ..., s_n} V_1={s_{n+1}, ... , s_{2*n}} [/mm] lokales Optimum. Ich wollte nun erstmal zeigen, dass diese Partion auch lokal optimal ist, wenn man zweimal tauschen kann. Sei also o.B.d.A [mm] \summe_{u\in U_1}^{}u [/mm] >= [mm] \summe_{v\in V_1}^{}v. [/mm] Nun tausche ich [mm] s_1 [/mm] und [mm] s_2 [/mm] gegen [mm] s_{n+1} [/mm] und [mm] s_{n+2},erhalte [/mm] also [mm] P_2=U_2 \cup V_2, U_2={s_3,...,s_{n+2}}, V_2={s_1,s_2, s_{n+3} ,.... , s_{2*n}}.
[/mm]
1.Fall: [mm] s_1 +s_2<= s_{n+1}+ s_{n+2}, [/mm] dann klappt der austausch.
2. Fall: [mm] s_1 [/mm] + [mm] s_2 [/mm] > [mm] s_{n+1}+ s_{n+2} [/mm] und o.B.d.A [mm] s_1>=s_2 [/mm] und [mm] s_{n+1}>= s_{n+2} [/mm] :
Dann hab ich wieder 4. Fälle:
a) [mm] s_1 <=s_2<=s_{n+1} <=s_{n +2}
[/mm]
b) [mm] s_1 <=s_{n+1} <=s_{n +2} <=s_2 [/mm]
c) [mm] s_{n+1} [/mm] <= [mm] s_1 <=s_2<=s_{n +2}
[/mm]
d) [mm] s_1 <=s_{n+1} <=s_2 <=s_{n +2}
[/mm]
a) tausche zuerst [mm] s_1 [/mm] und [mm] s_{n+1}. [/mm] Dann ist [mm] s_1 [/mm] + [mm] s_{n+2} [/mm] +, ....,+ [mm] s_{2*n} [/mm] >= [mm] s_2 [/mm] +,....., + [mm] s_{n+1} [/mm] und [mm] s_1 [/mm] + [mm] s_{n+2} [/mm] +, ....,+ [mm] s_{2*n} [/mm] >= [mm] s_1+s_2 [/mm] +,...,+ [mm] s_n, [/mm] da [mm] P_1 [/mm] lokal optimal ist. Tauschen wir nun [mm] s_2 [/mm] und [mm] s_{n+2}, [/mm] ist [mm] s_1 [/mm] + [mm] s_2 [/mm] + [mm] s_{n+3} [/mm] +,...,+ [mm] s_{2*n} [/mm] >= [mm] s_1 [/mm] + [mm] s_{n+2} [/mm] +, ....,+ [mm] s_{2*n} [/mm] , da [mm] s_2>=s_{n+2} [/mm] und wir sind fertig.
d) klappt genauso, aber bei b) und c) komm ich nicht weiter:
b) tauschen wir also wieder [mm] s_1 [/mm] und [mm] s_{n+1}. [/mm] Dann gilt wieder: [mm] s_{n+1}. [/mm] Dann ist [mm] s_1 [/mm] + [mm] s_{n+2} [/mm] + , ....,+ [mm] s_{2*n} [/mm] >= [mm] s_2 [/mm] +,.....+ [mm] s_{n+1} [/mm] und [mm] s_1 [/mm] + [mm] s_{n+2} [/mm] +, ....,+ [mm] s_{2*n} [/mm] >= [mm] s_1 [/mm] + [mm] s_2,...,+ s_n, [/mm] da [mm] P_1 [/mm] lokal optimal ist. Ich seh aber nicht, wie ich eine Aussage treffen kann, wenn ich nun noch [mm] s_2 [/mm] und [mm] s_{n+2}, s_2<=s_{n+2} [/mm] tausche. Hat da jemand eine Idee?
Gruss Guffel
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 11:20 Di 28.10.2008 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
