Intervallkonflikt analytisch lösen

Wissenschaft Mathematik
1

Liebe/-r Experte/-in,

seit geraumer Zeit sitze ich an einem Problem, welches ich am besten an einem kleinen Beispiel beschreibe:

Gegeben sind zwei (Zeit)-Intervalle A[10…130] und B[30…110]. Intervall B liegt offensichtlich in A. Dies stellt einen Konflikt dar. Der Konflikt ist dahingehend zu lösen, dass sich die Intervalle nicht mehr schneiden und dazu noch ein Zeitpuffer p = 30 zwischen den Intervallen beachtet wird.
Folgende Lösungen sind z. B. möglich:

a) A[10…10] B[40…110]
b) A[70…130] B[30…40]

Eine Lösung ist optimal, wenn sich die Verhältnisse aus ursprünglicher Intervalldistanz und neuer Intervalldistanz gleichen (la_alt/la_neu = lb_alt/lb_neu) und die neuen Längen maximal sind.
Optimale Lösungen im Beispiel wären:
c) A(10…52] B[82…110]
la_alt/la_neu = lb_alt/lb_neu = 0.35
d) A[88…130] B[30…58]
la_alt/la_neu = lb_alt/lb_neu = 0.35

Nun ist das Beispiel so gewählt (symmetrisch, einfache Zahlen zum Rechnen), dass sich die Optima leicht ermitteln lassen.

Meine Frage ist nun, ob sich dieses Problem (unter Beachtung des Zeitpuffers p analytisch lösen lässt?* Und wenn ja, wie?

* für Intervalle A[a0…an] und B[b0…bn], für die gilt:
a0 = bn („B liegt in/auf A“).

Ich hoffe, ich konnte mein Problem verstädnlich beschreiben und bedanke mich an dieser Stelle schon einmal für Eure Bemühungen!

Viele Grüße,

Christian

2

Hallo Christian,

wenn ich Dein Problem richtig verstanden habe, dann geht bei der neuen Aufteilung der Intervalle immer ein Stück des großen Intervalls verloren (abgesehen von dem Puffer). In Lösung a) wäre das [110…130] und in b) [10…30].

Für beliebige Intervalle A[a0…an] und B[b0…bn] mit den o.g. Bedingungen wären dann also zwei Lösungsmöglichkeiten zu prüfen:

  1. A’[a0…an’] und B’[b0’…bn] mit an’ + p = b0’
    und
  2. A’’[a0’…an] und B’’[b0…bn’] mit bn’ + p = a0’
    Da die Länge der Intervalle (und ich gehe davon aus, dass Du die Summe der beiden Intervalllängen meinst) maximal sein soll, ist an dieser Stelle schon diejenige Lösungsmöglichkeit zu wählen, für die diese Bedingung erfüllt ist. Falls b0 - a0 > an - bn, so ist dies Möglichkeit 1, andernfalls Möglichkeit 2.
    Sei nun o.B.d.A. Möglichkeit 1 maximal.
    Dann soll gelten
    la_alt/la_neu = lb_alt/lb_neu
    somit
    an-a0/an’-a0 = bn-b0/bn-b0’
    mit
    an’ + p = b0’ (Puffer zwischen den Intervallen)
    also:
    an-a0/an’-a0 = bn-b0/bn-an’-p
    Wir gehen davon aus, dass bn b0’ (ungleich) und a0 an’, dass also eine Lösung wie im Beispiel 1 nicht in Frage kommt, denn dann macht die Quotienten-Bedingung keinen Sinn.
    Daraus folgt durch Umformung:
    (an-a0)*(bn-an’-p) = (bn-b0)*(an’-a0)
    (an-a0)*(bn-p)-an’*(an-a0) = (bn-b0)*an’ - (bn-b0)*a0
    (an-a0)*(bn-p)+(bn-b0)*a0 = an’*(bn-b0+an-a0)
    ((an-a0)*(bn-p)+(bn-b0)*a0) / (bn-b0+an-a0) = an’

Somit hat man die Intervallgrenze an’ aus den bestehenden Werten ermittelt. Man kann dann mit an’+p=b0’ die Intervallgrenze b0’ ermitteln und hat die Lösung.

Falls die Lösungsmöglichkeit 2 maximal sein sollte, setzt man die entsprechenden Variablen anders ein.

Ich hoffe, ich konnte helfen.

Mit freundlichem Gruß

3

Hallo,

leider kann ich Ihnen bei Ihrem Problem nicht groß weiterhelfen.
Analytisch gesehen gibt es keine richtige Variable, nach der die Fkt abgeleitet werden kann.
Ich konnte aber ein Verhältnis zwischen allen Variablen herstellen, falls dies helfen konnte.

