--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.
--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.
Dieses Problem wird zu einem kollektiven Beschichtungsproblem.
Minimieren Sie td> | $ \ sum_i {x_i} + \ sum_j {y_j} $ td> | Anzahl der Polierungen td> tr> |
Variablen td> | $ x_i \ in \ {0, 1 \} ~ ~ \ forall i \ in Zeilen $ td> | Polnische Zeilen Ob td> tr> |
$ y_j \ in \ {0, 1 \} ~ ~ \ forall j \ in Spalte $ td> | Gibt an, ob die Spalte td> tr> poliert werden soll | |
Einschränkungen td> | $ x_i + y_j \ ge 1 ~ ~ \ forall i, j \ in \ mbox {verkratzter Bereich} $ td> | Alle Kratzer Polnisch td> tr> |
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');
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