一般化割当問題
$n$個の仕事$J=\{1,2,\dots,n\}$と$m$人のエージェント$I=\{1,2,\dots,m\}$に対して、仕事$j \in J$をエージェント$i \in I$に割当てたときのコスト$c_{ij}$と資源の要求量$a_{ij}(\ge 0)$、および各エージェント$i \in I$の利用可能資源量$b_i(\ge 0)$が与えられている。
それぞれの仕事を必ずいずれか1つのエージェントに割当てなければならず、また、各エージェントに割当てられた仕事の総資源要求量が、そのエージェントの利用可能資源量を超えないようにしなければいけない。このとき、コストの総和を最小にする割当を求めよ。
実行方法
usage
Signature: gap(cst, req, cap)
Docstring:
一般化割当問題
費用最小の割当を解く
入力
cst: エージェントごと、ジョブごとの費用のテーブル
req: エージェントごと、ジョブごとの要求量のテーブル
cap: エージェントの容量のリスト
出力
ジョブごとのエージェント番号リスト
python
from ortoolpy import gap
gap([[2, 2, 2], [1, 1, 1]], [[1, 1, 1], [1, 1, 1]], [2, 1])
結果
[0, 0, 1]
python
# pandas.DataFrame
from ortoolpy.optimization import Gap
Gap('data/gap.csv', [2,1])
| agent | job | cost | req | |
|---|---|---|---|---|
| 0 | 0 | 0 | 2 | 1 |
| 1 | 0 | 1 | 2 | 1 |
| 5 | 1 | 2 | 1 | 1 |