Résolution des problèmes d'organisation des districts scolaires grâce à l'optimisation des combinaisons

Qu'est-ce que c'est

Séminaire Gurobi Optimizer Solution Seminar 2016 de Optimization tenu le 12/2 event / 20161021.html), j'ai entendu dire que le district scolaire peut être résolu comme une grande variété problème de flux de coût minimum, alors je l'ai fait. Je l'ai essayé.

Façon de penser

――34 Créer des points de demande pour les préfectures. ―― La demande pour Aomori, Yamanashi et Yamaguchi est de 6, 20, 5 (à l'exclusion de vous-même) et -1 pour les autres. ―― Pensez à trois Japonais (Japon vert, Japon bleu et Japon rouge) représentés par Aomori, Yamanashi et Yamaguchi, et rendez-les adjacents les uns aux autres. (Réseau multi-produits) ―― Lien vers la même préfecture au Japon à partir des points de demande autres que les points représentatifs. ―― Lien vers le point de demande du point représentatif de la même préfecture de chaque Japon représenté par le point représentatif.

image

Résolvez le problème de flux de coût minimum sur ce réseau.

Essayez-le avec Python

python3


import numpy as np, networkx as nx
from japanmap import adjacent, pref_code, pref_map
Honshu= np.arange(2,36)
Point représentatif= {pref_code('Aomori'):7, pref_code('Yamanashi'):21, pref_code('Yamaguchi'):6}
#Création de graphes
g = nx.DiGraph()
g.add_nodes_from(Honshu, demand=-1)
for i,d en point représentatif.items():
    nwl = i*100
    g.node[i]['demand'] = d-1
    g.add_nodes_from(nwl+Honshu, demand=0)
    g.add_edge(nwl+i,i)
    g.add_edges_from((j,nwl+j)pour j dans Honshu si j pas en points représentatifs)
    g.add_edges_from(((nwl+j,nwl+k)pour j dans Honshu pour k dans adjacent(j)), weight=1)
r = nx.min_cost_flow(g)
#Affichage des résultats
dc = dict(zip(Point représentatif,['red','green','blue']))
dc.update({i:dc[j//100]for i, t in r.items() for j, v in t.items() if v and i < 100})
pref_map(Honshu, cols=[dc[i] for i in Honshu], width=4)

image

Je l'ai résolu comme je m'y attendais.

développement

En réalité, de nombreux facteurs doivent être pris en compte.

――Il est souhaitable d'avoir le même district scolaire qu'auparavant. «Je veux vraiment le diviser dans un endroit précis. --Faites la distance, pas le nombre de sauts.

Il semble que cela puisse être fait en fixant la formulation.

c'est tout

Recommended Posts

Résolution des problèmes d'organisation des districts scolaires grâce à l'optimisation des combinaisons
Résolvez le problème des 4 couleurs grâce à l'optimisation des combinaisons
Résolution des problèmes de planification des infirmières grâce à l'optimisation des combinaisons
Résolution de la théorie des jeux avec l'optimisation des combinaisons
Résolution des problèmes de sac à dos avec les outils OR de Google - Pratiquer les bases des problèmes d'optimisation combinée
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
Introduction à l'optimisation mathématique Python Résoudre des problèmes de mathématiques au collège avec pulp
Jeux de regroupement avec optimisation des combinaisons
Optimisation combinée avec recuit quantique
Résolution d'exercices de modèle d'optimisation mathématique avec les outils OR de Google (3) Problèmes d'optimisation de la production
Maximisez les ventes des restaurants grâce à l'optimisation combinée
Allez voir les baleines avec l'optimisation des combinaisons
Paver la route avec l'optimisation des combinaisons
Résolvez les problèmes d'optimisation des combinaisons avec les outils OR de Google (5) Décidez d'un cours de date
Empilons les livres à plat avec l'optimisation des combinaisons
Points à noter lors de la résolution de problèmes DP avec Python
Utiliser l'optimisation des combinaisons
○○ Résolution de problèmes dans le département de mathématiques avec optimisation
Résolution des problèmes de sac à dos avec des algorithmes génétiques et des modèles MGG