[PYTHON] Über das Problem der reisenden Verkäufer
Vor kurzem hatte ich aufgrund meiner Arbeit die Möglichkeit, mit "mathematischer Optimierung" in Kontakt zu treten. Es ist eine gute Idee, deshalb möchte ich die Ergebnisse einer kleinen privaten Berührung veröffentlichen.
Was ich getan habe, war ein Beispiel für mathematische Optimierung, das "Circular Salesman Problem". Da dies mit dem Pulp der freien Umgebung implementiert werden kann, habe ich versucht, es während der Vorbereitung der Umgebung zu implementieren.
Die Probleme, die ich versuchen möchte, sind wie folgt.
◆ 2.12 Problem mit dem Patrol-Verkäufer https://www.msi.co.jp/nuopt/docs/v19/examples/html/02-12-00.html
Ich habe unten ein einfaches Bild gezeichnet. A, B, C, D sind die Punkte auf der Karte.
Welche Route hat die geringste Gesamtentfernung, wenn Sie A verlassen und mit einem einzigen Schlag zurückkehren? Es scheint, dass das Optimierungsproblem als "Patrouillenverkäuferproblem" bezeichnet wird. Es heißt NP-Schwierigkeit, und es scheint ziemlich schwierig zu sein.
Der Ansatz mit dem Modellierer namens Pulp, der in der Python-Umgebung berührt wird, ist jedoch kostenlos !!! Es ist einfach, daher werde ich auf den folgenden Artikel verweisen.
◆ Mathematische Optimierung ausgehend vom Problem des Handlungsreisenden https://qiita.com/panchovie/items/6509fb54e3d53f4766aa
Das Tolle ist, dass wir alles haben, von der Installation von Zellstoff bis zum Beispielcode. Lassen Sie uns die erste Einstellung sofort in den Beispielcode einfügen. Was ist mit dem folgenden Code, der vorerst kompiliert zu werden scheint?
import pulp as pp
#Definition des Optimierungsmodells
mip_model = pp.LpProblem("tsp_mip", pp.LpMinimize)
N = 4
BigM = 10000
c_ = [
[0,6,5,5], # pointA > [pointA,pointB,pointC,pointD]
[6,0,7,4], # pointB > [pointA,pointB,pointC,pointD]
[5,7,0,3], # pointC > [pointA,pointB,pointC,pointD]
[5,4,3,0], # pointD > [pointA,pointB,pointC,pointD]
]
#Variablendefinition
x = [[pp.LpVariable("x(%s,%s)"%(i, j), cat="Binary") for i in range(N)] for j in range(N)]
u = [pp.LpVariable("u(%s)"%(i), cat="Continuous", lowBound=1.0, upBound=(N)) for i in range(N)]
#Definition und Registrierung des Bewertungsindex (Gleichung (1))
objective = pp.lpSum(c_[i][j] * x[i][j] for i in range(N) for j in range(N) if i != j)
mip_model += objective
#Bedingter Ausdruck(2)Registrierung von
for i in range(N):
mip_model += pp.lpSum(x[i][j] for j in range(N) if i != j) == 1
#Bedingter Ausdruck(3)Registrierung von
for i in range(N):
mip_model += pp.lpSum(x[j][i] for j in range(N) if i != j) == 1
for i in range(N):
mip_model += x[i][i] == 0
#Bedingter Ausdruck(4) (MTZ-Einschränkung)
for i in range(N):
for j in range(N):
if i != j:
mip_model += u[i] + 1.0 - BigM * (1.0 - x[i][j]) <= u[j]
#Führen Sie eine Optimierung durch
status = mip_model.solve()
#Die Ergebnisse verstehen
print("Status: {}".format(pp.LpStatus[status]))
print("Optimal Value [a.u.]: {}".format(objective.value()))
for i in range(N):
for j in range(N):
if i != j:
print("x[%d][%d]:%f" % (i,j,x[i][j].value()))
for i in range(len(u)):
print("u[%d] %f" % (i,u[i].value()))
Wenn Sie es in diesem Zustand ausführen ...
Status: Infeasible
Optimal Value [a.u.]: 18.0
x[0][1]:0.000000
x[0][2]:1.000000
x[0][3]:0.000000
x[1][0]:0.999800
x[1][2]:0.000000
x[1][3]:0.000200
x[2][0]:0.000200
x[2][1]:0.000000
x[2][3]:0.999800
x[3][0]:0.000000
x[3][1]:1.000000
x[3][2]:0.000000
Es scheint, dass es nicht gut berechnet wurde. Es scheint, dass die Einschränkungsbedingungen nicht gut erfüllt sind, so dass es nach verschiedenen Untersuchungen so aussieht, als ob die MTZ-Einschränkungsformel so seltsam ist, wie sie ist. Wenn Sie alle vier Formeln für x bis u im Endzustand schreiben, ist dies wie folgt.
u[0] < u[2]\\
u[1] < u[0]\\
u[2] < u[3]\\
u[3] < u[1]
Wenn es darum geht, all dies zu befriedigen,
u[0] < u[2] < u[3] < u[1] < u[0] < ...
Es wird unendlich zunehmen, aber da der effektive Bereich von u zwischen 1 und 4 liegt, scheint es einen Widerspruch zu geben. Lassen Sie uns daher die Formel wie folgt rekonstruieren, indem Sie die Einschränkung für die Variable entfernen, die am Ende zu Punkt A zurückkehrt.
u[0] < u[2]\\
u[2] < u[3]\\
u[3] < u[1]
Dies ändert die Implementierung und die MTZ-Bedingungsformel in:
#Bedingter Ausdruck(4) (MTZ-Einschränkung)
for i in range(N):
for j in range(1,N):
if i != j:
mip_model += u[i] + 1.0 - BigM * (1.0 - x[i][j]) <= u[j]
Der Quellcode ist unten zusammengefasst.
sample_route.py
import pulp as pp
#Definition des Optimierungsmodells
mip_model = pp.LpProblem("tsp_mip", pp.LpMinimize)
N = 4
BigM = 10000
c_ = [
[0,6,5,5], # pointA > [pointA,pointB,pointC,pointD]
[6,0,7,4], # pointB > [pointA,pointB,pointC,pointD]
[5,7,0,3], # pointC > [pointA,pointB,pointC,pointD]
[5,4,3,0], # pointD > [pointA,pointB,pointC,pointD]
]
#Variablendefinition
x = [[pp.LpVariable("x(%s,%s)"%(i, j), cat="Binary") for i in range(N)] for j in range(N)]
u = [pp.LpVariable("u(%s)"%(i), cat="Continuous", lowBound=1.0, upBound=(N)) for i in range(N)]
#Definition und Registrierung des Bewertungsindex (Gleichung (1))
objective = pp.lpSum(c_[i][j] * x[i][j] for i in range(N) for j in range(N) if i != j)
mip_model += objective
#Bedingter Ausdruck(2)Registrierung von
for i in range(N):
mip_model += pp.lpSum(x[i][j] for j in range(N) if i != j) == 1
#Bedingter Ausdruck(3)Registrierung von
for i in range(N):
mip_model += pp.lpSum(x[j][i] for j in range(N) if i != j) == 1
for i in range(N):
mip_model += x[i][i] == 0
#Bedingter Ausdruck(4) (MTZ-Einschränkung)
for i in range(N):
for j in range(1,N):
if i != j:
mip_model += u[i] + 1.0 - BigM * (1.0 - x[i][j]) <= u[j]
#Führen Sie eine Optimierung durch
status = mip_model.solve()
#Die Ergebnisse verstehen
print("Status: {}".format(pp.LpStatus[status]))
print("Optimal Value [a.u.]: {}".format(objective.value()))
for i in range(N):
for j in range(N):
if i != j:
print("x[%d][%d]:%f" % (i,j,x[i][j].value()))
for i in range(len(u)):
print("u[%d] %f" % (i,u[i].value()))
Das Ergebnis ist wie folgt.
Status: Optimal
Optimal Value [a.u.]: 18.0
x[0][1]:0.000000
x[0][2]:1.000000
x[0][3]:0.000000
x[1][0]:1.000000
x[1][2]:0.000000
x[1][3]:0.000000
x[2][0]:0.000000
x[2][1]:0.000000
x[2][3]:1.000000
x[3][0]:0.000000
x[3][1]:1.000000
x[3][2]:0.000000
u[0] 1.000000
u[1] 4.000000
u[2] 2.000000
u[3] 3.000000
Es konvergierte sicher. Die Ergebnisse sind nicht grafisch,
Punkt A → Punkt C → Punkt D → Punkt B → Punkt A.
Scheint die kürzeste zu sein und die Entfernung beträgt 18. Wo das Problem aufgeführt war
Punkt A → Punkt B → Punkt D → Punkt C → Punkt A.
Immerhin ist die Entfernung 18 und es scheint die kürzeste zu sein, also gibt es einige Antworten.
Die mathematische Optimierung ist nur in Bereichen sehr aktuell, die wir zuvor noch nicht angesprochen haben. Es gibt eine Umgebung, in der Sie es gerne ausprobieren können, also werde ich diese Gelegenheit nutzen, um verschiedene Dinge zu studieren.
Recommended Posts