조합 최적화로 학군 편성 문제 해결
이게 뭐야
12/2 에 행해진 최적화 의 세미나 Gurobi Optimizer 솔루션 세미나 2016 그리고, 학교의 학구 결정을 다품종 최소 비용 흐름 문제 로서 풀 수 있는 것을 들었으므로 실제로 해 보았습니다.
현별 데이터의 시각화 라이브러리 japanmap을 사용합니다.
사고방식
이 네트워크에서 최소 비용 흐름 문제를 해결합니다.
파이썬으로 시도
python3import numpy as np, networkx as nx
from japanmap import adjacent, pref_code, pref_map
本州 = np.arange(2,36)
代表点 = {pref_code('青森'):7, pref_code('山梨'):21, pref_code('山口'):6}
# グラフ作成
g = nx.DiGraph()
g.add_nodes_from(本州, demand=-1)
for i, d in 代表点.items():
nwl = i*100
g.node[i]['demand'] = d-1
g.add_nodes_from(nwl+本州, demand=0)
g.add_edge(nwl+i,i)
g.add_edges_from((j,nwl+j) for j in 本州 if j not in 代表点)
g.add_edges_from(((nwl+j,nwl+k) for j in 本州 for k in adjacent(j)), weight=1)
r = nx.min_cost_flow(g)
# 結果表示
dc = dict(zip(代表点,['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(本州, cols=[dc[i] for i in 本州], width=4)
생각대로 풀었습니다.
발전
현실에는 여러 가지 요소를 고려해야합니다.
import numpy as np, networkx as nx
from japanmap import adjacent, pref_code, pref_map
本州 = np.arange(2,36)
代表点 = {pref_code('青森'):7, pref_code('山梨'):21, pref_code('山口'):6}
# グラフ作成
g = nx.DiGraph()
g.add_nodes_from(本州, demand=-1)
for i, d in 代表点.items():
nwl = i*100
g.node[i]['demand'] = d-1
g.add_nodes_from(nwl+本州, demand=0)
g.add_edge(nwl+i,i)
g.add_edges_from((j,nwl+j) for j in 本州 if j not in 代表点)
g.add_edges_from(((nwl+j,nwl+k) for j in 本州 for k in adjacent(j)), weight=1)
r = nx.min_cost_flow(g)
# 結果表示
dc = dict(zip(代表点,['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(本州, cols=[dc[i] for i in 本州], width=4)
현실에는 여러 가지 요소를 고려해야합니다.
정식화를 고치면 할 수 있을 것 같습니다.
이상
Reference
이 문제에 관하여(조합 최적화로 학군 편성 문제 해결), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://qiita.com/SaitoTsutomu/items/3c91e08215522cd38b6f텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
좋은 웹페이지 즐겨찾기
