Project Selection Problem

• N個のプロジェクトがある

  • プロジェクトiをやると収入$r_i$が得られる

• M個の機械がある

  • 機械jを買うとコスト$c_j$が掛かる

• プロジェクトをやるためにはそのプロジェクトに必要な機械を買わなければならない

• 利益=収入-コストを最大化するにはどのプロジェクトを選べば良いか？

• 最小カット(最大流)で解ける

  • 

• 最小カットのカットは「辺を切る」ではない

  • 頂点の塗り分けと解釈すると理解しやすい
  • スタートと同じ色で塗られたプロジェクトが「選択したプロジェクト」
  • 同じ色で塗られたマシンが「購入されたマシン」
  • 
  • 図中の-pはrと読み替える
  • 

下記の解説は最小カットのカットは「辺を切る」ではないを理解する前に書いたのであまり良くない説明

• N個のプロジェクトがある

• M個の機械がある

• プロジェクトはいくつかの機械を必要とする

• プロジェクトpiを選ぶと収入r(pi)が得られる

• 必要な機械qjを買うとコストc(qj)が掛かる

• 利益-コストを最大化するにはどのプロジェクトを選べば良いか？

• 最小カット(最大流)で解ける

  • 

• 「あるプロジェクトが選ばれたなら、必要な機械を買わなければならない」と言う制約を無限大の辺で表現する

  • 右側か左側かどちらかを切らなければならない
  • プロジェクトの辺を切らないことを「プロジェクトの選択」と見る
  • 機械の辺を切ることを「機械の購入」と見る
  • プロジェクトを選択した(辺を切らない)なら、機械を購入する(辺を切る)必要がある
  • プロジェクトを選択しない=収入減、機械を買う=コスト、この和を最小化したい→最小カット
  • 

• 二択の選択肢から選ぶ問題とも解釈できる

  • LPとグラフと定式化

https://en.wikipedia.org/wiki/Max-flow_min-cut_theorem#Project_selection_problem 最大流