Empilons les livres à plat avec l'optimisation des combinaisons

Contexte

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.

problème

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.

Façon de penser

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.

Formulation

--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)

Résolvons-le avec Python

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.

production

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.

De côté

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

Empilons les livres à plat avec l'optimisation des combinaisons
Jeux de regroupement avec optimisation des combinaisons
Optimisation combinée avec recuit quantique
Résolvez le problème des 4 couleurs grâce à l'optimisation des combinaisons
Allez voir les baleines avec l'optimisation des combinaisons
Paver la route avec l'optimisation des combinaisons
Résolution de la théorie des jeux avec l'optimisation des combinaisons
Résolvons le portefeuille avec une optimisation continue
Résolution des problèmes de planification des infirmières grâce à l'optimisation des combinaisons
Créer un programme académique avec optimisation des combinaisons
Décidons le cours de date par optimisation de combinaison
Résolution des problèmes d'organisation des districts scolaires grâce à l'optimisation des combinaisons
Résolution du problème N Queen avec l'optimisation continue / combinée
Résolution du problème N Queen avec l'optimisation des combinaisons
Utiliser l'optimisation des combinaisons
Optimisation apprise avec OR-Tools [plan linéaire: raffinons l'huile]
Aménagement routier par optimisation
Optimisation du regroupement par combinaison
Introduction à l'optimisation
Décidons la conférence de PyCon JP 2016 par optimisation de combinaison
Décidons la position du service d'incendie par optimisation combinée