(a_n-a_0)/120=(b_n-b_0)/80
Das Verhältnis der Zahlen ist ja gleich groß, 120 und 80 sind als Anfangsintervalle gegeben.
Mit dem Unterschied p zwischen den Zeiten a_n und b_0:
a_n=b_0-p folgt
…
2,5*b_0-1,5*b_n-a_0=p
Hier kann man jetzt die Optimallösung durch einsetzen herausfinden.

Ich hoffe ich konnte Ihnen trotzdem irgendwie helfen.

Lg

4

Hallo Christian,

ich habe noch nicht verstanden, wie die neuen Intervalle zu bilden sind. Das ist mir schon bei

a) A[10…10] B[40…110]
b) A[70…130] B[30…40]

nicht klar. Warum diese Intervalle? Nach welchen Regeln werden sie gebildet?

Viele Grüße,

Heike

5

Hallo cweiss106,

ich trage erstmal zusammen. Gegeben sind zwei Intervalle

A = [a_1,a_2],\quad
B = [b\_1,b\_2]

und eine Zahl p.

Gesucht sind geänderte Intervalle

\tilde A = [\tilde a_1,\tilde a_2],\quad
\tilde B = [\tilde b_1,\tilde b_2],

die die Nebenbedingungen

\frac{a_2 - a_1}{\tilde a_2 - \tilde a_1} =
\frac{b_2 - b_1}{\tilde b_2 - \tilde b_1}

sowie

\tilde a_2 + p = \tilde b_1

erfüllen. Die Anzahl der gesuchten Variablen (4) übersteigt die Anzahl der Bedingungen (2), darum gibt es in der obigen Form in der Regel unendlich viele Lösungen.

Um eine Optimierungsaufgabe daraus zu machen, fehlt noch eine Zielfunktion, die minimiert oder maximiert werden soll. Im vorliegenden Fall bietet sich eine Minimierung des Werts

|\tilde a_1 - a_1| + |\tilde a_2 - a_2| +
|\tilde b_1 - b_1| + |\tilde b_2 - b_2|

oder

(\tilde a_1 - a_1)^2 + (\tilde a_2 - a_2)^2 +
(\tilde b_1 - b_1)^2 + (\tilde b_2 - b_2)^2

an, d.h. die geänderten Intervalle sollen möglichst wenig von den gegebenen Intervallen abweichen. Passt das zu dem Problem?

Auf jeden Fall braucht man noch mehr Bedingungen, so wie Du es beschrieben hast, ist noch zu viel Freiheit drin. Ich denke, man kann dann aber aufgrund der geringen Zahl von Variablen auf eine analytische Loesung hoffen.

HTH
soja

6

Hallo!
Es tut mir leid, aber davon habe ich keine Ahnung…
Viele Grüße!

7

Hallo,

ich poste nur den Lösungsweg, da ich nicht so viel Zeit habe, die Lösung auszurechnen.

Auf ihre Optimierungsaufgabe lässt sich die sogenannte Lagrangesche Multiplikatorenmethode anwenden.

Dazu muss man die Aufgabe etwas formalisieren (das hätten Sie vielleicht besser machen können bei Ihrer Fragestellung :stuck_out_tongue:)

Sei A=[a1,a2], B = [b1,b2], B Teilmenge von A. Sei „Puffer“ p gegeben.
Gesucht sind Intervallgrenzen von C=[c1,c2] und D =[d1,d2], wobei (*) c2+p = d1 (c2 ist „Puffer“-weit von d1 entfernt).
Außerdem gelte (**) (c2-c1)/(a2-a1) = (d2-d1)/(b2-b1). (Das ist das Verhältnis der Längen).

Wir haben zwei lineare Gleichungen ((*) und (**))mit 4 Unbekannten (c1, c2, d1, d2) und 2 davon lassen sichn also eliminieren. Nehmen wir an, wir Eliminieren c2 und d1. Dann ist unsere Aufgabe:

Maximiere d2-c1 (d.h. den Abstand von „Anfang von C“ und „Ende von D“).
Hier war übrigens nicht klar, welche Randpunkte Sie fest haben wollen. Innere (c2, d1)? Äussere? Ich habe mich für die äusseren entschieden.

Also:

Aufgabenstellung:
d2- c1 —> MAX
bei Nebenbeidingungen: (*) und (**).

(1) Das vorbereitende Vorgehen:
c2, d1 eliminieren:
d1 = c2 +p (direkt aus (*)).
c2 = c1(b2-b1)+d2(a2-a1)-p(a2-a1) (folgt aus (**)).
(Das bitte selbst nachrechnen!)

