[PYTHON] Minimieren Sie die Anzahl der Polierungen, indem Sie die Kombination optimieren

Einführung

--Hersteller A produziert und verkauft dekorative Platten. ――Bei der endgültigen Herstellung von Dekorplatten werden die bei der Inspektion festgestellten Kratzer poliert und gereinigt. ―― Angenommen, Sie möchten den Polieraufwand minimieren.

Poliermethode

--Das Poliergerät poliert die automatisch ermittelte Breite von Ende zu Ende, wenn Sie eine Reihe angeben. ――Da es in der Mitte um 90 Grad gedreht wird, bedeutet dies, dass es zeilenweise oder spaltenweise poliert werden kann.

  • Der Zweck besteht darin, die Anzahl der Zeilen oder Spalten zu minimieren, die alle Kratzer abdecken.

image

Formulierung

Dieses Problem wird zu einem kollektiven Beschichtungsproblem.

Minimieren Sie $ \ sum_i {x_i} + \ sum_j {y_j} $ Anzahl der Polierungen
Variablen $ x_i \ in \ {0, 1 \} ~ ~ \ forall i \ in Zeilen $ Polnische Zeilen Ob
$ y_j \ in \ {0, 1 \} ~ ~ \ forall j \ in Spalte $ Gibt an, ob die Spalte poliert werden soll
Einschränkungen $ x_i + y_j \ ge 1 ~ ~ \ forall i, j \ in \ mbox {verkratzter Bereich} $ Alle Kratzer Polnisch

Auf Python ausführen

Erstellen Sie einen 4-mal-6-Dummy. Der weiße Teil ist der Kratzer.

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

Erstellen Sie ein mathematisches Modell und führen Sie es aus.

python3


m = LpProblem()
x = [LpVariable('x%d'%i, cat=LpBinary) for i in range(a.shape[0])] #Ob die Reihe poliert werden soll
y = [LpVariable('y%d'%i, cat=LpBinary) for i in range(a.shape[1])] #Ob die Reihe poliert werden soll
m += lpSum(x + y) #Zielfunktion(Häufigkeit des Polierens)
for i in range(a.shape[0]):
    for j in range(a.shape[1]):
        if a[i, j]:
            m += x[i] + y[j] >= 1 #Polieren Sie Zeilen oder Spalten, wenn sie zerkratzt sind
m.solve()
for i in range(a.shape[0]):
    if value(x[i]):
        print('Linie%Polnisch d'%i)
for j in range(a.shape[1]):
    if value(y[j]):
        print('Säule%Polnisch d'%j)
>>>
Polnische Linie 3
Polnische Reihe 2

Sie können sehen, dass es mit 2 Mal gemacht wird, was die minimale Anzahl von Polierungen ist.

das ist alles

Recommended Posts