Mir wurde gesagt, ich solle "die Wäsche trocknen" und ich dachte beim Trocknen darüber nach.
Trocknen Sie die Wäsche mit dem Gewicht w = [7, 8, 9, 11, 13, 15, 17] nacheinander bei den Koordinaten p = [-3, -2, -1, 0, 1, 2, 3]. Finden Sie die Trocknungsmethode, die den absoluten Wert des Schwerpunkts minimiert, wenn
Informationen zur Formulierungsmethode finden Sie unter Kombinationsoptimierung verwenden.
| Variablen | $ x_ {ijk} \ in \ {0, 1 \} $ | $ i $ th Position $ j $ für Wäsche $ k Gibt an, ob $ getrocknet werden soll |
| $ y $ | Absolutwert des Schwerpunkts | |
| Zielfunktion | $ y $ | $ \ rightarrow $ Minimum |
| Einschränkungen | $ \ sum ^ n_ {i = 0} {\ sum_j {\ sum_k {p [j] ~ w [k] ~ x_ {ijk}}} \ le y $ | $\forall n \in \{0, 1, \dots \}$ |
| Jedes Mal platzieren In alle Positionen bringen Alle Wäsche platzieren |
python
from pulp import * # pip install pulp
def addvar(lowBound=0, var_count=[0], *args, **kwargs):
var_count[0] += 1
return LpVariable('v%d' % var_count[0], lowBound=lowBound, *args, **kwargs)
p = [-3, -2, -1, 0, 1, 2, 3]
w = [5, 6, 7, 9, 10, 11, 12]
r = range(len(p))
m = LpProblem()
x = [[[addvar(cat=LpBinary) for _ in r] for _ in r] for _ in r]
y = addvar()
m += y
for n in r:
m += lpSum(x[n][j][k] for j in r for k in r) == 1
m += lpSum(x[i][n][k] for i in r for k in r) == 1
m += lpSum(x[i][j][n] for i in r for j in r) == 1
if n:
m += lpSum(p[j] * w[k] * x[i][j][k]
for i in range(n+1) for j in r for k in r) <= y
m += lpSum(-p[j] * w[k] * x[i][j][k]
for i in range(n+1) for j in r for k in r) <= y
m += lpSum(x[0][len(p) // 2][k] for k in r) == 1
m += lpSum(x[1][j][k] for j in range(len(p) // 2) for k in r) == 1
%time m.solve()
print(LpStatus[m.status], value(m.objective))
>>>
Wall time: 2 s
Optimal 10.0
Da es jederzeit an der Positionskoordinate 0 platziert werden kann, wird es zuerst platziert. Der nächste kann auch links oder rechts sein, so dass er links fixiert ist.
Ergebnisanzeige
for i in r:
for j in r:
for k in r:
if value(x[i][j][k]) > 0.5:
print(i, j, k)
>>>
0 3 6
1 2 4
2 5 3
3 1 2
4 6 0
5 0 1
6 4 5
Da es mehrere optimale Lösungen zu geben scheint, ist eine ungefähre Lösung wie eine lokale Suchmethode wahrscheinlich effektiver.
Die Verwendung von Pandas in der Formulierung macht es einfacher, Folgendes zu sehen.
py3
import pandas as pd
from pulp import * # pip install pulp
def addvar(lowBound=0, var_count=[0], *args, **kwargs):
var_count[0] += 1
return LpVariable('v%d' % var_count[0], lowBound=lowBound, *args, **kwargs)
def Σ(s, f=None):
if not f:
return lpSum(t.query(s.format(**globals())).x)
return lpSum(t.query(s.format(**globals())).apply(f, axis=1))
p = [-3, -2, -1, 0, 1, 2, 3] #Koordinate
w = [5, 6, 7, 9, 10, 11, 12] #Gewicht
r = range(len(p)) #Reichweite
m = LpProblem() #Mathematisches Modell
t = pd.DataFrame([(i, j, k, addvar(cat=LpBinary))
for i in r for j in r for k in r], columns=['Auftrag', 'Position', 'Gewicht', 'x'])
y = addvar() #Absolutwert des Schwerpunkts
m += y #Zielfunktion
for n in r:
m += Σ('Auftrag=={n}') == 1 # Auftrag n で置くこと
m += Σ('Position=={n}') == 1 # Position n に置くこと
m += Σ('Gewicht=={n}') == 1 #Wäsche legen
if n:
#Der absolute Wert des Schwerpunkts ist y oder weniger
m += Σ('Auftrag<={n}', lambda q: p[q.Position] * w[q.Gewicht] * q.x) <= y
m += Σ('Auftrag<={n}', lambda q: -p[q.Position] * w[q.Gewicht] * q.x) <= y
m += Σ('Auftrag==0 &Position==3') == 1 # Auftrag 0 にPosition 3 に置くこと
m += Σ('Auftrag==1 &Position<=2') == 1 # Auftrag 1 にPositionが 2 以下に置くこと
m.solve()
print(LpStatus[m.status], value(m.objective))