Minimierung der Summe von Quadraten (mit Randbedingungen)

25/08/2010 - 18:19 von Alexander Hompe | Report spam
Liebe Mathematiker!

Ich habe verschiedene Tàtigkeiten von unterschiedlicher Zeitdauer, die
es in verschiedenen Zeitintervallen zu erledigen gilt. Jede Tàtigkeit
wird durch ihren frühesten Anfang, ihre Dauer und ihr spàteste Ende
charakterisiert.
Die Aufgabe besteht darin, diese Tàtigkeiten zeitlich so zu legen,
dass immer möglichst wenig Tàtigkeiten gleichzeitig auszuführen sind.

Bsp.:
Annahme: Beginn und Ende darf immer nur zur vollen Stunde sein.
- Tàtigkeit a)
frühester Beginn: 10 Uhr, Dauer: 3 Stunden, spàtestes Ende: 15 Uhr.
- Tàtigkeit b)
frühester Beginn: 11 Uhr, Dauer: 4 Stunden, spàtestes Ende: 16 Uhr.
Es gibt somit 3 Möglichkeiten für die Tàtigkeit a) und 2 Möglichkeiten
für die Tàtigkeit b)

10 11 12 13 14 15 16 Uhr

a1 a1 a1
a2 a2 a2
a3 a3 a3
b1 b1 b1 b1
b2 b2 b2 b2

Ich möchte gerne herausfinden, dass die a1-Tàtigkeit und die
b2-Tàtigkeit die am besten geeignete Kombination der beiden
Tàtigkeiten ist, weil es bei dieser Kombination nur eine Stunde lang
eine Überschneidung gibt.

^
Anzahl | x
| x x x x x x
+> Uhrzeit
10 11 12 13 14 15 16 Uhr

Meine gesuchte Lösung wàre also
a1 = 1
a2 = 0
a3 = 0
b1 = 0
b2 = 1

Nun _glaube_ ich, dass ich mein gewünschtes Ergebnis bekomme, indem
ich für jede Stunde die Anzahl aller Tàtigkeiten quadriere und für die
Summe dieser Quadrate das/ein Minimum suche.

Mathematisch formuliert habe ich:

10 Uhr: Anzahl z10 = a1
11 Uhr: Anzahl z11 = a1 + a2 + b1
12 Uhr: Anzahl z12 = a1 + a2 + a3 + b1 + b2
13 Uhr: Anzahl z13 = + a2 + a3 + b1 + b2
14 Uhr: Anzahl z14 = + a3 + b1 + b2
15 Uhr: Anzahl z15 = b2

Z10^2 + z11^2 + z12^2 + z13^2 + z14^2 + z15^2 --> MINIMUM

Einsetzen:
(a1 )^2
+ (a1 + a2 + b1 )^2
+ (a1 + a2 + a3 + b1 + b2)^2
+ ( a2 + a3 + b1 + b2)^2
+ ( + a3 + b1 + b2)^2
+ ( b2)^2

Randbedingung:
a1 + a2 + a3 = 1
b1 + b2 = 1
alle Variablen sind entweder 0 oder 1.

Für obiges Beispiel kann man das noch ganz gut per Hand bzw. irgendwie
mit Logik ausrechnen, aber ich benötige einen programmierbaren
Lösungsweg für unterschiedlichste Anzahlen an Tàtigkeiten,
unterschiedlichste Dauern usw.

Und nun meine große Frage: Wie löst man solch eine Minimierungsaufgabe?
Vermutlich kann das jeder Mathestudent im Vordiplom, aber mir (großer
Nichtmathematiker) fehlt jegliche Idee. Es wàre schön, wenn mir jemand
einfach ein paar sachdienliche Begriffe an den Kopf wirft, mit denen
ich dann gezielt suchen kann.

Vielen, vielen Dank,
Alexander

PS: Ich habe schon mal was gehört von einer Methode der kleinsten
Quadrate. Aber ich hab mich mit meinem Problem bis jetzt nicht darin
wiedergefunden. (Habs aber auch noch nicht so richtig verstanden) Wàre
das der richtige Ansatz?
 

Lesen sie die antworten

