一般化割当問題

$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

データ

data/gap.csv