著者

櫻庭 セルソ 智 柳浦 睦憲

出版者

公益社団法人日本オペレーションズ・リサーチ学会

雑誌

オペレーションズ・リサーチ : 経営の科学 = [O]perations research as a management science [r]esearch (ISSN:00303674)

巻号頁・発行日

vol.57, no.6, pp.327-334, 2012-06-01

参考文献数

38

---

線形順序付け問題は,正方行列の行と列を同じ順列で並べ替え,下三角部分の値の合計を最小化する問題であり,古くから研究されている.この問題は,辺に重みのついた有向グラフから一部の辺を取り除いてすべての有向閉路を除去するとき,取り除いた辺の重みの合計を最小化するフィードバック辺集合問題と等価である.本稿では,この問題に対するさまざまな解法を,実用的解法を中心に紹介する.