Wie löse ich dieses Optimierungsproblem?
Ich benötige für die Konfiguration einer Software die Lösung des folgenden Problems:
d, q, b, a sind gesucht.
Evtl. gibt es keine Lösung. Falls es mindestens eine gibt, benötige ich
Bei Wolfram Alpha bin ich mir nicht sicher ob ich keine Lösung erhalte, weil es keine gibt, oder weil es missinterpretiert wird.
Bruteforce Ausprobieren aller Ganzzahlen in Python hat ergeben, dass es jede Menge Lösungen gibt, jeweils mit b=100 und a=0.
Die Lösung bei der zusätzlich max{d-q} gilt, ist b=100, a=0 d=255, a=128.
Das ist die Lösung auf die ich ursprünglich durch reine Überlegung im Kopf gekommen war daher leider nicht zu gebrauchen.
Das eigentliche Problem wäre nicht f(0.01 * b) = 128 gewesen, sondern f(1) = 128 = f(a). Oder sowas in der Art. Ich geh wohl mal schlafen.
Sicher, dass es a >= 0 und nicht a > 0 heißen sollte?
In der Anwendung darf a=0 sein, ob das bei der Optimierung Schwierigkeiten macht, weiß ich leider nicht
2 Antworten
f ist eine Gerade mit Steigung d−q.
- Entweder ist d=q=128, dann kannst du a und b frei wählen,
- oder es gilt d−q≠0 und b=100a.
b−a wird maximal für b=100 und – in Fall 2 – a=1. Aus f(1)=128 folgt dann
(d−q)/100=128−q ⇔ d=12800−99q.
Je kleiner q, desto größer d und damit d−q. Das Maximum wird also am Rand für d=255 und q=(12800−255)/99≈126,7 angenommen. Da ist d−q≈128,3. Der beste ganzzahlige Wert liegt bei q=127 und d=227 mit d−q=100.
Fazit:
- Entweder gehst Du aufs Ganze und nimmst Fall 1: b−a=100 und zwangsläufig d−q=0,
- oder Du begnügst Dich in Fall 2 mit b−a=99 und schindest dabei noch d−q≈128,3 raus.
Das eigentliche Problem wäre [...] f(1) = 128 = f(a)
Bei d≠q folgt daraus zwangsläufig a=1, weil f dann bijektiv ist.
Upps, ich sehe erst jetzt Deine Nebenbedingung d>q. Damit hat sich Fall 1 wohl erledigt.
Hallo.
- b = 100
- a = 1
- d = 227
- q = 127
Wäre eine Möglichkeit, wenn ich mich nicht täusche.
Allerdings übernehme ich keine Garantie auf Richtigkeit, ist schließlich 2 Uhr. 😉
Auch steht noch die Frage im Raum, zu welchen Zahlenmengen die Variablen gehören? Ich werde heute nicht mehr dazu kommen dir nochmals zu antworten, hoffe aber die eine Lösung hilft dir bereits weiter.
LG
Hallo erneut.
Also wenn sich alle Variablen so eingrenzen lassen, dann ist das ja kein Problem:
for a in range(1, 101):
b = a/10000
for q in range(0,255):
for d in range(q+1, 256):
if (b*(d-q)+q)==128:
print(f"a={a/100},b={a},d={d},q={q}")
Liefert neben meiner bereits genannten Lösung ebenfalls noch a=0.8,b=80,d=252,q=127
a darf nicht 0 sein, da sonst a und b/100 verschieden sind und demnach ein unterschiedliches Ergebnis liefern. Ausnahme wäre, wenn (d-q) = 0 ist, aber das darf durch die Vorgaben ja auch nicht sein, da d>q sein muss.
Damit war mein Instinkt richtig, der mir gesagt hat, dass a möglichst am Maximum gewählt werden sollte (1), da man dadurch den größtmöglichen Faktor bekommt. Wird dieser zu klein, ist es durch die Limitierung von 255 auf d praktisch unmöglich noch auf 128 zu kommen.
Auch muss a eine Zahl sein, die als Divisor von 1 ein endliches Ergebnis erzielt. In deinem Fall sogar auf 2 Nachkommastellen limitiert. Da bleiben zum einen nicht viele übrig, zum anderen darf der Faktor ja wie gesagt nicht zu klein werden.
Mit deinen Vorgaben gibt es damit nur diese beiden Möglichkeiten. 👍
Soderle.
Hatte auf der Zugfahrt aus großer Langeweile noch mal drüber nachgedacht und wir können die Schleifendurchläufe natürlich noch massiv verkürzen.
Wie bereits erläutert muss a größer 0 sein, da 0.01b = a sein muss, gleichzeitig aber gilt, dass b > a ist. Wenn a = 0 wäre, wären 0.01b ebenfalls 0. Dann wäre b aber gleich a und damit unzulässig!
Da b>=100 sein muss, gilt 1 >= a > 0 und b = 100a. x/100 kann also maximal 0.01 ergeben und minimal > 0!
Ferner kann auch der Klammerinhalt nicht 0 werden, da d>q sein muss. Der maximale Klammerinhalt ist 255-0 = 255. Wenn wir dies mit 0.01 multiplizieren, wird also das Produkt, welches zum ersten Summanden wird, maximal 2,55.
q hingegen muss kleiner 128 sein, da der erste Summand > 0 ergibt. Wenn q größer oder gleich 128 wäre, wäre die Summe größer 128.
q_min = 128 - 2,55 = 125,45
Wenn wir dieses q nun erneut in die Klammer mit d füllen, verändert sich aber wieder das q_min:
0,01(255 - 128 + 2,55) = 1,2955
0,01(255 - 128 + 1,2955) = 1,282955
0,01(255 - 128 + 1,282955) = 1,28282955
...
Dies nähert sich immer weiter einem q_min von 126,7171... an. Damit gilt:
128 > q > 126,717171...
Und wenn d als auch q natürliche Zahlen sein müssen, bleibt für q nur 127 übrig. Damit muss der erste Summand immer 128-127=1 ergeben. Da 1 der maximalste erste Faktor ist, darf die geringste Differenz zwischen d und q demnach nicht kleiner als 100 werden. Damit muss d>=227 sein!
Der Klammerinhalt kann maximal
255 - 127 = 128
ergeben. Damit das Produkt eine 1 wird, muss a mindestens
1 / (0.01*128) = 0,78125
sein. Da a und b auf 2 Nachkommastellen limitiert sind, gilt demnach
1 >= a >= 0,79
Zusammenfassend lassen sich also folgende Einschränkungen festlegen:
1 >= a > 0,79
b = 100a
255 >= d >= 227
q = 127
Womit wir das Schleifenkonstrukt verkürzen können auf
for a in range(79, 101):
for d in range(227, 256):
if ((a/10000)*(127-q)+127)==128:
print(f"a={a/100},b={a},d={d},q=127")
Wie du siehst war die Zugfahrt extremst langweilig! 😉 Dieses Gedankenspiel ändert nichts am Ergebnis, aber so würde eine Optimierung der Parameterfindung ablaufen. Viel Denkarbeit über Optimierung der Grenzen.
Von 3.264.000 Schleifendurchläufe runter auf 638 Durchläufe.
LG
Ja, das Problem mit der Uhrzeit hab ich auch :D Danke für die Mühen
b, a sind Kommazahlen mit 2 Nachkommastellen, d und q sind Ganzzahlen - aber so genau muss die Lösung gar nicht sein
Ich habe jetzt realisiert, dass - sinnvoller Weise - a natürlich gerade der minimale Wert ist, für den f(x) = 128 gilt.
Leider ergibt sich daraus, dann (die Erläuterung die von meinem Problem abhängt erspare ich mal), dass das was ich mir erhofft habe nicht möglich ist und ich bereits die optimale Lösung habe