J'ai décidé d'aller au parc d'attractions avec elle. Comment faites-vous le tour des installations du parc d'attractions pour maximiser sa satisfaction? Cependant, en raison de son couvre-feu, le parc d'attractions ne dispose que de 200 minutes.

Vous pouvez résoudre un tel problème avec Optimisation de combinaison. C'est similaire au problème du sac à dos et au problème du voyageur de commerce, mais formulons-le maintenant.

Formulation

Cependant, $ TM_ {fr, to} $ est le temps de trajet de l'installation $ fr $ à $ à $, et $ TU_ {to} $ est le temps d'utilisation de l'installation $ à $. De plus, la condition de contrainte (6) n'est valide que lorsque $ x_ {fr, to} $ vaut 1. La première installation S sera l'entrée du parc d'attractions et reviendra à l'entrée à la fin. De plus, la même installation ne peut être utilisée qu'une seule fois.

Résoudre avec Python

Essayez-le avec Python 3.5 de Jupyter. Si vous pouvez utiliser docker, vous pouvez l'exécuter avec tsutomu7 / jupyter ou tsutomu7 / alpine-python: jupyter.

Préparation

Importez la bibliothèque à utiliser et définissez le dessin.

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

Paramètres des installations et des temps de trajet

python3

n = 6
np.random.seed(2)
a = pd.DataFrame(OrderedDict([
        ('Établissement', ['S'] + [chr(65+i) for i in range(n-1)]),
        ('Niveau de satisfaction', np.random.randint(50, 100, n)),
        ('Temps d'utilisation', np.random.randint(3, 6, n) * 10),
        ]))
a.loc[0, a.columns[1:]] = 0
Temps de voyage= np.random.randint(1, 7, (n, n))
Temps de voyage+=Temps de voyage.T #Faire une matrice symétrique
a

Vous pouvez utiliser OrderedDict pour fixer l'ordre des colonnes.

Formuler et résoudre

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.Facilité pour j dans un.Établissement], columns=['fr','to','x']) # (1)
    b['Temps de voyage'] = Temps de voyage.flatten()
    b = b.query('fr!=to')
    y = {i:LpVariable('y%s'%i) for i in a.Établissement} # そのÉtablissementの利用終了時刻(2)
    m += lpDot(*pd.merge(b, a, left_on='fr', right_on='Établissement')
        [['x', 'Niveau de satisfaction']].values.T) #Fonction objective(3)
    for i in a.Établissement:
        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.Temps de voyage.sum() + a.Temps d'utilisation.sum() #Valeur assez grande
    for _, r in b.iterrows():
        m += y[r.to] >= r.Temps de voyage+ a[a.Établissement==r.to].Temps d'utilisation.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('Satisfaction totale= %g'%objv)
rs
>>>
Satisfaction totale= 311

Si vous tournez A-> E-> C-> B depuis l'entrée (S), vous pouvez voir que la satisfaction totale peut être maximisée à 311.

Voyons la transition entre le temps de séjour et la satisfaction

python3

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

plt.title('Changements de satisfaction')
plt.xlabel('Durée maximale du séjour')
plt.plot(rng, rsl);
>>>
CPU times: user 1.11 s, sys: 128 ms, total: 1.24 s
Wall time: 6.47 s

Plus vous passez du temps ensemble, plus vous êtes satisfait.

Ce problème devient un problème difficile appelé le problème d'optimisation des nombres entiers mixtes. Au fur et à mesure que le nombre d'installations augmente, il devient soudainement impossible à résoudre, donc dans ce cas, il est nécessaire de concevoir, par exemple, une méthode de résolution approximative.

c'est tout