Minimisez le nombre de polissages en optimisant la combinaison
Introduction
- Le fabricant A fabrique et vend des panneaux décoratifs. ―― Dans le processus final de fabrication des panneaux décoratifs, les rayures trouvées lors de l'inspection sont polies et nettoyées. ――Supposons que vous vouliez minimiser l'effort de polissage.
Méthode de polissage
- Le dispositif de polissage polit la largeur automatiquement déterminée de bout en bout lorsque vous spécifiez une ligne. ―― Puisqu'il est tourné de 90 degrés au milieu, cela signifie qu'il peut être poli ligne par ligne ou colonne par colonne.
- Le but est de minimiser le nombre de lignes ou de colonnes qui couvrent toutes les rayures.
Formulation
Ce problème devient un problème de revêtement collectif.
| Minimiser | $ \ sum_i {x_i} + \ sum_j {y_j} $ | Nombre de polissages |
| Variables | $ x_i \ in \ {0, 1 \} ~ ~ \ forall i \ in Rows $ | Polonais lignes Si |
| $ y_j \ in \ {0, 1 \} ~ ~ \ forall j \ in Column $ | S'il faut polir la colonne | |
| Contraintes | $ x_i + y_j \ ge 1 ~ ~ \ forall i, j \ in \ mbox {zone rayée} $ | Toutes les rayures Polonais |
Exécuter sur Python
Créez un mannequin 4 sur 6. La partie blanche est la rayure.
python3
%matplotlib inline
import numpy as np, matplotlib.pyplot as plt
from pulp import *
np.random.seed(55)
a = np.random.randint(0, 8, 24).reshape(4, -1) // 7
plt.imshow(a, cmap='gray', interpolation='none');
Créez et exécutez un modèle mathématique.
python3
m = LpProblem()
x = [LpVariable('x%d'%i, cat=LpBinary) for i in range(a.shape[0])] #Que ce soit pour polir la ligne
y = [LpVariable('y%d'%i, cat=LpBinary) for i in range(a.shape[1])] #Que ce soit pour polir la ligne
m += lpSum(x + y) #Fonction objective(Nombre de polissage)
for i in range(a.shape[0]):
for j in range(a.shape[1]):
if a[i, j]:
m += x[i] + y[j] >= 1 #Polonais des lignes ou des colonnes si rayées
m.solve()
for i in range(a.shape[0]):
if value(x[i]):
print('ligne%Polonais d'%i)
for j in range(a.shape[1]):
if value(y[j]):
print('Colonne%Polonais d'%j)
>>>
Polonais ligne 3
Polonais ligne 2
Vous pouvez voir qu'il est fait avec 2 fois, qui est le nombre minimum de polissages.
c'est tout
Recommended Posts