11
14

More than 3 years have passed since last update.

組合せ最適化 - 典型問題 - 最小費用流問題

Last updated at Posted at 2015-07-10

典型問題と実行方法

最小費用流問題

有向グラフ$G=(V,E)$において、各辺の容量と重みさらに節点の需要量が与えられたとき、各辺の容量を超過せずに各辺の流量に対する重みの総和が最小となるフローを求めよ。

  • 各節点において、「流入量 - 流出量」は、需要量と等しい。
  • 需要量が負の場合、供給量を表す。
  • 全ての節点の需要量の和は0でなければいけない。

実行方法

usage
Signature: nx.min_cost_flow(G, demand='demand', capacity='capacity', weight='weight')
Docstring:
Return a minimum cost flow satisfying all demands in digraph G.

G is a digraph with edge costs and capacities and in which nodes
have demand, i.e., they want to send or receive some amount of
flow. A negative demand means that the node wants to send flow, a
positive demand means that the node want to receive flow. A flow on
the digraph G satisfies all demand if the net flow into each node
is equal to the demand of that node.
python
# CSVデータ
import pandas as pd, networkx as nx
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, directed=True)[0]
result = nx.min_cost_flow(g)
for i, d in result.items():
    for j, f in d.items():
        if f: print((i, j), f)
結果
(0, 1) 1
(0, 3) 1
(0, 4) 2
(4, 5) 1
python
# pandas.DataFrame
from ortoolpy.optimization import MinCostFlow
MinCostFlow('data/node0.csv','data/edge0.csv')
node1 node2 capacity weight flow
0 0 1 2 1 1
1 0 3 2 2 1
2 0 4 2 2 2
3 4 5 2 1 1
python
# 乱数データ
import networkx as nx
g = nx.fast_gnp_random_graph(8, 0.2, 1, True)
g.nodes[1]['demand'] = -2 # 供給
g.nodes[7]['demand'] = 2 # 需要
g.adj[2][7]['capacity'] = 1 # 容量
result = nx.min_cost_flow(g)
for i, d in result.items():
    for j, f in d.items():
        if f: print((i, j), f)
結果
(1, 2) 2
(2, 3) 1
(2, 7) 1
(3, 7) 1

データ

11
14
1

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
11
14