c2 in d1 einsetzen - ergibt eine Gleichung in Abh. von c1 und d2.
c2 und d1 sind nun beide in Abh. von c1 und d2 gegeben.
Diese GLeichungen für c2 und d1 in (**) einsetzen.
Wir erhalten eine Gleichung (***) NUR in Abh. von c1 und d2.
(Bitte diese Gleichung selbst berechnen!)

Benennen wir nun unsere Variablen um:
x:= c1, y:= d2.
In (***) bitte die Variablen entsprechend umbenennen.
Stellen Sie (***) bitte so um, dass alles auf einer Seite steht - also bringen Sie es in die Form g(x,y)=0, wobei g irgend ein Ausdruck in Abhängigkeit von x und y ist).

Wir erhalten eine nue Aufgabe:
Maximiere y-x bei Nebenbeidingung g(x,y) =0.

Lagrangesche Multiplikatorenmethode:

Gegeben ist eine Funktion von R^2 (reellem zweidimensionalem Raum) nach R, nämlich f(x,y) = y-x.
Wir suchen das Maximum dieser Funktion bei der Nebenbeidingung g(x,y) =0.

Vorgehen:

  1. Schreiben Sie den folgenden Ausdruck (+) auf:
    (+) f(x,y) + t * g(x,y) = 0
    Dabei ist t eine neue Unbekannte (der Lagrangesche Multiplikator). Wie und warum diese Methode funktioniert, können Sie Google oder mathematische Literatur fragen.

  2. Leiten Sie beide Seiten der Gleichung nach x ab.
    Sie erhalten eine Gleichung der Form
    irgendwas(x,y,t) = 0.

  3. Leiten Sie beide Seiten der Gleichung nach y ab.
    Sie erhalten eine Gleichung der Form
    irgendwasanderes(x,y,t) = 0.

  4. Schreiben Sie die Gleichung aus 2. und 3. und darunter die Gleichung g(x,y) = 0 untereinander.
    Sie haben jetzt ein Gleichungssystem in Abhängigkeit von 3 Variablen. Die zweite Gleichung enthält den Multiplikator t nicht.
    Stellen Sie die zwei ersten Gleichungen nach t um und setzen Sie sie gleich. Sie haben nun ein Gleichungssystem mit 2 Unbekannten. Lösen Sie es. Sie sind fertig.

Wichtig ist: Die Lösungen sind nur *KANDIDATEN* für Maxima und Minima. Überprüfen Sie die Lösung nach Konsistenz mit „Hinschauen“ - also schmeissen Sie die eventuellen Minima raus, schmeissen Sie die „unmöglichen“ Lösungen (für zB y>x) raus.

Tut mir leid, dass ich das nicht genauer gemacht habe. Ich habe einfach nicht die Zeit.
Hoffe, das hat geholfen.

Tschüss
Lena

8

Hallo Christian,

Du hast ursprünglich A = [a_0, a_n] und B = [b\_0, b\_n] mit a_0 \le b_0 \le b_n \le a_n.

Deine erste Lösung hat doch immer die Form A’ = [a_0, a_n’] und B’ = [b\_0’, b\_n] mit a_0 \le a_n’ \le b_0’ \le b_n.
Die Forderung nach dem Zeitpuffer kann man als b_0’ - a_n’ = p formulieren.
Eine optimale Lösung erfüllt zusätzlich \frac{l(A’)}{l(A)} = \frac{l(B’)}{l(B)}, also \frac{a_n’-a_0}{a_n-a_0} = \frac{b_n-b_0’}{b_n-b_0}.
Das sind zusammen zwei lineare Gleichungen für die beiden Unbekannten a_n’ und b_0’, das sich (außer in nicht-generischen Fällen…) eindeutig lösen läßt.

Für zweite Lösung A’’ = [a_0’’, a_n] und B’’ = [b\_0, b\_n’’] kannst ein analoges Gleichungssystem konstruieren – und lösen.

Reicht das als Tip?
Schöne Grüße,

Manfred

9

Hallo Heike,

erst einmal vielen Dank für Deine Mühen!

Kurz gesagt, zwischen den Intervallen soll eine Mindestseparation p liegen. In der Lösung muss demzzufolge gelten: an + p = b0. Meine Lösung a) und b) sind nur zwei aus einer größeren Menge von Lösungen. Die optimale Lösung beachtet zudem noch die Verhältnisse zwischen alter Länge und neuer Intervalllänge. Oder andersherum gesagt: beide Intervalle sollen im gleichen Verhältnis gekürzt werden, aber nur so weit, wie es nötig ist.

Es gibt wohl - und dabei auch Danke an die anderen Helfer - zwei verschiedene Ansätze (siehe weiter unten).

Viele Grüße und einen schönen Abend!

Christian

10

Hallo Christian,

hier die Lösung - erst einmal an einem Beispiel.

[10, 100] 20 [20, 120] seien gegeben.
Gesucht ist [10, a] 20 [b, 120].

