15

More than 3 years have passed since last update.

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

Last updated at Posted at 2015-07-10

## 最小費用流問題

• 各節点において、「流入量 - 流出量」は、需要量と等しい。
• 需要量が負の場合、供給量を表す。
• 全ての節点の需要量の和は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
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 # 需要
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
``````

## データ

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
What you can do with signing up
15