Ich beschloss, mit ihr in den Vergnügungspark zu gehen. Wie gehen Sie durch die Einrichtungen des Vergnügungsparks, um ihre Zufriedenheit zu maximieren? Aufgrund ihrer Ausgangssperre hat der Vergnügungspark jedoch nur 200 Minuten.

Sie können ein solches Problem mit [Kombinationsoptimierung] lösen (http://qiita.com/Tsutomu-KKE@github/items/bfbf4c185ed7004b5721). Es ist ähnlich wie das Rucksackproblem und das Problem der reisenden Verkäufer, aber lassen Sie es uns jetzt formulieren.

Formulierung

$ TM_ {fr, to} $ ist jedoch die Reisezeit von der Einrichtung $ fr $ bis $ to $, und $ TU_ {to} $ ist die Nutzungszeit in der Einrichtung $ to $. Außerdem ist die Randbedingung (6) nur gültig, wenn $ x_ {fr, to} $ 1 ist. Die erste Einrichtung S ist der Eingang zum Vergnügungspark und kehrt am Ende zum Eingang zurück. Dieselbe Einrichtung kann auch nur einmal verwendet werden.

Löse mit Python

Versuchen Sie es mit Python 3.5 von Jupyter. Wenn Sie Docker verwenden können, können Sie es mit tsutomu7 / jupyter oder tsutomu7 / alpine-python: jupyter ausführen.

Vorbereitung

Importieren Sie die zu verwendende Bibliothek und legen Sie die Zeichnung fest.

python3

%matplotlib inline
import numpy as np, pandas as pd, matplotlib.pyplot as plt
from collections import OrderedDict
from pulp import *
from pulp.constants import LpConstraintEQ as EQ, LpConstraintLE as LE
plt.rcParams['font.family'] = 'IPAexGothic'
plt.rcParams['font.size'] = 16

Einstellungen für Einrichtung und Reisezeit

python3

n = 6
np.random.seed(2)
a = pd.DataFrame(OrderedDict([
        ('Einrichtung', ['S'] + [chr(65+i) for i in range(n-1)]),
        ('Zufriedenheitsgrad', np.random.randint(50, 100, n)),
        ('Nutzungszeit', np.random.randint(3, 6, n) * 10),
        ]))
a.loc[0, a.columns[1:]] = 0
Reisezeit= np.random.randint(1, 7, (n, n))
Reisezeit+=Reisezeit.T #Machen Sie eine symmetrische Matrix
a

Mit OrderedDict können Sie die Reihenfolge der Spalten festlegen.

Formulieren und lösen

python3

def solve_route(a, limit):
    n = a.shape[0]
    m = LpProblem(sense=LpMaximize)
    b = pd.DataFrame([(i, j, LpVariable('x%s%s'%(i,j), cat=LpBinary))
        for i in a.Einrichtung für j in a.Einrichtung], columns=['fr','to','x']) # (1)
    b['Reisezeit'] = Reisezeit.flatten()
    b = b.query('fr!=to')
    y = {i:LpVariable('y%s'%i) for i in a.Einrichtung} # そのEinrichtungの利用終了時刻(2)
    m += lpDot(*pd.merge(b, a, left_on='fr', right_on='Einrichtung')
        [['x', 'Zufriedenheitsgrad']].values.T) #Zielfunktion(3)
    for i in a.Einrichtung:
        m += LpConstraint(lpSum(b[b.fr==i].x), EQ if i=='S' else LE, rhs=1) # (4)
        m += lpSum(b[b.fr==i].x) == lpSum(b[b.to==i].x) # (5)
    M = b.Reisezeit.sum() + a.Nutzungszeit.sum() #Groß genug Wert
    for _, r in b.iterrows():
        m += y[r.to] >= r.Reisezeit+ a[a.Einrichtung==r.to].Nutzungszeit.sum() \
                        + (0 if r.fr=='S' else y[r.fr]) - (1-r.x)*M # (6)
    m += y['S'] <= limit # (7)
    m.solve()
    return value(m.objective), b[b.x.apply(value)>0]
objv, rs = solve_route(a, 200)
print('Totale Zufriedenheit= %g'%objv)
rs
>>>
Totale Zufriedenheit= 311

Wenn Sie vom Eingang (S) aus A-> E-> C-> B drehen, können Sie sehen, dass die Gesamtzufriedenheit auf 311 maximiert werden kann.

Lassen Sie uns den Übergang von Aufenthaltszeit und Zufriedenheit sehen

python3

%%time
rng = np.linspace(250, 130, 13)
rsl = [solve_route(a, i)[0] for i in rng]

plt.title('Veränderungen in der Zufriedenheit')
plt.xlabel('Maximale Aufenthaltsdauer')
plt.plot(rng, rsl);
>>>
CPU times: user 1.11 s, sys: 128 ms, total: 1.24 s
Wall time: 6.47 s

Je länger Sie zusammen verbringen, desto zufriedener sind Sie.

Dieses Problem wird zu einem schwierigen Problem, das als Optimierungsproblem für gemischte Ganzzahlen bezeichnet wird. Wenn die Anzahl der Einrichtungen zunimmt, wird es plötzlich unmöglich, sie zu lösen. In diesem Fall ist es notwendig, beispielsweise eine ungefähre Lösungsmethode zu entwickeln.

das ist alles