LoginSignup
2

More than 5 years have passed since last update.

組合せ最適化 - 典型問題 - 一般化割当問題

Last updated at Posted at 2015-07-10

典型問題と実行方法

一般化割当問題

$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

データ

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
2