Ich versuche, ein Online-Meeting auf meinem Laptop zu haben. Die Position des Notebooks ist niedrig, sodass der Winkel der Kamera von unten ist. Ich möchte die Höhe meines Notebooks in Eile erhöhen, kann aber nur wenige Bücher verwenden. Notebooks sind größer als Bücher, daher müssen Sie Bücher in zwei Reihen stapeln. Wenn die Höhen der Bücher in den beiden Reihen unterschiedlich sind, ist die Balance schlecht, daher möchte ich die Höhen der Bücher in den beiden Reihen gleich machen.
Stapeln Sie einige Bücher in zwei Reihen und machen Sie sie so hoch wie möglich. Zu diesem Zeitpunkt sollte der Höhenunterschied zwischen den beiden Buchreihen bis zu 1 mm betragen.
Lösen Sie mit Kombinationsoptimierung. Das Verfahren besteht darin, das Problem zu formulieren, ein Modell in Python zu erstellen und es mit einem Löser zu lösen. Siehe auch Python in Optimization.
--Eingabeparameter
--books: Höhe jedes Buches
--limit: Obergrenze des Höhenunterschieds zwischen 2 Spalten
--Variable
--obj: Die untere der Höhen der beiden Reihen
--suml: Höhe in der linken Spalte
--sumr: Höhe in der rechten Spalte
--vl: Gibt an, ob jedes Buch in der linken Spalte gestapelt werden soll (0: nicht stapeln, 1: stapeln)
--vr: Gibt an, ob jedes Buch in der rechten Spalte gestapelt werden soll (0: nicht stapeln, 1: stapeln)
obj ist das kleinere von suml und sumr (1)
--suml ist die Höhe der linken Spalte (2)
--sumr ist die Höhe der rechten Spalte (3)Eingabeparameter werden entsprechend mit Zufallszahlen erstellt.
import random
from ortoolpy import model_max, addvars, addbinvars, lpDot, value
random.seed(1)
books = [random.randint(10, 20) for _ in range(20)] #Buchdicke (mm)
limit = 1 #Zulässiger Unterschied zwischen linker und rechter Höhe (mm)
n = len(books)
m = model_max() #Mathematisches Modell
obj, suml, sumr = addvars(3) #Niedrigere Höhe, linke Höhe, rechte Höhe
vl = addbinvars(n) #Stellen Sie das Buch links
vr = addbinvars(n) #Stellen Sie das Buch rechts
m += obj #Zielfunktion (so hoch wie möglich machen)
m += obj <= suml # (1)
m += obj <= sumr # (1)
m += suml == lpDot(books, vl) # (2)
m += sumr == lpDot(books, vr) # (3)
m += suml - sumr <= limit # (4)
m += sumr - suml <= limit # (4)
for vli, vri in zip(vl, vr):
m += vli + vri <= 1 # (5)
m.solve() #Mit Löser lösen
print(f'{m.status = }')
print(f'{value(suml) = }')
print(f'{value(sumr) = }')
print(f'{[int(value(vli) - value(vri)) for vli, vri in zip(vl, vr)]}')
lpDot (X, Y) ist das innere Produkt von X und Y. "LpDot (books, vl)" ist also die Höhe der linken Spalte.
m.status = 1
value(suml) = 149.0
value(sumr) = 148.0
[-1, -1, -1, 1, -1, 1, -1, 1, 1, 1, -1, 1, 1, 1, -1, -1, -1, 1, 1, -1]
"m.status = 1" bedeutet, dass die optimale Lösung erhalten wurde.
value (X) erhält den Wert der Variablen X.
Die Höhe der linken Spalte beträgt 149 mm, die Höhe der rechten Spalte beträgt 148 mm und die Differenz beträgt 1 mm.
Die endgültige Liste zeigt, dass 1 in der linken Spalte und -1 in der rechten Spalte steht.
Das Obige kann in 0,1 Sekunden berechnet werden, aber wenn "Limit" auf 0 gesetzt ist, beträgt die Berechnungszeit 24 Sekunden (240 Mal). Wie Sie sehen, kann sich bei der Kombinationsoptimierung die Berechnungszeit erheblich ändern, wenn sich die Parameter geringfügig ändern. Wenn Sie das "Limit" auf verschiedene Arten ändern möchten, müssen Sie möglicherweise etwas wie "So lösen Sie das Problem beim Verpacken von Behältern" entwickeln.
Recommended Posts