#1 Thomas Plehn
26/08/2010 - 21:51 | Warnen spam
ich habe jetzt leider wenig zeit, aber google mal nach lagrange
multiplikator!

Am 25.08.2010 18:19, schrieb Alexander Hompe:
Liebe Mathematiker!

Ich habe verschiedene Tàtigkeiten von unterschiedlicher Zeitdauer, die
es in verschiedenen Zeitintervallen zu erledigen gilt. Jede Tàtigkeit
wird durch ihren frühesten Anfang, ihre Dauer und ihr spàteste Ende
charakterisiert.
Die Aufgabe besteht darin, diese Tàtigkeiten zeitlich so zu legen, dass
immer möglichst wenig Tàtigkeiten gleichzeitig auszuführen sind.

Bsp.:
Annahme: Beginn und Ende darf immer nur zur vollen Stunde sein.
- Tàtigkeit a)
frühester Beginn: 10 Uhr, Dauer: 3 Stunden, spàtestes Ende: 15 Uhr.
- Tàtigkeit b)
frühester Beginn: 11 Uhr, Dauer: 4 Stunden, spàtestes Ende: 16 Uhr.
Es gibt somit 3 Möglichkeiten für die Tàtigkeit a) und 2 Möglichkeiten
für die Tàtigkeit b)

10 11 12 13 14 15 16 Uhr

a1 a1 a1
a2 a2 a2
a3 a3 a3
b1 b1 b1 b1
b2 b2 b2 b2

Ich möchte gerne herausfinden, dass die a1-Tàtigkeit und die
b2-Tàtigkeit die am besten geeignete Kombination der beiden Tàtigkeiten
ist, weil es bei dieser Kombination nur eine Stunde lang eine
Überschneidung gibt.

^
Anzahl | x
| x x x x x x
+> Uhrzeit
10 11 12 13 14 15 16 Uhr

Meine gesuchte Lösung wàre also
a1 = 1
a2 = 0
a3 = 0
b1 = 0
b2 = 1

Nun _glaube_ ich, dass ich mein gewünschtes Ergebnis bekomme, indem ich
für jede Stunde die Anzahl aller Tàtigkeiten quadriere und für die Summe
dieser Quadrate das/ein Minimum suche.

Mathematisch formuliert habe ich:

10 Uhr: Anzahl z10 = a1
11 Uhr: Anzahl z11 = a1 + a2 + b1
12 Uhr: Anzahl z12 = a1 + a2 + a3 + b1 + b2
13 Uhr: Anzahl z13 = + a2 + a3 + b1 + b2
14 Uhr: Anzahl z14 = + a3 + b1 + b2
15 Uhr: Anzahl z15 = b2

Z10^2 + z11^2 + z12^2 + z13^2 + z14^2 + z15^2 --> MINIMUM

Einsetzen:
(a1 )^2
+ (a1 + a2 + b1 )^2
+ (a1 + a2 + a3 + b1 + b2)^2
+ ( a2 + a3 + b1 + b2)^2
+ ( + a3 + b1 + b2)^2
+ ( b2)^2

Randbedingung:
a1 + a2 + a3 = 1
b1 + b2 = 1
alle Variablen sind entweder 0 oder 1.

Für obiges Beispiel kann man das noch ganz gut per Hand bzw. irgendwie
mit Logik ausrechnen, aber ich benötige einen programmierbaren
Lösungsweg für unterschiedlichste Anzahlen an Tàtigkeiten,
unterschiedlichste Dauern usw.

Und nun meine große Frage: Wie löst man solch eine Minimierungsaufgabe?
Vermutlich kann das jeder Mathestudent im Vordiplom, aber mir (großer
Nichtmathematiker) fehlt jegliche Idee. Es wàre schön, wenn mir jemand
einfach ein paar sachdienliche Begriffe an den Kopf wirft, mit denen ich
dann gezielt suchen kann.

Vielen, vielen Dank,
Alexander

PS: Ich habe schon mal was gehört von einer Methode der kleinsten
Quadrate. Aber ich hab mich mit meinem Problem bis jetzt nicht darin
wiedergefunden. (Habs aber auch noch nicht so richtig verstanden) Wàre
das der richtige Ansatz?

Ähnliche fragen