翱搁学会 2015/9/11 組合せ最適化の体系化とフリーソフトによる最適化
- 13. 翱搁学会2015年秋季研究発表会
import pandas as pd, networkx as nx, matplotlib.pyplot as plt
from ortoolpy import graph_from_table, networkx_draw
tbn = pd.read_csv('data/node0.csv')
tbe = pd.read_csv('data/edge0.csv')
g = graph_from_table(tbn, tbe)
t = nx.minimum_spanning_tree(g)
pos = networkx_draw(g)
nx.draw_networkx_edges(t, pos, width=3)
plt.show()
print(t.edges())
[(0, 1),
(0, 3),
(0, 4),
(2, 3),
(4, 5)]
- 14. 翱搁学会2015年秋季研究発表会
usage
Signature: knapsack(size, weight, capacity)
Docstring:
ナップサック問題
価値の最大化
入力
size: 荷物の大きさのリスト
weight: 荷物の価値のリスト
capacity: 容量
出力
価値の総和と選択した荷物番号リスト
from ortoolpy import knapsack
size = [21, 11, 15, 9, 34, 25, 41, 52]
weight = [22, 12, 16, 10, 35, 26, 42, 53]
capacity = 100
print(knapsack(size, weight, capacity))
結果
(105.0, [0, 1, 3, 4, 5])
- 15. 翱搁学会2015年秋季研究発表会
from ortoolpy import addvar
size = [21, 11, 15, 9, 34, 25, 41, 52]
weight = [22, 12, 16, 10, 35, 26, 42, 53]
capacity = 100
m = LpProblem(sense=LpMaximize)
v = [addvar(cat=LpBinary) for _ in size]
m += lpDot(weight, v)
m += lpDot(size, v) <= capacity
m.solve()
print([i for i in range(len(size)) if value(v[i]) > 0.5])
結果
[0, 1, 3, 4, 5]
モデル
変数
目的関数
制約
![翱搁学会2015年秋季研究発表会
import pandas as pd, networkx as nx, matplotlib.pyplot as plt
from ortoolpy import graph_from_table, networkx_draw
tbn = pd.read_csv('data/node0.csv')
tbe = pd.read_csv('data/edge0.csv')
g = graph_from_table(tbn, tbe)
t = nx.minimum_spanning_tree(g)
pos = networkx_draw(g)
nx.draw_networkx_edges(t, pos, width=3)
plt.show()
print(t.edges())
[(0, 1),
(0, 3),
(0, 4),
(2, 3),
(4, 5)]](https://image.slidesharecdn.com/or2015-150826064645-lva1-app6892/85/OR-2015-9-11-13-320.jpg)
![翱搁学会2015年秋季研究発表会
usage
Signature: knapsack(size, weight, capacity)
Docstring:
ナップサック問題
価値の最大化
入力
size: 荷物の大きさのリスト
weight: 荷物の価値のリスト
capacity: 容量
出力
価値の総和と選択した荷物番号リスト
from ortoolpy import knapsack
size = [21, 11, 15, 9, 34, 25, 41, 52]
weight = [22, 12, 16, 10, 35, 26, 42, 53]
capacity = 100
print(knapsack(size, weight, capacity))
結果
(105.0, [0, 1, 3, 4, 5])](https://image.slidesharecdn.com/or2015-150826064645-lva1-app6892/85/OR-2015-9-11-14-320.jpg)
![翱搁学会2015年秋季研究発表会
from ortoolpy import addvar
size = [21, 11, 15, 9, 34, 25, 41, 52]
weight = [22, 12, 16, 10, 35, 26, 42, 53]
capacity = 100
m = LpProblem(sense=LpMaximize)
v = [addvar(cat=LpBinary) for _ in size]
m += lpDot(weight, v)
m += lpDot(size, v) <= capacity
m.solve()
print([i for i in range(len(size)) if value(v[i]) > 0.5])
結果
[0, 1, 3, 4, 5]
モデル
変数
目的関数
制約](https://image.slidesharecdn.com/or2015-150826064645-lva1-app6892/85/OR-2015-9-11-15-320.jpg)
