[DOCKER] Décidons le cours de date par optimisation de combinaison

Décidons un cours de date

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

Variables $ x_ {fr, to} \ in \ {0, 1 \} ~ ~ \ forall fr, to \ in Facility $ S'il faut passer de l'établissement $ fr $ à l'établissement $ à $ (1)
$ y_i ~ ~ \ forall i \ in Facility $ Heure de fin d'utilisation de l'installation $ i $ (2)
Fonction objectif $ \ sum_ {fr, to \ in Facility} ~~~ {Satisfaction_ {fr} ~ x_ {fr, to}} $ → Maximiser td> Satisfaction totale (3)
Contraintes $ \ sum_ {fr, to \ in Facility | fr = i} ~~~ {x_ {fr, to}} = 1 ~~ ~ i = S $ L'entrée doit passer (4)
$ \ sum_ {fr, vers \ dans l'installation | fr = i} ~~~ {x_ {fr, vers}} \ le 1 ~~~ \ forall i \ dans l'installation \ setminus S $ Jusqu'à 1 utilisation (4)
$\sum_{fr,to \dans l'établissement| fr=i}~~~{x_{fr,to}} = \sum_{fr,to \dans l'établissement| to=i}~~~{x_{fr,to}} ~~~ \forall i \dans l'établissement$Même entrée et sortie de l'installation(5)
$ y_ {to} \ ge TM_ {fr, to} + TU_ {to} ~~~ \ forall fr, to \ in Facility, fr = S $ Fin d'utilisation de l'installation Réglage de l'heure (6)
$ y_ {to} \ ge TM_ {fr, to} + TU_ {to} + y_ {fr} ~~~ \ forall fr, to \ in Facility, fr \ ne S $ Réglage de l'heure de fin d'utilisation de l'installation (6)
$ y_i ~~~ \ le 200 ~~~ i = S $ Durée maximale de séjour (7)

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
Établissement Niveau de satisfaction Temps d'utilisation
0 S 0
1 A 65
2 B 95
3 C 58
4 D 72
5 E 93

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
fr to x Temps de voyage
1 S A xSA
11 A E xAE
12 B S xBS
20 C B xCB
33 E C xEC

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

image

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

Recommended Posts

Décidons le cours de date par optimisation de combinaison
Décidons la conférence de PyCon JP 2016 par optimisation de combinaison
Décidons la position du service d'incendie par optimisation combinée
Optimisation du regroupement par combinaison
Minimisez le nombre de polissages en optimisant la combinaison
Juger la finition du mahjong par l'optimisation des combinaisons
Résolution de "cubes en cubes" avec optimisation des combinaisons
Paver la route avec l'optimisation des combinaisons
Déterminer le programme enregistré par optimisation de combinaison
La puissance des solveurs d'optimisation combinée
Divisez en équipes par optimisation de combinaison
Décidons le gagnant du bingo
Penser les menus par l'optimisation des combinaisons
Résolvons le portefeuille avec une optimisation continue
Empilons les livres à plat avec l'optimisation des combinaisons
Trouver l'itinéraire des patrouilleurs en optimisant
Méthode gagnante des courses de chevaux par optimisation des combinaisons
Trouver la main de "Millijan" par l'optimisation des combinaisons
Astuce BeautifulSoup: choisissez la balise en spécifiant le chemin
Résolution du problème N Queen avec l'optimisation continue / combinée
Résolution du problème N Queen avec l'optimisation des combinaisons
Utiliser l'optimisation des combinaisons
○○ Résolution de problèmes dans le département de mathématiques avec optimisation
Diviser en équipes par optimisation de combinaison (minimiser l'écart moyen)
Diviser en équipes par optimisation de combinaison (méthode de cuisson)
Visualisons les données pluviométriques publiées par la préfecture de Shimane