Daraus ergeben sich zwei Gleichungen mit zwei Unbekannten.

  1. (100-10)/(a-10) = (120-20)/(120-b)

  2. a+20 = b

  3. in 1) einsetzen.
    90/(a-10) = 100/(120-(a+20)) = 100/(120-a-20) = 100/(100-a)
    90(100-a) = 100(a-10)
    9000-90a = 100a-1000
    10000 = 190a
    a = 1000/19

Lösung in 2) einsetzen.
b = (1000+380)/19 = 1380/19

Jetzt die allgemeine Lösung.
Gegeben: [al, ar2] p [bl1, br].
Gesucht: [al, ar2] p [bl2, br].

Die beiden Gleichungen:

  1. (ar1-al)/(ar2-al) = (br-bl1)/br-bl2),

  2. ar2 + p = bl2.

  3. in 1) einsetzen.
    (ar1-al)/(ar2-1l) = (br-bl1)/(br-ar2-p)
    (ar1-al)(br-ar2-p) = (br-bl1)(ar2-al)
    ar1*br-al*br-ar1*ar2-p*ar1+p*al = br*ar2-bl1*ar2-br*al+bl1*al
    -ar1*ar2+al*ar2-br*ar2+bl1*ar2 = -ar1*br+al*br+p*ar1-p*al-br*al+bl1*al
    ar2 = (-ar1*br+al*br+p*ar1-p*al-br*al+bl1*al) / (-ar1*ar2+al*ar2-br*ar2+bl1*ar2)

ar2 in 2) einsetzen.
bl2 = (-ar1*br+al*br+p*ar1-p*al-br*al+bl1*al) / (-ar1*ar2+al*ar2-br*ar2+bl1*ar2) + p

Viele Grüße,

Heike

11

Hi,
Ich hoffe, ich hab dein Problem richtig verstanden und versuchs mal.
(Achtung: die folgenden Gedanken enthalten Fehler und sind lediglich zur Inspiration tauglich.)

Alte Intervalle: A[a0…an] und B[b0…bm]
Neue Intervalle: A’[c0…cq] und B’[d0…dr]
Jedes Intervall ist vollständig beschrieben durch ersten Punkt und Länge, also
A -> a0, n
B -> b0, m
A’-> c0, q
B’-> d0, r

Es soll gelten:

Zeitpuffer:
d0 - cq = p oder c0 - dr = p.
Anders formuliert:
d0 - c0 - q = p oder c0 - d0 - r = p.

Verhältnis der Intervalllängen:
n /q = m / r, umgestellt:
r = q*m/n bzw. q = r*n/m.

Ausserdem soll A von A’ und B’ sowie p vollständig überdeckt sein:
n = r + q + p

Also für den Fall, dass B’ das „obere“ Intervall ist (andersrum geht analog):

d0 - c0 - q = p (*)
c0 = a0 (da untere Intervallgrenze von A und A’ übereinstimmen sollen)
q = r*n/m (s.o.)
Einsetzen in (*):
d0 - a0 - r*n/m = p
Somit sind noch r und d0 unbekannt.
Weiter mit der Gleichung von oben:
n = r + q + p = r + r*n/m + p = r*(1+n/m)+p
Also: (n-p)/(1+n/m) = r

12

Sehr geehrter Christian,

die Aufgabe lässt sich analytisch lösen.
Führen Sie eine Variable x ein, die die obere Schranke des unteren Intervalls markiert. x+p wäre dann die untere Schranke des oberen Intervalls. Die jeweils anderen Schranken der beiden neuen Intervalle gewinnen Sie aus den alten Intervallen, wobei gegebenenfalls eine Fallunterscheidung nötig ist.
Die Nebenbedingung, dass die Verhältnisse la_alt/la_neu und lb_alt/lb_neu gleich sein sollen, liefert Ihnen für jeden Fall eine Gleichung, die Sie lösen müssen.
Wählen Sie in Ihrem Beispiel das untere Intervall aus A, so haben Sie die neuen Intervalle [10 , x] und [x+30 , 130], was zur Gleichung (x-10)/120 = (110-(x+30))/80 führt.
Wählen Sie das untere Intervall aus B, so haben Sie in Ihrem Beispiel die neuen Intervalle [30 , x] und [x+30 , 110], was zu Gleichung (x-30)/80 = (130-(x+30))/120 führt.
Beide Fälle führen zu den von Ihnen gefundenen Lösungen, nämlich x = 52 bzw. x = 58. Von diesen Lösungen wählen Sie nun diejenige(n) aus, die die maximalen Intervalle ergeben. Bei Ihrem Beispiel sind beide gleich. Das muss aber nicht unbedingt so sein.

Mit freundlichen Grüßen

Thomas Klingbeil