[PYTHON] 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.

image

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

image

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