 |
Sei
E(n_1,n_2,...,n_k) = \sum_{i=1}^k e(n_i) = \sum_{i=1}^k ( 1+(n_i-3)^2 )
die Gesamtkostenfunktion.
Falls es ein n_i>4 gäbe, dann lohnt sich ein weiterer Schlitten mit drei Geschenken, denn
e(n_i) = 1+(n_i-3)^2
e(n_i) = 1+(n_i-6+3)^2
e(n_i) = 1+(n_i-6)^2 + 6*(n_i-6) + 9
e(n_i) >= 1+(n_i-6)^2 - 6 + 9
e(n_i) > 1+(e_n-6)^2 + 1
e(n_i) > e(n_i-3) + e(3)
Damit liegt die optimale Lösung (3,3,4) nahe mit E(3,3,4) = 1 + 1 + 2 = 4 .
Bei mehr als 3 Schlitten hätte mindestens ein Schlitten weniger als 3 Geschenke geladen, sonst würde man mindestens 12 Geschenke transportieren. Damit ist für k>3 auf jeden Fall E(n_1,n_2,...,n_k) > 4. Andererseits hätte ein Schlitten bei weniger als 3 Schlitten mindestens 5 Geschenke geladen, so dass die obige Argumentation für n_i>4 gilt.
Also muss die optimale Lösung genau k=3 Schlitten haben. Wenn aber mehr als zwei Schlitten eine von 3 abweichende Anzahl an Geschenken transportieren würden, dann wäre E(n_1,n_2,n_3) wiederum größer als 4. Und die Möglichkeit, dass alle n_i=3 sind, scheidet ebenfalls aus, da dann nur insgesamt 9 Geschenke transportiert werden.
Somit besteht die optimale Beladung aus zwei Schlitten mit je 3 Geschenken -- für den dritten Schlitten bleiben dann genau 4 Geschenke übrig. Das Optimum der Kostenfunktion beträgt 4.
|
16 Zusammenfassung / Summary
