J'essaye d'avoir une réunion en ligne sur mon ordinateur portable. La position de l'ordinateur portable est basse, donc l'angle de la caméra part du bas. Je souhaite élever rapidement la hauteur de mon ordinateur portable, mais je ne peux utiliser que quelques livres à portée de main. Les ordinateurs portables sont plus grands que les livres, vous devez donc les empiler sur deux rangées. De plus, si les hauteurs des livres des deux rangées sont différentes, l'équilibre sera médiocre, donc je veux que les hauteurs des livres des deux rangées soient à peu près les mêmes.
Empilez quelques livres sur deux rangées et faites-les aussi haut que possible. À ce moment-là, la différence de hauteur entre les deux rangées de livres doit être jusqu'à 1 mm.
Résolvez en utilisant l'optimisation des combinaisons. La procédure consiste à formuler le problème, à créer un modèle en Python et à le résoudre avec un solveur. Voir aussi Python dans l'optimisation.
--Paramètres d'entrée
--books: Hauteur de chaque livre
--limit: limite supérieure de la différence de hauteur entre 2 colonnes
--Variable
--ʻObj: la plus basse des hauteurs des deux rangées --suml: Hauteur dans la colonne de gauche --sumr: Hauteur dans la colonne de droite --vl: s'il faut empiler chaque livre dans la colonne de gauche (0: ne pas empiler, 1: pile) --vr: s'il faut empiler chaque livre dans la colonne de droite (0: ne pas empiler, 1: pile) --Fonction objective: Maximise la plus basse des hauteurs des deux colonnes --Restrictions --ʻObj est le plus petit de "suml" et "sumr" (1)
--suml est la hauteur de la colonne de gauche (2)
--sumr est la hauteur de la colonne de droite (3)
--La différence entre «suml» et «sumr» est inférieure ou égale à «limit» (4)
Les paramètres d'entrée sont créés de manière appropriée avec des nombres aléatoires.
import random
from ortoolpy import model_max, addvars, addbinvars, lpDot, value
random.seed(1)
books = [random.randint(10, 20) for _ in range(20)] #Épaisseur du livre (mm)
limit = 1 #Différence admissible entre la hauteur gauche et droite (mm)
n = len(books)
m = model_max() #Modèle mathématique
obj, suml, sumr = addvars(3) #Hauteur inférieure, hauteur gauche, hauteur droite
vl = addbinvars(n) #Mettez-vous le livre sur la gauche
vr = addbinvars(n) #Mettez-vous le livre sur la droite
m += obj #Fonction objective (la rendre aussi haute que possible)
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() #Résoudre avec le solveur
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)» est le produit interne de «X» et «Y». Donc lpDot (books, vl) est la hauteur de la colonne de gauche.
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» signifie que la solution optimale a été obtenue.
value (X) obtient la valeur de la variable X.
La hauteur de la colonne de gauche est de 149 mm, la hauteur de la colonne de droite est de 148 mm et la différence est de 1 mm.
La liste finale montre que 1 est dans la colonne de gauche et -1 est dans la colonne de droite.
Ce qui précède peut être calculé en 0,1 seconde, mais si «limit» est défini sur 0, le temps de calcul sera de 24 secondes (240 fois).
Comme vous pouvez le voir, dans l'optimisation combinée, le temps de calcul peut changer considérablement si les paramètres changent légèrement.
Si vous voulez changer la limite de différentes manières, vous devrez peut-être concevoir quelque chose comme" Comment résoudre le problème de conditionnement des bacs ".
Recommended Posts